Skip to contentSkip to conversation

An IPC implementation base on Linux IDRs

RFC PATCH In review [email protected] 3 participants 12 messages Aug 31, 2007 – Sep 10, 2007

lore
Share & tools
lore
#0 lore raw

cover An IPC implementation base on Linux IDRs

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:
after proposing a radix tree based implementation at the beginning of July, I'm now proposing a new ipc implementation based on the Linux idr API.

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

With this completely dynamic implementation, it becomes possible to set the kernel default maximum values higher in order to prevent early DoS feedback, on configurations with a high amount of memory. Even if the maximum values are huge, no memory space will be wasted, since the allocations are done "on demand". This is not the case with the existing array based implementation:
an array of the maximum number of entries is allocated only if a single ipc object is actually created.

These patches should be applied to 2.6.23-rc2, in the following order:

[PATCH 1/6]: ipc_idr.patch
[PATCH 2/6]: ipc_syscalls.patch
[PATCH 3/6]: ipc_get.patch
[PATCH 4/6]: ipc_lock_and_check.patch
[PATCH 5/6]: ipcid_to_idx.patch
[PATCH 6/6]: ipc_buildid.patch

--

Regards,
Nadia

#1 lore raw

RFC PATCH 1/6 Storing ipcs into IDRs

[PATCH 01/06]

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

---
 include/linux/ipc.h |    1 
 include/linux/msg.h |    1 
 include/linux/sem.h |    1 
 include/linux/shm.h |    1 
 ipc/msg.c           |  113 +++++++++++++---------
 ipc/sem.c           |  111 ++++++++++++---------
 ipc/shm.c           |  116 +++++++++++++---------
 ipc/util.c          |  264 +++++++++++++++++++++++-----------------------------
 ipc/util.h          |   32 +-----
 9 files changed, 329 insertions(+), 311 deletions(-)
include/linux/ipc.h +1 -0
Index: linux-2.6.23-rc2/include/linux/ipc.h
===================================================================
@@ -61,6 +61,7 @@ struct kern_ipc_perm
 {
 	spinlock_t	lock;
 	int		deleted;
+	int		id;
 	key_t		key;
 	uid_t		uid;
 	gid_t		gid;
include/linux/msg.h +0 -1
Index: linux-2.6.23-rc2/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 */
include/linux/sem.h +0 -1
Index: linux-2.6.23-rc2/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.23-rc2/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;
ipc/util.h +8 -24
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -10,6 +10,8 @@
 #ifndef _IPC_UTIL_H
 #define _IPC_UTIL_H
 
+#include <linux/idr.h>
+
 #define USHRT_MAX 0xffff
 #define SEQ_MULTIPLIER	(IPCMNI)
 
@@ -25,24 +27,17 @@ 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;
 	unsigned short seq;
 	unsigned short seq_max;
 	struct mutex mutex;
-	struct ipc_id_ary nullentry;
-	struct ipc_id_ary* entries;
+	struct idr ipcs_idr;
 };
 
 struct seq_file;
 
