Table of Contents

• Submission
• Introduction
• Details
  • Memory Simulator
  • Memory Types
• Testing
• Requirements and Hints
• Grading
• Logistics

Submission

Submission deadline: 11:59 pm, Sunday, November 24th 2024.

Submission method: The submission method will be the same as previous exercises, but the script has not been made available. An announcement will be made when the autograder is running and submissions can be made.

Introduction

Quickstart: Base code.

You will write a dynamic memory allocator built on top of a memory simulator in Rust, ie. your own version of malloc, free and realloc. You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient, and fast.

Details

The bulk of your work done will be in src/allocator/solution.rs. You will implement at least the following four methods:

• Allocator::new(memory) -> Self

  Before calling Allocator::malloc, Allocator::free, or Allocator::realloc, the driver program calls Allocator::new to any necessary initializations, such as allocating the initial heap area.

• Allocator::malloc(size) -> MResult<Option<Pointer>>

  The Allocator::malloc routine returns a Pointer to an allocated block payload of at least size bytes. The entire allocated block should lie within the simulated heap region and should not overlap with any other allocated chunk.

  The Rust standard library allocator allows specifying alignments of powers of 2, but for simplification we will go with the standard C library (libc), whose malloc always returns payload pointers that are aligned to 16 bytes. Your malloc implementation should do likewise and always return 16-byte aligned pointers.

• Allocator::free(ptr) -> MResult<()>

  The Allocator::free routine frees the block pointed to by ptr. It returns nothing on success. This routine is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to Allocator::malloc or Allocator::realloc and has not yet been freed.

• Allocator::realloc(ptr, size) -> MResult<Option<Pointer>>

  The Allocator::realloc routine returns a pointer to an allocated region of at least size bytes with the following constraints:

  • if size is equal to zero, the call is equivalent to Allocator::free(ptr)

  • otherwise, ptr must have been returned by an earlier call to Allocator::malloc or Allocator::realloc. The call to Allocator::realloc changes the size of the memory block pointed to by ptr (the old block) to size bytes and returns the address of the new block. Notice that the address of the new block might be the same as the old block, or it might be different, depending on your implementation, the amount of internal fragmentation in the old block, and the size of the realloc request.

    The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Note that the new size may be smaller than the old size. Everything else is uninitialized. For example, if the old block is 8 bytes and the new block is 12 bytes, then the first 8 bytes of the new block are identical to the first 8 bytes of the old block and the last 4 bytes are uninitialized. Similarly, if the old block is 8 bytes and the new block is 4 bytes, then the contents of the new block are identical to the first 4 bytes of the old block.

fn test(ptr: Pointer) {
    let mut u32_ptr = TypedPointer::<u32>::from_ptr(ptr);
    let raw_u32_ptr: Pointer = (u32_ptr + 1).raw();
    assert_eq!(raw_u32_ptr, ptr + 4);

    let mut u64_ptr = TypedPointer::<u64>::from_ptr(ptr);
    let raw_u64_ptr: Pointer = (u64_ptr + 1).raw();
    assert_eq!(raw_u64_ptr, ptr + 8);
}

godbolt
playground

#[derive(Clone, Copy, Default, bytemuck::Pod, bytemuck::Zeroable)]
#[repr(C)]
struct MyCustomType {}

godbolt
playground

Testing

Note: The below examples use the provided implicit allocator, you will use Solution in place of Implicit to test your custom allocator.

You can test your allocator in two ways when running the default binary crate in the package:

$ cargo runUsage: simalloc [OPTIONS] <COMMAND>Commands:  tui   Run the TUI  test  Test your allocator with one or more trace files  help  Print this message or the help of the given subcommand(s)Options:  -v, --verbose  Show verbose output  -h, --help     Print help

1. cargo run -- tui --help

   The tui subcommand launches a Text-based User Interface that will allow you to interact with your allocator. You can use it to manually run allocation and deallocation routines, or test your allocator step by step with a trace file.

   Note: You should run the tui subcommand in debug mode to surface debug logging.

   You are free to use the tracing crate included in the project to log messages that will be captured by the TUI driver. For example, tracing::debug!(?block_size) or tracing::warn!("No free block found").

   Sample commands:

   # Test the implicit allocator
   $ cargo run -- tui --allocator Implicit
   # Test the implicit allocator, loading a trace file for execution
   $ cargo run -- tui --trace-file ./traces/amptjp-bal.rep --allocator Implicit
   # Auto-run a list of commands on startup
   $ cargo run -- tui --cmd-file samples/sample_cmd_file.txt
   
   
   

