Homework 1
E6998 Spring 2008
DUE: 2/13/2008 at 11:59pm EST

E6998 Spring 2008 - Homework 1

All homework problems are to be done individually. All homework submissions are to be made via Courseworks. For all programming problems you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. The README should explain any way in which your solution differs from what was assigned, and any assumptions you made. Refer to the homework submission page on the class web site for additional submission instructions.

For your convenience, all programming can be developed on any machine that can run Linux. However, only those programs which compile using the gcc compiler on the CLIC machines will be graded. Furthermore, it is critically important that all submitted program listings and executions be thoroughly documented.

In this homework you will construct a program that can profile the execution of a function using binary translation. The program will follow the execution of a function and record the number of times each basic block is executed. The following steps will lead you through this process.

We have provided you with a source skeleton which you should use for this assignment. A couple of notes about the source skeleton provided. The skeleton should compile and run out-of-the-box. In the source you will find several NOT_IMPLEMENTED macros. You job will be to implement these pieces.

0. Binary Patching (10 points)

This first step will get you warmed-up and comfortable with patching code. Look at the bottom of main(). Just before main calls fib() it calls StartProfiling. StartProfiling is your hook. It gives you and opportunity to inspect and/or modify the target function, fib() in this case, before it starts executing.

Your objective in Step 0 is to use StartProfiling to binary patch fib() to immediately return. Although this may sound pointless, this technique is very useful in the real world. Often you have debugging code that needs to be removed after some time. On-the-fly binary patching allows you to remove functionality without recompiling your code. If fib() was some debugging code and this was in the kernel, binary patching fib() to return immediately would allow you to speed up the kernel without rebooting the machine.

1. Callouts (10 points)

In this step you should accomplish the same thing as step 0 but this time using a callout that emulates a RET. The trickiness about callouts is that they need to save all the registers and EFLAGS because the code was not expecting a callout. The normal gcc calling conventions don't work. Find the glue code in hw1.S.

You should patch the first instruction on fib() with a callout. The callout should emulate the behanior of the RET by returning not to the calling site of the callout (which is the normal behavior) but directly to the return PC on the stack.

2. Instruction Decode (30 points)

The goal of this step is to use StartProfiling to decode a block of instructions. You need only to decode enough of each instruction to determine its length. By doing this you should be able to decode a block of instructions of arbitrary length. StartProfiling should print the address, opcode, and length of the first 24 instructions of fib().

Use the pseudocode in Figure 2.12a and 2.12b of the textbook as a guide. An IA32 opcode map has been provided in ia32DecodeTable to save having to type all this out. Use it as you see fit.

3. Control Flow Following (30 points)

You should now have the tools to follow the execution of control flow. To do this decode the instructions to be executed until you hit a control flow instruction. Binary patch that instruction to call you instead of doing the control flow. You can then return to the code knowing that you will be called before execution passes that point. When your handler is called, unpatch the instruction, emulate its behavior and binary patch the end of the next basic block.

For each basic block you encounter, dump the instructions in that block in the same format as in step 1. You should stop this process when you hit the StopProfiling function.

4. Profiling (20 points)

Create a data structure to capture the start address each basic block executed. A large array that store the start of the basic block and the count of times it was executed.

Dump the contents of the table in StopProfiling.

Notes

You may find this reference helpful for PC assembly language programming. You will need the Intel IA32 manuals for exact instruction formats and decoding rules. You can find them here: