From 2027d1abc25ff770cc3bc936abd33570ce85d85a Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:47:57 -0700 Subject: 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 Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/idr.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'include/linux/idr.h') diff --git a/include/linux/idr.h b/include/linux/idr.h index 9a2d762124d..1af61d23be3 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -15,6 +15,7 @@ #include #include #include +#include #if BITS_PER_LONG == 32 # define IDR_BITS 5 @@ -51,6 +52,7 @@ struct idr_layer { unsigned long bitmap; /* A zero bit means "space here" */ struct idr_layer *ary[1< Date: Fri, 25 Jul 2008 01:47:59 -0700 Subject: idr: error checking factorization Do some code factorization in the return code analysis. Signed-off-by: Nadia Derbey Cc: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/idr.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'include/linux/idr.h') diff --git a/include/linux/idr.h b/include/linux/idr.h index 1af61d23be3..762c3f2c631 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -73,6 +73,12 @@ 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_NEED_TO_GROW -2 +#define IDR_NOMORE_SPACE -3 + +#define _idr_rc_to_errno(rc) ((rc) == -1 ? -EAGAIN : -ENOSPC) + /* * This is what we export. */ -- cgit v1.2.3 From f9c46d6ea5ce138a886c3a0f10a46130afab75f5 Mon Sep 17 00:00:00 2001 From: Nadia Derbey Date: Fri, 25 Jul 2008 01:48:01 -0700 Subject: idr: make idr_find rcu-safe Make idr_find rcu-safe: it can now be called inside an rcu_read critical section. Signed-off-by: Nadia Derbey Reviewed-by: "Paul E. McKenney" Cc: Manfred Spraul Cc: Jim Houston Cc: Pierre Peiffer Acked-by: Rik van Riel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/idr.h | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'include/linux/idr.h') diff --git a/include/linux/idr.h b/include/linux/idr.h index 762c3f2c631..fa035f96f2a 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -79,6 +79,22 @@ struct idr { #define _idr_rc_to_errno(rc) ((rc) == -1 ? -EAGAIN : -ENOSPC) +/** + * idr synchronization (stolen from radix-tree.h) + * + * idr_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 idr tree *and* a synchronize_rcu() grace + * period). + */ + /* * This is what we export. */ -- cgit v1.2.3