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

[Balbir Singh]

> 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

Your analysis is very interesting and seems correct. My analysis is
similar, but a bit
different

Best case is S+nK is aligned
Worst case is S+nK is off by +1 byte from an alignment boundary

Taking the worst case, we find a-1 bytes of space eaten up by the
alignment operation.
We need to see if the a-1 bytes that we lost, could have accommodated
another object of
size o and a bufctl of size K. If that is true we need to reduce n.

The equation becomes

If o+K < a-1, reduce n

If a is atmost o, then it leads to (from your analysis assumption)

if K < -1 reduce n, K is certainly positive, hence do not reduce n.

Balbir
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/