🔬 Lab
CS 240 Lab 9
Procedures and the Call Stack
CS 240 Lab 9
In lab this week, you will experiment with how the stack is used for procedure/function calls.
Recursive Program
Exercise 1: When compiled, the C program from the lab assignment produces the x86 assembly shown on the right.
C program | X86 assembly |
---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Using VSCode, create the program and save it as stack.c
by copying and pasting the following code:
#include <stdio.h>
long getAndSumValues() {
long x;
("Enter an integer: ");
printf(" %ld",&x);
scanfif (x == 0) {
return 0;
} else {
return x + getAndSumValues();
}
}
int main() {
long result;
= getAndSumValues();
result ("The result = %ld\n",result);
printfreturn 0;
}
Exercise 1:
Compile the code:
gcc -Wall --std=c99 -g -O -o stack.bin stack.c
Run the program under gdb
, start
the
program, and disassemble getAndSumValues
:
$ gdb ./stack.bin
(gdb) start (gdb) disas getAndSumValues
Set a breakpoint right before the stack pointer is reset before the return, on the instruction:
add $0x18,%rsp
(In the assembly above this would be at
getAndSumValues+49
, but if you got different assembly code
just set the breakpoint on that instruction.)
continue
the program, and enter the following
values:
(gdb) continue
Enter an integer: 10
Enter an integer: 11
Enter an integer: 12 Enter an integer: 0
When you hit the breakpoint, use info reg rsp
to find
the current value of the stack pointer %rsp. Use the
backtrace
command (or bt
for short) to show a
summary of the currently active stack frames. How many stack frames are
active?
Correct answer: 5
Of the active stack frames, how many of them are for
getAndSumValues
?
Correct answer: 4
What gdb
command can be used to display multiple 8-byte
values starting at the stack pointer?
bt
x /20gx $rsp
print $rsp
print *$rsp
Run that command, and observe the output. Which values from the backtrace output also appear in the raw stack data?
Example answer: The backtrace lists memory addresses of instructions for each function, indicating where code will pick up when we resume that stack frame. These are taken from the stored return address values on the stack.
How many 8-byte values are in each stack frame that you see?
Correct answer: 4
How could we have known this from looking at the assembly code, without examining the stack?
Example
answer: The function call itself always
pushes one address onto the stack, and the code for
getAndSumValues
starts with sub $0x18,%rsp
,
which is the only modification it makes to the stack. Since
0x18
in hex is 16 + 8 = 24 in decimal, that’s an additional
3 8-byte slots being reserved, for a total of four per stack
frame.
Here’s what your stack data display should look like (possibly with some variation in the precise addresses and in the left column of values):
0x7fffffffd990: 0x0000000000000000 0x0000000000000000
0x7fffffffd9a0: 0x0000000000000000 0x0000000000401176
0x7fffffffd9b0: 0x0000000000000000 0x000000000000000c
0x7fffffffd9c0: 0x0000000000000000 0x0000000000401176
0x7fffffffd9d0: 0x0000000000000000 0x000000000000000b
0x7fffffffd9e0: 0x0000000000000001 0x0000000000401176
0x7fffffffd9f0: 0x0000000200000006 0x000000000000000a
0x7fffffffda00: 0x0000000000000800 0x000000000040118b
0x7fffffffda10: 0x0000000000000000 0x00007ffff7c3feb0 0x7fffffffda20: 0x0000000000000000 0x000000000040117d
Which of these values are the values that you entered when you ran the program?
Example answer: The ‘a’, ‘b’, and ‘c’ in the right-hand column are the values you entered.
Why might the values in the left-hand column change from computer to computer?
Example
answer: These values are not actually used by
the program: space is reserved for 3 8-byte values, but only one of them
(at 0x8($rsp)
which means “8 bytes above the bottom of the
stack”) actually gets used. So the slots in the left-hand column (slots
0 and 2 of our stack frame) are never assigned a value, and thus retain
whatever value they might have previously had when used by a prior stack
frame before it was cleaned up.
Why does gdb
seem to display the stack in “backwards”
order?
Example
answer: gdb
shows values in
increasing memory address order, but since the stack grows downwards,
this is the opposite of how we draw it on the board.
Which register should we watch to see the return value from each function call frame (give the 3-letter name with a ‘%’ beforehand)?
Correct answer: %rax
gdb
has a command called display
which
works like print
but which will auto-display the value
every time we hit a breakpoint. Which command will display the value of
%rax
for us automatically?
display $rax
info reg rax
display *$rax
display $rsp
Run that command, and then use c
to continue one step at
a time until the program terminates. What values of %rax
did you observe?
- 1st value before any continues: Correct answer: 0
- 2nd value after first continue: Correct answer: 12
- 3rd value: Correct answer: 23
- 4th value: Correct answer: 33
Delete your breakpoints and display expressions and set a new
breakpoint at the start of getAndSumValues
. Then run from
the start again:
(gdb) delete break
(gdb) delete display
(gdb) br getAndSumValues (gdb) run
Enter the same sequence of values as before (10, 11, 12, 0), but this time inspect the stack each time your breakpoint gets hit. Notice how each invocation of the function adds one stack frame.
Mystery Program
Analyze the X86 code (below) for a function mystery
,
disassembled with gdb
.
push %rbx
0x400474 <+0>: mov %rdi,%rbx
0x400475 <+1>: mov $0x1,%rax
0x400478 <+4>: test %rdi,%rdi
0x40047d <+9>: je 0x40048f <mystery+27>
0x400480 <+12>: lea -0x1(%rdi),%rdi
0x400482 <+14>: 0x400474 <mystery>
0x400486 <+18>: callq imul %rbx,%rax
0x40048b <+23>: pop %rbx
0x40048f <+27>: 0x400490 <+28>: retq
Exercise 2:
How many parameters does this function take?
Correct
answer: 1 Explanation: Of the parameter-passing registers,
%rdi
is the only one used by this
code.
Is register %rbx
a callee-saved or caller-saved
register?
Caller-saved
Callee-saved
Explain which two instructions the compiler included because of your answer above:
Example
answer: The initial push %rbx
and penultimate pop %rbx
implement the callee-saved nature
of the %rbx
register: since we overwrite that register by
doing mov $rdi,%rbx
and it’s a callee-saved register, we
are responsible for restoring its value by the end of our function call
back to the original value it had before the call started.
What is the lea
instruction accomplishing?
Example
answer: It subtracts 1 from
%rdi
.
What is the base case for the recursion in this code?
Example
answer: The code avoids recursing if it
executes the jump at address +12. That jump depends on the test at +9,
which in turn depends on the value of %rdi
, the first
argument to the function. So when the argument is 0, recursion stops. In
that case %rax
will be 1 because of the mov
at
address +4.
Describe the overall purpose of this function:
Example answer: It multiplies the number you give it by each smaller integer, down to 1, computing the factorial of the argument using recursion.
Assume that mystery
is called from a main
function with return address 0x401240
, and that
%rdi
is 4 and %rbx
is 0xff
.
Furthermore, assume that %rsp
was 0x7f...538
before the call
instruction was executed (you can include
the 7f...
in your answers).
How many stack frames of mystery
will be generated
overall?
Correct answer: 5
What values will %rdi
take on for the start of each
stack frame?
Example answer: 4, 3, 2, 1, and finally 0.
How many 8-byte slots does each stack frame for mystery
take up?
Correct answer: 2
Exercise 3:
Draw four stack diagrams on the board (or draw one and take pictures
as you update it). In each diagram, note the values of
%rdi
, %rbx
, and %rax
, as well as
%rsp
and %pc
(the program counter). Show
program counter values for the instruction that will execute next, and
indicate with an arrow which block of memory %rsp
points
to, using 8-byte memory blocks. Draw diagrams for the following
moments:
- The diagram showing the first function call frame, paused before the
very first execution of the +18
callq
instruction. - The diagram showing the second function call frame, paused before
the second execution of the +18
callq
instruction. - The diagram showing all of the stack frames produced, paused before
the +27
pop
instruction that starts the return process. - The diagram showing the state of the stack just before executing the
final iteration of the
retq
instruction at +28 that will return from the very first function call frame.
Compare your diagrams with these examples as you create each one to check your understanding of stack mechanics:
First diagram:
Second diagram:
Third diagram:
Fourth diagram:
Read Six Numbers
phase_2
in the x86
assignment uses a
function called read_six_numbers
to gather input, and
allocates space on the stack as part of that process. To disarm
phase_2
, it will be useful to understand how this
works.
Exercise 4:
Go to your x86practice
folder from last week’s lab, and
start debugging sample.bin
:
$ gdb ./sample.bin
(gdb) break trip_alarm
(gdb) start
Disassemble the function phase_2
:
Note: phase_2
has one parameter, and
it is a pointer to the string that is input by the user to solve
phase_2
. Therefore, %rdi
will contain the
pointer to the input when the function begins execution.
(gdb) disas phase_2
Dump of assembler code for function phase_2:
0x0000000000401232 <+0>: push %rbp
0x0000000000401233 <+1>: push %rbx
0x0000000000401234 <+2>: sub $0x28,%rsp
0x0000000000401238 <+6>: mov %rsp,%rsi
0x000000000040123b <+9>: callq 0x401465 <read_six_numbers>
0x0000000000401240 <+14>: lea 0x4(%rsp),%rbx
0x0000000000401245 <+19>: lea 0x18(%rsp),%rbp
0x000000000040124a <+24>: mov -0x4(%rbx),%eax
0x000000000040124d <+27>: add $0x5,%eax
0x0000000000401250 <+30>: cmp %eax,(%rbx)
0x0000000000401252 <+32>: je 0x4010c8 <phase_2+39>
0x0000000000401254 <+34>: call 0x40181c <trip_alarm>
0x0000000000401259 <+39>: add $0x4,%rbx
0x000000000040125d <+43>: cmp %rbp,%rbx
0x0000000000401261 <+46>: jne 0x4010b9 <phase_2+24>
0x0000000000401263 <+48>: add $0x28,%rsp
0x0000000000401267 <+52>: pop %rbx
0x0000000000401268 <+53>: pop %rbp
0x0000000000401269 <+54>: ret End of assembler dump.
Notice lines +2 and +6 above. First stack space is made by
subtracting from %rsp
, and then the second parameter to
read_six_numbers is being set up by copying the current
%rsp
to %rsi
before the call to
read_six_numbers.
How many empty 8-byte slots does the sub
instruction add
to the stack?
Correct
answer: 5 Explanation: 0x28
is 2 16s and an
8.
How many 8-byte slots do we need to store 6 integers?
Correct answer: 3 Explanation: Each int is 4 bytes.
Accounting for all stack usage, how many 8-byte slots does the stack
frame for a call to phase_2
include?
Correct
answer: 8 Hint: Remember to include the
return address as well as any pushed values. Explanation: In addition to the 5 slots allocated by
sub
, the two pushes beforehand each use 8 bytes, and the
call
instruction that entered the function uses 8 bytes to
store the return address.
This code does not mention %rdi
, but we know that
read_six_numbers
will use the %rdi
value as
its first parameter. Which function set %rdi
, and why
doesn’t phase_2
need to set it?
Example
answer: %rdi
was set by main
when it called phase_2
. Since phase_2
is
passing its own first parameter directly to
read_six_numbers
, it doesn’t need to modify the value
before making that call.
What do you think the purpose of read_six_numbers
is?
Where do you think the results of executing
read_six_numbers
will be stored?
Example answer: The purpose is probably to read in 6 numbers from the line of text that the user types, since its first argument is the user input string. Given that the pointer argument it gets is a copy of the stack pointer, they will be stored on the stack (in the stack frame for the calling function, i.e., phase_2).
Disassemble read_six_numbers
and examine the code:
(gdb) disas read_six_numbers
Dump of assembler code for function read_six_numbers:
0x0000000000401465 <+0>: sub $0x18,%rsp
0x0000000000401469 <+4>: mov %rsi,%rdx
0x000000000040146c <+7>: lea 0x4(%rsi),%rcx
0x0000000000401470 <+11>: lea 0x14(%rsi),%rax
0x0000000000401474 <+15>: mov %rax,0x8(%rsp)
0x0000000000401479 <+20>: lea 0x10(%rsi),%rax
0x000000000040147d <+24>: mov %rax,(%rsp)
0x0000000000401481 <+28>: lea 0xc(%rsi),%r9
0x0000000000401485 <+32>: lea 0x8(%rsi),%r8
0x0000000000401489 <+36>: mov $0x402325,%esi
0x000000000040148e <+41>: mov $0x0,%eax
0x0000000000401493 <+46>: callq 0x400b20 <__isoc99_sscanf@plt>
0x0000000000401498 <+51>: cmp $0x5,%eax
0x000000000040149b <+54>: jg 0x4014a2 <read_six_numbers+61>
0x000000000040149d <+56>: callq 0x401392 <trip_alarm>
0x00000000004014a2 <+61>: add $0x18,%rsp
0x00000000004014a6 <+65>: retq End of assembler dump.
Which line in the code above calls a C standard library function
(give the +
offset, including the +
)?
Correct
answer: +46 Explanation: The __isoc99_
part of the name
identifies the specific C library version; ISO stands for “International
Standards Organization” and C99 is the 1999 standard for the C language.
The @plt
part indicates that it’s part of the “process
linkage table” which you can read more about via that link if you
want, but which we won’t ask you to understand for this
class.
Which standard library function is it calling (just the function name as it would have been used in C code)?
Correct
answer: sscanf
Look up the behavior of sscanf
by searching online, and
answer these questions:
What does sscanf
do?
Example answer: It reads formatted values from a string, and stores them into variables pointed to by pointers it is given in addition to the string to scan.
How many parameters does sscanf
have?
Example answer: It has a variable number of parameters, but always at least 3: the first parameter is the string to scan, the second is the format to recognize, and the third and subsequent parameters are pointers to variables where the scan results should be placed. For each % escape in the format string, the result will be placed into the variable pointed to by the next argument in order.
What are the first and second parameter of sscanf
, and
how are they used?
Example answer: The first parameter is the string to scan, and the second is the format string. The format string determines what kind(s) of values sscanf will try to read from the string being scanned, using % escapes like printf.
What are the remaining parameters of sscanf
, and how are
they used?
Example answer: Each additional parameter is a pointer to a variable into which the next scan result should be placed.
What value is returned by sscanf
?
Example answer: It returns the number of items successfully scanned.
Notice that a large immediate value is loaded into
%esi
before the call to sscanf
. In the
assembly code above (but not necessarily in your code), what is that
value?
An “immediate” value refers to a value that’s
hard-coded into the assembly code, (and appears as part of the machine
instruction). It’s “immediate” because it’s immediately available as
part of the instruction, as opposed to being a value that the CPU
accesses via either loading from a register or from memory. A
$
appears in assembly code to indicate the use of an
immediate value, as opposed to a memory reference.
Correct answer: 0x402325
Which parameter of sscanf
is this value being used as?
How do you know?
Example
answer: The second parameter, because
%rsi
(or in this case the lower half %esi
) is
always the second parameter to a function
call.
Examine memory at the address used by the code you’re running (may not match the value above exactly). Explain what you see:
Example
answer: The value is the string
"%d %d %d %d %d %d"
, which is being used as the format
string for sscanf
. The %d
escape is for a
“decimal” value, just as we use in printf
, so this format
string indicates that sscanf
should read 6 numbers
separated by whitespace from the string it is
given.
Assume that you have called phase_2
with a pointer to
the string “1 2 3 4 5 6” as its argument (let’s say the pointer’s
numeric value is 0x603ba4
). The return address for the call
is 0x400f32
in main
, and the values of
%rbp
and %rbx
are currently
0xfeed
and 0xf00d
. The value of
%rsp
is 0x7f...578
.
Draw stack diagrams for the following moments in the code (or draw
and update one diagram, taking pictures along the way). Check your work
as you complete each diagram. Write ‘?’ for any memory locations which
need to be included in your diagram but which have unpredictable values.
Include the values of registers %pc
, %rsp
,
%rbp
, %rbx
, %rcx
,
%rdx
, %r8
, %r9
,
%rdi
, %rsi
, and %rax
in each
diagram, using ‘?’ values for registers that haven’t been assigned to
yet.
- Right before the
call
instruction atphase_2+9
which will callread_six_numbers
. - Right before the
mov
instruction atread_six_numbers+4
afterread_six_numbers
has allocated additional stack space. - Right before the
call
instruction atread_six_numbers+46
, which will callsscanf
. - Right before the
cmp
instruction atread_six_numbers+51
, immediately aftersscanf
returns (you do NOT need to read the assembly code forsscanf
). - Right before the
lea
instruction atphase_2+14
, immediately afterread_six_numbers
returns. - Right before the
je
instruction atphase_2+32
. Note for this diagram whether the jump will be taken or not.
For now, ask your lab instructor to verify the diagrams you draw at each step.
TODO: Add diagrams for each of these steps to this page.
If you have time left, you should work on the x86
assignment for the rest of the lab.