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

Bill Hawes (
Wed, 06 Aug 1997 18:13:22 -0400

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.

Yes, I have in mind a couple of very simple schemes that seem to meet
David's criteria. Basically each size object has a per-processor list
(or array), but there's only one slab. I assume there's a processor
index 0 to N-1 that indexes the list or array to be used, so there's no
processor contention. The call to fast_alloc(OBJ_TYPE) combines the
object size with the processor index, and picks an object off the list
in three instructions. Returning objects go back onto the list (or
array) in the same fashion.

The maintenance of the lists is very easy too -- you have a maintenance
thread that can run on any processor. It first grooms its own slot
(stocking it with a certain number of objects, which could be
dynamically tuned). To care for the other porcessors, it atomically
switches each other processor's index to its own, cares for that list,
then restores the original index and moves on the next processor.

So except when the list empties out, each processor sees no contention
-- the total time per alloc or free is just an indexing. The list size
can be dynamically varied to achieve whatever performance/memory use
tradeoffs. And the fragmentation can be controlled by a smart
maintenance thread that decides which objects to return to the SLAB pool
and which to keep on the hot lists.

Very simple, but should be very fast.