sys/kern/bufq_disksort.c

   1 /*      $NetBSD: bufq_disksort.c,v 1.10 2009/01/16 01:48:09 yamt Exp $  */
   2 /*      NetBSD: subr_disk.c,v 1.61 2004/09/25 03:30:44 thorpej Exp      */
   3
   4 /*-
   5  * Copyright (c) 1996, 1997, 1999, 2000 The NetBSD Foundation, Inc.
   6  * All rights reserved.
   7  *
   8  * This code is derived from software contributed to The NetBSD Foundation
   9  * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
  10  * NASA Ames Research Center.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  23  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  24  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  25  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * Copyright (c) 1982, 1986, 1988, 1993
  36  *      The Regents of the University of California.  All rights reserved.
  37  * (c) UNIX System Laboratories, Inc.
  38  * All or some portions of this file are derived from material licensed
  39  * to the University of California by American Telephone and Telegraph
  40  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
  41  * the permission of UNIX System Laboratories, Inc.
  42  *
  43  * Redistribution and use in source and binary forms, with or without
  44  * modification, are permitted provided that the following conditions
  45  * are met:
  46  * 1. Redistributions of source code must retain the above copyright
  47  *    notice, this list of conditions and the following disclaimer.
  48  * 2. Redistributions in binary form must reproduce the above copyright
  49  *    notice, this list of conditions and the following disclaimer in the
  50  *    documentation and/or other materials provided with the distribution.
  51  * 3. Neither the name of the University nor the names of its contributors
  52  *    may be used to endorse or promote products derived from this software
  53  *    without specific prior written permission.
  54  *
  55  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  56  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  57  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  58  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  59  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  60  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  61  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  62  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  63  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  64  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  65  * SUCH DAMAGE.
  66  *
  67  *      @(#)ufs_disksubr.c      8.5 (Berkeley) 1/21/94
  68  */
  69
  70 #include <sys/cdefs.h>
  71 __KERNEL_RCSID(0, "$NetBSD: bufq_disksort.c,v 1.10 2009/01/16 01:48:09 yamt Exp $");
  72
  73 #include <sys/param.h>
  74 #include <sys/systm.h>
  75 #include <sys/buf.h>
  76 #include <sys/bufq.h>
  77 #include <sys/bufq_impl.h>
  78 #include <sys/kmem.h>
  79
  80 /*
  81  * Seek sort for disks.
  82  *
  83  * There are actually two queues, sorted in ascendening order.  The first
  84  * queue holds those requests which are positioned after the current block;
  85  * the second holds requests which came in after their position was passed.
  86  * Thus we implement a one-way scan, retracting after reaching the end of
  87  * the drive to the first request on the second queue, at which time it
  88  * becomes the first queue.
  89  *
  90  * A one-way scan is natural because of the way UNIX read-ahead blocks are
  91  * allocated.
  92  */
  93
  94 struct bufq_disksort {
  95         TAILQ_HEAD(, buf) bq_head;      /* actual list of buffers */
  96 };
  97
  98 static void bufq_disksort_init(struct bufq_state *);
  99 static void bufq_disksort_put(struct bufq_state *, struct buf *);
 100 static struct buf *bufq_disksort_get(struct bufq_state *, int);
 101
 102 BUFQ_DEFINE(disksort, 20, bufq_disksort_init);
 103
 104 static void
 105 bufq_disksort_put(struct bufq_state *bufq, struct buf *bp)
 106 {
 107         struct bufq_disksort *disksort = bufq_private(bufq);
 108         struct buf *bq, *nbq;
 109         int sortby;
 110
 111         sortby = bufq->bq_flags & BUFQ_SORT_MASK;
 112
 113         bq = TAILQ_FIRST(&disksort->bq_head);
 114
 115         /*
 116          * If the queue is empty it's easy; we just go on the end.
 117          */
 118         if (bq == NULL) {
 119                 TAILQ_INSERT_TAIL(&disksort->bq_head, bp, b_actq);
 120                 return;
 121         }
 122
 123         /*
 124          * If we lie before the currently active request, then we
 125          * must locate the second request list and add ourselves to it.
 126          */
 127         if (buf_inorder(bp, bq, sortby)) {
 128                 while ((nbq = TAILQ_NEXT(bq, b_actq)) != NULL) {
 129                         /*
 130                          * Check for an ``inversion'' in the normally ascending
 131                          * block numbers, indicating the start of the second
 132                          * request list.
 133                          */
 134                         if (buf_inorder(nbq, bq, sortby)) {
 135                                 /*
 136                                  * Search the second request list for the first
 137                                  * request at a larger block number.  We go
 138                                  * after that; if there is no such request, we
 139                                  * go at the end.
 140                                  */
 141                                 do {
 142                                         if (buf_inorder(bp, nbq, sortby))
 143                                                 goto insert;
 144                                         bq = nbq;
 145                                 } while ((nbq =
 146                                     TAILQ_NEXT(bq, b_actq)) != NULL);
 147                                 goto insert;            /* after last */
 148                         }
 149                         bq = nbq;
 150                 }
 151                 /*
 152                  * No inversions... we will go after the last, and
 153                  * be the first request in the second request list.
 154                  */
 155                 goto insert;
 156         }
 157         /*
 158          * Request is at/after the current request...
 159          * sort in the first request list.
 160          */
 161         while ((nbq = TAILQ_NEXT(bq, b_actq)) != NULL) {
 162                 /*
 163                  * We want to go after the current request if there is an
 164                  * inversion after it (i.e. it is the end of the first
 165                  * request list), or if the next request is a larger cylinder
 166                  * than our request.
 167                  */
 168                 if (buf_inorder(nbq, bq, sortby) ||
 169                     buf_inorder(bp, nbq, sortby))
 170                         goto insert;
 171                 bq = nbq;
 172         }
 173         /*
 174          * Neither a second list nor a larger request... we go at the end of
 175          * the first list, which is the same as the end of the whole schebang.
 176          */
 177 insert: TAILQ_INSERT_AFTER(&disksort->bq_head, bq, bp, b_actq);
 178 }
 179
 180 static struct buf *
 181 bufq_disksort_get(struct bufq_state *bufq, int remove)
 182 {
 183         struct bufq_disksort *disksort = bufq->bq_private;
 184         struct buf *bp;
 185
 186         bp = TAILQ_FIRST(&disksort->bq_head);
 187
 188         if (bp != NULL && remove)
 189                 TAILQ_REMOVE(&disksort->bq_head, bp, b_actq);
 190
 191         return (bp);
 192 }
 193
 194 static struct buf *
 195 bufq_disksort_cancel(struct bufq_state *bufq, struct buf *buf)
 196 {
 197         struct bufq_disksort *disksort = bufq->bq_private;
 198         struct buf *bq;
 199
 200         TAILQ_FOREACH(bq, &disksort->bq_head, b_actq) {
 201                 if (bq == buf) {
 202                         TAILQ_REMOVE(&disksort->bq_head, bq, b_actq);
 203                         return buf;
 204                 }
 205         }
 206         return NULL;
 207 }
 208
 209 static void
 210 bufq_disksort_fini(struct bufq_state *bufq)
 211 {
 212
 213         KASSERT(bufq->bq_private != NULL);
 214         kmem_free(bufq->bq_private, sizeof(struct bufq_disksort));
 215 }
 216
 217 static void
 218 bufq_disksort_init(struct bufq_state *bufq)
 219 {
 220         struct bufq_disksort *disksort;
 221
 222         disksort = kmem_zalloc(sizeof(*disksort), KM_SLEEP);
 223         bufq->bq_private = disksort;
 224         bufq->bq_get = bufq_disksort_get;
 225         bufq->bq_put = bufq_disksort_put;
 226         bufq->bq_cancel = bufq_disksort_cancel;
 227         bufq->bq_fini = bufq_disksort_fini;
 228         TAILQ_INIT(&disksort->bq_head);
 229 }