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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
