Crate multiple_heaps

source ·
Expand description

An implementation of an allocator that uses multiple heaps. The heap that will be used on each allocation is determined by a key. Right now we use the apic id as the key, so that we have per-core heaps.

The heaps are ZoneAllocators (given in the slabmalloc crate). Each ZoneAllocator maintains 11 separate “slab allocators” for sizes 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 and (8KiB - bytes of metadata) bytes. The maximum allocation size is given by ZoneAllocator::MAX_ALLOC_SIZE. The slab allocator maintains linked lists of allocable pages from which it allocates objects of the same size. The allocable pages are 8 KiB (ObjectPage8k::SIZE), and have metadata stored in the ending bytes (ObjectPage8k::METADATA_SIZE). The metadata includes a heap id, MappedPages object this allocable page belongs to, forward and back pointers to pages stored in a linked list and a bitmap to keep track of allocations. The maximum allocation size can change if the size of the objects in the metadata change. If that happens it will be automatically reflected in the constants ZoneAllocator::MAX_ALLOC_SIZE and ObjectPage8k::METADATA_SIZE

Any memory request greater than maximum allocation size, a large allocation, is satisfied through a request for pages from the kernel. All other requests are satisfied through the per-core heaps.

The per-core heap which will be used on allocation is determined by the cpu that the task is running on. On deallocation of a block, the heap id is retrieved from metadata at the end of the allocable page which contains the block.

When a per-core heap runs out of memory, pages are first moved between the slab allocators of the per-core heap, then requested from other per-core heaps. If no empty pages are available within any of the per-core heaps, then more virtual pages are allocated from the range of virtual addresses dedicated to the heap KERNEL_HEAP_START and dynamically mapped to physical memory frames.

Structs

  • MultipleHeaps
    An allocator that contains multiple heaps. The heap that is used on each allocation is determined by a key. Currently the apic id is used as the key.

Constants

Functions

  • init_individual_heap
    Initializes the heap given by key. There are 11 size classes in each heap ranging from [8,16,32,64 ..ZoneAllocator::MAX_ALLOC_SIZE]. We evenly distribute the pages allocated for each heap between the size classes.
  • switch_to_multiple_heaps
    The setup routine for multiple heaps. It creates and initializes the multiple heaps, then sets the multiple heaps as the default allocator. Only call this function when the multiple heaps are ready to be used.