CTJ-46 Explaining Stack in C

I am on a journey to finish C Programming and Memory Management — Full Course. To follow, copy the code and paste it into an Online C compiler on pythontutor.com. The name of the journey is CTJ. These are my public notes. This is the step CTJ-46; The aim is to explain the concept of the stack data structure as used on memory management.

As I work with/for ClickHouse, I’m making some references to the DB. As I enjoy Python, I’m making constant python-vs-c diffs.

• Initially, we’ve conceptualized memory as giant addressed array of bytes
• However, there is additional structuring into the two main additional regions: stack & heap
• In the runtine of the program, each function return, the stack frame is de-allocated

1. In the runtime of the program, each function call creates a new stack frame

• a stack frame stores the function’s full execution context:
• parameters passed in
• local variables
• return address (where to jump back when the function returns)
• saved frame pointer (link back to the caller’s frame)

1.1. 1 tangent: Dijkstra, goto, and why structured programming maps to the stack

• goto in C is intra-function only — jumps within the same frame, no push/pop
• Dijkstra’s 1968 letter “Go To Statement Considered Harmful” [1][3] argued:
• goto breaks the correspondence between code structure and execution structure
• structured programming’s three constructs map cleanly to the call stack:
• function call → push frame
• function return → pop frame
• if/while/for → stay in current frame
• irony: Linux kernel uses goto legitimately for cleanup — C has no defer [2]
• [1] https://dl.acm.org/doi/10.1145/362929.362947
• [2] https://www.kernel.org/doc/html/latest/process/coding-style.html#centralized-exiting-of-functions
• [3] https://feelingof.com/episodes/067/

2. Stack is a LIFO datastructure: last in, first out

• it consists of stack frames (also called activation records or call frames)
• each function call, a new frame is pushed onto the stack
• when the function returns, its frame is popped off the stack

Get Pavol Z. Kutaj’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

4. Let’s have an example

• the output is

• the addresses decrease — they go from high > low
• the stack grows “from the ceiling to the floor”
• let’s do the math, in ipython👇, the frame has 28 bytes

• for this particular function 4 bytes is the data, and 14 bytes is the constant
• return pointer
• frame pointer
• padding
• …

5. A ClickHouse stack trace is the same call stack — just a snapshot at the moment of error

• read bottom-to-top: frame 15 is the oldest caller, frame 0 is where the error happened
• same LIFO structure as the C example above
• The server doesn’t crash — it catches the exception, prints the trace, and keeps running

• Frame — numbered 0 (deepest/most recent) to N (oldest caller)
• Source file: line — where in the source code this call happens
• Function signature — C++ fully-qualified function name with namespace (DB::, Poco::)
• Address — memory address of the instruction in the compiled binary (.text segment — code, not stack data)

6. exercise

• 0x109cd0000 (~4.4 billion) — low region — .text segment — compiled machine code of my_func
• 0x16b625f9c (~6.1 billion) — high region — stack — where local_var was allocated at call time
• ~1.6 GB apart — completely different regions of virtual memory
• The ClickHouse trace addresses are the 0x109cd0000 kind — code addresses, not stack data
• memory is not just stack + heap — the full layout is

High addresses
┌──────────────┐
│    Stack     │  ← &local_var lives here (grows ↓)
├──────────────┤
│   (unused)   │
├──────────────┤
│    Heap      │  ← malloc'd memory (grows ↑)
├──────────────┤
│    .bss      │  ← uninitialized globals
├──────────────┤
│    .data     │  ← initialized globals
├──────────────┤
│    .text     │  ← my_func code lives here
├──────────────┤
│   (reserved) │
└──────────────┘
Low addresses