Date: Mon, 13 Jun 2005 13:26:21 +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: <20050613132621.310a3deb.antoine.brodin@laposte.net> In-Reply-To: <20050608162637.U16943@mail.chesapeake.net> References: <20050608162637.U16943@mail.chesapeake.net>
next in thread | previous in thread | raw e-mail | index | archive | help
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: 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?20050613132621.310a3deb.antoine.brodin>