[PATCH] Breaking down the global IPC locks

[PATCH] Breaking down the global IPC locks

[mingming cao]

[-- Attachment #1: Type: text/plain, Size: 639 bytes --]

Hi Linus and All,

This patch breaks down the three global IPC locks into one lock per IPC
ID. 

In current implementation, the operations on any IPC semaphores are
synchronized by one single IPC semaphore lock.  Changing the IPC locks
from one lock per IPC resource type into one lock per IPC ID makes sense
to me.  By doing so could reduce the possible lock contention in some
applications where the IPC resources are heavily used.

Test results from the LMbench Pipe and IPC latency test shows this patch 
improves the performance of those functions from 1% to 9%.  

Patch applies to 2.5.30 kernel. Please consider it.

--
Mingming Cao

[-- Attachment #2: ipclock.patch --]
[-- Type: text/plain, Size: 2255 bytes --]

diff -urN -X ../dontdiff ../base/linux-2.5.30/ipc/util.c 2.5.30-ipc/ipc/util.c
--- ../base/linux-2.5.30/ipc/util.c	Thu Aug  1 14:16:21 2002
+++ 2.5.30-ipc/ipc/util.c	Fri Aug  2 16:06:19 2002
@@ -74,9 +74,11 @@
 		printk(KERN_ERR "ipc_init_ids() failed, ipc service disabled.\n");
 		ids->size = 0;
 	}
-	ids->ary = SPIN_LOCK_UNLOCKED;
-	for(i=0;i<ids->size;i++)
+	ids->ary_lock =RW_LOCK_UNLOCKED;
+	for(i=0;i<ids->size;i++) {
 		ids->entries[i].p = NULL;
+		ids->entries[i].lock = SPIN_LOCK_UNLOCKED;
+	}
 }
 
 /**
@@ -119,14 +121,15 @@
 	memcpy(new, ids->entries, sizeof(struct ipc_id)*ids->size);
 	for(i=ids->size;i<newsize;i++) {
 		new[i].p = NULL;
+		new[i].lock = SPIN_LOCK_UNLOCKED;
 	}
-	spin_lock(&ids->ary);
+	write_lock(&ids->ary_lock);
 
 	old = ids->entries;
 	ids->entries = new;
 	i = ids->size;
 	ids->size = newsize;
-	spin_unlock(&ids->ary);
+	write_unlock(&ids->ary_lock);
 	ipc_free(old, sizeof(struct ipc_id)*i);
 	return ids->size;
 }
@@ -165,7 +168,8 @@
 	if(ids->seq > ids->seq_max)
 		ids->seq = 0;
 
-	spin_lock(&ids->ary);
+	read_lock(&ids->ary_lock);
+	spin_lock(&ids->entries[id].lock);
 	ids->entries[id].p = new;
 	return id;
 }
diff -urN -X ../dontdiff ../base/linux-2.5.30/ipc/util.h 2.5.30-ipc/ipc/util.h
--- ../base/linux-2.5.30/ipc/util.h	Thu Aug  1 14:16:28 2002
+++ 2.5.30-ipc/ipc/util.h	Fri Aug  2 16:06:19 2002
@@ -20,11 +20,13 @@
 	unsigned short seq_max;
 	struct semaphore sem;	
 	spinlock_t ary;
+	rwlock_t ary_lock;
 	struct ipc_id* entries;
 };
 
 struct ipc_id {
 	struct kern_ipc_perm* p;
+	spinlock_t	lock;
 };
 
 
@@ -72,16 +74,25 @@
 	if(lid >= ids->size)
 		return NULL;
 
-	spin_lock(&ids->ary);
+	/*spin_lock(&ids->ary);*/
+	read_lock(&ids->ary_lock);
+	spin_lock(&ids->entries[lid].lock);
 	out = ids->entries[lid].p;
-	if(out==NULL)
-		spin_unlock(&ids->ary);
+	if(out==NULL) {
+		spin_unlock(&ids->entries[lid].lock);
+		read_unlock(&ids->ary_lock);
+	}
 	return out;
 }
 
 extern inline void ipc_unlock(struct ipc_ids* ids, int id)
 {
-	spin_unlock(&ids->ary);
+	int lid = id % SEQ_MULTIPLIER;
+        if(lid >= ids->size)
+                return;
+
+	spin_unlock(&ids->entries[lid].lock);
+	read_unlock(&ids->ary_lock);
 }
 
 extern inline int ipc_buildid(struct ipc_ids* ids, int id, int seq)

