freelists

Freelists are data structures used in memory management to track resources that are not currently in use. In many allocators, a freelist is a linked list of free memory blocks or objects. Each free block stores a pointer to the next free block, allowing the allocator to traverse and reuse blocks quickly without consulting a central free store.

Operation: When a block is freed, it is added to the head of the freelist. When a block is requested, the allocator removes a block from the head of the freelist and returns it to the caller. To support variable sizes, some allocators maintain separate freelists for different size classes, a technique known as segregated freelists.

Variants: Freelist implementations vary. Simple freelists use a single linked list. Segregated freelists maintain multiple lists for different sizes. Some systems use per-thread freelists to reduce contention, or slab allocators that keep caches for specific object types.

Advantages and drawbacks: Freelist-based allocation is fast and cache-friendly when objects are reused, and it enables rapid reuse of freed memory. Drawbacks include potential fragmentation over time, overhead from storing pointers in free blocks, and complexity in handling different sizes or coalescing adjacent free blocks.

Context and examples: Freelist concepts appear in kernel memory allocators (for example, slab or slab-like pools in Linux), user-space allocators such as jemalloc or tcmalloc, and in custom object pools that reuse frequently allocated types.