Futexes IV (Fast Lightweight Userspace Semaphores)

The normal way to use multithreading under UNIX is the pthread library. Here the condition variables are the equivalent to kernel wait queues. So I think to really implement a fast pthread lib based on futexes one needs some means to implement condition variables (with synchronous futex release to implement pthread_cond_wait(..)!).

This could either be done with the exported waitqueue approach or a bit easier (but less general) by associating a second hashed waitqueue with each futex (maybe marked by the odd offset+1?). Then we would have two additional variants of sys_futex (with parameters FUTEX_WAIT, FUTEX_SIGNAL).

The principle implementation is:

FUTEX_WAIT:
add_to_cond_queue
current->state=INTERRUPTIBLE
futex_up
schedule
remove_from_cond_queue
futex_down

FUTEX_SIGNAL
wake_up_all on cond_queue

Later we may also want FUTEX_SIGNAL_ONE and FUTEX_WAIT_TIMEOUT.

The user space code for pthread_cond_wait then of course needs a chaining of the protecting pthread_mutex and the futex used as condition variable.

Martin

Let me mention this again... The IBM release of NGPT states that Linus has approved the inclusion of the NGPT patches in the mainline kernel. Will this be in 2.4.19 release? I've been running 2.4.17 for NGPT, haven't tried 2.4.19 other than to see the patch didn't apply).

(NGPT = Next Generation Pthreads, a cleaner and faster POSIX threads)

bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

--On Wednesday, March 13, 2002 02:41:52 PM -0500 Bill Davidsen

The 2.4 patch needed for NGPT was accepted by Marcelo and is in 2.4.19-pre3.

Dave McCracken

======================================================================
Dave McCracken IBM Linux Base Kernel Team 1-512-838-3059
[email protected] T/L 678-3059

2.5 but hopefully it will get backported as it proves solid and the API is fixed

Good info, thanks! I hand edited the 2.4.17 patch to 2.4.18, but 19-pre2 didn't apply and I ran out of time about 1am this morning;-) When pre3 settles down a bit I'll use that as a base.

bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

In message <[email protected]> you write:

Discussions with Ulrich have reaffirmed my opinion that pthreads are crap. Hence I'm not all that tempted to warp the (nice, clean, usable) futex code too far to meet pthreads' wierd needs.

However, it's not too hard to implement condition variables using an unavailable mutex, if we go for "full" semaphores: ie. not just mutexes. It requires a bit more of a stretch for kernel atomic ops...

Yet another untested patch,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.7-pre1/kernel/futex.c working-2.5.7-pre1-sem/kernel/futex.c
@@ -129,17 +129,18 @@
 	return page;
 }
 
-/* Try to decrement the user count to zero. */
-static int decrement_to_zero(struct page *page, unsigned int offset)
+/* Try to decrement the user count to >= zero. */
+static int decrement_futex(struct page *page, unsigned int offset)
 {
 	atomic_t *count;
 	int ret = 0;
 
 	count = kmap(page) + offset;
-	/* If we take the semaphore from 1 to 0, it's ours.  If it's
-           zero, decrement anyway, to indicate we are waiting.  If
-           it's negative, don't decrement so we don't wrap... */
-	if (atomic_read(count) >= 0 && atomic_dec_and_test(count))
+	/* If we take one from the sem, and it's still >= 0, it's
+           ours.  If it's zero, we decrement anyway to indicate we are
+           waiting.  If it's negative, don't decrement so we don't
+           wrap... */
+	if (atomic_read(count) >= 0 && !atomic_add_negative(-1, count))
 		ret = 1;
 	kunmap(page);
 	return ret;

@@ -173,12 +174,36 @@
 	return retval;
 }
 
