Implement a Slab Allocator in Go

Memory management is a critical aspect of performance-sensitive applications. A slab allocator is a specialized memory management technique that aims to reduce the overhead of frequent memory allocations and deallocations, particularly for objects of fixed sizes. This challenge asks you to implement a basic slab allocator in Go to manage memory for fixed-size objects efficiently.

Problem Description

You need to implement a SlabAllocator in Go. This allocator will be responsible for managing a pool of memory for objects of a specific, fixed size. The primary goal is to optimize for speed by pre-allocating memory chunks (slabs) and serving requests from these slabs, rather than relying solely on the Go runtime's general-purpose allocator for every small object allocation.

Key Requirements:

1. Initialization: The allocator should be initialized with a size parameter, which defines the fixed size of objects it will manage.
2. Allocation (Alloc):
   • When Alloc is called, the allocator should return a slice of bytes ([]byte) of the specified size.
   • If there are available free objects within its managed slabs, it should reuse one.
   • If no free objects are available, it should allocate a new slab, populate it with free objects, and then return one.
3. Deallocation (Free):
   • When Free is called with a slice of bytes previously returned by Alloc, the allocator should mark that object as free and make it available for reuse.
   • It's crucial that Free only accepts slices that were originally allocated by this allocator and are of the correct size. Invalid Free calls should ideally be handled gracefully (e.g., ignored or cause a panic, depending on design choice).
4. Slab Management:
   • Slabs should be large enough to hold multiple objects of the specified size. A common practice is to define a slabSize that is a multiple of the object size plus some overhead for bookkeeping.
   • The allocator should keep track of which objects within a slab are free and which are in use.

Expected Behavior:

• Alloc should be fast, especially when there are free objects available.
• Free should also be fast.
• The total memory used by the allocator should grow only when necessary (i.e., when all existing objects are in use and a new slab needs to be allocated).

Edge Cases to Consider:

• Allocating an object of size 0.
• Freeing an invalid pointer (one not allocated by this allocator, or a duplicate free).
• Very high allocation/deallocation rates.
• What happens if the requested object size is larger than a reasonable slab capacity? (For this challenge, assume size is reasonable).

Examples

Example 1: Basic Allocation and Deallocation

// Assuming SlabAllocator is implemented and initialized
allocator, _ := NewSlabAllocator(8) // Allocate objects of size 8 bytes

// Allocate first object
obj1 := allocator.Alloc()
fmt.Printf("Allocated obj1: %v (len: %d)\n", obj1, len(obj1))

// Allocate second object
obj2 := allocator.Alloc()
fmt.Printf("Allocated obj2: %v (len: %d)\n", obj2, len(obj2))

// Free first object
allocator.Free(obj1)
fmt.Printf("Freed obj1\n")

// Allocate third object (should reuse obj1's space)
obj3 := allocator.Alloc()
fmt.Printf("Allocated obj3: %v (len: %d)\n", obj3, len(obj3))

// Free second and third objects
allocator.Free(obj2)
allocator.Free(obj3)
fmt.Printf("Freed obj2 and obj3\n")

Expected Output:

Allocated obj1: [0 0 0 0 0 0 0 0] (len: 8)
Allocated obj2: [0 0 0 0 0 0 0 0] (len: 8)
Freed obj1
Allocated obj3: [0 0 0 0 0 0 0 0] (len: 8)
Freed obj2 and obj3

Note: The actual byte values in the obj slices will be zero-initialized or hold whatever was last in that memory location. The key is the slice itself and its availability.

Example 2: Allocating More Than Available

// Assuming SlabAllocator is implemented and initialized
allocator, _ := NewSlabAllocator(16) // Allocate objects of size 16 bytes
// Let's assume a slab can hold 4 objects of size 16.
// So, initially, 4 objects are available.

// Allocate 5 objects
var objects [][]byte
for i := 0; i < 5; i++ {
    obj := allocator.Alloc()
    objects = append(objects, obj)
    fmt.Printf("Allocated object %d\n", i)
}

// Free the first 3 objects
for i := 0; i < 3; i++ {
    allocator.Free(objects[i])
    fmt.Printf("Freed object %d\n", i)
}

// Allocate 3 more objects.
// The first 3 will be reused from the freed objects.
// The 4th will be from the initial slab.
// The 5th will trigger a new slab allocation.
for i := 0; i < 3; i++ {
    obj := allocator.Alloc()
    fmt.Printf("Allocated new object %d\n", i)
}

Expected Output:

Allocated object 0
Allocated object 1
Allocated object 2
Allocated object 3
Allocated object 4
Freed object 0
Freed object 1
Freed object 2
Allocated new object 0
Allocated new object 1
Allocated new object 2

Explanation: The first 4 allocations use the initial slab. The 5th allocation fills the initial slab, likely triggering a new slab. When the first 3 are freed, subsequent allocations reuse those slots. The final 3 allocations will then pick from the freed slots.

Constraints

• The object size will be a positive integer, 1 <= size <= 1024.
• The SlabAllocator should be thread-safe. Multiple goroutines may call Alloc and Free concurrently.
• A slab should contain at least 2 objects.
• The maximum number of objects in a single slab is not strictly defined but should be reasonable (e.g., 64 to 256 objects per slab).

Notes

• Consider how you will track free objects within a slab. A free list or a bitmap are common approaches.
• For thread safety, you will need to use synchronization primitives like mutexes.
• When allocating a new slab, decide on a slab capacity that is a reasonable trade-off between memory overhead and fragmentation. For instance, a slab could be object_size * objects_per_slab.
• The NewSlabAllocator function should return an error if the size is invalid (e.g., 0 or negative).
• The Free method should ideally be robust to invalid inputs. For this challenge, you can choose to panic on invalid frees or simply ignore them.
• Think about memory alignment. While Go's []byte handles this, consider if your internal slab structures might benefit from specific alignment for performance.
• The SlabAllocator should not grow indefinitely. While it will add slabs as needed, there's no requirement to shrink or release memory back to the OS in this challenge.