-void ipc_init_ids(struct ipc_ids *ids, int size);
+void 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 *));
@@ -55,11 +50,12 @@ 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 *ids, key_t key);
+int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
+int ipc_get_maxid(struct ipc_ids *);
 
 /* 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);
 
@@ -79,18 +75,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 +117 -147

393 lines not on this page · raw message

ipc/msg.c +69 -44

233 lines not on this page · raw message

ipc/sem.c +65 -46

225 lines not on this page · raw message

ipc/shm.c +69 -47

228 lines not on this page · raw message

--

#2 lore raw

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

Quoted 11 lines · [email protected] writes:

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

Thanks for doing this work. It was long overdue.

Do you have any data how this changes memory consumption with many objects?

-Andi

#3 lore raw

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

Quoted 16 lines · Andi Kleen
Quoted 11 lines · [email protected] writes:

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

Quoted 4 lines

Thanks for doing this work. It was long overdue.

Do you have any data how this changes memory consumption with many objects?

No. Will try to send you this as soon as I've done some measurements.

Regards,
Nadia

Signature · 10 lines
===============================================================
Name.......... Nadia DERBEY
Organization.. BULL/DT/OSwR&D/Linux
---------------------------------------------------------------
Email......... mailto:[email protected]
Address....... BULL, B.P. 208, 38432 Echirolles Cedex, France
Tel........... (33) 76 29 77 62 [Internal Bull: (229) 77 62]
Telex,Fax..... 980648 F - (33) 76 29 76 00
Internal Bull. Mail: FREC-B1405
===============================================================
#4 lore raw

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

In reply to Andi Kleen
Quoted 16 lines · Andi Kleen
Quoted 11 lines · [email protected] writes:

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

Quoted 6 lines

Thanks for doing this work. It was long overdue.

Do you have any data how this changes memory consumption with many objects?

-Andi

Andi,

Here are the results I got when creating 32768 (IPCMNI) msg queues with the patched kernel:

http://akt.sourceforge.net/results/2.6.23-rc2-idr/msg11/output.new

It's the output from msg11.c. This script does what follows:
. gets sysinfo(2) results
. captures /proc/meminfo
. captures /proc/slabinfo
. creates XX msg queues (XX given as parameter) . captures /proc/meminfo
. captures /proc/slabinfo
. gets sysinfo results
. outputs all the results
. removes the created ipcs

sysinfo results: a BEFORE and an AFTER column are output where necessary. BEFORE means "before creating the objects"
AFTER means "after the objects have been created"

meminfo results: the BEFORE and AFTER files are pasted

slabinfo results: only the differences between the BEFORE and the AFTER are output.

Here are also the sizes for the ref and the patched kernel:

size linux-2.6.23-rc2.ref/vmlinux linux-2.6.23-rc2/vmlinux
text data bss dec hex filename

4432697  496450  602112 5531259  54667b linux-2.6.23-rc2.ref/vmlinux
4430747  496450  602112 5529309  545edd linux-2.6.23-rc2/vmlinux

The http://akt.sourceforge.net/results/2.6.23-rc2-idr/msg11 directory is structured as follows:

msg11.c: the script I used to generate the results output.ref: the output from msg11 with the ref kernel output.new: the output from msg11 with the patched kernel
size: the output from the size command
ref: directory with the results files for the ref kernel
new: directory with the results files for the patched kernel In these 2 directories:
*_mem_*before: /proc/meminfo before creating the msg queues *_mem_*after: /proc/meminfo after creating the msg queues *_slab_*before: /proc/slabinfo before creating the msg queues *_slab_*after: /proc/slabinfo after creating the msg queues

Regards,
Nadia

#5 lore raw

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

Quoted 65 lines · Nadia Derbey
Quoted 20 lines · Andi Kleen
Quoted 6 lines · [email protected] writes:

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed
into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when
adding

Quoted 9 lines

an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

Quoted 5 lines

Thanks for doing this work. It was long overdue.

Do you have any data how this changes memory consumption with many objects? -Andi

Andi,

Here are the results I got when creating 32768 (IPCMNI) msg queues with the patched kernel:

http://akt.sourceforge.net/results/2.6.23-rc2-idr/msg11/output.new

It's the output from msg11.c. This script does what follows:
. gets sysinfo(2) results
. captures /proc/meminfo
. captures /proc/slabinfo
. creates XX msg queues (XX given as parameter) . captures /proc/meminfo
. captures /proc/slabinfo
. gets sysinfo results
. outputs all the results
. removes the created ipcs

sysinfo results: a BEFORE and an AFTER column are output where necessary. BEFORE means "before creating the objects"
AFTER means "after the objects have been created"

meminfo results: the BEFORE and AFTER files are pasted

slabinfo results: only the differences between the BEFORE and the AFTER are output.

Here are also the sizes for the ref and the patched kernel:

size linux-2.6.23-rc2.ref/vmlinux linux-2.6.23-rc2/vmlinux
text data bss dec hex filename

4432697  496450  602112 5531259  54667b linux-2.6.23-rc2.ref/vmlinux
4430747  496450  602112 5529309  545edd linux-2.6.23-rc2/vmlinux

The http://akt.sourceforge.net/results/2.6.23-rc2-idr/msg11 directory is structured as follows:

Quoted 12 lines

msg11.c: the script I used to generate the results output.ref: the output from msg11 with the ref kernel output.new: the output from msg11 with the patched kernel
size: the output from the size command
ref: directory with the results files for the ref kernel
new: directory with the results files for the patched kernel In these 2 directories:
*_mem_*before: /proc/meminfo before creating the msg queues *_mem_*after: /proc/meminfo after creating the msg queues *_slab_*before: /proc/slabinfo before creating the msg queues *_slab_*after: /proc/slabinfo after creating the msg queues

Andi,

Here is an annalysis of the results I sent you yesterday (I guess you don't have enoguh time to look at everything):

ref code:

1) since /proc/sys/kernel/msgmni has been set to 32768, vmalloc(0x20014) is called to allocate the entries[] array (see grow_ary() --> ipc_rcu_alloc()).

==>

Before msg queues allocation:  VmallocUsed = 2860 kB
After msg queues allocation:   VmallocUsed = 2996 KB

Once allocated this array is never freed.

Unfortunately, in the result I sent you yesterday, you can't see the evolution since it was not the 1st time I was running the test, so the vmalloc() has not been called.

2) Since 32768 msg queues have been created and a msg_queue structure < PAGE_SIZE, kmalloc(0x6C) is called 32768 times

==> size-128 in slabinfo: (I slighty simplified the output to make it fit in the mail):

objs slabs
# name <active> <num> <size> : <active> <num>
before : size-128 1070 1320 128 : 44 44
after : size-128 33840 33840 128 : 1128 1128

patched code:
1) since 32768 msg queues are created, idr_pre_get() is called 32768 times ==> idr_layer_cache in slabinfo:

objs slabs
# name <active> <num> <size> : <active> <num>
before : idr_layer_cache 112 116 136 : 4 4
after : idr_layer_cache 1189 1189 136 : 41 41

2) This point remains unchanged compared to the ref code.

Regards,
Nadia

#6 lore raw

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

In reply to [email protected]
Quoted 15 lines · On Fri, 31 Aug 2007 13:24:46 +0200 [email protected] wrote:

[PATCH 01/06]

This patch introduces ipcs storage into IDRs. The main changes are:
. This ipc_ids structure is changed: the entries array is changed into a
root idr structure.
. The grow_ary() routine is removed: it is not needed anymore when adding
an ipc structure, since we are now using the IDR facility.
. The ipc_rmid() routine interface is changed:
. 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

This is a large patch, and I have neither the time nor competence to review it :(

I hope that someone will find the time to do a detailed review-n-test of this code, because the IPC code is pretty touchy and isn't well-maintained, as I'm sure you have noticed.

Meanwhile I'll queue the patches up for a bit of compile-time and runtime testing, thanks.

ipc/msg.c static void freeque(struct ipc_namespace · line 287

Quoted 3 lines

...

ipc/msg.c +1 -0
+		msq = (struct msg_queue *) ipc_findkey(&msg_ids(ns), key);

As a separate cleanup: the code casts the ipc_findkey to some outer struct in all cases. It would be nicer to convert this to container_of(). It'll generate the same code, but it actually represents what the code is doing and perhaps means that the code will continue to work if the `struct kern_ipc_perm' is not at the start of the containing struct.

#7 lore raw

RFC PATCH 2/6 Unifying the syscalls code

In reply to [email protected]

[PATCH 02/06]

This patch introduces a change into the sys_msgget(), sys_semget() and sys_shmget() routines: they now share a common code, which is better for maintainability.

---
 ipc/msg.c  |   61 ++++++++++--------------------------
 ipc/sem.c  |   78 ++++++++++++++++++-----------------------------
 ipc/shm.c  |   75 ++++++++++++++++-----------------------------
 ipc/util.c |  101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ipc/util.h |   43 +++++++++++++++++++++++++
 5 files changed, 217 insertions(+), 141 deletions(-)
ipc/util.h +42 -1
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -35,6 +35,35 @@ struct ipc_ids {
 	struct idr ipcs_idr;
 };
 
+/*
+ * Structure that holds the parameters needed by the ipc operations
+ * (see after)
+ */
+struct ipc_params {
+	key_t key;
+	int flg;
+	union {
+		size_t size;	/* for shared memories */
+		int nsems;	/* for semaphores */
+	} u;			/* holds the getnew() specific param */
+};
+
+/*
+ * Structure that holds some ipc operations. This structure is used to unify
+ * the calls to sys_msgget(), sys_semget(), sys_shmget()
+ *      . routine to call to create a new ipc object. Can be one of newque,
+ *        newary, newseg
+ *      . routine to call to call to check permissions for a new ipc object.
+ *        Can be one of security_msg_associate, security_sem_associate,
+ *        security_shm_associate
+ *      . routine to call for an extra check if needed
+ */
+struct ipc_ops {
+	int (*getnew) (struct ipc_namespace *, struct ipc_params *);
+	int (*associate) (void *, int);
+	int (*more_checks) (void *, struct ipc_params *);
+};
+
 struct seq_file;
 
 void ipc_init_ids(struct ipc_ids *);
