How exactly does the callstack work?

Question

I'm trying to get a deeper understanding of how the low level operations of programming languages work and especially how they interact with the OS/CPU. I've probably read every answer in every stack/heap related thread here on Stack Overflow, and they are all brilliant. But there is still one thing that I didn't fully understand yet.

Consider this function in pseudo code which tends to be valid Rust code ;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

This is how I assume the stack to look like on line X:

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

Now, everything I've read about how the stack works is that it strictly obeys LIFO rules (last in, first out). Just like a stack datatype in .NET, Java or any other programming language.

But if that's the case, then what happens after line X? Because obviously, the next thing we need is to work with a and b, but that would mean that the OS/CPU (?) has to pop out d and c first to get back to a and b. But then it would shoot itself in the foot, because it needs c and d in the next line.

So, I wonder what exactly happens behind the scenes?

Another related question. Consider we pass a reference to one of the other functions like this:

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

From how I understand things, this would mean that the parameters in doSomething are essentially pointing to the same memory address like a and b in foo. But then again this means that there is no pop up the stack until we get to a and b happening.

Those two cases make me think that I haven't fully grasped how exactly the stack works and how it strictly follows the LIFO rules.

Solution 1

The call stack could also be called a frame stack.
The things that are stacked after the LIFO principle are not the local variables but the entire stack frames ("calls") of the functions being called. The local variables are pushed and popped together with those frames in the so-called function prologue and epilogue, respectively.

Inside the frame the order of the variables is completely unspecified; Compilers "reorder" the positions of local variables inside a frame appropriately to optimize their alignment so the processor can fetch them as quickly as possible. The crucial fact is that the offset of the variables relative to some fixed address is constant throughout the lifetime of the frame - so it suffices to take an anchor address, say, the address of the frame itself, and work with offsets of that address to the variables. Such an anchor address is actually contained in the so-called base or frame pointer which is stored in the EBP register. The offsets, on the other hand, are clearly known at compile time and are therefore hardcoded into the machine code.

This graphic from Wikipedia shows what the typical call stack is structured like¹:

Add the offset of a variable we want to access to the address contained in the frame pointer and we get the address of our variable. So shortly said, the code just accesses them directly via constant compile-time offsets from the base pointer; It's simple pointer arithmetic.

Example

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org gives us

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

.. for main. I divided the code into three subsections. The function prologue consists of the first three operations:

• Base pointer is pushed onto the stack.
• The stack pointer is saved in the base pointer
• The stack pointer is subtracted to make room for local variables.

Then cin is moved into the EDI register² and get is called; The return value is in EAX.

So far so good. Now the interesting thing happens:

The low-order byte of EAX, designated by the 8-bit register AL, is taken and stored in the byte right after the base pointer: That is -1(%rbp), the offset of the base pointer is -1. This byte is our variable c. The offset is negative because the stack grows downwards on x86. The next operation stores c in EAX: EAX is moved to ESI, cout is moved to EDI and then the insertion operator is called with cout and c being the arguments.

Finally,

• The return value of main is stored in EAX: 0. That is because of the implicit return statement. You might also see xorl rax rax instead of movl.
• leave and return to the call site. leave is abbreviating this epilogue and implicitly
  • Replaces the stack pointer with the base pointer and
  • Pops the base pointer.

After this operation and ret have been performed, the frame has effectively been popped, although the caller still has to clean up the arguments as we're using the cdecl calling convention. Other conventions, e.g. stdcall, require the callee to tidy up, e.g. by passing the amount of bytes to ret.

Frame Pointer Omission

It is also possible not to use offsets from the base/frame pointer but from the stack pointer (ESB) instead. This makes the EBP-register that would otherwise contain the frame pointer value available for arbitrary use - but it can make debugging impossible on some machines, and will be implicitly turned off for some functions. It is particularly useful when compiling for processors with only few registers, including x86.

This optimization is known as FPO (frame pointer omission) and set by -fomit-frame-pointer in GCC and -Oy in Clang; note that it is implicitly triggered by every optimization level > 0 if and only if debugging is still possible, since it doesn't have any costs apart from that. For further information see here and here.

---

¹ As pointed out in the comments, the frame pointer is presumably meant to point to the address after the return address.

² Note that the registers that start with R are the 64-bit counterparts of the ones that start with E. EAX designates the four low-order bytes of RAX. I used the names of the 32-bit registers for clarity.

Solution 2

