OSDev.org

My idea is thus.

Have a structure containing two binary trees for each physical page. These is stored at a predetermined location in memory, all contiguous, in an array.

Because they are stored this way, the location of the page being referred to in memory can be calculated just by knowing a pointer to the binary tree node. This is important because it means you don't have to store a pointer to the actual page in the Location data structure.

Anyway, the first binary tree points to a sorted Size of the tree. The second points to a sorted Location. On allocation, the Size tree is searched for the smallest possible (best-fit). The selected node is removed, and if a larger one was taken than requested, a new one with a smaller size (and a Location at the end of the allocation) is inserted.

On freeing, the node's Location tree element is inserted back into the tree. The left and right neighbors are checked for coalescing.

All in all I think such a scheme should allow for a fairly fast best-fit allocator. The overhead will be 32 bytes per page on the design I've worked up. Are there any problems with this scheme? Suggestions? Thanks

I don't exactly understand whether you have one node per page or one node per free region.
Is your tree balanced ? if not, what prevent it to degenerate into a linked list ? and if it is, the cost for keeping it balanced (deleting and adding back nodes in both of them) seems huge to me.
Also, i guess you'll need to perform merging of regions when you free one ...

All in all, i fear that all these heavy operations quickly become more complex than sweeping a list of regions ... but this should be tested.

---

Now, let's just think about it with a cold head. About 99% of your memory allocation will be 1-page requests from the on-demand paging system. Filling virtual memory for the user process don't require the lookup of X-sized regions. The contiguous requests will only come from device drivers, etc. So you could expect the system to reserve a fixed amount of memory (typically <16MB so that it's addressable via DMA) which will have an algorithm like the one you described and keep the rest of the physical memory for 1-page allocation mechanism (starring a modified bitmap algorithm, for instance)