OSDev.org

Hey people!
Its Me again, the never sleeping caffieneaholic Zeii!
(aka, word slaughterer)

Anywho, Ive been working on a concept for a VMM / Block Allocator.

And, Ive decided on this.
PMM - Allocates Pages, Returns Physical Address that the page addresses.

VMM - Maps the Page as a 4kb Block, all allocations work there, until the 4kb is used or ABOUT to be used up, in which case the VMM orders PMM to allocate another page, which is then added to the VMM Block list as another 4kb block.

Anywho, for the Block Manager, Im going to use a Binary Search tree.

you know, Something greater than a node, will link onto the RightNode Pointer, something less than a node will link onto thoe LeftNode pointer.

I will keep track of the BlockSize, the BlockAddress and a Flag.
(I will optimize this to take only one variable in the future, when my idea is working. )

Anywho, This is my plan...
I will order the Tree by Address.

When the VMM Initializes, it allocates a page, a 4kb 'heap' is active.

So, we Have a 4kb 'block-node', with starting address of wherever the Block actually exists.

Say we want to allocate 1kb?

First of all, we half the 4kb block. Size = Size / 2, then we add a 2kb block to the Tree. The 2kb block address is the previous block plus previou sblock size.

2048
0x000
F= FREE
\

2048
0x800
F= FREE

We will always split the lowest address first, IF it is greater than the size to be allocated.

For 1kb, we need to split 2048.
We half the 2048 block.
And add a 1024 block, address = previousblockaddr + previousblocksize


1024
0x000
F=FREE
\
2048
0x800
F=FREE
/
1024
0x400
F=FREE

No we have a 1024 block, that we can use!
We set the Root block (1024) Flag to USED and return the Address as a pointer. Then we have memory that can be used, YAY!

Now what happens when we free that 1024b block?
We will want to Merge all the free blocks!
But, Since we cant really 'delete' a Node, since there is no Delete system in place, We will have to store what nodes arent 'existant' anymore.

POST 1

For that purpose, I will have a 'Unused' List. Constructed from the Nodes that we arent using. The LEFTNODE and RIGHTNODE pointers will become, conceptually - PREVNODE and NEXTNODE.

So, when we free the 1024b, the first then we do is set that blocks Flag to FREE.

Then we perform a check of the Buddy of that block.
The buddy of that block, is always going to be BLOCKADDR + BLOCKSIZE, and since we order it by Addres, we can check easy.

We traverse the list, looking for its Buddy. When we find the buddy, we check if it is Free aswell.

If it is free, We make the 'originating' blocks Size, double what it is. So, 1024b becomes 2048.

2048
0x000
F= FREE
\
2048
0x800
/
1024
0x400
F=FREE

But as you see, we still have that 1024 entry. Now, if we were in a hosted environment we could just free it, but since we arent, we have to get rid of it in another method.

for that, we simply append it to the UNUSED node list.

2048 unused_list_header
0x000 FREE |
\ ^--[ 1024 ]--v
2048 |
0x800 FREE NULL

Now, weve 'pruned' the tree.
We see that both 2048 blocks are free.
So, we continue pruning.

4096 unused_list_header
0x00 FREE |
^--[ 1024 ]--v
^--[ 2048 ]--v
|
NULL

Now, WHEN we allocate something, the first thing we do, is check if there are UNUSED nodes that we can readd to the tree.
If there are no Unused nodes, then we simply make a new node.

When we remove nodes, We will have to check for children.
Candy has informed me this is the rule for removing children in a BS Tree.
(adapted for No MM environment)

Go LEFT from ChildToBeRemoved.
Go RIGHT until there are NO more Rights.
If RIGHTMOST node has left child, copy data from Rightmost Node into the NodeToBeRemoved, then copy Data from LeftChild into Rightmost Node. Add Leftchild to UnusedNode List.

IF the RIGHTMOST Has no children, simply copy its data to the node to be removed, and add the RIGHTMOST node to UnusedNode list.

BUT... What happens if there is no Left node?
After a little pondering, head scratching and coffee slurping, I have come up with this...

IF no left node, and if no right node. Add Node to unused list.
IF No left node, but a right node exists, Link the Parent of the Node to be removed, to the Rightnode. And add the node to be removed to the Unused list.

