Allocators

Overview

A dynamic memory allocator is used to manage memory mapped to a process's heap. For each process, the kernel maintains a variable brk that points to the top of the heap. An allocator maintains the heap as a collection of various-size blocks. Each block is a contiguous chunk of virtual memory that is either allocated or free.

There are two basic kinds of allocators:

• Explicit allocators require the application to explicitly free any allocated blocks.
• Implicit allocators require the allocator to detect when an allocated block is no longer being used by the program and then freeing the block.

System Calls

The brk and sbrk functions are used to set the break or lowest address of a process's data segment. It was primarily used before the advent of virtual memory. These functions have been superseded (not respectively) by mmap and munmap.

Metrics

Generally speaking, the author of an allocator needs to find a balance between maximizing the following two metrics:

• Throughput, i.e. the number of allocation and freeing requests processed per unit of time.
• Utilization, i.e. the percentage of the heap used by the application.

Bryant et al. recommends characterizing utilization using peak utilization. This is the ratio between the allocated memory high-water mark (HWM) and the heap HWM.

Free Lists

A free list is a linked list in which each data element of the list corresponds to an unallocated region of memory. The first word of each unallocated region contains a pointer to the next. A free list is implicit if free blocks are located using the size fields in block headers (both allocated and free). A free list is explicit is free blocks are instead referenced using pointers.

A placement policy is a strategy used when finding a free block large enough to accommodate an allocation request. Common policies include:

• First Fit. Search from the beginning for a large enough free block.
• Next Fit. Search from the last allocated block for a large enough free block.
• Best Fit. Search for the smallest free block large enough to handle the request.

Splitting

When servicing an allocation request, most free list implementations perform splitting. This action divides a free block designated for the request and divides it into an allocated block (to hold the payload) and a free block (with the remainder of memory).

Splitting prevents internal fragmentation but contributes to external fragmentation.

Coalescing

Coalesing is the process by which two adjacent free blocks are consolidated into one larger block. There are generally two strategies used for coalescing:

• Immediate coalescing. Adjacent blocks are merged as soon as an allocated block is freed.
• Deferred coalescing. A decision is made to wait some time before coalescing free blocks.

Coalescing prevents external fragmentation.

Garbage Collection

A garbage collector is an implicit dynamic memory allocator. The process of collecting "garbage" is called garbage collection.

A garbage collector views memory as a directed reachability graph. Nodes of the graph are partitioned into a set of root nodes and a set of heap nodes. Each root node corresponds to a memory location not in the heap (e.g. registers, the stack, etc.). Each heap node corresponds to an allocated block in the heap. A directed edge from one node to another indicates that some location in the former block points to a location in the latter.

A node is reachable if there exists a directed path from any root node to it. Unreachable nodes correspond to garbage that can never be used again and should be freed.

Mark and Sweep

Mark & Sweep is a simple garbage collection algorithm that works in two phases:

1. Mark. Recursively mark every reachable node.
2. Sweep. Scan through the entire heap and free any unmarked nodes.