simplify disksort, please review.

[Antoine Brodin]

Jeff Roberson <jroberson at chesapeake.net> wrote:
> 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;

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