new semaphores

Andrea Arcangeli (andrea@suse.de)
Sun, 29 Aug 1999 00:53:11 +0200 (CEST)

It seems to me that there's no need of wake-up the sleepers in the success
path of __down(). If you get the semaphore nobody else can do progresses.
You'll sure wakeup the sleepers some time soon in up().

Then I changed the kind of the semaphores from wake-all to wake-one-FIFO.
To do that I must always try to wakeup one sleeper if I giveup in
down_interruptible() since I may got the wakeup from an up() while I was
giving up while I was still in the waitqueue. So I must make sure to pass
the wake-one wakeup from me to another sleeper before giving up.

down_trylock seems buggy because it always returns 1 and it won't make
difference between the case that held the semaphore and the case that find
the semaphore busy. In trylock we must not care about the waitqueue at all
since we don't add ourself in the waitqueue there. trylock can't be the
cause of a missed wakeup from an up(). down_interruptible() is different
since we giveup while we are inside the waitqueue. The only detail to care
is to undo the sem->count with the spinlock held (so other sleepers will
look at the sem->count only when it will be uptodate and so other sleepers
will be able to grab the semaphore if an up() happened while we was giving
up in trylock). If an up() happened this way:

task1 task2 task3
-------------------------------------
down_trylock()
up()
wakeup()
sleeper wakenup
try to grab
can't grab due the
underlaying trylock
sleep again
__down_trylock()
got the semaphore

we'll be fine too since __down_trylock will happen some time soon and then
it will grab the semaphore instead of the task2.

Here it is a patch against clean 2.3.15 to fix all the above issues and to
implement wake-one-FIFO:

--- 2.3.15/arch/i386/kernel/semaphore.c Thu Aug 26 02:54:55 1999
+++ 2.3.15-semaphores/arch/i386/kernel/semaphore.c Sun Aug 29 00:29:30 1999
@@ -49,28 +49,25 @@
{
struct task_struct *tsk = current;
DECLARE_WAITQUEUE(wait, tsk);
- tsk->state = TASK_UNINTERRUPTIBLE;
- add_wait_queue(&sem->wait, &wait);
+ tsk->state = TASK_UNINTERRUPTIBLE|TASK_EXCLUSIVE;
+ add_wait_queue_exclusive(&sem->wait, &wait);

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

schedule();
- tsk->state = TASK_UNINTERRUPTIBLE;
+ tsk->state = TASK_UNINTERRUPTIBLE|TASK_EXCLUSIVE;
spin_lock_irq(&semaphore_lock);
}
spin_unlock_irq(&semaphore_lock);
@@ -80,17 +77,15 @@

int __down_interruptible(struct semaphore * sem)
{
- int retval;
+ int retval = 0;
struct task_struct *tsk = current;
DECLARE_WAITQUEUE(wait, tsk);
- tsk->state = TASK_INTERRUPTIBLE;
- add_wait_queue(&sem->wait, &wait);
+ tsk->state = TASK_INTERRUPTIBLE|TASK_EXCLUSIVE;
+ add_wait_queue_exclusive(&sem->wait, &wait);

spin_lock_irq(&semaphore_lock);
sem->sleepers ++;
for (;;) {
- int sleepers = sem->sleepers;
-
/*
* With signals pending, this turns into
* the trylock failure case - we won't be
@@ -98,12 +93,14 @@
* it has contention. Just correct the count
* and exit.
*/
- retval = -EINTR;
if (signal_pending(current)) {
+ retval = -EINTR;
+ /* sync the count with the sleepers before changin
+ the sleepers field, everybody must enforce this
+ rule. Remeber to undo the count decrement
+ before giving up (no -1 here). */
+ atomic_add(sem->sleepers, &sem->count);
sem->sleepers = 0;
- if (atomic_add_negative(sleepers, &sem->count))
- break;
- wake_up(&sem->wait);
break;
}

@@ -113,9 +110,7 @@
* "-1" is because we're still hoping to get
* the lock.
*/
- if (!atomic_add_negative(sleepers - 1, &sem->count)) {
- wake_up(&sem->wait);
- retval = 0;
+ if (!atomic_add_negative(sem->sleepers - 1, &sem->count)) {
sem->sleepers = 0;
break;
}
@@ -123,12 +118,17 @@
spin_unlock_irq(&semaphore_lock);

schedule();
- tsk->state = TASK_INTERRUPTIBLE;
+ tsk->state = TASK_INTERRUPTIBLE|TASK_EXCLUSIVE;
spin_lock_irq(&semaphore_lock);
}
spin_unlock_irq(&semaphore_lock);
tsk->state = TASK_RUNNING;
remove_wait_queue(&sem->wait, &wait);
+ if (retval)
+ /* here we'll sure wakeup another waiter since we aren't
+ in the waitqueue anymore. We need this additional wakeup
+ because an up() may be happened while we was giving up. */
+ wake_up(&sem->wait);
return retval;
}

@@ -142,21 +142,22 @@
*/
int __down_trylock(struct semaphore * sem)
{
- int retval, sleepers;
+ int failed;

spin_lock_irq(&semaphore_lock);
- sleepers = sem->sleepers + 1;
- sem->sleepers = 0;
-
/*
- * Add "everybody else" and us into it. They aren't
+ * Add "everybody else" into it. They aren't
* playing, because we own the spinlock.
*/
- if (!atomic_add_negative(sleepers, &sem->count))
- wake_up(&sem->wait);
-
+ failed = atomic_add_negative(sem->sleepers, &sem->count);
+ sem->sleepers = 0;
+ if (failed)
+ /* we didn't got the semaphore so undo the count
+ decrement. */
+ atomic_inc(&sem->count);
spin_unlock_irq(&semaphore_lock);
- return 1;
+
+ return failed;
}


Andrea

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/