Because obviously, the next thing we need is to work with a and b but that would mean that the OS/CPU (?) has to pop out d and c first to get back to a and b. But then it would shoot itself in the foot because it needs c and d in the next line.

In short:

There is no need to pop the arguments. The arguments passed by caller foo to function doSomething and the local variables in doSomething can all be referenced as an offset from the base pointer.
So,

• When a function call is made, function's arguments are PUSHed on stack. These arguments are further referenced by base pointer.
• When the function returns to its caller, the arguments of the returning function are POPed from the stack using LIFO method.

---

In detail:

The rule is that each function call results in a creation of a stack frame (with the minimum being the address to return to). So, if funcA calls funcB and funcB calls funcC, three stack frames are set up one on top of the another. When a function returns, its frame becomes invalid. A well-behaved function acts only on its own stack frame and does not trespass on another's. In another words the POPing is performed to the stack frame on the top (when returning from the function).

The stack in your question is setup by caller foo. When doSomething and doAnotherThing are called, then they setup their own stack. The figure may help you to understand this:

Note that, to access the arguments, the function body will have to traverse down (higher addresses) from the location where the return address is stored, and to access the local variables, the function body will have to traverse up the stack (lower addresses) relative to the location where the return address is stored. In fact, typical compiler generated code for the function will do exactly this. The compiler dedicates a register called EBP for this (Base Pointer). Another name for the same is frame pointer. The compiler typically, as the first thing for the function body, pushes the current EBP value on to the stack and sets the EBP to the current ESP. This means, once this is done, in any part of the function code, argument 1 is EBP+8 away (4 bytes for each of caller's EBP and the return address), argument 2 is EBP+12(decimal) away, local variables are EBP-4n away.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

Take a look at the following C code for the formation of stack frame of the function:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

When caller call it

MyFunction(10, 5, 2);  

the following code will be generated

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

and the assembly code for the function will be (set-up by callee before returning)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp
 

---

References:

• Function Call Conventions and the Stack.
• Frame Pointer and Local Variables.
• x86 Disassembly/Functions and Stack Frames.

Solution 3

Like others noted, there is no need to pop parameters, until they go out of scope.

I will paste some example from "Pointers and Memory" by Nick Parlante. I think the situation is a bit more simple than you envisioned.

Here is code:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

The points in time T1, T2, etc. are marked in the code and the state of memory at that time is shown in the drawing:

Solution 4

Different processors and languages use a few different stack designs. Two traditional patterns on both the 8x86 and 68000 are called the Pascal calling convention and the C calling convention; each convention is handled the same way in both processors, except for the names of the registers. Each uses two registers to manage the stack and associated variables, called the stack pointer (SP or A7) and the frame pointer (BP or A6).

When calling subroutine using either convention, any parameters are be pushed on the stack before calling the routine. The routine's code then pushes the current value of the frame pointer onto the stack, copies the current value of the stack pointer to the frame pointer, and subtracts from the stack pointer the number of bytes used by local variables [if any]. Once that is done, even if additional data are pushed onto the stack, all local variables will be stored at variables with a constant negative displacement from the stack pointer, and all parameters that were pushed on the stack by the caller may be accessed at a constant positive displacement from the frame pointer.

The difference between the two conventions lies in the way they handle an exit from subroutine. In the C convention, the returning function copies the frame pointer to the stack pointer [restoring it to the value it had just after the old frame pointer was pushed], pops the old frame pointer value, and performs a return. Any parameters the caller had pushed on the stack before the call will remain there. In the Pascal convention, after popping the old frame pointer, the processor pops the function return address, adds to the stack pointer the number of bytes of parameters pushed by the caller, and then goes to the popped return address. On the original 68000 it was necessary to use a 3-instruction sequence to remove the caller's parameters; the 8x86 and all 680x0 processors after the original included a "ret N" [or 680x0 equivalent] instruction which would add N to the stack pointer when performing a return.

The Pascal convention has the advantage of saving a little bit of code on the caller side, since the caller doesn't have to update the stack pointer after a function call. It requires, however, that the called function know exactly how many bytes worth of parameters the caller is going to put on the stack. Failing to push the proper number of parameters onto the stack before calling a function which uses the Pascal convention is almost guaranteed to cause a crash. This is offset, however, by the fact that a little extra code within each called method will save code at the places where the method is called. For that reason, most of the original Macintosh toolbox routines used the Pascal calling convention.

The C calling convention has the advantage of allowing routines to accept a variable number of parameters, and being robust even if a routine doesn't use all the parameters that are passed (the caller will know how many bytes worth of parameters it pushed, and will thus be able to clean them up). Further, it isn't necessary to perform stack cleanup after every function call. If a routine calls four functions in sequence, each of which used four bytes worth of parameters, it may--instead of using an ADD SP,4 after each call, use one ADD SP,16 after the last call to cleanup the parameters from all four calls.

Nowadays the described calling conventions are considered somewhat antiquated. Since compilers have gotten more efficient at register usage, it is common to have methods accept a few parameters in registers rather than requiring that all parameters be pushed on the stack; if a method can use registers to hold all the parameters and local variables, there's no need to use a frame pointer, and thus no need to save and restore the old one. Still, it's sometimes necessary to use the older calling conventions when calling libraries that was linked to use them.

Solution 5

There are already some really good answers here. However, if you are still concerned about the LIFO behavior of the stack, think of it as a stack of frames, rather than a stack of variables. What I mean to suggest is that, although a function may access variables that are not on the top of the stack, it is still only operating on the item at the top of the stack: a single stack frame.

Of course, there are exceptions to this. The local variables of the entire call chain are still allocated and available. But they won't be accessed directly. Instead, they are passed by reference (or by pointer, which is really only different semantically). In this case a local variable of a stack frame much further down can be accessed. But even in this case, the currently executing function is still only operating on its own local data. It is accessing a reference stored in its own stack frame, which may be a reference to something on the heap, in static memory, or further down the stack.

This is the part of the stack abstraction that makes functions callable in any order, and allows recursion. The top stack frame is the only object that is directly accessed by the code. Anything else is accessed indirectly (through a pointer that lives in the top stack frame).

It might be instructive to look at the assembly of your little program, especially if you compile without optimization. I think you will see that all of the memory access in your function happens through an offset from the stack frame pointer, which is the how the code for the function will be written by the compiler. In the case of a pass by reference, you would see indirect memory access instructions through a pointer that is stored at some offset from the stack frame pointer.

View more solutions

Comments

[VoidStar]

LIFO only matters for reserving space on the stack. You can always access any variable that is at least on your stack frame (declared inside the function) even if it is under a lot of other variables

[HolyBlackCat]

In other words, LIFO means you can add or remove elements only at the end of the stack, and you can always read/change any element.

[Peter - Reinstate Monica]

Why don't you disassemble a simple function after compiling with -O0 and look at the generated instructions? It's pretty, well, instructive ;-). You'll find that the code makes good use of the R part of the RAM; it accesses addresses directly at will. You can think of a variable name as an offset to an address register (the stack pointer). As the others said, the stack is just LIFO with respect to stacking (good for recursion etc.). It's not LIFO with respect to accessing it. Access is completely random.

