Date: Thu, 9 Jun 2005 21:30:08 +0200 From: Pawel Jakub Dawidek <pjd@FreeBSD.org> To: Jeff Roberson <jroberson@chesapeake.net> Cc: arch@freebsd.org Subject: Re: simplify disksort, please review. Message-ID: <20050609193008.GB837@darkness.comp.waw.pl> 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
--cNtNYsKpUFVU3qjo Content-Type: text/plain; charset=iso-8859-2 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Jun 08, 2005 at 04:43:03PM -0400, Jeff Roberson wrote: +> http://www.chesapeake.net/~jroberson/disksort.diff +>=20 +> 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. It is not related to you patch, but I think our disk sort is just too trivial. The one example of how the order can be broken (write(offset, size)): write(1024, 512) write(0, 2048) It'll be sorted to: write(0, 2048) write(1024, 512) because we're sorting only based on offset. AFAIR we now require from file system not to send next request to the same area until previous request is not finished, so we should be safe (for now). --=20 Pawel Jakub Dawidek http://www.wheel.pl pjd@FreeBSD.org http://www.FreeBSD.org FreeBSD committer Am I Evil? Yes, I Am! --cNtNYsKpUFVU3qjo Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (FreeBSD) iD8DBQFCqJjAForvXbEpPzQRAkXYAJ4q2xqM6jN7fqpy9ZcDVGIbMou9JgCcCAU0 QOCbUw9muIE5CelxY/fDxnc= =PNcu -----END PGP SIGNATURE----- --cNtNYsKpUFVU3qjo--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050609193008.GB837>