Re: simplify disksort, please review.

From: Jeff Roberson (jroberson_at_chesapeake.net)
Date: 06/13/05

  • Next message: Antoine Brodin: "Re: simplify disksort, please review." 
    Date: Mon, 13 Jun 2005 15:36:45 -0400 (EDT)
To: Antoine Brodin <antoine.brodin@laposte.net>

    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;

    >
    > 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
    >
    _______________________________________________
    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: Antoine Brodin: "Re: simplify disksort, please review."