From owner-freebsd-arch@FreeBSD.ORG Mon Jun 13 19:36:47 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 E1E9516A41C for ; Mon, 13 Jun 2005 19:36:47 +0000 (GMT) (envelope-from jroberson@chesapeake.net) Received: from mail.chesapeake.net (chesapeake.net [208.142.252.6]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5CA8E43D49 for ; Mon, 13 Jun 2005 19:36:47 +0000 (GMT) (envelope-from jroberson@chesapeake.net) Received: from mail.chesapeake.net (localhost [127.0.0.1]) by mail.chesapeake.net (8.12.10/8.12.10) with ESMTP id j5DJajk9057541; Mon, 13 Jun 2005 15:36:45 -0400 (EDT) (envelope-from jroberson@chesapeake.net) Received: from localhost (jroberson@localhost) by mail.chesapeake.net (8.12.10/8.12.10/Submit) with ESMTP id j5DJajjX057536; Mon, 13 Jun 2005 15:36:45 -0400 (EDT) (envelope-from jroberson@chesapeake.net) X-Authentication-Warning: mail.chesapeake.net: jroberson owned process doing -bs Date: Mon, 13 Jun 2005 15:36:45 -0400 (EDT) From: Jeff Roberson To: Antoine Brodin In-Reply-To: <20050613132621.310a3deb.antoine.brodin@laposte.net> Message-ID: <20050613153625.N16943@mail.chesapeake.net> References: <20050608162637.U16943@mail.chesapeake.net> <20050613132621.310a3deb.antoine.brodin@laposte.net> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 19:36:48 -0000 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; > > If you have this situation: > > queue:------------ 5 - 6 - 7 > last_offset: 4 | > insert_point:------+ > > And you bioq_disksort a bio with an offset of 1: > > queue:------------ 5 - 1 - 6 - 7 > last_offset: 4 | > insert_point:------+ > > It looks weirdly sorted. > > IIRC, the previous algorithm gave: > > queue:------------ 5 - 6 - 7 - 1 > > Looking at revision 1.83, it looks like insert_point was useless, not > switch_point. > > I can't test this change since disksort doesn't seem to be used by > ata(4) anymore (is there any reason ?). > > Cheers, > > Antoine >