Disassembler Assignment

You may have noticed that debuggers (e.g., gdb) do a remarkably good job of understanding source-code-level information entered from the keyboard.  They also understand which assembly language instructions correspond to a given line of source code, so they can “single-step” through your code one line at a time.  This is possible because the compiler (when invoked with appropriate command-line switches) includes symbol table information in its assembly language output.  In the current assignment you will leverage this information to implement a web-based source and assembly cross-referencing tool. 

Gcc (and likewise llvm and other compilers) is capable of producing symbol table information in a variety of formats.  One of the most comprehensive of these—and the one used by default on Linux—is known as DWARF.  It captures details about variables, functions, typedefs, etc., including the locations in the source code (file and the line number), at which they are declared.  To embed DWARF information in your object file, compile with the -g3 command-line switch in gcc.  This instructs the compiler to include detailed debugging information, including macro definitions, in the symbol table. 

After compilation, DWARF information can be extracted from an executable or object file in any of several ways.  Arguably the easiest is to use the llvm-dwarfdump tool, which you can find in /usr/bin/ on the csug machines. 

Your task in this assignment is to write a Ruby program—call it disassem—that uses the output of  llvm-dwarfdump --debug-line  and  objdump -d  (also found in /usr/bin/) to construct a web page that contains side-by-side source and assembly language versions of a given (single-file) program. 

Naively, one might expect that each line of source code would be turned into a sequence of instructions in the assembly code, and that one could list these sequences next to the corresponding statements.  This doesn’t work in practice, however: even at low levels of optimization, compilers scramble their output code in surprisingly complicated ways.  While the compiler can generally say which set of instructions serve to implement a given line of source code, those instructions may not be contiguous with one another in the assembly code.  Moreover, some source lines (e.g., declarations, comments, or delimiters) may not correspond to any target code instructions, and some instructions may be considered to contribute to more than one line of source. 

To help a debugger set breakpoints, single-step through code, or print the source code context of the current program counter, DWARF provides a debug-line table that captures the mapping between source and assembly.  Your disassem tool will use this table to make its side-by-side code listing interactive in the following way:

As an example, we are providing an example of the output your tool should produce:

ascii.c
is a simple single-file C program that allows the user to explore a new keyboard or print the ascii character set.  (It’s actually a handy tool; I picked it up in grad school and still use it occasionally.)  I compiled it on the csug machines using  gcc -g3 -O1 -o ascii ascii.c
llvm-dwarfdump.txt
is the output of  llvm-dwarfdump --debug-line ascii
objdump.txt
is the output of  objdump -d ascii
ascii_disassem.html
is a (hand-written) version of what your code should produce.  Specifically,  disassem name  should run llvm-dwarfdump --debug-line name  and  objdump -d name, generate a disassembly web page, and place it in name_disassem.html.  Note that disassem should orchestrate all this work itself—the user should not need to perform any separate steps.  Note also that the name(s) of the source file(s) from which an executable was created should be gleaned from the llvm-dwarfdump output; this information will not be provided on the command line, nor should you assume that it can be inferred from the name of the executable. 

You will want to download the source of that last file and use it as a guide.  Among other things, it includes simple CSS and JavaScript code for the clicking and highlighting functionality.  Caveat: I am not a skilled web programmer.  There may be much better ways to do this.  Feel free to implement changes that make the code simpler and easier to generate.  Please do not introduce complexity to make the web page prettier; that will just make it harder to grade, and the purpose of this assignment is to gain familiarity with DWARF and the scripting facilities needed to generate the web page—not to showcase your CSS and JavaScript skills. 

The DWARF Line-Number Table

Pointers to on-line DWARF documentation can be found below.  Please don’t be intimidated by the complexity of the standard.  What you need for this assignment is relatively simple.  It’s basically the first two columns of the table at the end of the  llvm-dwarfdump --debug-line  output.  Lines in the table are sorted by assembly code address (column 1).  Each line indicates that the instruction at the given address corresponds to (helps to implement) the source code on the line given in column 2. 

