Hello Chris,

I was inspired by your minimalist C library article, and the simplicity of your hashtries and arenas, to implement in the same spirit a Buddy allocator. I have written an article on it, if you have some time to skim it: https://jvernay.fr/en/blog/buddy-allocator/implementation/

Have a nice day,
- Julien Vernay.

> It doesn't even know the address of the region it's managing

One interesting property is that the metadata are almost serializable,
if the three pointers in JvBuddy are replaced with offsets.
Not sure if something useful can be done with it. Maybe it could be used
to cache HTTP payloads of various sizes in a single file on disk?

> Your allocator nearly supports internal pointers.

jvBuddyQuery does permit this usage, even though I did not thought of it.
I never needed internal pointer, but it makes sense when considering garbage collection.

> I haven't had a real world case where I've needed a buddy allocator.

I work for the custom engine of a AAA game, so given the 25yo codebase + 100 programmers
+ the game is open to 3rd party mods, it is hard to survey every memory usage 🥲
To be more resilient on memory on consoles, I wanted to leverage writable file mappings,
which the OS is free to swap to disk (memory swapping is not activated by default).
So I create a big file mapping of 4 GiB, and at the end of our general allocator,
if the allocation is more than 1 MiB, use the file mapping instead of syscall.
Thus, the OS is free to make disk write when physical RAM becomes tight.

Another use case for work which I have not tested yet, is to reserve a big address range
with VirtualAlloc and MEM_WRITE_WATCH, then call GetWriteWatch() regularly to observe
memory patterns and maybe detect unexpected hot memory usage.

Finally, I think it could be useful for performance, to MEM_RESERVE a big address range
at first (at which point the OS sets up the page table) and then to MEM_COMMIT during
execution (at which point the OS maps physical RAM to virtual addressse). So half the
cost of VirtualAlloc can be amortized at program startup instead of eg. main loop.
To be tested!

> I never got around to writing about it, but here's my buddy allocator from
> earlier this year [...] then wrote a "minimalist" conservative garbage collector

I never thought about GC, mainly because for the few times I needed "interesting" lifetimes,
refcount has been sufficient and simpler, or weak handles with generational IDs.

> It accepts the region up-front and carves metadata out of it

Because my implementation always return offset 0 for the first successful allocation,
using the managed region to store metadata is possible too:

    char buffer[SIZE];
    int64_t metaSize = jvBuddyGetMetadataSize(params);
    assert(metaSize < sizeof(buffer));
    pBuddy = jvBuddyInit(params, buffer);
    jvBuddyAlloc(pBuddy, metaSize);
    // At this point, the buddy is usable, and will never mess with the metadata.

Have a nice day,
- Julien Vernay.

Interesting, thanks for sharing, Julien! Good overview, and easy to read 
code. Returning offsets rather than pointers is an interesting decision. I 
implemented a buddy allocator of my own 3 months ago, and it didn't take 
long to realize that internally it ought to work in terms of offsets. It's 
a natural choice simply to return those offsets. In your case, of course, 
it doesn't even know the address of the region it's managing, which is an 
interesting twist!

You didn't mention it in your write-up, but your allocator nearly supports 
internal pointers. Low offset bits are ignored by early right-shifts, and 
jvBuddyQuery can find a block from any pointer within — but importantly, 
*not* one-past-the-end. It doesn't quite work out with jvBuddyFree, which 
gets confused if it points outside the first min chunk, and it messes up 
the metadata. Perfectly reasonable since you never promised this would 
work! Though that means, without code changes, if I know I'm dealing with 
a potential internal pointer I could jvBuddyQuery to get the base offset, 
then use that with jvBuddyFree.

I haven't had a real world case where I've needed a buddy allocator. (And 
if I imagine past cases where it might have been useful, I would sooner 
use my since-then experience to transform the problem into one that didn't 
need general purpose allocation in the first place.) My primary imagined 
use case that couldn't be transformed is executing an embedded scripting 
language in a disposable "virtual machine" of sorts, where objects within 
the language have arbitrary, dynamic lifetimes. I could allocate a short 
term buddy allocator from a scratch arena, run the script using it as its 
allocator, then implicitly dispose the whole buddy allocator the usual 
way. A minimalist buddy allocator like yours fits the bill perfectly!

I never got around to writing about it, but here's my buddy allocator from 
earlier this year:

https://github.com/skeeto/scratch/blob/master/misc/buddy.c

It accepts the region up-front and carves metadata out of it, determining 
parameters automatically from the size, though minimizing fragmentation is 
still more fiddly than I like. In my imagined use case I might offer the 
entire unused region of the arena, so that fragmentation wouldn't matter. 
It has a query function (heap_getblock) just like yours. After I realized 
how easy it was to support internal pointers, I embraced it as an explicit 
feature, then wrote a "minimalist" conservative garbage collector, and 
finally on top of that a stack scanning garbage collector library (x86/x64 
Windows-only).