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:

/*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.

Because allocating items as an array is so common, we have a special function for it.

int *p = (int *) calloc(5, sizeof(int));

While allocating arrays with malloc() is simple and effective, it can be problematic. First off, malloc() makes no guarantee that memory allocated will be clean — it can be anything. For example, consider this simple program:

//allocate a 20 byte array
int * a = (int *) malloc(20 * sizeof(int));
int i;
for(i = 0; i < 20; i++){
  printf("%d\n",i);
}

What is the output of this program? We don't know. It's undefined. The allocated memory from malloc() can have any value, usually whatever value the memory used to have if it was previously allocated. If you don't believe me, try running and executing the program a few times, and you'll see that you can get widely different results.

The second problem with using malloc() is that it is a multi-purpose allocation tool. It is generally designed to allocate memory of a given size that can be used for both arrays and other data types. This means that to allocate an array of the right size, you have to perform an arithmetic computation, like 20 * sizeof(int), which is non-intuitive and reduces the readability of code.

To address these issues, there is a special purpose allocator that is a lot more effective for array allocation. It's calloc() or the counting allocator. It's usage is as follows.

//  The number of items 
//  to be allocated      --.
//                         |
//                         v
  int * a = (int *) calloc(20, sizeof(int));
//                                  ^
//                                  |      
//                            The size of each item

calloc() takes two arguments, the number of items needed and the size of each item. For an array, that is the length of the array, and the size is the sizeof() the array type, which is int in this case. Not only does calloc() make the array allocation more straight forward, it will also zero-out or clean the memory that is allocated. For example, this program will always print 0's.

//allocate a 20 byte array
int * a = (int *) calloc(20, sizeof(int));
int i;
for(i = 0; i < 20; i++){
  printf("%d\n",i); // 0 b/c calloc zeros out allocated memory
}

So far in this lesson we've discussed allocating basic types, but we can also dynamically allocate memory for other types, such as strings and structures. For example, consider the pair_t structure below:

typedef struct{
  int left;
  int right;
} pair_t;

Suppose we want an array of such structures, then we can use dynamic allocation using calloc() to allocate array of pair_t's just like we did to generate an array of int's.

pair_t * pairs = (pair_t *) calloc(10, sizeof(pair_t));

pairs[0].left  =  2;  //do assignment
pairs[0].right = 10;

As you can see, once the array is generated, we can access each individual pair_t using array indexing, and the array was allocated with enough memory for 10 pair_t strucutes we use the . operator to access each item.

This alocation is fine for many circumstances, but it can pose some subtle problems in certain situations. Suppose we wanted to keep track of which pairs have been set and which have not? Could we just look at the array of pairs and know this? We can't because calloc() will zero out all the pairs and we can't tell difference between a pair just stores to zeros and one that was not set. Another problem could occur if we want to be memory efficient. What if we only want to allocate the full pair_t struct as needed?

Adding an extra layer of redirection makes such tasks much easier. Essentially, we wish to construct an array of pointers to the desired type, or a pointer to a pointer, a double pointer. Instead of having an array of pair_t's, we have an array of pointers to pair_t's. Then we can know if the pair_t is set because either the pointer will be NULL or it will reference a pair_t, and we can allocate new pair_t's as needed. The allocation is as follows:

//     .-- Double Pointer -.          array of pair_t pointers
//     |                   |                      |
//     v                   v                      v
pair_t ** pairs = (pair_t **) calloc(10, sizeof(pair_t *));

pairs[0] = malloc(sizeof(pair_t)); //allocate memory for a new pair_t

pairs[0]->left  =  2; //do assignment
pairs[0]->right = 10;

While at first this might seem like a funky and unnecessary way of allocating structure types, but it is quite common in practice. It is often the case that you will need to store and reference a number of structure types, the amount of them is unknown ahead of time. Managing all this data requires careful programing and memory management. Keeping track of what has been allocated, what has been freed, and what resources are newly available are the key to designing good programs.

A common mistake when dealing with double pointers is poor deallocation. Let's extend the above example by modularizing the process of creating the array of pair pointers and the addition of a new pair into functions to simplify the code. This might look like below.

pair_t ** new_pairs(){
    pair_t ** pairs = (pair_t **) calloc(10, sizeof(pair_t *));
    return pairs;
}

pair_t * add_pair(pair_t ** pairs, int left , int right){
  int i;
  for(i=0;i<10;i++){
    if(pairs[i] == NULL){
      pairs[i] = malloc(sizeof(pair_t)); //allocate

      pairs[i]->left = left;//do asignment
      pairs[i]->right = right;

      return pairs[i]; //return the new pair
    }
  }  
  return NULL; //list full, return NULL for eror
}

int main(int argc, char * argv[]){
  pair_t ** pairs = new_pairs(); //create a new pair array

  add_pair(pairs, 2, 10); //assign a new pair
  add_pair(pairs, 0, 3); //assign a new pair
  //...
  // deallocate?
}

Now, the addition of a new pair is as simple as calling add_pair() which will find the first NULL pointer in the pairs array to do the insert. If the array is full, it returns NULL on error.

This is great! We've just generalized our double pointer array into a mini data structure that is memory efficient and easy to use. There's one problem though, how do we properly deallocate the double pointer to make sure we don't have a memory leak? The following will not work:

void delete_pairs(pair_t ** pairs){
   free(pairs); // memory leak!!!  
}

This will cause a memory leak because the index of pairs are pointers which may reference other allocated memory. You can't just free up the larger array without first deallocating any memory referenced from within the array. If you do, then the address of that memory will be lost, thus leaking the memory.

Instead, you have to be more careful and generate a code block to deallocate it properly.

void delete_pairs(pair_t ** pairs){
  int i;

  for(i=0;i<10;i++){
    if (pairs[i] != NULL){ //don't want to free(NULL), cause coredump
       free(pairs[i]); //free allocated memory within array
    }
  }

  free(pairs); //free array
}

As have been noted a number of times now, arrays and pointers are actually the same, mostly. The only difference is that when you declare an array, e.g., int array[10], the variable array is declared static, as in it cannot change unlike a declared pointer, e.g., int * p. However, we have seen how we can use the pointer to act like an array, such as below:

int a[5] = {10,20,30,40,50}; //inex is value
int * p = a; // (1)
p[0] = 5; //(2)
printf("%d\n", a[0]); //prints 5 !!

      STACK (1)         |        STACK  (2)
      .----.----.       |       .----.----.   
      | a  |  .-+--.    |       | a  |  .-+--.
      |----|----|  |    |       |----|----|  |
a[0]  |    | 10 |<-.    | a[0]  |    | 5  |<-.
      |    |    |<-.    |       |    |    |<-.
      |----|----|  |    |       |----|----|  |
a[1]  |    | 20 |  |    | a[1]  |    | 20 |  |
      |----|----|  |    |       |----|----|  |
      :    :    :  |    |       :    :    :  |
      .    .    .  |    |       .    .    .  |
      :    :    :  |    |       :    :    :  |
      |----|----|  |    |       |----|----|  |
a[4]  |    | 50 |  |    | a[4]  |    | 50 |  |
      |----|----|  |    |       |----|----|  |
      | p  |  .-+--'    |       | p  |  .-+--'
      '----'----'       |       '----'----'

We also took it one step further to demonstrate how the indexing function, e.g., p[i], is really de-reference using pointer arithmetic, p[i] = *(p+i)

int a[5] = {10,20,30,40,50}; 
int * p = a; // (1)
*(p+1) = 5; //(2)
printf("%d\n", a[1]); //prints 5 !!

      STACK (1)         |        STACK  (2)
      .----.----.       |       .----.----.   
      | a  |  .-+--.    |       | a  |  .-+--.
      |----|----|  |    |       |----|----|  |
a[0]  |    | 10 |<-.    | a[0]  |    | 10 |<-.
      |----|----|       |       |----|----|  |
a[1]  |    | 20 |<-.    | a[1]  |    | 5  |  | <- p+1
      |----|----|  |    |       |----|----|  |
      :    :    :  |    |       :    :    :  |
      .    .    .  |    |       .    .    .  |
      :    :    :  |    |       :    :    :  |
      |----|----|  |    |       |----|----|  |
a[4]  |    | 50 |  |    | a[4]  |    | 50 |  | 
      |----|----|  |    |       |----|----|  |
      | p  |  .-+--'    |       | p  |  .-+--'
      '----'----'       |       '----'----'

No surprises so far, but lets take a look a bit more at the pointer arithmetic and de-referencing. For one, an integer is 4 bytes in length, but when we add 1 to the pointer value of p we do not actually increase the pointer value by 1 but by 4 bytes to the start of the next integer. We can see this if we add the following line to the program:

printf("p: %p p+1: %p \n", p,p+1);

$ ./pointer_arithmetic 
5
p: 0x7fff585f5a10 p+1: 0x7fff585f5a14

Note that the pointer values of p and p+1 is 4 bytes difference. This is what we want it do and not reference a byte within the integer, but we should also be asking ourselves, what if we do want to reference the byte within the integer? To do this, we can take advantage of a peculiarity of pointers in that they can be arbitrarily cast to other pointer types.

Pointers are weird. You've seen that already, but now we are going to take a few more steps down the rabbit hole. First consider the program below:

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

  int a = 10;             //declare an integer
  char * p = (char *) &a; //save address of integer as char *

  int i;
  printf("0x");
  for(i=0;i<4;i++){
    printf("%02x",p[i]); //print the bytes of the integer in hex!
  }
  printf("\n");

}

The program assigns to p, a character pointer, the address of a, an integer. You should feel a bit dirty doing this. Having a char * reference an integer is wrong, right? It is wrong, but probably not for the reasons you think. It's actually perfectly reasonable with respect to pointers. A pointer is just a memory address. The memory address of an int or a char is the same size, 8-bytes, so who cares what it is called.

The type of the pointer does impact how we interpret the data the memory address references. When we say &a we are providing a memory address that references data for an integer. If we interpret that memory address as a char * instead, then we can treat those 4 bytes of the integer as 4 bytes of a character array.

If you follow the program further, we can now go ahead an interpret the individual bytes of the integer and print them out. To do so, we used hexadecimal, which you should recall, two hex-digits can represent one byte. After running the program, we get the following: (Note, we write '0x' as the leading part of hex digits to indicate that this is in hexadecimal.)

$ ./pointer_cast 
0x0a000000

Those are the bytes of the integer that stores 10. In hex, the hex-digit 'a' is ten, and we see a 0x0a in the output. However, it doesn't seem to be in the right place. It is at the front instead of the end. Wouldn't 0x00000000a make more sense? Sure, to us measly humans, but to computers, what does it matter if numbers are written forward and backward?

Back in the day, there were two major architecture for data representation.: Big Endian and Little Endian. The difference is the order of the bytes in building larger data elements. All major architectures we will use (except for one later in the course) uses Little Endian. In Little Endian, the least significant bytes come before the more significant bytes, which is backward from how humans read numbers.

To see this in action, let's do another example of pointer casting, this time with a larger integer value and one we can recognize more easily; my favorite number, 0xdeadbeef. Here's a program to print the individual bytes of that number:

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

  unsigned int a = 0xdeadbeef;    //hex number
  unsigned char * p = (unsigned char *) &a; 

  int i;
  printf("0x");
  for(i=0;i<4;i++){
    printf("%02x",p[i]);
  }
  printf("\n");

}

Now the output:

$ ./deadbeef 
0xefbeadde

All the bytes are there, just in the wrong order. This will become important later in the semester, but its useful to understand the underlying data model.