Skip to contentSkip to conversation

Optimize semtimedop

RFC PATCH New Chris Mason 4 participants 25 messages Apr 12, 2010 – May 18, 2010

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Optimize semtimedop

We've been poking around in semtimedop for a while now, mostly because it is consistently showing up at the top of the CPU profiles for benchmarking runs on big numa systems. The biggest problem seems to be the IPC lock, and the fact that we hold it for a long time while we loop over different lists and try to do semaphore operations.

Zach Brown came up with a set of patches a while ago that switched away from the global pending list, and semtimedop was recently optimized for the single sop case by Nick and Manfred.

This patch series tries to build on ideas from all of these patches. The list of pending semaphore operations is pushed down to the individual semaphore and the locking is also pushed down into the semaphore. The result is much faster with my micro benchmark:

http://oss.oracle.com/~mason/sembench.c

It more than doubles the total number of post/wait cycles the benchmark is able to get in 30s. Before this patch, semtimedop scored about the same as futexes for the post/wait cycles, and so now it is 2x faster.

I did run this code through all of the ltp ipc tests, and later this week I hope to get a full tpc database benchmark on it.

#1 lore raw

PATCH 1/2 ipc semaphores: reduce ipc_lock contention in semtimedop

One feature of the ipc semaphores is they are defined to be atomic for the full set of operations done per syscall. So if you do a semtimedop syscall changing 100 semaphores, the kernel needs to try all 100 changes and only apply them when all 100 are able to succeed without putting the process to sleep.

Today we use a single lock per semaphore array (the ipc lock). This lock is held every time we try a set of operations requested by userland, and when taken again when a process is woken up.

Whenever a given set of changes sent to semtimedop would sleep, that set is queued up on a big list of pending changes for the entire semaphore array.

Whenever a semtimedop call changes a single semaphore value, it walks the entire list of pending operations to see if any of them can now succeed. The ipc lock is held for this entire loop.

This change makes two major changes, pushing both the list of pending operations and a spinlock down to each individual semaphore. Now:

Whenever a given semaphore modification is going to block, the set of operations semtimedop wants to do is saved onto that semaphore's list.

Whenever a givem semtimedop call changes a single semaphore value, it walks the list of pending operations on that single semaphore to see if they can now succeed. If any of the operations will block on a different semaphore, they are moved to that semaphore's list.

The locking is now done per-semaphore. In order to get the changes done atomically, the lock of every semaphore being changed is taken while we test the requested operations. We sort the operations by semaphore id to make sure we don't deadlock in the kernel.

I have a microbenchmark to test how quickly we can post and wait in bulk. With this change, semtimedop is able do to more than twice as much work in the same run. On a large numa machine, it brings the IPC lock system time (reported by perf) down from 85% to 15%.

---
 include/linux/sem.h |    4 +-
 ipc/sem.c           |  504 +++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 372 insertions(+), 136 deletions(-)
include/linux/sem.h +1 -3
index 8a4adbe..8b97b51 100644
@@ -86,6 +86,7 @@ struct task_struct;
 struct sem {
 	int	semval;		/* current value */
 	int	sempid;		/* pid of last operation */
+	spinlock_t		lock;
 	struct list_head sem_pending; /* pending single-sop operations */
 };
 
@@ -95,15 +96,12 @@ struct sem_array {
 	time_t			sem_otime;	/* last semop time */
 	time_t			sem_ctime;	/* last change time */
 	struct sem		*sem_base;	/* ptr to first semaphore in array */
-	struct list_head	sem_pending;	/* pending operations to be processed */
 	struct list_head	list_id;	/* undo requests on this array */
 	int			sem_nsems;	/* no. of semaphores in array */
-	int			complex_count;	/* pending complex operations */
 };
 
 /* One queue for each sleeping process in the system. */
 struct sem_queue {
-	struct list_head	simple_list; /* queue of pending operations */
 	struct list_head	list;	 /* queue of pending operations */
 	struct task_struct	*sleeper; /* this process */
 	struct sem_undo		*undo;	 /* undo structure */
ipc/sem.c +371 -133

759 lines not on this page · raw message

Signature · 1 line
1.7.0.3
#2 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Hi Chris,

Quoted 10 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Quoted 15 lines

SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
unsigned, nsops, const struct timespec __user *, timeout)
{

ipc/sem.c +2 -0
@@ -1129,6 +1306,8 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
  	struct sem_queue queue;
  	unsigned long jiffies_left = 0;
  	struct ipc_namespace *ns;
+	struct sem *blocker = NULL;
+	LIST_HEAD(pending);
 
  	ns = current->nsproxy->ipc_ns;
 
@@ -1168,6 +1347,14 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
  			alter = 1;
  	}

ipc/sem.c SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops, · line 1358

Quoted 10 lines
ipc/sem.c +8 -0
 
+	/*
+	 * try_atomic_semop takes all the locks of all the semaphores in
+	 * the sops array.  We have to make sure we don't deadlock if userland
+	 * happens to send them out of order, so we sort them by semnum.
+	 */
+	if (nsops>  1)
+		sort(sops, nsops, sizeof(*sops), sembuf_compare, NULL);
+
 

Does sorting preserve the behavior?

#3 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 13 lines · Manfred Spraul

Hi Chris,

Quoted 9 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Quoted 6 lines

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Do you mean within a single sop array doing all three of these? I don't know if the sort is going to leave the three operations on semaphore 5 in the same order (it probably won't).

But I could change that by having it include the slot in the original sop array in the sorting. That way if we have duplicate semnums in the array, they will end up in the same position relative to each other in the sorted result.

(ewwww ;)

-chris

#4 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 25 lines · Chris Mason
Quoted 13 lines · Manfred Spraul

Hi Chris,

Quoted 9 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Quoted 6 lines

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Do you mean within a single sop array doing all three of these? I don't know if the sort is going to leave the three operations on semaphore 5 in the same order (it probably won't).

Quoted 6 lines

But I could change that by having it include the slot in the original sop array in the sorting. That way if we have duplicate semnums in the array, they will end up in the same position relative to each other in the sorted result.

(ewwww ;)

I had a bit of a hack at doing per-semaphore stuff when I was looking at the first optimization, but it was tricky to make it work.

The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

#5 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 33 lines · Nick Piggin
Quoted 25 lines · Chris Mason
Quoted 13 lines · Manfred Spraul

Hi Chris,

Quoted 9 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Quoted 6 lines

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Do you mean within a single sop array doing all three of these? I don't know if the sort is going to leave the three operations on semaphore 5 in the same order (it probably won't).

Quoted 6 lines

But I could change that by having it include the slot in the original sop array in the sorting. That way if we have duplicate semnums in the array, they will end up in the same position relative to each other in the sorted result.

(ewwww ;)

Quoted 8 lines

I had a bit of a hack at doing per-semaphore stuff when I was looking at the first optimization, but it was tricky to make it work.

The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Quoted 7 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids. Zach's simpler API is cooking too, but if I can get this done without insane complexity it helps with more than just the post/wait oracle workload.

-chris

#6 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 43 lines · Chris Mason
Quoted 33 lines · Nick Piggin
Quoted 25 lines · Chris Mason
Quoted 13 lines · Manfred Spraul

Hi Chris,

Quoted 9 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Quoted 6 lines

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Do you mean within a single sop array doing all three of these? I don't know if the sort is going to leave the three operations on semaphore 5 in the same order (it probably won't).

Quoted 6 lines

But I could change that by having it include the slot in the original sop array in the sorting. That way if we have duplicate semnums in the array, they will end up in the same position relative to each other in the sorted result.

(ewwww ;)

