The Stack

CS 301 Lecture, Dr. Lawlor

So "a stack" is a data structure that you can perform two operations on:
For example, this ordinary C++ code implements a stack as a C++ object: 
void die(const char *why) {std::cout<<why<<"\n"; exit(1);}
class my_stack {
	int storage[10]; /* contents of stack */
	int top; /* Points to element on top of stack */
public:
	my_stack() {top=-1;}
	~my_stack() {if (top!=-1) die("Left stuff on stack!");}
	
	void push(int i) {
		top=top+1; 
		storage[top]=i;
	}
	int pop(void) {
		int i=storage[top];
		top=top-1;
		return i;
	}
};
int foo(void) {
	my_stack s;
	s.push(3);
	s.push(7);
	s.pop();
	return s.pop();
}
The defining feature of a stack is that the newest stuff comes off first (a stack is "LIFO": Last-In, First-Out).  This means if you push 3, then 7, you'll pop first the 7, then the 3.  So the first "pop" above returns 7, and the next "pop" returns 3.   If you don't pop exactly the same number of times that you push, you're either leaving extra junk on the stack, or taking too much off the stack, which is an error.  In assembly, of course, "an error" means a segfault or some other equally horrible crash.

The CPU itself supports a stack, normally called "The Stack" (although not normally capitalized!).  It's "The" stack because the CPU itself does pushing and popping, most simply with the push and pop routines:
    push eax;   <- copies eax onto the top of the stack
    pop ecx;  <- copies the top of the stack into ecx

You can push almost anything (a register, a constant, a label, etc.), and you can pop almost anything as well. 

The biggest use of The Stack in assembly is as a convenient place to stash variables while you call another function.  For computing, registers are the most convenient place to store variables, but there aren't that many registers (especially on x86!), and other subroutines have a nasty habit of overwriting your scratch registers.  The stack, by contrast, can store at least several megabytes of data, and is guaranteed to be private.

Call and Return

The "call" instruction is used to run another function.  When that function hits the "ret" instruction, the machine continues execution where the "call" left off.  For example, here are two assembly functions, foo and bar:
global foo ; <- allow foo to be called from main
; A function, like the C/C++: "int foo(void) {return bar()+1000;}"
foo:
	call bar; Run bar, and come back with return value in eax.
	add eax,1000; Add 1000 to eax
	ret

; A function, like the C/C++: "int bar(void) {return 17;}"
bar:
	mov eax,17; eax is the return result register on x86
	ret
(runnable NetRun Link)

The machine keeps track of where "ret" should return to by using the stack:
So we could be really explicit by writing the same subroutines foo and bar above like this:
global foo ; <- allow foo to be called from main
; A function, like the C/C++: "int foo(void) {return bar()+1000;}"
foo:
	; See below... call bar; Run bar, and come back with return value in eax.
	push rest_of_foo; <- Where to jump back to
	jmp bar; <- Go run bar function now
rest_of_foo:
	add eax,1000; Add 1000 to eax
	ret

; A function, like the C/C++: "int bar(void) {return 17;}"
bar:
	mov eax,17; eax is the return result register on x86
	; See below... ret
	pop ecx ; <- Where to jump back to
	jmp ecx ; Jumps back to rest_of_foo
(runnable NetRun Link)

Of course, push/jmp isn't nearly as clear as "call", and it uses more machine-code instructions.  But it's important to understand what call and return are doing.

Why?  Well, calling a recursive function (or any deeply-nested sequence of functions) uses up stack space to store the return address.  This means recursion can easily run out of stack space with only a few million calls--and this can happen in way under a second!

Passing Parameters on the Stack

Consider how we can pass parameters into a function, like the values 3 and 7 in this C/C++ code:
    bar(3,7);
The nicest way to pass parameters *into* a function is to stash them in registers.  For example, on 64-bit x86, the first parameter, 3, goes into register edi.  The second parameter, 7, goes into esi.  You then call bar, and bar can look in edi and esi to find its parameters.  On PowerPC, the first parameter goes into %r3, the second into %r4, and so on.  Note that even on 32-bit x86, the return value is passed *out* of a subroutine in a register, eax.

But there's one big drawback to passing parameters in registers.  What happens when a function takes more parameters than you've got registers?
    bar_big(x,y,z,4,8,15,16,23,42,"fuzzy",false);
That's 11 parameters, and x86 only has 8 registers counting the stack pointer--so we can't keep all the parameters in registers.

So on 32-bit x86, the usual thing is to pass all parameters "on the stack".  That is, to call bar(3,7), we push 7, then push 3, then call bar, and then clean up the stack:
    push 7
    push 3
    call bar
    pop esi
    pop esi

The "pop"s are used to clean up the stack after we call bar--because we pushed on those parameters, we have to pop them, or we'll get a horrible crash when our subroutine tries to return.

Bar then can access its parameters by looking on the stack--in the worst case, it could tear apart the stack looking for its parameters:
    pop edx ; <- return address, from "call"
    pop ecx ; <- first parameter, 3
    pop eax;  <- second parameter, 7
But I don't recommend this approach, because you've got to be very careful to put back the return address (so "ret" will work) *and* all the parameters (so your caller will be able to pop the parameters he pushed).

Instead, the best way to access your parameters is to do pointer arithmetic on the stack pointer, like this horrific thing:
    mov ecx, [esp+4] ; <- copies the first parameter, 3, into edx
The [] brackets are how you access memory in assembly--they're the equivalent of a C/C++ pointer-dereference, like "*esp".

We add 4 to esp to skip over the 4-byte return address, and get one int deeper into the stack, where our first parameter is stored.

We'll talk more about memory access and pointer arithmetic on Monday.