Is there any book about memory allocators ?

[gilesgoat]

Recently I had to write a "sort of" memory allocator, too long to explain but I had to.

"In the end I kinda cheated" well sort of because in reality is "a mem allocator for a specific purporse and a special case of how that memory is called/used" so I had the luck to have the possibility to give/take mem "in a certain way".

However .. "if you think at the general problem" it gets complicated almost immediately.

So you have in essence "a big blob of mem A" let's say "Starts at 0 ends up at PoolSize-1" ..

Any time you need a "block" X of N "size" you could advance a PTR and return it.

And let's say you have a list that says "Block X of size N is in-use" ..

Eventually you can ran out of "PoolSize" and then the memory is all over .. ok no problem.

Then you have the "free" someone says "I don't need X any more", you can mark that block as "Free" ..

And there starts where I started to go into "bananez territory", first of all even this "list of blocks" cannot be "infinite" and/or "expand all time" becuase it would mean that then you have "a mem allocator" for the list itself but still in any case "can't expand to infinite".

It may get to a point you still in theory have free mem in "Pool A" but you exhausted all mem to keep track of it.

But then ok suppose you say "I don't need X any more" .. I tried to say "ok let's scan the list and look for ALL the blocks
marked as 'free' and see if there are TWO or more 'consecutive blocks' marked as free that I could 'merge' into ONE single block of ( N-1 + N ) of "size sum of the two sizes" ..

I.e. if "block 10" started ad "PTR 00" of size "100" and "block 11" started at "PTR 100" of "size 50" you could make "block 10" become "start at PTR 00, size 150" and mark "block 11" as "not in use" so you still have " a free list element" you can use for later.

I think that's what they call "coalescence" of mem block and/or I suppose you could call it "defrag".

But likewise "it's pointless" if you don't have a "split" so suppose you need a block of "size Y" and after you searched all your list of "free blocks" you find the MINIMAL one that can contain Y but you find it is still bigger than Y.

You could, assuming you have still some space in that list "split" it into a block of Y-required size ( and assign it to a not-in-use block and made it 'free' , or even better you should merge it in another ) and one of 'required size' ..

And all that above sounds "reasonable" until .. until you get FUCKED by "a small problem" .. alignment ..

You will find out that "not only you need a mem block of size X" but that "ptr" returned has to be aligned at 8, or 16 .. or else bytes .. which is not a huge problem per-se but becomes "a really big problem" when you try to merge blocks ..

I think "unavoidably" if you have something that requests/releases mem blocks all time you end up with a "gruyere of memory and crap all over the place".

I spent about 4 days over this sort of crap, in the end I cheated a bit on the consideration that "hang on, cause what is happening here I don't really need all that complication".

It did work but I wasn't so happy because I haven't "fully solved the problem the elegant way".

However made me think "I can't even imagine what crap happens to the mem with all those things that do dynamic alloc/free all the time" ..

And also, could not find any good documentation about this sort of problems.

The little I found in the past looking around ALMOST ALWAYS ended up with a sentence like " .. and this problem is too complex to be described here it would required a book of its own .. " ..

Where are those books ?

[venusian]

I have implemented malloc/free/realloc exactly once (so take with a grain of salt) but I think I did it in the canonical way.

First off, you don't need separate memory for your free/used list and other metadata - the memory in the pool is the memory used to build the list. The pool is split into blocks. Every block has three fields at the start of it: the size of the block, the size the user has been told, and the pointer to the next block. These should be immutable outside of the allocator's code so including a checksum would be a reasonable way of checking for corruption. The memory given to the user comes from these blocks, but they don't get the whole of the block. Thus, the memory pool holds its own list and so you can never run out of memory for the list whilst actual memory remains unallocated. (This only works for physically backed memory, of course; virtual allocators do need additional memory.)

When you allocate a block, you need a block that's the user's requested size, plus the three fields, plus any alignment (plus a virtual gap if you want realloc to behave "nicely"). The user gets the address of the first byte after the header. When they free it, they give you their pointer back, then you subtract the size of the three fields and you've got a block pointer again. If you have alignment to track, you'd need an additional field right before the user's pointer in order to find the header.

At system start-up you have a pointer to the whole of memory, which has three fields: block_size=$MEMSIZE, user_size=<n/a> and next=NULL.

