Custom Allocator for Embedded Rust

Embedded systems often have strict memory constraints and require fine-grained control over memory management. This challenge asks you to implement a custom memory allocator in Rust for an embedded environment. You'll need to handle memory allocation and deallocation requests efficiently, considering the limitations of typical embedded hardware.

Problem Description

Your task is to create a GlobalAlloc implementation in Rust that can be used as a custom allocator for embedded systems. This allocator should manage a fixed-size memory pool. You will need to implement the alloc and dealloc methods, ensuring that memory is allocated and deallocated correctly and that the allocator remains in a valid state.

Key Requirements:

Fixed Memory Pool: The allocator will operate on a pre-defined, contiguous block of memory provided at initialization.
Basic Allocation Strategy: Implement a simple allocation strategy, such as a first-fit or best-fit approach. For this challenge, a first-fit strategy is sufficient.
GlobalAlloc Trait: Your implementation must adhere to the core::alloc::GlobalAlloc trait.
No External Dependencies (beyond core): The allocator should not rely on any external crates for its core functionality, reflecting typical embedded development practices.
Thread Safety (for single-threaded embedded): Assume a single-threaded embedded environment. While GlobalAlloc implies thread safety, for this specific embedded context, you don't need to implement complex locking mechanisms.

Expected Behavior:

When alloc is called with a non-zero size, the allocator should return a pointer to a sufficiently large, aligned block of free memory from the pool.
When dealloc is called with a valid pointer and size, the corresponding memory block should be marked as free and potentially merged with adjacent free blocks.
If memory cannot be allocated (e.g., pool is full or no suitable block exists), alloc should return a null pointer.
Handling of zero-sized allocations is not strictly required for this challenge, but a robust implementation might consider it.

Edge Cases to Consider:

Allocating a block that exactly fills a free block.
Allocating a block that leaves a small remainder in a free block.
Deallocating a block that is adjacent to one or more free blocks, leading to merging.
Deallocating a block that is not currently allocated (this behavior is undefined by GlobalAlloc, but defensive programming is good).
Repeated allocations and deallocations leading to memory fragmentation.

Examples

Let's assume a simple memory pool of 100 bytes, initially all free. We'll represent memory blocks conceptually.

Example 1:

// Conceptual state: [ Free(100) ]
alloc(20 bytes)

Output: Pointer P1 to a 20-byte block.
// Conceptual state: [ Allocated(20) | Free(80) ]

Explanation: The allocator finds the first-fit block (the entire 100-byte pool) and allocates 20 bytes from it. The remaining 80 bytes form a new free block.

Example 2:

// Continuing from Example 1:
// Conceptual state: [ Allocated(20) | Free(80) ]
alloc(30 bytes)

Output: Pointer P2 to a 30-byte block.
// Conceptual state: [ Allocated(20) | Allocated(30) | Free(50) ]

Explanation: The allocator finds the next free block (the 80-byte one) and allocates 30 bytes from it. The remaining 50 bytes form a new free block.

Example 3:

// Continuing from Example 2:
// Conceptual state: [ Allocated(20) | Allocated(30) | Free(50) ]
dealloc(P1, 20 bytes)

Output: No explicit return value (function returns void).
// Conceptual state: [ Free(20) | Allocated(30) | Free(50) ]

Explanation: The memory pointed to by P1 is freed, turning the first 20-byte allocated block into a free block.

Example 4:

// Continuing from Example 3:
// Conceptual state: [ Free(20) | Allocated(30) | Free(50) ]
dealloc(P2, 30 bytes)

Output: No explicit return value.
// Conceptual state: [ Free(20) | Free(30) | Free(50) ]

Explanation: The memory pointed to by P2 is freed. Since it's adjacent to the previous free block (of 20 bytes), these two free blocks merge.

Example 5:

// Continuing from Example 4:
// Conceptual state: [ Free(50) | Free(50) ] (after previous merges)
alloc(60 bytes)

Output: Pointer to null.
// Conceptual state: [ Free(50) | Free(50) ]

Explanation: Even though there are 100 bytes free in total, they are in two separate 50-byte blocks. Neither block is large enough to satisfy a 60-byte allocation.

Constraints

Memory Pool Size: The fixed memory pool size will be a const usize that you will define. A reasonable starting size might be 1024 bytes, but you can adjust this.
Alignment: Allocations must respect standard memory alignment rules (e.g., usize::BITS / 8). Your allocator needs to manage this.
No Dynamic Memory Allocation: The allocator itself cannot use Box, Vec, or other dynamic memory allocation mechanisms to manage its internal data structures. It must operate solely on the provided static memory pool.
Performance: While not heavily optimized for extreme performance, the first-fit approach should be reasonably efficient for typical embedded workloads. Avoid algorithms that have quadratic or worse time complexity for basic operations.

Notes

You'll need to define a static mut array of bytes to represent your memory pool. Be mindful of unsafe blocks when accessing it.
Consider how you will track free and allocated blocks within the memory pool. A common approach is to use metadata (e.g., a header) stored before or after each block.
The align_up function (often found in core::mem or num crates, but you might need to implement a simple version) will be crucial for handling alignment requirements.
This challenge focuses on the allocator's logic. You don't need to set up a full embedded system, but you can test your allocator using #[cfg(test)] modules.
Think about how to represent the state of each memory chunk (free or allocated) and its size.