+/* Atomically: Add 1 if already positive, otherwise set to 1. */
+static void futex_make_positive(atomic_t *count)
+{
+	int old_count, new_count;
+
+#ifndef CONFIG_SMP
+	preempt_disable();
+	old_count = atomic_read(count);
+	new_count = old_count > 0 ? old_count+1 : 1;
+	atomic_set(count, new_count);
+	preempt_enable();
+#elif defined(__HAVE_ARCH_CMPXCHG)
+	do {
+		old_count = atomic_read(count);
+		new_count = old_count > 0 ? old_count+1 : 1;
+	} while (cmpxchg(count, old_count, new_count) != old_count);
+#else
+	/* Do this one at a time.  You will need to implement
+	   atomic_add_positive(). */
+	while (!atomic_add_positive(count, 1));
+#endif
+}
+
 static int futex_up(struct list_head *head, struct page *page, int offset)
 {
 	atomic_t *count;
 
 	count = kmap(page) + offset;
-	atomic_set(count, 1);
+	/* set to MAX(count, 0) + 1 */
+	futex_make_positive(count);
 	smp_wmb();
 	kunmap(page);
 	wake_one_waiter(head, page, offset);

Crap or not, there are tons of software based on pthreads and at least the NGPT team says that Linus agreed to implement for necessary kernel-infrastructure for a full, fast pthread implementation.

Now, if you want to implement mutexes and condition variables with the attribute PTHREAD_PROCESS_SHARED then you need some functionality like the futexes. Or NGPT will add his own syscalls to handle these things, which is simply unnecessary double functionality.

A full semaphore is nice, but not a full replacement for a waitqueue (or a pthread condition variable brr..). For the semaphore you always have to assure that the ups and downs are balanced, what is not the case for the condition variable.

Martin

Folks, its not that simple as "use futex for PTHREAD_PROCESS_SHARED". First, you must realize that conceptually, the N kernel threads utilized in a M:N thread model like NGPT are virtual processors. Hence you can't simply wait in the kernel as you would block your v-proc. Hence the current futex interface of up and down kernel calls in not sufficient.

What is required is an asynchronous mechanism that lets a v-proc leave a notification object <nobj> in the kernel that get's enqueued just like every other waiting task. <nobj> ::= <v-proc, struct *futex> When the futex is signaled and <nobj> is woken up, a scheduling event is send to the <v-proc> or its task or its process (this has to be thought through). This can be done through a signal or through an shared event queue or a combination of such.

Under no circumstances can you block the <v-proc> == task on a futex !!!

I talked with Bill Abt of the NGPT team about it and he conceptually agrees with this approach, but since the regular interface is still not hammered out and stable, no point going after more sophisticated stuff yet.

-- Hubertus Franke  ([email protected])

I think the "crap" refers to current missing meatures of linuxthreads (most notable: PTHREAD_PROCESS_SHARED on cond and mutex, don't know about sema)

BTW, NGPT introduces two new syscalls: gettid and tkill

also remember pthread_cond_broadcast - waking up _all_ waiting threads. If the woken up threads check their condition and go to sleep again, is up to them ( read: the standard mandates that _all_ get woken up)

pthread_cond_signal notifies _one_ thread - which one depends on implementation ( I would like to see a priority based decision )

In message <[email protected]> you write:

Let me clarify my "pthreads are crap" statement.

I firmly believe that there is a place for clone & futex threaded programs, which is not met by pthreads for cleanliness and performance reasons, and that such programs will become increasingly important.

Therefore I refuse to penalise such progressive programs so we can have standards compliance. Hence my insistance on a clean, minimal, useful interface.

on

The solution I was referring to before, using full semaphores, would look like so:

struct pthread_cond_t

{
	int num_waiting;
	struct futex wait, ack;
};

#define PTHREAD_COND_INITIALIZER { 0, { 0 }, { 0 } }

int pthread_cond_signal(pthread_cond_t *cond)

{
	if (cond->num_waiters)
		return futex_up(&cond->futex, 1);
	return 0;
}

int pthread_cond_broadcast(pthread_cond_t *cond)

{
	unsigned int waiters = cond->num_waiting;

	if (waiters) {
		futex_up(&cond->futex, waiters);
		/* Wait for ack before returning. */
		futex_down(&cond->ack);
	}
	return 0;
}

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)

{
	int ret;

	/* Increment first so broadcaster knows we are waiting. */
	atomic_inc(cond->num_waiting);
	futex_up(&mutex, 1);
	ret = futex_down(&cond);
	if (atomic_dec_and_test(cond->num_waiting))
		futex_up(&cond->ack);
	futex_down(&mutex->futex);
	return ret;
}

Hope that clarifies,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

In principle that works. But one of things that's less nice with pthread_cond_wait is
that you sometimes have a (most of the time) unnecessary schedule ping-pong, and with the
approach above you always have this (due to ack). And secondly if futex_up(&f, N) for N > 1
relies on the chained wakeup in the kernels futex_up routine the broadcast may take a while to
complete (the lowest priority waiter penalizes all others queued behind him). A semaphore simply is no full replacement for a waitqueue with wake_all.

Martin

P.S. With respect to pthreads I was not thinking of a bloated N:M library, but of some simple fast pthread semantics compatible wrapper for _clone etc.

I have to correct myself. This is the description of SUSV2 about pthread_cond_signal/broadcast:

---snip---
These two functions are used to unblock threads blocked on a condition variable.

The pthread_cond_signal() call unblocks at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond).

The pthread_cond_broadcast() call unblocks all threads currently blocked on the specified condition variable cond.

