SAllocator

A simple free-list memory allocator in Go.

Uses a fixed byte arena and a doubly-linked list of MemBlock nodes. Supports variable-size allocations (first-fit), splitting, coalescing, and full teardown.

Allocation strategy

This allocator uses First Fit: it walks the free list from the head and picks the first block that is large enough. It is the simplest strategy and the fastest in the common case.

Other common strategies:

Best Fit: scan the entire list and pick the smallest block that fits the request. Minimizes per-block waste but requires a full list scan. Worst Fit: pick the largest block. Leaves the biggest remainder, which can reduce fragmentation in some workloads.

Usage

package main

import "fmt"

func main() {
    // Init
    sa := InitAllocator(1024)

    // Alloc
    offset, err := sa.Alloc(100)
    if err != nil {
        // not enough space or zero-size
    }
    fmt.Printf("allocated at offset %d\n", offset)

    // Dealloc
    err = sa.DeAlloc(uint(offset))
    if err != nil {
        // offset not found
    }

    // Reset
    sa.TearDown()
}

Future research

• Alignment: 8-byte / 16-byte boundaries
• Fragmentation analysis
• Segregated free lists: size classes
• Slab allocators
• Thread safety: locks / lock-free
• Requesting memory from the OS: mmap / sbrk
• Best Fit / Worst Fit strategies