@@ -50,7 +79,6 @@ void __init ipc_init_proc_interface(cons
 #define IPC_SHM_IDS	2
 
 /* must be called with ids->mutex acquired.*/
-struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key);
 int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
 int ipc_get_maxid(struct ipc_ids *);
 
@@ -95,5 +123,18 @@ int ipc_parse_version (int *cmd);
 extern void free_msg(struct msg_msg *msg);
 extern struct msg_msg *load_msg(const void __user *src, int len);
 extern int store_msg(void __user *dest, struct msg_msg *msg, int len);
+extern int ipcget_new(struct ipc_namespace *, struct ipc_ids *,
+			struct ipc_ops *, struct ipc_params *);
+extern int ipcget_public(struct ipc_namespace *, struct ipc_ids *,
+			struct ipc_ops *, struct ipc_params *);
+
+static inline int ipcget(struct ipc_namespace *ns, struct ipc_ids *ids,
+			struct ipc_ops *ops, struct ipc_params *params)
+{
+	if (params->key == IPC_PRIVATE)
+		return ipcget_new(ns, ids, ops, params);
+	else
+		return ipcget_public(ns, ids, ops, params);
+}
 
 #endif
ipc/util.c +100 -1

113 lines not on this page · raw message

ipc/msg.c +17 -44

