Custom Allocator in Rust

Memory management is a crucial aspect of software development. This challenge asks you to implement a custom allocator in Rust, allowing you to gain a deeper understanding of how memory is allocated and deallocated. Building a custom allocator can be useful for performance optimization, resource control, or specialized memory management scenarios.

Problem Description

You are tasked with creating a simple, yet functional, custom allocator in Rust. The allocator should provide basic allocation and deallocation functionalities. It should manage a fixed-size memory pool and return pointers to allocated blocks within that pool. The allocator should handle allocation requests of varying sizes, but it should not allow allocations that exceed the pool's capacity. It should also prevent double-free errors and memory leaks.

Key Requirements:

Fixed-Size Pool: The allocator should operate on a fixed-size memory pool. The size of this pool will be provided as a parameter during initialization.
allocate(size: usize) -> *mut u8: This function should allocate a block of memory of the specified size from the pool. It should return a raw pointer (*mut u8) to the beginning of the allocated block if successful, and null (or std::ptr::null_mut()) if the allocation fails (e.g., insufficient memory).
deallocate(ptr: *mut u8): This function should deallocate the memory block pointed to by ptr. It should return () (unit type) on success and panic if the pointer is invalid (e.g., not allocated by this allocator, or already freed).
Error Handling: The allocator should gracefully handle allocation failures by returning null. It should also prevent double-free errors and memory leaks.
Alignment: All allocations should be aligned to at least 8 bytes.

Expected Behavior:

Multiple allocations should be possible as long as the total allocated size does not exceed the pool's capacity.
Deallocating a pointer should free the corresponding memory block.
Attempting to deallocate a null pointer should be a no-op (do nothing).
Attempting to deallocate the same pointer twice should result in a panic.
Attempting to allocate a size larger than the pool's capacity should return null.

Edge Cases to Consider:

Allocation of zero-sized blocks.
Allocation of blocks at the very edge of the pool.
Deallocation of a pointer that was not allocated by the allocator.
Deallocation of a null pointer.
Fragmentation within the pool. (While perfect defragmentation isn't required, consider how your allocator handles it.)

Examples

Example 1:

Input: pool_size = 1024, allocate_size = 512, allocate_size = 256, deallocate(ptr1), allocate_size = 300
Output: ptr1 (pointer to 512 bytes), ptr2 (pointer to 256 bytes), null (allocation fails)
Explanation: The first two allocations succeed, consuming 768 bytes. The third allocation fails because there are only 256 bytes remaining.

Example 2:

Input: pool_size = 256, allocate_size = 128, allocate_size = 64, deallocate(ptr1), deallocate(ptr2)
Output: ptr1 (pointer to 128 bytes), ptr2 (pointer to 64 bytes), () , ()
Explanation: Two allocations succeed, then both are deallocated successfully.

Example 3: (Edge Case)

Input: pool_size = 100, allocate_size = 50, allocate_size = 50, deallocate(ptr1), allocate_size = 75
Output: ptr1 (pointer to 50 bytes), ptr2 (pointer to 50 bytes), (), ptr2 (pointer to 50 bytes)
Explanation:  Initial allocation of 50 bytes succeeds. Second allocation of 50 bytes succeeds. Deallocating ptr1 frees the first block.  A subsequent allocation of 75 bytes succeeds because 50 bytes are now free.

Constraints

Pool Size: The pool size will be a usize between 1024 and 1048576 (inclusive).
Allocation Size: The allocation size will be a usize between 0 and half the pool size (inclusive).
Alignment: All allocations must be aligned to at least 8 bytes.
Performance: While not a primary focus, avoid excessively inefficient algorithms. A simple first-fit approach is acceptable.
Safety: The allocator must be memory-safe and prevent common memory errors like double-free and use-after-free.

Notes

You can use std::alloc::Layout for alignment requirements.
Consider using a linked list or a bitmap to track free blocks within the pool.
The unsafe keyword will likely be necessary for pointer manipulation. Use it carefully and ensure memory safety.
Focus on the core allocation and deallocation logic. Error reporting beyond returning null is not required.
This is a simplified allocator. Real-world allocators are significantly more complex and optimized.