IC221: Systems Programming (SP14)


Home Policy Calendar Syllabus Resources Piazza

Lecture 06: Memory Allocation and Program Layout

Table of Contents

1 Memory Model

So far in programming C, we haven't given a lot of thought to the variables we declare and what it actually means to declare a variable of a given type. Recall that in C the notion of a type and the amount of memory to store that type are strongly linked. For the basic types we've looked at so far, here are their memory requirements:

  • int : integer number : 4-bytes
  • short : integer number : 2-bytes
  • long : integer number : 8-bytes
  • char : character : 1-byte
  • float : floating point number : 4-bytes
  • double : floating point number : 8-bytes
  • void * : pointers : 8-bytes on (64 bit machines)

But, what does it mean for a type to require memory, and where does that memory come from and how is it managed? Understanding the memory model in C is vital to becoming a good programmer because there are situations where you have to use complex memory management to write effective programs. Simple mistakes can lead to programs with mysterious bugs that fail in inexplicable ways.

2 Local Memory Allocation on the Stack

When you declare a variable, you are actually stating to C that you need to create space for the data of that variable to exist. Consider a very simple example.

int a = 10;

The declaration of the integer a will allocate memory for the storage for an integer (4-bytes). We refer to the data stored in memory via the variable a.

Memory allocation refers to the process by which the program makes "space" for the storage of data. When you declare a variable of a type, enough memory is allocation locally to store data of that type. The allocation is local, occurring within the scope of the function, and when that function returns the memory is deallocated. This should be intuitive based on your experience with programming so far, you can't referenced a variable outside the scope of your function.

However with pointers in C, it's easy to make mistakes where your pointer references a memory address out of scope of the current function or even completely unallocated memory. As an example of a common mistake, consider the simple program below which has a function plus() which adds two numbers and returns a memory address for the result value.

int * plus(int a, int b){
  int c = a + b;
  return &c;    //return a reference to
                //locally declared c
}

int main(int argc, char * argv[]){
  int * p = plus(1,2);
  printf("%d\n",*p); //dereference return value
                     //to print an integer 
}

The function plus is declared to take two integers as arguments and return a pointer to an integer. Within the body of the function, the two integers are summed together, and the result in stored in c, a variable declared locally within the context of the function. The function then returns the memory address of c, which is assigned to the pointer value p in main.

What's the problem? The memory of c is deallocated once the function returns, and now p is referencing a memory address which is unallocated. The print statement, which deferences p, following the pointer to the memory address, may fail. The above code is bad, and you can also follow the reasoning with a stack diagram.

            plus(1,2)         return &c            printf("%d\n",*p)
             
(main)         |  (main)         |  (main)            |  (main)
.---.----.     |  .---.----.     |  .---.----.        |  .---.----.
| p |  .-+-X   |  | p |  .-+-X   |  | p |  .-+---.    |  | p |  .-+---.
'---'----'     |  '---'----'     |  '---'----'   |    |  '---'----'   |
               | -------------   | ------------  |    |               |
               |  (plus)         |  (plus)       |    |               |
               |  .---.---.      |  .---.---.    |    |               |
               |  | a | 1 |      |  | a | 1 |    |    |               |
               |  |---|---|      |  |---|---|    |    |               |
               |  | b | 2 |      |  | b | 2 |    |    |               |
               |  |---|---|      |  |---|---|    |    |               |
               |  | c | 3 |      |  | c | 3 | <--'    |            X--'
               |  '---'---'      |  '-------'
                
                c exists locally    returning a reference       When p is dereferenced
                in plus()           to c assined to p           it points to unallocated memory

First, in main(), p waits for the result of the call to plus(), which set's c. Once plus() returns, the value of p references a variable declared in plus(), but all locally declared variables in plus() are deallocated once plus() returns. That means, by the time the printf() is called and p is dereferenced, the memory address references unallocated memory, and we cannot guarantee that the data at that memory address will be what we expect.

2.1 The Stack

Another term for local memory allocation is stack allocation because the way programs track execution across functions is based on a stack. A stack is a standard ordred data structure, like a list, that has the property that the last item inserted on the stack is the first item that is removed. This is often referred to as LIFO data structure, last-in-first-out. A stack has two primary functions:

  • push : push an item on to the top of the stack
  • pop : pop an item off the top of the stack

