Simple Slab: A slab allocator with minimal meta information
Um, with all this discussion of keeping caches hot, people do remember that FIFO handling of free blocks *greatly* reduces fragmentation, right?
That's an observation from malloc implementations that support merging of any two adjacent blocks, but at least some of it should apply to slab pages that require multple adjacent free objects to be returned to the free-page pool.
With steady-state allocations and a LIFO free list, your "hot" end of the list is never free long enough to be combined, and the "cold" end, which shared pages with long-lived objects that have no hope of ever being freed, is rarely used and just wastes memory.
Managing the free list FIFO gives every chunk an equal opportunity to have its neighbor chunks freed.
The first idea that comes to mind for adapting this to a slab cache is to put the cache pages on a free list. Whenever a chunk is freed on a page, that page is moved to the "recent" end. Objects are allocated from the page at the "old" end until it is full, then the next-oldest page taken, and so on.
Completely free pages are either returned to the system, or put on a lowest-priority list that is only used when the other pages are all full.
Especially in a memory-constrained embedded environment, I'd think space-efficiency would be at least as important as time.
[email protected] writes:
[this time without typo in cc, sorry if you get it twice]
Quoted 7 lines
Um, with all this discussion of keeping caches hot, people do remember that FIFO handling of free blocks *greatly* reduces fragmentation, right?
That's an observation from malloc implementations that support merging of any two adjacent blocks, but at least some of it should apply to slab pages that require multple adjacent free objects to be returned to the free-page pool.
Interesting observation.
slab is a zone allocator and stores objects of the same type into zones. The theory behind that is that normally that objects of the same type have similar livetimes and that should in theory avoid
many fragmentation problems.
However some caches like dcache/inode cache don't seem to follow that, and kmalloc which mixes all kinds of objects into the same caches especially doesn't.
Quoted 2 lines
Especially in a memory-constrained embedded environment, I'd think space-efficiency would be at least as important as time.
For memory-constrained environments there is already the optional specialized "slob" allocator.
That said even big systems have problems with fragmentation.
It is good that the basic assumptions behind slabs are being revisited now. I suspect some of them might be obsolete.
-Andi