Re: simplify disksort, please review.

From: Antoine Brodin (antoine.brodin_at_laposte.net)
Date: 06/13/05

  • Next message: Poul-Henning Kamp: "Re: simplify disksort, please review." 
    Date: Mon, 13 Jun 2005 22:07:57 +0200
To: Jeff Roberson <jroberson@chesapeake.net>

    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
    _______________________________________________
    freebsd-arch@freebsd.org mailing list
    http://lists.freebsd.org/mailman/listinfo/freebsd-arch
    To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"

  • Next message: Poul-Henning Kamp: "Re: simplify disksort, please review."

    Relevant Pages