idr: change the idr structure
After scalability problems have been detected when using the sysV ipcs, I have
proposed to use an RCU based implementation of the IDR api instead (see
threads http://lkml.org/lkml/2008/4/11/212 and
http://lkml.org/lkml/2008/4/29/295).
This resulted in many people asking to convert the idr API and make it rcu
safe (because most of the code was duplicated and thus unmaintanable and
unreviewable).
So here is a first attempt.
The important change wrt to the idr API itself is during idr removes: idr
layers are freed after a grace period, instead of being moved to the free
list.
The important change wrt to ipcs, is that idr_find() can now be called
locklessly inside a rcu read critical section.
Here are the results I've got for the pmsg test sent by Manfred:
2.6.25-rc3-mm1 2.6.25-rc3-mm1+ 2.6.25-mm1 Patched 2.6.25-mm1
1 1168441 1064021 876000 947488
2 1094264 921059 1549592 1730685
3 2082520 1738165 1694370 2324880
4 2079929 1695521 404553 2400408
5 2898758 406566 391283 3246580
6 2921417 261275 263249 3752148
7 3308761 126056 191742 4243142
8 3329456 100129 141722 4275780
1st column: stock 2.6.25-rc3-mm1
2nd column: 2.6.25-rc3-mm1 + ipc patches (store ipcs into idrs)
3nd column: stock 2.6.25-mm1
4th column: 2.6.25-mm1 + this pacth series.
This patch:
Add an rcu_head to the idr_layer structure in order to free it after a grace
period.
Signed-off-by: Nadia Derbey <Nadia.Derbey@bull.net>
Reviewed-by: "Paul E. McKenney" <paulmck@us.ibm.com>
Cc: Manfred Spraul <manfred@colorfullife.com>
Cc: Jim Houston <jim.houston@comcast.net>
Cc: Pierre Peiffer <peifferp@gmail.com>
Acked-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 9a2d762..1af61d2 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -15,6 +15,7 @@
#include <linux/types.h>
#include <linux/bitops.h>
#include <linux/init.h>
+#include <linux/rcupdate.h>
#if BITS_PER_LONG == 32
# define IDR_BITS 5
@@ -51,6 +52,7 @@
unsigned long bitmap; /* A zero bit means "space here" */
struct idr_layer *ary[1<<IDR_BITS];
int count; /* When zero, we can release it */
+ struct rcu_head rcu_head;
};
struct idr {