Re: [PATCH] Breaking down the global IPC locks

[Hugh Dickins]

On Mon, 5 Aug 2002, mingming cao wrote:
> In current implementation, the operations on any IPC semaphores are
> synchronized by one single IPC semaphore lock.  Changing the IPC locks
> from one lock per IPC resource type into one lock per IPC ID makes sense
> to me.  By doing so could reduce the possible lock contention in some
> applications where the IPC resources are heavily used.

Yes, the unused "id" argument to ipc_lock() cries out to be put to use.
However...

> Test results from the LMbench Pipe and IPC latency test shows this patch 
> improves the performance of those functions from 1% to 9%.  

I cast doubt in other mail: I don't see how LMbench gets here at all.

If it's worth changing around this SysV IPC locking,
then I think there's rather more that needs to be done:

1. To reduce dirty cacheline bouncing, shouldn't the per-id spinlock
   be in the kern_ipc_perm structure pointed to by entries[lid], not
   mixed in with the pointers of the entries array?  I expect a few
   areas would need to be reworked if that change were made, easy to
   imagine wanting the lock/unlock before/after the structure is there.

2. I worry more about the msg_ids.sem, sem_ids.sem, shm_ids.sem which
   guard these areas too.  Yes, there are some paths where the ipc_lock
   is taken without the down(&ipc_ids.sem) (perhaps those are even the
   significant paths, I haven't determined); but I suspect there's more
   to be gained by avoiding those (kernel)semaphores than by splitting
   the spinlocks.

3. You've added yet another level of locking, the read/write-locking
   on ary_lock.  That may be the right way to go, but I think there's
   now huge redundancy between that and the ipc_ids.sem - should be
   possible to get rid of one or the other.
   
4. You've retained the ids->ary field when you should have removed it;
   presumably retained so ipc_lockall,ipc_unlockall compile, but note
   that now ipc_lockall only locks against another ipc_lockall, which
   is certainly not its intent.  If it's essential (it's only used for
   SHM_INFO), then I think you need to convert it to a lock on ary_lock.

Hugh

Re: [PATCH] Breaking down the global IPC locks

[mingming cao]

Hugh Dickins wrote:
> 
> 1. To reduce dirty cacheline bouncing, shouldn't the per-id spinlock
>    be in the kern_ipc_perm structure pointed to by entries[lid], not
>    mixed in with the pointers of the entries array?  I expect a few
>    areas would need to be reworked if that change were made, easy to
>    imagine wanting the lock/unlock before/after the structure is there.
> 
You are right at the cacheline bouncing issue.  I will make that change.

> 2. I worry more about the msg_ids.sem, sem_ids.sem, shm_ids.sem which
>    guard these areas too.  Yes, there are some paths where the ipc_lock
>    is taken without the down(&ipc_ids.sem) (perhaps those are even the
>    significant paths, I haven't determined); but I suspect there's more
>    to be gained by avoiding those (kernel)semaphores than by splitting
>    the spinlocks.
>
I don't worry the ipc_ids.sem very much.  They are used to protect the
IPC info, which is not updated quiet often (by operation such as
semctl()). Significant IPC operations, like semop(), msgsnd() and
msgrcv(), need the access to the IPC ID, where only the ipc_lock() is
needed.
 
> 3. You've added yet another level of locking, the read/write-locking
>    on ary_lock.  That may be the right way to go, but I think there's
>    now huge redundancy between that and the ipc_ids.sem - should be
>    possible to get rid of one or the other.
>
They look similar at the first glance. But they serve for different
purposes.  The ipc_ids.sem is used to protect the IPC infos, while the
ary_lock is used to protect the IPC ID array.  This way we could do
semctl() and semop() in parallel.
 
> 4. You've retained the ids->ary field when you should have removed it;
>    presumably retained so ipc_lockall,ipc_unlockall compile, but note
>    that now ipc_lockall only locks against another ipc_lockall, which
>    is certainly not its intent.  If it's essential (it's only used for
>    SHM_INFO), then I think you need to convert it to a lock on ary_lock.
> 
Thanks for point this out to me. I need to get ipc_lockall/ipc_unlockall
fixed.

Mingming

Re: [PATCH] Breaking down the global IPC locks - 2.5.31

[mingming cao]

