Date: Mon, 13 Jun 2005 22:07:57 +0200 From: Antoine Brodin <antoine.brodin@laposte.net> To: Jeff Roberson <jroberson@chesapeake.net> Cc: arch@freebsd.org Subject: Re: simplify disksort, please review. 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>
next in thread | previous in thread | raw e-mail | index | archive | help
Jeff Roberson <jroberson@chesapeake.net> wrote: > 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; 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050613220757.1063996b.antoine.brodin>