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.
Sometimes an activating task wants to wait until the daemon completes
whatever it's supposed to do - flushing memory in this case. I
generalized the above idea by adding another semaphore for wakers to
sleep on, and a count variable to let the daemon know how many
sleepers it needs to activate. This patch updates bdflush and
wakeup_bdflush to use that mechanism.
The implementation uses two semaphores and a counter:
DECLARE_MUTEX_LOCKED(bdflush_request);
DECLARE_MUTEX_LOCKED(bdflush_waiter);
atomic_t bdflush_waiters /*= 0*/;
A task wanting to activate bdflush does:
up(&bdflush_request);
A task wanting to activate bdflush and wait does:
atomic_inc(&bdflush_waiters);
up(&bdflush_request);
down(&bdflush_waiter);
When bdflush has finished its work it does:
waiters = atomic_read(&bdflush_waiters);
atomic_sub(waiters, &bdflush_waiters);
while (waiters--)
up(&bdflush_waiter);
down(&bdflush_request);
Since I wasn't sure whether the side effect in the existing code of
setting the current task RUNNING was really wanted, I wrote this in
explicitly in the places where the side effect was noted, with the
obligatory comment.
I've done some fairly heavy stress-testing and this new scheme (but
not on non-x86 or SMP) and it does seem to work much the same as the
existing one. I doubt that there is a measureable difference in
execution overhead, nor is there a difference in correctness as far as
I can see. But for me at least, it's considerably easier to verify
that the semaphore approach is correct.
OK, there it is. Is this better, worse, or lateral?
--
Daniel
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/
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
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
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
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
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() 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.
--
Daniel
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
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 problems when put into the xfs tree an run through a
stress test. I don't remember what kernel version that tree was, but it
was before the TASK_EXCLUSIVE change..
*/
typedef void sv_mon_lock_t;
typedef void (*sv_mon_unlock_func_t)(sv_mon_lock_t *lock);
/* sv_flags values: */
#define SV_ORDER_FIFO 0x001
#define SV_ORDER_FILO 0x002
/* If at some point one order becomes preferable to others, we can
use that order when sv_init() isn't given an order. */
#define SV_ORDER_DEFAULT SV_ORDER_FIFO
#define SV_ORDER_MASK 0x00f
#define SV_MON_SEMA 0x010
#define SV_MON_SPIN 0x020
#define SV_MON_MASK 0x0f0
/*
Set if the monitor lock can be aquired from interrupts. Note that this
is a superset of the cases in which the sv itself can be touched from
interrupts.
This is only valid when the monitor lock is a spinlock.
If this is used, sv_wait(), sv_signal(), and sv_broadcast() must all be
called with interrupts disabled, which had to have happened anyway to
have acuired the monitor spinlock.
*/
#define SV_INTS 0x100
/* sv_wait_flag values: */
/* Allow sv_wait() to be interrupted by a signal */
#define SV_WAIT_SIG 0x001
typedef struct sv_s {
wait_queue_head_t sv_waiters;
/* Lock held to ensure exclusive access to monitor. */
sv_mon_lock_t *sv_mon_lock;
sv_mon_unlock_func_t sv_mon_unlock_func;
spinlock_t sv_lock; /* Spinlock protecting the sv itself. */
int sv_flags;
} sv_t;
#define DECLARE_SYNC_VARIABLE(sv, l, f) sv_t sv = sv_init(&sv, l, f)
kernel/sv.c:
static inline void sv_lock(sv_t *sv) {
spin_lock(&sv->sv_lock);
}
static inline void sv_unlock(sv_t *sv) {
spin_unlock(&sv->sv_lock);
}
/* up() and spin_unlock() may be inline or macros; the real version
uses wrappers for them. */
static inline void sv_set_mon_type(sv_t *sv, int type) {
switch (type) {
case SV_MON_SPIN:
sv->sv_mon_unlock_func = spin_unlock;
break;
case SV_MON_SEMA:
sv->sv_mon_unlock_func = up;
if(sv->sv_flags & SV_INTS) {
printk(KERN_ERR "sv_set_mon_type: The monitor lock "
"cannot be shared with interrupts if it is a "
"semaphore!\n");
BUG();
}
break;
default:
BUG();
}
sv->sv_flags |= type;
}
static inline void sv_set_ord(sv_t *sv, int ord) {
if (!ord)
ord = SV_ORDER_DEFAULT;
if (ord != SV_ORDER_FIFO && ord != SV_ORDER_LIFO) {
BUG();
}
sv->sv_flags |= ord;
}
/*
* sv the sync variable to initialize
* monitor_lock the lock enforcing exclusive running in the monitor
* flags one of
* SV_MON_SEMA monitor_lock is a semaphore
* SV_MON_SPIN monitor_lock is a spinlock
* and a bitwise or of some subset of
* SV_INTS - the monitor lock can be acquired from interrupts (and
* hence, whenever we hold it, interrupts are disabled (or
* we're in an interrupt.)) This is only valid when the sv
* is of type SV_MON_SPIN.
*/
void sv_init(sv_t *sv, sv_mon_lock_t *lock, int flags)
{
int ord = flags & SV_ORDER_MASK;
int type = flags & SV_MON_MASK;
/* Copy all non-order, non-type flags */
sv->sv_flags = flags & ~(SV_ORDER_MASK | SV_MON_MASK);
sv_set_ord(sv, ord);
sv_set_mon_type(sv, type);
sv->sv_mon_lock = lock;
spin_lock_init(&sv->sv_lock);
init_waitqueue_head(&sv->sv_waiters);
}
/*
* The associated lock must be locked on entry. It is unlocked on return.
*
* Set SV_WAIT_SIG in sv_wait_flags to let the sv_wait be interrupted
* by signals.
*
* timeout is how long to wait before giving up, or 0 to wait
* indefinately. It is given in jiffies, and is relative.
*
* Return values:
*
* n < 0 : interrupted, -n jiffies remaining on timeout, or -1 if timeout == 0
* n = 0 : timeout expired
* n > 0 : sv_signal()'d, n jiffies remaining on timeout, or 1 if timeout == 0
*/
signed long sv_wait(sv_t *sv, int sv_wait_flags, unsigned long timeout)
{
DECLARE_WAITQUEUE( wait, current );
signed long ret = 0;
sv_lock(sv);
sv->sv_mon_unlock_func(sv->sv_mon_lock);
/* Add ourselves to the wait queue and set the state before
releasing the sv_lock so as to avoid racing with wake_up in
sv_signal() and sv_broadcast. */
switch(sv->sv_flags & SV_ORDER_MASK) {
case SV_ORDER_FIFO:
add_wait_queue_exclusive(&sv->sv_waiters, &wait);
break;
case SV_ORDER_FILO:
add_wait_queue(&sv->sv_waiters, &wait);
break;
default:
BUG();
}
if(sv_wait_flags & SV_WAIT_SIG)
set_current_state(TASK_EXCLUSIVE | TASK_INTERRUPTIBLE );
else
set_current_state(TASK_EXCLUSIVE | TASK_UNINTERRUPTIBLE);
if(sv->sv_flags & SV_INTS)
spin_unlock_irq(&sv->sv_lock);
else
spin_unlock(&sv->sv_lock);
if (timeout)
ret = schedule_timeout(timeout);
else
schedule();
if(current->state != TASK_RUNNING) /* XXX Is this possible? */ {
printk(KERN_ERR "sv_wait: state not TASK_RUNNING after "
"schedule().\n");
set_current_state(TASK_RUNNING);
}
remove_wait_queue(&sv->sv_waiters, &wait);
/* Return cases:
- woken by a sv_signal/sv_broadcast
- woken by a signal
- woken by timeout expiring
*/
/* FIXME: This isn't really accurate; we may have been woken
before the signal anyway.... */
if(signal_pending(current))
return timeout ? -ret : -1;
return timeout ? ret : 1;
}
void sv_signal(sv_t *sv)
{
/* If interrupts can acquire this lock, they can also acquire the
sv_mon_lock, which must be held to have called this, so
interrupts must be disabled already. If interrupts cannot
contend for this lock, we don't have to disable them. */
sv_lock(sv);
wake_up(&sv->sv_waiters);
sv_unlock(sv);
}
void sv_broadcast(sv_t *sv)
{
sv_lock(sv);
wake_up_all(&sv->sv_waiters);
sv_unlock(sv);
}
/*
* These files are subject to the terms and conditions of the GNU General Public
* License.
*
* Copyright (C) 2000 Silicon Graphics, Inc. All rights reserved.
*
* Paul Cassella <[email protected]>
*/
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
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
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
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]
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
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
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
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