Quoted 8 lines

I had a bit of a hack at doing per-semaphore stuff when I was looking at the first optimization, but it was tricky to make it work.

The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 3 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

Quoted 9 lines
Quoted 6 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids.

Duplicate semids? What do you mean?

Quoted 3 lines

Zach's simpler API is cooking too, but if I can get
this done without insane complexity it helps with more than just the post/wait oracle workload.

Iam worried about complexity and slowing other cases, given that Oracle DB seems willing to adapt to the (better suited) new API. So I'd be interested to know what it helps outside Oracle.

#7 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 51 lines · Nick Piggin
Quoted 43 lines · Chris Mason
Quoted 33 lines · Nick Piggin
Quoted 25 lines · Chris Mason
Quoted 13 lines · Manfred Spraul

Hi Chris,

Quoted 9 lines · Chris Mason

/*
+ * when a semaphore is modified, we want to retry the series of operations
+ * for anyone that was blocking on that semaphore. This breaks down into
+ * a few different common operations:
+ *
+ * 1) One modification releases one or more waiters for zero.
+ * 2) Many waiters are trying to get a single lock, only one will get it.
+ * 3) Many modifications to the count will succeed.
+ *

Quoted 6 lines

Have you thought about odd corner cases:
Nick noticed the last time that it is possible to wait for arbitrary values:
in one semop:
- decrease semaphore 5 by 10
- wait until semaphore 5 is 0
- increase semaphore 5 by 10.

Do you mean within a single sop array doing all three of these? I don't know if the sort is going to leave the three operations on semaphore 5 in the same order (it probably won't).

Quoted 6 lines

But I could change that by having it include the slot in the original sop array in the sorting. That way if we have duplicate semnums in the array, they will end up in the same position relative to each other in the sorted result.

(ewwww ;)

Quoted 8 lines

I had a bit of a hack at doing per-semaphore stuff when I was looking at the first optimization, but it was tricky to make it work.

The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 3 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

Quoted 7 lines

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

Ok, fair enough, I'll add the sequence number.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids.

Duplicate semids? What do you mean?

Sorry, semnums...index into the array of semaphores.

Quoted 10 lines
Quoted 5 lines

Zach's simpler API is cooking too, but if I can get
this done without insane complexity it helps with more than just the post/wait oracle workload.

Iam worried about complexity and slowing other cases, given that Oracle DB seems willing to adapt to the (better suited) new API. So I'd be interested to know what it helps outside Oracle.

Sure, I'd hope that your benchmark from last time around is faster now.

-chris

#8 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 23 lines · Chris Mason
Quoted 10 lines · Nick Piggin

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

Ok, fair enough, I'll add the sequence number.

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Yeah, that's why my patches include code to handle userland sending duplicate semids.

Duplicate semids? What do you mean?

Sorry, semnums...index into the array of semaphores.

OK, I wonder just how much it helps, and what.

Quoted 10 lines
Quoted 8 lines
Quoted 3 lines

Zach's simpler API is cooking too, but if I can get
this done without insane complexity it helps with more than just the post/wait oracle workload.

Iam worried about complexity and slowing other cases, given that Oracle DB seems willing to adapt to the (better suited) new API. So I'd be interested to know what it helps outside Oracle.

Sure, I'd hope that your benchmark from last time around is faster now.

I didn't actually reproduce it here, I think it was a customer or partner workload. But SAP only seemed to have one contended semnum in its array, and it was being operated on with "simple" semops (so that's about as far as the patches went).

I didn't notice anything that should make that go faster?

Yes, with such a workload, using semops is basically legacy and simple mutexes should work better. So I'm not outright against improving sysv sem performance for more complex cases where nothing else we have works as well.

#9 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 24 lines · Nick Piggin
Quoted 23 lines · Chris Mason
Quoted 10 lines · Nick Piggin

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

Ok, fair enough, I'll add the sequence number.

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Yeah, that's why my patches include code to handle userland sending duplicate semids.

Duplicate semids? What do you mean?

Sorry, semnums...index into the array of semaphores.

OK, I wonder just how much it helps, and what.

Detecting the dups just keeps me from deadlocking. I'm locking each individual semaphore in sequence, so if userland does something strange and sends two updates to the same semaphore, the code detects that and only locks the first one.

Quoted 11 lines
Quoted 11 lines
Quoted 10 lines
Quoted 5 lines

Zach's simpler API is cooking too, but if I can get
this done without insane complexity it helps with more than just the post/wait oracle workload.

Iam worried about complexity and slowing other cases, given that Oracle DB seems willing to adapt to the (better suited) new API. So I'd be interested to know what it helps outside Oracle.

Quoted 8 lines
Quoted 1 line

Sure, I'd hope that your benchmark from last time around is faster now.

I didn't actually reproduce it here, I think it was a customer or partner workload. But SAP only seemed to have one contended semnum in its array, and it was being operated on with "simple" semops (so that's about as far as the patches went).

I didn't notice anything that should make that go faster?

Since I'm avoiding the ipc lock while operating on the array, it'll help any workload that hits on two or more semaphores in the array at once.

Quoted 6 lines

Yes, with such a workload, using semops is basically legacy and simple mutexes should work better. So I'm not outright against improving sysv sem performance for more complex cases where nothing else we have works as well.

I'm not in a hurry to overhaul a part of the kernel that has been stable for a long time. But it really needs some love I think. I'll have more numbers from a tpc run later this week.

-chris

#10 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 6 lines · Chris Mason
Quoted 1 line · Nick Piggin

I didn't notice anything that should make that go faster?

Since I'm avoiding the ipc lock while operating on the array, it'll help any workload that hits on two or more semaphores in the array at once.

Yeah, I don't think SAP did that, significantly to matter. Possibly some (aside from Oracle of course), do though.

Quoted 9 lines
Quoted 5 lines

Yes, with such a workload, using semops is basically legacy and simple mutexes should work better. So I'm not outright against improving sysv sem performance for more complex cases where nothing else we have works as well.

I'm not in a hurry to overhaul a part of the kernel that has been stable for a long time. But it really needs some love I think. I'll have more numbers from a tpc run later this week.

Yep, I'm not against it. "industry standard benchmark" numbers would be great.

I do think we need to be really careful with semantics though. The API's been around for long enough that it is going to have been (ab)used in every way possible :)

#11 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 4 lines · Chris Mason

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

Quoted 9 lines

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

The management process won't get the sem on Linux either:
Linux implements FIFO, but there is no protection at all against starvation.

If I understand the benchmark numbers correctly, a 4-core, 2 GHz Phenom is able to do ~ 2 million semaphore operations per second in one semaphore array. That's the limit - cache line trashing on the sma structure prevent higher numbers.

For a NUMA system, the limit is probably lower.

Chris:
Do you have an estimate how many semop() your app will perform in one array?

Perhaps we should really remove the per-array list, sma->sem_perm.lock and sma->sem_otime.

--
Manfred

#12 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 25 lines · Manfred Spraul
Quoted 7 lines · Nick Piggin
Quoted 3 lines · Chris Mason

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

Quoted 8 lines

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Then you could have some overall management process for example which tries to take both sems. It will never get it.

The management process won't get the sem on Linux either:
Linux implements FIFO, but there is no protection at all against starvation.

If I understand the benchmark numbers correctly, a 4-core, 2 GHz Phenom is able to do ~ 2 million semaphore operations per second in one semaphore array.
That's the limit - cache line trashing on the sma structure prevent higher numbers.

Quoted 4 lines

For a NUMA system, the limit is probably lower.

Chris:
Do you have an estimate how many semop() your app will perform in one array?

There are two different workloads at play. The first is to just use semaphores as a lock, which is a traditional mutex type operation (one at a time). This isn't a problem with the current code, aside from lock contention created by the second case.

The second case is batched wakeup. One process will wake hundreds or more at once that are each waiting on their own semaphore.

Quoted 3 lines

Perhaps we should really remove the per-array list, sma->sem_perm.lock and sma->sem_otime.

So far for our uses the per-array list was the biggest trouble. I tried to benchmark your patches on Friday, but these are preproduction systems and it appears to have woken up in a bad mood.

The hardware guys are giving it some TLC and I'll be able to run on Monday.

-chris

#13 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

In reply to Manfred Spraul
Quoted 13 lines · Manfred Spraul
Quoted 12 lines · Nick Piggin
Quoted 3 lines · Chris Mason

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

Yes, because it's not just a theoretical livelock, it can be basically a certainty, given the right pattern of semops.

You could have two mostly-independent groups of processes, each taking and releasing a different sem, which are always contended (eg. if it is being used for a producer-consumer type situation, or even just mutual exclusion with high contention).

Quoted 5 lines
Quoted 3 lines

Then you could have some overall management process for example which tries to take both sems. It will never get it.

The management process won't get the sem on Linux either:
Linux implements FIFO, but there is no protection at all against starvation.

Yeah I did realise this after I posted. But anyway I think FIFO is reasonable to have, although you *may* be able to justify removing it after your research of other UNIXes, if there are sufficient gains.

Quoted 17 lines

If I understand the benchmark numbers correctly, a 4-core, 2 GHz Phenom is able to do ~ 2 million semaphore operations per second in one semaphore array.
That's the limit - cache line trashing on the sma structure prevent higher numbers.

For a NUMA system, the limit is probably lower.

Chris:
Do you have an estimate how many semop() your app will perform in one array?

Perhaps we should really remove the per-array list, sma->sem_perm.lock and sma->sem_otime.

--
Manfred

#14 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

In reply to Chris Mason
Quoted 10 lines · Chris Mason
Quoted 8 lines · Nick Piggin

On Tue, Apr 13, 2010 at 01:39:41PM -0400, Chris Mason wrote:

The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 5 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

How do you want to determine the sequence number?
Is atomic_inc_return() on a per-semaphore array counter sufficiently fast?

Quoted 4 lines
Quoted 4 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

Quoted 9 lines
Quoted 3 lines

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids. Zach's simpler API is cooking too, but if I can get this done without insane complexity it helps with more than just the post/wait oracle workload.

What is the oracle workload, which multi-sembuf operations does it use? How many semaphores are in one array?

When the last optimizations were written, I've searched a bit:
- postgres uses per-process semaphores, with small semaphore arrays. [process sleeps on it's own semaphore and is woken up by someone
else when it can make progress]
- with google, I couldn't find anything relevant that uses multi-sembuf semop() calls.

And I agree with Nick: We should be careful about changing the API.

--
Manfred

#15 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 8 lines · Manfred Spraul
Quoted 7 lines · Chris Mason
Quoted 6 lines · Nick Piggin

On Tue, Apr 13, 2010 at 01:39:41PM -0400, Chris Mason wrote:
The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 6 lines
Quoted 4 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

How do you want to determine the sequence number?
Is atomic_inc_return() on a per-semaphore array counter sufficiently fast?

I haven't tried yet, but hopefully it won't be a problem. A later patch does atomics on the reference count and it doesn't show up in the profiles.

Quoted 12 lines
Quoted 5 lines
Quoted 5 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

Quoted 7 lines
Quoted 2 lines

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids. Zach's simpler API is cooking too, but if I can get this done without insane complexity it helps with more than just the post/wait oracle workload.

Quoted 7 lines

What is the oracle workload, which multi-sembuf operations does it use? How many semaphores are in one array?

When the last optimizations were written, I've searched a bit:
- postgres uses per-process semaphores, with small semaphore arrays. [process sleeps on it's own semaphore and is woken up by someone
else when it can make progress]

This is similar to Oracle (and the sembench program). Each process has a semaphore and when it is waiting for a commit it goes to sleep on it. They are woken up in bulk with semtimedop calls from a single process.

But oracle also uses semaphores for locking in a traditional sense.

Putting the waiters into a per-semaphore list is really only part of the speedup. The real boost comes from the patch to break up the locks into a per semaphore lock.

We gain another 10-15% from a later patch that gets uses atomics on the refcount, which lets us do sem_putref without a lock (meaning we're lockless once we get woken up).

I'm cleaning up fixes based on suggestions here and will repost.

Quoted 3 lines

- with google, I couldn't find anything relevant that uses multi-sembuf semop() calls.

I think this should help any workload that has more than one semaphore per array, even if they only do one sem per call.

Quoted 1 line

And I agree with Nick: We should be careful about changing the API.

Definitely, thanks for reading through it.

-chris

#16 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 43 lines · Chris Mason
Quoted 11 lines · Manfred Spraul
Quoted 9 lines · Chris Mason
Quoted 7 lines · Nick Piggin

On Tue, Apr 13, 2010 at 01:39:41PM -0400, Chris Mason wrote:
The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 8 lines
Quoted 5 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

How do you want to determine the sequence number?
Is atomic_inc_return() on a per-semaphore array counter sufficiently fast?

I haven't tried yet, but hopefully it won't be a problem. A later patch does atomics on the reference count and it doesn't show up in the profiles.

Quoted 17 lines
Quoted 5 lines
Quoted 5 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

Quoted 9 lines
Quoted 3 lines

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids. Zach's simpler API is cooking too, but if I can get this done without insane complexity it helps with more than just the post/wait oracle workload.

What is the oracle workload, which multi-sembuf operations does it use? How many semaphores are in one array?

Quoted 10 lines
Quoted 5 lines

When the last optimizations were written, I've searched a bit:
- postgres uses per-process semaphores, with small semaphore arrays. [process sleeps on it's own semaphore and is woken up by someone
else when it can make progress]

This is similar to Oracle (and the sembench program). Each process has a semaphore and when it is waiting for a commit it goes to sleep on it. They are woken up in bulk with semtimedop calls from a single process.

Hmm. Thus you have:
- single sembuf decrease operations that are waiting frequently.
- multi-sembuf increase operations.

What about optimizing for that case?
Increase operations succeed immediately. Thus complex_count is 0.

If we have performed an update operation, then we can scan all simple_lists that have seen an increase instead of checking the global list - as long as there are no complex operations waiting. Right now, we give up if the update operation was a complex operation - but that does not matter.
All that matters are the sleeping operations, not the operation that did the wakeup.
I've attached an untested idea.

Quoted 7 lines

But oracle also uses semaphores for locking in a traditional sense.

Putting the waiters into a per-semaphore list is really only part of the speedup. The real boost comes from the patch to break up the locks into a per semaphore lock.

Ok. Then simple tricks won't help.
How many semaphores are in one array?

--
Manfred

ipc/sem.c +12 -2
index dbef95b..8986239 100644
@@ -1224,8 +1224,18 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 
 	error = try_atomic_semop (sma, sops, nsops, un, task_tgid_vnr(current));
 	if (error <= 0) {
-		if (alter && error == 0)
-			update_queue(sma, (nsops == 1) ? sops[0].sem_num : -1);
+		if (alter && error == 0) {
+			if (sma->complex_count) {
+				update_queue(sma, -1);
+			} else {
+				int i;
+				
+				for (i=0;i<nsops;i++) {
+					if (sops[i].sem_op > 0)
+						update_queue(sma, sops[i].sem_num);
+				}
+			}
+		}
 
 		goto out_unlock_free;
 	}
#17 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 42 lines · Manfred Spraul
Quoted 33 lines · Chris Mason
Quoted 8 lines · Manfred Spraul
Quoted 7 lines · Chris Mason
Quoted 6 lines · Nick Piggin

On Tue, Apr 13, 2010 at 01:39:41PM -0400, Chris Mason wrote:
The other thing I don't know if your patch gets right is requeueing on of the operations. When you requeue from one list to another, then you seem to lose ordering with other pending operations, so that would seem to break the API as well (can't remember if the API strictly mandates FIFO, but anyway it can open up starvation cases).

Quoted 6 lines
Quoted 4 lines

I don't see anything in the docs about the FIFO order. I could add an extra sort on sequence number pretty easily, but is the starvation case really that bad?

How do you want to determine the sequence number?
Is atomic_inc_return() on a per-semaphore array counter sufficiently fast?

I haven't tried yet, but hopefully it won't be a problem. A later patch does atomics on the reference count and it doesn't show up in the profiles.

Quoted 14 lines
Quoted 11 lines
Quoted 6 lines

I was looking at doing a sequence number to be able to sort these, but it ended up getting over complex (and SAP was only using simple ops so it didn't seem to need much better).

We want to be careful not to change semantics at all. And it gets tricky quickly :( What about Zach's simpler wakeup API?

Yeah, that's why my patches include code to handle userland sending duplicate semids. Zach's simpler API is cooking too, but if I can get this done without insane complexity it helps with more than just the post/wait oracle workload.

What is the oracle workload, which multi-sembuf operations does it use? How many semaphores are in one array?

Quoted 8 lines
Quoted 4 lines

When the last optimizations were written, I've searched a bit:
- postgres uses per-process semaphores, with small semaphore arrays. [process sleeps on it's own semaphore and is woken up by someone
else when it can make progress]

This is similar to Oracle (and the sembench program). Each process has a semaphore and when it is waiting for a commit it goes to sleep on it. They are woken up in bulk with semtimedop calls from a single process.

Quoted 6 lines

Hmm. Thus you have:
- single sembuf decrease operations that are waiting frequently.
- multi-sembuf increase operations.

What about optimizing for that case?
Increase operations succeed immediately. Thus complex_count is 0.

I've been wondering about that. I can optimize the patch to special case the increase operations. The only problem I saw was checking or the range overflow. Current behavior will abort the whole set if the range overflow happens.

Quoted 9 lines

If we have performed an update operation, then we can scan all simple_lists that have seen an increase instead of checking the global list - as long as there are no complex operations waiting. Right now, we give up if the update operation was a complex operation - but that does not matter.
All that matters are the sleeping operations, not the operation that did the wakeup.
I've attached an untested idea.

Zach Brown's original patch set tried just the list magic and not the spinlocks. I'm afraid it didn't help very much over all.

Quoted 9 lines
Quoted 7 lines

But oracle also uses semaphores for locking in a traditional sense.

Putting the waiters into a per-semaphore list is really only part of the speedup. The real boost comes from the patch to break up the locks into a per semaphore lock.

Ok. Then simple tricks won't help.
How many semaphores are in one array?

On a big system I saw about 4000 semaphores total. The database will just allocate as many as it can into a single array and keep creating arrays until it has all it needs.

-chris

#18 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 5 lines · Chris Mason

On a big system I saw about 4000 semaphores total. The database will just allocate as many as it can into a single array and keep creating arrays until it has all it needs.

What happens if SEMMSL is reduced (first entry in /proc/sys/kernel/sem)?

--
Manfred

#19 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 6 lines · Manfred Spraul
Quoted 4 lines · Chris Mason

On a big system I saw about 4000 semaphores total. The database will just allocate as many as it can into a single array and keep creating arrays until it has all it needs.

What happens if SEMMSL is reduced (first entry in /proc/sys/kernel/sem)?

Performance improves slightly but the ipc lock is still at the top of the profile ;)

-chris

#20 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

In reply to Nick Piggin
Quoted 1 line

What about Zach's simpler wakeup API?

It's making slow progress in the background as a longer-term experiment.

http://oss.oracle.com/~zab/wake-many/

That URL still has an API description, patches, and little test utilities for the simple first draft.

- z

#21 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

In reply to Chris Mason
Quoted 6 lines · Chris Mason

I have a microbenchmark to test how quickly we can post and wait in bulk. With this change, semtimedop is able do to more than twice as much work in the same run. On a large numa machine, it brings the IPC lock system time (reported by perf) down from 85% to 15%.

Looking at the current code:
- update_queue() can be O(N^2) if only some of the waiting tasks are woken up.
Actually: all non-woken up tasks are rescanned after a task that can be woken up is found.

- Your test app tests the best case for the current code:
You wake up the tasks in the same order as the called semop().
If you invert the order (i.e.: worklist_add() adds to head instead of tail), I would expect an even worse performance of the current code.

The O(N^2) is simple to fix, I've attached a patch.
For your micro-benchmark, the patch does not change much: you wake-up in-order, thus the current code does not misbehave.

Do you know how Oracle wakes up the tasks?
FIFO, LIFO, un-ordered?

Quoted 24 lines
	while(unlikely(error == IN_WAKEUP)) {

cpu_relax();
error = queue.status;
}

(quoted diff) +18 -1
-	if (error != -EINTR) {
+	/*
+	 * we are lock free right here, and we could have timed out or
+	 * gotten a signal, so we need to be really careful with how we
+	 * play with queue.status.  It has three possible states:
+	 *
+	 * -EINTR, which means nobody has changed it since we slept.  This
+	 * means we woke up on our own.
+	 *
+	 * IN_WAKEUP, someone is currently waking us up.  We need to loop
+	 * here until they change it to the operation error value.  If
+	 * we don't loop, our process could exit before they are done waking us
+	 *
+	 * operation error value: we've been properly woken up and can exit
+	 * at any time.
+	 *
+	 * If queue.status is currently -EINTR, we are still being processed
+	 * by the semtimedop core.  Someone either has us on a list head
+	 * or is currently poking our queue struct.  We need to find that

Review

Quoted 10 lines
(quoted diff) +8 -0
+	 * reference and remove it, which is what remove_queue_from_lists
+	 * does.
+	 *
+	 * We always check for both -EINTR and IN_WAKEUP because we have no
+	 * locks held.  Someone could change us from -EINTR to IN_WAKEUP at
+	 * any time.
+	 */
+	if (error != -EINTR&&  error != IN_WAKEUP) {
  		/* fast path: update_queue already obtained all requested
  		 * resources */

No: The code accesses a local variable. The loop above the comment guarantees that the error can't be IN_WAKEUP.

Review

Quoted 5 lines
(quoted diff) +4 -0
+
+out_putref:
+	sem_putref(sma);
+	goto out_free;

Is it possible to move the sem_putref into wakeup_sem_queue()? Right now, the exit path of semtimedop doesn't touch the spinlock. You remove that optimization.

--
Manfred

ipc/sem.c +98 -14
index dbef95b..efadb6d 100644
@@ -434,6 +434,69 @@ static void unlink_queue(struct sem_array *sma, struct sem_queue *q)
 		sma->complex_count--;
 }
 
