Rust Memory Sanitizer: Safe Allocation and Deallocation

Memory safety is a critical concern in software development. This challenge asks you to implement a simplified memory sanitizer in Rust that tracks allocations and deallocations, ensuring that all allocated memory is eventually freed. This exercise will reinforce your understanding of Rust's ownership and borrowing system, and introduce concepts related to memory management and debugging.

Problem Description

You are tasked with creating a MemorySanitizer struct that manages a pool of allocated memory blocks. The sanitizer should provide functions for allocating memory, deallocating memory, and reporting any memory leaks at the end of the program. The core functionality revolves around tracking allocated blocks and ensuring they are freed.

What needs to be achieved:

• Implement a MemorySanitizer struct with methods for allocation (allocate), deallocation (deallocate), and leak detection (report_leaks).
• The allocate method should return a pointer to a newly allocated block of memory.
• The deallocate method should free a previously allocated block of memory.
• The report_leaks method should iterate through the tracked allocations and report any blocks that have not been deallocated.

Key Requirements:

• The MemorySanitizer should internally maintain a data structure (e.g., a Vec) to track allocated memory blocks. Each entry in this structure should store the pointer to the allocated block and its size.
• The allocate method should allocate memory using Box::new and store the pointer and size in the internal tracking structure.
• The deallocate method should remove the corresponding entry from the tracking structure and effectively drop the Box to free the memory.
• The report_leaks method should print a message for each leaked block, including its address and size.
• The sanitizer should be thread-safe. Use Mutex to protect the internal data structure.

Expected Behavior:

• allocate should return a valid pointer to allocated memory.
• deallocate should successfully free the memory pointed to by the provided pointer.
• report_leaks should accurately identify and report any memory leaks.
• Multiple allocations and deallocations should work correctly.
• Deallocating the same pointer twice should panic (as Box::drop does).

Edge Cases to Consider:

• Allocation of zero-sized blocks (should be handled gracefully).
• Deallocation of a pointer that was not allocated by the sanitizer.
• Concurrent allocation and deallocation from multiple threads.
• Deallocation of a pointer that has already been deallocated.

Examples

Example 1:

Input:
allocate(10);
allocate(20);
deallocate(ptr1);
report_leaks();

Output:

Leaked memory block at address: 0x..., size: 20

Explanation: The first allocation creates a block of 10 bytes. The second creates a block of 20 bytes. The first block is deallocated, leaving the second block as a leak.

Example 2:

Input:
allocate(5);
deallocate(ptr1);
deallocate(ptr1); // Attempt to deallocate twice
report_leaks();

Output:

thread 'main' panicked at 'called `drop` twice on the same data', src/main.rs:XX:XX

Explanation: The first allocation creates a block of 5 bytes. The first deallocation frees the memory. The second deallocation attempts to free the same memory again, causing a panic.

Example 3: (Concurrent Access)

Input: (Multiple threads concurrently allocating and deallocating)
report_leaks();

Output: (May vary depending on allocation/deallocation order, but should accurately report leaks)

Leaked memory block at address: 0x..., size: ...

Explanation: Concurrent access is handled safely by the Mutex. The final report_leaks call should accurately identify any memory blocks that were allocated but not deallocated, regardless of the order of operations.

Constraints

• The allocate function should be able to allocate blocks of up to 1024 bytes.
• The deallocate function should only accept pointers that were previously allocated by the allocate function.
• The report_leaks function should complete within 100 milliseconds.
• The sanitizer must be thread-safe, handling concurrent access from multiple threads without data races.
• The solution must be written in Rust and compile without warnings.

Notes

• Consider using a Vec<(usize, *mut u8)> to store the allocated blocks, where usize represents the size of the block and *mut u8 is the pointer to the block.
• The allocate function should return the pointer to the allocated memory.
• The deallocate function should take the pointer as input.
• Use std::sync::Mutex to protect the internal data structure from concurrent access.
• Error handling is not required for this challenge; assume that allocation always succeeds. Focus on the core memory tracking and leak detection logic.
• You can use std::ptr::null_mut() as a placeholder for an invalid pointer.
• The addresses in the report_leaks output are for demonstration purposes and may not be meaningful in a real-world scenario.