(I'm using the same API as described in the Bonwick paper for a coherent frame of reference.)

You can resolve the fixed-size issue by creating multiple object caches in a power-of-two size schema, and then populating cache_table[] below. Then wrap the slab allocator with a rudimentary layer. Round your allocation to the closest matching bucket by indexing into it based on the size of the object you're requesting.

So something like:

#define MAXOBJSIZE 8192 /* Maximum size you want to create an object cache for */
#define ALIGN_SHIFT 4 /* 2^4 = 16 = minimum guaranteed alignment */

void *slabmem_alloc(int size, int flags)
{
void *obj;
int idx = (int)(size - 1) >> ALIGN_SHIFT;

if ((unsigned int)idx < MAXOBJSIZE >> ALIGN_SHIFT) {
kmem_cache_t *cp = cache_table[idx];
obj = kmem_cache_alloc(cp, flags);
return (obj);
} else {
/* Fall through to non-slab allocation here */
}
}

Basically you treat each slab cache as a backing store bucket in a power-of-two (or similar) allocator. It gives you O(1) allocations and frees. The only thing you have to watch for is internal fragmentation, which is not an issue if you pick your cache_table entries properly. This is also greatly mitigated by the slab allocator's slab management strategy, and the fact there are no O(n) coalescings performed as in most other allocators (e.g. Doug Lea's malloc, which while pretty cool, is not O(1) for this reason.)

Also, frees need the size of the object to be passed in as a parameter.

Make sense?

Whoa, yes... this all makes a lot of sense.

I still don't understand why coalescings needs to be O(n). If you keep a mapping of free regions' start and end points, whenever you free a new region, you could check to see if the freed region has free regions on either side of it and combine them. With something like Judy (judy.sf.net), that mapping is pretty cheap, I'd think. Definitely better than O(n).

In any case, powers-of-two slab allocation seems like the best bet here.

Thanks!

Coalescing can be made O(1) very easily. And slab allocators don't have to be power-of-two. In fact, they're usually not used for that. Slab allocators are used when you have a large number of objects that are _not_ power-of-two sized. The slab allocator is substantially better at reducing fragmentation and minimizing memory usage.