If more than one thread is blocked on a condition variable, the scheduling policy determines the order in which threads are unblocked. When each thread unblocked as a result of a pthread_cond_signal() or pthread_cond_broadcast() returns from its call to pthread_cond_wait() or pthread_cond_timedwait(), the thread owns the mutex with which it called pthread_cond_wait() or pthread_cond_timedwait(). The thread(s) that are unblocked contend for the mutex according to the scheduling policy (if applicable), and as if each had called pthread_mutex_lock().

The pthread_cond_signal() or pthread_cond_broadcast() functions may be called by a thread whether or not it currently owns the mutex that threads calling pthread_cond_wait() or pthread_cond_timedwait() have associated with the condition variable during their waits; however, if predictable scheduling behaviour is required, then that mutex is locked by the thread calling pthread_cond_signal() or pthread_cond_broadcast().

The pthread_cond_signal() and pthread_cond_broadcast() functions have no effect if there are no threads currently blocked on cond.

RETURN VALUE

If successful, the pthread_cond_signal() and pthread_cond_broadcast() functions return zero. Otherwise, an error number is returned to indicate the error.

ERRORS

The pthread_cond_signal() and pthread_cond_broadcast() function may fail if:

[EINVAL]
The value cond does not refer to an initialised condition variable.

These functions will not return an error code of [EINTR].
--snip---

So the semantic of a condvar implies that when returning from a "succesful" wait [ i.e. not ETIMEDOUT] , the thread owns the mutex. Therefore the scheduler _should_ only wake up the highest priority waiting thread - it does not matter if we signal or broadcast! It's the same operation in effect. Perhaps the broadcast is there for implementations that wouldn't queue up (or wake up) the waiters in priority order?

For this, I think, kernel support is best, since the waiters get woken up in priority order giving wake_one semantics.

For pthread_cond_timedwait() a kernel timer is necessary. So making the signal/broadcast a syscall that does NOT lead to a context switch would be benefical. At the next scheduling point the kernel decides whom to wake up, also checking for timed waiters to return with ETIMEDOUT.

Then there is the issue with a crashing process holding locks. I think on IRIX the waiters get a trap causing them to die - what else one could do?

[after writing and deleting some pseudo code]

I think the condvars are best implemented in shmem + kernel semaphores. The only issue is a pthread_cond_timedwait - but a semaphore op IS interruptible. Besides alarm(2)/setitimer(2) - what are other timeout mechanisms in Linux?

In QNX Neutrino you have TimerTimeout() to arm a kernel timeout for any blocking state (to avoid the window in alarm/timer_settime and the blocking function call)

Without this you can hardly implement a reliable timeout (with sub second resolution) for pthread_cond_timedwait or sigtimedwait.

So for PTHREAD_PROCESS_PRIVATE one could use futexes - on PTHREAD_PROCESS_SHARED it has to reside in the kernel anyway and you naturally have to live with context switches and a performance hit.

Now the problem with N:M threading model: here it's necessary to prevent the kernel from blocking the whole process? Well, what is pthread_setconcurrency(int new_level) for?

And, what is so bad about condvars? How would you implement a typical consumer/producer problem?

To cite Stevens (Vol II, page 165):
... "mutexes are for locking and cannot be used for waiting." page 167: "A mutex is for locking and a condition variable is for waiting. ... and both are needed"

-----------------------------------------------------------------------
Peter Waechtler

[snip]

Only vs. pthread_cond_broadcast. And if you're using that you probably have some other performance issues anyway?

Yes, we could have a "wake N" variant, which would be more efficient here.

Hope that clarifies,
Rusty.

  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

No. pthread_barrier_wait has the same problem. It has to wake up lots of thread.

Why? Conditional variables are of use in situations with loosely coupled threads.

---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

Hmmm....

What do you WANT in a kernel primitive then? Given that we now have mutexes, what else do we need to make pthreads relatively painless?

I meant vs. pthread_cond_signal.

Look, here is an example implementation. Please suggest:
1) Where this is flawed,
2) Where this is suboptimal,
3) What kernel primitive would help to resolve these?

Thanks,
Rusty.

  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

/* Assume we have the following semaphore operations:

   futex_down(futex);
   futex_down_time(futex, relative timeout);
   futex_up(futex, count);
*/
typedef struct
{
	struct futex futex;
} pthread_mutex_t;

typedef struct 
{
	int num_waiting;
	struct futex wait, ack;
} pthread_cond_t;

typedef struct
{
	unsigned int num_left;
	struct futex wait;
	unsigned int initial_count;
} pthread_barrier_t;

#define PTHREAD_MUTEX_INITIALIZER { { 1 } }
#define PTHREAD_COND_INITIALIZER { 0, { 0 }, { 0 } }

int pthread_barrier_init(struct pthread_barrier_t *barrier,
			 void *addr,
			 unsigned int count)
{
	barrier->num_left = barrier->initial_count = count;
	barrier->wait.count = 0;
}

