How to manage header chunks in Buddy's algorithm?

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:

[nil<-header1->nil][data1 ...............................]

      

        
        
        
      

    

Where data1

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 data1

.

[nil<-header1->header2][data1........[header1<-header2->nil][data2]........]

      

        
        
        
      

    

This new one header2

must have an offset of next

-1 to indicate that it is at the end of the list, with the previous offset returning by header1

for its peer. header1

also has to update its next offset to point to header2

, and we have to make both sizes 128 bytes (half of what header1

was originally saved before the block was split).

We can then return a pointer to data1

so that the client can write as it wants and also mark header1

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 data1

to header1

. We can also see from header1

that its neighbor header2

, which is currently not in use, is the same size as that header1

, making it a merge buddy. So when can we unite.

The process is very simple. header1's

the next offset is simply overwritten with the header2's

next offset, which is -1, and its size is doubled. We will still keep this data header2

in memory until the user overwrites it (unless it's a style operation calloc

where we write 0s to overwrite it ourselves). However, this is just a lingering artifact floating around in memory now meant to be overwritten.

[nil<-header1->nil][data1 ...............................]

      

        
        
        
      

    

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.