Stack Overflow

A stack is the last in, first out (LIFO) buffer that you place data into while your program runs. LIFO means that the last thing you put in is always going to be the first thing you get back out. It stands that if you push 2 items on the stack, X and then Y, then the first thing you pop off the stack will be Y, and the next will be X.

When a function is called in code, the next instruction after the function call is stored on the stack, and any storage space that might be overwritten by the function call. The function might use up more stack by calling it’s own local variables. Once the function complete, it frees up the local variable stack space it used, and then returns to the previous function.

Here is one way to visualize, at a high level, the layout of your computer’s memory:

Using the above picture as reference, when code is run, a system will store initially all of the 0s and 1s an the “top” of your memory, so to speak. The OS will first load all of these 0’s and 1’s (otherwise known as the machine code) into one big chunk of memory at the top. So when you run code (./run or double-clicking in File Explorer), the machine code is loaded in first at the top.

Below that, it stores global variables. These are going to be any variables that are created in a program outside of main or any functions.

After that is the heap (moving downwards).

  • Example: anytime you use malloc, that memory ends up on the heap.

And finally, there is the stack at the bottom (moving upwards).

  • Example: anytime you use local variables in a function, that memory ends up on the stack

A stack overflow is when you use more and more memory by calling more and more functions, or using local variables, you use a lot of this stack memory.

If you keep allocating memory (malloc) over and over, without ever freeing that memory allocated, the heap will grow.

At some point the heap and stack memory will collide and overflow into one another. This is a stack overflow, which will inevitably lead to your program crashing.

In essence, a stack overflow is when you’ve used more memory for the stack than your program was supposed to. Consider a function X, which calls function Y, that then calls function Z, that then calls function X again. This might work without issue, but assuming a wrong input, it will cause these functions to go in that circle forever, until the computer recognizes that the stack is overblown.

This often happens when using recursions where termination has been forgotten (resulting in an infinite recursive call). If you’re writing recursively (e.g. your function calls itself), then you’ll need to be aware of this and use static or global variables to prevent infinite recursion.