Basic memory allocators explained in 10 minutes
There's a lot of crap out there about memory allocators. Try searching for explanations about slab allocators and there'll be a lot of prattling on about OS resources, which is something slab allocators can be used for, but it's not what they are. So I'm going to quickly cover the basics of several simple memory allocators!
Bump allocator
The bump allocator is the fastest allocator there is. All it does is give you a pointer to where it currently is, then advances the pointer by the requested size. Super simple. It can't free memory however. Bump allocators are useful because you can give them a fixed size chunk to allocate from and then reset them at some point where you know you're done with all the resources. For example, in gamedev you can allocate stuff into it that will only last until the end of the frame, then reset it. Very fast, very efficient, not great for general purpose.
Buddy allocator
A buddy allocator is assigned some power of two memory region and then creates a binary tree to allocate the smallest power of two size memory that will fit, often a minimum size of 4kb. So if you have a completely clear buddy allocator of 256k and you request 16k, it'll split into two chunks of 128k, then split one of those into two of 64k, then 32k, then 16k, and allocate one. When freeing you check if the buddy of the freed chunk is free, if it is you merge the chunks back up into the larger size.
Buddy allocators are relatively simple and have the advantage that you can store a bitfield outside of the memory it manages of which chunks at all levels are free/allocated so that the actual memory inside the allocator remains contiguous.
Slab allocator
Don't believe anything you read on Google about OS resources and other bullshit, a slab allocator is literally just a fucking array with a singly linked list pointing at the next free item. That is, slab allocators are meant to give you single elements of one size, which often means they're used for one specific type of item.
They're very fast and efficient and unlike a bump allocator can free items, but do need to maintain a linked list and are limited by a single size of allocation for a single item. You can fancy these up by creating an additional linked list that points at multiple buffers rather than using a single buffer, so you can dynamically grow and shrink the amount of memory the allocator is using.
Freelist allocator
By far the most complex, a freelist takes a region of memory and divides it up by chunks that fit the requested allocations, keeping a linked list of free chunks (hence the name) so that it only has to search that list to find a chunk that fits when allocating. When previously allocated chunks are freed they're merged with any free chunks that neighbour them.
The tricky bit is that since you're building a memory allocated you generally don't have a linked list implementation just sitting around (cause that requires a memory allocator, wahey!) so you have to implement the list inside the memory region that holds the allocations. This can be done many ways, but the easiest is for chunks to add a small section of memory before the memory intended to be used by the calling code, and storing whether the chunk is free or allocated, its size (including the header) so we can reach the next chunk, and:
* if an allocated block, the size of the previous block, so it's easier to merge with a preceding block of free memory when being freed
* if a free block, where the previous/next free blocks in the linked list can be found
You can get fancy about this. Some freelists use a singly linked list that's kept sorted (so previous is always behind and next is always ahead in memory), and some use a single bit for allocated chunks to store whether the previous chunk is free or not, then store a footer at the end of free chunks which also contains the size, to save on memory wasted. But that's all garnish, the basics aren't that bad.
Conclusion
These are the basics of several memory allocator types. General purpose memory allocators will tend to be a mixture or composition of multiple types of allocators. Feel free to ask questions and share if you found this helpful, cause someone else may too.
Additional reading:
* Why std::allocator sucks and how to create a good allocator via composition: CppCon 2015: Andrei Alexandrescu “std::allocator...” [https://www.youtube.com/watch?v=LIb3L4vKZ7U]
* How to design a freelist: GWU OS: memory allocation - malloc and free [https://www.youtube.com/watch?v=5zvu7vyypt0] by Gabriel Parmer [https://www.youtube.com/user/nothing6001]
* Slab and buddy allocators: GWU OS: Memory Allocation - Slab and Buddy Allocators [https://www.youtube.com/watch?v=DRAHRJEAEso] by Gabriel Parmer [https://www.youtube.com/user/nothing6001]
Edit: oh and read the comments, people are saying helpful stuff in there!