+/** check_restart(sma, q)
+ * @sma: semaphore array
+ * @q: the operation that just completed
+ *
+ * update_queue is O(N^2) when it restarts scanning the whole queue of
+ * waiting operations. Therefore this function checks if the restart is
+ * really necessary. It is called after a previously waiting operation
+ * was completed.
+ */
+static int check_restart(struct sem_array *sma, struct sem_queue *q)
+{
+	struct sem * curr;
+	struct sem_queue *h;
+
+	/* if the operation didn't modify the array, then no restart */
+	if (q->alter == 0)
+		return 0;
+
+	/* pending complex operations are too difficult to analyse */
+	if (sma->complex_count)
+		return 1;
+
+	/* we were a sleeping complex operation. Too difficult */
+	if (q->nsops > 1)
+		return 1;
+
+	curr = sma->sem_base + q->sops[0].sem_num;
+
+	/* No-one waits on this queue */
+	if (list_empty(&curr->sem_pending))
+		return 0;
+
+	/* the new semaphore value */
+	if (curr->semval) {
+		/* It is impossible that someone waits for the new value:
+		 * - q is a previously sleeping simple operation that
+		 *   altered the array. It must be a decrement, because
+		 *   simple increments never sleep.
+		 * - The value is not 0, thus wait-for-zero won't proceed.
+		 * - If there are older (higher priority) decrements
+		 *   in the queue, then they have observed the original
+		 *   semval value and couldn't proceed. The operation
+		 *   decremented to value - thus they won't proceed either.
+		 */
+		BUG_ON(q->sops[0].sem_op >= 0);
+		return 0;
+	}
+	/*
+	 * semval is 0. Check if there are wait-for-zero semops.
+	 * They must be the first entries in the per-semaphore simple queue
+	 */
+	h=list_first_entry(&curr->sem_pending, struct sem_queue, simple_list);
+	BUG_ON(h->nsops != 1);
+	BUG_ON(h->sops[0].sem_num != q->sops[0].sem_num);
+	
+	/* Yes, there is a wait-for-zero semop. Restart */	
+	if (h->sops[0].sem_op == 0)
+		return 1;
+
+	/* Again - no-one is waiting for the new value. */
+	return 0;
+}		
+
 
 /**
  * update_queue(sma, semnum): Look for tasks that can be completed.
@@ -469,7 +532,7 @@ static void update_queue(struct sem_array *sma, int semnum)
 again:
 	walk = pending_list->next;
 	while (walk != pending_list) {
-		int error, alter;
+		int error, restart;
 
 		q = (struct sem_queue *)((char *)walk - offset);
 		walk = walk->next;
@@ -494,22 +557,42 @@ again:
 
 		unlink_queue(sma, q);
 
-		/*
-		 * The next operation that must be checked depends on the type
-		 * of the completed operation:
-		 * - if the operation modified the array, then restart from the
-		 *   head of the queue and check for threads that might be
-		 *   waiting for the new semaphore values.
-		 * - if the operation didn't modify the array, then just
-		 *   continue.
-		 */
-		alter = q->alter;
+		if (error)
+			restart = 0;
+		else
+			restart = check_restart(sma, q);
+
 		wake_up_sem_queue(q, error);
