Project 3: Y86 disassembler

This project is based on a project originally written by Dr. Michael Kirkpatrick.

This project serves as an expansion of the Mini-ELF utility from the first and second projects, and the goal is to reinforce assembly code concepts and the standard components of executable files.

In this project, you will implement the "fetch" cycle of a von Neumann architecture by reading machine code instructions from memory and populating a C struct with the decoded instruction details. You will also write a disassembly routine to output the machine code as human-readable assembly code. Finally, for full credit you will also output some details about the data segments of an executable file.

For generic project instructions, refer to the project guide.

Here is the path to the starter tarball file on stu: 

/cs/students/cs261/sp24/lam/p3-disas.tar.gz

The project distribution contains a compiled solution to projects 1 and 2. As for project 2, we recommend using your solutions instead if they are complete, but again I recommend testing without them before you submit just to make sure that you haven't made any incorrect assumptions that were not exposed by the P2 test suite.

Y86 decoding

The first step of the standard von Neumann process involves fetching the bytes of an instruction from memory and decoding the instruction. In this project, you will implement this step for the Y86 architecture.

The unit requirements will require you to write a routine to decode an individual instruction. To do this, you will examine the first byte of the instruction to determine what kind of instruction it is (we recommend using a switch statement for this). Depending on the instruction type, you may then need to read additional bytes to determine things like register numbers, immediate values, or memory addresses. The hardware version of this process is described in detail in Section 4.3.4 of your textbook (see the "Fetch Stage" subsection). Here you will be reading all of the relevant information into a y86_inst_t struct.

The integration requirements for this project will require you to step through executable segments, decoding all of the instructions. Note that Y86 uses a variable-length instruction encoding, so you will need to decode the current instruction in order to find out how many bytes forward to skip to get to the next instruction.

As an example, consider the simple.o file in tests/inputs. (Note that this file is different from the simple.o file from P2!) Here is the "-a" output of the previous project: 

$ ./y86 -a tests/inputs/simple.o
01 00 00 01 10 00 01 00  00 00 00 00 45 4c 46 00
Mini-ELF version 1
Entry point 0x100
There are 1 program headers, starting at offset 16 (0x10)
There is no symbol table present
There is no string table present
 Segment   Offset    Size      VirtAddr  Type      Flags
  00       0x0024    0x0017    0x0100    CODE      R X
Contents of memory from 0100 to 0117:
  0100  30 f0 68 24 00 00 00 00  00 00 30 f3 34 12 00 00
  0110  00 00 00 00 60 03 00

Examining the program headers, we see that there is a single 23-byte code segment that is loaded at address 0x100 in virtual memory. The first opcode is 0x30, which indicates an irmovq instruction. The second byte is 0xf0, which indicates that the destination register is %rax (register 0 in the low-order 4 bits and f in the high-order 4 bits). The next eight bytes contain the immediate value 0x2468 stored in little-endian format. The next instruction begins at address 0x10a and also has a 0x30 opcode. If we were to continue this process until the end of the segment, we would find the following instruction sequence (with associated assembly code): 

  30 f0 68 24 00 00 00 00 00 00    irmovq 0x2468, %rax
  30 f3 34 12 00 00 00 00 00 00    irmovq 0x1234, %rbx
  60 03                            addq %rax, %rbx
  00                               halt

Unit requirements

Here is the required function that you must implement in p3-disas.c. We will use unit tests to exercise this portion of your submission.

  • y86_inst_t fetch (y86_t *cpu, byte *memory);

    Fetch the instruction and supporting operands from memory. The cpu parameter contains the PC value that is the address of the instruction. You should populate all relevant fields of a y86_inst_t struct with information from that instruction. If there is no valid instruction at that location, the function should return an instruction with an INVALID type. There are many conditions that could render an individual instruction invalid; you should carefully study the Y86 reference sheet to anticipate these conditions. The function should also set the stat field of the CPU to the appropriate error code if the instruction is invalid or any part of the instruction is outside the address space.

WARNING: To ensure your solution's compatibility with future projects, you should NOT print anything to standard output in this function, nor should you change any part of the cpu parameter.

Recommended functions

