Re: The Slab Allocator (Was: Re: New dcache not using slab allocator?)

Mark Hemment (
Fri, 8 Aug 1997 00:49:45 +0100 (BST)

On Wed, 6 Aug 1997, Martin von Loewis wrote:
> You are probably thinking of a mechanism where you have a list of
> free objects, and do the allocation inline (invoking SLAB if the list
> is empty). I was wondering myself why this has not been done.

It hasn't been done because I haven't had the time, and no-one else has
come forward.

> Here
> a couple of possible reasons:
> - risk of fragmentation. you somehow have to choose when to return memory
> to SLAB, otherwise you risk eating too much memory.

As a rule of thumb, large objects tend to have low allocation frequency.
Therefore, an inline would only be used for small objects for which
fragmentation is not such an important problem - page fragmentation does
not lock many pages. (Yea, I remember my logic! Just becasue large
objects have a low frequency, that doesn't mean small objects have a high
frequency, but you get the idea).

> - race conditions: for file system code, and possible process management,
> interference with interrupt handlers is not an issue. However, on SMP
> systems, dirty things can happen. Per-processor might help, but also
> might worsen the first problem: One processor always allocates from SLAB
> because the list is empty, the other one always puts the released entry
> into its list.

Per-engine (processor) caches do increase page-fragmentation. The
assumption is that if you have paid for an extra processor, you can afford
extra the extra memory to absorb the fragmentation :)
By allocation to a central pool, and moving a "magazine" (thanks to
whomever introduced me to that term!) to a per-engine pool. We can assume
an even distribution [of allocations and releases] over the engines.
Unfortunately, due to most interrupts being delieved to one [the
base] engine (perhaps this has changed recently?), this is not 100% true.

> The first problem could be solved by putting an upper limit on the number
> of cached objects (a small number, like 4 or 8 - fine tuning would be
> subject to profiling). Could the second problem be solved with bus locking?

Bus-locking is to be avoid if at all possible - it doesn't scale well.

With per-engine caches, the ownership of the engine (ie. we are running
on it) is the lock. This has problems with reaping, which can be
over-come by changing the scheduler by allowing binding a task [which is a
kernel task in this case] to an engine.

It is difficult to write lock free SMP code, and not always worth the
effort - over engineering. Many parts of the kernel are not currently
threaded, so having an allocator which avoids busy-waits could be
considered overkill. However, it is an interesting exercise.



Mark Hemment, Unix/C Software Engineer (Contractor)
"Success has many fathers, failure is a B**TARD!" - anon