sys/kern/bufq_readprio.c

   1 /*      $NetBSD: bufq_readprio.c,v 1.12 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_readprio.c,v 1.12 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 two queues.  The first queue holds read requests; the second
  84  * holds write requests.  The read queue is first-come first-served; the
  85  * write queue is sorted in ascendening block order.
  86  * The read queue is processed first.  After PRIO_READ_BURST consecutive
  87  * read requests with non-empty write queue PRIO_WRITE_REQ requests from
  88  * the write queue will be processed.
  89  */
  90
  91 #define PRIO_READ_BURST         48
  92 #define PRIO_WRITE_REQ          16
  93
  94 struct bufq_prio {
  95         TAILQ_HEAD(, buf) bq_read, bq_write; /* actual list of buffers */
  96         struct buf *bq_write_next;      /* next request in bq_write */
  97         struct buf *bq_next;            /* current request */
  98         int bq_read_burst;              /* # of consecutive reads */
  99 };
 100
 101 static void bufq_readprio_init(struct bufq_state *);
 102 static void bufq_prio_put(struct bufq_state *, struct buf *);
 103 static struct buf *bufq_prio_get(struct bufq_state *, int);
 104
 105 BUFQ_DEFINE(readprio, 30, bufq_readprio_init);
 106
 107 static void
 108 bufq_prio_put(struct bufq_state *bufq, struct buf *bp)
 109 {
 110         struct bufq_prio *prio = bufq->bq_private;
 111         struct buf *bq;
 112         int sortby;
 113
 114         sortby = bufq->bq_flags & BUFQ_SORT_MASK;
 115
 116         /*
 117          * If it's a read request append it to the list.
 118          */
 119         if ((bp->b_flags & B_READ) == B_READ) {
 120                 TAILQ_INSERT_TAIL(&prio->bq_read, bp, b_actq);
 121                 return;
 122         }
 123
 124         bq = TAILQ_FIRST(&prio->bq_write);
 125
 126         /*
 127          * If the write list is empty, simply append it to the list.
 128          */
 129         if (bq == NULL) {
 130                 TAILQ_INSERT_TAIL(&prio->bq_write, bp, b_actq);
 131                 prio->bq_write_next = bp;
 132                 return;
 133         }
 134
 135         /*
 136          * If we lie after the next request, insert after this request.
 137          */
 138         if (buf_inorder(prio->bq_write_next, bp, sortby))
 139                 bq = prio->bq_write_next;
 140
 141         /*
 142          * Search for the first request at a larger block number.
 143          * We go before this request if it exists.
 144          */
 145         while (bq != NULL && buf_inorder(bq, bp, sortby))
 146                 bq = TAILQ_NEXT(bq, b_actq);
 147
 148         if (bq != NULL)
 149                 TAILQ_INSERT_BEFORE(bq, bp, b_actq);
 150         else
 151                 TAILQ_INSERT_TAIL(&prio->bq_write, bp, b_actq);
 152 }
 153
 154 static struct buf *
 155 bufq_prio_get(struct bufq_state *bufq, int remove)
 156 {
 157         struct bufq_prio *prio = bufq->bq_private;
 158         struct buf *bp;
 159
 160         /*
 161          * If no current request, get next from the lists.
 162          */
 163         if (prio->bq_next == NULL) {
 164                 /*
 165                  * If at least one list is empty, select the other.
 166                  */
 167                 if (TAILQ_FIRST(&prio->bq_read) == NULL) {
 168                         prio->bq_next = prio->bq_write_next;
 169                         prio->bq_read_burst = 0;
 170                 } else if (prio->bq_write_next == NULL) {
 171                         bp = prio->bq_next = TAILQ_FIRST(&prio->bq_read);
 172                         prio->bq_read_burst = 0;
 173                         KASSERT((bp == NULL) ||
 174                             ((bp->b_flags & B_READ) == B_READ));
 175                 } else {
 176                         /*
 177                          * Both list have requests.  Select the read list up
 178                          * to PRIO_READ_BURST times, then select the write
 179                          * list PRIO_WRITE_REQ times.
 180                          */
 181                         if (prio->bq_read_burst++ < PRIO_READ_BURST)
 182                                 prio->bq_next = TAILQ_FIRST(&prio->bq_read);
 183                         else if (prio->bq_read_burst <
 184                             PRIO_READ_BURST + PRIO_WRITE_REQ)
 185                                 prio->bq_next = prio->bq_write_next;
 186                         else {
 187                                 prio->bq_next = TAILQ_FIRST(&prio->bq_read);
 188                                 prio->bq_read_burst = 0;
 189                         }
 190                 }
 191         }
 192
 193         bp = prio->bq_next;
 194
 195         if (bp != NULL && remove) {
 196                 if ((bp->b_flags & B_READ) == B_READ)
 197                         TAILQ_REMOVE(&prio->bq_read, bp, b_actq);
 198                 else {
 199                         /*
 200                          * Advance the write pointer before removing
 201                          * bp since it is actually prio->bq_write_next.
 202                          */
 203                         prio->bq_write_next =
 204                             TAILQ_NEXT(prio->bq_write_next, b_actq);
 205                         TAILQ_REMOVE(&prio->bq_write, bp, b_actq);
 206                         if (prio->bq_write_next == NULL)
 207                                 prio->bq_write_next =
 208                                     TAILQ_FIRST(&prio->bq_write);
 209                 }
 210
 211                 prio->bq_next = NULL;
 212         }
 213
 214         return (bp);
 215 }
 216
 217 static struct buf *
 218 bufq_prio_cancel(struct bufq_state *bufq, struct buf *buf)
 219 {
 220         struct bufq_prio *prio = bufq->bq_private;
 221         struct buf *bq;
 222
 223         /* search read queue */
 224         TAILQ_FOREACH(bq, &prio->bq_read, b_actq) {
 225                 if (bq == buf) {
 226                         TAILQ_REMOVE(&prio->bq_read, bq, b_actq);
 227                         /* force new section */
 228                         prio->bq_next = NULL;
 229                         return buf;
 230                 }
 231         }
 232
 233         /* not found in read queue, search write queue */
 234         TAILQ_FOREACH(bq, &prio->bq_write, b_actq) {
 235                 if (bq == buf) {
 236                         if (bq == prio->bq_write_next) {
 237                                 /*
 238                                  * Advance the write pointer before removing
 239                                  * bp since it is actually prio->bq_write_next.
 240                                  */
 241                                 prio->bq_write_next =
 242                                     TAILQ_NEXT(prio->bq_write_next, b_actq);
 243                                 TAILQ_REMOVE(&prio->bq_write, bq, b_actq);
 244                                 if (prio->bq_write_next == NULL)
 245                                         prio->bq_write_next =
 246                                             TAILQ_FIRST(&prio->bq_write);
 247                         } else {
 248                                 TAILQ_REMOVE(&prio->bq_write, bq, b_actq);
 249                         }
 250                         /* force new section */
 251                         prio->bq_next = NULL;
 252                         return buf;
 253                 }
 254         }
 255
 256         /* still not found */
 257         return NULL;
 258 }
 259
 260 static void
 261 bufq_prio_fini(struct bufq_state *bufq)
 262 {
 263
 264         KASSERT(bufq->bq_private != NULL);
 265         kmem_free(bufq->bq_private, sizeof(struct bufq_prio));
 266 }
 267
 268 static void
 269 bufq_readprio_init(struct bufq_state *bufq)
 270 {
 271         struct bufq_prio *prio;
 272
 273         bufq->bq_get = bufq_prio_get;
 274         bufq->bq_put = bufq_prio_put;
 275         bufq->bq_cancel = bufq_prio_cancel;
 276         bufq->bq_fini = bufq_prio_fini;
 277         bufq->bq_private = kmem_zalloc(sizeof(struct bufq_prio), KM_SLEEP);
 278         prio = (struct bufq_prio *)bufq->bq_private;
 279         TAILQ_INIT(&prio->bq_read);
 280         TAILQ_INIT(&prio->bq_write);
 281 }
 282