non contiguous memory; page frame allocation

[ghost]

would it be possible to repurpose this allocator for non contiguous memory? ie. physical memory which has holes and reserved/unusable regions in between usable memory.

[spaskalev]

This is very much doable. Here's how :)

The allocator has a component structure - there is the underlying allocator tree, which is sizeless and works in arbitrary units where the smallest arbitrary unit is tracked by a leaf of the tree. The tree is used by the allocator and the allocator converts these arbitrary units to memory sizes and memory locations.

The tree maps to a contiguous, power-of-two virtual arena. The allocator supports non-power-of-two sized arenas by masking out the up-to-power-of-two complement in the tree as already allocated. This is currently done by the buddy_toggle_virtual_slots function.

If you need to mask out other holes you can make the internal functions non-static and use them in the same way. As long as your program doesn't do a free() to these they will remain masked.

[spaskalev]

And, if you want to ensure that you cannot free such masked ranges you need to take care of some extra precautions. The tree doesn't know whether a slot is allocated or reserved but it is likely the your reserved slots are just a few and can be probably stored in the allocator struct by adding a new member and interval-checked during free() to catch erroneous free() calls for them.