slab: cache_estimate cleanup
PATCH 4/9 slab: cache_estimate cleanup
From: Steven Rostedt <[email protected]>
This patch cleans up cache_estimate in mm/slab.c and improves the algorithm by taking an initial guess before executing the while loop. The optimization was originally made by Balbir Singh with further improvements from Steven Rostedt. Manfred Spraul provider further modifications: no loop at all for the off-slab case and explain the background.
---
mm/slab.c | 89 ++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 64 insertions(+), 25 deletions(-)
mm/slab.c +64 -25
@@ -700,32 +700,71 @@ kmem_cache_t *kmem_find_general_cachep(s }EXPORT_SYMBOL (kmem_find_general_cachep); -/* Cal the num objs, wastage, and bytes left over for a given slab size. */ -static void cache_estimate (unsigned long gfporder,size_t size,size_t align, -int flags,size_t *left_over,unsigned int *num) +static size_t slab_mgmt_size (size_t nr_objs,size_t align) { -int i; -size_t wastage =PAGE_SIZE <<gfporder; -size_t extra =0 ; -size_t base =0 ; - -if (!(flags &CFLGS_OFF_SLAB )) { - base =sizeof (struct slab ); - extra =sizeof (kmem_bufctl_t); - } - i =0 ; -while (i*size +ALIGN (base+i*extra, align) <= wastage) - i++; -if (i >0 ) - i--; - -if (i >SLAB_LIMIT ) - i =SLAB_LIMIT ; - - *num = i; - wastage -= i*size; - wastage -=ALIGN (base+i*extra, align); - *left_over = wastage; +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) +{ +int nr_objs; +size_t mgmt_size; +size_t slab_size =PAGE_SIZE << gfporder; + +/* +* The slab management structure can be either off the slab or +* on it. For the latter case, the memory allocated for a +* slab is used for: +* +* - The struct slab +* - One kmem_bufctl_t for each object +* - Padding, to achieve alignment of @align +* - @obj_size bytes for each object +*/ +if (flags &CFLGS_OFF_SLAB ) { + mgmt_size =0 ; + nr_objs = slab_size / obj_size; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ; + }else { +/* 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)); + +/* +* Now take the padding into account and increase the +* number of objects/slab until it doesn't fit +* anymore. +*/ +while (slab_mgmt_size (nr_objs, align) + nr_objs*obj_size + <= slab_size) + nr_objs++; + +/* +* Reduce it by one which the maximum number of objects that +* fit in the slab. +*/ +if (nr_objs >0 ) + nr_objs--; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ; + + mgmt_size =slab_mgmt_size (nr_objs, align); + } + *num = nr_objs; + *left_over = slab_size - nr_objs*obj_size - mgmt_size; }#define slab_error (cachep, msg) __slab_error(__FUNCTION__, cachep, msg)
--
Quoted 7 lines · Pekka Enberg
From: Steven Rostedt <[email protected]>
This patch cleans up
cache_estimateinmm/slab.cand improves the algorithm by taking an initial guess before executing the while loop. The optimization was originally made by Balbir Singh with further improvements from Steven Rostedt. Manfred Spraul provider further modifications: no loop at all for the off-slab case and explain the background.
The no loop at all probably needs a comment, since I don't see one. [ see below ]
Quoted 12 lines
Signed-off-by Manfred Spraul <[email protected]>Signed-off-by Pekka Enberg <[email protected]>---
mm/slab.c | 89 ++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 64 insertions(+), 25 deletions(-)Index:
2.6/mm/slab.c
===================================================================mm/slab.c +0
-0
[snip]
Quoted 10 lines
mm/slab.c +10
-0+/* 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) +{ +int nr_objs; +size_t mgmt_size; +size_t slab_size =PAGE_SIZE << gfporder; +
mm/slab.c kmem_cache_t *kmem_find_general_cachep(s · line 727
Quoted 10 lines
mm/slab.c +10
-0+/* +* The slab management structure can be either off the slab or +* on it. For the latter case, the memory allocated for a +* slab is used for: +* +* - The struct slab +* - One kmem_bufctl_t for each object +* - Padding, to achieve alignment of @align +* - @obj_size bytes for each object +*/
Probably want a comment here that says something to the following:
If the slab management structure is off the slab, then the alignment will already be calculated into the size. Because the slabs are all pages aligned, the objects will be at the correct alignment when allocated.
[more below]
mm/slab.c kmem_cache_t *kmem_find_general_cachep(s · line 736
Quoted 9 lines
mm/slab.c +9
-0+if (flags &CFLGS_OFF_SLAB ) { + mgmt_size =0 ; + nr_objs = slab_size / obj_size; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ; + }else { +/* Ignore padding for the initial guess. The padding +* is at most @align-1 bytes, and @size is at least
should @size be @obj_size
Quoted 6 lines
mm/slab.c +6
-0+* @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)) /
mm/slab.c kmem_cache_t *kmem_find_general_cachep(s · line 752
Quoted 10 lines
mm/slab.c +10
-0+ (obj_size +sizeof (kmem_bufctl_t)); + +/* +* Now take the padding into account and increase the +* number of objects/slab until it doesn't fit +* anymore. +*/ +while (slab_mgmt_size (nr_objs, align) + nr_objs*obj_size + <= slab_size) + nr_objs++;
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.
-- Steve
Quoted 11 lines
mm/slab.c +10
-0+ +/* +* Reduce it by one which the maximum number of objects that +* fit in the slab. +*/ +if (nr_objs >0 ) + nr_objs--; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ;
mm/slab.c kmem_cache_t *kmem_find_general_cachep(s
Quoted 10 lines
mm/slab.c +5
-1+ + mgmt_size =slab_mgmt_size (nr_objs, align); + } + *num = nr_objs; + *left_over = slab_size - nr_objs*obj_size - mgmt_size; }#define slab_error (cachep, msg) __slab_error(__FUNCTION__, cachep, msg) --
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PAGE_SIZE (1<<12)
struct slab {
int x[7];
};typedef long kmem_bufctl_t;
#define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
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);
}int estimate (int size, int align, int *leftover, int *hold1, int * hold2, int *num, int order)
{
int nr_objs;
int slab_size = PAGE_SIZE << order;
int nr1;
int nr2;
int mgmt_size;
int nr_while;
int nr_if;
int ret = 0;
nr_objs = (slab_size - sizeof(struct slab)) /
(size + sizeof(kmem_bufctl_t));
nr1 = nr_objs;
/*
* Now take the padding into account and increase the
* number of objects/slab until it doesn't fit
* anymore.
*/
nr_if = nr_objs;
if (slab_mgmt_size(nr_objs, align) + nr_objs*size
<= slab_size)
nr_if++;
if (slab_mgmt_size(nr_objs, align) + nr_objs*size
<= slab_size)
nr_objs++;
if (nr_if != nr_objs)
ret = 1;
nr2 = nr_objs;
/*
* Reduce it by one which the maximum number of objects that
* fit in the slab.
*/
if (nr_objs > 0)
nr_objs--;
mgmt_size = slab_mgmt_size(nr_objs, align);
*num = nr_objs;
*leftover = slab_size - nr_objs*size - mgmt_size;
*hold1 = nr1;
*hold2 = nr2;
return ret;
}int main (int argc, char **argv)
{
int i;
int x;
int leftover;
int hold1;
int hold2;
int num;
int order;
for (order=0; order <= 1; order++) {
for (i=8; i < (PAGE_SIZE >> 1); i++) {
for (x=4; x < i; x++) {
if (estimate(i, x, &leftover, &hold1, &hold2, &num, order))
printf("%8d%8d%8d%8d%8d%8d%8d%8d\n", i, x, leftover,
hold1, hold2, num, hold1-num, hold2-num);
}
}
}
return 0;
}Quoted 38 lines · Steven Rostedt
Review
Quoted 9 lines
(quoted diff) +9
-0+ if (flags & CFLGS_OFF_SLAB) { + mgmt_size = 0; + nr_objs = slab_size / obj_size; + + if (nr_objs > SLAB_LIMIT) + nr_objs = SLAB_LIMIT; + } else { + /* Ignore padding for the initial guess. The padding + * is at most @align-1 bytes, and @size is at leastshould @size be @obj_size
Quoted 6 lines
(quoted diff) +6
-0+ * @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)) /Review
Quoted 10 lines
(quoted diff) +10
-0+ (obj_size + sizeof(kmem_bufctl_t)); + + /* + * Now take the padding into account and increase the + * number of objects/slab until it doesn't fit + * anymore. + */ + while (slab_mgmt_size(nr_objs, align) + nr_objs*obj_size + <= slab_size) + nr_objs++;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 (wherePAGE_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.-- Steve
Quoted 7 lines
Review
Quoted 7 lines
(quoted diff) +7
-0+ + /* + * Reduce it by one which the maximum number of objects that + * fit in the slab. + */ + if (nr_objs > 0) + nr_objs--;
Looking even further into this, we can get rid of the while and this if, and replace it with one if.
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--; if (nr_objs > SLAB_LIMIT) nr_objs = SLAB_LIMIT;
Note the change from <= to >.
Here's a new patch for that.
-- Steve
From: Steven Rostedt <[email protected]>
This patch cleans up cache_estimate in mm/slab.c and improves the algorithm by taking an initial guess before executing the while loop. The optimization was originally made by Balbir Singh with further improvements from Steven Rostedt. Manfred Spraul provider further modifications: no loop at all for the off-slab case and explain the background.
mm/slab.c +56 -25
@@ -700,32 +700,63 @@ }EXPORT_SYMBOL (kmem_find_general_cachep); -/* Cal the num objs, wastage, and bytes left over for a given slab size. */ -static void cache_estimate (unsigned long gfporder,size_t size,size_t align, -int flags,size_t *left_over,unsigned int *num) +static size_t slab_mgmt_size (size_t nr_objs,size_t align) { -int i; -size_t wastage =PAGE_SIZE <<gfporder; -size_t extra =0 ; -size_t base =0 ; - -if (!(flags &CFLGS_OFF_SLAB )) { - base =sizeof (struct slab ); - extra =sizeof (kmem_bufctl_t); - } - i =0 ; -while (i*size +ALIGN (base+i*extra, align) <= wastage) - i++; -if (i >0 ) - i--; - -if (i >SLAB_LIMIT ) - i =SLAB_LIMIT ; - - *num = i; - wastage -= i*size; - wastage -=ALIGN (base+i*extra, align); - *left_over = wastage; +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) +{ +int nr_objs; +size_t mgmt_size; +size_t slab_size =PAGE_SIZE << gfporder; + +/* +* The slab management structure can be either off the slab or +* on it. For the latter case, the memory allocated for a +* slab is used for: +* +* - The struct slab +* - One kmem_bufctl_t for each object +* - Padding, to achieve alignment of @align +* - @obj_size bytes for each object +*/ +if (flags &CFLGS_OFF_SLAB ) { + mgmt_size =0 ; + nr_objs = slab_size / obj_size; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ; + }else { +/* 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--; + +if (nr_objs >SLAB_LIMIT ) + nr_objs =SLAB_LIMIT ; + + mgmt_size =slab_mgmt_size (nr_objs, align); + } + *num = nr_objs; + *left_over = slab_size - nr_objs*obj_size - mgmt_size; }#define slab_error (cachep, msg) __slab_error(__FUNCTION__, cachep, msg)
Balbir Singh
Acked-byQuoted 8 lines
This patch cleans up
cache_estimateinmm/slab.cand improves the algorithm by taking an initial guess before executing the while loop. The optimization was originally made by Balbir Singh with further improvements from Steven Rostedt. Manfred Spraul provider further modifications: no loop at all for the off-slab case and explain the background.Signed-off-by Manfred Spraul <[email protected]>Signed-off-by Pekka Enberg <[email protected]>
I had prepared this patch about five years ago and completely forgot about it.
Quoted 9 lines · Steven Rostedt
Quoted 9 lines
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 (wherePAGE_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.
[...]
Quoted 2 lines
+static
size_tslab_mgmt_size(size_t nr_objs, size_t align)
{
[ delete deletion ]
Quoted 10 lines
mm/slab.c +10
-0+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) +{ +
[...]
Quoted 7 lines
mm/slab.c +7
-0+/* 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. +*/
mm/slab.c line 751
Quoted 10 lines
mm/slab.c +10
-0+ 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
Quoted 66 lines
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_sizeis 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
Quoted 8 lines
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