[-- Attachment #1: Type: text/plain, Size: 522 bytes --]

This patch breaks the three global IPC locks into one lock per IPC ID.
By doing so it could reduce possible lock contention in workloads which
make heavy use of IPC semaphores, message queues and Shared
memories...etc.

Changes from last version:
- move the IPC ID lock from the ipc_ids structure to kern_ipc_perm
structure to avoid cacheline bouncing
- make the ipc_lockall() and ipc_unlockal() use the global read-write
locks.  Remove the old global spin locks.

Patch is against 2.5.31 kernel. Please comment.

Mingming

[-- Attachment #2: ipclock.patch --]
[-- Type: text/plain, Size: 2785 bytes --]

diff -urN -X ../dontdiff ../base/linux-2.5.31/include/linux/ipc.h 2.5.31-ipc/include/linux/ipc.h
--- ../base/linux-2.5.31/include/linux/ipc.h	Sat Aug 10 18:41:16 2002
+++ 2.5.31-ipc/include/linux/ipc.h	Tue Aug 13 10:23:59 2002
@@ -56,6 +56,7 @@
 /* used by in-kernel data structures */
 struct kern_ipc_perm
 {
+	spinlock_t	lock;
 	key_t		key;
 	uid_t		uid;
 	gid_t		gid;
diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.c 2.5.31-ipc/ipc/util.c
--- ../base/linux-2.5.31/ipc/util.c	Sat Aug 10 18:41:27 2002
+++ 2.5.31-ipc/ipc/util.c	Wed Aug 14 15:59:19 2002
@@ -74,7 +74,7 @@
 		printk(KERN_ERR "ipc_init_ids() failed, ipc service disabled.\n");
 		ids->size = 0;
 	}
-	ids->ary = SPIN_LOCK_UNLOCKED;
+	ids->ary =RW_LOCK_UNLOCKED;
 	for(i=0;i<ids->size;i++)
 		ids->entries[i].p = NULL;
 }
@@ -120,13 +120,13 @@
 	for(i=ids->size;i<newsize;i++) {
 		new[i].p = NULL;
 	}
-	spin_lock(&ids->ary);
+	write_lock(&ids->ary);
 
 	old = ids->entries;
 	ids->entries = new;
 	i = ids->size;
 	ids->size = newsize;
-	spin_unlock(&ids->ary);
+	write_unlock(&ids->ary);
 	ipc_free(old, sizeof(struct ipc_id)*i);
 	return ids->size;
 }
@@ -165,7 +165,9 @@
 	if(ids->seq > ids->seq_max)
 		ids->seq = 0;
 
-	spin_lock(&ids->ary);
+	new->lock = SPIN_LOCK_UNLOCKED;
+	read_lock(&ids->ary);
+	spin_lock(&new->lock);
 	ids->entries[id].p = new;
 	return id;
 }
diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.h 2.5.31-ipc/ipc/util.h
--- ../base/linux-2.5.31/ipc/util.h	Sat Aug 10 18:41:40 2002
+++ 2.5.31-ipc/ipc/util.h	Wed Aug 14 17:05:22 2002
@@ -19,7 +19,7 @@
 	unsigned short seq;
 	unsigned short seq_max;
 	struct semaphore sem;	
-	spinlock_t ary;
+	rwlock_t ary;
 	struct ipc_id* entries;
 };
 
@@ -47,7 +47,7 @@
 
 extern inline void ipc_lockall(struct ipc_ids* ids)
 {
-	spin_lock(&ids->ary);
+	write_lock(&ids->ary);
 }
 
 extern inline struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id)
@@ -63,7 +63,7 @@
 
 extern inline void ipc_unlockall(struct ipc_ids* ids)
 {
-	spin_unlock(&ids->ary);
+	write_unlock(&ids->ary);
 }
 extern inline struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id)
 {
@@ -72,16 +72,29 @@
 	if(lid >= ids->size)
 		return NULL;
 
-	spin_lock(&ids->ary);
+	read_lock(&ids->ary);
 	out = ids->entries[lid].p;
-	if(out==NULL)
-		spin_unlock(&ids->ary);
+	if(out==NULL) {
+		read_unlock(&ids->ary);
+		return NULL;
+	}
+	spin_lock($out->lock);
 	return out;
 }
 
 extern inline void ipc_unlock(struct ipc_ids* ids, int id)
 {
-	spin_unlock(&ids->ary);
+	int lid = id % SEQ_MULTIPLIER;
+	struct kern_ipc_perm* out;
+
+        if(lid >= ids->size)
+		return;
+	out = ids->entries[lid].p;
+	if (out == NULL)
+		return;
+
+	spin_unlock(&out->lock);
+	read_unlock(&ids->ary);
 }
 
 extern inline int ipc_buildid(struct ipc_ids* ids, int id, int seq)