The stack's top always references the last item pushed onto the stack, and the items below the top are ordered base on when they were pushed on. The most recently pushed items come first. This means when you pop items off the top stack, the next item becomes the next top, which maintains the LIFO principle.

The stack model (last-in-first-out) matches closely the model of function calls and returns during program execution. The act of calling a function is the same as pushing the called function execution onto the top of the stack, and, once that function completes, the results are returned popping the function off the stack.

Each function is contained within a structure on the stack called a stack frame. A stack frame contains all the allocated memory from variable deliberations as well as a pointer to the execution point of the calling function, the so called return pointer. A very common exploit in computer security is a buffer overflow attack where an attacker overwrite the return pointer such that when the function returns, code chosen by the attacker is executed.

To understand how function calls are modeled in the stack, we have nested function calls under addonetwo(), and which ever function is currently executing has the stack frame at the top of the stack and the calling function, where to the current function returns, is the stack frame next from top. When the current function returns, its stack frame is popped off the stack, and the calling function, now the top of the stack, continues executing from the point of function call.

int gettwo(){
   return 2;
} 

int getone(){
  return 1;
}

int addonetwo(){
  int one = getone();
  int two = gettwo();
  return one+two;
}

int main(){
  int a = func2();

}
            program executed     .------ top of stack
                                 v
                main()
push main         |      |     main()     |
                  |      '----------------' 

              addonetwo()
                  |
push addonetwo    |      |   addonetwo()  |
                  |      |     main()     |
                  |      '----------------'

               getone()
                  |
                  |      |     getone()   |
push getone       |      |   addonetwo()  |
                  |      |     main()     |
                  |      '----------------'

               return 1
pop               |      |   addonetwo()  |
                  |      |     main()     |
                  |      '----------------'

               gettwo()
                  |
                  |      |     gettwo()   |
push gettwo       |      |   addonetwo()  |
                  |      |     main()     |
                  |      '----------------'
          
               return 2
pop               |      |   addonetwo()  |
                  |      |     main()     |
                  |      '----------------'
              
           return  1 + 2 
pop               |      |     main()     |
                  |      '----------------'
            
             program exits

The act of pushing and popping functions onto the stack also affects the memory allocation. By pushing a function onto the stack, the computer is actually allocating memory for the function's local variables, and once that function returns, the function and its allocated memory is popped off the stack, deallocating it. This is why local declared variables are also called stacked variables.

Following the example from before we can now better understand why it fails by adding in the pushes and pops of the stack.

            *PUSH*            *POP*

            plus(1,2)         return &c            printf("%d\n",*p)
             
(main)         |  (main)         |  (main)            |  (main)
.---.----.     |  .---.----.     |  .---.----.        |  .---.----.
| p |  .-+-X   |  | p |  .-+-X   |  | p |  .-+---.    |  | p |  .-+---.
'---'----'     |  '---'----'     |  '---'----'   |    |  '---'----'   |
               | -------------   | ------------  |    |               |
               |  (plus)         |  (plus)       |    |               |
               |  .---.---.      |  .---.---.    |    |               |
               |  | a | 1 |      |  | a | 1 |    |    |               |
               |  |---|---|      |  |---|---|    |    |               |
               |  | b | 2 |      |  | b | 2 |    |    |               |
               |  |---|---|      |  |---|---|    |    |               |
               |  | c | 3 |      |  | c | 3 | <--'    |            X--'
               |  '---'---'      |  '-------'
                
             Pusing plus()           The return of plus()      When p is dereferenced          
             onto the stack          pops it off the stack     in the print, p now 
             allocates memory        unallocated all stack     references unallocated
             for c                   variables including c     memory

3 Global Memory Allocation on the Heap

Just because the sample program with plus() from the previous section doesn't work properly when returning a memory reference, it does not mean you cannot write functions that return a memory reference. What is needed is a different allocation procedure for global memory which is not deallocated automatically when functions return and thus remains in scope for the entirety of the program execution.

In fact, you have already seen how to do this in C++ when you using the new construct. When you call new for some structure, what is actually going on? Consider the small code snippet below:

Node * node = new Node();