We recommend writing the following functions as helpers for your main routine, but they are not required and thus are not covered by unit tests. You may add these to either main.c or p3-disas.c, but we recommend the latter. In future projects, we will provide compiled implementations of these functions in p3-disas.o.

  • bool parse_command_line_p3 (int argc, char **argv, bool *print_header, bool *print_phdrs, bool *print_membrief, bool *print_memfull, bool *disas_code, bool *disas_data, char **filename);

    As in Projects 1 and 2, set the booleans pointed to by the parameters as appropriate based on the command-line parameters. The two new parameters disas_codeand disas_data correspond to the "-d" and "-D" flags, respectively.
  • void disassemble (y86_inst_t *inst);

    Disassemble a single Y86 instruction inst. This should ONLY print the assembly code (e.g., the instruction name and operands), not the newline or spacing or any of the surrounding data (e.g., address, hex bytes, etc.) described below. That printing should be done in disassemble_code.
  • void disassemble_code (byte_t *memory, elf_phdr_t *phdr, elf_hdr_t *hdr);

    Disassemble an entire code segment. This function should repeatedly call fetch to retrieve instructions from the segment and print the information, using a call to disassemble for the actual assembly code output. Essentially, this function should implement a three-cycle von Neumann architecture where the stages are "fetch," "disassemble," and "update PC," and where the PC update is just an increment based on the current instruction size (i.e., no control flow changes). The function takes a pointer to a single program header struct (phdr) that describes the section to be disassembled as well as a pointer to the original ELF header struct (hdr). A sample starter template for this function is provided in the "Hints" section below.
  • void disassemble_data (byte_t *memory, elf_phdr_t *phdr);

    Disassemble a single read-write data segment that consists of a sequence of .quad assembler directives. The segment is described by the phdr parameter.
  • void disassemble_rodata (byte_t *memory, elf_phdr_t *phdr);

    Disassemble a single read-only data segment that consists of strings. The segment is described by the phdr parameter.

In addition, you must implement main() in main.c such that your program behaves as described below.

Integration requirements

To disassemble Y86, you will need to write a routine that prints out decoded instructions in a human-readable form as shown in the following example: 

$ ./y86 -d tests/inputs/simple.o
Disassembly of executable contents:
  0x100:                               | .pos 0x100 code
  0x100:                               | _start:
  0x100: 30 f0 68 24 00 00 00 00 00 00 |   irmovq 0x2468, %rax
  0x10a: 30 f3 34 12 00 00 00 00 00 00 |   irmovq 0x1234, %rbx
  0x114: 60 03                         |   addq %rax, %rbx
  0x116: 00                            |   halt

Each segment will start with a .pos line indicating the starting address of the segment. The _start: label must be provided for the instruction that is identified by the Mini-ELF header as the entry point. The remainder of the lines consist of the address of the instruction, the hex byte encoding, and then the disassembly of the instruction. If there are multiple code sections, you should print all of them with the appropriate .pos header and a trailing empty line. In the above output, only the bolded text should be printed by disassemble(); the rest of the output should be printed in disassemble_code() or main().

Some Y86 object files have data segments as well as code segments. There are two cases for data segments: 1) read-write and 2) read-only. For the first case (read-write), the segment by convention consists of global variables that are all 8 bytes in size. To disassemble this data, simply print each variable in hex. Here is an example: 

$ ./y86 -Hs tests/inputs/data.o
01 00 00 01 10 00 02 00  00 00 00 00 45 4c 46 00
Mini-ELF version 1
Entry point 0x100
There are 2 program headers, starting at offset 16 (0x10)
There is no symbol table present
There is no string table present
 Segment   Offset    Size      VirtAddr  Type      Flags
  00       0x0038    0x0001    0x0100    CODE      R X
  01       0x0039    0x0018    0x0200    DATA      RW

$ ./y86 -D tests/inputs/data.o
Disassembly of data contents:
  0x200:                               | .pos 0x200 data
  0x200: 88 77 66 55 44 33 22 11       |   .quad 0x1122334455667788
  0x208: 78 56 34 12 00 00 00 00       |   .quad 0x12345678
  0x210: 42 00 00 00 00 00 00 00       |   .quad 0x42

For the second case (read-only), the segment by convention consists of a sequence of null-terminated ASCII-encoded strings (as in C). To disassemble this data, you will need to scan to find the trailing null characters that separate individual strings. Here are a couple of examples: 

$ ./y86 -D tests/inputs/rodata.o
Disassembly of data contents:
  0x200:                               | .pos 0x200 rodata
  0x200: 68 65 6c 6c 6f 00             |   .string "hello"

$ ./y86 -D tests/inputs/rodata_long.o
Disassembly of data contents:
  0x200:                               | .pos 0x200 rodata
  0x200: 30 31 32 33 34 35 36 37 38 39 |   .string "0123456789"
  0x20a: 00                            |
  0x20b: 68 65 6c 6c 6f 20 77 6f 72 6c |   .string "hello world"
  0x215: 64 00                         |
  0x217: 61 62 63 64 65 66 67 68 69 6a |   .string "abcdefghijklmnopqrstuvwxyz"
  0x221: 6b 6c 6d 6e 6f 70 71 72 73 74 |
  0x22b: 75 76 77 78 79 7a 00          |

As can be seen in the second example, the strings may be longer than ten characters. In this case, you should print the entire string on the first line, but wrap the hex digits to fit inside the ten-byte hex field.

If both executable and data contents should be disassembled, you should handle all of the executable disassembly first and then all of the data disassembly.

Error checking

Robust software proactively checks for potential errors and responds appropriately when an error occurs. Failure to build robust software leads to security breaches, lost sales, and other problems; this failure is not acceptable. Our grading procedures will try to break your code. The following list is a sample (not complete) of the types of errors we may test:

  • Passing NULL values in pointer parameters.
  • Passing a file that contains invalid instructions.
  • Passing a file with references to addresses that are outside Y86 virtual address space.
  • Passing a file with program headers that have invalid flags or types.
  • Passing invalid PC values (e.g., part of the instruction is outside the Y86 virtual address space) to the fetch() function.
  • Attempting to fetch a Y86 instruction that is not a valid instruction according to the ISA specification (e.g., the ifun is not zero for a halt or the rA is not 0xf for a irmovq).
  • Passing invalid instructions to disassemble().