[Crowman]

You can make your own stack data structure using an array, and just storing the index of the top element, incrementing it when you push, decrementing it when you pop. If you did this, you'd still be able to access any individual element in the array at any time without pushing or popping it, just like you always can with arrays. Approximately the same thing is happening here.

[haccks]

@PaulGriffiths; Good explanation.

[Christoph]

Thank you all for the great comments. You helped me to get a far better understanding of such low level things. You rock!

[pjc50]

Further note: in C at least, the compiler isn't obliged to put variables on the stack at all. The optimizer may keep them in registers. It may also place them on the stack in a different order. Also, take a look at the "Forth" language and its stack-orientated programming.

[usr]

A single stack frame is a mostly unstructured memory area under the sole control of the compiler. There are no rules that the compiler has to obey inside of a single frame. It can violate "LIFO order" and legally scribble over bytes as it pleases. The structure the stack has mostly comes from the requirement that many different languages need to interoperate and call each other (using a common calling convention).

[Harry Johnston]

To provide some historical perspective: when the stack was first invented it was indeed used only in a LIFO manner; you pushed data to the stack to save it while you did something else, popped it when you were done. So, in those days, how did you use the stack to store local variables? Generally, you didn't! Local variables lived in static memory, and yes, that meant most procedures weren't re-entrant. And then stack frames were invented, and there was general rejoicing. :-)

[Keith Thompson]

The C standard doesn't even mention the word "stack". A contiguous stack like the one being discussed is certainly the most common way to implement C's memory model, but it's not the only one. There have been C compilers that allocate memory for function calls from the heap, or something like it, so that the in-memory ordering of frames for successive calls is entirely arbitrary.

