Go Custom Allocator Challenge

Go's garbage collector is highly efficient, but sometimes you need more control over memory management for performance-critical applications or to interact with C code. This challenge asks you to build a simple custom memory allocator in Go. You'll learn how Go's runtime interacts with memory and how to manage it directly.

Problem Description

You need to implement a CustomAllocator struct that provides methods for allocating and deallocating blocks of memory. This allocator should manage a pre-allocated contiguous buffer of memory.

What needs to be achieved:

1. Create a CustomAllocator that initializes with a fixed-size byte slice (the memory pool).
2. Implement an Allocate(size int) method that returns a pointer (represented as an []byte slice pointing into the memory pool) to a block of memory of the requested size.
3. Implement a Deallocate(ptr []byte) method that marks the memory block referenced by ptr as free.
4. The allocator should keep track of free and used memory blocks.
5. Handle cases where allocation fails due to insufficient memory.

Key requirements:

• Memory Pool: The allocator uses a single, contiguous byte slice as its memory pool.
• Allocation Strategy: A simple "first-fit" allocation strategy is sufficient: find the first free block that is large enough to satisfy the allocation request.
• Deallocation: Deallocating a block should make that memory available for future allocations. You do not need to implement memory coalescing (merging adjacent free blocks) for this challenge, but consider how simple deallocation would work.
• No Garbage Collection Interference: Your allocator should operate on raw bytes and not rely on Go's garbage collector to manage the allocated memory itself. The GC will manage the CustomAllocator struct and the underlying memory pool slice, but the slices returned by Allocate should represent direct memory access within that pool.

Expected behavior:

• Allocate should return a valid slice of the requested size if memory is available.
• Allocate should return an error (e.g., fmt.Errorf("not enough memory")) if the requested size cannot be accommodated.
• Deallocate should correctly mark the memory as free, allowing it to be reused. Calling Deallocate on a pointer not originally returned by Allocate (or already deallocated) can be considered undefined behavior, but a robust implementation might have checks for this.
• Multiple calls to Allocate and Deallocate should work correctly, reusing freed memory.

Important edge cases:

• Allocating 0 bytes.
• Allocating memory larger than the entire pool.
• Attempting to deallocate a nil slice.
• Deallocating a slice that has already been deallocated.

Examples

Example 1:

Input:
allocator := NewCustomAllocator(1024) // 1KB memory pool
ptr1, err1 := allocator.Allocate(100)
ptr2, err2 := allocator.Allocate(200)
allocator.Deallocate(ptr1)
ptr3, err3 := allocator.Allocate(150)

Output:
ptr1: non-nil slice of length 100
err1: nil
ptr2: non-nil slice of length 200
err2: nil
ptr3: non-nil slice of length 150 (ideally reusing memory from ptr1)
err3: nil

Explanation:
The allocator is initialized with 1024 bytes. The first allocation of 100 bytes succeeds. The second allocation of 200 bytes also succeeds, leaving 1024 - 100 - 200 = 724 bytes free. Deallocating ptr1 frees up 100 bytes. The third allocation of 150 bytes can then be satisfied, possibly by reusing the memory block previously occupied by ptr1.

Example 2:

Input:
allocator := NewCustomAllocator(200) // 200 byte memory pool
ptr1, _ := allocator.Allocate(150)
ptr2, _ := allocator.Allocate(100) // This allocation should fail

Output:
ptr1: non-nil slice of length 150
ptr2: nil slice
Error from second allocation: "not enough memory"

Explanation:
After allocating 150 bytes from a 200-byte pool, only 50 bytes remain. An attempt to allocate 100 bytes fails, as there isn't a contiguous block of 100 free bytes.

Constraints

• The total memory pool size will be between 1 byte and 1,000,000 bytes (inclusive).
• The requested allocation size will be between 0 bytes and 1,000,000 bytes (inclusive).
• The CustomAllocator should be thread-safe for Allocate and Deallocate operations (consider using sync.Mutex).
• The implementation should aim for reasonable performance; frequent reallocations or inefficient searching for free blocks should be avoided.

Notes

• You'll need to devise a way to track free and used memory blocks within the contiguous buffer. A common approach is to use metadata stored alongside the memory blocks themselves or a separate data structure (like a linked list of free blocks).
• Consider how you will represent the "pointer" returned by Allocate. In Go, a []byte slice pointing into the memory pool is a good representation as it carries both a pointer and a length.
• Think about the overhead of your metadata. For small allocations, metadata can become a significant portion of the memory used.
• For this challenge, simply returning an error on allocation failure is sufficient. You are not required to implement resizing or compaction.
• The NewCustomAllocator function should return a pointer to a CustomAllocator struct.