Scalability requirements for sysv ipc - v2
Subsystems (2)
cover Scalability requirements for sysv ipc - v2
After scalability problems had been detected when using the sysV ipcs, I have proposed to use an RCU based implementation of the IDR api instead (see thread http://lkml.org/lkml/2008/4/11/212).
Resending the patch series after
. integrating Paul's remarks
. fixing a bug I had introduced
. porting it to 2.6.25-mm1.
Reviewers are still welcome!
Patch 1 can be taken alone: it fixes a problem in the existing IDR API.
Patches should be applied on linux-2.6.25-mm1, in the following order:
[ PATCH 01/10 ] : idr_minor_fix.patch [ PATCH 02/10 ] : ridr_structure.patch [ PATCH 03/10 ] : ridr_pre_get.patch [ PATCH 04/10 ] : ridr_init.patch
[ PATCH 05/10 ] : ridr_get_new_above.patch [ PATCH 06/10 ] : ridr_get_new.patch [ PATCH 07/10 ] : ridr_find.patch
[ PATCH 08/10 ] : ridr_remove.patch
[ PATCH 09/10 ] : ipc_use_ridr.patch [ PATCH 10/10 ] : remove_ipc_lock_down.patch
Regards,
Nadia
--
PATCH 1/10 Fix idr_remove()
[PATCH 01/10]
This patch fixes idr_remove(): the return inside the loop makes us free only a single layer.
--- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/idr.c +1 -1
@@ -385,8 +385,8 @@ void idr_remove(struct idr *idp, int id)while (idp->id_free_cnt >=IDR_FREE_MAX ) { p =alloc_layer (idp);kmem_cache_free (idr_layer_cache, p); -return ; } +return ; }EXPORT_SYMBOL (idr_remove);
--
Andrew Morton
maintainerRe: [PATCH 01/10] Fix idr_remove()
Quoted 16 lines · On Tue, 29 Apr 2008 16:33:05 +0200 [email protected] wrote:
[PATCH 01/10]
This patch fixes
idr_remove(): the return inside the loop makes us free only a single layer.Signed-off-by Nadia Derbey <[email protected]>--- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)Index:
linux-2.6.25-mm1/lib/idr.c
===================================================================
lib/idr.c void idr_remove(struct idr *idp, int id) · line 391
Quoted 8 lines
lib/idr.c +1
-1@@ -385,8 +385,8 @@ void idr_remove(struct idr *idp, int id)while (idp->id_free_cnt >=IDR_FREE_MAX ) { p =alloc_layer (idp);kmem_cache_free (idr_layer_cache, p); -return ; } +return ; }EXPORT_SYMBOL (idr_remove);
erk, ancient bug.
I _think_ the implications of this are that an idr tree will grow fatter than it needs to be, but there is no permanent leak: idr_destroy() will still free everything, yes?
And a consequence of the fix is that idr manipulations will now result in more allocs and frees, but the amount of memory which a tree uses will be less?
Re: [PATCH 01/10] Fix idr_remove()
Quoted 32 lines · Andrew Morton
Quoted 16 lines · On Tue, 29 Apr 2008 16:33:05 +0200 [email protected] wrote:
[PATCH 01/10]
This patch fixes
idr_remove(): the return inside the loop makes us free only a single layer.Signed-off-by Nadia Derbey <[email protected]>---
lib/idr.c| 2 +-1 file changed, 1 insertion(+), 1 deletion(-)Index:
linux-2.6.25-mm1/lib/idr.c
===================================================================lib/idr.c void idr_remove(struct idr *idp, int id) · line 391
Quoted 8 lines
lib/idr.c +1
-1@@ -385,8 +385,8 @@ void idr_remove(struct idr *idp, int id)while (idp->id_free_cnt >=IDR_FREE_MAX ) { p =alloc_layer (idp);kmem_cache_free (idr_layer_cache, p); -return ; } +return ; }EXPORT_SYMBOL (idr_remove);erk, ancient bug.
Quoted 3 lines
I _think_ the implications of this are that an idr tree will grow fatter than it needs to be, but there is no permanent leak:
idr_destroy()will still free everything, yes?
Yes, exactly. Actually, I've not checked whether all the kernel components call idr_destroy() when needed.
Quoted 3 lines
And a consequence of the fix is that idr manipulations will now result in more allocs and frees,
Not necessarily more allocs: this loop keeps IDR_FREE_MAX layers in the free list. So idr_pre_get() should be a noop.
Quoted 5 lines
but the amount of memory which a tree uses will be less?
Regards,
Nadia
PATCH 2/10 Introduce the ridr structure
In reply to [email protected][PATCH 02/10]
This patch introduces the ridr structure as an RCU safe idr structure: a layer is actually made of the existing idr layer, followed by the rcu head.
--- include/linux/idr.h | 6 +++--- include/linux/ridr.h | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++ init/main.c | 2 ++ lib/Makefile | 2 +- lib/idr.c | 2 +- lib/ridr.c | 26 ++++++++++++++++++++++++++ 6 files changed, 83 insertions(+), 5 deletions(-)
include/linux/ridr.h new file +50 -0
@@ -0,0 +1,50 @@ +/* +* include/linux/ridr.h +* +* Small id to pointer translation service avoiding fixed sized +* tables. RCU-based implmentation of IDRs. +*/ + +#ifndef _RIDR_H_ +#define _RIDR_H_ + +#include <linux/idr.h> +#include <linux/rcupdate.h> + +/* +* The idr_layer part should stay at the beginning of the structure +*/ +struct ridr_layer { +struct idr_layer idr; +struct rcu_head rcu_head; +}; + +struct ridr { +struct ridr_layer *top; +struct ridr_layer *id_free; +int layers; +int id_free_cnt; +spinlock_t lock; +}; + +#define RIDR_INIT (name) \ +{ \ + .top = NULL, \ + .id_free = NULL, \ + .layers = 0, \ + .id_free_cnt = 0, \ + .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ +} +#define DEFINE_RIDR (name) struct ridr name = RIDR_INIT(name) + +#define idr_to_ridr (p) container_of((p), struct ridr_layer, idr) +#define ridr_to_idr (p) (&((p)->idr)) + +/* +* This is what we export. +*/ + + +void __init ridr_init_cache (void ); + +#endif /* _RIDR_H_ */
lib/ridr.c new file +26 -0
@@ -0,0 +1,26 @@ +/* +* RCU-based idr API +*/ + + +#include <linux/slab.h> +#include <linux/init.h> +#include <linux/module.h> +#include <linux/ridr.h> + +static struct kmem_cache *ridr_layer_cache; + + +static void ridr_cache_ctor (struct kmem_cache *ridr_layer_cache, +void *ridr_layer) +{ +memset (ridr_layer,0 ,sizeof (struct ridr_layer )); +} + +void __init ridr_init_cache (void ) +{ + ridr_layer_cache =kmem_cache_create ("ridr_layer_cache" , +sizeof (struct ridr_layer ),0 ,SLAB_PANIC , + ridr_cache_ctor); +} +
lib/Makefile +1 -1
@@ -6,7 +6,7 @@ lib-y := ctype.o string.o vsprintf.o cmd rbtree.o radix-tree.o dump_stack.o \ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ - proportions.o prio_heap.o ratelimit.o + proportions.o prio_heap.o ratelimit.o ridr.o ifdef CONFIG_FTRACE # Do not profile string.o, since it may be used in early boot or vdso
init/main.c +2 -0
@@ -61,6 +61,7 @@#include <linux/sched.h> #include <linux/signal.h> #include <linux/idr.h> +#include <linux/ridr.h> #include <asm/io.h> #include <asm/bugs.h>
@@ -639,6 +640,7 @@ asmlinkage void __init start_kernel(voidkmem_cache_init ();debug_objects_mem_init ();idr_init_cache (); +ridr_init_cache ();setup_per_cpu_pageset ();numa_policy_init ();if (late_time_init)
lib/idr.c +1 -1
@@ -342,7 +342,7 @@ static void sub_remove(struct idr *idp,while ((shift >0 ) && p) { n = (id >> shift) &IDR_MASK ;__clear_bit (n, &p->bitmap); - *++paa = &p->ary[n]; + *++paa = (struct idr_layer **) &p->ary[n]; p = p->ary[n]; shift -=IDR_BITS ; }
include/linux/idr.h +3 -3
@@ -48,9 +48,9 @@#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVELstruct idr_layer { -unsigned long bitmap;/* A zero bit means "space here" */ -struct idr_layer *ary[1 <<IDR_BITS ]; -int count;/* When zero, we can release it */ +unsigned long bitmap;/* A zero bit means "space here" */ +void *ary[1 <<IDR_BITS ]; +int count;/* When zero, we can release it */ };struct idr {
--
Re: [PATCH 02/10] Introduce the ridr structure
include/linux/ridr.h line 6
Quoted 11 lines · On Tue 29 Apr at 16:33:06 +0200 [email protected] said:
Index:
linux-2.6.25-mm1/include/linux/ridr.h
===================================================================include/linux/ridr.h new file +6
-0@@ -0,0 +1,50 @@ +/* +* include/linux/ridr.h +* +* Small id to pointer translation service avoiding fixed sized +* tables. RCU-based implmentation of IDRs. +*/
^^^^^^^
s/implmentation/reimplementation
Additional comment here might be nice here since this amounts to a mostly copy of idr.h and its backing implementation, with all the associated maintenance headaches if both are in tree.
include/linux/ridr.h line 20
Quoted 7 lines
include/linux/ridr.h new file +7
-0+/* +* The idr_layer part should stay at the beginning of the structure +*/ +struct ridr_layer { +struct idr_layer idr; +struct rcu_head rcu_head; +};
Why does it have to be at the beginning? So an ridr_layer can be used as an idr_layer? This doesn't help review. As previous commenters noted, review would be a lot easier if this was incremental on idr.
lib/Makefile lib-y := ctype.o string.o vsprintf.o cmd · line 9
Quoted 10 lines
Index: linux-2.6.25-mm1/lib/Makefile
===================================================================lib/Makefile +1
-1@@ -6,7 +6,7 @@ lib-y := ctype.o string.o vsprintf.o cmd rbtree.o radix-tree.o dump_stack.o \ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ - proportions.o prio_heap.o ratelimit.o + proportions.o prio_heap.o ratelimit.o ridr.o
I vaguely recall past discussion of preferred insertion point, but lacking something in CodingStyle and especially given the redundancy here it could be nice to add ridr.o next to idr.o.
lib/idr.c static void sub_remove(struct idr *idp, · line 348
Quoted 12 lines
===================================================================
lib/idr.c +1
-1@@ -342,7 +342,7 @@ static void sub_remove(struct idr *idp,while ((shift >0 ) && p) { n = (id >> shift) &IDR_MASK ;__clear_bit (n, &p->bitmap); - *++paa = &p->ary[n]; + *++paa = (struct idr_layer **) &p->ary[n]; p = p->ary[n]; shift -=IDR_BITS ; }
For shifty use of an ridr_layer as an idr_layer?
Quoted 8 lines
Index:
linux-2.6.25-mm1/include/linux/idr.h
===================================================================include/linux/idr.h +0
-0@@ -48,9 +48,9 @@#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
include/linux/idr.h line 56
Quoted 10 lines
include/linux/idr.h +3
-3struct idr_layer { -unsigned long bitmap;/* A zero bit means "space here" */ -struct idr_layer *ary[1 <<IDR_BITS ]; -int count;/* When zero, we can release it */ +unsigned long bitmap;/* A zero bit means "space here" */ +void *ary[1 <<IDR_BITS ]; +int count;/* When zero, we can release it */ };struct idr {
This hunk is white space only...
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 3/10 Introduce ridr_pre_get()
In reply to [email protected][PATCH 03/10]
This patch introduces the ridr_pre_get() routine.
--- include/linux/ridr.h | 1 + lib/ridr.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+)
include/linux/ridr.h +1 -0
@@ -43,6 +43,7 @@ struct ridr {/* * This is what we export. */ +int ridr_pre_get (struct ridr *,gfp_t );void __init ridr_init_cache (void );
lib/ridr.c +46 -0
52 lines not on this page · raw message
--
Re: [PATCH 03/10] Introduce ridr_pre_get()
Quoted 3 lines · On Tue 29 Apr at 16:33:07 +0200 [email protected] said:
[PATCH 03/10]
This patch introduces the
ridr_pre_get()routine.
There's almost nothing here that isn't 1:1 duplication of idr.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 4/10 Introduce ridr_init()
In reply to [email protected][PATCH 04/10]
This patch introduces the ridr_init() routine.
--- include/linux/ridr.h | 1 + lib/ridr.c | 14 ++++++++++++++ 2 files changed, 15 insertions(+)
include/linux/ridr.h +1 -0
@@ -44,6 +44,7 @@ struct ridr {* This is what we export. */ int ridr_pre_get (struct ridr *,gfp_t ); +void ridr_init (struct ridr *);void __init ridr_init_cache (void );
lib/ridr.c +14 -0
@@ -70,3 +70,17 @@ void __init ridr_init_cache(void) ridr_cache_ctor); } +/** +* ridr_init - initialize ridr handle +* @idp: ridr handle +* +* This function is used to set up the handle (@idp) that you will pass +* to the rest of the functions. +*/ +void ridr_init (struct ridr *idp) +{ +memset (idp,0 ,sizeof (struct ridr )); +spin_lock_init (&idp->lock); +} +EXPORT_SYMBOL (ridr_init); +
--
Re: [PATCH 04/10] Introduce ridr_init()
Quoted 3 lines · On Tue 29 Apr at 16:33:08 +0200 [email protected] said:
[PATCH 04/10]
This patch introduces the
ridr_init()routine.
Again nothing added.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 5/10 Introduce ridr_get_new_above()
In reply to [email protected][PATCH 05/10]
This patch introduces the ridr_get_new_above() routine, and some common code between the idr an ridr API's.
--- include/linux/idr.h | 21 ++++++ include/linux/ridr.h | 1 lib/idr.c | 151 ++++++++++++++++++++++++++------------------ lib/ridr.c | 175 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 287 insertions(+), 61 deletions(-)
include/linux/ridr.h +1 -0
@@ -44,6 +44,7 @@ struct ridr {* This is what we export. */ int ridr_pre_get (struct ridr *,gfp_t ); +int ridr_get_new_above (struct ridr *,void *,int ,int *);void ridr_init (struct ridr *);
include/linux/idr.h +21 -0
@@ -71,6 +71,27 @@ struct idr { }#define DEFINE_IDR (name) struct idr name = IDR_INIT(name) +/* Actions to be taken after a call to _idr_sub_alloc */ +#define IDR_DONE -1 +#define IDR_NEED_TO_GROW -2 +#define IDR_NOMORE_SPACE -3 +#define IDR_GO_TOP -4 +#define IDR_GO_UP -5 + +#define _idr_rc_to_errno (rc) ((rc) == -1 ? -EAGAIN : -ENOSPC) + +static inline void _idr_set_new_slot (struct idr_layer *new, +struct idr_layer *p) +{ + new->ary[0 ] = p; + new->count =1 ; +if (p->bitmap ==IDR_FULL ) +__set_bit (0 , &new->bitmap); +} + +void _idr_mark_full (struct idr_layer **,int ); +int _idr_sub_alloc (int *,int *,struct idr_layer **,struct idr_layer **); +/* * This is what we export. */
lib/idr.c +90 -61
220 lines not on this page · raw message
lib/ridr.c +175 -0
187 lines not on this page · raw message
--
Re: [PATCH 05/10] Introduce ridr_get_new_above()
Quoted 4 lines · On Tue 29 Apr at 16:33:09 +0200 [email protected] said:
[PATCH 05/10]
This patch introduces the
ridr_get_new_above()routine, and some common code between the idr an ridr API's.
The ridr_get_new_above() is the first place we see something really different compared to idr (an RCU addition). This is a lot of patching so far for what would be a small incremental change otherwise.
Quoted 5 lines
Index:
linux-2.6.25-mm1/include/linux/idr.h
===================================================================
include/linux/idr.h struct idr { · line 79
Quoted 9 lines
include/linux/idr.h +6
-0@@ -71,6 +71,27 @@ struct idr { }#define DEFINE_IDR (name) struct idr name = IDR_INIT(name) +/* Actions to be taken after a call to _idr_sub_alloc */ +#define IDR_DONE -1 +#define IDR_NEED_TO_GROW -2 +#define IDR_NOMORE_SPACE -3 +#define IDR_GO_TOP -4 +#define IDR_GO_UP -5
This stuff is useful on its own in as much as it improves code readability. A lot of this patch (the "some common code between the idr and ridr API's" part) could be a standalone patch distinct from the ridr series and then be at the head of your stack.
include/linux/idr.h struct idr { · line 91
Quoted 12 lines
include/linux/idr.h +11
-0+return action; +case IDR_DONE : + goto end_loop; +case IDR_GO_UP : +continue ; +case IDR_GO_TOP : + goto restart; +default : + m = action;break ; + } +BUG_ON (m <0 );
Why the added BUG_ON()? These couple hunks are a bit muddled, so maybe I missed something. But I don't see anything different in how m or bm are being manipulated such that m<0 is anymore likely after this patch.
Quoted 15 lines
Index:
linux-2.6.25-mm1/lib/ridr.c
===================================================================lib/ridr.c +7
-0@@ -11,6 +11,23 @@static struct kmem_cache *ridr_layer_cache; +static struct ridr_layer *get_from_free_list (struct ridr *idp) +{ +struct ridr_layer *q; +struct idr_layer *p; +unsigned long flags; + +spin_lock_irqsave (&idp->lock, flags);
lib/ridr.c line 30
Quoted 10 lines
lib/ridr.c +10
-0+if ((q = idp->id_free)) { + p =ridr_to_idr (q); + idp->id_free = p->ary[0 ]; + idp->id_free_cnt--; + p->ary[0 ] =NULL ; + } +spin_unlock_irqrestore (&idp->lock, flags); +return (q); +} +
idr's alloc_layer() in disguise?
lib/ridr.c line 32
Quoted 2 lines
lib/ridr.c +2
-0+static int sub_alloc (struct ridr *idp,int *starting_id, +struct ridr_layer **rpa,struct idr_layer **pa)
...
More or less duplication
...
Quoted 9 lines
lib/ridr.c +9
-0+* Create the layer below if it is missing. +*/ +if (!p->ary[m]) { + new =get_from_free_list (idp); +if (!new) +return -1 ; +rcu_assign_pointer (p->ary[m], new); + p->count++; + }
lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 132
Quoted 10 lines
lib/ridr.c +10
-0+ pa[l] = p; + rpa[l--] =idr_to_ridr (p); + p = p->ary[m]; + } + +end_loop: + pa[l] = p; + rpa[l] =idr_to_ridr (p); +return id; +}
Oh but wait..there's some RCU-ness tucked in there.
Quoted 13 lines
lib/ridr.c +13
-0+ +static int ridr_get_empty_slot (struct ridr *idp,int starting_id, +struct ridr_layer **rpa,struct idr_layer **pa) +{ +struct ridr_layer *p, *rnew; +int layers, v, id; +unsigned long flags; + + id = starting_id; +build_up: + p = idp->top; + layers = idp->layers; +if (unlikely (!p)) {
lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 155
Quoted 10 lines
lib/ridr.c +10
-0+ p =get_from_free_list (idp); +if (!p) +return -1 ; + layers =1 ; + } +/* +* Add a new layer to the top of the tree if the requested +* id is larger than the currently allocated space. +*/ +while (layers <MAX_LEVEL -1 && id >= (1 << (layers *IDR_BITS ))) {
^^ ^^
Dropped some parens. Otherwise more duplication...
Quoted 7 lines
lib/ridr.c +7
-0+ rnew->idr.ary[0 ] =NULL ; + rnew->idr.bitmap = rnew->idr.count =0 ; +__move_to_free_list (idp, rnew); + } +spin_unlock_irqrestore (&idp->lock, flags); +return -1 ; + }
lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 184
Quoted 10 lines
lib/ridr.c +10
-0+_idr_set_new_slot (ridr_to_idr (rnew),ridr_to_idr (p)); + p = rnew; + } +rcu_assign_pointer (idp->top, p); + idp->layers = layers; + v =sub_alloc (idp, &id, rpa, pa); +if (v ==IDR_NEED_TO_GROW ) + goto build_up; +return (v); +}
Some more RCU.
Quoted 10 lines
lib/ridr.c +10
-0+static int ridr_get_new_above_int (struct ridr *idp,void *ptr,int starting_id) +{ +struct ridr_layer *rpa[MAX_LEVEL ]; +struct idr_layer *pa[MAX_LEVEL ]; +int id; + + id =ridr_get_empty_slot (idp, starting_id, rpa, pa); +if (id >=0 ) { +/* +* Successfully found an empty slot. Install the user
lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 205
Quoted 10 lines
lib/ridr.c +10
-0+* pointer and mark the slot full. +*/ +rcu_assign_pointer (pa[0 ]->ary[id &IDR_MASK ], + (struct ridr_layer *)ptr); + pa[0 ]->count++; +_idr_mark_full (pa, id); + } + +return id; +}
And other line of RCU.
OK. So at this point in patch 5/10 we've got 3 lines of new code and hundreds of lines of duplicated code?
A while more looking through the rest of the patches for the rest of the context and I might be able to actually think about the implications of these three lines being where they are.
Locking changes are complicated enough without all this obfuscation! I understand the desire to not break IDR, but...
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
Re: [PATCH 05/10] Introduce ridr_get_new_above()
Quoted 194 lines · Tim Pepper
Quoted 4 lines · On Tue 29 Apr at 16:33:09 +0200 [email protected] said:
[PATCH 05/10]
This patch introduces the
ridr_get_new_above()routine, and some common code between the idr an ridr API's.The
ridr_get_new_above()is the first place we see something really different compared to idr (an RCU addition). This is a lot of patching so far for what would be a small incremental change otherwise.Quoted 5 lines
Index:
linux-2.6.25-mm1/include/linux/idr.h
===================================================================include/linux/idr.h struct idr { · line 79
Quoted 9 lines
include/linux/idr.h +6
-0@@ -71,6 +71,27 @@ struct idr { }#define DEFINE_IDR (name) struct idr name = IDR_INIT(name) +/* Actions to be taken after a call to _idr_sub_alloc */ +#define IDR_DONE -1 +#define IDR_NEED_TO_GROW -2 +#define IDR_NOMORE_SPACE -3 +#define IDR_GO_TOP -4 +#define IDR_GO_UP -5This stuff is useful on its own in as much as it improves code readability. A lot of this patch (the "some common code between the idr and ridr API's" part) could be a standalone patch distinct from the ridr series and then be at the head of your stack.
include/linux/idr.h struct idr { · line 91
Quoted 12 lines
include/linux/idr.h +11
-0+return action; +case IDR_DONE : + goto end_loop; +case IDR_GO_UP : +continue ; +case IDR_GO_TOP : + goto restart; +default : + m = action;break ; + } +BUG_ON (m <0 );Why the added
BUG_ON()? These couple hunks are a bit muddled, so maybe I missed something. But I don't see anything different in how m or bm are being manipulated such that m<0 is anymore likely after this patch.Quoted 15 lines
Index:
linux-2.6.25-mm1/lib/ridr.c
===================================================================lib/ridr.c +7
-0@@ -11,6 +11,23 @@static struct kmem_cache *ridr_layer_cache; +static struct ridr_layer *get_from_free_list (struct ridr *idp) +{ +struct ridr_layer *q; +struct idr_layer *p; +unsigned long flags; + +spin_lock_irqsave (&idp->lock, flags);lib/ridr.c line 30
Quoted 10 lines
lib/ridr.c +10
-0+if ((q = idp->id_free)) { + p =ridr_to_idr (q); + idp->id_free = p->ary[0 ]; + idp->id_free_cnt--; + p->ary[0 ] =NULL ; + } +spin_unlock_irqrestore (&idp->lock, flags); +return (q); +} +idr's
alloc_layer()in disguise?lib/ridr.c line 32
Quoted 2 lines
lib/ridr.c +2
-0+static int sub_alloc (struct ridr *idp,int *starting_id, +struct ridr_layer **rpa,struct idr_layer **pa)...
More or less duplication
...Quoted 9 lines
lib/ridr.c +9
-0+* Create the layer below if it is missing. +*/ +if (!p->ary[m]) { + new =get_from_free_list (idp); +if (!new) +return -1 ; +rcu_assign_pointer (p->ary[m], new); + p->count++; + }lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 132
Quoted 10 lines
lib/ridr.c +10
-0+ pa[l] = p; + rpa[l--] =idr_to_ridr (p); + p = p->ary[m]; + } + +end_loop: + pa[l] = p; + rpa[l] =idr_to_ridr (p); +return id; +}Oh but wait..there's some RCU-ness tucked in there.
Quoted 13 lines
lib/ridr.c +13
-0+ +static int ridr_get_empty_slot (struct ridr *idp,int starting_id, +struct ridr_layer **rpa,struct idr_layer **pa) +{ +struct ridr_layer *p, *rnew; +int layers, v, id; +unsigned long flags; + + id = starting_id; +build_up: + p = idp->top; + layers = idp->layers; +if (unlikely (!p)) {lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 155
Quoted 10 lines
lib/ridr.c +10
-0+ p =get_from_free_list (idp); +if (!p) +return -1 ; + layers =1 ; + } +/* +* Add a new layer to the top of the tree if the requested +* id is larger than the currently allocated space. +*/ +while (layers <MAX_LEVEL -1 && id >= (1 << (layers *IDR_BITS ))) {^^ ^^
Dropped some parens. Otherwise more duplication...Quoted 7 lines
lib/ridr.c +7
-0+ rnew->idr.ary[0 ] =NULL ; + rnew->idr.bitmap = rnew->idr.count =0 ; +__move_to_free_list (idp, rnew); + } +spin_unlock_irqrestore (&idp->lock, flags); +return -1 ; + }lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 184
Quoted 10 lines
lib/ridr.c +10
-0+_idr_set_new_slot (ridr_to_idr (rnew),ridr_to_idr (p)); + p = rnew; + } +rcu_assign_pointer (idp->top, p); + idp->layers = layers; + v =sub_alloc (idp, &id, rpa, pa); +if (v ==IDR_NEED_TO_GROW ) + goto build_up; +return (v); +}Some more RCU.
Quoted 10 lines
lib/ridr.c +10
-0+static int ridr_get_new_above_int (struct ridr *idp,void *ptr,int starting_id) +{ +struct ridr_layer *rpa[MAX_LEVEL ]; +struct idr_layer *pa[MAX_LEVEL ]; +int id; + + id =ridr_get_empty_slot (idp, starting_id, rpa, pa); +if (id >=0 ) { +/* +* Successfully found an empty slot. Install the user lib/ridr.c int ridr_pre_get(struct ridr *idp, gfp_t · line 205
Quoted 10 lines
lib/ridr.c +10
-0+* pointer and mark the slot full. +*/ +rcu_assign_pointer (pa[0 ]->ary[id &IDR_MASK ], + (struct ridr_layer *)ptr); + pa[0 ]->count++; +_idr_mark_full (pa, id); + } + +return id; +}And other line of RCU.
OK. So at this point in patch 5/10 we've got 3 lines of new code and hundreds of lines of duplicated code?
Quoted 7 lines
A while more looking through the rest of the patches for the rest of the context and I might be able to actually think about the implications of these three lines being where they are.
Locking changes are complicated enough without all this obfuscation! I understand the desire to not break IDR, but...
OK, you convinced me. I'll re-send a new patchset that is incremental on top of idr. Sorry (and thanks a lot) for the painful review!
Regards,
Nadia
PATCH 6/10 Introduce ridr_get_new()
In reply to [email protected][PATCH 06/10]
This patch introduces the ridr_get_new() routine.
--- include/linux/ridr.h | 1 + lib/ridr.c | 27 +++++++++++++++++++++++++++ 2 files changed, 28 insertions(+)
include/linux/ridr.h +1 -0
@@ -44,6 +44,7 @@ struct ridr {* This is what we export. */ int ridr_pre_get (struct ridr *,gfp_t ); +int ridr_get_new (struct ridr *,void *,int *);int ridr_get_new_above (struct ridr *,void *,int ,int *);void ridr_init (struct ridr *);
lib/ridr.c +27 -0
@@ -232,6 +232,33 @@ int ridr_get_new_above(struct ridr *idp, }EXPORT_SYMBOL (ridr_get_new_above); +/** +* ridr_get_new - allocate new ridr entry +* @idp: ridr handle +* @ptr: pointer you want associated with the ide +* @id: pointer to the allocated handle +* +* This is the allocate id function. It should be called with any +* required locks. +* +* If memory is required, it will return -EAGAIN, you should unlock +* and go back to the ridr_pre_get() call. If the ridr is full, it will +* return -ENOSPC. +* +* @id returns a value in the range 0 ... 0x7fffffff +*/ +int ridr_get_new (struct ridr *idp,void *ptr,int *id) +{ +int rv; + + rv =ridr_get_new_above_int (idp, ptr,0 ); +if (rv <0 ) +return _idr_rc_to_errno (rv); + *id = rv; +return 0 ; +} +EXPORT_SYMBOL (ridr_get_new); +static void ridr_cache_ctor (struct kmem_cache *ridr_layer_cache,void *ridr_layer) {
--
Re: [PATCH 06/10] Introduce ridr_get_new()
Quoted 3 lines · On Tue 29 Apr at 16:33:10 +0200 [email protected] said:
[PATCH 06/10]
This patch introduces the
ridr_get_new()routine.
Duplication + small useful cleanup that could be standalone.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 7/10 Introduce ridr_find()
In reply to [email protected][PATCH 07/10]
This patch introduces the ridr_find() routine.
--- include/linux/ridr.h | 17 +++++++++++++++++ lib/ridr.c | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 51 insertions(+)
include/linux/ridr.h +17 -0
@@ -40,9 +40,26 @@ struct ridr {#define idr_to_ridr (p) container_of((p), struct ridr_layer, idr)#define ridr_to_idr (p) (&((p)->idr)) +/** +* Ridr synchronization (see radix-tree.h) +* +* ridr_find() is able to be called locklessly, using RCU. The caller must +* ensure calls to this function are made within rcu_read_lock() regions. +* Other readers (lock-free or otherwise) and modifications may be running +* concurrently. +* +* It is still required that the caller manage the synchronization and +* lifetimes of the items. So if RCU lock-free lookups are used, typically +* this would mean that the items have their own locks, or are amenable to +* lock-free access; and that the items are freed by RCU (or only freed after +* having been deleted from the ridr tree *and* a synchronize_rcu() grace +* period). +*/ +/* * This is what we export. */ +void *ridr_find (struct ridr *,int );int ridr_pre_get (struct ridr *,gfp_t );int ridr_get_new (struct ridr *,void *,int *);int ridr_get_new_above (struct ridr *,void *,int ,int *);
lib/ridr.c +34 -0
@@ -259,6 +259,40 @@ int ridr_get_new(struct ridr *idp, void }EXPORT_SYMBOL (ridr_get_new); +/** +* ridr_find - return pointer for given id +* @idp: ridr handle +* @id: lookup key +* +* Return the pointer given the id it has been registered with. A %NULL +* return indicates that @id is not valid or you passed %NULL in +* ridr_get_new(). +* +* This function can be called under rcu_read_lock(), given that the leaf +* pointers lifetimes are correctly managed. +*/ +void *ridr_find (struct ridr *idp,int id) +{ +int n; +struct ridr_layer *p; + + n = idp->layers *IDR_BITS ; + p =rcu_dereference (idp->top); + +/* Mask off upper bits we don't use for the search. */ + id &=MAX_ID_MASK ; + +if (id >= (1 << n)) +return NULL ; + +while (n >0 && p) { + n -=IDR_BITS ; + p =rcu_dereference (p->idr.ary[(id >> n) &IDR_MASK ]); + } +return ((void *)p); +} +EXPORT_SYMBOL (ridr_find); +static void ridr_cache_ctor (struct kmem_cache *ridr_layer_cache,void *ridr_layer) {
--
Re: [PATCH 07/10] Introduce ridr_find()
Quoted 3 lines · On Tue 29 Apr at 16:33:11 +0200 [email protected] said:
[PATCH 07/10]
This patch introduces the
ridr_find()routine.
Finally this one has some meat. But, besides the comments, this could be around two lines added to idr instead of many more duplicated.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 8/10 Introduce ridr_remove()
In reply to [email protected][PATCH 08/10]
This patch introduces the ridr_remove() routine.
--- include/linux/idr.h | 1 include/linux/ridr.h | 1 lib/idr.c | 7 ++-- lib/ridr.c | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 89 insertions(+), 3 deletions(-)
include/linux/ridr.h +1 -0
@@ -63,6 +63,7 @@ void *ridr_find(struct ridr *, int);int ridr_pre_get (struct ridr *,gfp_t );int ridr_get_new (struct ridr *,void *,int *);int ridr_get_new_above (struct ridr *,void *,int ,int *); +void ridr_remove (struct ridr *,int );void ridr_init (struct ridr *);
include/linux/idr.h +1 -0
@@ -91,6 +91,7 @@ static inline void _idr_set_new_slot(strvoid _idr_mark_full (struct idr_layer **,int );int _idr_sub_alloc (int *,int *,struct idr_layer **,struct idr_layer **); +void _idr_remove_warning (const char *,int );/* * This is what we export.
lib/idr.c +4 -3
@@ -356,9 +356,10 @@ int idr_get_new(struct idr *idp, void *p }EXPORT_SYMBOL (idr_get_new); -static void idr_remove_warning (int id) +void _idr_remove_warning (const char *caller,int id) { -printk ("idr_remove called for id=%d which is not allocated.\n" , id); +printk (KERN_INFO "%s called for id=%d which is not allocated.\n" , + caller, id);dump_stack (); }
@@ -390,7 +391,7 @@ static void sub_remove(struct idr *idp,if (!*paa) idp->layers =0 ; }else -idr_remove_warning (id); +_idr_remove_warning ("idr_remove" , id); }/**
lib/ridr.c +83 -0
95 lines not on this page · raw message
--
Re: [PATCH 08/10] Introduce ridr_remove()
Quoted 3 lines · On Tue 29 Apr at 16:33:12 +0200 [email protected] said:
[PATCH 08/10]
This patch introduces the
ridr_remove()routine.
A bit of cleanup and roughly 2 lines RCU.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 9/10 Integrate the ridr code into IPC code
In reply to [email protected][PATCH 09/10]
This patche makes the ipc ode use the ridr API.
--- include/linux/ipc_namespace.h | 4 ++-- ipc/namespace.c | 2 +- ipc/shm.c | 2 +- ipc/util.c | 41 ++++++++++++++++------------------------- 4 files changed, 20 insertions(+), 29 deletions(-)
include/linux/ipc_namespace.h +2 -2
@@ -2,7 +2,7 @@#define __IPC_NAMESPACE_H__#include <linux/err.h> -#include <linux/idr.h> +#include <linux/ridr.h> #include <linux/rwsem.h> #include <linux/notifier.h>
@@ -21,7 +21,7 @@ struct ipc_ids {unsigned short seq;unsigned short seq_max;struct rw_semaphore rw_mutex; -struct idr ipcs_idr; +struct ridr ipcs_ridr; };struct ipc_namespace {
ipc/namespace.c +1 -1
@@ -74,7 +74,7 @@ void free_ipcs(struct ipc_namespace *ns, in_use = ids->in_use;for (total =0 , next_id =0 ; total < in_use; next_id++) { - perm =idr_find (&ids->ipcs_idr, next_id); + perm =ridr_find (&ids->ipcs_ridr, next_id);if (perm ==NULL )continue ;ipc_lock_by_ptr (perm);
ipc/shm.c +1 -1
@@ -569,7 +569,7 @@ static void shm_get_stat(struct ipc_namestruct shmid_kernel *shp;struct inode *inode; - shp =idr_find (&shm_ids (ns).ipcs_idr, next_id); + shp =ridr_find (&shm_ids (ns).ipcs_ridr, next_id);if (shp ==NULL )continue ;
ipc/util.c +16 -25
143 lines not on this page · raw message
--
Re: [PATCH 09/10] Integrate the ridr code into IPC code
Quoted 3 lines · On Tue 29 Apr at 16:33:13 +0200 [email protected] said:
[PATCH 09/10]
This patche makes the ipc ode use the ridr API.
Superfluous except...
Quoted 7 lines
ipc/util.c +0
-2@@ -699,18 +695,13 @@ struct kern_ipc_perm *ipc_lock(struct ipstruct kern_ipc_perm *out;int lid =ipcid_to_idx (id); -down_read (&ids->rw_mutex); -rcu_read_lock ();
ipc/util.c struct kern_ipc_perm *ipc_lock(struct ip · line 713
Quoted 10 lines
ipc/util.c +1
-4- out =idr_find (&ids->ipcs_idr, lid); + out =ridr_find (&ids->ipcs_ridr, lid);if (out ==NULL ) {rcu_read_unlock (); -up_read (&ids->rw_mutex);return ERR_PTR (-EINVAL ); } -up_read (&ids->rw_mutex); -
...the removal of the rw_mutex down/up_read().
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
PATCH 10/10 Get rid of ipc_lock_down()
In reply to [email protected][PATCH 10/10]
With the previous patch ipc_lock() becomes lockless. So there is no need anymore for ipc_lock_down()-like routines.
--- ipc/shm.c | 21 +++------------------ ipc/util.c | 52 +--------------------------------------------------- ipc/util.h | 6 ------ 3 files changed, 4 insertions(+), 75 deletions(-)
ipc/util.c +1 -51
@@ -716,56 +716,6 @@ struct kern_ipc_perm *ipc_lock(struct ipreturn out; } -/** -* ipc_lock_down - Lock an ipc structure with rw_sem held -* @ids: IPC identifier set -* @id: ipc id to look for -* -* Look for an id in the ipc ids ridr and lock the associated ipc object. -* -* The ipc object is locked on exit. -* -* This is the routine that should be called when the rw_mutex is already -* held, i.e. ridr tree protected. -*/ - -struct kern_ipc_perm *ipc_lock_down (struct ipc_ids *ids,int id) -{ -struct kern_ipc_perm *out; -int lid =ipcid_to_idx (id); - -rcu_read_lock (); - out =ridr_find (&ids->ipcs_ridr, lid); -if (out ==NULL ) { -rcu_read_unlock (); -return ERR_PTR (-EINVAL ); - } - -spin_lock (&out->lock); - -/* -* No need to verify that the structure is still valid since the -* rw_mutex is held. -*/ -return out; -} - -struct kern_ipc_perm *ipc_lock_check_down (struct ipc_ids *ids,int id) -{ -struct kern_ipc_perm *out; - - out =ipc_lock_down (ids, id); -if (IS_ERR (out)) -return out; - -if (ipc_checkid (out, id)) { -ipc_unlock (out); -return ERR_PTR (-EIDRM ); - } - -return out; -} -struct kern_ipc_perm *ipc_lock_check (struct ipc_ids *ids,int id) {struct kern_ipc_perm *out;
@@ -837,7 +787,7 @@ struct kern_ipc_perm *ipcctl_pre_down(stint err;down_write (&ids->rw_mutex); - ipcp =ipc_lock_check_down (ids, id); + ipcp =ipc_lock_check (ids, id);if (IS_ERR (ipcp)) { err =PTR_ERR (ipcp); goto out_up;
ipc/util.h +0 -6
@@ -102,11 +102,6 @@ void* ipc_rcu_alloc(int size);void ipc_rcu_getref (void *ptr);void ipc_rcu_putref (void *ptr); -/* -* ipc_lock_down: called with rw_mutex held -* ipc_lock: called without that lock held -*/ -struct kern_ipc_perm *ipc_lock_down (struct ipc_ids *,int );struct kern_ipc_perm *ipc_lock (struct ipc_ids *,int );void kernel_to_ipc64_perm (struct kern_ipc_perm *in,struct ipc64_perm *out);
@@ -155,7 +150,6 @@ static inline void ipc_unlock(struct kerrcu_read_unlock (); } -struct kern_ipc_perm *ipc_lock_check_down (struct ipc_ids *ids,int id);struct kern_ipc_perm *ipc_lock_check (struct ipc_ids *ids,int id);int ipcget (struct ipc_namespace *ns,struct ipc_ids *ids,struct ipc_ops *ops,struct ipc_params *params);
ipc/shm.c +3 -18
@@ -112,23 +112,8 @@ void __init shm_init (void) }/* -* shm_lock_(check_)down routines are called in the paths where the rw_mutex -* is held to protect access to the idr tree. -*/ -static inline struct shmid_kernel *shm_lock_down (struct ipc_namespace *ns, -int id) -{ -struct kern_ipc_perm *ipcp =ipc_lock_down (&shm_ids (ns), id); - -if (IS_ERR (ipcp)) -return (struct shmid_kernel *)ipcp; - - return container_of(ipcp, struct shmid_kernel, shm_perm); -} - -/* * shm_lock_(check_) routines are called in the paths where the rw_mutex -* is not held. +* is not necessarily held. */ static inline struct shmid_kernel *shm_lock (struct ipc_namespace *ns,int id) {
@@ -211,7 +196,7 @@ static void shm_close(struct vm_area_strdown_write (&shm_ids (ns).rw_mutex);/* remove from the list of attaches of the shm segment */ - shp =shm_lock_down (ns, sfd->id); + shp =shm_lock (ns, sfd->id);BUG_ON (IS_ERR (shp)); shp->shm_lprid =task_tgid_vnr (current); shp->shm_dtim =get_seconds ();
@@ -933,7 +918,7 @@ invalid: out_nattch:down_write (&shm_ids (ns).rw_mutex); - shp =shm_lock_down (ns, shmid); + shp =shm_lock (ns, shmid);BUG_ON (IS_ERR (shp)); shp->shm_nattch--; if(shp->shm_nattch == 0 &&
--
Re: [PATCH 10/10] Get rid of ipc_lock_down()
Quoted 4 lines · On Tue 29 Apr at 16:33:14 +0200 [email protected] said:
[PATCH 10/10]
With the previous patch
ipc_lock()becomes lockless. So there is no need anymore for ipc_lock_down()-like routines.
...cleanup post conversion to RCU.
Could we get a version of the series without all the duplication and without the cleanups (separate into standalone pre- and post- patches)? If you're too busy, now that I've sifted through these I could make a simpler series that does this.
It will be a looooot easier to discuss the locking when all we're looking at is the locking changes.
Signature · 2 lines
Tim Pepper <[email protected]> IBM Linux Technology Center
Andrew Morton
maintainerQuoted 15 lines · On Tue, 29 Apr 2008 16:33:04 +0200 [email protected] wrote:
After scalability problems had been detected when using the sysV ipcs, I have proposed to use an RCU based implementation of the IDR api instead (see thread http://lkml.org/lkml/2008/4/11/212).
Resending the patch series after
. integrating Paul's remarks
. fixing a bug I had introduced
. porting it to 2.6.25-mm1.Reviewers are still welcome!
Patch 1 can be taken alone: it fixes a problem in the existing IDR API.
Patches should be applied on linux-2.6.25-mm1, in the following order:
Quoted 11 lines
[ PATCH 01/10 ] : idr_minor_fix.patch [ PATCH 02/10 ] : ridr_structure.patch [ PATCH 03/10 ] : ridr_pre_get.patch [ PATCH 04/10 ] : ridr_init.patch
[ PATCH 05/10 ] : ridr_get_new_above.patch [ PATCH 06/10 ] : ridr_get_new.patch [ PATCH 07/10 ] : ridr_find.patch
[ PATCH 08/10 ] : ridr_remove.patch
[ PATCH 09/10 ] : ipc_use_ridr.patch [ PATCH 10/10 ] : remove_ipc_lock_down.patch
hm, you've been busy.
As all this work is entirely for performance reasons, the changelog should have (lots of) performance testing results! Please.
Quoted 32 lines · Andrew Morton
Quoted 15 lines · On Tue, 29 Apr 2008 16:33:04 +0200 [email protected] wrote:
After scalability problems had been detected when using the sysV ipcs, I have proposed to use an RCU based implementation of the IDR api instead (see thread http://lkml.org/lkml/2008/4/11/212).
Resending the patch series after
. integrating Paul's remarks
. fixing a bug I had introduced
. porting it to 2.6.25-mm1.Reviewers are still welcome!
Patch 1 can be taken alone: it fixes a problem in the existing IDR API.
Patches should be applied on linux-2.6.25-mm1, in the following order:
Quoted 11 lines
[ PATCH 01/10 ] : idr_minor_fix.patch [ PATCH 02/10 ] : ridr_structure.patch [ PATCH 03/10 ] : ridr_pre_get.patch [ PATCH 04/10 ] : ridr_init.patch
[ PATCH 05/10 ] : ridr_get_new_above.patch [ PATCH 06/10 ] : ridr_get_new.patch [ PATCH 07/10 ] : ridr_find.patch
[ PATCH 08/10 ] : ridr_remove.patch
[ PATCH 09/10 ] : ipc_use_ridr.patch [ PATCH 10/10 ] : remove_ipc_lock_down.patch
Quoted 6 lines
hm, you've been busy.
As all this work is entirely for performance reasons, the changelog should have (lots of) performance testing results! Please.
Here are the results I've got for the pmsg test sent by Manfred:
for i in 1 2 3 4 5 6 7 8;do ./pmsg $i 5;done > output.25_mm1.ref.8 for i in 1 2 3 4 5 6 7 8;do ./pmsg $i 5;done > output.25_mm1.patch.8
2.6.25-mm1 (ref) 2.6.25-mm1(patched)
Total (1 cpu): 876000 985496 Total (2 cpus): 1549592 1740591 Total (3 cpus): 1694370 2327468 Total (4 cpus): 404553 2465787 Total (5 cpus): 391283 3215676 Total (6 cpus): 263249 3849121 Total (7 cpus): 191742 4209866 Total (8 cpus): 141722 4255585
Full output files attached.
Will send the rest tomorrow.
Regards
Nadia
pmsg [nr queues] [timeout]
Using 1 queues/cpus (2 threads) for 5 seconds.
thread 1: sysvmsg 0 type 0 bound to 0001h
thread 0: sysvmsg 0 type 1 bound to 0001h
Result matrix:
Thread 0: 438000 1: 438000
Total: 876000
pmsg [nr queues] [timeout]
Using 2 queues/cpus (4 threads) for 5 seconds.
thread 0: sysvmsg 32768 type 1 bound to 0001h
thread 1: sysvmsg 65537 type 1 bound to 0002h
thread 3: sysvmsg 65537 type 0 bound to 0002h
thread 2: sysvmsg 32768 type 0 bound to 0001h
Result matrix:
Thread 0: 385675 2: 385675 Thread 1: 389121 3: 389121
Total: 1549592
pmsg [nr queues] [timeout]
Using 3 queues/cpus (6 threads) for 5 seconds.
thread 0: sysvmsg 98304 type 1 bound to 0001h
thread 3: sysvmsg 98304 type 0 bound to 0001h
thread 1: sysvmsg 131073 type 1 bound to 0002h
thread 2: sysvmsg 163842 type 1 bound to 0004h
thread 5: sysvmsg 163842 type 0 bound to 0004h
thread 4: sysvmsg 131073 type 0 bound to 0002h
Result matrix:
Thread 0: 279690 3: 279690 Thread 1: 283228 4: 283229 Thread 2: 284266 5: 284267
Total: 1694370
pmsg [nr queues] [timeout]
Using 4 queues/cpus (8 threads) for 5 seconds.
thread 0: sysvmsg 196608 type 1 bound to 0001h
thread 1: sysvmsg 229377 type 1 bound to 0002h
thread 2: sysvmsg 262146 type 1 bound to 0004h
thread 3: sysvmsg 294915 type 1 bound to 0008h
thread 4: sysvmsg 196608 type 0 bound to 0001h
thread 7: sysvmsg 294915 type 0 bound to 0008h
thread 6: sysvmsg 262146 type 0 bound to 0004h
thread 5: sysvmsg 229377 type 0 bound to 0002h
Result matrix:
Thread 0: 50305 4: 50305 Thread 1: 50168 5: 50168 Thread 2: 50922 6: 50922 Thread 3: 50881 7: 50882
Total: 404553
pmsg [nr queues] [timeout]
Using 5 queues/cpus (10 threads) for 5 seconds.
thread 0: sysvmsg 327680 type 1 bound to 0001h
thread 1: sysvmsg 360449 type 1 bound to 0002h
thread 2: sysvmsg 393218 type 1 bound to 0004h
thread 3: sysvmsg 425987 type 1 bound to 0008h
thread 4: sysvmsg 458756 type 1 bound to 0010h
thread 8: sysvmsg 425987 type 0 bound to 0008h
thread 7: sysvmsg 393218 type 0 bound to 0004h
thread 6: sysvmsg 360449 type 0 bound to 0002h
thread 5: sysvmsg 327680 type 0 bound to 0001h
thread 9: sysvmsg 458756 type 0 bound to 0010h
Result matrix:
Thread 0: 29684 5: 29684 Thread 1: 30236 6: 30237 Thread 2: 30902 7: 30902 Thread 3: 30699 8: 30700 Thread 4: 74119 9: 74120
Total: 391283
pmsg [nr queues] [timeout]
Using 6 queues/cpus (12 threads) for 5 seconds.
thread 0: sysvmsg 491520 type 1 bound to 0001h
thread 2: sysvmsg 557058 type 1 bound to 0004h
thread 7: sysvmsg 524289 type 0 bound to 0002h
thread 1: sysvmsg 524289 type 1 bound to 0002h
thread 8: sysvmsg 557058 type 0 bound to 0004h
thread 3: sysvmsg 589827 type 1 bound to 0008h
thread 6: sysvmsg 491520 type 0 bound to 0001h
thread 4: sysvmsg 622596 type 1 bound to 0010h
thread 11: sysvmsg 655365 type 0 bound to 0020h
thread 5: sysvmsg 655365 type 1 bound to 0020h
thread 10: sysvmsg 622596 type 0 bound to 0010h
thread 9: sysvmsg 589827 type 0 bound to 0008h
Result matrix:
Thread 0: 17229 6: 17230 Thread 1: 17442 7: 17442 Thread 2: 17337 8: 17337 Thread 3: 17420 9: 17421 Thread 4: 31020 10: 31020 Thread 5: 31175 11: 31176
Total: 263249
pmsg [nr queues] [timeout]
Using 7 queues/cpus (14 threads) for 5 seconds.
thread 0: sysvmsg 688128 type 1 bound to 0001h
thread 1: sysvmsg 720897 type 1 bound to 0002h
thread 2: sysvmsg 753666 type 1 bound to 0004h
thread 3: sysvmsg 786435 type 1 bound to 0008h
thread 4: sysvmsg 819204 type 1 bound to 0010h
thread 5: sysvmsg 851973 type 1 bound to 0020h
thread 6: sysvmsg 884742 type 1 bound to 0040h
thread 8: sysvmsg 720897 type 0 bound to 0002h
thread 10: sysvmsg 786435 type 0 bound to 0008h
thread 9: sysvmsg 753666 type 0 bound to 0004h
thread 11: sysvmsg 819204 type 0 bound to 0010h
thread 7: sysvmsg 688128 type 0 bound to 0001h
thread 13: sysvmsg 884742 type 0 bound to 0040h
thread 12: sysvmsg 851973 type 0 bound to 0020h
Result matrix:
Thread 0: 12058 7: 12058 Thread 1: 12054 8: 12055 Thread 2: 12023 9: 12023 Thread 3: 12062 10: 12062 Thread 4: 15940 11: 15940 Thread 5: 15725 12: 15726 Thread 6: 16008 13: 16008
Total: 191742
pmsg [nr queues] [timeout]
Using 8 queues/cpus (16 threads) for 5 seconds.
thread 1: sysvmsg 950273 type 1 bound to 0002h
thread 2: sysvmsg 983042 type 1 bound to 0004h
thread 3: sysvmsg 1015811 type 1 bound to 0008h thread 4: sysvmsg 1048580 type 1 bound to 0010h
thread 0: sysvmsg 917504 type 1 bound to 0001h
thread 8: sysvmsg 917504 type 0 bound to 0001h
thread 10: sysvmsg 983042 type 0 bound to 0004h
thread 9: sysvmsg 950273 type 0 bound to 0002h
thread 12: sysvmsg 1048580 type 0 bound to 0010h thread 11: sysvmsg 1015811 type 0 bound to 0008h thread 5: sysvmsg 1081349 type 1 bound to 0020h thread 6: sysvmsg 1114118 type 1 bound to 0040h thread 13: sysvmsg 1081349 type 0 bound to 0020h thread 7: sysvmsg 1146887 type 1 bound to 0080h thread 14: sysvmsg 1114118 type 0 bound to 0040h thread 15: sysvmsg 1146887 type 0 bound to 0080h Result matrix:
Thread 0: 8757 8: 8757 Thread 1: 8819 9: 8819 Thread 2: 8848 10: 8849 Thread 3: 8832 11: 8832 Thread 4: 8930 12: 8931 Thread 5: 8893 13: 8894 Thread 6: 8894 14: 8894 Thread 7: 8886 15: 8887
Total: 141722
pmsg [nr queues] [timeout]
Using 1 queues/cpus (2 threads) for 5 seconds. thread 0: sysvmsg 1507328 type 1 bound to 0001h thread 1: sysvmsg 1507328 type 0 bound to 0001h Result matrix:
Thread 0: 492748 1: 492748
Total: 985496
pmsg [nr queues] [timeout]
Using 2 queues/cpus (4 threads) for 5 seconds. thread 0: sysvmsg 1540096 type 1 bound to 0001h thread 1: sysvmsg 1572865 type 1 bound to 0002h thread 3: sysvmsg 1572865 type 0 bound to 0002h thread 2: sysvmsg 1540096 type 0 bound to 0001h Result matrix:
Thread 0: 436429 2: 436430 Thread 1: 433866 3: 433866
Total: 1740591
pmsg [nr queues] [timeout]
Using 3 queues/cpus (6 threads) for 5 seconds. thread 0: sysvmsg 1605632 type 1 bound to 0001h thread 1: sysvmsg 1638401 type 1 bound to 0002h thread 2: sysvmsg 1671170 type 1 bound to 0004h thread 5: sysvmsg 1671170 type 0 bound to 0004h thread 4: sysvmsg 1638401 type 0 bound to 0002h thread 3: sysvmsg 1605632 type 0 bound to 0001h Result matrix:
Thread 0: 388457 3: 388457 Thread 1: 384674 4: 384674 Thread 2: 390603 5: 390603
Total: 2327468
pmsg [nr queues] [timeout]
Using 4 queues/cpus (8 threads) for 5 seconds. thread 0: sysvmsg 1703936 type 1 bound to 0001h thread 1: sysvmsg 1736705 type 1 bound to 0002h thread 2: sysvmsg 1769474 type 1 bound to 0004h thread 3: sysvmsg 1802243 type 1 bound to 0008h thread 6: sysvmsg 1769474 type 0 bound to 0004h thread 5: sysvmsg 1736705 type 0 bound to 0002h thread 7: sysvmsg 1802243 type 0 bound to 0008h thread 4: sysvmsg 1703936 type 0 bound to 0001h Result matrix:
Thread 0: 307122 4: 307122 Thread 1: 308710 5: 308711 Thread 2: 307589 6: 307589 Thread 3: 309472 7: 309472
Total: 2465787
pmsg [nr queues] [timeout]
Using 5 queues/cpus (10 threads) for 5 seconds. thread 0: sysvmsg 1835008 type 1 bound to 0001h thread 1: sysvmsg 1867777 type 1 bound to 0002h thread 2: sysvmsg 1900546 type 1 bound to 0004h thread 3: sysvmsg 1933315 type 1 bound to 0008h thread 4: sysvmsg 1966084 type 1 bound to 0010h thread 7: sysvmsg 1900546 type 0 bound to 0004h thread 9: sysvmsg 1966084 type 0 bound to 0010h thread 8: sysvmsg 1933315 type 0 bound to 0008h thread 6: sysvmsg 1867777 type 0 bound to 0002h thread 5: sysvmsg 1835008 type 0 bound to 0001h Result matrix:
Thread 0: 338483 5: 338483 Thread 1: 266569 6: 266569 Thread 2: 285255 7: 285256 Thread 3: 335819 8: 335819 Thread 4: 381711 9: 381712
Total: 3215676
pmsg [nr queues] [timeout]
Using 6 queues/cpus (12 threads) for 5 seconds. thread 0: sysvmsg 1998848 type 1 bound to 0001h thread 2: sysvmsg 2064386 type 1 bound to 0004h thread 7: sysvmsg 2031617 type 0 bound to 0002h thread 3: sysvmsg 2097155 type 1 bound to 0008h thread 4: sysvmsg 2129924 type 1 bound to 0010h thread 5: sysvmsg 2162693 type 1 bound to 0020h thread 8: sysvmsg 2064386 type 0 bound to 0004h thread 1: sysvmsg 2031617 type 1 bound to 0002h thread 6: sysvmsg 1998848 type 0 bound to 0001h thread 11: sysvmsg 2162693 type 0 bound to 0020h thread 10: sysvmsg 2129924 type 0 bound to 0010h thread 9: sysvmsg 2097155 type 0 bound to 0008h Result matrix:
Thread 0: 318850 6: 318850 Thread 1: 307664 7: 307664 Thread 2: 316157 8: 316157 Thread 3: 274740 9: 274741 Thread 4: 352108 10: 352109 Thread 5: 355040 11: 355041
Total: 3849121
pmsg [nr queues] [timeout]
Using 7 queues/cpus (14 threads) for 5 seconds. thread 1: sysvmsg 2228225 type 1 bound to 0002h thread 7: sysvmsg 2195456 type 0 bound to 0001h thread 2: sysvmsg 2260994 type 1 bound to 0004h thread 3: sysvmsg 2293763 type 1 bound to 0008h thread 4: sysvmsg 2326532 type 1 bound to 0010h thread 5: sysvmsg 2359301 type 1 bound to 0020h thread 13: sysvmsg 2392070 type 0 bound to 0040h thread 9: sysvmsg 2260994 type 0 bound to 0004h thread 8: sysvmsg 2228225 type 0 bound to 0002h thread 0: sysvmsg 2195456 type 1 bound to 0001h thread 12: sysvmsg 2359301 type 0 bound to 0020h thread 6: sysvmsg 2392070 type 1 bound to 0040h thread 11: sysvmsg 2326532 type 0 bound to 0010h thread 10: sysvmsg 2293763 type 0 bound to 0008h Result matrix:
Thread 0: 311401 7: 311402 Thread 1: 255123 8: 255124 Thread 2: 311868 9: 311868 Thread 3: 299011 10: 299011 Thread 4: 280114 11: 280115 Thread 5: 314069 12: 314070 Thread 6: 333345 13: 333345
Total: 4209866
pmsg [nr queues] [timeout]
Using 8 queues/cpus (16 threads) for 5 seconds. thread 0: sysvmsg 2424832 type 1 bound to 0001h thread 1: sysvmsg 2457601 type 1 bound to 0002h thread 2: sysvmsg 2490370 type 1 bound to 0004h thread 3: sysvmsg 2523139 type 1 bound to 0008h thread 4: sysvmsg 2555908 type 1 bound to 0010h thread 5: sysvmsg 2588677 type 1 bound to 0020h thread 6: sysvmsg 2621446 type 1 bound to 0040h thread 7: sysvmsg 2654215 type 1 bound to 0080h thread 10: sysvmsg 2490370 type 0 bound to 0004h thread 13: sysvmsg 2588677 type 0 bound to 0020h thread 9: sysvmsg 2457601 type 0 bound to 0002h thread 12: sysvmsg 2555908 type 0 bound to 0010h thread 11: sysvmsg 2523139 type 0 bound to 0008h thread 8: sysvmsg 2424832 type 0 bound to 0001h thread 14: sysvmsg 2621446 type 0 bound to 0040h thread 15: sysvmsg 2654215 type 0 bound to 0080h Result matrix:
Thread 0: 234942 8: 234942 Thread 1: 262977 9: 262978 Thread 2: 294207 10: 294208 Thread 3: 288878 11: 288879 Thread 4: 273532 12: 273532 Thread 5: 248904 13: 248904 Thread 6: 260121 14: 260122 Thread 7: 264229 15: 264230
Total: 4255585
Andrew Morton
maintainerQuoted 11 lines · On Mon, 05 May 2008 18:52:50 +0200 Nadia Derbey <[email protected]> wrote:
2.6.25-mm1 (ref) 2.6.25-mm1(patched)Total (1 cpu): 876000 985496 Total (2 cpus): 1549592 1740591 Total (3 cpus): 1694370 2327468 Total (4 cpus): 404553 2465787 Total (5 cpus): 391283 3215676 Total (6 cpus): 263249 3849121 Total (7 cpus): 191742 4209866 Total (8 cpus): 141722 4255585
Looks encouraging. A comparison with 2.6.22 (or whichever kernel it was before we broke it) would be interesting too, please.
Quoted 4 lines
Full output files attached.
Will send the rest tomorrow.
Nobody reads the raw data, sorry. And it is inefficient to have everyone independently pore over the raw data extracting the (same) actual information.
Please condense the result of your performance testing into a preferably-less-than-one-page summary and include (and maintain) that within the patch changelog.