How to manage header chunks in Buddy's algorithm?
I am working on tcmalloc for learning about memory management. But there is also a part that I cannot understand. When using buddy algorithmn , how do you manage chunks of headers when you split or merge blocks? I mean, when you merge two chunks, you don't need two headers anymore, so what? Are you just freeing up memory? You can't free up memory space between two chunks if I'm not mistaken.
So any help or links are appreciated ^^
EDIT: After talking to some people, I found out that I need to manage the chunk header in a different area of memory. It is right? How can i do this?
source to share
I think one part where you might get confused is that there is nothing wrong with overwriting the memory where existing headers are stored. In fact, what you want to do efficiently is when you combine blocks via merge, in addition to inserting new headers on the fly when you split them.
So if we present a simplified example where your -0 blocks are 64 bytes and your largest -3 blocks are 256 bytes, then we start with a 256-byte block like this:
is the memory available to the client, requesting memory to overwrite as it pleases. As a basic example, let's say you are using 8-byte 64-bit alignment headers that store cumulative offsets to the adjacent previous / next block along with a flag indicating which blocks are used and their size (a block is a buddy if it has an offset next / prev, which makes it contiguous and matches the same size). Initially, these values can be -1 to indicate that there are no adjacent blocks available.
Another way to look at this starting block of about 256 bytes is that there should be enough room for 4 blocks of order-0. So the total block memory should be 256 + 4 * 8 bytes or 288 bytes.
Now let's say the client asks for 128 bytes. In this case, we need to split our block of about 256 bytes into two blocks of order -1, halving their size. In this process, we can insert a new header in the middle, 128 bytes after the address where it starts
This new one
must have an offset of
-1 to indicate that it is at the end of the list, with the previous offset returning by
for its peer.
also has to update its next offset to point to
, and we have to make both sizes 128 bytes (half of what
was originally saved before the block was split).
We can then return a pointer to
so that the client can write as it wants and also mark
as in use.
Now let's say the client then asks to free this block. In this case, we can subtract 8 bytes from the memory address it transfers to get from
. We can also see from
that its neighbor
, which is currently not in use, is the same size as that
, making it a merge buddy. So when can we unite.
The process is very simple.
the next offset is simply overwritten with the
next offset, which is -1, and its size is doubled. We will still keep this data
in memory until the user overwrites it (unless it's a style operation
where we write 0s to overwrite it ourselves). However, this is just a lingering artifact floating around in memory now meant to be overwritten.
This describes a fairly basic implementation, and I've only looked at one possibility of how to handle splits and merges. You can also get fancy and store the headers in a separate memory space, but this will often offer a little more overhead with looking up of some sort to get the relevant header information from the pointer. This can be useful for reducing memory overhead by using the smallest order-0 blocks (mostly avoiding alignment requirements), but is a little harder to do quickly. When the title is stored in the same location, we can do something basic like a simple subtraction to get the content of the title.
source to share