Implementing a Pool Allocator in Rust

Pool allocators are a specialized memory allocation strategy that pre-allocates a fixed-size block of memory and then manages allocations within that block. This approach is particularly useful when dealing with frequent allocations and deallocations of objects of a known, fixed size, as it avoids the overhead of system calls associated with traditional heap allocation. This challenge asks you to implement a basic pool allocator in Rust to understand memory management and improve performance in specific scenarios.

Problem Description

You are tasked with implementing a PoolAllocator struct in Rust. This allocator should manage a pre-allocated pool of memory, allowing for efficient allocation and deallocation of fixed-size blocks within that pool. The allocator should support the following operations:

• new(size: usize, block_size: usize): Constructs a new PoolAllocator. size represents the total size of the memory pool, and block_size represents the size of each block that can be allocated. The pool should be initialized with a Vec<u8> of the specified size.
• allocate() -> Option<*mut u8>: Allocates a block of memory from the pool. If a block is available, it returns a raw pointer to the beginning of the allocated block. If the pool is exhausted (no blocks available), it returns None.
• deallocate(ptr: *mut u8): Deallocates a block of memory pointed to by the given raw pointer. The pointer must have been previously allocated by this allocator. The block should be marked as free and available for future allocation.
• is_valid(ptr: *mut u8) -> bool: Checks if the given raw pointer was allocated by this allocator. This is important for safety and preventing double-frees or use-after-free errors.

The allocator should use a simple "first-fit" strategy for allocation – it searches for the first available block in the pool. Deallocation simply marks the block as free. No complex data structures (like linked lists) are required for tracking free blocks, but you must ensure that deallocate doesn't corrupt the pool's memory.

Examples

Example 1:

Input: PoolAllocator::new(1024, 64)
allocate() -> Some(0x...)
allocate() -> Some(0x...)
deallocate(0x...)
allocate() -> Some(0x...)

Output: As described above. Explanation: The pool is initialized with 1024 bytes, divided into blocks of 64 bytes each. The first two allocations succeed, then the first block is deallocated, and the third allocation succeeds.

Example 2:

Input: PoolAllocator::new(128, 32)
allocate() -> Some(0x...)
allocate() -> Some(0x...)
allocate() -> Some(0x...)
allocate() -> Some(0x...)
allocate() -> None

Output: As described above. Explanation: The pool is initialized with 128 bytes, divided into blocks of 32 bytes each. Four allocations succeed, exhausting the pool. The subsequent allocation returns None.

Example 3: (Edge Case - Invalid Pointer)

Input: PoolAllocator::new(256, 16);
let ptr1 = allocator.allocate();
let ptr2 = allocator.allocate();
assert_eq!(allocator.is_valid(ptr1), true);
assert_eq!(allocator.is_valid(ptr2), true);
assert_eq!(allocator.is_valid(0xdeadbeef), false); // Arbitrary invalid pointer

Output: false Explanation: Demonstrates the is_valid function correctly identifies an invalid pointer.

Constraints

• size and block_size must be positive integers.
• block_size must be less than or equal to size.
• The allocator should not panic under any circumstances. Return None for allocation failures.
• deallocate should not be called with a pointer that was not allocated by the allocator. is_valid should help prevent this.
• The allocator should be reasonably efficient for the given constraints. While performance is not the primary focus, avoid unnecessary overhead.
• The pool should be initialized with a Vec<u8>.

Notes

• Consider using unsafe Rust blocks for pointer manipulation. Be extremely careful to avoid memory safety issues.
• The is_valid function can be implemented by storing the base address of the pool and checking if the pointer falls within that range.
• This is a simplified pool allocator. More sophisticated implementations might use more complex data structures to track free blocks and improve allocation efficiency.
• Focus on correctness and safety first. Performance optimizations can be considered later.
• The raw pointers returned by allocate() are not guaranteed to be aligned to any specific boundary. The caller is responsible for ensuring that the data being written to the allocated memory is properly aligned.
• Error handling is minimal. The focus is on the core allocation/deallocation logic.
• Assume that the block_size is a multiple of the size of a pointer. This simplifies alignment considerations.