Re: [RFC] Semaphores used for daemon wakeup
On Thu, Dec 21, 2000 at 01:30:03PM -0600, Paul Cassella wrote:
> The mechanism being developed here seems a lot like synchronization
> variables (aka condition variables), which are a part of the "monitor"
> synchronization construct. There is a simple implementation of them in
> the xfs patch. I've been working on a more general version in order to
> aid porting some other stuff, which I have appended to this post.
>
> I had been holding off on posting about it since I didn't have any code
> that used it ready, and probably wouldn't until 2.5 anyway, but due to
> this thread, I think bringing it up now might be helpful.
>
We have a similar set of locks that were developed while porting the
Quadrics device drivers over to Linux from True64. These are pretty
close to the way pthreads mutexes and condition variables work in user
space and are similar to primitives that exist in True64 kernel land
(thus the need to develop them to make the port easier). They allow
for use of semaphores or spinlocks depending on whether you are going
to sleep while holding the mutex. The only caveat with it is that it
requires that wake_up_process() be exported in kernel/ksyms.c in order
to use it in modules. We're in the process of making a Linux web site
here at the lab that has papers as well as patches that we have made
to help Linux along in the high performance computing area. Until
that is up, here are the two files that implement mutexes and
condition variables.
BAPper
/*
*Copyright (C) 2000 Regents of the University of California
*
*This program is free software; you can redistribute it and/or modify
*it under the terms of the GNU General Public License as published by
*the Free Software Foundation; either version 2 of the License, or
*(at your option) any later version.
*
*This program is distributed in the hope that it will be useful,
*but WITHOUT ANY WARRANTY; without even the implied warranty of
*MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
*GNU General Public License for more details.
*
*You should have received a copy of the GNU General Public License
*along with this program; if not, write to the Free Software
*Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*Mutex functions.
* MUTEX_SPIN spinlock
* MUTEX_SPIN_INTR spinlock with interrupts disabled
* MUTEX_BLOCK semaphore
*
*Define -DDEBUG_MUTEX to get debugging spinlocks on alpha
*(will report file/line no. of stuck spinlocks)
*
*Jim Garlick <[EMAIL PROTECTED]>
*/
#if !defined(_LINUX_MUTEX_H)
#define _LINUX_MUTEX_H
#if defined(__KERNEL__)
#if defined(DEBUG_MUTEX) && defined(__alpha__) && !defined(DEBUG_SPINLOCK)
#define DEBUG_SPINLOCK
#endif
#include
#include
#include
#include
#include
#include
#if !defined(DEBUG_SPINLOCK)
#define debug_spin_lock(lock, file, line) spin_lock(lock)
#define debug_spin_trylock(lock, file, line)spin_trylock(lock)
#endif
#define mutex_trylock(l) debug_mutex_trylock(l, __BASE_FILE__, __LINE__)
#define mutex_lock(l) debug_mutex_lock(l, __BASE_FILE__, __LINE__)
#define PID_NONE(PID_MAX + 1)
#define PID_INTR(PID_MAX + 2 + smp_processor_id())
#define MY_PID (in_interrupt() ? PID_INTR : current->pid)
#define MY_CPU smp_processor_id()
#define MUTEX_MAX_NAME 16
typedef enum { MUTEX_SPIN, MUTEX_SPIN_INTR, MUTEX_BLOCK } lock_type_t;
typedef struct {
lock_type_t type;
union {
struct {
spinlock_t lock;
unsigned long flags;
} spin;
struct {
struct semaphorelock;
} blocking;
} mutex_u;
pid_t holder;
#if defined(DEBUG_MUTEX)
charname[MUTEX_MAX_NAME];
#endif
} mutex_t;
/* binary semaphores */
#if LINUX_VERSION_CODE < KERNEL_VERSION(2,3,0)
#define BS_INIT(s) (s) = MUTEX
#else
#define BS_INIT(s) init_MUTEX(&(s))
#endif
#define BS_TRY(s) (down_trylock(&(s)) == 0)
#define BS_LOCK(s) down(&(s))
#define BS_UNLOCK(s)up(&(s))
extern __inline__ void
mutex_init(mutex_t *l, char *name, lock_type_t type)
{
l->type = type;
switch(l->type) {
case MUTEX_BLOCK:
BS_INIT(l->mutex_u.blocking.lock);
break;
case MUTEX_SPIN:
case MUTEX_SPIN_INTR:
l->mutex_u.spin.lock = SPIN_LOCK_UNLOCKED;
break;
}
l->holder = PID_NONE;
#if defined(DEBUG_MUTEX)
strncpy(l->name, name, MUTEX_MAX_NAME);
#endif
}
extern __inline__ void
mutex_destroy(mutex_t *l)
{
ASSERT(l->holder == PID_NONE);
}
/*
* Return nonzero if lock is held by this thread.
*/
extern __inline__ int
Re: [RFC] Semaphores used for daemon wakeup
Tim Wright wrote: > > On Fri, Dec 22, 2000 at 12:46:28PM +0100, Daniel Phillips wrote: > [...] > > Granted, it's just an example, but it doesn't make sense to wake up more > > dmabuf_alloc waiters than you actually have buffers for. You do one > > up() per freed buffer, and the semaphore's wait queue better be fifo or > > have some other way of ensuring a task doesn't languish there. (I don't > > know, does it?) > > ...You are correct - it doesn't > make sense to wake up more waiters than you can satify if you know this at > the time. As Paul mentioned, the idea here is that we may have freed > multiple buffers, and so we wake all the consumers and let them fight it out. With my model, if you were freeing several buffers you'd do several ups, and especially in the common case where nobody is waiting that's efficient enough that it would be hard to justify optimizing further with say, an up_many(sem, n). > At least in DYNIX/ptx, semaphores are exclusively FIFO. This gives wake-one > semantics by default, and prevents starvation. Then it's most probably that way in Linux too, but __wake_up_common will take a little time to digest. > One general rule to remember is that if you need to take multiple locks, then > you need to always take them in the same order to avoid deadlocks. Yes, I picked that one up while working on tailmerging and had to lock multiple inodes. Then I changed the design so it only takes one lock at a time - what an improvement. The moral of this story is that the best lock is the one you never have to take. > One simple, if crude way of doing this if they're not two fixed locks is to > always take the lock with the lower address first. I don't know if this > will help in this case, but it looks like you probably have to play with > the rw locks for the wait queues to make this atomic. I took a look at the code... the implementation details of these primitives are a whole nuther world. There's probably a simple implementation of up_down but I'm far from being able to see it at this point. -- Daniel - 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/
Re: [RFC] Semaphores used for daemon wakeup
On Fri, Dec 22, 2000 at 12:46:28PM +0100, Daniel Phillips wrote: [...] > Granted, it's just an example, but it doesn't make sense to wake up more > dmabuf_alloc waiters than you actually have buffers for. You do one > up() per freed buffer, and the semaphore's wait queue better be fifo or > have some other way of ensuring a task doesn't languish there. (I don't > know, does it?) > Sorry, I could have picked a clearer example. You are correct - it doesn't make sense to wake up more waiters than you can satify if you know this at the time. As Paul mentioned, the idea here is that we may have freed multiple buffers, and so we wake all the consumers and let them fight it out. At least in DYNIX/ptx, semaphores are exclusively FIFO. This gives wake-one semantics by default, and prevents starvation. > > The example wasn't meant to be an ideal use of sv's, but merely as an > > example of how they could be used to achieve the same behavior as the code > > that was posted. > > Yes, and a third example of the 'unlock/wakeup_and_sleep' kind of > primitive - there seems to be a pattern. I should at least take a look > and see if up_down is easy or hard to implement. > One general rule to remember is that if you need to take multiple locks, then you need to always take them in the same order to avoid deadlocks. One simple, if crude way of doing this if they're not two fixed locks is to always take the lock with the lower address first. I don't know if this will help in this case, but it looks like you probably have to play with the rw locks for the wait queues to make this atomic. Tim -- Tim Wright - [EMAIL PROTECTED] or [EMAIL PROTECTED] or [EMAIL PROTECTED] IBM Linux Technology Center, Beaverton, Oregon "Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI - 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/
Re: [RFC] Semaphores used for daemon wakeup
Paul Cassella wrote:
> > dmabuf_alloc(...)
> > {
> > while (1) {
> > spin_lock(&dmabuf_lock);
> > attempt to grab a free buffer;
> > spin_unlock(&dmabuf_lock);
> > if (success)
> >return;
> > down(&dmabuf_wait);
> > }
> > }
>
> > dmabuf_free(...)
> > {
> > spin_lock(&dmabuf_lock);
> > free up buffer;
> > spin_unlock(&dmabuf_lock);
> > up(&dmabuf_wait);
> > }
>
> This does things a little differently than the way the original did it.
> I thought the original implied that dmabuf_free() might free up multiple
> buffers. There's no indication in the comments that this is the case, but
> the original, by using vall_sema(), wakes up all dmabuf_alloc()'s that had
> gone to sleep.
Granted, it's just an example, but it doesn't make sense to wake up more
dmabuf_alloc waiters than you actually have buffers for. You do one
up() per freed buffer, and the semaphore's wait queue better be fifo or
have some other way of ensuring a task doesn't languish there. (I don't
know, does it?)
> The example wasn't meant to be an ideal use of sv's, but merely as an
> example of how they could be used to achieve the same behavior as the code
> that was posted.
Yes, and a third example of the 'unlock/wakeup_and_sleep' kind of
primitive - there seems to be a pattern. I should at least take a look
and see if up_down is easy or hard to implement.
--
Daniel
-
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/
Re: [RFC] Semaphores used for daemon wakeup
On Fri, 22 Dec 2000, Daniel Phillips wrote:
> But isn't this actually a simple situation? How about:
I had only adapted that example because it had already been posted showing
one way to do it, and so provided something to compare the sv approach to.
> dmabuf_alloc(...)
> {
> while (1) {
> spin_lock(&dmabuf_lock);
> attempt to grab a free buffer;
> spin_unlock(&dmabuf_lock);
> if (success)
>return;
> down(&dmabuf_wait);
> }
> }
> dmabuf_free(...)
> {
> spin_lock(&dmabuf_lock);
> free up buffer;
> spin_unlock(&dmabuf_lock);
> up(&dmabuf_wait);
> }
This does things a little differently than the way the original did it.
I thought the original implied that dmabuf_free() might free up multiple
buffers. There's no indication in the comments that this is the case, but
the original, by using vall_sema(), wakes up all dmabuf_alloc()'s that had
gone to sleep.
The example wasn't meant to be an ideal use of sv's, but merely as an
example of how they could be used to achieve the same behavior as the code
that was posted.
--
Paul Cassella
[EMAIL PROTECTED]
-
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/
Re: [RFC] Semaphores used for daemon wakeup
Paul Cassella wrote:
> The sync variable version of the dmabuf code snippet (assuming the
> dmabuf_mutex is never acquired from an interrupt) would look like this:
>
> dmabuf_init(...);
> {
> ...
> spin_lock_init(&dmabuf_spin);
> sv_init(&dmabuf_sv, &dmabuf_spin, SV_MON_SPIN);
> ...
> }
>
> dmabuf_alloc(...)
> {
>
> ...
> while (1) {
> spin_lock(&dmabuf_spin);
> attempt to grab a free buffer;
> if (success){
> spin_unlock(&dmabuf_spin);
> return;
> } else {
> sv_wait(&dmabuf_sv);
> }
> }
> }
>
> dmabuf_free(...)
> {
> ...
> spin_lock(&dmabuf_spin);
> free up buffer;
> sv_broadcast(&dmabuf_sv);
> spin_unlock(&dmabuf_spin);
> }
>
But isn't this actually a simple situation? How about:
dmabuf_alloc(...)
{
...
while (1) {
spin_lock(&dmabuf_lock);
attempt to grab a free buffer;
spin_unlock(&dmabuf_lock);
if (success)
return;
down(&dmabuf_wait);
}
}
dmabuf_free(...)
{
...
spin_lock(&dmabuf_lock);
free up buffer;
spin_unlock(&dmabuf_lock);
up(&dmabuf_wait);
}
--
Daniel
-
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/
Re: [RFC] Semaphores used for daemon wakeup
Paul Cassella wrote:
> > int atomic_read_and_clear(atomic_t *p)
> > {
> > int n = atomic_read(p);
> > atomic_sub(p, n);
> > return n;
> > }
>
> I don't think this will work; consider two callers doing the atomic_read()
> at the same time, or someone else doing an atomic_dec() after the
> atomic_read().
Oh yes, mea culpa, this is a terrible primitive, yet it works for this
application. 1) We don't have two callers 2) We only have atomic_inc
from the other processes, and it's ok for the atomic_inc to occur after
the atomic_read because that means the atomic_inc'er will then proceed
to up() the atomic_sub'ers semaphore, and it won't block.
I much preferred my original waiters = xchg(&sem.count, 0), but as noted
it doesn't work with sparc. A satisfying approach would be to create
the new primitive up_down, which simplifies everything dramatically.
--
Daniel
-
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/
Re: [RFC] Semaphores used for daemon wakeup
Looks good. I'd like to play with you patch, but certainly from a first glance, it would seem to be sufficiently powerful, and significantly cleaner/clearer (at least to me :-) than the current mechanism involving the wait queue games. Regards, Tim -- Tim Wright - [EMAIL PROTECTED] or [EMAIL PROTECTED] or [EMAIL PROTECTED] IBM Linux Technology Center, Beaverton, Oregon "Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI - 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/
Re: [RFC] Semaphores used for daemon wakeup
The mechanism being developed here seems a lot like synchronization
variables (aka condition variables), which are a part of the "monitor"
synchronization construct. There is a simple implementation of them in
the xfs patch. I've been working on a more general version in order to
aid porting some other stuff, which I have appended to this post.
I had been holding off on posting about it since I didn't have any code
that used it ready, and probably wouldn't until 2.5 anyway, but due to
this thread, I think bringing it up now might be helpful.
Daniel Phillips wrote:
> Tim Wright wrote:
> > p_sema_v_lock(&sema, priority, &lock); /* atomically release the lock AND */
> > /* go to sleep on the semaphore */
This in particular looks like sv_wait(), which atomically releases a
lock and goes to sleep.
The style is somewhat different, as a sync variable (sv) is not really a
lock, but is still something that a process can block on. A process goes
to sleep by calling sv_wait(sv), and is woken up by another process
calling sv_signal(sv) (wake one) or sv_broadcast(sv) (wake all). If there
is no process sleeping in sv_wait, signals and broadcasts have no effect;
they do not affect any process which subsequently calls sv_wait().
Each sync variable is associated with another lock, which provides mutual
exclusion guarantees. This lock must be held to call sv_wait(), and is
dropped atomically with the process going to sleep. This lock must also
be held to call sv_signal() or sv_broadcast(). Currently, this lock can
be a spinlock or a semaphore; other types of locks could be added if
necessary.
The sync variable version of the dmabuf code snippet (assuming the
dmabuf_mutex is never acquired from an interrupt) would look like this:
dmabuf_init(...);
{
...
spin_lock_init(&dmabuf_spin);
sv_init(&dmabuf_sv, &dmabuf_spin, SV_MON_SPIN);
...
}
dmabuf_alloc(...)
{
...
while (1) {
spin_lock(&dmabuf_spin);
attempt to grab a free buffer;
if (success){
spin_unlock(&dmabuf_spin);
return;
} else {
sv_wait(&dmabuf_sv);
}
}
}
dmabuf_free(...)
{
...
spin_lock(&dmabuf_spin);
free up buffer;
sv_broadcast(&dmabuf_sv);
spin_unlock(&dmabuf_spin);
}
If dmabuf_free() could be called from an interrupt, this would be modified
by passing the SV_INTS flag to sv_init(), using spin_lock_irq() in
dmabuf_alloc, and spin_lock_irqsave/restore in dmabuf_free().
> > As you can see, the spinlocks ensure no races, and the key is the atomicity
> > of p_sema_v_lock(). No-one can race in and sleep on dmabuf_wait, because
> > they have to hold dmabuf_mutex to do so. Exactly the same mechanism would
> > work for the bdflush problem.
The same protections are in place here, as the two methods are basically
the same.
> described. The main difference between this situation and bdflush is
> that dmabuf_free isn't really waiting on dmabuf_alloc to fullfill a
> condition (other than to get out of its exclusion region) while bdflush
> can have n waiters.
This could be done with two sv's. After all, there are two conditions:
"someone needs bdflush to run", and "bdflush is done".
> int atomic_read_and_clear(atomic_t *p)
> {
> int n = atomic_read(p);
> atomic_sub(p, n);
> return n;
> }
I don't think this will work; consider two callers doing the atomic_read()
at the same time, or someone else doing an atomic_dec() after the
atomic_read().
> the more involved wake_up_process(). What's clear is, they are all
> plenty fast enough for this application, and what I'm really trying for
> is readability.
I think sv's are pretty readable and clear, but I'd like to find out what
other people think.
If anyone finds this useful or finds any bugs, or has any questions or
suggestions, please let me know. I'll be reading the list, but I'm going
on vacation tomorrow, so I'd appreciate a Cc: so I have a better chance of
answering before then. Thanks.
--
Paul Cassella
[EMAIL PROTECTED]
And now, the code.
include/linux/sv.h:
/*
This is the version I'm using with a test8-pre1 kernel, so it uses the
old TASK_EXCLUSIVE semantics; it should be trivial to make it work with
new kernels. I haven't yet done so, since we're going to be using the
test8-pre1 kernel for a few more weeks yet.
In the interests of brevity, I've taken out most of the debugging code,
some typecasting, and some other things like the wrapper functions for
up() and spin_unlock(), which are needed because we need a function
pointer, and these may be macros or inline fuctions.
This was originally based on the version Steve Lord did for the xfs port.
This version had no pr
Re: [RFC] Semaphores used for daemon wakeup
On Wed, Dec 20, 2000 at 02:34:56AM +0100, Daniel Phillips wrote:
>
> Yes, I see. There are a lot of similarities to the situation I
> described. The main difference between this situation and bdflush is
> that dmabuf_free isn't really waiting on dmabuf_alloc to fullfill a
> condition (other than to get out of its exclusion region) while bdflush
> can have n waiters.
>
> If I could have a new primitive for this job it would be up_down(sem1,
> sem2), atomic with respect to a sleeper on sem1. And please give me an
> up_all for good measure. Then for a task wanting to wait on bdflush I
> could write:
>
> up_down(&bdflush_request, &bdflush_waiter);
>
> And in bdflush, just:
>
> up_all(&bdflush_waiter);
> down(&bdflush_request);
>
OK,
I believe that this would look like the following on ptx (omitting all the
obvious stuff :-)
lock_t bdflush_lock;
sema_t bdflush_request;
sema_t bdflush_waiters;
...
init_lock(&bdflush_lock);
init_sema(&bdflush_request, 0);
init_sema(&bdflush_waiters, 0);
...
wakeup_bdflush(...)
{
...
(void) p_lock(&bdflush_lock, SPLBUF);
v_sema(&bdflush_request);
p_sema_v_lock(&bdflush_waiters, PZERO, &bdflush_lock);
}
bdflush(...)
{
spl_t s;
...
s = p_lock(&bdflush_lock, SPLFS);
vall_sema(&bdflush_waiters);
v_lock(&bdflush_lock, s);
if (!flushed || ...
...
}
Once more, the use of p_sema_v_lock() avoids races.
>
> > One can argue the relative merits of the different approaches. I suspect that
> > the above code is less bus-intensive relative to the atomic inc/dec/count ops,
> > but I may be wrong.
>
> I couldn't say, because your mechanism would need to be elaborated a
> little to handle bdflush's multiple waiters, and I don't know exactly
> what your up_and_wait would look like. Do spinlocks work for bdflush,
> or would you have to go to semaphores? (If the latter you arrive at my
> up_down primitive, which is interesting.) It's even hard to say whether
> my approach is faster or slower than the existing approach. Ultimately,
> up() calls wake_up() and down() calls both add_wait_queue() and
> remove_wait_queue(), so I lose a little there. I win in the common case
> of the non-blocking wakeup, which normally runs through Ben Lahaises's
> lovingly handcrafted fast path in up(), whereas the existing code uses
> the more involved wake_up_process(). What's clear is, they are all
> plenty fast enough for this application, and what I'm really trying for
> is readability.
>
The above hopefully elaborates a little. I'm more than happy to give further
details etc. assuming it's not boring everybody to tears :-)
I agree with you that your changes improve the readability significantly.
Regards,
Tim
--
Tim Wright - [EMAIL PROTECTED] or [EMAIL PROTECTED] or [EMAIL PROTECTED]
IBM Linux Technology Center, Beaverton, Oregon
"Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI
-
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/
Re: [RFC] Semaphores used for daemon wakeup
Tim Wright wrote:
>
> Hi Daniel,
> On Tue, Dec 19, 2000 at 02:11:16PM +0100, Daniel Phillips wrote:
> [...]
> > I'm curious, is my method of avoiding the deadlock race the same as
> > yours? My solution is to keep a count of tasks that 'intend' to take
> > the down():
> >
> > atomic_inc(&bdflush_waiters);
> > up(&bdflush_request);
> > down(&bdflush_waiter);
> >
> > so that bdflush will issue the correct number of up's even if the waiter
> > has not yet gone to sleep. IOW, is your approach in DYNIX the same only
> > in spirit, or in detail?
> >
> > --
> > Daniel
>
> OK,
> this is not how we generally would achieve the goal, although the approach
> looks valid. We have a number of primitives available that are not currently
> used in Linux (unless I'm losing my eyesight :-)
> We use p_sema, and v_sema for down and up respectively (this was done many
> years ago, and the names are in deference to Edsger Dijkstra.
> For normal semaphores (as opposed to read/writer or other variants), we have
> sema_t sema;
> init_sema(&sema, 1);/* initialize semaphore & set initial count */
> p_sema(&sema, PZERO); /* "grab" semaphore and set process priority */
> /* priority < PZERO == sleep uninterruptibly */
> v_sema(&sema); /* release semaphore (i.e. increment count) */
> cp_sema(&sema); /* Attempt to grab semaphore iff free else EBUSY */
> vall_sema(&sema); /* Wake up all sleepers on this semaphore */
> blocked_sema(&sema);/* boolean: any sleepers ? */
> p_sema_v_lock(&sema, priority, &lock); /* atomically release the lock AND */
> /* go to sleep on the semaphore */
>
> Simple spinlock primitives are similar (e.g. p_lock ...), but the last
> primitive above is the key to avoiding many races. The classic coding style
> in DYNIX/ptx (this for buffer allocation) is then:
>
> dmabuf_init(...);
> {
> ...
> init_sema(&dmabuf_wait, 0);
> init_lock(&dmabuf_mutex);
> ...
> }
>
> dmabuf_alloc(...)
> {
> spl_t saved_spl;
> ...
> while (1) {
> saved_spl = p_lock(&dmabuf_mutex, SPLSWP);
> attempt to grab a free buffer;
> if (success){
> v_lock(&dmabuf_mutex, saved_spl);
> return;
> } else {
> p_sema_v_lock(&dmabuf_wait, PSWP+1, &dmabuf_mutex);
> }
> }
> }
>
> dmabuf_free(...)
> {
> spl_t saved_spl;
> ...
> saved_spl = p_lock(&dmabuf_mutex, SPLHI);
> free up buffer;
> if (blocked_sema(&dmabuf_wait)) {
> vall_sema(&dmabuf_wait);
> }
> v_lock(&dmabuf_mutex, s);
> }
>
> As you can see, the spinlocks ensure no races, and the key is the atomicity
> of p_sema_v_lock(). No-one can race in and sleep on dmabuf_wait, because
> they have to hold dmabuf_mutex to do so. Exactly the same mechanism would
> work for the bdflush problem.
Yes, I see. There are a lot of similarities to the situation I
described. The main difference between this situation and bdflush is
that dmabuf_free isn't really waiting on dmabuf_alloc to fullfill a
condition (other than to get out of its exclusion region) while bdflush
can have n waiters.
If I could have a new primitive for this job it would be up_down(sem1,
sem2), atomic with respect to a sleeper on sem1. And please give me an
up_all for good measure. Then for a task wanting to wait on bdflush I
could write:
up_down(&bdflush_request, &bdflush_waiter);
And in bdflush, just:
up_all(&bdflush_waiter);
down(&bdflush_request);
But I found I could do the job with existing primitives so I did.
Originally I wrote:
int waiters = xchg(&bdflush_waiters.count, 0);
while (waiters--)
up(&bdflush_waiter);
which uses one less atomic op but, as Philip Rumpf pointed out to me,
doesn't work on Sparc. Oh well. On Intel, the extra read is
practically free. I could have gone at it by making a new primitive:
int atomic_read_and_clear(atomic_t *p)
{
int n = atomic_read(p);
atomic_sub(p, n);
return n;
}
and on arch i86 it would become:
#define atomic_read_and_clear(p) (xchg(p, 0))
> One can argue the relative merits of the different approaches. I suspect that
> the above code is less bus-intensive relative to the atomic inc/dec/count ops,
> but I may be wrong.
I couldn't say, because your mechanism would need to be elaborated a
little to handle bdflush's multiple waiters, and I don't know exactly
what your up_and_wait would look like. Do spinlocks work for bdflush,
or would you have to go to semaphores? (If the latter you arrive at my
up_down primitive, which is interesting.) It's even hard to say whether
my approach is faster or slower than the existing approach. Ultimately,
up() calls wake_up() and down() calls both add_wait_queue()
Re: [RFC] Semaphores used for daemon wakeup
Hi Daniel,
On Tue, Dec 19, 2000 at 02:11:16PM +0100, Daniel Phillips wrote:
[...]
> I'm curious, is my method of avoiding the deadlock race the same as
> yours? My solution is to keep a count of tasks that 'intend' to take
> the down():
>
> atomic_inc(&bdflush_waiters);
> up(&bdflush_request);
> down(&bdflush_waiter);
>
> so that bdflush will issue the correct number of up's even if the waiter
> has not yet gone to sleep. IOW, is your approach in DYNIX the same only
> in spirit, or in detail?
>
> --
> Daniel
OK,
this is not how we generally would achieve the goal, although the approach
looks valid. We have a number of primitives available that are not currently
used in Linux (unless I'm losing my eyesight :-)
We use p_sema, and v_sema for down and up respectively (this was done many
years ago, and the names are in deference to Edsger Dijkstra.
For normal semaphores (as opposed to read/writer or other variants), we have
sema_t sema;
init_sema(&sema, 1);/* initialize semaphore & set initial count */
p_sema(&sema, PZERO); /* "grab" semaphore and set process priority */
/* priority < PZERO == sleep uninterruptibly */
v_sema(&sema); /* release semaphore (i.e. increment count) */
cp_sema(&sema); /* Attempt to grab semaphore iff free else EBUSY */
vall_sema(&sema); /* Wake up all sleepers on this semaphore */
blocked_sema(&sema);/* boolean: any sleepers ? */
p_sema_v_lock(&sema, priority, &lock); /* atomically release the lock AND */
/* go to sleep on the semaphore */
Simple spinlock primitives are similar (e.g. p_lock ...), but the last
primitive above is the key to avoiding many races. The classic coding style
in DYNIX/ptx (this for buffer allocation) is then:
dmabuf_init(...);
{
...
init_sema(&dmabuf_wait, 0);
init_lock(&dmabuf_mutex);
...
}
dmabuf_alloc(...)
{
spl_t saved_spl;
...
while (1) {
saved_spl = p_lock(&dmabuf_mutex, SPLSWP);
attempt to grab a free buffer;
if (success){
v_lock(&dmabuf_mutex, saved_spl);
return;
} else {
p_sema_v_lock(&dmabuf_wait, PSWP+1, &dmabuf_mutex);
}
}
}
dmabuf_free(...)
{
spl_t saved_spl;
...
saved_spl = p_lock(&dmabuf_mutex, SPLHI);
free up buffer;
if (blocked_sema(&dmabuf_wait)) {
vall_sema(&dmabuf_wait);
}
v_lock(&dmabuf_mutex, s);
}
As you can see, the spinlocks ensure no races, and the key is the atomicity
of p_sema_v_lock(). No-one can race in and sleep on dmabuf_wait, because
they have to hold dmabuf_mutex to do so. Exactly the same mechanism would
work for the bdflush problem.
One can argue the relative merits of the different approaches. I suspect that
the above code is less bus-intensive relative to the atomic inc/dec/count ops,
but I may be wrong.
Regards,
Tim
--
Tim Wright - [EMAIL PROTECTED] or [EMAIL PROTECTED] or [EMAIL PROTECTED]
"Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI
-
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/
Re: [RFC] Semaphores used for daemon wakeup
Tim Wright wrote: > > On Sun, Dec 17, 2000 at 01:06:10PM +0100, Daniel Phillips wrote: > > This patch illustrates an alternative approach to waking and waiting on > > daemons using semaphores instead of direct operations on wait queues. > > The idea of using semaphores to regulate the cycling of a daemon was > > suggested to me by Arjan Vos. The basic idea is simple: on each cycle > > a daemon down's a semaphore, and is reactivated when some other task > > up's the semaphore. > [...] > > > > OK, there it is. Is this better, worse, or lateral? > > Well, I have to confess I'm rather fond of this method, but that could have > something to do with it being how we did it in DYNIX/ptx (Sequent). > It certainly works, and I find it very clear, but of course I'm biased :-) I'm curious, is my method of avoiding the deadlock race the same as yours? My solution is to keep a count of tasks that 'intend' to take the down(): atomic_inc(&bdflush_waiters); up(&bdflush_request); down(&bdflush_waiter); so that bdflush will issue the correct number of up's even if the waiter has not yet gone to sleep. IOW, is your approach in DYNIX the same only in spirit, or in detail? -- Daniel - 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/
Re: [RFC] Semaphores used for daemon wakeup
Daniel Phillips wrote: > The idea of using semaphores to regulate the cycling of a daemon was > suggested to me by Arjan Vos. Actually, his name is Arjan van de Ven - sorry Arjan :-o Thanks also to Phillip Rumpf for auditing this patch for cross-platform correctness. -- Daniel - 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/
Re: [RFC] Semaphores used for daemon wakeup
On Sun, Dec 17, 2000 at 01:06:10PM +0100, Daniel Phillips wrote: > This patch illustrates an alternative approach to waking and waiting on > daemons using semaphores instead of direct operations on wait queues. > The idea of using semaphores to regulate the cycling of a daemon was > suggested to me by Arjan Vos. The basic idea is simple: on each cycle > a daemon down's a semaphore, and is reactivated when some other task > up's the semaphore. [...] > > OK, there it is. Is this better, worse, or lateral? Well, I have to confess I'm rather fond of this method, but that could have something to do with it being how we did it in DYNIX/ptx (Sequent). It certainly works, and I find it very clear, but of course I'm biased :-) Tim -- Tim Wright - [EMAIL PROTECTED] or [EMAIL PROTECTED] or [EMAIL PROTECTED] "Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI - 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/
Re: [RFC] Semaphores used for daemon wakeup
On Sun, 17 Dec 2000, Daniel Phillips wrote: > This patch illustrates an alternative approach to waking and waiting on > daemons using semaphores instead of direct operations on wait queues. > The idea of using semaphores to regulate the cycling of a daemon was > suggested to me by Arjan Vos. The basic idea is simple: on each cycle > a daemon down's a semaphore, and is reactivated when some other task > up's the semaphore. > Is this better, worse, or lateral? This is much better, especially from a maintainability point of view. It is also the method that a lot of operating systems already use. Nigel Gamble[EMAIL PROTECTED] Mountain View, CA, USA. http://www.nrg.org/ - 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/
