simplify disksort, please review.

[Jeff Roberson]

On Mon, 13 Jun 2005, Antoine Brodin wrote:

> Jeff Roberson <jroberson at 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
>