JOS - Call Stack

• x86 Stack
  • Registers
  • Instructions
• Stack vs Heap
• JOS Stack
• Reconstructing the Stack

Perhaps the most fundamental characteristic of modern software, call stacks are in virtually every high level software (i.e. non-machine code), including OS and even some BIOS.

Its prominence in software is rather intuitive, and Dijkstra explains it best in Recursive Programming. Simply put, the recursive nature of how we view procedures (and their sub-procedures) makes stack extremely suitable for storing their content. It is memory-efficient and fast.

x86 Stack

OS development is always a combination of software and hardware, so it is important to understand what kind of support does the hardware provide for call stacks. memory is allocated for stack.

For x86 architecture, the stack starts at a high memory address and grows downwards:

A few key registers and instructions are listed below:

Registers

Below are register names in 16-bit mode (since their names are the original ones):

• SP: Stack Pointer Register. It tracks the ‘top’ (bottom of x86 stack because the stack grows downwards) of the stack.
• BP: Stack Base Pointer Register. It points to the start address of current frame and holds the value of the start address of previous frame. The BP chain is used by debuggers to build up a representation of the call stack.
• IP: Instruction Pointer Register. It contains the address of the next instruction to be executed.

Instructions

• PUSH and POP: they exist to manage the stack and operate on SP register. PUSH SRC decreases SP and writes SRC to the address that the updated SP points to; POP DST copies from the address in SP to DST and increases SP.

  # 'push ax' is roughly equivalent to:
  sub $SIZE, %sp
  mov %ax, (%sp)
  # 'pop ax' is roughly equivalent to:
  mov (%sp), %ax 
  add $SIZE, %sp
  # Note: $SIZE depends on machine address size. There are slight differences in the results, e.g. flags.
  

• CALL and RET: they exist to correctly transfer the execution flow between frames and operate on SP and IP. CALL DST saves the IP register on the stack and then sets it to DST; RET pops from the stack to IP register.

  # 'call ax' can be thought of:
  push $ip
  mov $ax, $ip
  # 'ret' can be thought of:
  pop $ip
  # Note: directly writing to IP register is forbidden. This is an extremely simplified visualization.
  

• ENTER and LEAVE: they exist to create/destroy the memory used on entry/exit of a frame and operate on SP and BP. ENTER saves the BP register on the stack and updates it to point to current stack top; LEAVE undoes that.

  # 'enter' is equivalent to:
  push %bp
  mov %sp, %bp
  # 'leave' is equivalent to:
  move %bp, %sp
  pop %bp
  

Apart from those listed, there are some other instructions that modify the stack registers, many of them being expansion of the ones above, but also a few independent ones, e.g. int (interrupt) creates a new frame for the interrupt handling and thus the stack pointer is modified.

Stack vs Heap

Now that we know what is a call stack and how does it work, let’s see when it is used. The stack memory is used to save the function frame, namely arguments, instruction pointers, base addresses and local variables.

One interesting topic that comes up from time to time is stack vs heap. In contrast to stack memory where the residing local variables live and die with the function frame, variables allocated from heap memory are independent of the function frame. By this definition, we say heap memory is dynamically allocated. With added flexibility for its variables’ lifespan, a few sacrifices are made:

• its memory is more fragmented;
• memory may not be contiguous for adjacent allocations, and it leads to worse cache performance;
• deallocation is not automatic, and it’s more likely to cause memory issues.

It should be emphasized that the key factor for choosing between stack (e.g. local variables) vs heap (e.g. malloc/free, new/delete) are

• whether they need to outlive the function scopes;
• required memory size: stack memory is usually more limited than heap memory.

For legacy reasons (prior to c99 for C Language, and for C++ its current standards although most compilers support it), static (variable size known at compile time) is sometimes a requirement for using stack memory:

// when compiled with '-pedantic-errors', it fails with
// "error: ISO C++ forbids variable length array 'c' [-Wvla]"
// But most compilers supress this 'not-standard-conforming error'

// Example of variable length array allocation:
//   a: is a local var alloc-ed on stack
//   b: alloc-ed from heap
//   c: is var-length local array
int a = 5, *b = new int(6), c[rand()%10];
// print the storage location of each one of them 
printf("a:0x%p\nb:0x%p\nc:0x%p",&a, b, c);
// sample result
//   a:0x0x7ffd9073d564
//   b:0x0x1a69eb0
//   c:0x0x7ffd9073d550

We can see that c resides in stack memory.

JOS Stack

Now let’s take a look on how stack is set up in JOS. When the bootloader start, it overwrites the stack pointer value from BIOS to start (at 0x7c00):

# boot/boot.S 
movl $start, %esp
call bootmain

and grows into the opposite direction of the code section:

kernel destroys the bootloader stack

# kern/entry.S
.data
###################################################################
# boot stack
###################################################################
	.p2align	PGSHIFT		# force page alignment
	.globl		bootstack
bootstack:
	.space		KSTKSIZE
	.globl		bootstacktop   
bootstacktop:

Once we enter kernel, the stack used in boot is destroyed, and a new stack is create at a designated address:

# kern/entry.S
## clear ebp and esp
relocated:
  movl  $0x0,%ebp			# nuke frame pointer
  movl  $(bootstacktop),%esp
  call  i386_init
## stack location
.data
  .p2align	PGSHIFT		# force page alignment
  .globl    bootstack
bootstack:
  .space    KSTKSIZE
  .globl    bootstacktop   
bootstacktop:

Refer to previous post for memory layout. With that in mind, and

// inc/mmu.h
#define PGSIZE       4096       // 4k
#define PGSHIFT      12         // log2(PGSIZE)
// inc/memlayout.h
#define KSTKSIZE     (8*PGSIZE) // 32k

we can infer that JOS kernel stack is of size 32k. Further inspecting $esp during execution or objdump -h kernel, we know that it resides in 0xf0110000-0xf0108000 over the kernel code (.text) section (and .rodata, .stab, .stabstr).

Reconstructing the Stack

Lastly, the stack information is valuable in the sense that we can reconstruct the stack graph from the information stored on the stack. Debuggers use these information to implement backtrace/bt functionality. The ebp can be seen as a chain/linked-list of frame starting address, since each $ebp points to the location that contains the previous $ebp. Combining with the eip stored on the stack and .fstab information, we can fully reconstruct the call stack:

// kern/monitor.c
struct Eipdebuginfo info;
uint32_t* ebp = (uint32_t*)read_ebp();

while (ebp != 0) {
	// eip sits atop of ebp
	uintptr_t eip = *(ebp+1);
	...
	// debuginfo_eip() fetches the debug info related to eip from .stab 
	debuginfo_eip(eip, &info);
	...
	ebp = (uint32_t*) *ebp;
}