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:
-
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.
-
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.
- It only allocates from “low memory”. This is clearly not acceptable for compcache on 32-bit systems.