From owner-freebsd-arch@FreeBSD.ORG Thu Jun 9 19:30:10 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 B7F7D16A41C for ; Thu, 9 Jun 2005 19:30:10 +0000 (GMT) (envelope-from pjd@darkness.comp.waw.pl) Received: from darkness.comp.waw.pl (darkness.comp.waw.pl [195.117.238.136]) by mx1.FreeBSD.org (Postfix) with ESMTP id 53F2C43D48 for ; Thu, 9 Jun 2005 19:30:10 +0000 (GMT) (envelope-from pjd@darkness.comp.waw.pl) Received: by darkness.comp.waw.pl (Postfix, from userid 1009) id 69196ACAF4; Thu, 9 Jun 2005 21:30:08 +0200 (CEST) Date: Thu, 9 Jun 2005 21:30:08 +0200 From: Pawel Jakub Dawidek To: Jeff Roberson Message-ID: <20050609193008.GB837@darkness.comp.waw.pl> References: <20050608162637.U16943@mail.chesapeake.net> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="cNtNYsKpUFVU3qjo" Content-Disposition: inline In-Reply-To: <20050608162637.U16943@mail.chesapeake.net> User-Agent: Mutt/1.4.2i X-PGP-Key-URL: http://people.freebsd.org/~pjd/pjd.asc X-OS: FreeBSD 5.2.1-RC2 i386 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: Thu, 09 Jun 2005 19:30:10 -0000 --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--