Module kernel::memory::buddy_allocator

source ·
Expand description

This module implements a buddy allocator, an efficient scheme for managing physical memory. In this allocator, memory is broken up into a number of blocks, each of which is a power-of-2 frames in size. A block of size 2^^n frames is said to be of order n:

ⓘ
      16                               0       Order       Size of blocks
       |-------------------------------|
       |               8               |       4           2^^4 = 16
       |---------------|---------------|
       |      12       |       4       |       3           2^^3 = 8
       |-------|-------|-------|-------|
       |  14   |  10   |   6   |   2   |       2           2^^2 = 4
       |---|---|---|---|---|---|---|---|
       |   |   |   |   |   |   |   |   |       1           2^^1 = 2
       |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
       | | | | | | | | | | | | | | | | |       0           2^^0 = 1
       |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

The blocks in each order are arranged in pairs - each has a “buddy” where A’s buddy is B and B’s buddy is A. To find the address of a block’s buddy, the bit corresponding to the order is simply flipped (and so is easily calculated with XOR - see the buddy_of method). Blocks are tracked in bins, where each bin contains blocks of a single order.

When an allocation is requested, the allocator looks in the bin of the correct size. If a block is available, that block is removed from the bin and returned. If no blocks of the correct size are available, a block of the order above the one requested is removed from its bin, split into two blocks of the order requested (which are “buddies” of each other), of which one is returned and one is added to the correct bin. If no blocks of the larger order are available, this process continues recursively upwards to larger and larger block sizes, until a free block is found. If no block is found, an “out of memory” error is issued.

When a block is “freed” (returned to the allocator so that it can be allocated again), the allocator checks to see if its “buddy” is also free. If it’s not, the block is just added to the bin corresponding to its order. However, if its buddy is also free, the two can be merged to form a block of an order one greater - this process happens recursively until the block’s buddy is not free, at which point the block is added to the correct bin.

Overall, the buddy allocator is an efficient allocator that has a much lower cost than other algorithms such as first-fit. It also helps reduce external fragmentation, but can suffer from internal fragmentation in the case of allocations that are slightly larger than a block size (e.g. allocating 17 frames actually returns 32, wasting 15 frames). If the kernel needs to make many allocations of a constant, “known bad” size (e.g. 3 frames at a time), it would be better served allocating a larger block of frames at a time, and using a slab allocator to make the individual allocations.

Structs

Constants

  • BASE_SIZE 🔒
    The “base” block size - the smallest block size this allocator tracks. This is chosen at the moment to be 4096 bytes - the size of the smallest physical frame for all the architectures we wish to support at this point of time.
  • MAX_ORDER 🔒
    The largest block stored by the buddy allocator is 2^MAX_ORDER.
  • NUM_BINS 🔒