Skip to contentSkip to conversation

Scalability requirements for sysv ipc - v2

PATCH In review [email protected] 3 participants 26 messages Apr 29, 2008 – May 5, 2008

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

--

#1 lore raw

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
Index: linux-2.6.25-mm1/lib/idr.c
===================================================================
@@ -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);
 

--

maintainer
#2 lore raw

Re: [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.

---
 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?

#3 lore raw

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.

---
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

#4 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/lib/ridr.c
===================================================================
@@ -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
Index: linux-2.6.25-mm1/lib/Makefile
===================================================================
@@ -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
Index: linux-2.6.25-mm1/init/main.c
===================================================================
@@ -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(void
 	kmem_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
Index: linux-2.6.25-mm1/lib/idr.c
===================================================================
@@ -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
Index: linux-2.6.25-mm1/include/linux/idr.h
===================================================================
@@ -48,9 +48,9 @@
 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
 
 struct 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 {

--

#5 lore raw

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 -3
 struct 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
#6 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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

--

#7 lore raw

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
#8 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/lib/ridr.c
===================================================================
@@ -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);
+

--

#9 lore raw

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
#10 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/include/linux/idr.h
===================================================================
@@ -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

--

#11 lore raw

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
#12 lore raw

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        -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?

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

#13 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/lib/ridr.c
===================================================================
@@ -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)
 {

--

#14 lore raw

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
#15 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/lib/ridr.c
===================================================================
@@ -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)
 {

--

#16 lore raw

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
#17 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ridr.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/include/linux/idr.h
===================================================================
@@ -91,6 +91,7 @@ static inline void _idr_set_new_slot(str
 
 void _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
Index: linux-2.6.25-mm1/lib/idr.c
===================================================================
@@ -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

--

#18 lore raw

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
#19 lore raw

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
Index: linux-2.6.25-mm1/include/linux/ipc_namespace.h
===================================================================
@@ -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
Index: linux-2.6.25-mm1/ipc/namespace.c
===================================================================
@@ -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
Index: linux-2.6.25-mm1/ipc/shm.c
===================================================================
@@ -569,7 +569,7 @@ static void shm_get_stat(struct ipc_name
 		struct 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

--

#20 lore raw

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 ip
 	struct 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
#21 lore raw

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
Index: linux-2.6.25-mm1/ipc/util.c
===================================================================
@@ -716,56 +716,6 @@ struct kern_ipc_perm *ipc_lock(struct ip
 	return 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(st
 	int 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
Index: linux-2.6.25-mm1/ipc/util.h
===================================================================
@@ -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 ker
 	rcu_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
Index: linux-2.6.25-mm1/ipc/shm.c
===================================================================
@@ -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_str
 
 	down_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 &&

--

#22 lore raw

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
maintainer
#23 lore raw
In reply to [email protected]
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

hm, you've been busy.

As all this work is entirely for performance reasons, the changelog should have (lots of) performance testing results! Please.

#24 lore raw
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

maintainer
#25 lore raw
Quoted 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.