int pthread_barrier_wait(struct pthread_barrier_t *barrier)
{
	if (atomic_dec_and_test(&barrier->num_left)) {
		/* Restore barrier. */
		barrier->num_left = barrier->initial_count;
		/* Wake the other threads */
		futex_up(&barrier->wait, barrier->initial_count-1);
		return 0; /* PTHREAD_BARRIER_SERIAL_THREAD */
	}
	while (futex_down(&barrier->wait) == 0 || errno == EINTR);
	return 1;
}

int pthread_cond_signal(pthread_cond_t *cond)
{
	if (cond->num_waiters)
		return futex_up(&cond->futex, 1);
	return 0;
}

int pthread_cond_broadcast(pthread_cond_t *cond)
{
	unsigned int waiters = cond->num_waiting;

	if (waiters) {
		/* Re-initialize ACK.  Could have been upped by
                   pthread_cond_signal and pthread_cond_wait. */
		cond->ack.count = 0;
		futex_up(&cond->futex, waiters);
		/* Wait for ack before returning. */
		futex_down(&cond->ack);
	}
	return 0;
}

static int __pthread_cond_wait(pthread_cond_t *cond,
			       pthread_mutex_t *mutex,
			       const struct timespec *reltime)
{
	int ret;

	/* Increment first so broadcaster knows we are waiting. */
	atomic_inc(cond->num_waiting);
	futex_up(&mutex, 1);
	do {
		ret = futex_down_time(&cond, reltime);
	} while (ret < 0 && errno == EINTR);
	if (atomic_dec_and_test(cond->num_waiting))
		futex_up(&cond->ack);
	futex_down(&mutex->futex);
	return ret;
}

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)
{
	return __pthread_cond_wait(cond, mutex, NULL);
}

int pthread_cond_timedwait(pthread_cond_t *cond,
			   pthread_mutex_t *mutex,
			   const struct timespec *abstime)
{
	struct timeval _now;
	struct timespec now, rel;

	/* Absolute to relative */
	gettimeofday(&_now, NULL);
	TIMEVAL_TO_TIMESPEC(&_now, &now);
	if (now.tv_sec > abstime->tv_sec
	    || (now.tv_sec == abstime->tv_sec
		&& now.tv_nsec > abstime->tv_nsec))
		return ETIMEDOUT;

	rel.tv_sec = now.tv_sec - abstime->tv_sec;
	rel.tv_nsec = now.tv_usec - abstime->tv_usec;
	if (rel.tv_nsec < 0) {
		--rel.tv_sec;
		rel.tv_nsec += 1000000000;
	}
	return __pthread_cond_wait(cond, mutex, &rel);
}

I think wrt to the mutexes only wake-all is missing. I don't think that semaphore semantic is needed in the kernel.

I'll look at this a bit later.

---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

I. There is a race in __pthread_cond_wait between timeout and a cond_signal or broadcast. If the signal comes in

} while (ret < 0 && errno == EINTR);

	if (atomic_dec_and_test(cond->num_waiting))

then you up cond->wait one time to often, leaving it in an invalid state.

II. Your implementation relies on the fact that the signal or broadcast
caller owns the mutex used in cond_wait. According to the POSIX spec this need not be the case. The only thing that may happen is that you
miss a wakeup. But it is not allowed to screw up the internal state of
of the condition variable, which might well happen in your implementation. (Note: Calling cond_signal without holding the mutex is not necessarily flawed software. Think of a periodically occurring new_data or data_changed flag where it is not really important to sleep race free)

III. Minor nit: You should also clear cond->ack.count in cond_signal otherwise it may wrap around soon (at least for a 24-bit atomic variable) if you mostly use cond_signal.

As said in a previous e-mail, you need an futex_up(..,n) that really wakes_up n thread at once.

Your exported waitqueues or my suggestion for a second waitqueue associated with a futex.

Martin

And have all the waiters exit with errno = EAGAIN? ("You didn't get it but someone wanted you all woken").

It can be done, I'd have to see if is sufficient to implement pthreads.

Rusty.

  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

In message <[email protected]> you write:

Hmmm... this is true.

I hadn't appreciated this. That makes it harder. I think I have to abandon the atomics and use a mutex inside the condition variable.

Yep.

OK, we could read the value in the kernel's up() and wake that many.

Any chance of a rough patch (to the code below, at least)?

Thanks!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

@@ -11,6 +11,7 @@
 
 typedef struct 
 {
+	struct futex lock;
 	int num_waiting;
 	struct futex wait, ack;
 } pthread_cond_t;