The local variable declaration is for the variable node, but that's just a pointer to some memory. The variable node, itself, is declared on the stack and has enough memory to store a memory address. The value of that memory address is set by the return of the call new Node(). The new function will automatically allocate enough memory to store a Node structure and the node variable now references that memory. But, where does this new memory come from?

If you think about it, the memory cannot have been allocated on the stack because it is memory being returned from a function, the new function. As we've seen previously, if a function returns a local reference of a variable declared on the stack, that memory is automatically deallocated when the function returns. Instead, this memory must have been allocated somewhere else, and it is. The new function performs a dynamic memory allocation in global memory that is not associated with scope of functions or the stack. It is instead allocating on the heap.

3.1 The heap, malloc() and free()

The global memory region for a program is called the heap, which is a fragmented data structure where new allocation try and fit within unallocated regions. Whenever a program needs to allocate memory globally or in a dynamic way, that memory is allocated on the heap, which is shared across the entire program irrespective of function calls.

In C the new function is called malloc(), or memory allocator. The malloc() function takes the number of bytes to be allocated as its argument, and it returns a pointer to a memory region on the heap of the requested byte-size. Here is a code snippet to allocate memory to store an integer on the heap:

//                           .--- Allocate sizeof(int) number of bytes 
//                           v
 int * p = (int *) malloc(sizeof(int));
//            ^
//            '-- Cast to a integer pointer

First, to allocate an integer on the heap, we have to know how big an integer is, that is, what size is it, which we learn via sizeof() macro. Since an int is 4 byes in size, malloc() will allocate 4 bytes of memory on the heap in which an integer can be stored. malloc() then returns the memory address of the newly allocated memory, which is assigned to p. Since malloc() is a general purpose allocation tool, just allocating bytes which can be used to store data generally, we have to cast the resulting pointer value to the right type, int *. If we don't, the program won't fail, but you will get a compiler warning.

We can now use p like a standard pointer as before; however, once we're done with p we have to explicitly deallocate it. Unlike stack based memory allocations which are implicitly deallocated when functions return, there is no way for C to know when you are done using memory allocated on the heap. C does not track references, like Java, so it can't perform garbage collection; instead, you, the programmer, must indicate when you're done with the memory by freeing. The deallocation function is free() (equivalent to delete in C++), which takes a pointer value as input and "frees" the referenced memory on the heap.

int * p = (int *) malloc(sizeof(int));

//do something with p

free(p); //<-- deallocate p

With all of that, we can now complete the plus() program to properly return a memory reference to the result.

int * plus(int a, int b){ 
  int *p = (int *) malloc(sizeof(int)); //allocate enough space for 
  *p = a + b;                   //for an integer
  return p;  //return pointer

}

int main(int argc, char * argv[]){
  int * p = plus(1,2); //p now references memory on the heap
  printf("%d\n",*p); 
  free(p); //free allocated memory
}

3.2 Memory Leaks and other Memory Violations

In C (and C++), the programer is responsible for memory management, which includes both the allocation and deallocation of memory. As a result, there are many mistakes that can be made, which is natural considering that all programers make mistakes. Perhaps the most common mistake is a memory leak, where heap allocated memory is not freed. Consider the following program.

int main(int argc, char * argv[]){
  int i, * p;

  for(i=0;i>100;i++){
    p = (int *) malloc(sizeof(int));
    *p = i;
  }

}

At the malloc, on Line 5, the returned pointer to newly allocated memory is overwriting the previous value of p. There is no free() occuring, and once the previous pointer value is overwritten, there is no way to free that memory. It is considered lost, and the above program has a memory leak. Memory leaks are very bad, and over time, can cause your program to fail.

Another common mistake is dereferencing a dangling pointer. A dangling poiner is when a pointer value once referenced allocated memory, but that memory has seen been dealocated. We'e seen an example of this already in the plus() program, but it can also occur for heap allocations.

int main(int argc, char * argv[]){
  int *p = (int *) malloc(sizeof(int));
  //... code
  free(p);
  //... code  
  *p = 10;
}

Once p has been freed, the memory referenced by the p's value can be reclaimed by other allocations. At the point where p is dereferenced for the assignment, it might be the case that you are actually overwriting memory for some other value, and corrupting your program. Once memory is freed, it should never be dereferenced. These kinds of memory violations can lead to the dreaded SEGFAULT.

