bufq_readprio.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*      $NetBSD: bufq_readprio.c,v 1.11 2008/04/30 12:09:02 reinoud 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.11 2008/04/30 12:09:02 reinoud 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/malloc.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         bq = TAILQ_FIRST(&prio->bq_read);
  225         while (bq) {
  226                 if (bq == buf) {
  227                         TAILQ_REMOVE(&prio->bq_read, bq, b_actq);
  228                         /* force new section */
  229                         prio->bq_next = NULL;
  230                         return buf;
  231                 }
  232                 bq = TAILQ_NEXT(bq, b_actq);
  233         }
  234 
  235         /* not found in read queue, search write queue */
  236         bq = TAILQ_FIRST(&prio->bq_write);
  237         while (bq) {
  238                 if (bq == buf) {
  239                         if (bq == prio->bq_write_next) {
  240                                 /*
  241                                  * Advance the write pointer before removing
  242                                  * bp since it is actually prio->bq_write_next.
  243                                  */
  244                                 prio->bq_write_next =
  245                                     TAILQ_NEXT(prio->bq_write_next, b_actq);
  246                                 TAILQ_REMOVE(&prio->bq_write, bq, b_actq);
  247                                 if (prio->bq_write_next == NULL)
  248                                         prio->bq_write_next =
  249                                             TAILQ_FIRST(&prio->bq_write);
  250                         } else {
  251                                 TAILQ_REMOVE(&prio->bq_write, bq, b_actq);
  252                         }
  253                         /* force new section */
  254                         prio->bq_next = NULL;
  255                         return buf;
  256                 }
  257                 bq = TAILQ_NEXT(bq, b_actq);
  258         }
  259 
  260         /* still not found */
  261         return NULL;
  262 }
  263 
  264 static void
  265 bufq_readprio_init(struct bufq_state *bufq)
  266 {
  267         struct bufq_prio *prio;
  268 
  269         bufq->bq_get = bufq_prio_get;
  270         bufq->bq_put = bufq_prio_put;
  271         bufq->bq_cancel = bufq_prio_cancel;
  272         bufq->bq_private = malloc(sizeof(struct bufq_prio), M_DEVBUF, M_ZERO);
  273         prio = (struct bufq_prio *)bufq->bq_private;
  274         TAILQ_INIT(&prio->bq_read);
  275         TAILQ_INIT(&prio->bq_write);
  276 }
  277
Cache object: 2523b2fa02c1051e35e67f2552e0bd1e
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/kern/bufq_readprio.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/bufq_readprio.c
