lkml.org 
[lkml]   [1999]   [Jan]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
SubjectRe: semaphore
Date
Peter T. Breuer said:

"Sigh - can someone pass me the mail
from linus asking for an opinion on
the correctness of the new semaphores?"



Linus posted more than 5 messages containing the word "semaphore" in the
past 3 days, but I think the following message is the one you are looking
for -


- ----------------------- [Begins] -------------------------------


From: Linus Torvalds <torvalds@transmeta.com>
Date: Sat, 9 Jan 1999 13:50:14 -0800 (PST)
Subject: Re: MM deadlock [was: Re: arca-vm-8...]

On Sat, 9 Jan 1999, Linus Torvalds wrote:
>
> The cleanest solution I can think of is actually to allow semaphores to be
> recursive. I can do that with minimal overhead (just one extra instruction
> in the non-contention case), so it's not too bad, and I've wanted to do it
> for certain other things, but it's still a nasty piece of code to mess
> around with.
>
> Oh, well. I don't think I have much choice.

Does anybody know semaphores by heart? I've got code that may well work,
but the race conditions for semaphores are nasty. As mentioned, this only
adds a single instruction to the common non-contended case, and I really
do believe it should be correct, but it is completely untested (so it
might not work at all), and it would be good to have somebody with some
theory go through this..

Basically, these simple changes should make it ok to do recursive
semaphore grabs, so

down(&sem);
down(&sem);
up(&sem);
up(&sem);

should work and leave the semaphore unlocked.

Anybody? Semaphore theory used to be really popular at Universities, so
there must be somebody who has some automated proving program somewhere..

Linus

- -----
diff -u --recursive --new-file penguin/linux/include/asm-i386/semaphore.h
linux/include/asm-i386/semaphore.h
- --- penguin/linux/include/asm-i386/semaphore.h Fri Jan 1 11:56:20
1999
+++ linux/include/asm-i386/semaphore.h Sat Jan 9 13:37:29 1999
@@ -25,12 +25,23 @@

struct semaphore {
atomic_t count;
+ unsigned long owner;
int waking;
struct wait_queue * wait;
};

- -#define MUTEX ((struct semaphore) { ATOMIC_INIT(1), 0, NULL })
- -#define MUTEX_LOCKED ((struct semaphore) { ATOMIC_INIT(0), 0, NULL })
+/*
+ * Because we want the non-contention case to be
+ * fast, we save the stack pointer into the "owner"
+ * field, and to get the true task pointer we have
+ * to do the bit masking. That moves the masking
+ * operation into the slow path.
+ */
+#define semaphore_owner(sem) \
+ ((struct task_struct *)((2*PAGE_MASK) & (sem)->owner))
+
+#define MUTEX ((struct semaphore) { ATOMIC_INIT(1), 0, 0, NULL })
+#define MUTEX_LOCKED ((struct semaphore) { ATOMIC_INIT(0), 0, 0, NULL })

asmlinkage void __down_failed(void /* special register calling convention
*/);
asmlinkage int __down_failed_interruptible(void /* params in registers
*/);
@@ -64,13 +75,14 @@
spin_unlock_irqrestore(&semaphore_wake_lock, flags);
}

- -static inline int waking_non_zero(struct semaphore *sem)
+static inline int waking_non_zero(struct semaphore *sem, struct task_struct
*tsk)
{
unsigned long flags;
int ret = 0;

spin_lock_irqsave(&semaphore_wake_lock, flags);
- - if (sem->waking > 0) {
+ if (sem->waking > 0 || semaphore_owner(sem) == tsk) {
+ sem->owner = (unsigned long) tsk;
sem->waking--;
ret = 1;
}
@@ -91,7 +103,8 @@
"lock ; "
#endif
"decl 0(%0)\n\t"
- - "js 2f\n"
+ "js 2f\n\t"
+ "movl %%esp,4(%0)\n"
"1:\n"
".section .text.lock,\"ax\"\n"
"2:\tpushl $1b\n\t"
@@ -113,6 +126,7 @@
#endif
"decl 0(%1)\n\t"
"js 2f\n\t"
+ "movl %%esp,4(%1)\n\t"
"xorl %0,%0\n"
"1:\n"
".section .text.lock,\"ax\"\n"
diff -u --recursive --new-file penguin/linux/kernel/sched.c
linux/kernel/sched.c
- --- penguin/linux/kernel/sched.c Mon Jan 4 23:15:49 1999
+++ linux/kernel/sched.c Sat Jan 9 13:37:16 1999
@@ -883,7 +883,7 @@
* who gets to gate through and who has to wait some more. \
*/ \
for (;;) { \
- - if (waking_non_zero(sem)) /* are we waking up? */ \
+ if (waking_non_zero(sem, tsk)) /* are we waking up? */ \
break; /* yes, exit loop */

#define DOWN_TAIL(task_state) \
- ------------------------ [Ends] ------------------------------
Hope it helps.

Regards,
Pete
teamwork@freemail.c3.hu

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

\
 
 \ /
  Last update: 2005-03-22 13:49    [W:0.033 / U:0.452 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site