@@ -48,23 +49,29 @@
 
 int pthread_cond_signal(pthread_cond_t *cond)
 {
+	futex_down(&cond->lock);
+	/* Reset this so it doesn't overflow */
+	cond->ack.count = 0;
 	if (cond->num_waiters)
 		return futex_up(&cond->futex, 1);
+	futex_up(&cond->lock, 1);
 	return 0;
 }
 
 int pthread_cond_broadcast(pthread_cond_t *cond)
 {
-	unsigned int waiters = cond->num_waiting;
-
-	if (waiters) {
-		/* Re-initialize ACK.  Could have been upped by
-                   pthread_cond_signal and pthread_cond_wait. */
+	futex_down(&cond->lock);
+	if (cond->num_waiting) {
 		cond->ack.count = 0;
+		/* Release the waiters. */
 		futex_up(&cond->futex, waiters);
 		/* Wait for ack before returning. */
 		futex_down(&cond->ack);
+		/* Reset wait, in case someone who was waiting timed
+                   out and didn't decrement. */
+		cond->wait.count = 0;
 	}
+	futex_up(&cond->lock);
 	return 0;
 }
 

@@ -75,8 +82,10 @@
 	int ret;
 
 	/* Increment first so broadcaster knows we are waiting. */
+	futex_down(&cond->lock);
 	atomic_inc(cond->num_waiting);
 	futex_up(&mutex, 1);
+	futex_up(&cond->lock, 1);
 	do {
 		ret = futex_down_time(&cond, reltime);
 	} while (ret < 0 && errno == EINTR);

That's a joke, isn't it? ;-)

We can return -1 with errno=ELOCKBREAK if the process holding the lock

dies.

Why don't we need a semaphore in the kernel?
There is open_sem() for POSIX named semaphores. The SysV interface is there - and it's far more ugly.

in linuxthreads we have:
sem_t *sem_open(const char *name, int oflag, ...)
{
__set_errno (ENOSYS);
return SEM_FAILED;
}

Well, mutexes are not semaphores. Why not have fusema or fuma? They are good for thread pools where you want several workers.

I don't see the necessity for wake_all except for the barrier case.

A condvar implies, that when successfully returning, the thread owns the mutex. So even in the case of cond_broadcast, only one thread will get the mutex - the others will get blocked on that.

The only reason for cond_broadcast I can think of, are implementations that wouldn't wake_up the highest priority waiting thread. So with a broadcast all will be woken up and try to acquire the lock.

The waiters will NOT return without the mutex locked except on ETIMEDOUT (when the thread gets cancelled, the cancelation handler will be called and the thread will die).

It's also written in the spec, that when you want "predictable scheduling" the caller of signal/broadcast _has_to_ hold the mutex. On release of the mutex all other threads will race for it.

I have absolutely no objections whatsoever to get semaphore support in the kernel. It would be much more efficient in some situations and the basic infrastructures is already there. If you can convince the powers there are to accept such a patch I'm all for it.

---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

Up to know I was too focused on the wait functions, but there is
also a problem with cond_broadcast (and the mutex-protected version of cond_signal): since they may block (on ack or lock) this opens up chances for priority inversion like problems. I think to be really usefull cond_broacast and cond_signal should have a non-blocking behaviour with predictible runtime.

Just to convince you that this is a real world problem here is a description of one of my data-aquisition programs:

A 'producer' thread waits for the trigger of a transient recorder at 500 Hz IRQ-rate, reads out 64k on each event into a large circular buffer, calls cond_broadcast (every 5th IRQ) without holding a mutex and goes to sleep to wait for the next IRQ. (This thread is SCHED_FIFO)

Then there are three (SCHED_OTHER) 'consumer' threads which work on the same data doing different things of different importance (group them according to some hardware parameter and store them into different files, calculate averaged powerspectra, select pieces for an online scope-like display etc.)

If in this scenario the producer would have to wait in cond_broadcast until the least prio consumer has acknowledged (which may take a timer tick or longer) he would lose several IRQs each time.

So for my applications a cond_broadcast blocking for the waiters is simply not acceptable.

Martin

[real world example deleted]

Exactly.
I can't see a reason why the ack-futex is needed. I think we can simply delete it.
When deleted, the broadcast wouldn't block on ack (also preventing schedule ping-pong). With the cond->lock it's save to have several broadcasters. That's fine.
But:
static int __pthread_cond_wait(pthread_cond_t *cond,
pthread_mutex_t *mutex,
const struct timespec *reltime)

{
        int ret;

        /* Increment first so broadcaster knows we are waiting. */
	futex_down(&cond->lock);
        atomic_inc(cond->num_waiting);
(*)     futex_up(&mutex, 1);
a)	futex_up(&cond->lock, 1);  [move into syscall]
        do {
b)                ret = futex_down_time(&cond, ABSTIME); [cond_timed_wait]
        } while (ret < 0 && errno == EINTR);
	[futex_up(&cond->lock, 1); /* release condvar */]

        futex_down(&mutex->futex);
        return ret;
}

