Inside memory management

[Danylo Hlynskyi aka danbst]

What are purposes for functions unpool() and repool()? How do the
work?
How does cd() work? Everything after --a->c is a bit black magic.

[Scott Vokes]

These form Kona's memory management.

cd and ci are for reference counting[rc]. They are "counter-decrement"
and "counter-increment", respectively. When a counter goes to 0, the
structure's memory is repooled. Cyclic references are not allowed. There
are a few ways to create them, currently, but they are bugs and should
fail with errors instead.

[rc]: http://en.wikipedia.org/wiki/Reference_counting

unpool, repool, etc. in km.c form a pool memory allocator. For the
most part, it doesn't use malloc. Instead, it has an array (KPOOL)
pointing to several "lanes" of equally-sized memory blocks, which are
allocated all at once in multiples of the OS page size (typically, 4kb),
and a free list[fl] stack is maintained inside the lanes' unused cells.
KP stores the lanes' heads, so popping from them will allocate memory in
amortized constant time. (Amortized, because when a free list is
emptied, it has to mmap and link in a new page.) cd & repool push a
pointer back to the head of the appropriate lane, or munmap any data
cell larger than 2^KP_MAX (by default, 2^25, i.e. 32 mb). Because of the
reference counting, memory is recycled immediately, but the lanes are
never freed. (The OS is free to swap out idle ones, though.)

[fl]: http://en.wikipedia.org/wiki/Free_list

For example, to unpool a 256 byte region, unpool gets the pointer for
the 2^8 lane's head from KP. That points to the first free cell; the
lane head is mutated to what it points at (the next free cell in that
lane), and the first free cell is returned. repooling a cell changes its
value to the current lane head, and then KP's head for that lane is set
the newly repooled cell.

For a pool allocator in more conventional C, look at [mpool] - the
implementation is not identical, but the main ideas are the same. (It
handles allocation of memory chunks larger than PAGE_SIZE a bit
differently.)

[mpool]: http://github.com/silentbicycle/mpool

Hope that helps,
Scott