Edited By: Prof. Garth Santor

Every computer program, regardless of the language, requires a workbench to keep track of function calls and variables. Luckily, the kernel allocates space for each process when launched, allowing each program to have its own separate workbench. This process space is made up of different sections, and we will mainly look at the stack and the heap.

The stack is a location in ram that stores variables and function calls in a contiguous manner. This is important because it means that the program needs to know exactly how much memory to allocate for each variable. Which also means that we cannot store dynamic-sized memory on the stack. All sizes must be known upon compile time. We also cannot get rid of (deallocate) memory in any order that we like, we’d have to wait for that block to be popped back from the stack in the opposite order it came in.

The heap is also a location in RAM, but you can store variables in any location that the kernel allows, in no specific order. Meaning that we can literally throw any element size, anywhere (that the processor allows). It also means that we can get rid of (deallocate) our memory in any order we like.

To visualize this, let’s begin with a simple C program:


int main() {
   int i = 42;
   int iArr [3];
   iArr[0] = 41;
   iArr[1] = 42;
   iArr[2] = 43;
   return EXIT_SUCCESS;
}

Since an int is 4 bytes, i is allocated at 0x00AFFB54 with 4 bytes of memory, going from 0x00AFFB54 to 0x00AFFB58 (1 hex value is 4 bits/a nibble).

As for iArr, it starts at 0x00AFFB58 and allocates three 4-byte memory locations. It’s important to note that the array size is a constant. You cannot provide a variable as an array size, as the program would not be able to know how much stack memory to allocate before moving on to the next variable.

Because this memory is contiguous, we cannot deallocate i before deallocating iArr. It also means that we cannot change the size of iArr, because other memory would be allocated right after it.

So how do we accomplish dynamic memory allocations? This is where the heap comes in.

Assuming we have the following code:


int main() {
   int i = 3;
   int* ptr1 = malloc(i * sizeof(int));
   ptr1[0] = 41;
   ptr1[1] = 42;
   ptr1[2] = 43;
   int* ptr2 = malloc(2 * sizeof(int));
   ptr2[0] = 41;
   ptr2[1] = 42;
   free(ptr1);
   free(ptr2);
   return EXIT_SUCCESS;
}

In this case, i is allocated on the stack, and so are the pointers ptr1 and ptr2. The interesting thing that happened here is that the pointers are storing a heap memory address, provided by the function malloc (memory allocation).

Heap allocations are unmanaged, meaning that if ptr1 is popped (deallocated) from the stack, the referenced location on the heap will not be deallocated. If free() is not called on unreferenced heap locations, a memory leak will occur.

References

Lippman, Stanley; Lajoie, Josee; Moo, Barbara - C++ Primer
Schildt, Herbert - The Complete C Reference
Santor, Garth - Program Memory Layout

The Heap and the Stack

Edited By: Prof. Garth Santor

References