With the original code, we have a "signal/broadcast lost window (a->b)" that shouldn't be there:

SUSV2 on pthread_cond_[timed]wait:
These functions atomically release mutex(*) and cause the calling thread to block on the condition variable cond; atomically here means "atomically with respect to access by another thread to the mutex and then the condition variable". That is, if another thread is able to acquire the mutex after the about-to-block thread has released it, then a subsequent call to pthread_cond_signal() or pthread_cond_broadcast() in that thread behaves as if it were issued after the about-to-block thread has blocked.

So we would need to enhance the futex_down_timed() call, to atomically release the cond->lock on entry, re-aquiring on exit (because of the loop).
This boils down to a cond_var syscall to me (wouldn't sys_ulock(,,OP) a better name ? with OPs like MUTEX_UP,MUTEX_DOWN, SEMA_UPn, SEMA_DOWNn, COND_WAIT, COND_TIMED_WAIT, COND_SIGNAL, COND_BROADCAST, RWLOCK_WRLOCK, RWLOCK_RDLOCK,RWLOCK_UNLOCK)

Also note that we have to recalculate the relative time to sleep when signalled - or just using an absolute time stamp.
If the syscall is interruptible, we open the "signal/broadcast lost window (a->b)" again... hmh (Here queuing up RT signals are much better for handling the wakeup, because you can block them, and they don't get lost)

Alternatively when using the uwaitq: they could use a lock to serialize an add/wait and a possibly parallel wake operation (but with the above locks you can achieve exactly this)

-----------------------------------------------------------------------
Peter Waechtler

In message <[email protected]> you write:

No, you might end up waking someone who did the pthread_cond_wait() after you did the pthread_cond_broadcast in place of one of the existing pthread_cond_wait() threads.

I don't believe this is allowed.

Where? Having done the inc, the futex_up at (a) will fall through, giving the "thread behaves as if it [signal or broadcast] were issued after the about-to-block thread has blocked."

You're talking about a completely different beast.

So the summary is: futexes not sufficient to implement pthreads locking. That's fine; I can drop all the "extension for pthreads" futex patches and leave the code as-is ('cept the UP_FAIR patch, which is independent of this debate).

Thanks!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

So let's go back to the more generic "exporting waitqueues to userspace" idea, with a twist: we use a userspace address as the identifier on the waitq, which gives us a unique identifier, but the kernel never actually derefs the pointer. (And in my prior kernel code I optimized it so that waking did an implicit remove; not sure it's a win, so assumed that was removed here).

This gives code as below (Peter, Martin, please check):

/* Assume we have the following operations:

uwaitq_add(void *uaddr);
uwaitq_remove(void *uaddr);
uwaitq_wake(void *uaddr, int wake_all_flag);
uwaitq_wait(relative timeout);
*/
typedef struct

{
	int counter;
} pthread_mutex_t;

typedef struct

{
	int condition;
} pthread_cond_t;

typedef struct

{
	unsigned int num_left;
	unsigned int initial_count;
} pthread_barrier_t;

#define PTHREAD_MUTEX_INITIALIZER { { 1 } } #define PTHREAD_COND_INITIALIZER { 0, { 0 }, { 0 } }

int pthread_barrier_init(struct pthread_barrier_t *barrier,
void *addr,
unsigned int count)

{
	barrier->num_left = barrier->initial_count = count;
}

int pthread_barrier_wait(struct pthread_barrier_t *barrier)

{
	/* Use barrier address as uwaitq id. */
	uwaitq_add(barrier);
	if (atomic_dec_and_test(&barrier->num_left)) {
		/* Restore barrier. */
		barrier->num_left = barrier->initial_count;
		/* Wake the other threads */
		uwaitq_wake(barrier, 1 /* WAKE_ALL */);
		uwaitq_remove(barrier);
		return 0; /* PTHREAD_BARRIER_SERIAL_THREAD */
	}
	while (uwaitq_wait(NULL) == 0 || errno == EINTR);
	uwaitq_remove(barrier);
	return 1;
}

int pthread_cond_signal(pthread_cond_t *cond)

{
	return uwaitq_wake(cond, 0 /* WAKE_ONE */);
}

int pthread_cond_broadcast(pthread_cond_t *cond)

{
	return uwaitq_wake(cond, 1 /* WAKE_ALL */);
}

static int __pthread_cond_wait(pthread_cond_t *cond,
pthread_mutex_t *mutex, const struct timespec *reltime)

