OSDev.org

I have a ready buddy allocator and I would like to implement SLAB allocator on top of it for kernel needs.
However, I can't find a simple enough yet practical explanation of how I can implement this in my situation.
All the articles about implementing the SLAB allocator boil down to articles about how it works in Linux. Linux articles tend to be overly complicated, since Linux is more complicated than my hobby OS.

I want to find something (an article) that could help me, in my hobby OS, to implement the SLAB allocator. Does anyone know a source of such information? (I have already read the original SunOS article).
I want an article that deals with hobby OSdev, not Linux.

https://en.wikipedia.org/wiki/Slab_allocation

My hobby OS slab allocator is barely documented in the following page. But most of this page relates to how the garbage collection I implement on top of the slab allocator works:
- http://thewrongchristian.org.uk:8082/wiki?name=Slab

Code:
- http://thewrongchristian.org.uk:8082/ar ... b623fa8555

But my slab allocator is limited to single page slabs, and so is not very general purpose and useful only for small structures, and not for anything approaching page sized or larger.

But slab allocators are actually really simple.

The slab is the aggregate object out of which you allocate individual objects. In my OS, that aggregate object is page sized, in the bonwick paper and in Linux, the slab can be multiple pages.

Your slab has some meta-data. In my slab, I put this at the front of the slab. Then the remainder of the slab is split into equal sized allocation units (I call these slots in my allocator). The idea being that each slab allocates objects of the same type, hence the allocation sizes are all the same.

Your slab meta-data describes what the contained objects are (in my slab allocator, there is a pointer to a slab type, which gives information like the object size, and garbage collection marking/finalization functions, and also a list of slabs for this slab type.)

The slab meta-data also needs to track the free objects in the slab. In my slab allocator, the free objects use a linked list, and the slab meta-data points to the head of that linked list. Allocation from a slab is just then a case of removing the first free object from the list, and pointing to the next free object in the slab meta-data.

So, to allocate an object of type, say, a vnode (function names from my OS code).

- Using the vnode slab type, call slab_alloc().
- slab_alloc will use the type information to look for a slab of this type with some free space (slab_type_t::first in my code.)
- Having found a slab, remove the first free object from the list (slab_t::free in my code), and point the slab free pointer to the next free object (if any).
- Return the pointer for the now allocated object. My objects are preceded by a header (slab_slot_t in my code), so we advance the pointer beyond the header and return that.

My code is perhaps not the best example for you though, complicated as it is by the garbage collection code it incorporates. But if you can unpick the garbage collection code from slab_alloc, the actual lines of code to do the allocation are of the order of a 10-20 lines of code, all O(1), which is why slab allocators are so attractive.

Freeing a slab allocated object is also easy. Given the object pointer, you can find the slab from which it came easily if your slabs are paged sized. Simply round the pointer down to the slab alignment (1 page in my example), then that gives you the location of your header. You can use the unrounded portion of the freed pointer to find the actual object within the slab (it's just an array of uniformly sized objects), do a quick check that the offset is a valid object pointer, then put the newly freed object onto the slab meta-data free list.

I basically understand how the allocator works, but the problem arises with metadata storage. Bonwick writes that metadata from caches with small objects (PAGE_SIZE / 8) can be stored directly in the slab, everything is clear and simple here. However, for large objects, the data has to be stored outside the slab, then there is a problem with how to get this data having only the address of the object.
That is, at the moment when free() is called we get only the address, from this address we have to find the address of the slab's metadata, which is stored anywhere else. Have you encountered this problem? Bonwick suggests using hash tables, but I have little understanding of how they work (and how can I use them to solve this problem), so maybe there is some other way.

For large objects, in the bonwick paper, the kmem_slab and kmem_bufctl aren't stored in a page like structure, but are instead stored in other slabs (they're themselves allocated from a small object slab.)

So, in Solaris 2.4, given a pointer, you look up that pointer in the hash table for this object type, which points at the kmem_bufctl for this pointer, and that points back to the kmem_slab, which itself will reference the object type. So it should be all self consistent.

So, in the bonwick paper, the free() call will need the object type as well as the pointer being freed as arguments, then it will:

- Look up the pointer in the hash table for the object type.
- That hash lookup will produce a kmem_bufctl. That kmem_bufctl points to the kmem_slab, is added to the cache free list for this object type.

You can't implement free() in the bonwick paper without knowing the object type, as the hash table described is per object type.

And this makes sense in the context of Solaris or any other OS. We're not dealing with a general purpose allocator here. This is an object allocator, and the VFS code knows when it is freeing a vnode, for example, so it can pass the appropriate object type to free.

The Illumos kmem API is documented here, this is basically what the paper is describing:

https://www.illumos.org/man/9F/kmem_cache_create

Notice how kmem_cache_alloc/kmem_cache_free take a kmem_cache_t reference argument, this describes the object type, and the individual kmem_slab will be linked off this cache header.



Hash tables should be Required_Knowledge for implementing an OS.