Re: Patch: optimize kmem_alloc for frequent mid-sized allocations

[Andrew Doran <ad%netbsd.org@localhost>]

On Sun, Jan 11, 2009 at 04:51:03PM +0000, David Laight wrote:

> On Sun, Jan 11, 2009 at 01:40:48PM +0000, Andrew Doran wrote:
> > 
> > It is a problem for "mid-sized" allocations, up to PAGE_SIZE because these
> > occur frequently. The below patch introduces an additional level of caching,
> > from the maximum size provided by the quantum cache up to PAGE_SIZE. It also
> > adds debug code to check that allocated size == freed size.
> 
> So my understanding of the old version is that:
> 1) the minumum allocation size is 128

It's acutally ALIGNBYTES+1. "vmstat -C | grep kmem" will give you the list
of quantum cache sizes.

> 2) allocations above PAGE_SIZE directly map pages

vmem imports space from kernel_map and chops it up. It doesn't directly know
about PAGE_SIZE, although the uvm_km_alloc() code from which space is
imported _does_. Large allocations from vmem can span page boundaries if
there is recycling and chopping up of already imported sections.

> 3) allocations are done from some allocator with a bit-map free list??
>    dynamically freeing pages when no longer used

I'm can't remember, see subr_vmem.c. Space _is_ freed back to kernel_map
when a given run is no longer in use.

> With the modified version:
> 1) the minumum allocation size is 128

ALIGNBYTES+1

> 2) allocations above PAGE_SIZE directly map pages

See above.

> 3) allocations are done from free lists which contain power-of-2
>    sized items generated by splitting up pages.
>    The correct list being found by indexing with the size.

More closely to the truth:

- tiny allocations (which the kernel does a lot of) are satisfied by
  the quantum cache layer in subr_vmem.c.

- with the patch, mid-sized allocations are satisfied by an additional cache
  layer in subr_kmem.c. It's an addtional layer of pool_caches, covering
  (ALIGNBYTES+1) * 32 * 2 to PAGE_SIZE.

- with the patch, >PAGE_SIZE allocations are handled in the slow-path by
  subr_vmem.c, which chops up space imported from kernel_map.

> Investigate per-cpu free lists - or does pool_cache_xxxx(0 use them now.
> Possibly allow code to pre-lookup the free list for fixed size items.

Yes, there are already per-cpu free lists in pool_cache. vmem uses them for
the quantum cache, which is why kmem_alloc() rocks for small allocations
on MP systems.

Thanks,
Andrew