1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| ### Tricks
- We could update `dealloc` to check whether the freed allocation was the last allocation returned by `alloc` by comparing its end address with the `next` pointer. In case they’re equal, we can safely reset `next` back to the start address of the freed allocation. This way, each loop iteration reuses the same memory block.
- We could add an `alloc_back` method that allocates memory from the _end_ of the heap using an additional `next_back` field. Then we could manually use this allocation method for all long-lived allocations, thereby separating short-lived and long-lived allocations on the heap. Note that this separation only works if it’s clear beforehand how long each allocation will live. Another drawback of this approach is that manually performing allocations is cumbersome and potentially unsafe.
### The fundamental issue
A bump allocator cant effectively reuse freed memory regions.
There are a total of 5 unused memory regions, but the next pointer only gives us access to the last one. We could store all the unused regions in a constant sized array but we would not be able to know what size or how large it could get. We can't use dynamic data structures, because then our heap allocator would depend on itself.
## Linked List Allocator
A linked list can be used to keep track of the freed areas of memory, hence the name, *free list*.
Freed blocks should be merged together, else it will result in increasing and increasing fragmentation:
### Pros and Cons
- Able to reuse freed memory
- Poorer performance: list length depends on the number of unused memory blocks, the performance can vary extremely for different programs. A program that only creates a couple of allocations will experience relatively fast allocation performance. For a program that fragments the heap with many allocations, however, the allocation performance will be very bad because the linked list will be very long and mostly contain very small blocks.
## Fixed Size Block Allocator
Instead of allocating exactly as much memory as requested, we define a small number of block sizes and round up each allocation to the next block size. For example, with block sizes of 16, 64, and 512 bytes, an allocation of 4 bytes would return a 16-byte block, an allocation of 48 bytes a 64-byte block.
Like the linked list allocator, we keep track of the unused memory by creating a linked list in the unused memory. However, instead of using a single list with different block sizes, we create a separate list for each size class.
The property that each region in the list is the same size makes for some efficient allocations:
1. Round up the requested allocation size to the next block size. For example, when an allocation of 12 bytes is requested, we would choose the block size of 16 in the above example.
2. Retrieve the head pointer for the list, e.g., for block size 16, we need to use `head_16`.
3. Remove the first block from the list and return it.
Most notably, we can always return the first element of the list and no longer need to traverse the full list. Thus, allocations are much faster than with the linked list allocator. Deallocations also work the same way, by rounding up the freed size and adding the region to the head of the list, we avoid traversing the entire list.
### Fallback Allocator
A fallback allocator like a linked list allocator for allocation sizes which are rare, can reduce memory waste. Since only very few allocations of that size are expected, the linked list would stay small and the (de)allocations would still be reasonably fast.
## Variations
### Slab allocator
Use block sizes that directly correspond to selected types in the kernel. This way, allocations of those types fit a block size exactly and no memory is wasted. Sometimes, it might be even possible to preinitialize type instances in unused blocks to further improve performance.
Slab allocation is often combined with other allocators. For example, it can be used together with a fixed-size block allocator to further split an allocated block in order to reduce memory waste. It is also often used to implement an [object pool pattern](https://en.wikipedia.org/wiki/Object_pool_pattern) on top of a single large allocation.
### Buddy allocator
Instead of using a linked list to manage freed blocks, the [buddy allocator](https://en.wikipedia.org/wiki/Buddy_memory_allocation) design uses a [binary tree](https://en.wikipedia.org/wiki/Binary_tree) data structure together with power-of-2 block sizes. When a new block of a certain size is required, it splits a larger sized block into two halves, thereby creating two child nodes in the tree. Whenever a block is freed again, its neighbor block in the tree is analyzed. If the neighbor is also free, the two blocks are joined back together to form a block of twice the size.
The advantage of this merge process is that [external fragmentation](https://en.wikipedia.org/wiki/Fragmentation_(computing)#External_fragmentation) is reduced so that small freed blocks can be reused for a large allocation. It also does not use a fallback allocator, so the performance is more predictable. The biggest drawback is that only power-of-2 block sizes are possible, which might result in a large amount of wasted memory due to [internal fragmentation](https://en.wikipedia.org/wiki/Fragmentation_(computing)#Internal_fragmentation). For this reason, buddy allocators are often combined with a slab allocator to further split an allocated block into multiple smaller blocks.
|
