Writing a simple pool allocator in C

This code is very beautifully written, thanks for sharing.

However, you should consult the book "C: Interfaces and Implementations" by Dave Hanson, which has a library called "Arena" that is very similar to your "Pool"s, and it shows a few more tricks to make the code safer and easier to read (Chapters 5+6, 6 in particular).

D. Hanson's book (written in the 'literary programming' style invented by Donal Knuth) also demonstrates having debugging and production implementations for the same C API to catch memory errors, and his book is from 1997:

  > Copyright © 1997 by David R. Hanson

If you write your own allocator in C, do yourself a favor and use the valgrind API inside it. Its use can be conditional so you can "compile it out". Or should I say it has to be, so you can build the code in an environment where there's no valgrind API.

One aspect people don't tend to mention (and TFA does not because it has "general purpose" as a scope) about doing your own allocation arenas is that because a "pointer" is just the name (really number) of an allocated region, this also affords flexibility in the width of those numbers aka "pointer size" that decides your "address" space.

So, for example, if you are willing to limit yourself to 64 KiNodes of equal sized objects, a pool like https://github.com/c-blake/bst/blob/main/POOL.c can use an unsigned short 2-byte pointer. This small address space specialization can give a full 4x space overhead optimization over modern 64-bit pointers.

You could even use 8x less with 1-byte pointers if 256 nodes is enough or use bit fields or equivalents for even more fine-grained address space size selection. Admittedly, linked structures are usually less interesting for very small address space sizes, but this is sometimes useful. People may complain about arbitrary limits that relate to this kind of optimization, but the linked part could be "small by design" without compromising overall scale { such as for structure within a B-tree node or other multi-level indexing setups }.

In any event, I think it is useful to highlight pointer size arbitrariness to junior engineers. It is often learned once & immediately forgotten behind an onslaught of general purpose-ness (& pointer type systems/syntax). Relocation ideas also relate. E.g., if all the pointers are implicitly indices into a (small?) array, and all the code needs a "base address" of that array to get a VMem address, then you can relocate the whole bundle of objects pretty easily changing only the base address.

Hello, I am the author. Thank you all for the instructive comments, I made some changes to the article since I first posted it:

- Added a link to this HN post.

- Renamed some variables and types in the code for readability.

- Mention (in a footnote) that we could allocate the 'Pool' structure and the chunk arrays with a single call, or even return the 'Pool' on the stack. Suggested by 'liontwist' and 'unwind'.

- Mention (in a footnote) that we don't always need to store the full address when building the linked list of free chunks. Suggested by 'cb321'.

- Added valgrind support (also to my 'libpool' project). Suggested by 'kazinator'.

A long time ago, in a galaxy far far away, i wrote something similar for an embedded platform. I was implementing a WAP Browser at the time (yes, WAP, https://en.wikipedia.org/wiki/Wireless_Application_Protocol), and we needed dynamic memory allocation in an environment where everything was static due to realtime constraints.

So i ended up with this : https://github.com/jinie/memmgr

The parent article is quite interesting and slightly different being cpp [1]. There is also a post about writing a memory allocator [2].

[1]: http://dmitrysoshnikov.com/compilers/writing-a-pool-allocato...

[2]: http://dmitrysoshnikov.com/compilers/writing-a-memory-alloca...

Here's another interesting O(1) memory allocator but with arbitrary sized allocations and low fragmentation. Negative side is relatively high memory overhead (a few dozen bytes per allocation).

This kind of allocator is often used to suballocate GPU memory in game and graphics applications.

I'm using a variant of this algorithm with added support for shrinkable and aligned allocations and flexible bin sizing.

You can also extend this idea to two dimensions to create texture atlases, which is possible in O(1) for power of two sized allocations.

Original: https://github.com/sebbbi/OffsetAllocator Rust port: https://crates.io/crates/offset-allocator

(related) LLFree

Paper: LLFree: Scalable and Optionally-Persistent Page-Frame Allocation https://www.usenix.org/system/files/atc23-wrenger.pdf

Video presentation: https://www.youtube.com/watch?v=yvd3D5VOHc8

Implementation and benchmarks are well documented at the repos:

Rust repo https://github.com/luhsra/llfree-rs C repo https://github.com/luhsra/llfree-c

What I find weird is that the chunk's size is fixed, while the caller must specify how many chunks a pool contains at pool creation. I would do exactly the dual: the chunk's size should be defined at pool creation, so that you can create multiple pools, each dedicated to one specific kind of object. (You need a third field in struct Pool, though.) Instead, the number of chunks per pool should not something the user needs to care about: if they knew in advance how many objects are required, they would simply allocate an array big enough! The library implementation should define a sensible number and stick to it.

Similarly, I don't like exposing pool_expand(): too much burden on the user. Expansion should be automatically triggered by pool_alloc() whenever the current pool is exhausted.

This would also allow a much simpler pool_new() that just initializes its pointers to NULL, leaving it to the first invocation of pool_alloc() to actually do the first allocation. This would avoid the duplication of code between pool_new() and pool_expand().

Another benefit of fixing the number of chunks is a possible simplification of ArrayStart: this could include a proper array instead of a pointer, avoiding a malloc(). Something like this:

  struct ArrayStart {
    struct ArrayStart *next;
    Chunk arr[CHUNKS_PER_ARRAY];
  };

There is a small series of posts on the BitSquid blog about memory allocation which is worth reading! http://bitsquid.blogspot.com/2015/08/allocation-adventures-3...

It all depends on the load profile using the allocator. You never know, that said you cannot beat, in theory, a semantically specialized allocator for a specific load... in other words, the right way(TM). This means applications should bundle their own allocators for the various load types they have. The "generic" allocator is sort of an heresy for the lazy, short termists or those who are in hurry. Don't worry I still use such generic allocator, sometimes, but often I do mmap myself the memory and deal directly with it.

Also "Arena allocator tips and tricks (nullprogram.com)" [0]

[0] https://news.ycombinator.com/item?id=37670740