Go back to this week's lab writeup here.
These optional problems are an opportunity to further exercise your understanding of assembly and the runtime stack.
1) Recursion
About 15 min.
The factorial
program that we saw in lecture runs a classic recursive factorial function. Let's review it and take a closer look at the assembly level to understand how it works.
- Run
./factorial 5 6 7 8 9
to compute some small factorials. Try some larger values:./factorial 10 11 12 13 14 15 16
. Something fishy seems to be going on. The factorial function grows at an alarming rate -- it doesn't take long before overflowing the range of an integer! - Look over the code for the
factorial
function and trace out what you think will happen if you try to compute the factorial of a negative number. Now try it:./factorial -1
. Did you get what you expected?
Q1: How is an invalid number causing a memory problem? Run factorial
under gdb on argument -1. Use backtrace
to find out where the program was executing at the time of the crash. Does this shed some light on what has gone wrong?
-
Get into
gdb
and figure out how big eachfactorial
stack frame is. Here are two different strategies; try both!- Disassemble
factorial
and scan its instructions. You are looking for those instructions that change%rsp
, since this is what grows and shrinks the stack. Eachpushq
andcallq
instruction copies an 8-byte value to the stack and decrements%rsp
.%rsp
can also be explicitly moved to open up space for local variables or scratch results. (In this case, however, factorial exhibits no manual adjustment of%rsp
. The only data stored in its frame are saved registers placed there by push/call instructions.) Count the push/call instructions infactorial
and and multiply by 8 to get the total number of bytes used per stack frame. - Set a breakpoint on
factorial
, let a few calls through, and then use the gdb commandsinfo frame 1
andinfo frame 2
to examine the top two stack frames. Look for the frame addresses labeledStack frame at
and subtract the two to compute the size of a single frame. - Q: These two approaches should give you the same answer. Do they?
- Disassemble
Q2: In the OS on myth
, the stack segment is configured at program start to a particular fixed limit and cannot grow beyond that. The bash shell built-in ulimit -a
(or limit
for csh shells) displays various process limits. What does it report is the process limit for stack size?
- Divide the stack limit by the size of a
factorial
frame (info: 1 Megabyte = 1024 Kilobytes, 1 Kilobyte = 1024 Bytes). This estimates the maximum stack depth for factorial. Try factorial of -1 under gdb again. When it crashes, usebacktrace -10
to see the stack top to determine the stack depth.
Q3: How close is that depth to the maximum you estimated?
- Edit the Makefile to change the optimization level used to compile the program. Find the line that reads
factorial: CFLAGS += -Og
. The current setting is-Og
, a relatively modest level of optimization. Change-Og
to-O2
to apply more aggressive compiler optimizations. Make clean and make, then run./factorial -1
again.
Q4: Woah! What happened? Did the compiler "fix" the infinite recursion? Disassemble the optimized factorial
to see what the compiler did with the code.
(This fancy optimization is called "tail-recursion elimination". Note: gdb may not work as well with higher optimization levels, so you may have trouble e.g. setting breakpoints in the optimized version).
2) "Channeling" Information Between Functions
About 15 min.
The channel
program was inspired by a bug encountered in a past offering of CS107. The code in question was "working fine" until adding a print statement, which caused a incommensurate amount of grief. Removing the print statement "fixed" the problem - very mysterious!
Q1: Review the code in channel.c
. The init_array
and sum_array
function each declare a stack array. The init
function sets the array values, the sum function adds the array values. Neither init nor sum takes any arguments. There is a warning from the compiler about sum_array
, what is it?
Q2: The program calls init_array()
then sum_array()
. Despite no explicit pass/return between the two calls, the array seems to be magically passed as intended. How are these functions communicating? The term for this is "channeling". (Hint: when data is popped off the stack, it isn't cleared out - it just increments %rsp
to indicate that memory area can be reused).
Q3: The program's second attempt to channel the array from init
to sum
fails. What is different about this case?
Tell your group a story about a previous situation where your program's behavior was reproducibly yet inexplicably altered by adding/removing/changing some innocent and seemingly unrelated code -- does this exercise shed light on a possible explanation?
3) Clobbering Memory (about 20 minutes)
The clear_array
function in buggy.c
has the wrong bounds on its loop. It's a common-enough bug, especially to programmers unaccustomed to C's zero-based array indexing, but it has a surprising consequence in this context.
- Before you try executing the program, first discuss with your group: what do you expect to be the consequence?
- Run the program. It never seems to complete. Hmmm.
- Run it under gdb. Interrupt the program using Ctl-C and see where it is executing. Continue the program, then interrupt again. Where is it executing now?
- Interrupt again and then step from here. What is the loop taking so darn long? Just what is happening with the value of
i
?
Spoiler: the value of i
is changing as a result of code that doesn't directly assign to it. These kind of bugs are called "stomping" or "clobbering" memory. A variable can be "stomped on" due to an under/overrun of a neighboring region, using a pointer into a deallocated stack frame, referring to freed heap memory, or using an uninitialized pointer. These errors are difficult to debug since the variable is not named in the code that affects it and the stomping may go unnoticed until much later, making it difficult to connect cause and effect. Whereas Valgrind is awesome about reporting when you write to an invalid address, it cannot detect that you wrote to a valid address for the wrong reason. We need another strategy/tool to find this kind of error.
Debugging using gdb watchpoints
Let's learn how to use a gdb watchpoint . The gdb watch
command is given an expression or a memory location to watch. gdb sets up a special kind of breakpoint that stops your program whenever there is a change in the value of that expression or a write to that memory location. Here are some examples:
(gdb) watch myvar // report when myvar changes
(gdb) watch *0x608502 // report if write to memory location
- Run under gdb, set a breakpoint on
clear_array
and once hit, set up a watchpoint to monitor changes toi
. - Let's also add a
display
command to display the assembly instruction.(gdb) display/3i $rip
- Continue from here and gdb will stop on each change to i. The watchpoint will alert you to each increment of the counter in the loop: from 0 to 1, 1 to 2 and so on, but it also will report when
i
gets stomped on.
Q1: When i
changes from 2 to 3, execute disassemble
in GDB to see exactly what assembly instruction is responsible for changing i
at that point. As a tip, the =>
will point to the instruction that is about to be executed, so the one that changed i
comes before this. Where does this instruction come from in the C code?
Q2: When i
changes from 5 to 0, execute disassemble
again in GDB to see exactly what assembly instruction is responsible for changing i
at that point. It looks like it's a different instruction from the one changing i
before. What is that instruction? Where does it come from in the C code? What code is thus responsible for clobbering i
?
Watchpoints can be a useful tool for tracking down those bugs that make mysterious changes to memory (and may be a useful tool in reverse engineering an executable, too. Hmm...)