Stack and Heap Memory

by Jenny Chen, Ruohao Guo

Overview

When a program is running, it takes up memory. Sometimes we are not even aware of the memory being allocated. In fact, every time you create a new variable, your program is allocating more memory for you to store that variable. This article focuses on two kinds of memories: stack and heap.

General Memory Layout

Each running program has its own memory layout, separated from other programs. The layout consists of a lot of segments, including:

stack: stores local variables
heap: dynamic memory for programmer to allocate
data: stores global variables, separated into initialized and uninitialized
text: stores the code being executed

In order to pinpoint each memory location in a program’s memory, we assign each byte of memory an “address”. The addresses go from 0 all the way to the largest possible address, depending on the machine. As the figure below, the text, data, and heap segments have low address numbers, while the stack memory has higher addresses.

By convention, we express these addresses in base 16 numbers. For instance, the smallest possible address is 0x00000000 (where the 0x means base 16), and the largest possible address could be 0xFFFFFFFF.

Stack

As shown above, the stack segment is near the top of memory with high address. Every time a function is called, the machine allocates some stack memory for it. When a new local variables is declared, more stack memory is allocated for that function to store the variable. Such allocations make the stack grow downwards. After the function returns, the stack memory of this function is deallocated, which means all local variables become invalid. The allocation and deallocation for stack memory is automatically done. The variables allocated on the stack are called stack variables, or automatic variables.

The following figures show examples of what stack memory looks like when the corresponding code is run:

1. Allocate variable a for main

2. Allocate b for main and store -3

3. Allocate c for main and store 12345

4. Allocate p for main and store address of b

5. Allocate variable a for hello and store 100

6. Deallocate the stack memory of hello and return 100 to main

7. Allocate d for main and store 100

8. Deallocate the stack memory of main and return 0

Since the stack memory of a function gets deallocated after the function returns, there is no guarantee that the value stored in those area will stay the same. A common mistake is to return a pointer to a stack variable in a helper function. After the caller gets this pointer, the invalid stack memory can be overwritten at anytime. The following figures demonstrate one example of such scenario. Assume there is a Cube class that has methods getVolume and getSurfaceArea, as well as a private variable width.

1. Allocate Cube c for CreateCube

2. Deallocate stack memory of CreateCube and return address of c

3. Allocate pointer c for main and store the returned value. Notice that the stack memory of CreateCube is overwritten

4. Allocate stack memory for getVolume and calculate volume using the width of c. Since the width of c is corrupted, the volume is also incorrect

5. Deallocate memory of getVolume. Allocate r for main to store the return value of getVolume

6. Allocate stack memory for getSurfaceArea and calculate surface area using the width of c. Similar to getVolume, the surface area calculated will be incorrect

7. Deallocate memory of getSurfaceArea. Allocate v for main to store the return value of getSurfaceArea

8. Deallocate the stack memory of main and return 0

These examples provide a simplified version of stack memory. In reality, a function’s stack stores more than just local variables. You can find out more about what exactly is in the stack by taking a computer architecture class. In addition, the above example could cause a segmentation fault when we are calling c->getVolume() or c->getSurfaceArea(). This is because if the value of c is invalid, then the machine can’t find the getVolume function associated with c. If this happens, this program will crash instead of producing incorrect values.

Heap

In the previous section we saw that functions cannot return pointers of stack variables. To solve this issue, you can either return by copy, or put the value at somewhere more permanent than stack memory. Heap memory is such a place. Unlike stack memory, heap memory is allocated explicitly by programmers and it won’t be deallocated until it is explicitly freed. To allocate heap memory in C++, use the keyword new followed by the constructor of what you want to allocate. The return value of new operator will be the address of what you just created (which points to somewhere in the heap).

The figures below demonstrate what happens in both stack and heap when the corresponding code is executed:

1. Allocate an integer with default value 0 on the heap, allocate p on main's stack to store the address of the integer

2. Allocate a Cube with default width 20 on the heap, allocate c1 on main's stack to store the address of the Cube

3. Allocate c2 on main's stack and store a copy of c1

4. Call method setLength on c2, changes the width of the Cube pointed by both c1 and c2

5. Deallocate stack memory of main and return 0

You may notice in the above example that even at the end of the program, the heap memory is still not freed. This is called a memory leak.

Memory leaks in small programs might not look like a big deal, but for long-running servers, memory leaks can slow down the whole machine and eventually cause the program to crash.

To free heap memory, use the key word delete followed by the pointer to the heap memory. Be careful about the memory you freed. If you try to use the pointers to those memory after you free them, it will cause undefined behavior. To avoid such issues, it is good practice to set the value of freed pointers to nullptr immediately after delete. Here is an example that correctly frees memory after using it.

1. Allocate a Cube width 20 on the heap, allocate a Cube pointer c on CreateCubeOnHeap's stack to store the address of the Cube

2. Deallocate stack memory for CreateCubeOnHeap and return the value of pointer c

3. Allocate cube on main's stack and store the returned pointer

4. Call method getVolume on cube, which calculates the volume to be 8000

5. Allocate double v to store the return value 8000

6. Deallocate the Cube pointed by cube, notice that cube is still pointing to invalid memory on heap

7. Set the value of cube to nullptr, which is 0

8. Deallocate the stack memory of main

In the figures above, you can see that heap memory are not allocated continuously from bottom to top. This is because unlike stack where the invalid memory is always at the bottom, the user can free heap memory that’s in between valid memories, causing fragmentations in the heap. In order to reuse memory efficiently, there are numerous heap allocation scheme that try to pick the “best” spot for you. You will learn more about memory allocation in a system programming class.