Skip to contentSkip to conversation

an IPC implementation based on Linux radix trees

RFC PATCH In review [email protected] 2 participants 10 messages Jun 7, 2007 – Jun 8, 2007

lore
Share & tools
lore
#0 lore raw

cover an IPC implementation based on Linux radix trees

--

A couple of months ago, I dropped a series of patches that introduced the AKT framework (Automatic Kernel Tunables).

(see thread http://lkml.org/lkml/2007/1/16/16)

When reading the patches people complained that I was trying to treat a symptom, not the problem itself, and that it'd be better try to rewrite things where necessary (better data structures / implementations).

(see http://lkml.org/lkml/2007/2/7/248)

I'm trying to achieve this for the IPC case, with this new series of patches:
a new ipc implementation based on the Linux radix tree API is proposed.

In the current ipc implementation, the ipc structures pointers are stored in an array that is resized each time the corresponding tunable is changed (resized means that a new array is allocated with the new size, the old one is copied into that new array and the old array is de-allocated).

With this new implementation, there is no need for the array resizing since the size change becomes "natural".

I'll try to come up in the near future, with ipc max values that scale better to memory size: that way, the ipc tunables msgmni, semmni and shmmni should become actual DoS limits.

These patches should be applied to 2.6.21, in the following order:

[PATCH 1/6]: ipc_radix_tree.patch
[PATCH 2/6]: ipc_rmid.patch
[PATCH 3/6]: ipc_gang_lookups.patch
[PATCH 4/6]: ipc_lock_and_check.patch
[PATCH 5/6]: ipcid_to_idx.patch
[PATCH 6/6]: ipc_findkey.patch

Regards,
Nadia

#1 lore raw

RFC PATCH 1/6 Storing ipcs into radix trees

[PATCH 01/06]

This patch introduces ipcs storage into radix trees. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root radix_tree structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, due to radix trees introduction

---
 include/linux/ipc.h |    1 
 include/linux/msg.h |    1 
 include/linux/sem.h |    1 
 include/linux/shm.h |    1 
 ipc/msg.c           |   64 ++++++-------
 ipc/sem.c           |   63 ++++++------
 ipc/shm.c           |   63 ++++++------
 ipc/util.c          |  253 ++++++++++++++++++++++++++++------------------------
 ipc/util.h          |   30 +-----
 9 files changed, 248 insertions(+), 229 deletions(-)
ipc/util.h +8 -22
Index: linux-2.6.21/ipc/util.h
===================================================================
@@ -13,6 +13,8 @@
 #define USHRT_MAX 0xffff
 #define SEQ_MULTIPLIER	(IPCMNI)
 
+#define IPCS_MAX_SCAN_ENTRIES 256
+
 void sem_init (void);
 void msg_init (void);
 void shm_init (void);
@@ -25,19 +27,15 @@ void sem_exit_ns(struct ipc_namespace *n
 void msg_exit_ns(struct ipc_namespace *ns);
 void shm_exit_ns(struct ipc_namespace *ns);
 
-struct ipc_id_ary {
-	int size;
-	struct kern_ipc_perm *p[0];
-};
-
 struct ipc_ids {
 	int in_use;
 	int max_id;
+	int first_free;
 	unsigned short seq;
 	unsigned short seq_max;
 	struct mutex mutex;
-	struct ipc_id_ary nullentry;
-	struct ipc_id_ary* entries;
+	struct radix_tree_root id_tree;
+	DECLARE_BITMAP(in_use_bitmap, IPCMNI);
 };
 
 struct seq_file;
@@ -46,7 +44,7 @@ struct seq_file;
 #else
 #define __ipc_init	__init
 #endif
-void __ipc_init ipc_init_ids(struct ipc_ids *ids, int size);
+void __ipc_init ipc_init_ids(struct ipc_ids *);
 #ifdef CONFIG_PROC_FS
 void __init ipc_init_proc_interface(const char *path, const char *header,
 		int ids, int (*show)(struct seq_file *, void *));
@@ -59,8 +57,8 @@ void __init ipc_init_proc_interface(cons
 #define IPC_SHM_IDS	2
 
 /* must be called with ids->mutex acquired.*/
-int ipc_findkey(struct ipc_ids* ids, key_t key);
-int ipc_addid(struct ipc_ids* ids, struct kern_ipc_perm* new, int size);
+struct kern_ipc_perm *ipc_findkey(struct ipc_ids *, key_t);
+int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
 
 /* must be called with both locks acquired. */
 struct kern_ipc_perm* ipc_rmid(struct ipc_ids* ids, int id);
@@ -83,18 +81,6 @@ void* ipc_rcu_alloc(int size);
 void ipc_rcu_getref(void *ptr);
 void ipc_rcu_putref(void *ptr);
 
-static inline void __ipc_fini_ids(struct ipc_ids *ids,
-		struct ipc_id_ary *entries)
-{
-	if (entries != &ids->nullentry)
-		ipc_rcu_putref(entries);
-}
-
-static inline void ipc_fini_ids(struct ipc_ids *ids)
-{
-	__ipc_fini_ids(ids, ids->entries);
-}
-
 struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id);
 struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id);
 void ipc_lock_by_ptr(struct kern_ipc_perm *ipcp);
ipc/util.c +139 -114

396 lines not on this page · raw message

ipc/msg.c +34 -30

127 lines not on this page · raw message

ipc/sem.c +33 -30

133 lines not on this page · raw message

ipc/shm.c +33 -30

123 lines not on this page · raw message

include/linux/ipc.h +1 -0
Index: linux-2.6.21/include/linux/ipc.h
===================================================================
@@ -60,6 +60,7 @@ struct kern_ipc_perm
 {
 	spinlock_t	lock;
 	int		deleted;
+	int		id;
 	key_t		key;
 	uid_t		uid;
 	gid_t		gid;
include/linux/sem.h +0 -1
Index: linux-2.6.21/include/linux/sem.h
===================================================================
@@ -90,7 +90,6 @@ struct sem {
 /* One sem_array data structure for each set of semaphores in the system. */
 struct sem_array {
 	struct kern_ipc_perm	sem_perm;	/* permissions .. see ipc.h */
-	int			sem_id;
 	time_t			sem_otime;	/* last semop time */
 	time_t			sem_ctime;	/* last change time */
 	struct sem		*sem_base;	/* ptr to first semaphore in array */
include/linux/shm.h +0 -1
Index: linux-2.6.21/include/linux/shm.h
===================================================================
@@ -77,7 +77,6 @@ struct shmid_kernel /* private to the ke
 {	
 	struct kern_ipc_perm	shm_perm;
 	struct file *		shm_file;
-	int			id;
 	unsigned long		shm_nattch;
 	unsigned long		shm_segsz;
 	time_t			shm_atim;
include/linux/msg.h +0 -1
Index: linux-2.6.21/include/linux/msg.h
===================================================================
@@ -77,7 +77,6 @@ struct msg_msg {
 /* one msq_queue structure for each present queue on the system */
 struct msg_queue {
 	struct kern_ipc_perm q_perm;
-	int q_id;
 	time_t q_stime;			/* last msgsnd time */
 	time_t q_rtime;			/* last msgrcv time */
 	time_t q_ctime;			/* last change time */

--

#2 lore raw

Re: [RFC][PATCH 1/6] Storing ipcs into radix trees

Hi Nadia,

good to see someone is pounding this old beast again :-)

ipc/util.h line 16

Quoted 9 lines · On Thursday 07 June 2007, [email protected] wrote:

Index: linux-2.6.21/ipc/util.h
===================================================================

ipc/util.h +1 -0
@@ -13,6 +13,8 @@
 #define USHRT_MAX 0xffff
 #define SEQ_MULTIPLIER	(IPCMNI)
 
+#define IPCS_MAX_SCAN_ENTRIES 256

That ...

Quoted 12 lines

Index: linux-2.6.21/ipc/util.c
===================================================================

ipc/util.c +3 -1
@@ -252,72 +241,94 @@ void __init ipc_init_proc_interface(cons
  *	@key: The key to find
  *	
  *	Requires ipc_ids.mutex locked.
- *	Returns the identifier if found or -1 if not.
+ *	Returns the LOCKED pointer to the ipc structure if found or NULL
+ *	if not.
+ *      If key is found ipc contains its ipc structure

ipc/util.c void __init ipc_init_proc_interface(cons · line 252

Quoted 10 lines
ipc/util.c +3 -4
  */
 
-int ipc_findkey(struct ipc_ids* ids, key_t key)
+struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key)
 {
-	int id;
-	struct kern_ipc_perm* p;
-	int max_id = ids->max_id;
+	struct kern_ipc_perm *ipc;
+	struct kern_ipc_perm *ipcs[IPCS_MAX_SCAN_ENTRIES];

... together with this means 4*256 -> 1k of precious stack space used. Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that.

Same problem with your third patch called
"Changing the loops on a single ipcid into radix_tree_gang_lookup() calls"

If you cannot sleep, try to lower that constant (e.g. 16-32). The current users use much smaller numbers.

If you can sleep and performance goes down after lowering that constant, try to kmalloc these arrays (since kmalloc() of that small amount should succeed easily).

Regards

Ingo Oeser

#3 lore raw

Re: [RFC][PATCH 1/6] Storing ipcs into radix trees

Quoted 51 lines · Ingo Oeser

Hi Nadia,

good to see someone is pounding this old beast again :-)

ipc/util.h line 16

Quoted 9 lines · On Thursday 07 June 2007, [email protected] wrote:

Index: linux-2.6.21/ipc/util.h
===================================================================

ipc/util.h +1 -0
@@ -13,6 +13,8 @@
 #define USHRT_MAX 0xffff
 #define SEQ_MULTIPLIER	(IPCMNI)
 
+#define IPCS_MAX_SCAN_ENTRIES 256

That ...

Quoted 12 lines

Index: linux-2.6.21/ipc/util.c
===================================================================

ipc/util.c +3 -1
@@ -252,72 +241,94 @@ void __init ipc_init_proc_interface(cons
 *	@key: The key to find
 *	
 *	Requires ipc_ids.mutex locked.
- *	Returns the identifier if found or -1 if not.
+ *	Returns the LOCKED pointer to the ipc structure if found or NULL
+ *	if not.
+ *      If key is found ipc contains its ipc structure

ipc/util.c void __init ipc_init_proc_interface(cons · line 252

Quoted 10 lines
ipc/util.c +3 -4
 */
 
-int ipc_findkey(struct ipc_ids* ids, key_t key)
+struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key)
 {
-	int id;
-	struct kern_ipc_perm* p;
-	int max_id = ids->max_id;
+	struct kern_ipc_perm *ipc;
+	struct kern_ipc_perm *ipcs[IPCS_MAX_SCAN_ENTRIES];

... together with this means 4*256 -> 1k of precious stack space used. Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that.

Same problem with your third patch called "Changing the loops on a single ipcid into radix_tree_gang_lookup() calls"

If you cannot sleep, try to lower that constant (e.g. 16-32). The current users use much smaller numbers.

Quoted 9 lines

If you can sleep and performance goes down after lowering that constant, try to kmalloc these arrays (since kmalloc() of that small amount should succeed easily).

Regards

Ingo Oeser

Ingo,

You're completely right, but trying to lower the extraction size, I'm afraid this will have an impact on performances.

Here are the results of a small test I did: I have run ctxbench on both the 256 and and 16 entries versions

1) 256 entries:

[root@akt ctxbench-1.9]# echo 1000 > /proc/sys/kernel/msgmni [root@akt ctxbench-1.9]# ./ctx -m -t300

Context switching benchmark v1.17
Using message queue for IPC control
Max iterations: 0 (zero = no limit)
Max runtime (sec): 300 (zero = no limit)
42523679 itterations in 300.005423 seconds = 141743/sec

2) 16 entries:

[root@akt ctxbench-1.9]# echo 1000 > /proc/sys/kernel/msgmni [root@akt ctxbench-1.9]# ./ctx -m -t300

Context switching benchmark v1.17
Using message queue for IPC control
Max iterations: 0 (zero = no limit)
Max runtime (sec): 300 (zero = no limit)
41774255 itterations in 300.005334 seconds = 139245/sec

Will try with a dynamic allocation.

Regards,
Nadia

#4 lore raw

Re: [RFC][PATCH 1/6] Storing ipcs into radix trees

Hi,

Quoted 6 lines · Nadia Derbey
Quoted 2 lines · Ingo Oeser

... together with this means 4*256 -> 1k of precious stack space used. Please consider either lowering IPCS_MAX_SCAN_ENTRIES or kmalloc() that.

You're completely right, but trying to lower the extraction size, I'm afraid this will have an impact on performances.

Quoted 7 lines

Here are the results of a small test I did: I have run ctxbench on both the 256 and and 16 entries versions

1) 256 entries:
42523679 itterations in 300.005423 seconds = 141743/sec
2) 16 entries:
41774255 itterations in 300.005334 seconds = 139245/sec

So that is around 1.8% in a benchmark.

Not bad, if one considers, that this is an expensive syncronisation primitive anyway (and thus shouldn't dominate any real workload). At least _much_ better than possible stack underflow :-)

BTW: You forgot to include measurements with the unmodified code
as it is in Linus' tree now. They woule be a nice data point here.

Quoted 1 line

Will try with a dynamic allocation.

But than you have an additional error path
or have to sleep until memory becomes available.

Maybe try doubling IPCS_MAX_SCAN_ENTRIES - until the performance impact is in the noise - is simpler. Up to 64 seems acceptable.

Best Regards

Ingo Oeser

#5 lore raw

RFC PATCH 2/6 Changing ipc_rmid() interface

In reply to [email protected]

[PATCH 02/06]

This patch introduces the change to ipc_rmid() routine interface:
. there is no need for this routine to return the pointer passed in as
argument: it is now declared as a void
. since the id is now part of the kern_ipc_perm structure, no need to
have it as an argument to the routine

---
 ipc/msg.c  |   16 ++++++++++------
 ipc/sem.c  |   16 ++++++++++------
 ipc/shm.c  |    6 +++---
 ipc/util.c |   15 +++++++--------
 ipc/util.h |    2 +-
 5 files changed, 31 insertions(+), 24 deletions(-)
ipc/util.h +1 -1
Index: linux-2.6.21/ipc/util.h
===================================================================
@@ -61,7 +61,7 @@ struct kern_ipc_perm *ipc_findkey(struct
 int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
 
 /* must be called with both locks acquired. */
-struct kern_ipc_perm* ipc_rmid(struct ipc_ids* ids, int id);
+void ipc_rmid(struct ipc_ids *, struct kern_ipc_perm *);
 
 int ipcperms (struct kern_ipc_perm *ipcp, short flg);
 
ipc/util.c +7 -8
Index: linux-2.6.21/ipc/util.c
===================================================================
@@ -384,20 +384,19 @@ int ipc_addid(struct ipc_ids* ids, struc
 /**
  *	ipc_rmid	-	remove an IPC identifier
  *	@ids: identifier set
- *	@id: Identifier to remove
+ *	@id: ipc perm structure containing the identifier to remove
  *
  *	The identifier must be valid, and in use. The kernel will panic if
  *	fed an invalid identifier. The entry is removed and internal
- *	variables recomputed. The object associated with the identifier
- *	is returned.
- *	ipc_ids.mutex and the spinlock for this ID is hold before this function
+ *	variables recomputed.
+ *	ipc_ids.mutex and the spinlock for this ID is held before this function
  *	is called, and remain locked on the exit.
  */
  
-struct kern_ipc_perm* ipc_rmid(struct ipc_ids* ids, int id)
+void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 {
 	struct kern_ipc_perm* p;
-	int lid = id % SEQ_MULTIPLIER;
+	int lid = ipcp->id % SEQ_MULTIPLIER;
 	BUG_ON(lid > ids->max_id);
 
 	/* 
@@ -405,7 +404,7 @@ struct kern_ipc_perm* ipc_rmid(struct ip
 	 * on Alpha, since the ipc_ids.mutex is held.
 	 */	
 	p = radix_tree_delete(&ids->id_tree, lid);
-	BUG_ON(p == NULL);
+	BUG_ON(p == NULL || p != ipcp);
 
 	BUG_ON(ids->in_use <= 0);
 	ids->in_use--;
@@ -419,7 +418,7 @@ struct kern_ipc_perm* ipc_rmid(struct ip
 
 	p->deleted = 1;
 
-	return p;
+	return;
 }
 
 /**
ipc/msg.c +10 -6
Index: linux-2.6.21/ipc/msg.c
===================================================================
@@ -75,13 +75,12 @@ static struct ipc_ids init_msg_ids;
 
 #define msg_lock(ns, id)	((struct msg_queue*)ipc_lock(&msg_ids(ns), id))
 #define msg_unlock(msq)		ipc_unlock(&(msq)->q_perm)
-#define msg_rmid(ns, id)	((struct msg_queue*)ipc_rmid(&msg_ids(ns), id))
 #define msg_checkid(ns, msq, msgid)	\
 	ipc_checkid(&msg_ids(ns), &msq->q_perm, msgid)
 #define msg_buildid(ns, id, seq) \
 	ipc_buildid(&msg_ids(ns), id, seq)
 
-static void freeque (struct ipc_namespace *ns, struct msg_queue *msq, int id);
+static void freeque(struct ipc_namespace *, struct msg_queue *);
 static int newque (struct ipc_namespace *ns, key_t key, int msgflg);
 #ifdef CONFIG_PROC_FS
 static int sysvipc_msg_proc_show(struct seq_file *s, void *it);
@@ -120,7 +119,7 @@ void msg_exit_ns(struct ipc_namespace *n
 		if (msq == NULL)
 			continue;
 
-		freeque(ns, msq, i);
+		freeque(ns, msq);
 	}
 	mutex_unlock(&msg_ids(ns).mutex);
 
@@ -137,6 +136,11 @@ void __init msg_init(void)
 				IPC_MSG_IDS, sysvipc_msg_proc_show);
 }
 
+static inline void msg_rmid(struct ipc_namespace *ns, struct msg_queue *s)
+{
+	ipc_rmid(&msg_ids(ns), &s->q_perm);
+}
+
 static int newque (struct ipc_namespace *ns, key_t key, int msgflg)
 {
 	struct msg_queue *msq;
@@ -231,13 +235,13 @@ static void expunge_all(struct msg_queue
  * msg_ids.mutex and the spinlock for this message queue are held
  * before freeque() is called. msg_ids.mutex remains locked on exit.
  */
-static void freeque(struct ipc_namespace *ns, struct msg_queue *msq, int id)
+static void freeque(struct ipc_namespace *ns, struct msg_queue *msq)
 {
 	struct list_head *tmp;
 
 	expunge_all(msq, -EIDRM);
 	ss_wakeup(&msq->q_senders, 1);
-	msq = msg_rmid(ns, id);
+	msg_rmid(ns, msq);
 	msg_unlock(msq);
 
 	tmp = msq->q_messages.next;
@@ -558,7 +562,7 @@ asmlinkage long sys_msgctl(int msqid, in
 		break;
 	}
 	case IPC_RMID:
-		freeque(ns, msq, msqid);
+		freeque(ns, msq);
 		break;
 	}
 	err = 0;
ipc/sem.c +10 -6
Index: linux-2.6.21/ipc/sem.c
===================================================================
@@ -91,7 +91,6 @@
 
 #define sem_lock(ns, id)	((struct sem_array*)ipc_lock(&sem_ids(ns), id))
 #define sem_unlock(sma)		ipc_unlock(&(sma)->sem_perm)
-#define sem_rmid(ns, id)	((struct sem_array*)ipc_rmid(&sem_ids(ns), id))
 #define sem_checkid(ns, sma, semid)	\
 	ipc_checkid(&sem_ids(ns),&sma->sem_perm,semid)
 #define sem_buildid(ns, id, seq) \
@@ -100,7 +99,7 @@
 static struct ipc_ids init_sem_ids;
 
 static int newary(struct ipc_namespace *, key_t, int, int);
-static void freeary(struct ipc_namespace *ns, struct sem_array *sma, int id);
+static void freeary(struct ipc_namespace *, struct sem_array *);
 #ifdef CONFIG_PROC_FS
 static int sysvipc_sem_proc_show(struct seq_file *s, void *it);
 #endif
@@ -157,7 +156,7 @@ void sem_exit_ns(struct ipc_namespace *n
 		if (sma == NULL)
 			continue;
 
-		freeary(ns, sma, i);
+		freeary(ns, sma);
 	}
 	mutex_unlock(&sem_ids(ns).mutex);
 
@@ -174,6 +173,11 @@ void __init sem_init (void)
 				IPC_SEM_IDS, sysvipc_sem_proc_show);
 }
 
+static inline void sem_rmid(struct ipc_namespace *ns, struct sem_array *s)
+{
+	ipc_rmid(&sem_ids(ns), &s->sem_perm);
+}
+
 /*
  * Lockless wakeup algorithm:
  * Without the check/retry algorithm a lockless wakeup is possible:
@@ -499,7 +503,7 @@ static int count_semzcnt (struct sem_arr
  * the spinlock for this semaphore set hold. sem_ids.mutex remains locked
  * on exit.
  */
-static void freeary (struct ipc_namespace *ns, struct sem_array *sma, int id)
+static void freeary(struct ipc_namespace *ns, struct sem_array *sma)
 {
 	struct sem_undo *un;
 	struct sem_queue *q;
@@ -526,7 +530,7 @@ static void freeary (struct ipc_namespac
 	}
 
 	/* Remove the semaphore set from the ID radix tree */
-	sma = sem_rmid(ns, id);
+	sem_rmid(ns, sma);
 	sem_unlock(sma);
 
 	ns->used_sems -= sma->sem_nsems;
@@ -900,7 +904,7 @@ static int semctl_down(struct ipc_namesp
 
 	switch(cmd){
 	case IPC_RMID:
-		freeary(ns, sma, semid);
+		freeary(ns, sma);
 		err = 0;
 		break;
 	case IPC_SET:
ipc/shm.c +3 -3
Index: linux-2.6.21/ipc/shm.c
===================================================================
@@ -147,9 +147,9 @@ static inline int shm_checkid(struct ipc
 	return 0;
 }
 
-static inline struct shmid_kernel *shm_rmid(struct ipc_namespace *ns, int id)
+static inline void shm_rmid(struct ipc_namespace *ns, struct shmid_kernel *s)
 {
-	return (struct shmid_kernel *)ipc_rmid(&shm_ids(ns), id);
+	ipc_rmid(&shm_ids(ns), &s->shm_perm);
 }
 
 static inline int shm_addid(struct ipc_namespace *ns, struct shmid_kernel *shp)
@@ -185,7 +185,7 @@ static void shm_open(struct vm_area_stru
 static void shm_destroy(struct ipc_namespace *ns, struct shmid_kernel *shp)
 {
 	ns->shm_tot -= (shp->shm_segsz + PAGE_SIZE - 1) >> PAGE_SHIFT;
-	shm_rmid(ns, shp->shm_perm.id);
+	shm_rmid(ns, shp);
 	shm_unlock(shp);
 	if (!is_file_hugepages(shp->shm_file))
 		shmem_lock(shp->shm_file, 0, shp->mlock_user);

--

#6 lore raw

RFC PATCH 3/6 Changing the loops on a single ipcid into radix_tree_gang_lookup() calls

In reply to [email protected]

[PATCH 03/06]

This patch introduces the changes to the routines like *_exit_ns():
. instead of looping on each id, trying to lock it and do the job if the
id exists, they now call radix_tree_gang_lookup(): we are sure all the returned ipc structures exist, so we directly can do the job.

---
 ipc/msg.c  |   24 ++++++++++++++---
 ipc/sem.c  |   25 ++++++++++++++----
 ipc/shm.c  |   82 +++++++++++++++++++++++++++++++++++++++++--------------------
 ipc/util.c |   21 ---------------
 ipc/util.h |    1 
 5 files changed, 95 insertions(+), 58 deletions(-)
ipc/msg.c +19 -5
Index: linux-2.6.21/ipc/msg.c
===================================================================
@@ -112,14 +112,28 @@ void msg_exit_ns(struct ipc_namespace *n
 {
 	int i;
 	struct msg_queue *msq;
+	struct msg_queue *msqs[IPCS_MAX_SCAN_ENTRIES];
+	int nb_msqs, next_id;
+	int total, in_use;
 
 	mutex_lock(&msg_ids(ns).mutex);
-	for (i = 0; i <= msg_ids(ns).max_id; i++) {
-		msq = msg_lock(ns, i);
-		if (msq == NULL)
-			continue;
 
-		freeque(ns, msq);
+	in_use = msg_ids(ns).in_use;
+
+	next_id = 0;
+	for (total = 0; total < in_use; total += nb_msqs) {
+		nb_msqs = radix_tree_gang_lookup(&(msg_ids(ns).id_tree),
+			(void **) msqs, next_id, IPCS_MAX_SCAN_ENTRIES);
+		if (nb_msqs <= 0)
+			break;
+		for (i = 0; i < nb_msqs; i++) {
+			msq = msqs[i];
+			ipc_lock_by_ptr(&msq->q_perm);
+			freeque(ns, msq);
+		}
+
+		/* prepare for next id gang lookup */
+		next_id = (msqs[nb_msqs - 1]->q_perm.id % SEQ_MULTIPLIER) + 1;
 	}
 	mutex_unlock(&msg_ids(ns).mutex);
 
ipc/sem.c +20 -5
Index: linux-2.6.21/ipc/sem.c
===================================================================
@@ -149,14 +149,29 @@ void sem_exit_ns(struct ipc_namespace *n
 {
 	int i;
 	struct sem_array *sma;
+	struct sem_array *smas[IPCS_MAX_SCAN_ENTRIES];
+	int nb_smas, next_id;
+	int total, in_use;
 
 	mutex_lock(&sem_ids(ns).mutex);
-	for (i = 0; i <= sem_ids(ns).max_id; i++) {
-		sma = sem_lock(ns, i);
-		if (sma == NULL)
-			continue;
 
-		freeary(ns, sma);
+	in_use = sem_ids(ns).in_use;
+
+	next_id = 0;
+	for (total = 0; total < in_use; total += nb_smas) {
+		nb_smas = radix_tree_gang_lookup(&(sem_ids(ns).id_tree),
+			(void **) smas, next_id, IPCS_MAX_SCAN_ENTRIES);
+		if (nb_smas <= 0)
+			break;
+		for (i = 0; i < nb_smas; i++) {
+			sma = smas[i];
+			ipc_lock_by_ptr(&sma->sem_perm);
+			freeary(ns, sma);
+		}
+
+		/* prepare for next id gang lookup */
+		next_id = (smas[nb_smas - 1]->sem_perm.id % SEQ_MULTIPLIER)
+				+ 1;
 	}
 	mutex_unlock(&sem_ids(ns).mutex);
 
ipc/shm.c +56 -26

108 lines not on this page · raw message

ipc/util.c +0 -21
Index: linux-2.6.21/ipc/util.c
===================================================================
@@ -667,27 +667,6 @@ void ipc64_perm_to_ipc_perm (struct ipc6
 	out->seq	= in->seq;
 }
 
-/*
- * So far only shm_get_stat() calls ipc_get() via shm_get(), so ipc_get()
- * is called with shm_ids.mutex locked.  Since grow_ary() is also called with
- * shm_ids.mutex down(for Shared Memory), there is no need to add read
- * barriers here to gurantee the writes in grow_ary() are seen in order 
- * here (for Alpha).
- *
- * However ipc_get() itself does not necessary require ipc_ids.mutex down. So
- * if in the future ipc_get() is used by other places without ipc_ids.mutex
- * down, then ipc_get() needs read memery barriers as ipc_lock() does.
- */
-struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id)
-{
-	struct kern_ipc_perm* out;
-	int lid = id % SEQ_MULTIPLIER;
-	if (lid > ids->max_id)
-		return NULL;
-	out = radix_tree_lookup(&ids->id_tree, lid);
-	return out;
-}
-
 struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id)
 {
 	struct kern_ipc_perm* out;
ipc/util.h +0 -1
Index: linux-2.6.21/ipc/util.h
===================================================================
@@ -81,7 +81,6 @@ void* ipc_rcu_alloc(int size);
 void ipc_rcu_getref(void *ptr);
 void ipc_rcu_putref(void *ptr);
 
-struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id);
 struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id);
 void ipc_lock_by_ptr(struct kern_ipc_perm *ipcp);
 void ipc_unlock(struct kern_ipc_perm* perm);

--

#7 lore raw

RFC PATCH 4/6 Integrating ipc_checkid() into ipc_lock()

In reply to [email protected]

[PATCH 04/06]

This patch introduces the a change to the ipc_lock() routine interface:
. each time ipc_checkid() is called, this done after calling ipc_lock().
So a new paramameter is added to ipc_lock(). It tells whether or not a ipc_checkid() is needed, and ipc_checkid() is now called from inside ipc_lock().

---
 ipc/msg.c  |   65 ++++++++++++++++++-------------------------
 ipc/sem.c  |   74 ++++++++++++++++++++-----------------------------
 ipc/shm.c  |   92 ++++++++++++++++++++++++++++++-------------------------------
 ipc/util.c |   16 +++++++---
 ipc/util.h |    6 ++-
 5 files changed, 121 insertions(+), 132 deletions(-)
ipc/util.c +12 -4
Index: linux-2.6.21/ipc/util.c
===================================================================
@@ -667,7 +667,7 @@ void ipc64_perm_to_ipc_perm (struct ipc6
 	out->seq	= in->seq;
 }
 
-struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id)
+struct kern_ipc_perm *ipc_lock(struct ipc_ids *ids, int id, int checkid)
 {
 	struct kern_ipc_perm* out;
 	int lid = id % SEQ_MULTIPLIER;
@@ -675,12 +675,12 @@ struct kern_ipc_perm* ipc_lock(struct ip
 	rcu_read_lock();
 	if (lid > ids->max_id) {
 		rcu_read_unlock();
-		return NULL;
+		return ERR_PTR(-EINVAL);
 	}
 	out = radix_tree_lookup(&ids->id_tree, lid);
 	if(out == NULL) {
 		rcu_read_unlock();
-		return NULL;
+		return ERR_PTR(-EINVAL);
 	}
 	spin_lock(&out->lock);
 	
@@ -690,8 +690,16 @@ struct kern_ipc_perm* ipc_lock(struct ip
 	if (out->deleted) {
 		spin_unlock(&out->lock);
 		rcu_read_unlock();
-		return NULL;
+		return ERR_PTR(-EINVAL);
 	}
+
+	if (checkid)
+		if (ipc_checkid(ids, out, id)) {
+			spin_unlock(&out->lock);
+			rcu_read_unlock();
+			return ERR_PTR(-EIDRM);
+		}
+
 	return out;
 }
 
ipc/util.h +4 -2
Index: linux-2.6.21/ipc/util.h
===================================================================
@@ -12,9 +12,11 @@
 
 #define USHRT_MAX 0xffff
 #define SEQ_MULTIPLIER	(IPCMNI)
-
 #define IPCS_MAX_SCAN_ENTRIES 256
 
+#define IPC_CHECKID 1
+#define NO_IPC_CHECKID 0
+
 void sem_init (void);
 void msg_init (void);
 void shm_init (void);
@@ -81,7 +83,7 @@ void* ipc_rcu_alloc(int size);
 void ipc_rcu_getref(void *ptr);
 void ipc_rcu_putref(void *ptr);
 
-struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id);
+struct kern_ipc_perm *ipc_lock(struct ipc_ids *, int, int);
 void ipc_lock_by_ptr(struct kern_ipc_perm *ipcp);
 void ipc_unlock(struct kern_ipc_perm* perm);
 int ipc_buildid(struct ipc_ids* ids, int id, int seq);
ipc/msg.c +28 -37

119 lines not on this page · raw message

ipc/sem.c +31 -43

140 lines not on this page · raw message

ipc/shm.c +46 -46

172 lines not on this page · raw message

--

#8 lore raw

RFC PATCH 5/6 Introducing the ipcid_to_idx macro

In reply to [email protected]

[PATCH 05/06]

This is a trivial patch that changes all the (id % SEQ_MULTIPLIER) into a call to the ipcid_to_idx(id) macro.

---
 ipc/msg.c  |    2 +-
 ipc/sem.c  |    3 +--
 ipc/shm.c  |    6 ++----
 ipc/util.c |   10 +++++-----
 ipc/util.h |    2 ++
 5 files changed, 11 insertions(+), 12 deletions(-)
ipc/util.h +2 -0
Index: linux-2.6.21/ipc/util.h
===================================================================
@@ -58,6 +58,8 @@ void __init ipc_init_proc_interface(cons
 #define IPC_MSG_IDS	1
 #define IPC_SHM_IDS	2
 
+#define ipcid_to_idx(id) ((id) % SEQ_MULTIPLIER)
+
 /* must be called with ids->mutex acquired.*/
 struct kern_ipc_perm *ipc_findkey(struct ipc_ids *, key_t);
 int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
ipc/util.c +5 -5
Index: linux-2.6.21/ipc/util.c
===================================================================
@@ -270,7 +270,7 @@ struct kern_ipc_perm *ipc_findkey(struct
 		}
 
 		/* prepare for next id gang lookup */
-		next_id = (ipcs[nb_ipcs - 1]->id % SEQ_MULTIPLIER) + 1;
+		next_id = ipcid_to_idx(ipcs[nb_ipcs - 1]->id) + 1;
 	}
 
 	return NULL;
@@ -396,7 +396,7 @@ int ipc_addid(struct ipc_ids* ids, struc
 void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 {
 	struct kern_ipc_perm* p;
-	int lid = ipcp->id % SEQ_MULTIPLIER;
+	int lid = ipcid_to_idx(ipcp->id);
 	BUG_ON(lid > ids->max_id);
 
 	/* 
@@ -670,7 +670,7 @@ void ipc64_perm_to_ipc_perm (struct ipc6
 struct kern_ipc_perm *ipc_lock(struct ipc_ids *ids, int id, int checkid)
 {
 	struct kern_ipc_perm* out;
-	int lid = id % SEQ_MULTIPLIER;
+	int lid = ipcid_to_idx(id);
 
 	rcu_read_lock();
 	if (lid > ids->max_id) {
@@ -781,7 +781,7 @@ static void *sysvipc_proc_next(struct se
 
 	ipc = ipcs[0];
 	ipc_lock_by_ptr(ipc);
-	*pos = (ipc->id % SEQ_MULTIPLIER) + 1;
+	*pos = ipcid_to_idx(ipc->id) + 1;
 
 	return ipc;
 }
@@ -823,7 +823,7 @@ static void *sysvipc_proc_start(struct s
 
 	ipc = ipcs[0];
 	ipc_lock_by_ptr(ipc);
-	*pos = (ipc->id % SEQ_MULTIPLIER) + 1;
+	*pos = ipcid_to_idx(ipc->id) + 1;
 
 	return ipc;
 }
ipc/msg.c +1 -1
Index: linux-2.6.21/ipc/msg.c
===================================================================
@@ -130,7 +130,7 @@ void msg_exit_ns(struct ipc_namespace *n
 		}
 
 		/* prepare for next id gang lookup */
-		next_id = (msqs[nb_msqs - 1]->q_perm.id % SEQ_MULTIPLIER) + 1;
+		next_id = ipcid_to_idx(msqs[nb_msqs - 1]->q_perm.id) + 1;
 	}
 	mutex_unlock(&msg_ids(ns).mutex);
 
ipc/sem.c +1 -2
Index: linux-2.6.21/ipc/sem.c
===================================================================
@@ -169,8 +169,7 @@ void sem_exit_ns(struct ipc_namespace *n
 		}
 
 		/* prepare for next id gang lookup */
-		next_id = (smas[nb_smas - 1]->sem_perm.id % SEQ_MULTIPLIER)
-				+ 1;
+		next_id = ipcid_to_idx(smas[nb_smas - 1]->sem_perm.id) + 1;
 	}
 	mutex_unlock(&sem_ids(ns).mutex);
 
ipc/shm.c +2 -4
Index: linux-2.6.21/ipc/shm.c
===================================================================
@@ -132,8 +132,7 @@ void shm_exit_ns(struct ipc_namespace *n
 		}
 
 		/* prepare for next id gang lookup */
-		next_id = (shps[nb_shps - 1]->shm_perm.id % SEQ_MULTIPLIER)
-				+ 1;
+		next_id = ipcid_to_idx(shps[nb_shps - 1]->shm_perm.id) + 1;
 	}
 	mutex_unlock(&shm_ids(ns).mutex);
 
@@ -596,8 +595,7 @@ static void shm_get_stat(struct ipc_name
 		}
 
 		/* prepare for next id gang lookup */
-		next_id = (shps[nb_shps - 1]->shm_perm.id % SEQ_MULTIPLIER)
-				+ 1;
+		next_id = ipcid_to_idx(shps[nb_shps - 1]->shm_perm.id) + 1;
 	}
 }
 

--

#9 lore raw

RFC PATCH 6/6 Introducing msg_findkey() sem_findkey() and shm_findkey()

In reply to [email protected]

[PATCH 06/06]

This is a trivial patch that changes all the calls to casted ipc_findkey() into calls to static inline routines that do the cast themselves.

---
 ipc/msg.c |    8 +++++++-
 ipc/sem.c |    8 +++++++-
 ipc/shm.c |    8 +++++++-
 3 files changed, 21 insertions(+), 3 deletions(-)
ipc/msg.c +7 -1
Index: linux-2.6.21/ipc/msg.c
===================================================================
@@ -153,6 +153,12 @@ static inline struct msg_queue *msg_lock
 	return (struct msg_queue *) ipc_lock(&msg_ids(ns), id, chk);
 }
 
+static inline struct msg_queue *msg_findkey(struct ipc_namespace *ns,
+						key_t key)
+{
+	return (struct msg_queue *) ipc_findkey(&msg_ids(ns), key);
+}
+
 static inline void msg_rmid(struct ipc_namespace *ns, struct msg_queue *s)
 {
 	ipc_rmid(&msg_ids(ns), &s->q_perm);
@@ -286,7 +292,7 @@ asmlinkage long sys_msgget(key_t key, in
 	if (key == IPC_PRIVATE) 
 		ret = newque(ns, key, msgflg);
 	else  {
-		msq = (struct msg_queue *) ipc_findkey(&msg_ids(ns), key);
+		msq = msg_findkey(ns, key);
 		if (msq == NULL) {
 			/* key not used */
 			if (!(msgflg & IPC_CREAT))
ipc/sem.c +7 -1
Index: linux-2.6.21/ipc/sem.c
===================================================================
@@ -192,6 +192,12 @@ static inline struct sem_array *sem_lock
 	return (struct sem_array *) ipc_lock(&sem_ids(ns), id, chk);
 }
 
+static inline struct sem_array *sem_findkey(struct ipc_namespace *ns,
+						key_t key)
+{
+	return (struct sem_array *) ipc_findkey(&sem_ids(ns), key);
+}
+
 static inline void sem_rmid(struct ipc_namespace *ns, struct sem_array *s)
 {
 	ipc_rmid(&sem_ids(ns), &s->sem_perm);
@@ -295,7 +301,7 @@ asmlinkage long sys_semget (key_t key, i
 	if (key == IPC_PRIVATE) {
 		err = newary(ns, key, nsems, semflg);
 	} else {
-		sma = (struct sem_array *) ipc_findkey(&sem_ids(ns), key);
+		sma = sem_findkey(ns, key);
 		if (sma == NULL) {
 			/* key not used */
 			if (!(semflg & IPC_CREAT))
ipc/shm.c +7 -1
Index: linux-2.6.21/ipc/shm.c
===================================================================
@@ -155,6 +155,12 @@ static inline struct shmid_kernel *shm_l
 	return (struct shmid_kernel *) ipc_lock(&shm_ids(ns), id, chk);
 }
 
+static inline struct shmid_kernel *shm_findkey(struct ipc_namespace *ns,
+						key_t key)
+{
+	return (struct shmid_kernel *) ipc_findkey(&shm_ids(ns), key);
+}
+
 static inline void shm_rmid(struct ipc_namespace *ns, struct shmid_kernel *s)
 {
 	ipc_rmid(&shm_ids(ns), &s->shm_perm);
@@ -430,7 +436,7 @@ asmlinkage long sys_shmget (key_t key, s
 	if (key == IPC_PRIVATE) {
 		err = newseg(ns, key, shmflg, size);
 	} else {
-		shp = (struct shmid_kernel *) ipc_findkey(&shm_ids(ns), key);
+		shp = shm_findkey(ns, key);
 		if (shp == NULL) {
 			if (!(shmflg & IPC_CREAT))
 				err = -ENOENT;

--