From owner-cvs-all@FreeBSD.ORG Mon Oct 11 18:39:23 2004 Return-Path: Delivered-To: cvs-all@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 7FEA216A57A for ; Mon, 11 Oct 2004 18:39:21 +0000 (GMT) Received: from mail6.speakeasy.net (mail6.speakeasy.net [216.254.0.206]) by mx1.FreeBSD.org (Postfix) with ESMTP id D99EE43D4C for ; Mon, 11 Oct 2004 18:39:20 +0000 (GMT) (envelope-from jhb@FreeBSD.org) Received: (qmail 16164 invoked from network); 11 Oct 2004 18:39:20 -0000 Received: from dsl027-160-063.atl1.dsl.speakeasy.net (HELO server.baldwin.cx) ([216.27.160.63]) (envelope-sender ) encrypted SMTP for ; 11 Oct 2004 18:39:19 -0000 Received: from [10.50.40.210] (gw1.twc.weather.com [216.133.140.1]) (authenticated bits=0) by server.baldwin.cx (8.12.11/8.12.11) with ESMTP id i9BIdBmo041427; Mon, 11 Oct 2004 14:39:16 -0400 (EDT) (envelope-from jhb@FreeBSD.org) From: John Baldwin To: Robert Watson Date: Mon, 11 Oct 2004 14:40:08 -0400 User-Agent: KMail/1.6.2 References: In-Reply-To: MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200410111440.08998.jhb@FreeBSD.org> X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on server.baldwin.cx cc: cvs-src@FreeBSD.org cc: src-committers@FreeBSD.org cc: cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/dev/random randomdev_soft.c X-BeenThere: cvs-all@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: CVS commit messages for the entire tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 11 Oct 2004 18:39:23 -0000 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 <>< http://www.FreeBSD.org/~jhb/ "Power Users Use the Power to Serve" = http://www.FreeBSD.org