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

4. Let’s have an example

[embed]

• the output is

[embed]

• 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

[embed]

• 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

[embed]

• 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

[embed]

[embed]

• 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