search

Restioson / buddy-allocator-workshop

A workshop for comparing buddy allocator algorithms
Apache License 2.0
16 stars 2 forks source link

Theoretical question: bitmap buddy #1

Open V01D-NULL opened 2 years ago

V01D-NULL commented 2 years ago

Hey, I'm in the process of writing a bitmap based buddy allocator myself, however there are some things I don't quite understand and I hope you could clarify them :)

So, every bit in the bitmap represents a single node, and each node can have two states(1,0). 0 would be "not split" and one would be "split".

But, what if the node is allocated?

Restioson commented 2 years ago

Hi! Bitmap in this case is a bit of a misnomer. How I actually have implemented it is that each block is a byte which stores the largest block size available below itself. If it's allocated, that means that it's 0. If it's totally free, then it's equal to the order that it's at in the tree.

V01D-NULL commented 2 years ago

I'm trying my best to understand the code but I don't know any Rust, sorry for any inconveniences. By storing a byte per node instead of a bit, the size of the tree would be pow(2, 9) * 8 = 4096, right? (Assuming a max order is 9)

Assuming the "bitmap" would just be: unsigned long map;, I should have more than enough space to store it, 

cat /usr/include/limits.h | grep ULONG_MAX
#   define ULONG_MAX    18446744073709551615UL

it's just that 4k is kinda large since a buddy with a max order of 9 can allocate 2MiB at most, and many modern machines have many Gigabytes of RAM- are you sure this (the byte approach) is a good idea?

Restioson commented 2 years ago

it's just that 4k is kinda large since a buddy with a max order of 9 can allocate 2MiB at most, and many modern machines have many Gigabytes of RAM- are you sure this (the byte approach) is a good idea?

I went on to use this approach for physical memory allocation in a hobby operating system, where the lowest block size 1 was equal to 4KiB (one small page on x64). In this case, it was an acceptable size. Ymmv for smaller allocations

V01D-NULL commented 2 years ago

I'm actually using this for a hobby operating system as well :^) Thanks for the clarification, I'll see what I can do :+1:

Restioson commented 2 years ago

Cool and good luck!

By the way, just for interests sake, here's thing that I always wanted to look at implementing was improving the cache locality. As it is, you would except $levels cache hits per allocation, since each level of the tree is far from the other in ram. However, this could potentially be improved by storing several subtrees that are size 64 bytes or so each. Then, you could traverse 3 or 4 levels in each subtree before jumping to the next, cutting the number of cache misses by a factor of 3 or 4. Just an interesting aside :) I couldn't get it working though when I tried.