Re: [PATCH RT 00/02] SLOB optimizations

[Matt Mackall <mpm@selenic.com>]

On Tue, Dec 20, 2005 at 10:44:20AM -0500, Steven Rostedt wrote:
> (Andrew, I'm CC'ing you and Matt to see if you would like this in -mm)
> 
> OK Ingo, here it is.
> 
> The old SLOB did the old K&R memory allocations.
> 
> It had a global link list "slobfree".  When it needed memory it would
> search this list linearly to find the first spot that fit and then
> return it.  It was broken up into SLOB_UNITS which was the number of
> bytes to hold slob_t.
> 
> Since the sizes of the allocations would greatly fluctuate, the chances
> for fragmentation was very high.  This would also cause the looking for
> free locations to increase, since the number of free blocks would also
> increase due to the fragmentation.

On the target systems for the original SLOB design, we have less than
16MB of memory, so the linked list walking is pretty well bounded.
 
> It also had one global spinlock for ALL allocations.  This would
> obviously kill SMP performance.

And again, the locking primarily exists for PREEMPT and small dual-core.
So I'm still a bit amused that you guys are using it for -RT.

> When any block was freed via kfree, it would first search all the big
> blocks to see if it was a large allocation, and if not, then it would
> search the slobfree list to find where it goes.  Both taking two global
> spinlocks!

I don't think this is correct, or else indicates a bug. We should only
scan the big block list when the freed block was page-aligned.

> First things first, the first patch was to get rid of the bigblock list.
> I'm simple used the method of SLAB to use the lru list field of the
> corresponding page to store the pointer to the bigblock descriptor which
> has the information to free it. This got rid of the bigblock link list
> and global spinlock.

This I like a lot. I'd like to see a size/performance measurement of
this by itself. I suspect it's an unambiguous win in both categories.
 
> The next patch was the big improvement, with the largest changes.  I
> took advantage of how the kmem_cache usage that SLAB also takes
> advantage of.  I created a memory pool like the global one, but for
> every cache with a size less then PAGE_SIZE >> 1.

Hmm. By every size, I assume you mean powers of two. Which negates
some of the fine-grained allocation savings that current SLOB provides.

[...]
> So I have improved the speed of SLOB to almost that of SLAB!

Nice.

For what it's worth, I think we really ought to consider a generalized
allocator approach like Sun's VMEM, with various removable pieces.

Currently we've got something like this:

 get_free_pages     boot_mem         idr    resource_*   vmalloc ...
        |
      slab
        |
  per_cpu/node
        |
  kmem_cache_alloc
        |
     kmalloc

We could take it in a direction like this:

 generic range allocator          (completely agnostic)
          |
  optional size buckets           (reduced fragmentation, O(1))
          |    
    optional slab                 (cache-friendly, pre-initialized)
          |
 optional per cpu/node caches     (cache-hot and lockless)
          |
 kmalloc / kmem_cache_alloc / boot_mem / idr / resource_* / vmalloc / ...

(You read that right, the top level allocator can replace all the
different allocators that hand back integers or non-overlapping ranges.)

Each user of, say, kmem_create() could then pass in flags to specify
which caching layers ought to be bypassed. IDR, for example, would
probably disable all the layers and specify a first-fit policy.

And then depending on our global size and performance requirements, we
could globally disable some layers like SLAB, buckets, or per_cpu
caches. With all the optional layers disabled, we'd end up with
something much like SLOB (but underneath get_free_page!).

-- 
Mathematics is the supreme nostalgia of our time.