{
	int ret;

	uwaitq_add(cond);
	futex_up(&mutex, 1);
	while ((ret = uwaitq_wait(reltime)) == 0 || errno == EINTR);
	uwaitq_remove(cond);
	futex_down(&mutex, NULL);
	return ret;
}

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)

{
	return __pthread_cond_wait(cond, mutex, NULL);
}

int pthread_cond_timedwait(pthread_cond_t *cond,
pthread_mutex_t *mutex, const struct timespec *abstime)

{
	struct timeval _now;
	struct timespec now, rel;

	/* Absolute to relative */
	gettimeofday(&_now, NULL);
	TIMEVAL_TO_TIMESPEC(&_now, &now);
	if (now.tv_sec > abstime->tv_sec
	    || (now.tv_sec == abstime->tv_sec
		&& now.tv_nsec > abstime->tv_nsec))
		return ETIMEDOUT;

	rel.tv_sec = now.tv_sec - abstime->tv_sec;
	rel.tv_nsec = now.tv_usec - abstime->tv_usec;
	if (rel.tv_nsec < 0) {
		--rel.tv_sec;
		rel.tv_nsec += 1000000000;
	}
	return __pthread_cond_wait(cond, mutex, &rel);
}

  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

Indeed, I suspect that this isn't wanted.
With the cond->lock you almost prevent this: an ongoing broadcast can't be intermixed with newly incoming waiters (they will block on futex_down(&cond->lock))
But there is the window between a->b...

Right after (a) another thread gets scheduled, issueing a signal/broadcast.

Ah, and then the futex_down_timed() wouldn't block, OK ;-) But this way you have to use the ack->lock

I strongly believe, that the implementation of a condvar needs a lock to prevent intermixed calls. You will see my comment on your implementation with uwaitq. ;-)

Here another thread gets scheduled, calling signal/broadcast. Since the former thread is already on the queue -> well done ;-)

I assume that uwaitq_wait() will modify the reltime (which is legal) if signalled. Otherwise we would wait 2*retime, and so on

Then we have to be careful about errno and the return values:

static int __pthread_cond_wait(pthread_cond_t *cond,
pthread_mutex_t *mutex, const struct timespec *reltime)

{
	int ret;

! if (uwaitq_add(cond) == -1)
+

	return -1;
! if (futex_up(&mutex, 1) == -1){
+ 
	uwaitq_remove(cond);
+ 
	return -1;
+ }
! while ((ret = uwaitq_wait(cond,reltime)) == -1 && errno == EINTR);
+ saverrno=errno;
	uwaitq_remove(cond);
	futex_down(&mutex, NULL);

+ if (ret == -1){
+
if (saverrno == ENOENT)
+
return 0; /* there was a sig/broadc before we went to sleep*/
+

	errno=saverrno;
+ 
	return -1;
+ }
	return 0;
}

I assume that uwaitq_wait() will return -1 and errno==ENOENT or similar if we are not on the queue (anymore), -1 and ETIMEDOUT on timeout, -1 and EINVAL on illegal cond or reltime ,zero on wakeup?

In message <[email protected]> you write:

Oh yeah, I'll have to split that out and handle it. Not worth having the kernel do it as it's hardly going to be a fast path...

Sigh. Yep. I was pretty lax...

uwaitq_wait() which does not follow a uwaitq_add() would be some kind of error, yes. ETIMEDOUT on timeout, yes. EFAULT on illegal cond (that's all it can tell, that the address isn't in the user's range), and 0 on success.

OK, new tidier version...
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

/* Assume we have the following operations:

   uwaitq_add(void *uaddr);
   uwaitq_remove(void *uaddr);
   uwaitq_wake(void *uaddr, int wake_all_flag);
   uwaitq_wait(relative timeout);

And on top of them:
futex_down(struct futex *);
futex_up(struct futex *);
*/
typedef struct futex pthread_mutex_t;

typedef struct
{
int dummy; /* This could be an empty struct for gcc */
} pthread_cond_t;

typedef struct

{
	unsigned int num_left;
	unsigned int initial_count;
} pthread_barrier_t;

#define PTHREAD_MUTEX_INITIALIZER FUTEX_INITIALIZER #define PTHREAD_COND_INITIALIZER { 0 }

int pthread_barrier_init(struct pthread_barrier_t *barrier,
void *addr,
unsigned int count)

{
	barrier->num_left = barrier->initial_count = count;
}

int pthread_barrier_wait(struct pthread_barrier_t *barrier)

{
	int ret;

	/* Use barrier address as uwaitq id. */
	ret = uwaitq_add(barrier);
	if (ret < 0)
		return ret;

	if (atomic_dec_and_test(&barrier->num_left)) {
		/* Restore barrier. */
		barrier->num_left = barrier->initial_count;
		/* Wake the other threads */
		uwaitq_wake(barrier, 1 /* WAKE_ALL */);
		uwaitq_remove(barrier);
		return 0; /* PTHREAD_BARRIER_SERIAL_THREAD */
	}
	while (uwaitq_wait(NULL) == 0 || errno == EINTR);
	uwaitq_remove(barrier);
	return 1;
}

int pthread_cond_signal(pthread_cond_t *cond)

{
	return uwaitq_wake(cond, 0 /* WAKE_ONE */);
}

int pthread_cond_broadcast(pthread_cond_t *cond)

{
	return uwaitq_wake(cond, 1 /* WAKE_ALL */);
}

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)