On malloc(), find a big enough block in the free list, break it into two. One goes back on the freelist (usually optimised as an in-place mutation), the other is given to the user (there is no used-list). The header values are trivial to set up.

On free(), simply add the block back to the freelist.

On realloc(), nudge up the user-size if there's room else call malloc and memcpy under the covers

If malloc() fails because there isn't a big enough block, you do the only complex thing in the system: concatenate contiguous blocks on the freelist, then call malloc again. if you still can't satisfy the request, give up. Concatenation is slow; might if O(x^2) or worse.

It's a couple of screenfuls of code for the naïve implemenation)

If you're serious about performance, there're many questions and variations:
- given many big-enough free blocks, which to split?
- concatenate continually, or wait for a malloc fail?
- cache fighting might influence what blocks you allocate

There are slab allocations, buddy allocators...

For discussion in books, I'd look for OS and systems programming books. The BSD book has a few chapters on it for sure.

[KlaxonCow]

One thing to note is that one way to avoid the problems of memory fragmentation is to create fixed-sized memory pools.

That is, I've got a template class in my C++ code - "template <typename Type> class Pool" - which will create a (dynamic) array of "Type" objects.

The problem with memory fragmentation is that you could do a lot of little allocations, and then you release that memory in whatever random order, and now you've got a "Swiss cheese" of allocations and gaps.

And the classic example is that you've got, say, 1GB of RAM. Inside that, you allocate 512MB. Then you allocate 52 bytes. Then you release the 512MB of RAM.

So what you've got is 1GB of RAM where the first 512MB is now "free memory", then there's 52 bytes sat in the middle, then you've got another (512MB - 52 bytes) after that. There's this bloody small allocation sat right in the middle.

And the problem is that you want to now allocate 768MB. You've actually got that much free RAM there. But you can't allocate it, because you don't have 768MB of contiguous space. That allocation in the middle is getting in the way.

And, of course, that's just my trivial example to illustrate the point. In reality, you've actually got loads of allocations and deallocations, and this problem can get real gnarly, with that memory space becoming a horrible "Swiss cheese" full of tiny little gaps that you can't usefully allocate for anything else.

This is where my "Pool" concept comes in. It's a pool of "Type" objects. Every object in the pool is of a known fixed size (namely, "sizeof(Type)").

And this avoids the fragmentation problem because though the pool will also fragment, the gaps that are left are of fixed size and always big enough to allocate a new "Type" object.

In a sense, the problem with fragmenting memory comes from having variable-sized allocations and deallocations. 42 bytes here, 3MB there, 69 bytes over here. So when it inevitably fragments, you end up with a Swiss cheese of variable-sized gaps. And those gaps might be too small to practically use.

But if we - as I do with my "Pool" class - have it that only "Type" objects, of a known fixed size, can be allocated in that space, then the gaps are always going to be "sizeof(Type)", which is always big enough to re-use that gap to allocate a new "Type" object again.

So the idea is that I might have "Pool<Sprite> sprites" and then reserve "slots" for 1000 sprites (so "1000 * sizeof(Sprite)" is allocated in RAM and all of these "slots" are put on the "free list").

