Fragmentation in slab/LFH vs buddy allocator?

[simeonz]

I am reading on various OS topics. I am examining the trade-offs of general-purpose sub-page allocator designs. Here is what I have so far:

1. "Conventional". Tightly linearly indexed according to free chunk size. Coalescing is performed on all adjacent free memory. Used in Windows kernel-space and in the Windows user-space back end (one of two tiers). Linux user-space may use this too, but don't quote me on that. Comes paired with some front end or cache to ameliorate its drawbacks.
2. Buddy allocator. Linux uses this for page sized allocations. No one seems to use this option for small allocations.
3. Slab/segment based allocator. This is used in the Windows user-space front end (LFH) and in Linux kernel-space allocators.

Drawbacks/advantages (IMHO):

1. Biggest drawback to the conventional approach for me is that small free gaps may appear interspersed between larger busy chunks. Both other allocators theoretically solve this issue by carving small allocations from bigger blocks, thus leaving the possibility to reconstitute larger memory (eventually).
2. The buddy allocator uses perfectly aligned chunks, but unfortunately, the chunk headers have to go somewhere and in the case of small allocations they will probably be stored internally. This breaks the perfect alignment of the allocator, but it doesn't make it worse when compared to the other options. The coalescing I imagine can be quite slower, especially compared to the slab/segment variant.
3. The slab/segment allocator appears to be everyone's favorite, hence the question. It requires larger regions to coalesce before they can be repurposed. Coalescing is fast. Sizes are usually indexed with broader strokes to encourage coalescing. However, to me it has one fatal flaw - sporadic durable allocations will pin their corresponding slabs, causing excessive amount of external fragmentation in specific usage (which is not inconceivable in practice.)

Note that I am not assuming stationary distribution, because every reasonable allocator manages that somehow.

Why do you think was the slab allocator chosen over the buddy allocator in the Linux kernel and for the Windows heap? Do you think it was performance based decision, or does it offer improvements with respect to fragmentation (which I fail to see.)

[~]

Memory managers for paged and multitasked environments are no different to a file system. Memory management was originally thought to serve a single process and at most several threads of a single process. But with multitasking comes the need to use paging (virtual addresses) to provide all of the processes, an address space that they can access contiguously from memory pieces (pages) that are expected to be physically apart in a random order. If you implement a single-process, single-thread OS, you could assign all memory to that process without worrying too much about fragmentation.

But think about the fact that even a single process running would always end up seeing memory fragmentation if it ever allocates memory dynamically. It would always need to keep track of free, reserved and used memory chunks, and if it does many things, it would always end up freeing buffers, objects or structures that are in memory, and it would always end up freeing them in random order, according to the processes it needs to do, so it's in that randomness in freeing memory that the process would always end up seeing memory fragmentation and the need to manage it, if it ever allocates and frees memory dynamically (the simplest being a single-tasking OS with a bit map to keep track of free 65536-byte segments).

Instead of having a disk share its space between many files and directories whose sectors are normally scattered in a random order but linked somehow to retrieve them, we do the same in memory.

We also align data in pages, and we apply access and execution privileges just like an advanced file system.

Since implementing a paged and multitasking-capable memory manager is basically the same as implementing an on-disk file system, fragmentation is impossible to avoid in practice.

Actually, we need to deliberately allocate pages in a random order in memory to prove to ourselves that our memory manager is properly implemented and that it's actually able to easily and efficiently find free and reserved pages no matter how fragmented they are (as they would, for example, when running TV applications, web browsers with dozens of tabs and windows, text editors, compilers and multimedia players), and that is able to know to which process/user all of those pages belong to.

[simeonz]

Since implementing a paged and multitasking-capable memory manager is basically the same as implementing an on-disk file system, fragmentation is impossible to avoid in practice.

Of course. I only ask for opinion on the comparative qualities of the slab and buddy allocator for small allocations.

Some scenarios:

1. Allocation owner abruptly leaves the system. Immediately after that a memory demanding action is initiated.
2. Requests for one service drop in frequency. Some (significant) period of time passes and a memory demanding action is initiated.
3. Some allocations are being attached to durable system objects or object pools, other are attached to in-flight requests. The requests for particular service drop over time, and a memory demanding action is initiated.

My analysis:

1. The adjacency of smaller chunks will promote coalescing. The buddy and slab variants use grouping to achieve this. The slab allocator requires many adjacent frees to coalesce the entire slab, which event's probability declines exponentially with the slab size.
2. The slab allocator can recover over time if optimized. Usually, the optimization is to choose the most populated slab when providing a new chunk. Busy slabs stay busy and sparsely populated slabs gradually completely evacuate. The buddy allocator simply avoids splitting whenever possible.
3. Some allocations stay pinned. This is the eventuality in which I see the slab allocator suffering the most.

In defense of the slab allocator, its header is more compact, its coalescing is faster, and the buddy system tears free chunks on alignment boundaries.

I still wonder. What tilts the scale in favor of the slab allocator over the buddy allocator for heap and pool usage in real systems.