Custom Memory Allocator in Go

Memory allocation is a fundamental operation in any programming language. While Go provides a robust default memory allocator, understanding and implementing a custom allocator can provide valuable insights into memory management and potentially optimize performance for specific use cases. This challenge asks you to build a simplified custom allocator in Go, focusing on basic allocation and deallocation functionality.

Problem Description

You are tasked with creating a custom memory allocator in Go. The allocator should manage a fixed-size memory pool and provide functions for allocating and deallocating blocks of memory within that pool. The allocator should support allocating blocks of varying sizes (up to a maximum size) and should track allocated and free blocks. The goal is to demonstrate an understanding of memory management principles, not to create a production-ready allocator.

Key Requirements:

• Fixed-Size Pool: The allocator should operate on a pre-defined, fixed-size memory pool.
• Allocation: A function Allocate(size int) (uintptr, error) should allocate a block of memory of the specified size from the pool. It should return a pointer (uintptr) to the allocated block and an error if allocation fails (e.g., insufficient memory).
• Deallocation: A function Deallocate(ptr uintptr) should deallocate the memory block pointed to by ptr.
• Error Handling: The Allocate function should return an error if the requested size is invalid (e.g., negative, too large) or if there is insufficient free memory in the pool.
• Basic Tracking: The allocator should maintain a simple representation of allocated and free blocks within the pool. This doesn't need to be a complex data structure, but it should allow you to track which blocks are in use.
• No External Dependencies: The solution should only use standard Go libraries.

Expected Behavior:

• Multiple allocations should be possible as long as there is sufficient free memory.
• Deallocating a pointer that hasn't been allocated or has already been deallocated should result in an error (or a no-op, your choice, but document it).
• The allocator should prevent memory leaks by ensuring that all allocated memory is eventually deallocated.
• The allocator should not allow fragmentation to become excessive (though perfect defragmentation is not required).

Edge Cases to Consider:

• Allocation of zero-sized blocks.
• Allocation requests larger than the available memory pool.
• Deallocation of a nil pointer.
• Double-freeing a block.
• Allocation of a block that overlaps with an existing allocated block (should be prevented).

Examples

Example 1:

Input: poolSize = 1024, allocateSize = 100, allocateSize2 = 50
Output: Allocate(100) returns 0x1000, Allocate(50) returns 0x10F0
Explanation: The allocator successfully allocates two blocks of memory from the pool.  The exact addresses (0x1000, 0x10F0) are illustrative and will vary.

Example 2:

Input: poolSize = 1024, allocateSize = 600
Output: Allocate(600) returns error "insufficient memory"
Explanation: The requested allocation size (600) exceeds the available memory pool size (1024), so the allocation fails.

Example 3:

Input: poolSize = 1024, allocateSize = 100, ptr = 0x1000, deallocate(ptr)
Output: No error
Explanation: The memory block pointed to by ptr (0x1000) is successfully deallocated.

Constraints

• poolSize will be a positive integer between 1024 and 4096 (inclusive).
• size (the allocation size) will be a positive integer.
• The maximum allocation size should be less than or equal to half of the poolSize.
• The allocator should be reasonably efficient; avoid excessive overhead in allocation and deallocation. While performance is not the primary focus, extremely inefficient implementations will be penalized.
• The uintptr returned by Allocate should be a valid address within the managed memory pool.

Notes

• Consider using a simple linked list or a bitmap to track free blocks within the pool.
• You don't need to implement a garbage collector or any advanced memory management techniques.
• Focus on the core allocation and deallocation logic.
• Document your code clearly, explaining the data structures and algorithms used.
• Error handling is important. Provide meaningful error messages when allocation fails.
• Think about how to prevent common memory errors like double-freeing and memory leaks.
• You can choose to implement a "first-fit" or "best-fit" allocation strategy. Document your choice.