Hone logo
Hone
Problems

Implementing a Global Allocator in Rust

Global allocators manage memory allocation and deallocation for an entire program. Implementing one provides fine-grained control over memory usage, which is crucial for performance optimization, embedded systems, and scenarios where predictable memory behavior is essential. This challenge asks you to build a basic global allocator in Rust, demonstrating your understanding of memory management and unsafe Rust.

Problem Description

You are tasked with implementing a simple global allocator in Rust. The allocator should provide allocate and deallocate functions that manage a fixed-size memory pool. The allocator should use a first-fit allocation strategy.

What needs to be achieved:

  • Create a struct representing the global allocator.
  • Implement allocate function that finds a suitable block of memory within the pool and returns a raw pointer to it. If no suitable block is found, return a null pointer.
  • Implement deallocate function that releases a previously allocated block of memory back to the pool.
  • The allocator should maintain a bitmap to track allocated and free blocks.

Key Requirements:

  • The allocator should manage a fixed-size memory pool of POOL_SIZE bytes.
  • The minimum block size is MIN_BLOCK_SIZE bytes.
  • The allocator should use a first-fit allocation strategy. This means it searches for the first available block that is large enough to satisfy the allocation request.
  • The allocator must be thread-safe. While a full-blown lock-free allocator is beyond the scope of this challenge, you must use a Mutex to protect the allocator's internal state.
  • The allocator must be implemented using unsafe code due to the direct manipulation of memory pointers.

Expected Behavior:

  • allocate(size) should return a non-null pointer if a block of at least size bytes is available.
  • allocate(size) should return a null pointer if no block of at least size bytes is available.
  • deallocate(ptr, size) should release the memory block pointed to by ptr that was previously allocated with size bytes.
  • Double-freeing a pointer should result in undefined behavior (as in standard C/C++ allocators). While you don't need to detect this, be aware of it.
  • Allocating a size larger than the pool size should result in a null pointer return.

Edge Cases to Consider:

  • Allocation requests that are exactly equal to the remaining free space.
  • Allocation requests that are larger than the remaining free space.
  • Deallocating a pointer that was not allocated by this allocator.
  • Deallocating a pointer to a memory location outside the pool.
  • Multiple allocations and deallocations interleaved.

Examples

Example 1:

Input: POOL_SIZE = 1024, MIN_BLOCK_SIZE = 16, allocate(32), allocate(64), deallocate(ptr1, 32), allocate(32)
Output: ptr1 (non-null), ptr2 (non-null), (), ptr3 (non-null)
Explanation: The first allocation returns a pointer to a 32-byte block. The second allocation returns a pointer to a 64-byte block. Deallocating the first block frees it. The third allocation returns a pointer to a 32-byte block, reusing the freed space.

Example 2:

Input: POOL_SIZE = 1024, MIN_BLOCK_SIZE = 16, allocate(1024)
Output: null
Explanation: The pool size is 1024, and allocating 1024 bytes would leave no space for metadata or future allocations. Therefore, the allocation fails.

Example 3: (Edge Case)

Input: POOL_SIZE = 1024, MIN_BLOCK_SIZE = 16, allocate(512), allocate(512)
Output: ptr1 (non-null), ptr2 (null)
Explanation: The first allocation succeeds. The second allocation fails because there is not enough space left in the pool to allocate another 512-byte block.

Constraints

  • POOL_SIZE will be between 1024 and 4096 bytes (inclusive).
  • MIN_BLOCK_SIZE will be between 16 and 256 bytes (inclusive).
  • Allocation sizes will be between 8 and POOL_SIZE bytes (inclusive).
  • The allocator must be thread-safe, using a Mutex.
  • The allocator must be implemented in Rust.
  • The allocator should be reasonably efficient (avoiding unnecessary iterations or complex data structures).

Notes

  • You will need to use unsafe blocks to directly manipulate memory pointers. Be extremely careful when working with unsafe code to avoid memory safety issues.
  • Consider using a bitmap to track allocated and free blocks. This will allow you to efficiently determine if a block is available.
  • The first-fit strategy is a simple allocation strategy. More sophisticated strategies (e.g., best-fit, worst-fit) could be implemented, but are not required for this challenge.
  • Error handling is minimal. The allocator simply returns a null pointer if an allocation fails.
  • Focus on the core functionality of the allocator. Features like alignment or coalescing of free blocks are not required.
  • MIN_BLOCK_SIZE accounts for metadata overhead. You'll need to store information about each block (e.g., size, allocated/free status) in addition to the actual data. The bitmap is part of this metadata.
  • Define POOL_SIZE and MIN_BLOCK_SIZE as constants at the top of your code.
const POOL_SIZE: usize = 1024;
const MIN_BLOCK_SIZE: usize = 16;
Loading editor...
rust