Another, common mistake with memory allocation is a double free. The heap allocation functions maintain special data structures so that it is easy to find unallocated memory and reallocate for future malloc() calls. If you call free() twice on a pointer, you will corrupt that process, result in a core dump or some other very scary error.

4 Program Layout: Stack vs. Heap

Now that you understand the two different memory allocation procedures, let's zoom out and take a larger look at how memory in programs is managed more generally. Where is the stack? Where is the heap? How do they grow or shrink?

To answer these questions, you first need to think of a program as a memory profile. All information about a program, including the actual binary code and variables all are within the memory layout of a program. When executing, the Operating System will manage that memory layout, and a snapshot of that memory and the current execution point basically defines a program. This allows the operating system to swap in and out programs as needed.

On 64-bit machines, the total available memory addresses are from 0 to 264-1. For a program, the top and bottom of the address space are what is important. We can look at the program's memory layout in diagram form:

     2^64-1--->  .----------------------.
High Addresses   |      Enviroment      |
                 |----------------------|
                 |                      |   Functions and variable are declared
                 |         STACK        |   on the stack.
base pointer ->  | - - - - - - - - - - -|
                 |           |          |
                 |           v          |
                 :                      :
                 .                      .   The stack grows down into unused space
                 .         Empty       .   while the heap grows up. 
                 .                      .
                 .                      .
                 :                      :
                 |           ^          |
                 |           |          |
 break point ->  | - - - - - - - - - - -|   Dynamic memory is declared on the heap
                 |          HEAP        |
                 |                      |
                 |----------------------|
                 |          BSS         |   The compiled binary code is down here as
                 |----------------------|   well as static and initialzed data
                 |          Data        |
                 |----------------------|
Low Addresses    |          Text        |
      0 ----->   '----------------------'  

At the higher addresses is the stack and at the lower address is the heap. The two memory allocation regions grow into the middle of the address space, which is unused and unallocated. In this way, the two allocations will not interfere with each other. The stack base pointer is the current top of the stack, and as functions are called and returned, it will shift appropriately. The break point refers to the top of the programs data segment, which contains the heap. As the heap fills up, requirement more space, the break is set to higher addresses.

You should note that this memory layout is virtual. From the program's perspective it has access to the entire address range, but in reality, this might not be the case because the program is sharing physical memory with other programs, including the operating system. How that process works is a discussion for another class.

4.1 Memory Mapping and Dynamic Libraries

Between the break point and the base pointer is unallocated memory, but it may not be unused. This region can be memory mapped, which is the process of loading data directly from files into memory. As the programmer, you can directly memory map files, but often this is done automatically for you when you read and write files.

Another common use for the middle addresses is the loading of dynamic shared libraries. When you make a call to a function like printf() or malloc(), the code for those functions exist in shared libraries, the standard C library, to be precise. Your program must run that code, but the operating system doesn't want to have load more code into memory than needed. Instead, the O.S. loads shared libraries dynamically, and when it does so, it maps the necessary code into the middle address spaces.

4.2 Address Space Randomization

A final note about program memory address is that it is not consistent across runs. Take a look at the very simple program:

#+NAME random.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char * argv[]){
  int a;
  printf("0x%p\n",&a); //print the address of a                                                                                                                        
}

All this program does is print the address of the statically declared variable a. With your knowledge of the memory address layout, you could probably say with confidence that the address value should be a relatively large number, but you might also expect that it would be consistent across runs of the program.

#> for i in `seq 1 1 10`; do ./random; done
0x0x7fff58e0cafc
0x0x7fff50fffafc
0x0x7fff59a6dafc
0x0x7fff508c3afc
0x0x7fff533c8afc
0x0x7fff539a9afc
0x0x7fff528c6afc
0x0x7fff50984afc
0x0x7fff52f13afc
0x0x7fff5c97aafc

In fact, it is not consistent. While the addresses are relatively high in the address space, there least significant bits are quite random. This is on purpose, and for security purposes. The stack values also contain important pointers to next bit of code that should be executed, this is how program knows how to return to the previous execution prior to the function call. In a buffer overflow attack, the attacker overwrites the return pointer allowing code to be executed of the attacker's choosing, which can be exploit code. In order for the attack to be successful, the attacker must know exactly where in the program to set the return pointer, but if the addresses are randomized, this because a much more difficult tasks. Which is why the address space is randomized.