Messages in this thread | | | Subject | Re: [PATCH 06/30] mm: kmem_alloc_estimate() | From | Peter Zijlstra <> | Date | Wed, 30 Jul 2008 15:31:02 +0200 |
| |
On Wed, 2008-07-30 at 15:21 +0300, Pekka Enberg wrote: > Hi Peter, > > On Thu, 2008-07-24 at 16:00 +0200, Peter Zijlstra wrote:
> Just a nitpick, but: > > > +unsigned kmalloc_estimate_fixed(size_t, gfp_t, int); > > kmalloc_estimate_objs()? > > > +unsigned kmalloc_estimate_variable(gfp_t, size_t); > > kmalloc_estimate_bytes()?
Sounds good, I'll do some sed magic on the patch-set to make it happen.
> > > > /* > > * Allocator specific definitions. These are mainly used to establish optimized > > Index: linux-2.6/mm/slub.c > > =================================================================== > > --- linux-2.6.orig/mm/slub.c > > +++ linux-2.6/mm/slub.c > > @@ -2412,6 +2412,42 @@ const char *kmem_cache_name(struct kmem_ > > } > > EXPORT_SYMBOL(kmem_cache_name); > > > > +/* > > + * Calculate the upper bound of pages required to sequentially allocate > > + * @objects objects from @cachep. > > + * > > + * We should use s->min_objects because those are the least efficient. > > + */ > > +unsigned kmem_alloc_estimate(struct kmem_cache *s, gfp_t flags, int objects) > > +{ > > + unsigned long pages; > > + struct kmem_cache_order_objects x; > > + > > + if (WARN_ON(!s) || WARN_ON(!oo_objects(s->min))) > > + return 0; > > + > > + x = s->min; > > + pages = DIV_ROUND_UP(objects, oo_objects(x)) << oo_order(x); > > + > > + /* > > + * Account the possible additional overhead if the slab holds more that > > + * one object. Use s->max_objects because that's the worst case. > > + */ > > + x = s->oo; > > + if (oo_objects(x) > 1) { > > Hmm, I'm not sure why slab with just one object is treated separately > here. Surely you have per-CPU slabs then as well?
The thought was that if the slab only contains 1 obj, then the per-cpu slabs are always full (or empty but already there), so you don't loose memory to other cpu's having half-filled slabs.
Say you want to reserve memory for 10 object.
In the 1 object per slab case, you will always allocate a slab, no matter what cpu you do the allocation on.
With say, 16 objects per slab and allocations spread across 2 cpus, you have to allow for per-cpu slabs to be half-filled.
> > + /* > > + * Account the possible additional overhead if per cpu slabs > > + * are currently empty and have to be allocated. This is very > > + * unlikely but a possible scenario immediately after > > + * kmem_cache_shrink. > > + */ > > + pages += num_online_cpus() << oo_order(x); > > Isn't this problematic with CPU hotplug? Shouldn't we use > num_possible_cpus() here?
ACK, thanks!
> > +/* > > + * Calculate the upper bound of pages requires to sequentially allocate @bytes > > + * from kmalloc in an unspecified number of allocations of nonuniform size. > > + */ > > +unsigned kmalloc_estimate_variable(gfp_t flags, size_t bytes) > > +{ > > + int i; > > + unsigned long pages; > > + > > + /* > > + * multiply by two, in order to account the worst case slack space > > + * due to the power-of-two allocation sizes. > > + */ > > + pages = DIV_ROUND_UP(2 * bytes, PAGE_SIZE); > > For bytes > PAGE_SIZE this doesn't look right (for SLUB). We do page > allocator pass-through which means that we'll be grabbing high order > pages which can be bigger than what 'pages' is here.
Hehe - you actually made me think here.
Satisfying allocations from a bucket distribution with power-of-two (which page alloc order satisfies) has a worst case slack space of:
S(x) = 2^n - (2^(n-1)) - 1, n = ceil(log2(x))
This can be seen for the cases where x = 2^i + 1.
If we approximate S(x) by 2^(n-1) and compute the slack ratio for any given x:
R(x) ~ 2^n / 2^(n-1) = 2
We'll see that for any amount of x, we can only use half that due to slack space.
Therefore, by multiplying the demand @bytes by 2 we'll always have enough to cover the worst case slack considering the power-of-two allocation buckets.
In example, if @bytes asks for 4 pages + 1 byte = 16385 bytes (assuming 4k pages), then the above will request 8 pages + 2 bytes, rounded up to pages, is 9 pages. Which is enough to satisfy the order 3 allocation needed for the 8 contiguous pages to store the requested 16385 bytes.
> > Index: linux-2.6/mm/slab.c > > =================================================================== > > --- linux-2.6.orig/mm/slab.c > > +++ linux-2.6/mm/slab.c > > @@ -3854,6 +3854,81 @@ const char *kmem_cache_name(struct kmem_ > > EXPORT_SYMBOL_GPL(kmem_cache_name); > > > > /* > > + * Calculate the upper bound of pages required to sequentially allocate > > + * @objects objects from @cachep. > > + */ > > +unsigned kmem_alloc_estimate(struct kmem_cache *cachep, > > + gfp_t flags, int objects) > > +{ > > + /* > > + * (1) memory for objects, > > + */ > > + unsigned nr_slabs = DIV_ROUND_UP(objects, cachep->num); > > + unsigned nr_pages = nr_slabs << cachep->gfporder; > > + > > + /* > > + * (2) memory for each per-cpu queue (nr_cpu_ids), > > + * (3) memory for each per-node alien queues (nr_cpu_ids), and > > + * (4) some amount of memory for the slab management structures > > + * > > + * XXX: truely account these > > Heh, yes please. Or add a comment why it doesn't matter.
Since you were the one I cribbed that comment from some (long) time ago, can you advise on how well the below approximation is to an upper bound on the above factors - assuming SLAB will live long enough to make it worth the effort?
> > + */ > > + nr_pages += 1 + ilog2(nr_pages); > > + > > + return nr_pages; > > +}
| |