-		if (alter && !error)
+		if (restart)
 			goto again;
 	}
 }
 
+/** do_smart_update(sma, sops, nsops): Optimized update_queue
+ * @sma: semaphore array
+ * @sops: operations that were performed
+ * @nsops: number of operations
+ *
+ * do_smart_update() does the required called to update_queue, based on the
+ * actual changes that were performed on the semaphore array.
+ */
+void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsops)
+{
+	int i;
+
+	if (sma->complex_count) {
+		update_queue(sma, -1);
+		return;
+	}
+				
+	for (i=0;i<nsops;i++) {
+		if (sops[i].sem_op > 0 ||
+			(sops[i].sem_op < 0 && sma->sem_base[sops[i].sem_num].semval == 0))
+			update_queue(sma, sops[i].sem_num);
+	}
+}
+
+
 /* The following counts are associated to each semaphore:
  *   semncnt        number of tasks waiting on semval being nonzero
  *   semzcnt        number of tasks waiting on semval being zero
@@ -1224,8 +1307,9 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 
 	error = try_atomic_semop (sma, sops, nsops, un, task_tgid_vnr(current));
 	if (error <= 0) {
-		if (alter && error == 0)
-			update_queue(sma, (nsops == 1) ? sops[0].sem_num : -1);
+		if (alter && error == 0) {
+			do_smart_update(sma, sops, nsops);
+		}
 
 		goto out_unlock_free;
 	}
#22 lore raw

Re: [PATCH 1/2] ipc semaphores: reduce ipc_lock contention in semtimedop

Quoted 12 lines · Manfred Spraul
Quoted 5 lines · Chris Mason

I have a microbenchmark to test how quickly we can post and wait in bulk. With this change, semtimedop is able do to more than twice as much work in the same run. On a large numa machine, it brings the IPC lock system time (reported by perf) down from 85% to 15%.

Looking at the current code:
- update_queue() can be O(N^2) if only some of the waiting tasks are woken up.
Actually: all non-woken up tasks are rescanned after a task that can be woken up is found.

Quoted 7 lines

- Your test app tests the best case for the current code:
You wake up the tasks in the same order as the called semop(). If you invert the order (i.e.: worklist_add() adds to head instead of tail), I would expect an even worse performance of the current code.

The O(N^2) is simple to fix, I've attached a patch.

Good point.

Quoted 5 lines

For your micro-benchmark, the patch does not change much: you wake-up in-order, thus the current code does not misbehave.

Do you know how Oracle wakes up the tasks?
FIFO, LIFO, un-ordered?

Ordering in terms of the sem array? I had them try many variations ;) I don't think it will be ordered as well as sembench most of the time.

Quoted 29 lines
Quoted 29 lines
	while(unlikely(error == IN_WAKEUP)) {
(quoted diff) +22 -1
 		cpu_relax();
 		error = queue.status;
 	}
 
-	if (error != -EINTR) {
+	/*
+	 * we are lock free right here, and we could have timed out or
+	 * gotten a signal, so we need to be really careful with how we
+	 * play with queue.status.  It has three possible states:
+	 *
+	 * -EINTR, which means nobody has changed it since we slept.  This
+	 * means we woke up on our own.
+	 *
+	 * IN_WAKEUP, someone is currently waking us up.  We need to loop
+	 * here until they change it to the operation error value.  If
+	 * we don't loop, our process could exit before they are done waking us
+	 *
+	 * operation error value: we've been properly woken up and can exit
+	 * at any time.
+	 *
+	 * If queue.status is currently -EINTR, we are still being processed
+	 * by the semtimedop core.  Someone either has us on a list head
+	 * or is currently poking our queue struct.  We need to find that
+	 * reference and remove it, which is what remove_queue_from_lists
+	 * does.
+	 *
+	 * We always check for both -EINTR and IN_WAKEUP because we have no
Quoted 8 lines

Review

Quoted 6 lines
(quoted diff) +4 -0
+	 * locks held.  Someone could change us from -EINTR to IN_WAKEUP at
+	 * any time.
+	 */
+	if (error != -EINTR&&  error != IN_WAKEUP) {
 		/* fast path: update_queue already obtained all requested
 		 * resources */

No: The code accesses a local variable. The loop above the comment guarantees that the error can't be IN_WAKEUP.

Whoops, thanks.

Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +4 -0
+
+out_putref:
+	sem_putref(sma);
+	goto out_free;

Is it possible to move the sem_putref into wakeup_sem_queue()? Right now, the exit path of semtimedop doesn't touch the spinlock. You remove that optimization.

I'll look at this, we need to be able to go through the sma to remove the process from the lists if it woke up on its own, but I don't see why we can't putref in wakeup.

My current revision of the patch uses an atomic instead of the lock, so it restores the lockless wakeup either way. Still it is better to putref in wakeup.

-chris

#23 lore raw

PATCH 2/2 ipc semaphores: order wakeups based on waiter CPU

In reply to Chris Mason

When IPC semaphores are used in a bulk post and wait system, we can end up waking a very large number of processes per semtimedop call. At least one major database will use a single process to kick hundreds of other processes at a time.

This patch tries to reduce the runqueue lock contention by ordering the wakeups based on the CPU the waiting process was on when it went to sleep.

A later patch could add some code in the scheduler to help wake these up in bulk and take the various runqueue locks less often.

---
 include/linux/sem.h |    1 +
 ipc/sem.c           |   37 ++++++++++++++++++++++++++++++++++++-
 2 files changed, 37 insertions(+), 1 deletions(-)
include/linux/sem.h +1 -0
index 8b97b51..4a37319 100644
@@ -104,6 +104,7 @@ struct sem_array {
 struct sem_queue {
 	struct list_head	list;	 /* queue of pending operations */
 	struct task_struct	*sleeper; /* this process */
+	unsigned long		sleep_cpu;
 	struct sem_undo		*undo;	 /* undo structure */
 	int    			pid;	 /* process id of requesting process */
 	int    			status;	 /* completion status of operation */
ipc/sem.c +36 -1
index 335cd35..07fe1d5 100644
@@ -544,6 +544,25 @@ static void wake_up_sem_queue(struct sem_queue *q, int error)
 	preempt_enable();
 }
 
+/*
+ * sorting helper for struct sem_queues in a list.  This is used to
+ * sort by the CPU they are likely to be on when waking them.
+ */
+int list_comp(void *priv, struct list_head *a, struct list_head *b)
+{
+	struct sem_queue *qa;
+	struct sem_queue *qb;
+
+	qa = list_entry(a, struct sem_queue, list);
+	qb = list_entry(b, struct sem_queue, list);
+
+	if (qa->sleep_cpu < qb->sleep_cpu)
+		return -1;
+	if (qa->sleep_cpu > qb->sleep_cpu)
+		return 1;
+	return 0;
+}
+
 /**
  * update_queue(sma, semnum): Look for tasks that can be completed.
  * @sma: semaphore array.
@@ -557,6 +576,7 @@ static void update_queue(struct sem_array *sma, struct list_head *pending_list)
 	struct sem_queue *q;
 	LIST_HEAD(new_pending);
 	LIST_HEAD(work_list);
+	LIST_HEAD(wake_list);
 
 	/*
 	 * this seems strange, but what we want to do is process everything
@@ -591,7 +611,10 @@ again:
 			spin_unlock(&blocker->lock);
 			continue;
 		}
-		wake_up_sem_queue(q, error);
+		if (error)
+			wake_up_sem_queue(q, error);
+		else
+			list_add_tail(&q->list, &wake_list);
 
 	}
 
@@ -599,6 +622,13 @@ again:
 		list_splice_init(&new_pending, &work_list);
 		goto again;
 	}
+
+	list_sort(NULL, &wake_list, list_comp);
+	while (!list_empty(&wake_list)) {
+		q = list_entry(wake_list.next, struct sem_queue, list);
+		list_del_init(&q->list);
+		wake_up_sem_queue(q, 0);
+	}
 }
 
 /* The following counts are associated to each semaphore:
@@ -1440,6 +1470,11 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 	queue.status = -EINTR;
 	queue.sleeper = current;
 
+	/*
+	 * the sleep_cpu number allows sorting by the CPU we expect
+	 * their runqueue entry to be on..hopefully faster for waking up
+	 */
+	queue.sleep_cpu = my_cpu_offset;
 	current->state = TASK_INTERRUPTIBLE;
 
 	/*
Signature · 1 line
1.7.0.3
#24 lore raw

Re: [PATCH 2/2] ipc semaphores: order wakeups based on waiter CPU

Hi Chris,

Review again: · line 633

Quoted 13 lines · Chris Mason
(quoted diff) +7 -0
@@ -599,6 +622,13 @@ again:
  		list_splice_init(&new_pending,&work_list);
  		goto again;
  	}
+
+	list_sort(NULL,&wake_list, list_comp);
+	while (!list_empty(&wake_list)) {
+		q = list_entry(wake_list.next, struct sem_queue, list);
+		list_del_init(&q->list);
+		wake_up_sem_queue(q, 0);
+	}
  }
 

What about moving this step much later?

There is no need to hold any locks for the actual wake_up_process().

I've updated my patch:
- improved update_queue that guarantees no O(N^2) for your workload.
- move the actual wake-up after dropping all locks
- optimize setting sem_otime
- cacheline align the ipc spinlock.

But the odd thing:
It doesn't improve the sembench result at all (AMD Phenom X4) The only thing that is reduced is the system time:
From ~1 min system time for "sembench -t 250 -w 250 -r 30 -o 0" to ~30 sec.

cpu binding the sembench threads results in an improvement of ~50% - at the cost of a significant increase of the system time (from 30 seconds to 1 min) and the user time (from 2 seconds to 14 seconds).

Are you sure that the problem is contention on the semaphore array spinlock?
With the above changes, the code that is under the spin_lock is very short.
Especially:
- Why does optimizing ipc/sem.c only reduce the system time [reported by time] and not the sembench output?
- Why is there no improvement from the ___cache_line_align?
If there would be contention, then there should be trashing from accessing the lock and writing sem_otime and reading sem_base.
- Additionally: you wrote that reducing the array size does not help much.
But: The arrays are 100% independant, the ipc code scales linearly.
Spreading the work over multiple spinlocks is - like cache line aligning - usually a 100% guaranteed improvement if there is contention.

I've attached a modified sembench.c and the proposal for ipc/sem.c Could you try it?
What do you think?
How many cores do you have in your test system?

--
Manfred

include/linux/sem.h +3 -1
index 8a4adbe..66b5fc6 100644
@@ -78,6 +78,7 @@ struct  seminfo {
 
 #ifdef __KERNEL__
 #include <asm/atomic.h>
+#include <linux/cache.h>
 #include <linux/rcupdate.h>
 
 struct task_struct;
@@ -91,7 +92,8 @@ 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 */
+	struct kern_ipc_perm ____cacheline_aligned_in_smp
+				sem_perm;	/* permissions .. see ipc.h */
 	time_t			sem_otime;	/* last semop time */
 	time_t			sem_ctime;	/* last change time */
 	struct sem		*sem_base;	/* ptr to first semaphore in array */
ipc/sem.c +168 -37

345 lines not on this page · raw message

/*
* copyright Oracle 2007. Licensed under GPLv2
* To compile: gcc -Wall -o sembench sembench.c -lpthread
*
* usage: sembench -t thread count -w wakenum -r runtime -o op
* op can be: 0 (ipc sem) 1 (nanosleep) 2 (futexes)
*
* example:
* sembench -t 1024 -w 512 -r 60 -o 2
* runs 1024 threads, waking up 512 at a time, running for 60 seconds using
* futex locking.
*
*/
#define _GNU_SOURCE
#define _POSIX_C_SOURCE 199309
#include <fcntl.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/sem.h>
#include <sys/ipc.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <pthread.h>
#include <unistd.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <sys/syscall.h>
#include <errno.h>

#define VERSION "0.2"

static int g_cpu_bind = 0;
/* futexes have been around since 2.5.something, but it still seems I
* need to make my own syscall. Sigh.
*/

#define FUTEX_WAIT              0
#define FUTEX_WAKE              1
#define FUTEX_FD                2
#define FUTEX_REQUEUE           3
#define FUTEX_CMP_REQUEUE       4
#define FUTEX_WAKE_OP           5
static inline int futex (int *uaddr, int op, int val,
			 const struct timespec *timeout,
			 int *uaddr2, int val3)
{
	return syscall(__NR_futex, uaddr, op, val, timeout, uaddr2, val3);
}

static int all_done = 0;
static int timeout_test = 0;

#define SEMS_PERID 250

struct sem_operations;

struct lockinfo {
	unsigned long id;
	unsigned long index;
	int data;
	pthread_t tid;
	struct lockinfo *next;
	struct sem_operations *ops;
};
struct sem_wakeup_info {
	int wakeup_count;
	struct sembuf sb[SEMS_PERID];
};
struct sem_operations {
	void (*wait)(struct lockinfo *l);
	int (*wake)(struct sem_wakeup_info *wi, int num_semids, int num);
	void (*setup)(struct sem_wakeup_info **wi, int num_semids);
	void (*cleanup)(int num_semids);
	char *name;
};

int *semid_lookup = NULL;

#if 0
pthread_mutex_t worklist_mutex = PTHREAD_MUTEX_INITIALIZER;

void do_lock(void)

{
	pthread_mutex_lock(&worklist_mutex);
}

void do_unlock(void)

{
	pthread_mutex_unlock(&worklist_mutex);
}

#else
static volatile long lock = 1;

void do_lock(void)

{
	int res;

again:

	res = 0;
	asm volatile(
		"lock; xchgb %b0,%1\n\t"
		: "=q" (res)
		: "m" (lock), "0" (res)
		: "memory");
	if (res == 1) {
		if(lock == 1) {
			printf("Lock error 1.\n");
			exit(1);
		}
		return;
	}
	asm volatile("rep; nop \n\t" : : :);
	goto again;
}

void do_unlock(void)

{
	int res = 1;
	
	if(lock) {
		printf("Lock error 2a.\n");
		exit(1);
	}

	asm volatile(
		"lock; xchgb %b0,%1\n\t"
		: "=q" (res)
		: "m" (lock), "0" (res)
		: "memory");
	if (res == 1) {
		printf("lock error 2b.\n");
		exit(1);
	}
}

#endif

static unsigned long total_burns = 0;
static unsigned long min_burns = ~0UL;
static unsigned long max_burns = 0;
static int thread_count = 0;
struct lockinfo *worklist_head = NULL;
struct lockinfo *worklist_tail = NULL;

static void worklist_add(struct lockinfo *l)

{
	do_lock();
	l->next = NULL;
	if (!worklist_head)
		worklist_head = l;
	else
		worklist_tail->next = l;
	worklist_tail = l;
	do_unlock();
}

static struct lockinfo *worklist_rm(void)

{
	struct lockinfo *ret;
	do_lock();
	if (!worklist_head) {
		ret = NULL;
	} else {
		ret = worklist_head;
		worklist_head = ret->next;
		if (!worklist_head)
			worklist_tail = NULL;
	}
	do_unlock();
	return ret;
}

static void do_cpu_bind(int master)

{
	if (g_cpu_bind)
	{
		cpu_set_t cpus;
		pthread_t thread;
		int ret;

		CPU_ZERO(&cpus);

		thread = pthread_self();		

		if (master) {
			CPU_SET(0, &cpus);
		} else {
			ret = pthread_getaffinity_np(thread, sizeof(cpus), &cpus);
			if (ret < 0) {
				printf("pthread_getaffinity_np() failed for thread %p with errno %d.\n",
						thread, errno);
				fflush(stdout);
				return;
			}
 			CPU_CLR(0, &cpus);
		}

		ret = pthread_setaffinity_np(thread, sizeof(cpus), &cpus);
		if (ret < 0) {
			printf("pthread_setaffinity_np failed for thread %p with errno %d.\n",
					thread, errno);
			fflush(stdout);
			return;
		}

		ret = pthread_getaffinity_np(thread, sizeof(cpus), &cpus);
		if (ret < 0) {
			printf("pthread_getaffinity_np() failed for thread %p with errno %d.\n",
					thread, errno);
		} else {
			printf("thread %p: type %d bound to %04lxh\n",thread, master,
					cpus.__bits[0]);
		}
		fflush(stdout);
	}
}

/* ipc semaphore post& wait */
void wait_ipc_sem(struct lockinfo *l)

{
	struct sembuf sb;
	int ret;
	struct timespec *tvp = NULL;
	struct timespec tv = { 0, 1 };

	sb.sem_num = l->index;
	sb.sem_flg = 0;

	sb.sem_op = -1;
	l->data = 1;

	if (timeout_test && (l->id % 5) == 0)
		tvp = &tv;

	worklist_add(l);
	ret = semtimedop(semid_lookup[l->id], &sb, 1, tvp);

	while(l->data != 0 && tvp) {
		struct timespec tv2 = { 0, 500 };
		nanosleep(&tv2, NULL);
	}

	if (l->data != 0) {
		if (tvp)
			return;
		fprintf(stderr, "wakeup without data update\n");
		exit(1);
	}
	if (ret) {
		if (errno == EAGAIN && tvp)
			return;
		perror("semtimed op");
		exit(1);
	}
}

int ipc_wake_some(struct sem_wakeup_info *wi, int num_semids, int num)

{
	int i;
	int ret;
	struct lockinfo *l;
	int found = 0;

	for (i = 0; i < num_semids; i++) {
		wi[i].wakeup_count = 0;
	}
	while(num > 0) {
		struct sembuf *sb;
		l = worklist_rm();
		if (!l)
			break;
		if (l->data != 1)
			fprintf(stderr, "warning, lockinfo data was %d\n",
				l->data);
		l->data = 0;
		sb = wi[l->id].sb + wi[l->id].wakeup_count;
		sb->sem_num = l->index;
		sb->sem_op = 1;
		sb->sem_flg = IPC_NOWAIT;
		wi[l->id].wakeup_count++;
		found++;
		num--;
	}
	if (!found)
		return 0;
	for (i = 0; i < num_semids; i++) {
		int wakeup_total;
		int cur;
		int offset = 0;
		if (!wi[i].wakeup_count)
			continue;
		wakeup_total = wi[i].wakeup_count;
		while(wakeup_total > 0) {
			cur = wakeup_total > 64 ? 64 : wakeup_total;
			ret = semtimedop(semid_lookup[i], wi[i].sb + offset,
					 cur, NULL);
			if (ret) {
				perror("semtimedop");
				exit(1);
			}
			offset += cur;
			wakeup_total -= cur;
		}
	}
	return found;
}

void setup_ipc_sems(struct sem_wakeup_info **wi, int num_semids)

{
	int i;
	*wi = malloc(sizeof(**wi) * num_semids);
	semid_lookup = malloc(num_semids * sizeof(int));
	for(i = 0; i < num_semids; i++) {
		semid_lookup[i] = semget(IPC_PRIVATE, SEMS_PERID,
					 IPC_CREAT | 0777);
		if (semid_lookup[i] < 0) {
			perror("semget");
			exit(1);
		}
	}
	usleep(200);
}

void cleanup_ipc_sems(int num)

{
	int i;
	for (i = 0; i < num; i++) {
		semctl(semid_lookup[i], 0, IPC_RMID);
	}
}

struct sem_operations ipc_sem_ops = {
.wait = wait_ipc_sem,
.wake = ipc_wake_some,
.setup = setup_ipc_sems,
.cleanup = cleanup_ipc_sems,
.name = "ipc sem operations",
};

/* futex post & wait */
void wait_futex_sem(struct lockinfo *l)

{
	int ret;
	l->data = 1;
	worklist_add(l);
	while(l->data == 1) {
		ret = futex(&l->data, FUTEX_WAIT, 1, NULL, NULL, 0);
		if (ret && ret != EWOULDBLOCK) {
			perror("futex wait");
			exit(1);
		}
	}
}

int futex_wake_some(struct sem_wakeup_info *wi, int num_semids, int num)

{
	int i;
	int ret;
	struct lockinfo *l;
	int found = 0;

	for (i = 0; i < num; i++) {
		l = worklist_rm();
		if (!l)
			break;
		if (l->data != 1)
			fprintf(stderr, "warning, lockinfo data was %d\n",
				l->data);
		l->data = 0;
		ret = futex(&l->data, FUTEX_WAKE, 1, NULL, NULL, 0);
		if (ret < 0) {
			perror("futex wake");
			exit(1);
		}
		found++;
	}
	return found;
}

void setup_futex_sems(struct sem_wakeup_info **wi, int num_semids)

{
	return;
}

void cleanup_futex_sems(int num)

{
	return;
}

struct sem_operations futex_sem_ops = {
.wait = wait_futex_sem,
.wake = futex_wake_some,
.setup = setup_futex_sems,
.cleanup = cleanup_futex_sems,
.name = "futex sem operations",
};

/* nanosleep sems here */
void wait_nanosleep_sem(struct lockinfo *l)

{
	int ret;
	struct timespec tv = { 0, 1000000 };
	int count = 0;

	l->data = 1;
	worklist_add(l);
	while(l->data) {
		ret = nanosleep(&tv, NULL);
		if (ret) {
			perror("nanosleep");
			exit(1);
		}
		count++;
	}
}

int nanosleep_wake_some(struct sem_wakeup_info *wi, int num_semids, int num)

{
	int i;
	struct lockinfo *l;

	for (i = 0; i < num; i++) {
		l = worklist_rm();
		if (!l)
			break;
		if (l->data != 1)
			fprintf(stderr, "warning, lockinfo data was %d\n",
				l->data);
		l->data = 0;
	}
	return i;
}

void setup_nanosleep_sems(struct sem_wakeup_info **wi, int num_semids)

{
	return;
}

void cleanup_nanosleep_sems(int num)

{
	return;
}

struct sem_operations nanosleep_sem_ops = {
.wait = wait_nanosleep_sem,
.wake = nanosleep_wake_some,
.setup = setup_nanosleep_sems,
.cleanup = cleanup_nanosleep_sems,
.name = "nano sleep sem operations",
};

void *worker(void *arg)

{
	struct lockinfo *l = (struct lockinfo *)arg;
	int burn_count = 0;
	pthread_t tid = pthread_self();
	size_t pagesize = getpagesize();
	char *buf = malloc(pagesize);
	struct lockinfo *node_local_l;

	if (!buf) {
		perror("malloc");
		exit(1);
	}

	node_local_l = malloc(sizeof(struct lockinfo));
	if (!node_local_l) {
		perror("malloc");
		exit(1);
	}
	memcpy(node_local_l, l, sizeof(*l));
	l = node_local_l;
	node_local_l = (struct lockinfo *)arg;

	do_cpu_bind(0);

	do_lock();
	thread_count++;
	do_unlock();

	l->tid = tid;
	while(!all_done) {
		l->ops->wait(l);
		if (all_done)
			break;
		burn_count++;
	}
	do_lock();
	total_burns += burn_count;
	if (burn_count < min_burns)
		min_burns = burn_count;
	if (burn_count > max_burns)
		max_burns = burn_count;
	thread_count--;
	do_unlock();

	free(node_local_l);
	return (void *)0;
}

void print_usage(void)

{
	printf("usage: sembench [-t threads] [-w wake incr] [-r runtime]");
	printf("                [-o num] (0=ipc, 1=nanosleep, 2=futex)\n");
	printf("                [-b] (cpu bind) [-T] (time test)\n");
	exit(1);
}

#define NUM_OPERATIONS 3
struct sem_operations *allops[NUM_OPERATIONS] = { &ipc_sem_ops,

						&nanosleep_sem_ops,
						&futex_sem_ops};
int main(int ac, char **av) {
	int ret;
	int i;
	int semid = 0;
	int sem_num = 0;
	int burn_count = 0;
	struct sem_wakeup_info *wi = NULL;
	struct timeval start;
	struct timeval now;
	int num_semids = 0;
	int num_threads = 2048;
	int wake_num = 256;
	int run_secs = 30;
	int pagesize = getpagesize();
	char *buf = malloc(pagesize);
	struct sem_operations *ops = allops[0];

	if (!buf) {
		perror("malloc");
		exit(1);
	}
	for (i = 1; i < ac; i++) {
		if (strcmp(av[i], "-t") == 0) {
			if (i == ac -1)
				print_usage();
			num_threads = atoi(av[i+1]);
			i++;
		} else if (strcmp(av[i], "-w") == 0) {
			if (i == ac -1)
				print_usage();
			wake_num = atoi(av[i+1]);
			i++;
		} else if (strcmp(av[i], "-r") == 0) {
			if (i == ac -1)
				print_usage();
			run_secs = atoi(av[i+1]);
			i++;
		} else if (strcmp(av[i], "-o") == 0) {
			int index;
			if (i == ac -1)
				print_usage();
			index = atoi(av[i+1]);
			if (index >= NUM_OPERATIONS) {
				fprintf(stderr, "invalid operations %d\n",
					index);
				exit(1);
			}
			ops = allops[index];
			i++;
		} else if (strcmp(av[i], "-b") == 0) {
			g_cpu_bind = 1;
		}  else if (strcmp(av[i], "-T") == 0) {
			timeout_test = 1;
		} else if (strcmp(av[i], "-h") == 0) {
			print_usage();
		}
	}
	num_semids = (num_threads + SEMS_PERID - 1) / SEMS_PERID;
	ops->setup(&wi, num_semids);

	for (i = 0; i < num_threads; i++) {
		struct lockinfo *l;
		pthread_t tid;

		l = malloc(sizeof(*l));
		if (!l) {
			perror("malloc");
			exit(1);
		}
		l->id = semid;
		l->index = sem_num++;
		l->ops = ops;
		if (sem_num >= SEMS_PERID) {
			semid++;
			sem_num = 0;
		}
		ret = pthread_create(&tid, NULL, worker, (void *)l);
		if (ret) {
			perror("pthread_create");
			exit(1);
		}
		ret = pthread_detach(tid);
		if (ret) {
			perror("pthread_detach");
			exit(1);
		}
	}
	do_cpu_bind(1);
	while(thread_count != num_threads)
		usleep(200);

	while(!worklist_head)
		usleep(200);

	gettimeofday(&start, NULL);
	fprintf(stderr, "main loop going\n");
	while(1) {
		ops->wake(wi, num_semids, wake_num);
		burn_count++;
		gettimeofday(&now, NULL);
		if (now.tv_sec - start.tv_sec >= run_secs)
			break;
	}
	fprintf(stderr, "all done\n");
	all_done = 1;
	while(thread_count > 0) {
		ops->wake(wi, num_semids, wake_num);
		usleep(200);
	}
	printf("%d threads, waking %d at a time\n", num_threads, wake_num);
	printf("using %s\n", ops->name);
	printf("main thread burns: %d\n", burn_count);
	printf("worker burn count total %lu min %lu max %lu avg %lu\n",
	       total_burns, min_burns, max_burns, total_burns / num_threads);
	printf("run time %d seconds %lu worker burns per second\n",
		(int)(now.tv_sec - start.tv_sec),
		total_burns / (now.tv_sec - start.tv_sec));
	ops->cleanup(num_semids);
	return 0;
}