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? Q: 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 each factorial 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. Each pushq and callq 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 in factorial 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 commands info frame 1 and info frame 2 to examine the top two stack frames. Look for the frame addresses labeled Stack 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?

• 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. Q: 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, use backtrace -10 to see the stack top to determine the stack depth. Q: 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 optimizations. Make clean and make, then run ./factorial -1again. Woah! What happened? Q: 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!

• 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?
• 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. Q: 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).
• The program's second attempt to channel the array from init to sum fails. Q: 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 to i.
• 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.
• 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. Q: Where does this instruction come from in the C code?
• 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. Q: 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 a bomb, too. Hmm...)