Custom Allocator in Rust

Topic Overview

Swapping What Backs Every Box and Vec

Rust routes global allocation through GlobalAlloc. Discord and others plug in jemalloc or mimalloc for fleet wins; embedded targets sometimes ship a bump allocator with no individual free. Your exercise implements the trait the standard library expects.

rustCopy
Loading…

• Layout carries size and align; both must be honored on return
• alloc may return null; callers handle OOM
• dealloc receives the same layout passed to alloc
• Thread-safe implementations are required for #[global_allocator]

Bump Pointer Mechanics

Align an offset with (offset + align - 1) & !(align - 1), bump past the allocation, never free until reset. Zero-sized layouts are valid edge cases.

For this exercise, you will implement a GlobalAlloc bump allocator on a fixed byte array. This task asks you to pass Layout through correctly, because misaligned returns corrupt Vec growth and produce impossible-to-debug segfaults deep inside std.

Keep the relevant man page, ABI doc, or Rust reference chapter open while you work. When your output disagrees with the reference implementation on the same machine, the mismatch is usually an alignment rule, an off-by-one terminator, or a register slot you misread in GDB.

Your Task

Implement the policy behind a bump allocator, the kind you would put behind unsafe impl GlobalAlloc for an arena. Allocation just rounds the top pointer up to the requested alignment and bumps it. Freeing only helps when you free the most recent block. Everything else leaks until reset. Addresses are simulated: the arena starts at 0x1000.

Input

One command per line. Numbers are decimal.

cCopy
Loading…

Rules

• alloc: the layout is invalid unless SIZE ≥ 1 and ALIGN is a power of two ≤ 4096. Start = the current top rounded up to ALIGN, and padding = start − top. If start + SIZE passes the arena's end, it is out of memory and nothing changes. Otherwise top = start + SIZE.
• free: if the block ends exactly at the top, top rolls back to where it was before this block's allocation (so its padding is reclaimed too). Otherwise the bytes stay leaked.
• realloc: if the block ends at the top, resize it in place (grow or shrink; out of memory if it would pass the end). Otherwise bump-allocate a new block with the same alignment (the move), and the old block is leaked.
• reset: top = 0 and all allocations are forgotten.

Output

cCopy
Loading…

• "copied" is the smaller of the old and new size.
• "free" in an out-of-memory message is N − top, or N − block start for a failed in-place resize.
• "wasted" = used − live bytes (padding plus leaked blocks).
• Use allocation when the count is 1. The unit is always bytes, even for 1.

Errors: error: bad command: LINE, error: arena size must be 1..4096, error: no arena, error: bad number, error: name too long, error: NAME is already allocated (a live block has that name), and error: NAME is not allocated. For alloc, check in this order: numbers, layout, name length, duplicate name, space. For realloc: number, name, size 0 (invalid layout (size 0, align A)), then space.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Compute alignment with (addr + align - 1) & !(align - 1) on the absolute address, and validate layouts the way Layout::from_size_align does.
2. Track each block's start, size, alignment and the top before it was allocated.

Hidden tests cover LIFO frees that reclaim padding, frees that leak, in-place grow and shrink, moving reallocs, out-of-memory at the exact boundary, invalid layouts, and reset followed by reuse.