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

[John Baldwin]

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.

Like TAILQ_CONCAT? :)

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.
 */
void
turnstile_broadcast(struct turnstile *ts)
{

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

	...
}

/*
 * 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.
 */
void
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_INIT(&pending_threads);
	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;
			TD_CLR_LOCK(td);
			MPASS(TD_CAN_RUN(td));
			setrunqueue(td, SRQ_BORING);
		} else {
			td->td_flags |= TDF_TSNOBLOCK;
			MPASS(TD_IS_RUNNING(td) || TD_ON_RUNQ(td));
		}
	}
	...
}

-- 
John Baldwin <jhb at FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve"  =  http://www.FreeBSD.org