Re: [PATCH] Breaking down the global IPC locks - 2.5.31

[mingming cao]

[-- Attachment #1: Type: text/plain, Size: 293 bytes --]

mingming cao wrote:
> 
> This patch breaks the three global IPC locks into one lock per IPC ID.
> By doing so it could reduce possible lock contention in workloads which
> make heavy use of IPC semaphores, message queues and Shared
> memories...etc.

Here is the patch again. Fixed a typo. *_^

[-- Attachment #2: ipclock.patch --]
[-- Type: text/plain, Size: 2785 bytes --]

diff -urN -X ../dontdiff ../base/linux-2.5.31/include/linux/ipc.h 2.5.31-ipc/include/linux/ipc.h
--- ../base/linux-2.5.31/include/linux/ipc.h	Sat Aug 10 18:41:16 2002
+++ 2.5.31-ipc/include/linux/ipc.h	Tue Aug 13 10:23:59 2002
@@ -56,6 +56,7 @@
 /* used by in-kernel data structures */
 struct kern_ipc_perm
 {
+	spinlock_t	lock;
 	key_t		key;
 	uid_t		uid;
 	gid_t		gid;
diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.c 2.5.31-ipc/ipc/util.c
--- ../base/linux-2.5.31/ipc/util.c	Sat Aug 10 18:41:27 2002
+++ 2.5.31-ipc/ipc/util.c	Wed Aug 14 15:59:19 2002
@@ -74,7 +74,7 @@
 		printk(KERN_ERR "ipc_init_ids() failed, ipc service disabled.\n");
 		ids->size = 0;
 	}
-	ids->ary = SPIN_LOCK_UNLOCKED;
+	ids->ary =RW_LOCK_UNLOCKED;
 	for(i=0;i<ids->size;i++)
 		ids->entries[i].p = NULL;
 }
@@ -120,13 +120,13 @@
 	for(i=ids->size;i<newsize;i++) {
 		new[i].p = NULL;
 	}
-	spin_lock(&ids->ary);
+	write_lock(&ids->ary);
 
 	old = ids->entries;
 	ids->entries = new;
 	i = ids->size;
 	ids->size = newsize;
-	spin_unlock(&ids->ary);
+	write_unlock(&ids->ary);
 	ipc_free(old, sizeof(struct ipc_id)*i);
 	return ids->size;
 }
@@ -165,7 +165,9 @@
 	if(ids->seq > ids->seq_max)
 		ids->seq = 0;
 
-	spin_lock(&ids->ary);
+	new->lock = SPIN_LOCK_UNLOCKED;
+	read_lock(&ids->ary);
+	spin_lock(&new->lock);
 	ids->entries[id].p = new;
 	return id;
 }
diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.h 2.5.31-ipc/ipc/util.h
--- ../base/linux-2.5.31/ipc/util.h	Sat Aug 10 18:41:40 2002
+++ 2.5.31-ipc/ipc/util.h	Wed Aug 14 17:05:22 2002
@@ -19,7 +19,7 @@
 	unsigned short seq;
 	unsigned short seq_max;
 	struct semaphore sem;	
-	spinlock_t ary;
+	rwlock_t ary;
 	struct ipc_id* entries;
 };
 
@@ -47,7 +47,7 @@
 
 extern inline void ipc_lockall(struct ipc_ids* ids)
 {
-	spin_lock(&ids->ary);
+	write_lock(&ids->ary);
 }
 
 extern inline struct kern_ipc_perm* ipc_get(struct ipc_ids* ids, int id)
@@ -63,7 +63,7 @@
 
 extern inline void ipc_unlockall(struct ipc_ids* ids)
 {
-	spin_unlock(&ids->ary);
+	write_unlock(&ids->ary);
 }
 extern inline struct kern_ipc_perm* ipc_lock(struct ipc_ids* ids, int id)
 {
@@ -72,16 +72,29 @@
 	if(lid >= ids->size)
 		return NULL;
 
-	spin_lock(&ids->ary);
+	read_lock(&ids->ary);
 	out = ids->entries[lid].p;
-	if(out==NULL)
-		spin_unlock(&ids->ary);
+	if(out==NULL) {
+		read_unlock(&ids->ary);
+		return NULL;
+	}
+	spin_lock(&out->lock);
 	return out;
 }
 
 extern inline void ipc_unlock(struct ipc_ids* ids, int id)
 {
-	spin_unlock(&ids->ary);
+	int lid = id % SEQ_MULTIPLIER;
+	struct kern_ipc_perm* out;
+
+        if(lid >= ids->size)
+		return;
+	out = ids->entries[lid].p;
+	if (out == NULL)
+		return;
+
+	spin_unlock(&out->lock);
+	read_unlock(&ids->ary);
 }
 
 extern inline int ipc_buildid(struct ipc_ids* ids, int id, int seq)

