Call vs Jmp: The Stack Connection

mov edi,1000
call myfunction
add eax,7
ret

myfunction:
mov eax,edi ; copy our first parameter into eax (to be returned)
ret ; go back to foo

(Try this in NetRun now!)

mov edi,1000
jmp myfunction
add eax,7 ; <- never executed!
ret

myfunction:
mov eax,edi ; copy our first parameter into eax (to be returned)
ret ; go back to main

(Try this in NetRun now!)

Call and Return

• Temporary storage, like small arrays in the program.  You just "sub rsp, N" to allocate N bytes starting at rsp; as long as you be sure to "add rsp,N" to give those bytes back before your function returns.  One nice part about the stack is that once you move the stack pointer over an area, those bytes are YOURS until you give them back, unlike registers, which almost always get overwritten when you call another function.
• Saving preserved registers, usually just a "push" at the start of your function, and a "pop" at the end.
  

call make_beef
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	ret

int make_beef(void);
int foo(void) {
	make_beef();
	return 0xC0FFEE;
}

int make_beef(void) {
	return 0xBEEF;
}

jmp make_beef
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	ret

int foo(void) {
	goto make_beef;
	return 0xC0FFEE;
make_beef:
	return 0xBEEF;
}

jmp make_beef
come_back:
mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	jmp come_back

(Try this in NetRun now!)

push come_back ; - simulated "call" -
jmp make_beef  ; -   continued  -
come_back:     ; - end of simulated "call" -

mov eax,0xC0FFEE
ret

make_beef:
	mov eax,0xBEEF
	pop rcx   ; - simulated "ret" -
	jmp rcx   ; - end of simulated "ret" -

(Try this in NetRun now!)

There's a very weird hacky way to figure out what address your code is running from: call the next instruction, and then pop the return address that "call" pushed!

call nextline
nextline:
pop rax ; rax will store the location in memory of nextline
ret

(Try this in NetRun now!)

This is only useful if your code doesn't know where in memory it will get loaded.  This is true for some shared libraries, where you see exactly the above instruction sequence!

Optimization: Tail Recursion

Because calling functions takes some overhead (push return address, call function, do work, pop return address, return there), recursion is slower than iteration.  For example:

int sum(int i) {
	if (i==0) return 0;
	else return sum(i-1)+i;
}
int foo(void)
{
	return sum(10000000);
}

mov rdi,10000000
call sum
ret

; sum function: computes sum of numbers from 0...i
; one parameter: i, in rdi: number of recursions left
sum:
cmp   rdi,0 ; check if we're done
jle    base_case
push rdi
sub  rdi,0x1; i-1
call sum ; recursion step
pop rdi
add rax,rdi ; partial + i
ret

base_case: ; no more iterations--return zero
mov   rax,0
ret

Folks who love recursion have found an interesting optimization called "tail recursion", where you arrange for there to be *nothing* for the function to do after recursing, so there's no point in your children returning to you--you just "jmp" to them, not "call", because you don't want them to ever come back to you.  The base case is the only "ret".  Here's an example:

int sum(int i,int partial) {
	if (i==0) return partial;
	else return sum(i-1,partial+i);
}
int foo(void)
{
	return sum(10000000,0);
}

mov edi,1000000000 ; sum first argument
mov esi,0 ; partial result
call sum
ret

sum:
mov    eax,esi
cmp   edi,0
je    base_case
lea    esi,[rax+rdi*1] ; funky esi=eax+edi
sub    edi,0x1
jmp sum ; tail recursion step!

base_case:
ret

Tail recursion eliminates both the memory used on the stack for the return addresses, and the time taken for the call and return.  It can make recursion exactly as fast as iteration.  (Curiously, you can always transform an iteration into a recursion, and vice versa, although the code may get nasty.)

Sadly, my version of the gcc compiler doesn't seem to do the tail recursion optimization anymore on 64-bit machines, possibly due to the new stack alignment rules, although it used to this optimization reliably on 32-bit machines.

Why you care #1: Stack Space Usage

int silly_recursive(int i) {
	if (i==0) return 0;
	else return i+silly_recursive(i-1);
}

int foo(void) {
	std::cout<<"Returns: "<<silly_recursive(read_input());
	return 2;
}

(Try this in NetRun now!)

int silly_iterative(int n) {
	int sum=0;
	for (int i=0;i<=n;i++) sum+=i;
	return sum;
}

int foo(void) {
	std::cout<<"Returns: "<<silly_iterative(read_input());
	return 2;
}

(Try this in NetRun now!)

int f(int n) {
	if (n==1) return 1;
	else return f(n-1)*n;
}

int f(int n,int sofar) {
	if (n==1) return sofar;
	else return f(n-1,sofar*n);
}

int f(int n,int sofar) {
	start_of_f:
	if (n==1) return sofar;
	else {
		sofar=sofar*n;
		n=n-1;
		goto start_of_f;
	}
}

int f(int n,int sofar) {
	while (n>1) {
		sofar=sofar*n;
		n=n-1;
	}
	return sofar;
}

int f(int n) {
	int sofar=1;
	for (int i=1;i<=n;i++) {
		sofar=sofar*i;
	}
	return sofar;
}
(Try this in NetRun now!)

Why you care #2: Buffer Overflow Attack

int happy_innocent_code(void) {
	char str[8];
	cin>>str;
	cout<<"I just read a string: "<<str<<"!  I'm a big boy!\n";
	return 0;
}

void evil_bad_code(void) {
	cout<<"Mwa ha ha ha...\n";
	cout<<"...er, I can't return.  Crashing.\n";
}

int foo(void) {
	//void *p=(void *)evil_bad_code; /* address of the bad code */
	//printf("evil code is at: '%4s'\n",(char *)&p);
	happy_innocent_code();
	cout<<"How nice!\n";
	return 0;

}

(Try this in NetRun now!)