[mgarciaisaia]

You don't stack variables, but frames :)

[Christopher Barber]

Also note that for your example, some calling conventions won't even use the call stack to store or pass those values but will simply use registers.

[user3629249]

Generally, a stack pointer starts at the high address of the stack and grows toward lower addresses as things are pushed on the stack. Things are pushed on the stack in the order they are encountered, so the top entry on the stack will be '1' the next entry on the stack(at a lower address) will be '2' and so on.

[Siyuan Ren]

Basically, the naming of stack/heap is unfortunate. They bear little resemblance to stack and heap in data structures' terminology, so calling them the same is very confusing.

[Christoph]

@PeterMortensen well, it was written in a way to draw a specific scenario. As I said, I had read through pretty much everything I found about the topic but just couldn't find exactly those missing bits. People gave great answers here so I think everyone should be happy :)

[Justin]

IMO the best way to properly understand the stack and calling conventions is to write some assembly.

[Suraj Jain]

@Christoph May , I know what did you meant by "But then again this means that there is no pop up the stack until we get to a and b happening." I do not quite get it.

[Peter Cordes]

From a link-only answer: this blog post (cryptroix.com/2016/10/16/journey-to-the-stack) is fairly good. It uses Python as pseudo-code for simple asm functions (like you might find in C compiler output), and assumes a stack-args calling convention (modern calling conventions pass args in registers)

[Christoph]

Great answer. The thing with addressing the data by offsets was the missing bit for me :)

[Christoph]

Thank you for your answer. Also the links are really cool and help me to shed more light into the never ending question of how computers actually work :)

[Christoph]

Great visual explanation. I googled and found the paper here: cslibrary.stanford.edu/102/PointersAndMemory.pdf Really helpful paper!

[kasperd]

I think there is a minor mistake in the drawing. The frame pointer would have to be on the other side of the return address. Leaving a function is usually done as follows: move stack pointer to the frame pointer, pop the callers frame pointer from the stack, return (i.e. pop the callers program counter / instruction pointer from the stack.)

[Voo]

kasperd is absolutely right. You either don't use the frame pointer at all (valid optimization and particularly for register-starved architectures such as x86 extremely useful) or you use it and store the previous one on the stack - usually right after the return address. How the frame is set up and removed depends to a great deal on the architecture and ABI. There are quite a few architectures (hello Itanium) where the whole thing is.. more interesting (and there are things like variable sized argument lists!)

[Riking]

@Christoph I think you're approaching this from a conceptual point of view. Here's a comment that will hopefully clear this up - The RTS, or RunTime Stack, is a bit different from other stacks, in that it's a "dirty stack" - there isn't actually anything preventing you from looking at a value that isn't on the top. Notice that in the diagram, the "Return Address" for the green method - which is needed by the blue method! is after the parameters. How does the blue method get the return value, after the previous frame was popped? Well, it's a dirty stack, so it can just reach in and grab it.

[Siyuan Ren]

Frame pointer is actually not needed because one can always use offsets from the stack pointer instead. GCC targeting x64 architectures by default uses stack pointer, and frees up rbp to do other work.

[Christoph]

Wow! Can I borrow your brain for a week or so. Need to extract some nitty-gritty stuff! Great answer!

[Peter Cordes]

@Siyuan: What actually enables -fomit-frame-pointer to be on by default is that exception-handling can still be done. i.e. unwindind the stack like a debugger's backtrace. The amount of stack space each function reserves on the stack is stored in the .eh_frame_hdr section, or something like that (see the ABI doc for details). -fomit-frame-pointer has been the the default for 32bit for a few gcc versions now, because things are done the same way there.

[Peter Cordes]

@Riking: you're mixed up, and/or the diagram is confusing (or even wrong?). The ret instruction only works when the stack pointer is pointing directly at the return address. Return values aren't stored on the stack at all (functions return values in rax, or rdx:rax). The dirty stack thing is a good point, though: it's used for getting function args from before the return address. Oh, I think I figured it out: the stack is growing upwards, which is the opposite of how Intel manuals show things. Also, showing the "top of stack" at the top is wrong in that case.

[Columbo]

@PeterCordes If return values aren't stored on the stack, what happens if I return a large struct without copy elision being applicable?

[Peter Cordes]

