Re: [patch 4/9] slab: cache_estimate cleanup

[Steven Rostedt <rostedt@goodmis.org>]

On Tue, 2006-01-03 at 20:47 -0500, Steven Rostedt wrote:

> > 
> > I've also been looking at this and I've realized that we can even remove
> > the "while" and make it into an "if".  It works just as well. I created
> > the attached test program to see if there would be any difference
> > testing all sizes from 8 to PAGE_SIZE >> 1 (where PAGE_SIZE = 1<<12),
> > and all alignments of 4 to size, and I tried this with two orders of
> > pages.  The "if" should make the assembly a little better.
> > 
> >
[...]
> +static size_t slab_mgmt_size(size_t nr_objs, size_t align)
>  {

[ delete deletion ]

> +	return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);
> +}
> +
> +/* Calculate the number of objects and left-over bytes for a given
> +   object size. */
> +static void cache_estimate(unsigned long gfporder, size_t obj_size,
> +			   size_t align, int flags, size_t *left_over,
> +			   unsigned int *num)
> +{
> +

[...]

> +		/* Ignore padding for the initial guess.  The padding
> +		 * is at most @align-1 bytes, and @size is at least
> +		 * @align. In the worst case, this result will be one
> +		 * greater than the number of objects that fit into
> +		 * the memory allocation when taking the padding into
> +		 * account.
> +		 */
> +		nr_objs = (slab_size - sizeof(struct slab)) /
> +			  (obj_size + sizeof(kmem_bufctl_t));
> +
> +		/*
> +		 * This calculated number will be either the right
> +		 * amount, or one greater than what we want.
> +		 */
> +		if (slab_mgmt_size(nr_objs, align) + nr_objs*obj_size
> +		       > slab_size)
> +			nr_objs--;

No while is needed!  slab_mgmt_size(nr_objs, align) will end up being:

(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t)+align-1)&~(align-1)

lets say:
  S = sizeof(struct slab)
  K = sizeof(kmem_bufctl_t)
  n = nr_objs
  z = slab_size
  o = objsize
  a = align

	nr_objs = (slab_size - sizeof(struct slab)) /
		(size + sizeof(kmem_bufctl_t));

will be  n = (z - S) / (o + K)

looking at the if:

	if (slab_mgmt_size(nr_objs, align) + nr_objs*size
	       > slab_size)

and slab_mgmt_size:

   static size_t slab_mgmt_size(size_t nr_objs, size_t align)
   {
	return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);
   }

and ALIGN:

   #define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))

slab_mgmt_size is the same as:

    ALIGN(S + nK, a)

so this will not be greater than:

S + nK + a - 1


add this to the if:

if (S + nK + a-1 + no > z)

proof by contradiction: can the left side be greater than z + o?

S + nK + a-1 + no = z+o+1 ?

S + (o+K)n + a-1 = z+o+1

n = (z - S) / (o + K) so:

S + (o+K)(z-S)/(o+K) + a-1 = z+o+1

S + (z-S) + a-1 = z+o+1

removing the z and S

a-1 = o+1

We know that a can be at most o so:

o-1 = o+1

and thus we get:

-1 = 1

So I believe this is the proof by contradiction.  Might want to check
this, since I just woke up ;)

-- Steve