Breaking down the global IPC locks

PATCH In review mingming cao 2 participants 7 messages Aug 5, 2002 – Aug 23, 2002

lore

Share & tools

lore

mingming cao

author

2002-08-05 19:48 UTC #0 lore raw

PATCH 1/1 Breaking down the global IPC locks

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

ipc/util.c renamed from base/linux-2.5.30/ipc/util.c +9 -5

diff -urN -X ../dontdiff ../base/linux-2.5.30/ipc/util.c 2.5.30-ipc/ipc/util.c
@@ -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;
 }

ipc/util.h renamed from base/linux-2.5.30/ipc/util.h +15 -4

diff -urN -X ../dontdiff ../base/linux-2.5.30/ipc/util.h 2.5.30-ipc/ipc/util.h
@@ -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)

Hugh Dickins

2002-08-06 15:49 UTC #1 lore raw

Quoted 5 lines · mingming cao

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

Quoted 2 lines

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

mingming cao

author

2002-08-06 20:52 UTC #2 lore raw

Quoted 7 lines · Hugh Dickins

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.

Quoted 7 lines

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.

Quoted 5 lines

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.

Quoted 6 lines

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

mingming cao

author

2002-08-20 00:26 UTC #3 lore raw

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

In reply to Hugh Dickins

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

include/linux/ipc.h renamed from base/linux-2.5.31/include/linux/ipc.h +1 -0

diff -urN -X ../dontdiff ../base/linux-2.5.31/include/linux/ipc.h 2.5.31-ipc/include/linux/ipc.h
@@ -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;

ipc/util.c renamed from base/linux-2.5.31/ipc/util.c +6 -4

diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.c 2.5.31-ipc/ipc/util.c
@@ -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;
 }

ipc/util.h renamed from base/linux-2.5.31/ipc/util.h +20 -7

diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.h 2.5.31-ipc/ipc/util.h
@@ -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)

mingming cao

author

2002-08-20 17:47 UTC #4 lore raw

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

Quoted 5 lines · mingming cao

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. *_^

include/linux/ipc.h renamed from base/linux-2.5.31/include/linux/ipc.h +1 -0

diff -urN -X ../dontdiff ../base/linux-2.5.31/include/linux/ipc.h 2.5.31-ipc/include/linux/ipc.h
@@ -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;

ipc/util.c renamed from base/linux-2.5.31/ipc/util.c +6 -4

diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.c 2.5.31-ipc/ipc/util.c
@@ -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;
 }

ipc/util.h renamed from base/linux-2.5.31/ipc/util.h +20 -7

diff -urN -X ../dontdiff ../base/linux-2.5.31/ipc/util.h 2.5.31-ipc/ipc/util.h
@@ -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)

Hugh Dickins

2002-08-21 23:32 UTC #5 lore raw

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

Quoted 7 lines · mingming cao

Quoted 5 lines
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

mingming cao

author

2002-08-23 00:32 UTC #6 lore raw

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

Quoted 13 lines · Hugh Dickins

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.

Quoted 10 lines

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.

Quoted 1 line

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

I like it better too.:-)

Mingming