bufq_disksort.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_disksort.c,v 1.14 2017/05/04 11:03:27 kamil 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.14 2017/05/04 11:03:27 kamil 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 #include <sys/module.h>
   80 
   81 /*
   82  * Seek sort for disks.
   83  *
   84  * There are actually two queues, sorted in ascendening order.  The first
   85  * queue holds those requests which are positioned after the current block;
   86  * the second holds requests which came in after their position was passed.
   87  * Thus we implement a one-way scan, retracting after reaching the end of
   88  * the drive to the first request on the second queue, at which time it
   89  * becomes the first queue.
   90  *
   91  * A one-way scan is natural because of the way UNIX read-ahead blocks are
   92  * allocated.
   93  */
   94 
   95 struct bufq_disksort {
   96         TAILQ_HEAD(, buf) bq_head;      /* actual list of buffers */
   97 };
   98 
   99 static void bufq_disksort_init(struct bufq_state *);
  100 static void bufq_disksort_put(struct bufq_state *, struct buf *);
  101 static struct buf *bufq_disksort_get(struct bufq_state *, int);
  102 
  103 BUFQ_DEFINE(disksort, 20, bufq_disksort_init);
  104 
  105 static void
  106 bufq_disksort_put(struct bufq_state *bufq, struct buf *bp)
  107 {
  108         struct bufq_disksort *disksort = bufq_private(bufq);
  109         struct buf *bq, *nbq;
  110         int sortby;
  111 
  112         sortby = bufq->bq_flags & BUFQ_SORT_MASK;
  113 
  114         bq = TAILQ_FIRST(&disksort->bq_head);
  115 
  116         /*
  117          * If the queue is empty it's easy; we just go on the end.
  118          */
  119         if (bq == NULL) {
  120                 TAILQ_INSERT_TAIL(&disksort->bq_head, bp, b_actq);
  121                 return;
  122         }
  123 
  124         /*
  125          * If we lie before the currently active request, then we
  126          * must locate the second request list and add ourselves to it.
  127          */
  128         if (buf_inorder(bp, bq, sortby)) {
  129                 while ((nbq = TAILQ_NEXT(bq, b_actq)) != NULL) {
  130                         /*
  131                          * Check for an ``inversion'' in the normally ascending
  132                          * block numbers, indicating the start of the second
  133                          * request list.
  134                          */
  135                         if (buf_inorder(nbq, bq, sortby)) {
  136                                 /*
  137                                  * Search the second request list for the first
  138                                  * request at a larger block number.  We go
  139                                  * after that; if there is no such request, we
  140                                  * go at the end.
  141                                  */
  142                                 do {
  143                                         if (buf_inorder(bp, nbq, sortby))
  144                                                 goto insert;
  145                                         bq = nbq;
  146                                 } while ((nbq =
  147                                     TAILQ_NEXT(bq, b_actq)) != NULL);
  148                                 goto insert;            /* after last */
  149                         }
  150                         bq = nbq;
  151                 }
  152                 /*
  153                  * No inversions... we will go after the last, and
  154                  * be the first request in the second request list.
  155                  */
  156                 goto insert;
  157         }
  158         /*
  159          * Request is at/after the current request...
  160          * sort in the first request list.
  161          */
  162         while ((nbq = TAILQ_NEXT(bq, b_actq)) != NULL) {
  163                 /*
  164                  * We want to go after the current request if there is an
  165                  * inversion after it (i.e. it is the end of the first
  166                  * request list), or if the next request is a larger cylinder
  167                  * than our request.
  168                  */
  169                 if (buf_inorder(nbq, bq, sortby) ||
  170                     buf_inorder(bp, nbq, sortby))
  171                         goto insert;
  172                 bq = nbq;
  173         }
  174         /*
  175          * Neither a second list nor a larger request... we go at the end of
  176          * the first list, which is the same as the end of the whole schebang.
  177          */
  178 insert: TAILQ_INSERT_AFTER(&disksort->bq_head, bq, bp, b_actq);
  179 }
  180 
  181 static struct buf *
  182 bufq_disksort_get(struct bufq_state *bufq, int remove)
  183 {
  184         struct bufq_disksort *disksort = bufq_private(bufq);
  185         struct buf *bp;
  186 
  187         bp = TAILQ_FIRST(&disksort->bq_head);
  188 
  189         if (bp != NULL && remove)
  190                 TAILQ_REMOVE(&disksort->bq_head, bp, b_actq);
  191 
  192         return (bp);
  193 }
  194 
  195 static struct buf *
  196 bufq_disksort_cancel(struct bufq_state *bufq, struct buf *buf)
  197 {
  198         struct bufq_disksort *disksort = bufq_private(bufq);
  199         struct buf *bq;
  200 
  201         TAILQ_FOREACH(bq, &disksort->bq_head, b_actq) {
  202                 if (bq == buf) {
  203                         TAILQ_REMOVE(&disksort->bq_head, bq, b_actq);
  204                         return buf;
  205                 }
  206         }
  207         return NULL;
  208 }
  209 
  210 static void
  211 bufq_disksort_fini(struct bufq_state *bufq)
  212 {
  213 
  214         KASSERT(bufq->bq_private != NULL);
  215         kmem_free(bufq->bq_private, sizeof(struct bufq_disksort));
  216 }
  217 
  218 static void
  219 bufq_disksort_init(struct bufq_state *bufq)
  220 {
  221         struct bufq_disksort *disksort;
  222 
  223         disksort = kmem_zalloc(sizeof(*disksort), KM_SLEEP);
  224         bufq->bq_private = disksort;
  225         bufq->bq_get = bufq_disksort_get;
  226         bufq->bq_put = bufq_disksort_put;
  227         bufq->bq_cancel = bufq_disksort_cancel;
  228         bufq->bq_fini = bufq_disksort_fini;
  229         TAILQ_INIT(&disksort->bq_head);
  230 }
  231 
  232 MODULE(MODULE_CLASS_BUFQ, bufq_disksort, NULL);
  233 
  234 static int
  235 bufq_disksort_modcmd(modcmd_t cmd, void *opaque)
  236 {
  237 
  238         switch (cmd) {
  239         case MODULE_CMD_INIT:
  240                 return bufq_register(&bufq_strat_disksort);
  241         case MODULE_CMD_FINI:
  242                 return bufq_unregister(&bufq_strat_disksort);
  243         default:
  244                 return ENOTTY;
  245         }
  246 }
Cache object: 8c3ef2e9984b22059d552bbda7d1448b
[ 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_disksort.c

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