90 lines not on this page · raw message

ipc/sem.c +30 -48

110 lines not on this page · raw message

ipc/shm.c +28 -47

101 lines not on this page · raw message

--

#8 lore raw

RFC PATCH 3/6 Removing the ipc_get() routine

In reply to [email protected]

[PATCH 03/06]

This is a trivial patch that removes the ipc_get() routine: it is replaced by a call to idr_find().

---
 ipc/shm.c  |   16 +++++++++++++---
 ipc/util.c |   19 -------------------
 ipc/util.h |    1 -
 3 files changed, 13 insertions(+), 23 deletions(-)
ipc/util.h +0 -1
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -103,7 +103,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);
ipc/util.c +0 -19
Index: linux-2.6.23-rc2/ipc/util.c
===================================================================
@@ -669,25 +669,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;
-	out = idr_find(&ids->ipcs_idr, lid);
-	return out;
-}
-
 struct kern_ipc_perm *ipc_lock(struct ipc_ids *ids, int id)
 {
 	struct kern_ipc_perm *out;
ipc/shm.c +13 -3
Index: linux-2.6.23-rc2/ipc/shm.c
===================================================================
@@ -63,8 +63,6 @@ static struct ipc_ids init_shm_ids;
 	((struct shmid_kernel*)ipc_lock(&shm_ids(ns),id))
 #define shm_unlock(shp)			\
 	ipc_unlock(&(shp)->shm_perm)
-#define shm_get(ns, id)			\
-	((struct shmid_kernel*)ipc_get(&shm_ids(ns),id))
 #define shm_buildid(ns, id, seq)	\
 	ipc_buildid(&shm_ids(ns), id, seq)
 
@@ -562,7 +560,19 @@ static void shm_get_stat(struct ipc_name
 		struct shmid_kernel *shp;
 		struct inode *inode;
 
-		shp = shm_get(ns, next_id);
+		/*
+		 * idr_find() is called via shm_get(), so with shm_ids.mutex
+		 * locked. Since ipc_addid() is also called with
+		 * shm_ids.mutex down, there is no need to add read barriers
+		 * here to gurantee the writes in ipc_addid() are seen in
+		 * order here (for Alpha).
+		 * However idr_find() itself does not necessary require
+		 * ipc_ids.mutex down. So if idr_find() is used by other
+		 * places without ipc_ids.mutex down, then it needs read
+		 * read memory barriers as ipc_lock() does.
+		 */
+
+		shp = idr_find(&shm_ids(ns).ipcs_idr, next_id);
 		if (shp == NULL)
 			continue;
 

--

#9 lore raw

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

In reply to [email protected]

[PATCH 04/06]

This patch introduces a new ipc_lock_check() routine interface:
. each time ipc_checkid() is called, this is done after calling ipc_lock().
ipc_checkid() is now called from inside ipc_lock_check().

---
 ipc/msg.c  |   62 ++++++++++++++++++++----------------------
 ipc/sem.c  |   70 ++++++++++++++++++++++-------------------------
 ipc/shm.c  |   90 ++++++++++++++++++++++++++++++++-----------------------------
 ipc/util.c |   23 +--------------
 ipc/util.h |   40 ++++++++++++++++++++++++---
 5 files changed, 149 insertions(+), 136 deletions(-)
ipc/util.h +36 -4
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -103,11 +103,8 @@ 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);
-void ipc_lock_by_ptr(struct kern_ipc_perm *ipcp);
-void ipc_unlock(struct kern_ipc_perm* perm);
+struct kern_ipc_perm *ipc_lock(struct ipc_ids *, int);
 int ipc_buildid(struct ipc_ids* ids, int id, int seq);
-int ipc_checkid(struct ipc_ids* ids, struct kern_ipc_perm* ipcp, int uid);
 
 void kernel_to_ipc64_perm(struct kern_ipc_perm *in, struct ipc64_perm *out);
 void ipc64_perm_to_ipc_perm(struct ipc64_perm *in, struct ipc_perm *out);
@@ -127,6 +124,41 @@ extern int ipcget_new(struct ipc_namespa
 extern int ipcget_public(struct ipc_namespace *, struct ipc_ids *,
 			struct ipc_ops *, struct ipc_params *);
 
+static inline int ipc_checkid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp,
+				int uid)
+{
+	if (uid / SEQ_MULTIPLIER != ipcp->seq)
+		return 1;
+	return 0;
+}
+
+static inline void ipc_lock_by_ptr(struct kern_ipc_perm *perm)
+{
+	spin_lock(&perm->lock);
+}
+
+static inline void ipc_unlock(struct kern_ipc_perm *perm)
+{
+	spin_unlock(&perm->lock);
+}
+
+static inline struct kern_ipc_perm *ipc_lock_check(struct ipc_ids *ids,
+						int id)
+{
+	struct kern_ipc_perm *out;
+
+	out = ipc_lock(ids, id);
+	if (IS_ERR(out))
+		return out;
+
+	if (ipc_checkid(ids, out, id)) {
+		spin_unlock(&out->lock);
+		return ERR_PTR(-EIDRM);
+	}
+
+	return out;
+}
+
 static inline int ipcget(struct ipc_namespace *ns, struct ipc_ids *ids,
 			struct ipc_ops *ops, struct ipc_params *params)
 {
ipc/util.c +2 -21
Index: linux-2.6.23-rc2/ipc/util.c
===================================================================
@@ -678,7 +678,7 @@ struct kern_ipc_perm *ipc_lock(struct ip
 	out = idr_find(&ids->ipcs_idr, lid);
 	if (out == NULL) {
 		rcu_read_unlock();
-		return NULL;
+		return ERR_PTR(-EINVAL);
 	}
 
 	spin_lock(&out->lock);
@@ -689,36 +689,17 @@ struct kern_ipc_perm *ipc_lock(struct ip
 	if (out->deleted) {
 		spin_unlock(&out->lock);
 		rcu_read_unlock();
-		return NULL;
+		return ERR_PTR(-EINVAL);
 	}
 
 	return out;
 }
 
-void ipc_lock_by_ptr(struct kern_ipc_perm *perm)
-{
-	rcu_read_lock();
-	spin_lock(&perm->lock);
-}
-
-void ipc_unlock(struct kern_ipc_perm* perm)
-{
-	spin_unlock(&perm->lock);
-	rcu_read_unlock();
-}
-
 int ipc_buildid(struct ipc_ids* ids, int id, int seq)
 {
 	return SEQ_MULTIPLIER*seq + id;
 }
 
-int ipc_checkid(struct ipc_ids* ids, struct kern_ipc_perm* ipcp, int uid)
-{
-	if(uid/SEQ_MULTIPLIER != ipcp->seq)
-		return 1;
-	return 0;
-}
-
 #ifdef __ARCH_WANT_IPC_PARSE_VERSION
 
 
ipc/msg.c +30 -32

111 lines not on this page · raw message

ipc/sem.c +33 -37

137 lines not on this page · raw message

ipc/shm.c +48 -42

170 lines not on this page · raw message

--

#10 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/util.c |    4 ++--
 ipc/util.h |    2 ++
 2 files changed, 4 insertions(+), 2 deletions(-)
ipc/util.h +2 -0
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -78,6 +78,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.*/
 int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
 int ipc_get_maxid(struct ipc_ids *);
ipc/util.c +2 -2
Index: linux-2.6.23-rc2/ipc/util.c
===================================================================
@@ -413,7 +413,7 @@ int ipcget_public(struct ipc_namespace *
  
 void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 {
-	int lid = ipcp->id % SEQ_MULTIPLIER;
+	int lid = ipcid_to_idx(ipcp->id);
 
 	idr_remove(&ids->ipcs_idr, lid);
 
@@ -672,7 +672,7 @@ void ipc64_perm_to_ipc_perm (struct ipc6
 struct kern_ipc_perm *ipc_lock(struct ipc_ids *ids, int id)
 {
 	struct kern_ipc_perm *out;
-	int lid = id % SEQ_MULTIPLIER;
+	int lid = ipcid_to_idx(id);
 
 	rcu_read_lock();
 	out = idr_find(&ids->ipcs_idr, lid);

--

#11 lore raw

RFC PATCH 6/6 Inlining ipc_buildid()

In reply to [email protected]

[PATCH 06/06]

This is a trivial patch that changes the ipc_buildid() routine into a static inline.

---
 ipc/util.c |    5 -----
 ipc/util.h |    6 +++++-
 2 files changed, 5 insertions(+), 6 deletions(-)
ipc/util.h +5 -1
Index: linux-2.6.23-rc2/ipc/util.h
===================================================================
@@ -106,7 +106,6 @@ void ipc_rcu_getref(void *ptr);
 void ipc_rcu_putref(void *ptr);
 
 struct kern_ipc_perm *ipc_lock(struct ipc_ids *, int);
-int ipc_buildid(struct ipc_ids* ids, int id, int seq);
 
 void kernel_to_ipc64_perm(struct kern_ipc_perm *in, struct ipc64_perm *out);
 void ipc64_perm_to_ipc_perm(struct ipc64_perm *in, struct ipc_perm *out);
@@ -126,6 +125,11 @@ extern int ipcget_new(struct ipc_namespa
 extern int ipcget_public(struct ipc_namespace *, struct ipc_ids *,
 			struct ipc_ops *, struct ipc_params *);
 
+static inline int ipc_buildid(struct ipc_ids *ids, int id, int seq)
+{
+	return SEQ_MULTIPLIER * seq + id;
+}
+
 static inline int ipc_checkid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp,
 				int uid)
 {
ipc/util.c +0 -5
Index: linux-2.6.23-rc2/ipc/util.c
===================================================================
@@ -695,11 +695,6 @@ struct kern_ipc_perm *ipc_lock(struct ip
 	return out;
 }
 
-int ipc_buildid(struct ipc_ids* ids, int id, int seq)
-{
-	return SEQ_MULTIPLIER*seq + id;
-}
-
 #ifdef __ARCH_WANT_IPC_PARSE_VERSION
 
 

--