@Columbo: In most calling conventions, the caller passes a pointer as a hidden first parameter. The callee stores the return value in the pointed-to space. Consult the specific ABI doc for details (links on the x86 tag wiki for that architecture). examples: In i386 SysV, even a small struct is returned this way, but amd64 SysV packs structs up to 128b into rdx:rax. (As long as the members are all integer). There are alternatives, like leaving it in a temporary on the stack. Hidden pointer can save a copy in cases where the caller can pass a pointer to the final dest.

[Columbo]

@PeterCordes So return values are stored on the stack in some situations, namely when copy elision (which is what you described) does not apply.

[Peter Cordes]

@Columbo: For x86: only if that's where the caller decides to put the scratch space. It's just passing a pointer to one of its locals. It would be totally bogus to label a certain spot on the stack as the spot for the return value. It's on the stack because that's where the caller decided to put it (instead of passing a pointer to the middle of an array, or to a global, or to some space it just malloced, or whatever), not because the calling convention required it.

[Suraj Jain]

Sir , I am having this doubt for a long time. If in my function I write if (g==4) then int d = 3 and g I take input using scanf after that I define another variable int h = 5. Now , how does the compiler now give d = 3 space in the stack. How does the offset done because if g is not 4 , then there would be no memory for d in the stack and simply offset would be given to h and if g == 4 then offset will be first for g and then for h . How does compiler do that at compile time , it does not know our input for g.

[Suraj Jain]

What Do You Mean By "pushes the current EBP value onto the stack" and also does stack pointer is stored in register or that too occupies a position in stack ... i am little confused

[Suraj Jain]

And Shouldn't that be *[ebp + 8] not [ebp + 8] .?

[haccks]

@Suraj Jain; Do you know what is EBP and ESP ?

[Suraj Jain]

Where does the frame and stack pointer stored in the stack itself or anywhere else ?

[Suraj Jain]

esp is stack pointer and ebp is base pointer. If i have some miss knowledge , please kindly correct it.

[Columbo]

@SurajJain The frame is large enough to handle all possible paths inside the function.

[haccks]

EBP and ESP both are registers. EBP stores base pointer and EBP stores stack pointer which always point to the top of the stack. ebp stores the base pointer of caller function. When caller calls a callee then a new stack frame is created and to store the base pointer of new frame, caller's base pointer must be stored on the stack so that it can be fetched again when callee's frame is destroyed. Previous value of EBP is pushed on the stack before assigning esp to EBP.

[supercat]

@SurajJain: Typically, each saved copy of the frame pointer will be stored at a fixed displacement relative to the new frame pointer value.

[Suraj Jain]

Sir , I am having this doubt for a long time. If in my function I write if (g==4) then int d = 3 and g I take input using scanf after that I define another variable int h = 5. Now , how does the compiler now give d = 3 space in the stack. How does the offset done because if g is not 4 , then there would be no memory for d in the stack and simply offset would be given to h and if g == 4 then offset will be first for g and then for h . How does compiler do that at compile time , it does not know our input for g

[Suraj Jain]

You mean when a function call another function , the callee function ebp was in register , but when the called function come , the new base pointer value has to be store on ebp and the old one (of callee) will be stored on the new stack frame itself ??

[supercat]

@SurajJain: Early versions of C required that all automatic variables within a function must appear before any executable statements. Relaxing that complicated compilation slightly, but one approach is to generate code at the start of a function which subtracts from SP the value of a forward-declared label. Within the function, the compiler can at each point in the code keep track of how many bytes worth of locals are still in scope, and also track the maximum number of bytes worth of locals that are ever in scope. At the end of the function, it can supply the value for the earlier...

[supercat]

...label used in the stack-pointer subtraction. If the assembler can't handle forward references nicely, the compiler could define a linker symbol for the size of a particular function's automatic variables along with a "subtract" instruction that uses that value, but resolving the symbol before linking will be better if the target assembler can handle that.

[Suraj Jain]

I do not quite understand..can you explain it simpler terms ?

[Suraj Jain]

And also i want to know why the caller function stack frame stores the previous function base pointer..

[Suraj Jain]

"When caller calls a callee then a new stack frame is created and to store the base pointer of new frame, caller's base pointer must be stored on the stack so that it can be fetched again when callee's frame is destroyed. Previous value of EBP is pushed on the stack before assigning esp to EBP' Why is so is the case ?

[haccks]

@Suraj Jain; I would suggest you to read the first link mentioned in references. I hope that will clear most of your questions.