When I want to create a new sprite, I call the "allocate" of Pool, which looks for a free slot, runs an in-place "new" on it (to make sure we're getting a brand new "Type" object) and then hands it to the application. When I no longer need it, I call "deallocate" and this'll run the deconstructor (to make sure that the object is properly deconstructed) and will return it back to the "free list".

The fixed size makes all the difference. Because though the pool will become a bit of a Swiss cheese of gaps and allocations, as sprites are created and destroyed in the game, the gaps are always "sizeof(Sprite)" which means I can always allocate a new "Sprite" from the pool. The gaps are a fixed size and always useful for re-use of that slot over and over.

So another thing to consider, alongside your memory allocator, is that HOW you use memory in your code can make things easier / harder for memory allocations.

(My "Pool" class is actually derived from a "Vector" class, which is itself derived from a "Mapping" class, and that's actually a wrapper for raw "mmap" / "VirtualAlloc" whole 4K page allocations and reallocations. I've even made sure all of them properly implement "move" semantics as well, as I wanted as close to "zero memory copying" as possible.

Because the "Mapping" class only deals with whole 4K pages, though it keeps track of how much was actually requested. So if you ask for 42 bytes, it actually grabs a whole 4K page, but then records "size" as 42.

The first trick there being that if you then reallocate it to, say, 69 bytes, there is no need to actually reallocate any memory. It can just change "size" to 69 and return.

The second trick is that if it does need to reallocate new pages, I'm using the OS "mmap / mremap" (or Windows equivalent "VirtualAlloc", which can also do remapping). And what the OS is really doing is re-arranging its page tables. Pages can basically be anywhere in physical RAM, but the OS provides - via page tables - a contiguous "virtual address space" to the application.

So when you need another extra page, what the OS is really doing is grabbing a 4K page from basically anywhere in physical RAM but then it maps it into the application's "virtual address space" as a contiguous chunk of memory. It's just playing with page tables, and no memory copy (or, worse, the dreaded "create a new object, copy over the data from the old object, delete the old object" type of reallocation - which is basically the thing that I'm trying to avoid like the plague to have implemented all these classes that never do things that way, and endeavour to be as "zero copy" as they possibly can be).

Note that the OS page-based allocation and reallocation also works in a similar way to my "Pool" class, in that pages are fixed-size (4K on the x86). So you've got that same idea that though, with lots of allocations and deallocations, the physical RAM could become quite the "Swiss cheese" of allocated and unallocated pages, because they're all the same size, whenever I release a page and it goes back on the "free list", it's always possible to re-use that to allocate a new page.

So what I'm saying is that if you have a pool of fixed-sized objects, then you naturally avoid memory fragmentation becoming a problem. The problem is variable-sized gaps, really. But if you structure things in such a way that all your gaps are fixed-size (a pool of "Type" objects only), then you can allocate / deallocate / re-use from that "pool" all you like, and you can always allocate a new "Type" - re-use a gap - every time. The gaps are fixed-sized, so always useful to allocate a new "Type" object.

Thus, you know, once I've got my "Pool" class, then I can do things like "Pool<Sprite> sprites" or "Pool<Sound> sounds" and create these pools of similar objects, where I can grab a "free slot" and use it, then return it to the pool for re-use later on. The pool does actually fragment over time, but never in a problematic way.


(A further extension, which I've not implemented yet, is to take a leaf from the OS's "page tables" and have a level of indirection in there. So that you've actually got a "pointer to a pointer to an object" - though wrapped up in such a way that it acts just like a pointer to the application - but the idea is that it allows objects to be moved in memory, so that data structures can actually consolidate the RAM - move stuff around to remove any gaps - but code using these pointers has no idea that the RAM is actually being shuffled around.

Because the real problem, underlying it all, is that your memory allocator hands the application a pointer to the allocated memory and then it cannot move it. Because that code has that pointer to that RAM, so that RAM can't move or it'd make that pointer invalid. But, as I say, one idea I might play with is a "Pointer" class that actually hides an extra layer of indirection. The pointer you're returned is not actually directly to the allocated memory, but to a pointer to the allocated memory (a pointer to a pointer to a Type object), and therefore we actually could move the object in RAM by changing that hidden "inner pointer" to the new location.

Then, if that's possible, you could actually have data structures that can consolidate RAM. They can "garbage collect" those gaps and remove them, by shifting things down in RAM, at an opportune idle moment. But that's just an idea, and I've not actually implemented that one. There might be "gotchas" to the actual implementation that I've not thought of yet.)

[venusian]

That's a slab allocator.

[KlaxonCow]

That's a slab allocator.

Yup.

But my description tells you how it works. Just calling it "a slab allocator" only tells you that you know the names of things.

[venusian]

The fact that it's a slab allocator, a well understood construction in the field, is missing from your explanation so I added it for you. If you'd internalised your own video you would have been aware that names are an important tool if you wish to talk with other people.

[KlaxonCow]

The fact that it's a slab allocator, a well understood construction in the field, is missing from your explanation so I added it for you.

Thank you.

[Dio]

Don't write your own memory allocators if they are any more complex than a basic growing buffer allocator. They are much trickier than they look (especially when threads get involved) and they need a lot of extra work if you're going to get proper debugging information out of them. A robust, well tested basic memory allocator is a multiple month project; a full-featured one much more.

There are hundreds of them out there, and even if none of them exactly fit your needs you would be better taking a well-used working one and customising it. The most likely reason to write one from scratch is to learn how to write one, I suspect.

[KlaxonCow]

In fairness, my classes are all about NOT allocating / deallocating.

The "Pool" class has a bunch of re-usable "slots". Allocated up-front and then you just grab an object, use it and put it back, so you're NOT allocating and deallocating memory all the time (it does in-place "new" and "delete" so that the objects are constructed / deconstructed properly, but the memory itself is not freed / allocated and is re-used).

The "Vector" class which its based on (basically, a "Pool" is a "Vector" plus a free list to keep track of what's in use and available), is itself derived from the "Mapping" class and, as mentioned, that's a wrapper around "mmap" / "mremap" exactly because you can get a low-cost reallocation by the OS playing with its page tables. Also, it works in whole 4K pages, so there's a "reserve" on it. It won't actually reallocate anything going from, say, 42 bytes to 69 bytes. Just alters an internal "size" variable. So the calls to the OS only happen when we cross a page boundary (and the OS, under the hood, is just grabbing some arbitrary physical page - need not be contiguous - and is presenting it to the application as contiguous memory through its virtual address space, and I'm taking advantage of this for super-fast low-cost reallocations. Yes, I'm using "mmap" on Linux there, but Windows pretty much works in exactly the same way with "VirtualAlloc" / "VirtualFree" - same underlying memory model - so it works just as well over there, albeit that the API has a different name).

I'm creating these classes exactly so that the application has an "avoid allocation / deallocation" mindset. I'm writing these classes exactly because I don't want the memory allocator, unless it's absolutely necessary. Because I want that "no allocations / deallocations within the main loop" thing from the ground up.

The classes exist to be anti-memory-allocator, as it were. To avoid ever calling it. To re-use and reallocate and recycle all the way, unless there really is no more available "slots" and it has to create some more (but then it'll create whole 4K pages worth of "reserve" on that, so it'll only actually reallocate when it really has to).

Also, you mentioned debugging. I've got some "vanishing code" debugging macros - if "DEBUG" is defined then the code is included but, if not, then all that code equates to absolutely nothing and vanishes. And, in "debug mode", the "Pool" class actually keeps track of allocations as well as the free list (printed out to my debug log for later review), but when "debug mode" is off, it's only the free list. So, during development, with debugging turned on, I get a report on exactly what's allocated where and when, to track it all. But this all vanishes in "release mode", so doesn't impact performance in the final version.

This is another big reason for my classes. This is C / C++ code, so most bugs tend to be memory-related - memory leaks, double free, dereferencing a nullptr, etc. - and my classes really dig down on that. Keeping track of all that in "debug mode" to trace where things are going wrong, and a simple "has everything been released?" check in the deconstructor quickly double-checks that all allocations were deallocated by program's end. Though, note, as it's all based on "mmap" at the bottom of this class tree, I can still just unmap everything and all memory taken is returned, so I'm really doubling down on those "logical memory leaks" - where deallocations don't match allocations properly - but it can still give all allocated memory back at program's end anyway (because all of it's coming from the "Mapping" class, which can unmap the memory pages in the deconstructor regardless, but then flags up that it was not properly released).

And it's little things like that which you simply don't get from someone else's libraries. Because they're written to be generic, they don't / can't lean into debug logging, they don't do the extra debug checks - asserts, essentially - that all is in order and as expected.

And, generally, there's a balance with "should I use my own code, or lean on a library?". There's more effort to get "own code" working, sure, but with the logging and debug checks and stuff, it pays for itself on the other end, as debugging code goes way smoother - with most libraries, you get zero debugging feedback like this, so when things are wrong, tracking it down is a lot more work. My classes are very chatty with the debug log in debugging mode, so I can usually hone in on what's going wrong pretty quickly through the debug log.

That's a big one. Someone else's library(tm) usually gives zero feedback. My classes, in debug mode, give an abundance of feedback. So there is a "pays for itself" thing going on there, as the one-time effort of coding up these classes is paid back by all the time I'm not fucking around trying to find out why the memory allocations aren't working or how the hell I got a "nullptr" there, when it shouldn't possible.

A lot of what makes C / C++ coding hard is that, by default and convention, you get fuck all feedback on these kinds of things and every library I've seen works that way ("the C way"). But my classes basically have a built-in "valgrind" in debug mode.

It's short-termism vs. long-termism: The fastest route from point A to B isn't always a straight line.

[Dio]

An allocator that can't track not-freed, double free or basic overrun/underrun checks is simply deficient. Pretty much all libraries include those. Good ones probably also include use-after-free checks (via poison pool and checksum, although that only covers writes; much better is deallocating the block in the VM system) and call site based stats.

Writing all that yourself is a waste of time unless you want to learn these things. They are all easily available elsewhere and easily customised. Indeed the built in VC one includes most of it, although not so customisable.

As for allocation management in the classes using the allocator, RAII tends to be the best way to do it in C++ since it's pretty much impossible to get wrong.

[KlaxonCow]

RAII tends to be the best way to do it in C++

There is a reason why my "Vector" class calls the constructor on a newly acquired "slot" (an in-place "new") and the deconstructor on release (just calls the deconstructor directly). So that RAII all works on the contained types.

Honestly, I've done it already. It works. It's nicely generic that I've used it in a bunch of projects. It functions as a header library, basically.

I've got it now. What's the benefit, at this point, in switching to some other library? That'd just be a learning curve, learning its quirks, putting up with it doing things in some ugly way I don't like much, etc. in order to... get back to exactly the same point I'm at right now anyway.

Like anything, it was a pain to begin with and get it up and running. But that's good - "fail fast, fail often". You learn, you grow.

I chose the Moon. Not because it's easy, but because it's hard.

[venusian]

An allocator that can't track not-freed, double free or basic overrun/underrun checks is simply deficient.

There's an argument to be made that any language that requires these to be part of an allocation library rather than part of the language is deficient.

I wrote my malloc et al because I was building my own embedded OS and userland library, and very specifically wanted zero dependencies on other code. I'd echo Dio's assertion on the pedagogical argument though: by far the best way to learn _why_ something is difficult to try writing it yourself. At least very least it gives you intuition about what's gone wrong when the actual implementation fails. For example, why an underflow will likely kill your whole malloc system rather than just corrupt the previously allocated block.

The philosophy that for every task there's a pre-existing library is not without it's problems. Instead of creating your own bugs, you're simply importing somebody else's along with all the bugs and problems in their dependency chain (because every time that had a task, they used a library to solve it). Then there's the inefficiency involved in using a library slightly differently than the way the author envisaged: the necessity to either fork the library or use the API badly. Dependency inversion depends on the library author having implemented it well, the abstract interfaces being suitably 'good', and your language supporting it in a way that makes the code understandable and maintainable.

I'm reminded of the possibly apocryphal case where a programmer wanted the sort-order first item in a list by doing collection->sort()->first() because they'd been told to use the library API whenever possible.

[Little stoned kiwi]

When I think of a Windows app having it's own private address map, the system MMU, and who knows what in between, it's definately a job for someone else with the time and interest.

[KlaxonCow]

The philosophy that for every task there's a pre-existing library is not without it's problems.

If you think about it, it's also a self-contradictory philosophy.

That is, if everyone depended on other people's code... then who's writing all that library code in the first place?

This philosophy can only stand, allowing others to depend on "someone else's code(tm)" exactly because there is always a "someone else" out there who's ignored this philosophy and actually wrote the library, which everyone else uses, in the first place.

Also, by this logic, Yak and giles should be using Unreal Engine. John Carmack should have just used someone else's code, and stuck with 2D platformers. Notch shouldn't have created his own voxel engine. Et cetera.

[Dio]

My point was simply that spending time and effort writing a memory allocator is much harder than it looks, it's very easily available code with trivial interfacing, and therefore it's a waste of time and effort (which is pretty tightly related to money, if you are a professional programmer) unless you want to learn about writing a memory allocator.

I definitely agree that there's an argument against using C++ etc. for any new (ha!) projects, although I'll note that as of yet nobody has conclusively determined that the advantages and advantages of such languages are convincingly beaten out by others. Rust clearly has promise, and I talk regularly with one game developer who is entirely a Rust shop, but it's taken them years to really get productive with it. Clearly no other language is anywhere near C/C++ in the system / engine programming space.

Also, by this logic, Yak and giles should be using Unreal Engine. John Carmack should have just used someone else's code, and stuck with 2D platformers. Notch shouldn't have created his own voxel engine. Et cetera.

Are you writing your own operating system and video drivers? Filesystem handlers? USB HID processing? Audio interfaces? I guess you're satisfied with the moon when you should be aiming for Mars! Or is that "too hard" for you?