Linux kernel has few SLAB allocator variants included: SLAB, SLUB and SLOB. Of these, SLOB is especially meant to be used on embedded devices – it tries to be more memory space efficient than other SLAB variants.
Yesterday, I had a detailed look at SLOB allocator for possible use in
compcache poject and found it
unacceptable for the purpose. I did it in response to feedback on
xvmalloc allocator
– as part of compcache patches posted of inclusion in mainline Linux
kernel:
http://lkml.org/lkml/2009/3/17/116
The requirement of this project is allocation of large no. of randomly sized objects in range [32, f * PAGE_SIZE] where fraction ‘f’ is typically 3⁄4 and PAGE_SIZE 4Kb.
To begin with, SLOB maintains just 3 freelists:
- for size < 256 - free_slob_small
- [256, 1024) - free_slob_medium
- [1024, PAGE_SIZE) - free_slob_large
It allocates from one of these lists depending on size requested.
Why SLOB is bad:
1) O(n) allocation:
To find block of given size, it _linearaly_ scans corresponding free list to
find a page with _total_ free space >= requested size.
This free space might not be contiguous. So it runs through free blocks
within each such candidate page until it finally finds some page with
free contiguous area >= requested size.
2) Fragmentation: When growing
SLOB cache, page is added to one of 3 freelists (depending on what size
we are currently allocating). After this, this page can never move to
any other list - even if its free space drops down to fall in next range
below or vice versa. This has two problems:
- Potentially large wastage due to “page internal fragmentation”: e.g.:
alloc(3096) is satisfied from a page in ‘large free list’. Now it has
1000b free (assuming 4k page) which will now never be used.
- It can trigger unnecessary cache grows: e.g.: even though we have such
unfilled pages in ‘large’ list, allocation in ‘small’ range can still
cause cache grow if ‘small free list’ is empty.
3) It only allocates from “low memory”. This is clearly not acceptable for compcache on 32-bit systems.