Semaphores used for daemon wakeup

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

@@ -708,7 +708,8 @@
 static void refill_freelist(int size)
 {
 	if (!grow_buffers(size)) {
-		wakeup_bdflush(1);  /* Sets task->state to TASK_RUNNING */
+		wakeup_bdflush(1);
+		__set_current_state(TASK_RUNNING); /* needed?? */
 		current->policy |= SCHED_YIELD;
 		schedule();
 	}

@@ -2469,33 +2470,28 @@
  * response to dirty buffers.  Once this process is activated, we write back
  * a limited number of buffers to the disks and then go back to sleep again.
  */
-static DECLARE_WAIT_QUEUE_HEAD(bdflush_done);
+
+/* Semaphore wakeups, Daniel Phillips, [email protected], 2000/12 */
+
 struct task_struct *bdflush_tsk = 0;
+DECLARE_MUTEX_LOCKED(bdflush_request);
+DECLARE_MUTEX_LOCKED(bdflush_waiter);
+atomic_t bdflush_waiters /*= 0*/;
 
 void wakeup_bdflush(int block)
 {
-	DECLARE_WAITQUEUE(wait, current);
-
 	if (current == bdflush_tsk)
 		return;
 
-	if (!block) {
-		wake_up_process(bdflush_tsk);
+	if (!block)
+	{
+		up(&bdflush_request);
 		return;
 	}
 
-	/* kflushd can wakeup us before we have a chance to
-	   go to sleep so we must be smart in handling
-	   this wakeup event from kflushd to avoid deadlocking in SMP
-	   (we are not holding any lock anymore in these two paths). */
-	__set_current_state(TASK_UNINTERRUPTIBLE);
-	add_wait_queue(&bdflush_done, &wait);
-
-	wake_up_process(bdflush_tsk);
-	schedule();
-
-	remove_wait_queue(&bdflush_done, &wait);
-	__set_current_state(TASK_RUNNING);
+	atomic_inc(&bdflush_waiters);
+	up(&bdflush_request);
+	down(&bdflush_waiter);
 }
 
 /* This is the _only_ function that deals with flushing async writes

@@ -2640,7 +2636,7 @@
 int bdflush(void *sem)
 {
 	struct task_struct *tsk = current;
-	int flushed;
+	int flushed, waiters;
 	/*
 	 *	We have a bare-bones task_struct, and really should fill
 	 *	in a few more things so "top" and /proc/2/{exe,root,cwd}

@@ -2660,6 +2656,7 @@
 	spin_unlock_irq(&tsk->sigmask_lock);
 
 	up((struct semaphore *)sem);
+	printk("Testing semwake bdflush synchronization.\n");
 
 	for (;;) {
 		CHECK_EMERGENCY_SYNC

@@ -2668,28 +2665,16 @@
 		if (free_shortage())
 			flushed += page_launder(GFP_BUFFER, 0);
 
-		/* If wakeup_bdflush will wakeup us
-		   after our bdflush_done wakeup, then
-		   we must make sure to not sleep
-		   in schedule_timeout otherwise
-		   wakeup_bdflush may wait for our
-		   bdflush_done wakeup that would never arrive
-		   (as we would be sleeping) and so it would
-		   deadlock in SMP. */
-		__set_current_state(TASK_INTERRUPTIBLE);
-		wake_up_all(&bdflush_done);
-		/*
-		 * If there are still a lot of dirty buffers around,
-		 * skip the sleep and flush some more. Otherwise, we
-		 * go to sleep waiting a wakeup.
-		 */
-		if (!flushed || balance_dirty_state(NODEV) < 0) {
+		waiters = atomic_read(&bdflush_waiters);
+		atomic_sub(waiters, &bdflush_waiters);
+		while (waiters--)
+			up(&bdflush_waiter);
+
+		if (!flushed || balance_dirty_state(NODEV) < 0) 
+		{
 			run_task_queue(&tq_disk);
-			schedule();
+			down(&bdflush_request);
 		}
-		/* Remember to mark us as running otherwise
-		   the next schedule will block. */
-		__set_current_state(TASK_RUNNING);
 	}
 }
 

@@ -309,7 +309,8 @@
 repeat_bh:
 	bh = kmem_cache_alloc(bh_cachep, SLAB_BUFFER);
 	if (!bh) {
-		wakeup_bdflush(1);  /* Sets task->state to TASK_RUNNING */
+		wakeup_bdflush(1);
+		__set_current_state(TASK_RUNNING); /* needed?? */
 		current->policy |= SCHED_YIELD;
 		schedule();
 		goto repeat_bh;

@@ -323,7 +324,8 @@
 repeat_page:
 	page = alloc_page(GFP_BUFFER);
 	if (!page) {
-		wakeup_bdflush(1);  /* Sets task->state to TASK_RUNNING */
+		wakeup_bdflush(1);
+		__set_current_state(TASK_RUNNING); /* needed?? */
 		current->policy |= SCHED_YIELD;
 		schedule();
 		goto repeat_page;

This is much better, especially from a maintainability point of view. It is also the method that a lot of operating systems already use.

Nigel Gamble [email protected]
Mountain View, CA, USA. http://www.nrg.org/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

[...]

Well, I have to confess I'm rather fond of this method, but that could have something to do with it being how we did it in DYNIX/ptx (Sequent). It certainly works, and I find it very clear, but of course I'm biased :-)

Tim

--
Tim Wright - [email protected] or [email protected] or [email protected] "Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI -
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

Actually, his name is Arjan van de Ven - sorry Arjan :-o

Thanks also to Phillip Rumpf for auditing this patch for cross-platform correctness.

--
Daniel
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

I'm curious, is my method of avoiding the deadlock race the same as yours? My solution is to keep a count of tasks that 'intend' to take the down():

        atomic_inc(&bdflush_waiters);
        up(&bdflush_request);
        down(&bdflush_waiter);

so that bdflush will issue the correct number of up's even if the waiter has not yet gone to sleep. IOW, is your approach in DYNIX the same only in spirit, or in detail?

--
Daniel
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

Hi Daniel,
On Tue, Dec 19, 2000 at 02:11:16PM +0100, Daniel Phillips wrote:
[...]

OK,
this is not how we generally would achieve the goal, although the approach looks valid. We have a number of primitives available that are not currently used in Linux (unless I'm losing my eyesight :-)
We use p_sema, and v_sema for down and up respectively (this was done many years ago, and the names are in deference to Edsger Dijkstra. For normal semaphores (as opposed to read/writer or other variants), we have sema_t sema;
init_sema(&sema, 1); /* initialize semaphore & set initial count */
p_sema(&sema, PZERO); /* "grab" semaphore and set process priority */

			/* priority < PZERO == sleep uninterruptibly */

v_sema(&sema); /* release semaphore (i.e. increment count) */
cp_sema(&sema); /* Attempt to grab semaphore iff free else EBUSY */
vall_sema(&sema); /* Wake up all sleepers on this semaphore */
blocked_sema(&sema); /* boolean: any sleepers ? */
p_sema_v_lock(&sema, priority, &lock); /* atomically release the lock AND */

			/* go to sleep on the semaphore */

Simple spinlock primitives are similar (e.g. p_lock ...), but the last primitive above is the key to avoiding many races. The classic coding style in DYNIX/ptx (this for buffer allocation) is then:

dmabuf_init(...);

{
	...
	init_sema(&dmabuf_wait, 0);
	init_lock(&dmabuf_mutex);
	...
}

dmabuf_alloc(...)

{
	spl_t saved_spl;
	...
	while (1) {
		saved_spl = p_lock(&dmabuf_mutex, SPLSWP);
		attempt to grab a free buffer;
		if (success){
			v_lock(&dmabuf_mutex, saved_spl);
			return;
		} else {
			p_sema_v_lock(&dmabuf_wait, PSWP+1, &dmabuf_mutex);
		}
	}
}

dmabuf_free(...)

{
	spl_t saved_spl;
	...
	saved_spl = p_lock(&dmabuf_mutex, SPLHI);
	free up buffer;
        if (blocked_sema(&dmabuf_wait)) {
                vall_sema(&dmabuf_wait);
        }
        v_lock(&dmabuf_mutex, s);                                               
}

As you can see, the spinlocks ensure no races, and the key is the atomicity of p_sema_v_lock(). No-one can race in and sleep on dmabuf_wait, because they have to hold dmabuf_mutex to do so. Exactly the same mechanism would work for the bdflush problem.

One can argue the relative merits of the different approaches. I suspect that the above code is less bus-intensive relative to the atomic inc/dec/count ops, but I may be wrong.

Regards,

Tim

Tim Wright - [email protected] or [email protected] or [email protected]
"Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/

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

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

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.

The above hopefully elaborates a little. I'm more than happy to give further details etc. assuming it's not boring everybody to tears :-)
I agree with you that your changes improve the readability significantly.

Regards,
Tim

Tim Wright - [email protected] or [email protected] or [email protected]
IBM Linux Technology Center, Beaverton, Oregon
"Nobody ever said I was charming, they said "Rimmer, you're a git!"" RD VI
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/