Skip to content

learning.md

Latest commit

 

History

History
109 lines (71 loc) · 2.97 KB

learning.md

File metadata and controls

109 lines (71 loc) · 2.97 KB

Memory Allocator Learning Notes

1. Fixed-size blocks (SLAB / pool allocator)

What the quote describes:

split into 16/32/64 byte chunks

That is:

a memory pool (slab allocator)

  • very simple
  • fast
  • good for learning
  • not a general allocator

2. Free-list + splitting allocator (what you're actually building)

What you originally wanted:

one big memory region -> split dynamically based on request size

This is:

a real free-list allocator

  • variable sizes
  • splits blocks
  • merges blocks
  • used in real systems concepts

Summary

Building a free list allocator, splitting allocator to allow for variable size allocations. The fixed one is good for memory pools.

3. Go testing

  • t.Errorf marks test as failed but continues execution
  • t.Fatal marks test as failed and immediately stops (calls runtime.Goexit())

4. Deallocation strategy

  1. Walk free list, find node matching the offset
  2. Set Free = true
  3. Check next block (address + size) — if free, merge into current
  4. Check prev block — if free, merge current into it
  5. Merge by address adjacency, not list order

5. Zeroing contract (memory contents on free / alloc)

  • Not the allocator's job to zero memory on free or alloc
  • After free: user must not touch the memory — if they do, it's a use-after-free bug
  • After alloc: returned bytes have unspecified content — caller must write before reading
  • Reading uninitialized memory is the caller's bug
  • This matches the malloc standard contract
  • Zeroing on free would be O(n) overhead and defeats the purpose of a fast allocator
  • If zeroed memory is needed, the caller does it explicitly or uses calloc

6. Allocation strategies

First Fit (what we built)

Walk the list and take the first free block that is big enough.

[50][100][200]

Request 80 → [50][used][200]

Fast because you stop at the first match.

Best Fit

Walk the entire list and pick the smallest free block that fits.

[500][90][200]

Request 80 → [500][used][200]

Picks 90 over 500 and 200 — minimizes waste per block, but slower (full scan).

Worst Fit

Take the largest free block.

[50][100][200]

Request 80 → [50][100][used(80)+free(120)]

Leaves the biggest remainder, which can help with fragmentation in some workloads.

7. What I now understand about allocators

  • An arena is just a []byte — the allocator manages slices of it
  • Metadata (MemBlock with offset, size, free flag) lives separately from the arena
  • A free list tracks which chunks are available using a linked list
  • Splitting divides a block when the request is smaller than the block
  • Coalescing merges adjacent free blocks back together to avoid fragmentation
  • First-fit is the simplest allocation strategy
  • Offsets into the arena work because we never move blocks (no compaction)
  • Freeing does not return memory to the OS — the arena is fixed
  • The caller is responsible for initializing memory — the allocator does not zero