Wednesday, March 18, 2009

SLOB memory allocator

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:

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.

No comments:

Post a Comment