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

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
}

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.

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.

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.