Hows this sound people?

We have one tree and one list, constructed out of unused tree nodes.

This is just an idea I hope to test shortly, but I would like feedback!

~Zeii.

zeii wrote: Then we perform a check of the Buddy of that block.
The buddy of that block, is always going to be BLOCKADDR + BLOCKSIZE, and since we order it by Addres, we can check easy.

That's not an add. If it were, the buddy of 0x1000 would be 0x1400, where the buddy of 0x1400 would be 0x1800 - that's wrong.

It's an XOR. That way, 0x1000 and 0x1400 are buddies. (0x1400 xor 0x400 == 0x1000).

Now, WHEN we allocate something, the first thing we do, is check if there are UNUSED nodes that we can readd to the tree.
If there are no Unused nodes, then we simply make a new node.

When we remove nodes, We will have to check for children.

You needn't keep track of the unused nodes. You can abstract that away using an Allocator or something to do allocation and freeing for you. In C++, you can easily make an allocator that'll just take from an array and put back into the array with little overhead, and so that only one block will be used.

BUT... What happens if there is no Left node?
After a little pondering, head scratching and coffee slurping, I have come up with this...

The entire story was only if it had two children. If it has one, replace it by that one. If it has none, just remove it. Only when it has two must you think.


Allocation is relative. Make an allocator that allocates the tree entries from an array that is not allocated itself (or do make it allocated, if you like, but properly test the corner cases!). That way, there's no unused/free difference and you can keep your code cleaner and more reusable. And if it's good, I'd like to use it in my OS too

Ive got my current system working under Windows / Linux in a 'VMM Block playground' (64mb of space allocated, in which the VMM does its stuff).

Im having trouble with Overhead.
Atm, I workout how much space would be needed for all the tracking structure needed to track 64mb in 256b chunks.
Its about 5mb, Which makes it we have 59mb availible.

(I know, 5mb for tracking is HORRIBLE. Im working on a better idea now). Also, the 59mb availible screws up the numbers.

The blocks dont end up evenly divisable by two.

Would you mind explaining your Array idea? and only using one block? It sounds very appealing.

So far, My first Buddy allocation system (eh... bad, inefficient), can Allocate blocks, Merge blocks, split blocks, free blocks.

Im using One Binary Search tree, and an unused list, like my concept above said, except like you said, my buddy checking system was wrong, which ive got around. I wrote a 'fastsearch' function that searches through the tree looking for the right address, finds it, merges the buddies.

Still, its not good enough.

Hopefully Ill see you on ICQ soonish Candy!

~Zeii.

zeii wrote: Im having trouble with Overhead.
Atm, I workout how much space would be needed for all the tracking structure needed to track 64mb in 256b chunks.
Its about 5mb, Which makes it we have 59mb availible.

(I know, 5mb for tracking is HORRIBLE. Im working on a better idea now). Also, the 59mb availible screws up the numbers.

Explain how you get to 5MB. I told you my idea for a constant-time allocator (in part) which has about the worst amount of overhead possible, where the dynamic overhead can be reduced with a corresponding increase in static overhead, up to a certain level. It's got a constant overhead per allocation too, which is probably what's bogging you down. You only have 8% overhead, so that's pretty ok.

Would you mind explaining your Array idea? and only using one block? It sounds very appealing.

Read your chatlogs back, it's in there in whole. It's a part of the compression stuff, that reduces overhead. If it's in any way clear, post it here as well.

So far, My first Buddy allocation system (eh... bad, inefficient), can Allocate blocks, Merge blocks, split blocks, free blocks.

If it does that while handling all corner cases correctly then it's not bad at all.

Im using One Binary Search tree, and an unused list, like my concept above said, except like you said, my buddy checking system was wrong, which ive got around. I wrote a 'fastsearch' function that searches through the tree looking for the right address, finds it, merges the buddies.

Still, its not good enough.

If you want your code to be public, publish it here and ask others for a review. The buddy system isn't that complex (not simple, but not that complex) so I think a lot of people can comment on your style as well.

Hopefully Ill see you on ICQ soonish Candy!

Not likely. I'm only on on evenings I have time off, which is not often. Probably the first time will be monday evening GMT, about tuesday night/morning at your place.