I have been struggling to write a implementation of the binary buddy memory managment scheme for video memory managment. For some reason there is very little information and I can't seem to find those Yann L sliding slot threads anywere (darn search :() I have read that setting the system up using a binary tree should work. Now I have been thinking about the following. Let's imagine we allocate a megabyte of memory and we split it up in pieces of a specific minimum, let's say 2k. This would give us a huge binary tree overhead but we know where each node is located and what it's neigboors are. If two children are both not used then the parent can be used as a slot. Example tree: When I need to allocate a block of 2k then it's just walk through the tree until I'd find a 2k block which is free. Ofcourse, there would be some sort of look up table (with pointers to all 2k/4k/8k blocks (and there state)) Since the memory block is empty... the lookup looks like this 2k -> (empty), (empty), (empty), (empty) 4k -> (empty), (empty) 8k -> (empty) We look up the first free 2k block and allocate it. This lookup table also points into the BSP and we set a flag there to indicate this child is allocated. This also means that we need to set the state to the parent to used. It can't be used anymore since a child is in use so effectively the half part of the memory is gone. Our lookup table would look like this: 2k -> (used), (empty), (empty), (empty) 4k -> (used), (empty) 8k -> (used) Now there is a 4k request coming. We see there is one free 4k block. To allocate it for use we now need to set the children + parent state to used and eventually we turn the state of the 4k block to used. These changes need to be transferred through aswell the BSP table and the lookup table. Why the lookup table? We cannot allocate the children and parents anymore. And why the BSP? Simply because we need to look up what are it's children and it's parents. In this implementation there are 2 structures. - A lookup table - A binary tree. Can't these 2 be combined in just one structure? Well we could do it by creating the whole lot recursively by creating a BSP. Lateron we could link the BSP nodes in the lookup table. This way we recursively can determine the parents and children. How to you complicate things ;) Then there is one more issue to think about, there is no more free slot which is big enough. Consider the situation where we allocated all 4 2k blocks and we now need to allocate a 4k block. This means we need to de-allocate 2 2k blocks first. We could use LRU to determine which 2 2k blocks are the least recently used. This could implicetly be done by have the list sorted. Left are the oldest (least recent) and right the newest. Basically, if you need a block, take it from the left and stick it to the right. Back to our original case, we would select the 2 left blocks and deallocate the memory. Now we can set the children to unused. We cannot directly set the parent to unused because the parent may have it's other half busy. If the other half of the parent has it's busy flag set to false then also the parent can be set to unused. To allocate the 4k block we need to set all the underlying children to busy and move them to the right side of the list. Then we can use the 4k block. Then we need to set the parent busy again so it's no use to set the parent to unbusy as described before (small optimization already ;)) Basically this is my current ID. A binary tree which is smacked down into several smaller lookup tables. The tables contain sizes, used flags and pointers to their parent and left and right children (which originally came from the binary tree) If anybody has a working example of the binary buddy or a tutorial on it then please notify me. Maybe (if my ideas are correct ;)) It would be wise to turn it into a tutorial some day. Since there are so little tutorials on binary buddies. And it seems such a usefull technique to me. (Although i'm a bit concerned about the overhead) If anybody could poke me into the right direction then i'd be very glad. Thx

Firstly, the thread on Yann's sliding slot algorithm.

You're heading in the right direction and lot of your questions are answered in the above thread. Just one quick comment - you mention a lookup table and then later on the LRU cache scheme, this is best implemented as a linked list for each node granularity (e.g. your table would consist of a linked list for 2k, another for 4k, and so on...) As stated in the thread, the linked lists give you the LRU scheme for free.

Enjoy!

Kyle