Rust Memory Sanitizer

This challenge involves building a simplified memory sanitizer in Rust. Memory sanitizers are powerful debugging tools that help detect memory safety issues like buffer overflows, use-after-free bugs, and double-frees, which are notoriously difficult to find and debug. Implementing one yourself will provide deep insights into how these tools work and the complexities of memory management.

Problem Description

Your task is to implement a basic memory sanitizer that intercepts memory allocation and deallocation operations within a simulated environment. This sanitizer will track memory regions, detect common memory errors, and report them. You will need to design a system that:

1. Tracks Allocated Memory: Keep a record of all actively allocated memory blocks, including their starting address, size, and potentially metadata.
2. Detects Overruns/Underruns: When a write operation is simulated, check if the access falls within the bounds of an allocated memory block.
3. Detects Use-After-Free: When a memory block is deallocated, mark it as invalid. Subsequent access attempts to this block should be flagged.
4. Detects Double-Free: If a deallocation attempt is made on memory that has already been freed, flag this as an error.
5. Reporting: Provide clear and informative error messages when any of these memory safety violations are detected.

You will simulate memory operations using a Rust struct that acts as our "heap" and provides methods for allocation, deallocation, reading, and writing.

Examples

Example 1: Buffer Overflow

// Simulated Heap Operations
let mut heap = SimulatedHeap::new(1024); // 1KB heap
let ptr1 = heap.allocate(50).unwrap();
heap.write(ptr1, &[1; 50]); // Valid write
// Attempt to write beyond the allocated buffer
let _ = heap.write(ptr1.add(45), &[1; 10]); // This should trigger an error

Expected Output (Conceptual):

ERROR: Memory Sanitizer detected buffer overflow at address [address], attempted to write 10 bytes, but only 5 bytes were available.

Example 2: Use-After-Free

// Simulated Heap Operations
let mut heap = SimulatedHeap::new(1024);
let ptr1 = heap.allocate(30).unwrap();
heap.free(ptr1);
// Attempt to read from freed memory
let _ = heap.read(ptr1.add(5), 1); // This should trigger an error

Expected Output (Conceptual):

ERROR: Memory Sanitizer detected use-after-free at address [address]. Memory block was previously deallocated.

Example 3: Double-Free

// Simulated Heap Operations
let mut heap = SimulatedHeap::new(1024);
let ptr1 = heap.allocate(20).unwrap();
heap.free(ptr1);
// Attempt to free the same memory again
heap.free(ptr1); // This should trigger an error

Expected Output (Conceptual):

ERROR: Memory Sanitizer detected double-free at address [address]. Memory block was already deallocated.

Constraints

• The simulated heap size will be between 1KB and 1MB.
• Pointers will be represented as usize.
• Allocation sizes will be positive integers.
• The sanitizer should not introduce significant performance overhead beyond what's necessary for tracking and checking.

Notes

• You'll need to define a struct to represent your simulated heap and its state.
• Consider how to store metadata about allocated blocks. A HashMap mapping addresses to block information might be useful.
• For simplicity, you don't need to implement actual memory allocation. Instead, a Vec<u8> can serve as the underlying memory buffer.
• The "pointer arithmetic" (ptr.add(offset)) will be simulated by adding offsets to the usize pointer value.
• You'll need to handle the case where allocate fails due to insufficient memory.
• Think about how to represent a "freed" state for memory blocks.
• The primary goal is to demonstrate the logic of detecting these errors, not to replicate the full complexity of real-world sanitizers like AddressSanitizer.