Some instructions help to implement more than one line of source code: these have more than one line in the table (always consecutive).  If you compare the instruction addresses to the ones found in the output of objdump -d, you will see that some instructions are omitted from the table.  This is a space-saving convention: an omitted instruction corresponds to the same (single) source line as the previous instruction.  This means you can (and probably should!) insert the omitted instructions into the table (in sorted order), copying the line number from the line above.  If you think about the result for a bit, you’ll realize it defines a two-way mapping: you can infer not only which source line(s) correspond to a given assembly language instruction, but also which assembly language instructions (if any) correspond to a given line of source.  For the ascii program, this information has been encoded into the aline and sline attributes of the source and assembler lines, respectively. 

Additional Instructions and Hints

While Python is almost certainly the most familiar scripting language to students in the class, Ruby is heavily used for server-side web scripting and has significant advantages over Python for programs of nontrivial length.  (FWIW, it also has handier syntax for “regular” expressions and—if you want them—much better support for functional programming idioms.)

Be aware that behavioral details of gcc, llvm-dwarfdump, and objdump vary across versions and platforms, so your code is unlikely to port easily from elsewhere.  You will almost certainly want to work on this assignment on the csug machines. 

To get a sense of whether you’re interpreting the debug-line table correctly, you may want to look at the output of  objdump -Sd.  It generates a best-effort attempt at interleaved source and assembly.  You might also try the  disassemble /m  command in gdb.  For reasons explained above, the correspondences indicated by these tools won’t always be precise, but if your interpretation of the correspondence is dramatically different there may be a problem on your end.  Note that you are required to build your pages without using these extra mechanisms: you are required to glean the source-to-assembly correspondence from the debug-line table in llvm-dwarfdump’s output. 

At higher levels of optimization, the correspondence between source code and the assembly generated by a compiler becomes increasingly murky, and the information in the debug-line table becomes an increasingly rough approximation.  You will probably want to start with programs that have been compiled with ‑O0.  We reserve the right to test (and grade!) your code on arbitrary programs, however, including those that have been compiled with ‑O3

Finally, as you generate HTML output, be aware that &, <, and > characters in your C or assembly code will confuse the browser; you will need to convert these to appropriate character entities.  You may also want to make occasional use of nonblocking spaces (&nbsp;).  Examples can be found in the provided sample output. 

Division of labor and writeup

As in previous assignments, you may work alone or in teams of two.  If you choose to work in pairs, one possible division of labor is for one partner to write the code that inspects the llvm-dwarfdump and objdump output and the other to use this information to create the HTML files.  If you do this, be very careful to agree on the information you need, and read each other’s code to look for errors. 

Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to include your name(s)—both of them, if you’re working as a team.  Also be sure to describe any features of your code that the TAs might not immediately notice.  To illustrate the functionality of your code, you may want to include test data, contained in subdirectories. 

Resources

Extra Credit suggestions

  1. Extend your tool to accommodate programs comprising multiple separately compiled source files. 
  2. At every control transfer (conditional or unconditional jump; subroutine call) in your assembly code, make the target of the transfer a live link whose target is an anchor on the destination of the transfer.  This will allow the user to branch around the code, using the browser’s back button to return to the point of the transfer. 
  3. Consider additional cross-references—e.g., for function names, variables, types, or other entities in the source code.  All are identified in the DWARF debugging info. 
  4. Provide links to names declared in standard header files.  (You’ll probably need to create local copies of these, so the browser can find them.) 
  5. Extend your work to support source code in languages other than C. 
  6. Augment the web page so that up and down keys move to the (source or assembly) line above or below the currently selected line (if any), avoiding the need to click on the number of that line.

Trivia Assignment

Before the end of the day on Wednesday, November 30, each student should complete the T5 trivia assignment found on Blackboard

MAIN DUE DATE:

Friday December 16, by end of day; no extensions. 
Last Change: 22 October 2023 / Michael Scott's email address