2. cargo run --release -- test --help

   The test subcommand runs automatic tests on your allocator with one or more trace files. Each trace file contains a sequence of allocate, reallocate, and free directions that instruct the driver to call your implemented allocator routines.

   Note: You should run the test subcommand in release mode to disable any logging utilities and speed up testing.

   Sample command to test the implicit allocator with all traces:

   $ cargo run --release -- test --allocator Implicit ./traces/
   
   
   

   The test subcommand will print out

   • Any errors found while testing your allocator

   • The space utilization of your allocator. The space utilization is the ratio between the peak aggregate amount of memory used by the driver (ie. allocated but not yet freed) and the size of the heap used by your allocator. The optimal ratio equals to 1 – in that case, the heap grew exactly as much as was needed to accommodate the aggregate amount of allocated memory when at its peak. You should find good policies to minimize fragmentation in order to make this ratio as close as possible to the optimum.

   • The performance of your allocator, measured as time taken to complete all trace operations. Note the performance calculations may be revised with an accompanying announcement.

Requirements and Hints

Grading

The grade breakdown is as follows:

• Correctness. The points are evenly divided between each tested trace, and awarded regardless of performance. You need to have implemented an allocator that is not the provided implicit list allocator.

• Performance. The points are given based on the performance index, which is $0.6 \times \text{average\_utilization} + 0.4 \times \text{allocator\_performance}$.

  • $\text{average\_utilization}$ is the average of the space utilizations of your allocator for each trace.
  • $\text{allocator\_performance}$ is calculated by comparing the performance of your allocator with an optimized implementation on rlogin.

  Note: The grading command is equivalent to cargo run --release -- test --vary-size --allocator Solution ./traces/.

• Documentation and style. Your code should be sufficiently documented. You should also place a header comment at the start of src/allocator/solution.rs that describes the structure of your free and allocated blocks, and the design of your allocator.

• Git usage. You should make proper use of git. This includes the use of git as source control, and descriptive commit messages.

Logistics

You will use Git for managing your source code. Git is a distributed version control system in which every working directory contains a full repository, and thus the system can be used independently of a (centralized) repository server. Developers can commit changes to their local repository. However, in order to share their code with others, they must then push those commits to a remote repository. Your remote repository will be hosted on git.cs.vt.edu, which provides a facility to share this repository among group members. For further information on git in general you may browse the official Git documentation: http://git-scm.com/documentation, but feel free to ask questions on the forum as well! The use of git (or any distributed source code control system) may be new to some students, but it is a prerequisite skill for most programming related internships or jobs.

You will use a departmental instance of Gitlab for this class. You can access the instance with your SLO credentials at https://git.cs.vt.edu/.

The provided base code for the project is available on Gitlab at https://git.cs.vt.edu/cs3984-systems-rust/project-2-simalloc,

One team member should fork this repository by viewing this page and clicking the fork link. This will create a new repository for you with a copy of the contents. From there you must view your repository settings, and set the visibility level to private. On the settings page you may also invite your other team member to the project so that they can view and contribute.

Group members may then make a local copy of the repository by issuing a git clone <repository> command. The repository reference can be found on the project page such as git@git.cs.vt.edu:teammemberwhoclonedit/project-2-simalloc.git. To clone over SSH (which you may need to do on rlogin), you will have to add an SSH public key to your profile by visiting https://git.cs.vt.edu/profile/keys. This key is separate from the key you added to your ∼/.ssh/authorized_keys file. Although you could use the same key pair you use to log into rlogin, we recommend using a separate key pair. This way you can avoid storing the private key you use to access rlogin on rlogin itself.

If updates or bug fixes to this code are required, they will be announced on the forum. You will be required to use version control for this project. When working in a team, both team member should have a roughly equal number of committed lines of code to show their respective contributions.