-
Notifications
You must be signed in to change notification settings - Fork 0
Use Cases
As the OS must manage the allocation of a process's virtual memory - including it's backing by page files or physical memory - it is beyond the typical scope of user space applications to customize. Instead, the most fundamental building block of user-space memory allocation is typically OS APIs for page allocation.
| OS | alloc | free |
|---|---|---|
| windows | VirtualAlloc |
VirtualFree |
| *nix |
sbrk / mmap
|
mmap |
| WASM | memory.grow |
N/A |
Such APIs often allocate in 4 KiB chunks at minimum. WASM grows by 64 KiB pages. They may or may not give control over where such memory allocation takes place, and let you control things like if the page can be written to.
Allocating an entire 64 KiB page per instance of a type would be incredibly wasteful for most types. To avoid such waste, many allocators will take memory allocated by a Page Allocator and subdivide it.
Typically subdivide pages into a slot of fixed size. E.g. a specific pooling allocator instance might subdivide 4 KiB pages into 512 x 8 byte slots. When used directly, the size of a slot might exactly match the type it will be used for.
Instead of slots, divide memory into exactly two adjacent regions: allocated (starts empty and grows) and unallocated (starts full and shrinks). Pretty simple/fast, but cannot reclaim individual bits of memory. Can be used for temporaries (if you know you can throw away everything after a certain point in time), or data you know will remain loaded for the entire lifetime of the program.
A basic generic allocator might have a series of pooling allocators for various powers of two (8, 16, 32, 64, ...) or other vaguely exponential sequence, using the smallest pool that will fulfill a given allocation, falling back on page allocation for "huge" allocations. This can lead to memory fragmentation issues if at one point in the program you have many allocations in one pool's size, and then later have many allocations in another pool's size.
The simplest "debug" allocator simply counts the number of alive allocations, and complains if the number is negative (must've been a double-free somewhere) or nonzero at the end of the program (must've had a memory leak.)
More complicated debug allocators might:
- Keep track of which addresses have been allocated, and are thus valid to
free(...) - Overwrite or unmap freed memory to help catch use-after-free bugs.
- Collect stack traces on allocation for diagnosing memory leaks.
- Collect stack traces on deallocation to help track down what freed memory that perhaps should've remained valid.
The simplest "profiling" allocator simply counts the number of allocated bytes, and lets the developer display it somewhere.
More complicated profiling allocators might:
- Keep track of memory fragmentation
- Track multiple allocation categories
- Attach file/line information to each allocation call site to allow breaking down memory allocation by call site.
- Feed into fancy memory over time usage graphs
- ???