From owner-freebsd-arch@FreeBSD.ORG Mon Jun 13 20:08:04 2005 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 033BC16A439 for ; Mon, 13 Jun 2005 20:08:04 +0000 (GMT) (envelope-from antoine@madhouse.dreadbsd.org) Received: from barton.dreadbsd.org (madhouse.dreadbsd.org [82.67.196.50]) by mx1.FreeBSD.org (Postfix) with ESMTP id 588FC43D4C for ; Mon, 13 Jun 2005 20:08:03 +0000 (GMT) (envelope-from antoine@madhouse.dreadbsd.org) Received: from barton.dreadbsd.org (localhost [127.0.0.1]) by barton.dreadbsd.org (8.13.4/8.13.1) with ESMTP id j5DK7w0B051733; Mon, 13 Jun 2005 22:07:58 +0200 (CEST) (envelope-from antoine@madhouse.dreadbsd.org) Received: (from antoine@localhost) by barton.dreadbsd.org (8.13.4/8.13.1/Submit) id j5DK7vcD051732; Mon, 13 Jun 2005 22:07:57 +0200 (CEST) (envelope-from antoine) Date: Mon, 13 Jun 2005 22:07:57 +0200 From: Antoine Brodin To: Jeff Roberson Message-Id: <20050613220757.1063996b.antoine.brodin@laposte.net> In-Reply-To: <20050613153625.N16943@mail.chesapeake.net> References: <20050608162637.U16943@mail.chesapeake.net> <20050613132621.310a3deb.antoine.brodin@laposte.net> <20050613153625.N16943@mail.chesapeake.net> X-Mailer: Sylpheed version 1.9.12 (GTK+ 2.6.7; i386-portbld-freebsd6.0) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Cc: arch@freebsd.org Subject: Re: simplify disksort, please review. X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 13 Jun 2005 20:08:04 -0000 Jeff Roberson wrote: > On Mon, 13 Jun 2005, Antoine Brodin wrote: > > > Jeff Roberson wrote: > > > http://www.chesapeake.net/~jroberson/disksort.diff > > > > > > Our disksort algorithm used to be complicated by the BIO_ORDERED flag, > > > which could cause us to make some exceptions in the sorting. When the > > > ordered support was removed we never simplified the algorithm. The patch > > > above gets rid of the switch point and associated logic. It's now a > > > simple hinted insertion sort with a one way scan. Since it's a fairly > > > central algorithm, I'd appreciate a review. > > > > Sorry for the late review, but there's perhaps a problem: > > You are correct. What do you think of this: > > 10# cvs diff -u subr_disk.c > Index: subr_disk.c > =================================================================== > RCS file: /home/ncvs/src/sys/kern/subr_disk.c,v > retrieving revision 1.84 > diff -u -r1.84 subr_disk.c > --- subr_disk.c 12 Jun 2005 22:32:29 -0000 1.84 > +++ subr_disk.c 13 Jun 2005 19:35:35 -0000 > @@ -182,15 +182,12 @@ > } > } else > bq = TAILQ_FIRST(&bioq->queue); > - > + if (bp->bio_offset < bq->bio_offset) { > + TAILQ_INSERT_BEFORE(bq, bp, bio_queue); > + return; > + } > /* Insertion sort */ > while ((bn = TAILQ_NEXT(bq, bio_queue)) != NULL) { > - > - /* > - * We want to go after the current request if it is the > end > - * of the first request list, or if the next request is a > - * larger cylinder than our request. > - */ > if (bp->bio_offset < bn->bio_offset) > break; > bq = bn; This looks good. I think bioq_first and bioq_takefirst should be modified to take head->insert_point instead of TAILQ_FIRST(&head->queue). bioq_insert_head and bioq_insert_tail should perhaps be modified when they're called from outside of subr_disk.c too, to insert just before insert_point and replace it in the head case... but this probably affects sorting of later bios... Cheers, Antoine