Assignment 5: WebAssembler

Due: Wednesday, October 31 at 4:00pm
Submission cutoff: Saturday, November 3 at 4:00pm

After the WebAssembly committee turned down your proposal, you’ve decided to take matters into your own hands and become BDFL of your own WebAssembly variant. Your goal in this assignment is to fulfill this vision by implementing a WebAssembly interpreter for the subset described in class using Rust.

Setup

Install Rust and Cargo following the instructions here. Code is in src; the only files you should edit are src/interpret.rs and src/memory.rs. Build your code from the assignment root with cargo build and clean build with cargo clean.

1. Memory (25%)

To warm up with Rust, your first task is to implement a simple module that works as a WebAssembly memory. Specifically, a WebAssembly memory is any type that implements this interface:

pub trait WMemory: Debug {
  // Bounds-checked load. Some(n) if 0 <= address < |mem|, None otherwise.
  fn load(&self, address: i32) -> Option<i32>;

  // Bounds-checked store. Sets *address = value if within range and returns
  // true, returns false otherwise.
  fn store(&mut self, address: i32, value: i32) -> bool;

  // Increases the size of memory by 4096 i32s.
  fn grow(&mut self);

  // Gets the current size of memory in units of i32.
  fn size(&self) -> i32;
}

First, you are going to use Rust’s Vec type to implement a VecMem in src/memory.rs.

pub struct VecMem(Vec<i32>);

impl WMemory for VecMem {
  ...
}

You should look at the get, get_mut, append, and len functions.

Next, you are going to implement UnsafeMem which uses unsafe features to manually manage a growable memory.

pub struct UnsafeMem {
  data: *mut i32,
  size: i32,
}

impl UnsafeMem {
  fn new() -> UnsafeMem {
    let size = PAGE_SIZE as usize;
    let data = unsafe {
      let typesize = mem::size_of::<i32>();
      let mut data = alloc(Layout::from_size_align(size * typesize, typesize).unwrap());
      ptr::write_bytes(data, 0, size * typesize);
      data
    } as *mut i32;

    UnsafeMem { data, size: size as i32 }
  }
}

impl WMemory for UnsafeMem {
  ...
}

Look at UnsafeMem::new. To create a raw memory region (not managed by Rust’s borrow checker), we use a few functions in the alloc crate and the std::mem library. We get sizeof(i32), then allocate a piece of memory to hold PAGE_SIZE integers, and finally zero-initialize the region.

Using this as your starting point, implement the WMemory interface for UnsafeMem. You will need the offset method on raw pointers along with realloc for growing the memory.

Testing memory

We have tests for your safe and unsafe memory implementations at tests/memory_test_safe.rs and tests/memory_test_unsafe.rs. Run them both from the assignment root with cargo test, or run just one file at a time with ex. cargo test --test memory_test_safe. Ignore output sections that run 0 tests — there are 2 tests given for each implementation. If you’d like to write your own additional tests, cargo test will pick up any functions tagged with #[test] in the tests directory.

It may be helpful to get a backtrace, e.g. for segfaults and other errors. To produce a backtrace, you can add RUST_BACKTRACE=1 before your run/test command, ex. RUST_BACKTRACE=1 cargo test.

2. Interpreter (75%)

Now that your memory is ready, it’s time to implement the full interpreter. First, take a look in src/ast.rs. We have provided you with data types for each WebAssembly construct: instructions, functions, and modules, and configurations. Note that we define our configuration to only contain locals, stack, and instructions. Functions and memory are both stored in the module.

Next, look in src/interpret.rs. At the bottom, we have provided you with the interpret function that sets up the initial configuration (a call to the 0-th function) and loops over step until either the instructions are empty, or a trap is raised.

Your task is to implement the step function to match the full semantics provided in our custom WebAssembly specification.

fn step(module: &mut WModule, config: WConfig) -> WConfig;

A few notes on the setup.

• Like in the Assignment 2 interpreter, you can assume that your interpreter is provided a well-typed program. While we haven’t precisely defined what that means for WebAssembly, it generally means you can assume e.g. that upon reaching a binop, that at least two values will be on the stack for you to pop off. It does NOT mean e.g. that memory accesses are guaranteed to be in-range.
• Rather than having a full configuration that contains all program state, we simplify by having a global, mutable module that contains functions and memory. All function calls and memory operations should refer to and/or update this object. This means that your implementation will not look exactly like the provided semantics, but it should still implement the same semantics in effect.
• The provided skeleton in step removes the first instruction from the current instruction sequence and matches it. When processing the instruction, you can modify the stack using stack.push and stack.pop, modify the locals using vector indexing, or add a new instruction by returning one from the match (see the provided unreachable and const cases for examples).
• You can assume division by 0 results in 0, as before.
• We have augmented Trapping to include an error message. We will not be checking the contents of those messages in the autograder.
• Our reference implementation of step is about 180 lines of code.

Testing interpreter

Run cargo run tests/$testfile to run your implementation on an individual test. To run on all tests given, run python3 run_tests.py from assignment root. As usual, there are additional tests not provided here that we’ll test on when grading — we strongly encourage you to write your own additional tests. The tests here should cover the full grammar of our specification so that you have a reference for all language features. You can run your additional tests against our solution with ./solution_mac tests/$testfile or ./solution_linux tests/$testfile.

Submission

Run ./make_submission.sh and upload the generated assign5.zip to Gradescope.