cvs commit: src/sys/dev/random randomdev_soft.c

John Baldwin jhb at
Mon Oct 11 11:39:23 PDT 2004

On Saturday 09 October 2004 06:07 pm, Robert Watson wrote:
> On Sat, 9 Oct 2004, Robert Watson wrote:
> >   - When reaping harvested entries from the queue, move all entries from
> >     the queue at once, and when done with them, insert them all into a
> >     thread-local queue for processing; then insert them all into the
> >     empty fifo at once.  This reduces O(4n) mutex operations to O(2)
> >     mutex operations per wakeup.
> Right now we do a slightly harmful O(2N) walk of the records to move them
> to a thread-local queue.  It would be very nice to have an O(1) tailq (and
> other list) "move them all" operation to move all entries to a local head.
> This would also be useful when dealing with other work queues in worker
> threads, such as bio queues, etc.


I use that in the turnstile code to do such an O(1) move:

 * Put all blocked threads on the pending list.  This must be called with
 * the turnstile chain locked.
turnstile_broadcast(struct turnstile *ts)

	 * Transfer the blocked list to the pending list.
	TAILQ_CONCAT(&ts->ts_pending, &ts->ts_blocked, td_lockq);


 * Wakeup all threads on the pending list and adjust the priority of the
 * current thread appropriately.  This must be called with the turnstile
 * chain locked.
turnstile_unpend(struct turnstile *ts)
	TAILQ_HEAD( ,thread) pending_threads;

	 * Move the list of pending threads out of the turnstile and
	 * into a local variable.
	TAILQ_CONCAT(&pending_threads, &ts->ts_pending, td_lockq);

	 * Wake up all the pending threads.  If a thread is not blocked
	 * on a lock, then it is currently executing on another CPU in
	 * turnstile_wait() or sitting on a run queue waiting to resume
	 * in turnstile_wait().  Set a flag to force it to try to acquire
	 * the lock again instead of blocking.
	while (!TAILQ_EMPTY(&pending_threads)) {
		td = TAILQ_FIRST(&pending_threads);
		TAILQ_REMOVE(&pending_threads, td, td_lockq);
		MPASS(td->td_proc->p_magic == P_MAGIC);
		if (TD_ON_LOCK(td)) {
			td->td_blocked = NULL;
			td->td_lockname = NULL;
			setrunqueue(td, SRQ_BORING);
		} else {
			td->td_flags |= TDF_TSNOBLOCK;

John Baldwin <jhb at>  <><
"Power Users Use the Power to Serve"  =

More information about the cvs-src mailing list