Date: Mon, 13 Jun 2005 15:36:45 -0400 (EDT) From: Jeff Roberson <jroberson@chesapeake.net> To: Antoine Brodin <antoine.brodin@laposte.net> Cc: arch@freebsd.org Subject: Re: simplify disksort, please review. Message-ID: <20050613153625.N16943@mail.chesapeake.net> In-Reply-To: <20050613132621.310a3deb.antoine.brodin@laposte.net> References: <20050608162637.U16943@mail.chesapeake.net> <20050613132621.310a3deb.antoine.brodin@laposte.net>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, 13 Jun 2005, Antoine Brodin wrote: > Jeff Roberson <jroberson@chesapeake.net> 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 >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050613153625.N16943>