[patch 1/3] ipc: rename IPCMNI to IPCMNI_MAX

[patch 1/3] ipc: rename IPCMNI to IPCMNI_MAX

[Nick Piggin]

Hi,

Just a couple of small IPC patches I have, I wonder if you could
comment on or merge?

--
The IPCMNI limit is different from the other MNI limits. It is not exposed
to userspace, it is not tunable via sysctl -- it is a hard limit. Rename it
to IPCMNI_MAX, to signify it is a maximum rather than default value.

It is an internal value tied to IPC sequence numbering, so move it into
ipc/util.h.

Index: linux-2.6/include/linux/ipc.h
===================================================================
--- linux-2.6.orig/include/linux/ipc.h
+++ linux-2.6/include/linux/ipc.h
@@ -80,8 +80,6 @@ struct ipc_kludge {
 #ifdef __KERNEL__
 #include <linux/spinlock.h>
 
-#define IPCMNI 32768  /* <= MAX_INT limit for ipc arrays (including sysctl changes) */
-
 /* used by in-kernel data structures */
 struct kern_ipc_perm
 {
Index: linux-2.6/include/linux/msg.h
===================================================================
--- linux-2.6.orig/include/linux/msg.h
+++ linux-2.6/include/linux/msg.h
@@ -55,11 +55,11 @@ struct msginfo {
  * at most 1/MSG_MEM_SCALE of the lowmem (see the formula in ipc/msg.c):
  * up to 8MB       : msgmni = 16 (MSGMNI)
  * 4 GB            : msgmni = 8K
- * more than 16 GB : msgmni = 32K (IPCMNI)
+ * more than 16 GB : msgmni = 32K (IPCMNI_MAX)
  */
 #define MSG_MEM_SCALE 32
 
-#define MSGMNI    16   /* <= IPCMNI */     /* max # of msg queue identifiers */
+#define MSGMNI    16   /* <= IPCMNI_MAX */ /* max # of msg queue identifiers */
 #define MSGMAX  8192   /* <= INT_MAX */   /* max size of message (bytes) */
 #define MSGMNB 16384   /* <= INT_MAX */   /* default max size of a message queue */
 
Index: linux-2.6/include/linux/sem.h
===================================================================
--- linux-2.6.orig/include/linux/sem.h
+++ linux-2.6/include/linux/sem.h
@@ -63,7 +63,7 @@ struct  seminfo {
 	int semaem;
 };
 
-#define SEMMNI  128             /* <= IPCMNI  max # of semaphore identifiers */
+#define SEMMNI  128             /* <= IPCMNI_MAX  max semaphore identifiers */
 #define SEMMSL  250             /* <= 8 000 max num of semaphores per id */
 #define SEMMNS  (SEMMNI*SEMMSL) /* <= INT_MAX max # of semaphores in system */
 #define SEMOPM  32	        /* <= 1 000 max num of ops per semop call */
Index: linux-2.6/include/linux/shm.h
===================================================================
--- linux-2.6.orig/include/linux/shm.h
+++ linux-2.6/include/linux/shm.h
@@ -14,15 +14,15 @@
  * be increased by sysctl
  */
 
-#define SHMMAX 0x2000000		 /* max shared seg size (bytes) */
-#define SHMMIN 1			 /* min shared seg size (bytes) */
-#define SHMMNI 4096			 /* max num of segs system wide */
+#define SHMMAX 0x2000000	 /* max shared seg size (bytes) */
+#define SHMMIN 1		 /* min shared seg size (bytes) */
+#define SHMMNI 4096		 /* <= IPCMNI_MAX max num of segs system wide */
 #ifdef __KERNEL__
 #define SHMALL (SHMMAX/PAGE_SIZE*(SHMMNI/16)) /* max shm system wide (pages) */
 #else
 #define SHMALL (SHMMAX/getpagesize()*(SHMMNI/16))
 #endif
-#define SHMSEG SHMMNI			 /* max shared segs per process */
+#define SHMSEG SHMMNI		 /* max shared segs per process */
 
 #ifdef __KERNEL__
 #include <asm/shmparam.h>
Index: linux-2.6/ipc/msg.c
===================================================================
--- linux-2.6.orig/ipc/msg.c
+++ linux-2.6/ipc/msg.c
@@ -81,7 +81,7 @@ static int sysvipc_msg_proc_show(struct
  * Scale msgmni with the available lowmem size: the memory dedicated to msg
  * queues should occupy at most 1/MSG_MEM_SCALE of lowmem.
  * Also take into account the number of nsproxies created so far.
- * This should be done staying within the (MSGMNI , IPCMNI/nr_ipc_ns) range.
+ * This should be done staying within the (MSGMNI , IPCMNI_MAX/nr_ipc_ns) range.
  */
 void recompute_msgmni(struct ipc_namespace *ns)
 {
@@ -100,8 +100,8 @@ void recompute_msgmni(struct ipc_namespa
 		return;
 	}
 
-	if (allowed > IPCMNI / nb_ns) {
-		ns->msg_ctlmni = IPCMNI / nb_ns;
+	if (allowed > IPCMNI_MAX / nb_ns) {
+		ns->msg_ctlmni = IPCMNI_MAX / nb_ns;
 		return;
 	}
 
Index: linux-2.6/ipc/util.c
===================================================================
--- linux-2.6.orig/ipc/util.c
+++ linux-2.6/ipc/util.c
@@ -113,7 +113,7 @@ __initcall(ipc_init);
  *	@ids: Identifier set
  *
  *	Set up the sequence range to use for the ipc identifier range (limited
- *	below IPCMNI) then initialise the ids idr.
+ *	below IPCMNI_MAX) then initialise the ids idr.
  */
  
 void ipc_init_ids(struct ipc_ids *ids)
@@ -218,12 +218,12 @@ int ipc_get_maxid(struct ipc_ids *ids)
 	if (ids->in_use == 0)
 		return -1;
 
-	if (ids->in_use == IPCMNI)
-		return IPCMNI - 1;
+	if (ids->in_use == IPCMNI_MAX)
+		return IPCMNI_MAX - 1;
 
 	/* Look for the last assigned id */
 	total = 0;
-	for (id = 0; id < IPCMNI && total < ids->in_use; id++) {
+	for (id = 0; id < IPCMNI_MAX && total < ids->in_use; id++) {
 		ipc = idr_find(&ids->ipcs_idr, id);
 		if (ipc != NULL) {
 			max_id = id;
@@ -253,8 +253,8 @@ int ipc_addid(struct ipc_ids* ids, struc
 	gid_t egid;
 	int id, err;
 
-	if (size > IPCMNI)
-		size = IPCMNI;
+	if (size > IPCMNI_MAX)
+		size = IPCMNI_MAX;
 
 	if (ids->in_use >= size)
 		return -ENOSPC;
@@ -859,7 +859,7 @@ static struct kern_ipc_perm *sysvipc_fin
 	if (total >= ids->in_use)
 		return NULL;
 
-	for ( ; pos < IPCMNI; pos++) {
+	for ( ; pos < IPCMNI_MAX; pos++) {
 		ipc = idr_find(&ids->ipcs_idr, pos);
 		if (ipc != NULL) {
 			*new_pos = pos + 1;
Index: linux-2.6/ipc/util.h
===================================================================
--- linux-2.6.orig/ipc/util.h
+++ linux-2.6/ipc/util.h
@@ -13,7 +13,9 @@
 #include <linux/unistd.h>
 #include <linux/err.h>
 
-#define SEQ_MULTIPLIER	(IPCMNI)
+#define IPCMNI_MAX 32768  /* <= MAX_INT absolute limit for ipc arrays */
+
+#define SEQ_MULTIPLIER	(IPCMNI_MAX)
 
 void sem_init (void);
 void msg_init (void);

[patch 2/3] ipc: use shifts to extract seq/idx

[Nick Piggin]

All the ipc ids and sequences are signed integers, so power of 2
sequence multiplier does not work so well. Convert it to use shifts,
which improves generated code particularly in ipc_lock/ipc_lock_check
fast paths.

Index: linux-2.6/ipc/util.c
===================================================================
--- linux-2.6.orig/ipc/util.c
+++ linux-2.6/ipc/util.c
@@ -123,7 +123,7 @@ void ipc_init_ids(struct ipc_ids *ids)
 	ids->in_use = 0;
 	ids->seq = 0;
 	{
-		int seq_limit = INT_MAX/SEQ_MULTIPLIER;
+		int seq_limit = INT_MAX >> SEQ_SHIFT;
 		if (seq_limit > USHORT_MAX)
 			ids->seq_max = USHORT_MAX;
 		 else
Index: linux-2.6/ipc/util.h
===================================================================
--- linux-2.6.orig/ipc/util.h
+++ linux-2.6/ipc/util.h
@@ -13,9 +13,11 @@
 #include <linux/unistd.h>
 #include <linux/err.h>
 
-#define IPCMNI_MAX 32768  /* <= MAX_INT absolute limit for ipc arrays */
+/* IPCMNI_MAX should be <= MAX_INT, absolute limit for ipc arrays */
+#define IPCMNI_MAX_SHIFT	15
+#define IPCMNI_MAX		(1 << IPCMNI_MAX_SHIFT)
 
-#define SEQ_MULTIPLIER	(IPCMNI_MAX)
+#define SEQ_SHIFT		IPCMNI_MAX_SHIFT
 
 void sem_init (void);
 void msg_init (void);
@@ -93,7 +95,7 @@ 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)
+#define ipcid_to_idx(id) ((id) & ((1UL << SEQ_SHIFT) - 1))
 
 /* must be called with ids->rw_mutex acquired for writing */
 int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
@@ -146,7 +148,7 @@ extern void recompute_msgmni(struct ipc_
 
 static inline int ipc_buildid(int id, int seq)
 {
-	return SEQ_MULTIPLIER * seq + id;
+	return (seq << SEQ_SHIFT) + id;
 }
 
 /*
@@ -154,7 +156,7 @@ static inline int ipc_buildid(int id, in
  */
 static inline int ipc_checkid(struct kern_ipc_perm *ipcp, int uid)
 {
-	if (uid / SEQ_MULTIPLIER != ipcp->seq)
+	if ((uid >> SEQ_SHIFT) != ipcp->seq)
 		return 1;
 	return 0;
 }

[patch 3/3] ipc: increase IPCMNI_MAX

[Nick Piggin]

Just wondering whether there is a good reason to have a full 16 bits of
sequence in ipc ids? 32K indexes is pretty easy to overflow, if only in
stress tests for now. I was doing some big aim7 stress testing, which
required this patch, but it's not exactly a realistic workload :) 

But the sequence seems like it just helps slightly with buggy apps, and
if the app is buggy then it can by definition mess up its own ids
anyway? So I don't see that such amount of seq is required.

Index: linux-2.6/ipc/util.h
===================================================================
--- linux-2.6.orig/ipc/util.h
+++ linux-2.6/ipc/util.h
@@ -14,7 +14,16 @@
 #include <linux/err.h>
 
 /* IPCMNI_MAX should be <= MAX_INT, absolute limit for ipc arrays */
-#define IPCMNI_MAX_SHIFT	15
+/*
+ * IPC ids consist of an index into the idr, which allocates from the bottom
+ * up, and a sequence number which is continually incremented. Valid indexes
+ * are from 0..IPCMNI_MAX (or further constrained by sysctls or other limits).
+ * The sequence number prevents ids from being reused quickly. The sequence
+ * number resides in the top part of the 'int' after IPCMNI_MAX.
+ *
+ * Increasing IPCMNI_MAX reduces the sequence wrap interval.
+ */
+#define IPCMNI_MAX_SHIFT	20
 #define IPCMNI_MAX		(1 << IPCMNI_MAX_SHIFT)
 
 #define SEQ_SHIFT		IPCMNI_MAX_SHIFT

Re: [patch 2/3] ipc: use shifts to extract seq/idx

[Manfred Spraul]

On 05/20/2010 09:00 AM, Nick Piggin wrote:
> All the ipc ids and sequences are signed integers, so power of 2
> sequence multiplier does not work so well. Convert it to use shifts,
> which improves generated code particularly in ipc_lock/ipc_lock_check
> fast paths.
>
>    
Have you checked the asm output?
I would expect that gcc auto-optimizes constant divides by power-of-two.

--
     Manfred

Re: [patch 2/3] ipc: use shifts to extract seq/idx

[Nick Piggin]

On Thu, May 20, 2010 at 08:16:24PM +0200, Manfred Spraul wrote:
> On 05/20/2010 09:00 AM, Nick Piggin wrote:
> >All the ipc ids and sequences are signed integers, so power of 2
> >sequence multiplier does not work so well. Convert it to use shifts,
> >which improves generated code particularly in ipc_lock/ipc_lock_check
> >fast paths.
> >
> Have you checked the asm output?

Yep, it's quite improved (although this isn't a particularly hot
path I thought it is a good cleanup).


> I would expect that gcc auto-optimizes constant divides by power-of-two.

It can't with signed I guess.

Re: [patch 3/3] ipc: increase IPCMNI_MAX

[Andrew Morton]

On Thu, 20 May 2010 17:07:41 +1000
Nick Piggin <npiggin@suse.de> wrote:

> Just wondering whether there is a good reason to have a full 16 bits of
> sequence in ipc ids? 32K indexes is pretty easy to overflow, if only in
> stress tests for now. I was doing some big aim7 stress testing, which
> required this patch, but it's not exactly a realistic workload :) 
> 
> But the sequence seems like it just helps slightly with buggy apps, and
> if the app is buggy then it can by definition mess up its own ids
> anyway? So I don't see that such amount of seq is required.
> 
> Index: linux-2.6/ipc/util.h
> ===================================================================
> --- linux-2.6.orig/ipc/util.h
> +++ linux-2.6/ipc/util.h
> @@ -14,7 +14,16 @@
>  #include <linux/err.h>
>  
>  /* IPCMNI_MAX should be <= MAX_INT, absolute limit for ipc arrays */
> -#define IPCMNI_MAX_SHIFT	15
> +/*
> + * IPC ids consist of an index into the idr, which allocates from the bottom
> + * up, and a sequence number which is continually incremented. Valid indexes
> + * are from 0..IPCMNI_MAX (or further constrained by sysctls or other limits).
> + * The sequence number prevents ids from being reused quickly. The sequence
> + * number resides in the top part of the 'int' after IPCMNI_MAX.
> + *
> + * Increasing IPCMNI_MAX reduces the sequence wrap interval.
> + */
> +#define IPCMNI_MAX_SHIFT	20
>  #define IPCMNI_MAX		(1 << IPCMNI_MAX_SHIFT)
>  
>  #define SEQ_SHIFT		IPCMNI_MAX_SHIFT

Some anaylsis of the worst-case memory consumption would be mollifying.

I took the absence of Signed-off-by:'s to mean "rfc" and wandered away.

Re: [patch 3/3] ipc: increase IPCMNI_MAX

[Nick Piggin]

On Fri, May 21, 2010 at 01:31:36PM -0700, Andrew Morton wrote:
> On Thu, 20 May 2010 17:07:41 +1000
> Nick Piggin <npiggin@suse.de> wrote:
> 
> > Just wondering whether there is a good reason to have a full 16 bits of
> > sequence in ipc ids? 32K indexes is pretty easy to overflow, if only in
> > stress tests for now. I was doing some big aim7 stress testing, which
> > required this patch, but it's not exactly a realistic workload :) 
> > 
> > But the sequence seems like it just helps slightly with buggy apps, and
> > if the app is buggy then it can by definition mess up its own ids
> > anyway? So I don't see that such amount of seq is required.
> > 
> > Index: linux-2.6/ipc/util.h
> > ===================================================================
> > --- linux-2.6.orig/ipc/util.h
> > +++ linux-2.6/ipc/util.h
> > @@ -14,7 +14,16 @@
> >  #include <linux/err.h>
> >  
> >  /* IPCMNI_MAX should be <= MAX_INT, absolute limit for ipc arrays */
> > -#define IPCMNI_MAX_SHIFT	15
> > +/*
> > + * IPC ids consist of an index into the idr, which allocates from the bottom
> > + * up, and a sequence number which is continually incremented. Valid indexes
> > + * are from 0..IPCMNI_MAX (or further constrained by sysctls or other limits).
> > + * The sequence number prevents ids from being reused quickly. The sequence
> > + * number resides in the top part of the 'int' after IPCMNI_MAX.
> > + *
> > + * Increasing IPCMNI_MAX reduces the sequence wrap interval.
> > + */
> > +#define IPCMNI_MAX_SHIFT	20
> >  #define IPCMNI_MAX		(1 << IPCMNI_MAX_SHIFT)
> >  
> >  #define SEQ_SHIFT		IPCMNI_MAX_SHIFT
> 
> Some anaylsis of the worst-case memory consumption would be mollifying.

OK.
 
> I took the absence of Signed-off-by:'s to mean "rfc" and wandered away.

Yes. They should probably go through Manfred to you anyway.