Re: [PATCH] Breaking down the global IPC locks - 2.5.31

[Hugh Dickins]

On Tue, 20 Aug 2002, mingming cao wrote:
> > 
> > This patch breaks the three global IPC locks into one lock per IPC ID.
> > By doing so it could reduce possible lock contention in workloads which
> > make heavy use of IPC semaphores, message queues and Shared
> > memories...etc.
> 
> Here is the patch again. Fixed a typo. *_^

Looks good to me...

Except last time around I persuaded you that ipc_lockall, ipc_unlockall
(shm_lockall, shm_unlockall) needed updating; and now I think that they
were redundant all along and can just be removed completely.  Only used
by SHM_INFO, I'd expected you to make them read_locks: surprised to find
write_locks, thought about it some more, realized you would need to use
write_locks - except that the down(&shm_ids.sem) is already protecting
against everything that the write_lock would protect against (the values
reported, concurrent freeing of an entry, concurrent reallocation of the
entries array).  If you agree, please just delete all ipc_lockall
ipc_unlockall shm_lockall shm_unlockall lines.  Sorry for not
noticing that earlier.

You convinced me that it's not worth trying to remove the ipc_ids.sems,
but I'm still slightly worried that you add another layer of locking.
There's going to be no contention over those read_locks (the write_lock
only taken when reallocating entries array), but their cachelines will
still bounce around.  I don't know if contention or bouncing was the
more important effect before, but if bouncing then these changes may
be disappointing in practice.  Performance results (or an experienced
voice, I've little experience of such tradeoffs) would help dispel doubt.
Perhaps, if ReadCopyUpdate support is added into the kernel in future,
RCU could be used here instead of rwlocking?

Nit: I'd prefer "= RW_LOCK_UNLOCKED" instead of "=RW_LOCK_UNLOCKED".

Hugh

Re: [PATCH] Breaking down the global IPC locks - 2.5.31

[mingming cao]

Hugh Dickins wrote:
> 
> Except last time around I persuaded you that ipc_lockall, ipc_unlockall
> (shm_lockall, shm_unlockall) needed updating; and now I think that they
> were redundant all along and can just be removed completely.  Only used
> by SHM_INFO, I'd expected you to make them read_locks: surprised to find
> write_locks, thought about it some more, realized you would need to use
> write_locks - except that the down(&shm_ids.sem) is already protecting
> against everything that the write_lock would protect against (the values
> reported, concurrent freeing of an entry, concurrent reallocation of the
> entries array).  If you agree, please just delete all ipc_lockall
> ipc_unlockall shm_lockall shm_unlockall lines.  Sorry for not
> noticing that earlier.
> 

Agree. I was worrried about the case when shm_destroy() is called while
trying to do a shm_get_stat().  But since shm_ids.sem is used to protect
almost every shm operations, so I think that removing the ipc_lockall()
totally should be safe.  


> You convinced me that it's not worth trying to remove the ipc_ids.sems,
> but I'm still slightly worried that you add another layer of locking.
> There's going to be no contention over those read_locks (the write_lock
> only taken when reallocating entries array), but their cachelines will
> still bounce around.  I don't know if contention or bouncing was the
> more important effect before, but if bouncing then these changes may
> be disappointing in practice.  Performance results (or an experienced
> voice, I've little experience of such tradeoffs) would help dispel doubt.
> Perhaps, if ReadCopyUpdate support is added into the kernel in future,
> RCU could be used here instead of rwlocking?

Hmm...note sure about the tradeoffs either.  Having one lock per IPC ID
does make sense to me, but the cacheline bouncing should also be avoid. 
I need to re-think about this read-write lock and the ipc_ids.sems.  
 
> Nit: I'd prefer "= RW_LOCK_UNLOCKED" instead of "=RW_LOCK_UNLOCKED".

I like it better too.:-)


Mingming