{
	int ret, saved_errno;

	uwaitq_add(cond);
	futex_up(&mutex);
	while ((ret = uwaitq_wait(NULL)) == 0 || errno == EINTR);
	saved_errno = errno;
	uwaitq_remove(cond);
	futex_down(&mutex);
	errno = saved_errno;
	return ret;
}

int pthread_cond_timedwait(pthread_cond_t *cond,
pthread_mutex_t *mutex, const struct timespec *abstime)

{
	struct timeval _now;
	struct timespec now, rel;
	int saved_errno, ret;

	/* Absolute to relative */
 again:
	gettimeofday(&_now, NULL);
	TIMEVAL_TO_TIMESPEC(&_now, &now);
	if (now.tv_sec > abstime->tv_sec
	    || (now.tv_sec == abstime->tv_sec
		&& now.tv_nsec > abstime->tv_nsec))
		return ETIMEDOUT;

	rel.tv_sec = now.tv_sec - abstime->tv_sec;
	rel.tv_nsec = now.tv_usec - abstime->tv_usec;
	if (rel.tv_nsec < 0) {
		--rel.tv_sec;
		rel.tv_nsec += 1000000000;
	}

	uwaitq_add(cond);
	futex_up(&mutex);
	ret = uwaitq_wait(&rel);
	if (ret < 0 && errno == EINTR)
		goto again;

	saved_errno = errno;
	uwaitq_remove(cond);
	futex_down(&mutex);
	errno = saved_errno;

	return ret;
}

Why not keep the simple one-sys-call interface for the fuxtexes. The code is so small that it is not worth to delete it.

You should loop here in order catch signals:

	while ( futex_down(&mutex) < 0 && errno == EINTR)

This assumes that you are allowed to do a double uwaitq_add.

Also loop here

Now whats interesting is the kernel part. I must admit that I haven't fully understood all effects of the double use of the cookie in your first implementation. But if you use a memory location as identifier you have to keep a separate flag within uwaitq_head that is zeroed before you add to the waitqueue and set by the signal functions. Then uwaitq_wait has to check for it. This is necessary in order not to loose a wakeup while you are on the queue but not sleeping.

uwaitq_remove also takes an argument, are you heading for waiting on multiple events?

Since you need to pin down the page between uwaitq_add and uwaitq_remove you will have to limit the number of simultaneous add calls. Should this be configurable?

Cheers,
Martin

In message <[email protected]> you write:

Because it's a premature optimization. We can add it later if someone proves it's a major hotspot. But it may turn out some other primitive is more important: I'm not smart enough to know.

...

Yep.

Oops.... Fixed by moving the uwaitq_add above the again: label.

Yep.

Yes. My prior implementation actually deleted the sleeper from the queue on wakeup, making it easy to detect and also saving a syscall. I'm leaning towards the "flag" idea now though.

Yes. The problem is: how many? Each one takes memory and (as you point out) pinned pages (although this could be changed with some loss of simplicity). An arbitrary limit smacks of SysV IPC: a sure sign of bad taste. So for the moment, the limit is 1.

Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

Rusty, you lost me in all these discussions now.
Is the current position to export wait queues and drop the futex interface ? I would recommend against that. If we need 2 syscalls to implement the futex behavior that certainly will create quite some overhead.

add/wait sequence. This as you know is/was due to the fact that I used semaphores in the kernel. While that created some allocation problems and won't allow for usage of the wait queues, it seems more compact. Any chance to move the semaphore behavior into the futexes.

-- Hubertus Franke  ([email protected])

In message <[email protected]> you write:

I know the feeling 8)

I'm still playing with the options. Two system calls in the slow path is definitely slower, but it's not insanely slow, and it's becoming fairly clear that the wider range of primitives is worthwhile.

Both approaches can coexist, but I would consider the sys_futex call a premature optimization if uwaitqs go in: this comes down to the numbers. I can supply a uwaitq implementation for benchmarking if you want?

The allocation element is the one I don't like: there's no really good way of limiting it.

Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.