semaphore fairness patch against test11-pre6

Hi Linus et al,

I've applied your semaphore fairness patch (slightly fixed) below. It fixes my original bug report of vmstat, ps etc. stalls waiting for the mmap_sem. I can now run my memory 'hog' processes and actually see vmstat update every second even under heavy memory pressure. More importantly, ps works so I can find the pid to kill. I'm no expert in checking for races, but I went over all (I think) the 2 process cases as well as I could and they seem to look ok to me, but what do I know. I know someone else reported it didn't fix the problem, but perhaps that's some other issue.

I ran many 'ps' (20?) in the background trying to simulate many process contention, and everything still worked fine. I've run some other stress tests too (dbench, my own I/O throughput test etc) and so far all's well (famous last words).

If you can find the time to check this out more completely, I recommend it, because it seems like a great improvement to be able to accurately see vmstat numbers in times of system load. I hope the other side effects are beneficial as well :-)

The change to the patch was that you had 'if (sleepers > 1)' when obviously you meant 'if (sem->sleepers > 1)'...

Here's your patch again (also attached in case of mangling):

@@ -64,6 +64,14 @@
 
 	spin_lock_irq(&semaphore_lock);
 	sem->sleepers++;
+
+	/*
+	 * Are there other people waiting for this?
+	 * They get to go first.
+	 */
+	if (sem->sleepers > 1)
+		goto inside;
+
 	for (;;) {
 		int sleepers = sem->sleepers;
 

@@ -76,6 +84,7 @@
 			break;
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
+inside:
 		spin_unlock_irq(&semaphore_lock);
 
 		schedule();

Index: linux/arch/i386/kernel/semaphore.c
===================================================================
RCS file: /home/kernel/cvs_master/linux/arch/i386/kernel/semaphore.c,v retrieving revision 1.3

diff -u -r1.3 semaphore.c
@@ -64,6 +64,14 @@
 
 	spin_lock_irq(&semaphore_lock);
 	sem->sleepers++;
+
+	/*
+	 * Are there other people waiting for this?
+	 * They get to go first.
+	 */
+	if (sem->sleepers > 1)
+		goto inside;
+
 	for (;;) {
 		int sleepers = sem->sleepers;
 

@@ -76,6 +84,7 @@
 			break;
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
+inside:
 		spin_unlock_irq(&semaphore_lock);
 
 		schedule();

Hi David,

I wanted to point out that there may be some performance impacts by
this: We had exactly the new behaviour on SYSV semaphores. It led to very bad behaviour in high load situations since for high frequency, short critical paths this led to very high context switch rates instead of using the available time slice for the program.

We changed the behaviour of SYSV semaphores to the current kernel sem behaviour and never had problems with that change.

I still think that your change is right since this is kernel space and you do not have the notion of a time slice.

Christoph

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

Has anyone tried it on SMP? I get fairly repeatable instances of immortal `D'-state processes with this patch.

The patch isn't right - it allows `sleepers' to increase without bound. But it's a boolean!

If you cut out the unnecessary code and the incorrect comments from __down() it looks like this:

void __down(struct semaphore * sem)

{
        struct task_struct *tsk = current;
        DECLARE_WAITQUEUE(wait, tsk);
        tsk->state = TASK_UNINTERRUPTIBLE;
        add_wait_queue_exclusive(&sem->wait, &wait);

        spin_lock_irq(&semaphore_lock);
        for (;;) {
                /*
                 * Effectively:
                 *
                 *      if (sem->sleepers)
                 *              sem->count++
                 *      if (sem->count >= 0)
                 *              sem->sleepers = 0;
                 *              break;
                 */
                if (!atomic_add_negative(sem->sleepers, &sem->count)) {
                        sem->sleepers = 0;
                        break;
                }
                sem->sleepers = 1;
                spin_unlock_irq(&semaphore_lock);

                schedule();
                tsk->state = TASK_UNINTERRUPTIBLE;
                spin_lock_irq(&semaphore_lock);
        }
        spin_unlock_irq(&semaphore_lock);
        remove_wait_queue(&sem->wait, &wait);
        tsk->state = TASK_RUNNING;
        wake_up(&sem->wait);
}

I spent a couple of hours trying to get "fairness" working right and have not been able to come up with a non-racy solution. That semaphore algorithm is amazing. I'm really impressed.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

Too bad. I really thought it should be safe to do.

It's not a boolean. It's really a "bias count". It happens to get only the values 0 and 1 simply becase the logic is that we always account for all the other people when any process goes to sleep, so "sleepers" only ever counts the one process that went to sleep last.

But the algorithm itself should allow for other values. In fact, I think that you'll find that it works fine if you switch to non-exclusive wait-queues, and the only reason you see the repeatable D states is exactly the case where we didn't "take" the semaphore even though we were awake, and that basically makes us an exclusive process that didn't react to an exclusive wakeup.

(Think of it this way: with the "inside" patch, the process does

	tsk->state = TASK_INTERRUPTIBLE;

twice, even though there was only one semaphore that woke it up: we basically "lost" a wakeup event, not because "sleepers" cannot be 2, but because we didn't pick up the wakeup that we might have gotten.

Instead of the "goto inside", how about just doing it without the "double sleep", and doing something like

	tsk->state = TASK_INTERRUPTIBLE;
	add_wait_queue_exclusive(&sem->wait, &wait);

	spin_lock_irq(&semaphore_lock);
	sem->sleepers ++;

+ if (sem->sleepers > 1) {
+ spin_unlock_irq(&semaphore_lock);
+ schedule();
+ spin_lock_irq(&semaphore_lock);
+ }

	for (;;) {

The only difference between the above and the "goto inside" variant is really that the above sets "tsk->state = TASK_INTERRUPTIBLE;" just once per loop, not twice as the "inside" case did. So if we happened to get an exclusive wakeup at just the right point, we won't go to sleep again and miss it.

But these things are very subtle. The current semaphore algorithm was basically perfected over a week of some serious thinking. The fairness change should similarly get a _lot_ of attention. It's way too easy to miss things.

Does the above work for you even in SMP?

Linus

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

I don't see a path where David's patch can cause a lost wakeup in the way you describe.

This still causes stuck processes. There's a bonnie++ test which hammers pipes. It's quite easy to get four instances of bonnie++ stuck on a pipe semaphore. This is with your suggested change applied to both __down and __down_interruptible, BTW. Switching both functions to use non-exclusive waitqueues didn't help. Still missing a wakeup somewhere.

Moving on to this version:

void __down(struct semaphore * sem)

{
        struct task_struct *tsk = current;
        DECLARE_WAITQUEUE(wait, tsk);
        tsk->state = TASK_UNINTERRUPTIBLE;
        add_wait_queue_exclusive(&sem->wait, &wait);

        spin_lock_irq(&semaphore_lock);
        if (sem->sleepers)
                goto inside;
        for (;;) {
                /*
                 * Add "everybody else" into it. They aren't
                 * playing, because we own the spinlock.
                 */
                if (!atomic_add_negative(sem->sleepers, &sem->count)) {
                        sem->sleepers = 0;
                        break;
                }
                sem->sleepers = 1;      /* us - see -1 above */
inside:
                spin_unlock_irq(&semaphore_lock);

                schedule();
                tsk->state = TASK_UNINTERRUPTIBLE;
                spin_lock_irq(&semaphore_lock);
        }
        spin_unlock_irq(&semaphore_lock);
        remove_wait_queue(&sem->wait, &wait);
        tsk->state = TASK_RUNNING;
        wake_up(&sem->wait);
}

The only difference here is that we're not allowing `sem->sleepers' to take the value '2' outside the spinlock. But it still turns bonnie++ into Rip van Winkle.

Next step is to move the waitqueue and wakeup operations so they're inside the spinlock. Nope. That doesn't work either.

Next step is to throw away the semaphore_lock and use the sem->wait lock instead. That _does_ work. This is probably just a fluke - it synchronises the waker with the sleepers and we get lucky.

But at least it's now benchmarkable. It works well. Kernel build times are unaffected. bw_tcp is down a few percent. Worth pursuing.

David, could you please verify that the patch at
http://www.uow.edu.au/~andrewm/linux/semaphore.patch
still fixes the starvation problem?

Agree. The fact that this algorithm can work while random CPUs are asynchronously incrementing and decrementing sem->count makes analysis and understanding a _lot_ harder.

There's a lot more work needed here.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

Basically, if there are two up() calls, they might end up waking up only one process, because the same process goes to sleep twice. That's wrong. It should wake up two processes.

However, thinking about it more, that's obviously possible only for semaphores that are used for more than just mutual exclusion, and basically nobody does that anyway.

Yes, especially on a two-cpu machine that kind of synchronization can basically end up hiding real bugs.

I'll think about this some more. One thing I noticed is that the "wake_up(&sem->wait);" at the end of __down() is kind of bogus: we don't actually want to wake anybody up at that point at all, it's just that if we don't wake anybody up we'll end up having "sem = 0, sleeper = 0", and when we unlock the semaphore the "__up()" logic won't trigger, and we won't ever wake anybody up. That's just incredibly bogus.

Instead of the "wake_up()" at the end of __down(), we should have something like this at the end of __down() instead:

			... for-loop ...
		}
		tsk->state = TASK_RUNNING;
		remove_wait_queue(&sem->wait, &wait);

		/* If there are others, mark the semaphore active */
		if (wait_queue_active(&sem_wait)) {
			atomic_dec(&sem->count);
			sem->sleepers = 1;
		}
		spin_unlock_irq(&semaphore_lock);
	}

which would avoid an unnecessary reschedule, and cause the wakeup to happen at the proper point, namely "__up()" when we release the semaphore.

I suspect this may be part of the trouble with the "sleepers" count
playing: we had these magic rules that I know I thought about when the code was written, but that aren't really part of the "real" rules.

Linus

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

There's another reason why we need the wakeup in the tail of __down():

1 void __down(struct semaphore * sem)
2 {
3 struct task_struct *tsk = current;
4 DECLARE_WAITQUEUE(wait, tsk);
5 tsk->state = TASK_UNINTERRUPTIBLE|TASK_EXCLUSIVE;
6 add_wait_queue_exclusive(&sem->wait, &wait);
7
8 spin_lock_irq(&semaphore_lock);
9 sem->sleepers++;
10 for (;;) {
11 int sleepers = sem->sleepers;
12
13 /*
14 * Add "everybody else" into it. They aren't
15 * playing, because we own the spinlock.
16 */
17 if (!atomic_add_negative(sleepers - 1, &sem->count)) {
18 sem->sleepers = 0;
19 break;
20 }
21 sem->sleepers = 1; /* us - see -1 above */
22 spin_unlock_irq(&semaphore_lock);
23
24 schedule();
25 tsk->state = TASK_UNINTERRUPTIBLE;
26 spin_lock_irq(&semaphore_lock);
27 }
28 spin_unlock_irq(&semaphore_lock);
29 remove_wait_queue(&sem->wait, &wait);
30 tsk->state = TASK_RUNNING;
31 wake_up(&sem->wait);
32 }

Suppose two tasks A and B are sleeping on the semaphore and somebody does an up(). Task A wakes and sets TASK_UNINTERRUPTIBLE.

Task A then executes statements 26, 11, 17, 18, 19, 28 and 29 while it's on the head of the exclusive waitqueue in state TASK_UNINTERRUPTIBLE. If during this, another CPU does an up() on the semaphore the wakeup will be directed to Task A and will be lost.

Hence Task A must do the wakeup once it has removed itself from the waitqueue just in case this happened. Did anyone ever mention that exclusive wakeups should atomically remove tasks from the waitqueue? :)

This won't help, because in the failure scenario we never get to exit the 'for' loop. Read on...

Here's why the `goto inside' thingy isn't working:

Assume the semaphore is free:

Task A does down():
-------------------

count->0
sleepers=0

Task B does down():
-------------------

count: 0 -> -1
sleepers: 0->1
if (sleepers > 1) is false
atomic_add_negative(1-1, -1): count -1 -> -1.
`if' fails.
sleepers: 1->1
schedule()

Task C does down():
-------------------

count: -1 -> -2
sleepers: 1->2
if (sleepers > 1) is true
schedule()

Someone does up():
------------------

(reminder: count=-2, sleepers=2)
count: -2 -> -1
wakeup()
-FINISHED-

Task C, CPU0 CPU1

wakes up
tsk->state = TASK_UNINTERRUPTIBLE
spin_lock

						down()
						count: -1->-2
						spins....

(reminder: sleepers=2, count=-2)
atomic_add_negative(2-1, -2): count->-1
aargh! `if' fails!
sleepers->1
spin_unlock()
schedule()
unspins....
sem->sleepers++ sleepers: 1->2
if (sleepers > 1) is true
aargh! atomic_add_negative test would have succeeded! spin_unlock()
schedule()

** Nobody woke up **

Someone does up(), but assume CPU1 gets the lock
------------------------------------------------

(reminder: count=-2, sleepers=2)

count: -2 -> -1
wakeup()
-FINISHED-

Task C, CPU0 CPU1

wakes up
tsk->state = TASK_UNINTERRUPTIBLE

						down()
						count: -1->-2
						spin_lock
spins...
						sem->sleepers++ sleepers: 2->3
						if (sleepers > 1) is true
						spin_unlock()
						schedule()

unspins...
(reminder: sleepers=3, count=-2)
atomic_add_negative(3-1, -2): count->0
'if' succeeds
sleepers->1
spin_unlock()
schedule()

** OK, that worked, and it was "fair" **

Here's the story with the current (test11) implementation
=========================================================

Task A does down():
-------------------

count->0
sleepers=0

Task B does down():
-------------------

count: 0 -> -1
sleepers: 0->1
atomic_add_negative: count -1 -> -1. false.
sleepers->1
schedule()

Task C does down():
-------------------

count: -1 -> -2
sleepers: 1->2
atomic_add_negative: count -2 -> -1. false
sleepers->1
schedule()

Someone does up():
------------------

count: -1 -> 0
wakeup()
-FINISHED-

Task C, CPU0 CPU1

wakes up
tsk->state = TASK_UNINTERRUPTIBLE
spin_lock

						down()
						count: 0 -> -1
						spins....

(reminder: count=-1, sleepers=1)
atomic_add_negative(1-1, -1): count->-1
`if' fails.
sleepers->1
spin_unlock()
schedule()

						unspins...
						sem->sleepers++: 1->2
						atomic_add_negative(2-1, -1): count: -1->0
						'if' is true.
						sleepers->0
						break
						<runs>

	** OK, that worked too **

Linus, this code is too complex.

-
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/