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.

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().

The same protections are in place here, as the two methods are basically the same.

This could be done with two sv's. After all, there are two conditions:
"someone needs bdflush to run", and "bdflush is done".

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().

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

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

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/

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/

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/

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.

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/

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?)

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/

On Fri, Dec 22, 2000 at 12:46:28PM +0100, Daniel Phillips wrote:
[...]

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.

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/

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).

Then it's most probably that way in Linux too, but __wake_up_common will take a little time to digest.

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.

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/

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 <asm/smp.h>
#include <asm/spinlock.h>
#include <asm/semaphore.h>
#include <linux/debug.h>
#include <linux/interrupt.h>
#include <linux/version.h>

#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 semaphore	lock;
		} blocking;
	} mutex_u;
	pid_t		holder;
#if	defined(DEBUG_MUTEX)
	char		name[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
mutex_held(mutex_t *l)

{
	return (l->holder == MY_PID);
}

/*
* really we want to be using spin_lock_irqsave/spin_unlock_irqrestore -
* however there's no trylock functional interface.
*/

#if LINUX_VERSION_CODE < KERNEL_VERSION(2,3,0)
#if defined(__alpha__) || defined(__sparc__)
#define local_irq_save(x) __save_and_cli(x)
#define local_irq_restore(x) __restore_flags(x)
#elif defined(__i386__)
#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ; cli":"=g" (x): /* no input */ :"memory")
#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl": /* no output */ :"g" (x):"memory")
#else
#error UNKNOWN ARCH.
#endif
#endif

extern __inline__ void debug_mutex_lock(mutex_t *l, char *file, int line)

{	
	unsigned long flags;

	ASSERT(!mutex_held(l));
	switch(l->type) {
		case MUTEX_BLOCK:
			ASSERT(!in_interrupt());
			BS_LOCK(l->mutex_u.blocking.lock);
			break;
		case MUTEX_SPIN_INTR:
			local_irq_save(flags);
			debug_spin_lock(&l->mutex_u.spin.lock, file, line);
			l->mutex_u.spin.flags = flags;
			break;
		case MUTEX_SPIN:
			debug_spin_lock(&l->mutex_u.spin.lock, file, line);
			break;
	}
	l->holder = MY_PID;
}

extern __inline__ void
mutex_unlock(mutex_t *l)

{
	unsigned long flags;

	ASSERT(mutex_held(l));
	l->holder = PID_NONE;
	switch(l->type) {
		case MUTEX_BLOCK:
			BS_UNLOCK(l->mutex_u.blocking.lock);
			break;
		case MUTEX_SPIN_INTR:
			flags = l->mutex_u.spin.flags;
			spin_unlock(&l->mutex_u.spin.lock);
			local_irq_restore(flags);
			break;
		case MUTEX_SPIN:
			spin_unlock(&l->mutex_u.spin.lock);
			break;
	}
}

/*
* Unordered lock releasing - if a spinlock, we need to make sure we
* when l1 is released, we __restore_flags() the value from l. *
* Usage:

 *   mutex_lock(l)
 *   mutex_lock(l1)
 *   mutex_unlock_unordered(l, l1)
 *   mutex_unlock(l1)
 */
extern __inline__ void
mutex_unlock_unordered(mutex_t *l, mutex_t *l1)
{
	unsigned long flags;

	ASSERT(mutex_held(l));
	ASSERT(mutex_held(l1));

	l->holder = PID_NONE;
	switch (l->type) {
		case MUTEX_BLOCK:
			BS_UNLOCK(l->mutex_u.blocking.lock);
			break;
		case MUTEX_SPIN_INTR:
			ASSERT(l1->type == MUTEX_SPIN_INTR);
			flags = l->mutex_u.spin.flags;
			spin_unlock(&l->mutex_u.spin.lock);
			local_irq_restore(l1->mutex_u.spin.flags);
			l1->mutex_u.spin.flags = flags;
			break;
		case MUTEX_SPIN:
			spin_unlock(&l->mutex_u.spin.lock);
			break;
	}
}

/*
* Returns nonzero if lock has been acquired. */
extern __inline__ int debug_mutex_trylock(mutex_t *l, char *file, int line)

{
	int res;
	unsigned long flags;

	ASSERT(!mutex_held(l));
	switch(l->type) {
		case MUTEX_BLOCK:
			ASSERT(!in_interrupt());
			res = BS_TRY(l->mutex_u.blocking.lock);
			break;
		case MUTEX_SPIN_INTR:
			local_irq_save(flags);
			res = (debug_spin_trylock(&l->mutex_u.spin.lock, 
					file, line) != 0);
			if (res)
				l->mutex_u.spin.flags = flags;
			else
				local_irq_restore(flags);
			break;
		case MUTEX_SPIN:
			res = (debug_spin_trylock(&l->mutex_u.spin.lock, file, line) != 0);
			break;
	}
	if (res)
		l->holder = MY_PID;
	return res;
}

#endif /* __KERNEL__ */
#endif /* _LINUX_MUTEX_H */

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

*
* Condition variables.
* Jim Garlick <[email protected]>
*/

#if !defined(_LINUX_CONDVAR_H)
#define _LINUX_CONDVAR_H

#if defined(__KERNEL__)

#include <linux/list.h>
#include <linux/debug.h>
#include <linux/mutex.h>

#define CV_RET_SIGPENDING 0
#define CV_RET_TIMEOUT (-1)
#define CV_RET_NORMAL 1

#define CV_MAX_NAME 16

struct cv_task {
struct task_struct *task; /* need to wrap task in this */
struct list_head list; /* to thread as a list */
int blocked;
};

typedef struct {
	struct list_head	task_list; 	/* list of cv_task's */
						/*   that are waiting on cv */
#if	defined(DEBUG_CV)
	char 			name[CV_MAX_NAME];

#endif
} condvar_t;

#if defined(DEBUG_CV)
#define LOCK_NAME(c) (c)->name
#else
#define LOCK_NAME(c) "<unknown>"
#endif

#define cv_wait(c,l) debug_cv_wait(c, l, 0, 0, __BASE_FILE__, __LINE__)
#define cv_waitsig(c,l) debug_cv_wait(c, l, 0, 1, __BASE_FILE__, __LINE__)
#define cv_timedwait(c,l,to) debug_cv_wait(c, l, to, 0, __BASE_FILE__, __LINE__)
#define cv_timedwaitsig(c,l,to) debug_cv_wait(c, l, to, 1, __BASE_FILE__, __LINE__)
#define cv_wakeup_one(c,l) cv_wakeup(c, l, 0)
#define cv_wakeup_all(c,l) cv_wakeup(c, l, 1)

extern __inline__ void
cv_init(condvar_t *c, char *name)

{
	INIT_LIST_HEAD(&c->task_list);
#if	defined(DEBUG_CV)
	strncpy(c->name, name, CV_MAX_NAME);

#endif
}

extern __inline__ void
cv_destroy(condvar_t *c)

{
	ASSERT(list_empty(&c->task_list));
}

/*
* We thread a struct cv_task, allocated on the stack, onto the condvar_t's
* task_list, and take it off again when we wake up.
* Note: the reason we avoid using TASK_UNINTERRUPTIBLE is that avenrun
* computation treats it like TASK_RUNNABLE. The cvt.blocked flag
* distinguishes a signal wakeup from a cv_wakeup.
*/
extern __inline__ int
debug_cv_wait(condvar_t *c, mutex_t *l, long tmo, int interruptible,
char *file, int line)

{
	struct cv_task cvt;
	int ret = CV_RET_NORMAL;

	ASSERT(!in_interrupt());		/* we can block */
	ASSERT(mutex_held(l));			/* enter holding lock */
	/*DBF("cv_wait:\tsleep %s %d:%d\n", LOCK_NAME(c), MY_PID, MY_CPU);*/
	cvt.task = current;
	cvt.blocked = 1;
	list_add(&cvt.list, &c->task_list);
	do {
		current->state = TASK_INTERRUPTIBLE;
		mutex_unlock(l);		/* drop lock for sleep */
		if (tmo) {
			if (tmo <= jiffies || !schedule_timeout(tmo - jiffies))
				ret = CV_RET_TIMEOUT;
		} else
			schedule();
		debug_mutex_lock(l, file, line); /* pick up lock again */
		if (interruptible && signal_pending(current))
			ret = CV_RET_SIGPENDING;
	} while (cvt.blocked && ret == CV_RET_NORMAL);
	list_del(&cvt.list);
	/*DBF("cv_wait:\tawake %s %d:%d %s\n", 
	    LOCK_NAME(c), MY_PID, MY_CPU, ret == CV_RET_TIMEOUT ? "timeout" : 
	    (ret == CV_RET_SIGPENDING) ? "sigpending" : "normal");*/
	return ret;				/* return holding lock */
}

extern __inline__ void
cv_wakeup(condvar_t *c, mutex_t *l, int wakeall)

{
	struct list_head *lp;
	struct cv_task *cvtp;

	ASSERT(mutex_held(l)); 			/* already holding lock */
	for (lp = c->task_list.next; lp != &c->task_list; lp = lp->next) {
		cvtp = list_entry(lp, struct cv_task, list);
		if (cvtp->blocked) {
			/*DBF("cv_wakeup:\twaking %s pid=%d %d:%d\n", 
			    LOCK_NAME(c), p->pid, MY_PID, MY_CPU);*/
			cvtp->blocked = 0;
			/* wake_up_process added to kernel/ksyms.c */
			wake_up_process(cvtp->task); 
			if (!wakeall)
				break;
		}
	}
}						/* return still holding lock */

#endif /* __KERNEL__ */
#endif /* _LINUX_CONDVAR_H */