If an invalid opcode is detected during the disassembly routines, the program should print the error message "Invalid opcode: 0xYY" where YY is the value of the opcode. Disassembly of a segment should not continue past an invalid opcode. However, if there are more code segments at higher addresses, the program should continue to disassemble those.

The above list is not necessarily exhaustive, and you should think carefully about what sort of errors might occur so that you can prevent them or perform additional error checking as needed. In particular, we will also use valgrind to detect memory leaks. Failure to respond appropriately will result in grade reductions.

In P3 and P4, some tests are non-deterministic, meaning that they use random numbers to prevent hard-coding of solutions. You can see some examples by searching for calls to the rand() function in public.c. This means that it is even more important than ever to ensure that your solution is as general as possible.

Hints

After you have read the above description thoroughly, watch the P3 experimentation video for a less structured and more informal walkthrough of the "big picture" of this project before you dive into the details of your implementation.

  • Start early. This project involves writing significantly more code than the two previous projects.
  • Work incrementally. As always, start small and gradually add more functionality. Start by implementing the first part of fetch() by reading the opcode from memory based on the program count (PC) from the Y86 CPU. Determine what kind of instruction it is by splitting the opcode into the instruction code (icode) and function (ifun), calculating the address of the next instruction (valP), and handling any errors (e.g., is the function code correct?). Focus exclusively on the one-byte instructions at first! Once both fetching and disassembly is functional for one-byte instructions, work your way up to the ten-byte instructions. Leave the data disassembly for last.
  • Implement disassembly as you implement fetching so that you can test them together. Do not focus on fetch() at the expense of the disassembly functionality! The goal of the project is to implement BOTH fetch and disassembly operations, and you will get no credit for a full fetch implementation if the disassembly portion is not also working (or vice versa).
  • Use switch statements and bitwise operators. This will make your fetch() and disassemble() functions much cleaner and easier to read. Shifts and masks will be particularly helpful in manipulating instruction encodings, and default cases are useful for detecting invalid instructions.
  • Don't forget endianness. When printing the memory bytes for an instruction, the bytes have to appear in the order they do in memory (i.e., little-endian). However, when printing an immediate or address interpretation in an instruction's disassembly, you must display them using the standard representation (e.g., in big-endian).
  • Make sure you understand y86.h. This file contains a number of definitions and declarations that will make your work significantly easier if you use them properly.

To help you get started, here is the general framework (not complete!) for the three-stage (fetch/disassemble/update PC) von Neumann cycle that you should implement in disassemble_code: 

    y86_t cpu;			// CPU struct to store "fake" PC
    y86_inst_t ins;		// struct to hold fetched instruction

    // start at beginning of the segment
    cpu.pc = phdr->p_vaddr;

    // iterate through the segment one instruction at a time
    while (cpu.pc < end_of_segment) {

        ins = fetch (&cpu, memory);         // stage 1: fetch instruction

        // TODO: abort with error if instruction was invalid
        // TODO: print current address and raw bytes of instruction

        disassemble (&ins);                 // stage 2: print disassembly
        cpu.pc = ins.valP;                  // stage 3: update PC (go to next instruction)
    }

Grading

The following requirements are necessary to earn a grade of 'A' for this project:

  1. Correctly fetch and disassemble all one-byte instructions (except iotrap)
  2. Correctly fetch and disassemble all two-byte instructions and iotrap
  3. Correctly fetch and disassemble all instructions
  4. Correctly fetch and disassemble all data segments
  5. Accept all valid Y86 Mini-ELF files
  6. Reject all invalid Y86 Mini-ELF files

Completing steps 1-3 (with the corresponding elements of 5-6) are required to earn a grade of 'B' while completing only steps 1-2 (with the corresponding elements of 5-6) will yield a maximum grade of 'C'. You may receive a grade of 'D' for completing only step 1. You may receive a grade of 'A-' for completing all of steps 1-6 with the exception of correct multiline read-only data output (as exercised by the A_rodata_long and A_rodata_shakespeare tests). Note that these are the maximum grades you can earn. Inadequate error checking, failure to adhere to the coding standards, or deviations from the submit procedures will result in grade reductions as described in the project guide. Because this project requires significantly more code than the previous projects, it is particularly important to include sufficient documentation.

Failure to submit code that compiles on stu.cs.jmu.edu may result in an automatic grade of 0. In particular, you SHOULD NOT modify the included header files; your code must compile without errors or warnings against the original headers. Also, your code must not depend on being compiled with your previous solutions to P1 and P2. If you wish to use helpers that you wrote for those projects, please copy them into p3-disas.c.

Submission

Please see the project guide for general project help and grading policies. Please refer to the coding standards for coding practice guidelines.