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
