kernel/os/bdev_dsort.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 1989 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 /*      Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T     */
  28 /*        All Rights Reserved   */
  29
  30 /*
  31  * Portions of this source code were derived from Berkeley 4.3 BSD
  32  * under license from the Regents of the University of California.
  33  */
  34
  35 #ident  "%Z%%M% %I%     %E% SMI"
  36 /* from ufs_dsort.c     2.12    89/07/24 SMI"   */
  37 /*
  38  * Seek sort for disks.  We depend on the driver
  39  * which calls us using b_resid as the current cylinder number.
  40  *
  41  * The argument dp structure holds a b_actf activity chain pointer
  42  * on which we keep two queues, sorted in ascending cylinder order.
  43  * The first queue holds those requests which are positioned after
  44  * the current cylinder (in the first request); the second holds
  45  * requests which came in after their cylinder number was passed.
  46  * Thus we implement a one way scan, retracting after reaching the
  47  * end of the drive to the first request on the second queue,
  48  * at which time it becomes the first queue.
  49  *
  50  * A one-way scan is natural because of the way UNIX read-ahead
  51  * blocks are allocated.
  52  */
  53
  54 #include <sys/types.h>
  55 #include <sys/param.h>
  56 #include <sys/systm.h>
  57 #include <sys/buf.h>
  58
  59 #define b_cylin b_resid
  60
  61 void
  62 disksort(dp, bp)
  63         register struct diskhd *dp;
  64         register struct buf *bp;
  65 {
  66         register struct buf *ap;
  67
  68         /*
  69          * If nothing on the activity queue, then
  70          * we become the only thing.
  71          */
  72         ap = dp->b_actf;
  73         if (ap == NULL) {
  74                 dp->b_actf = bp;
  75                 dp->b_actl = bp;
  76                 bp->av_forw = NULL;
  77                 return;
  78         }
  79         /*
  80          * If we lie after the first (currently active)
  81          * request, then we must locate the second request list
  82          * and add ourselves to it.
  83          */
  84         if (bp->b_cylin < ap->b_cylin) {
  85                 while (ap->av_forw) {
  86                         /*
  87                          * Check for an ``inversion'' in the
  88                          * normally ascending cylinder numbers,
  89                          * indicating the start of the second request list.
  90                          */
  91                         if (ap->av_forw->b_cylin < ap->b_cylin) {
  92                                 /*
  93                                  * Search the second request list
  94                                  * for the first request at a larger
  95                                  * cylinder number.  We go before that;
  96                                  * if there is no such request, we go at end.
  97                                  */
  98                                 do {
  99                                         if (bp->b_cylin < ap->av_forw->b_cylin)
 100                                                 goto insert;
 101                                         ap = ap->av_forw;
 102                                 } while (ap->av_forw);
 103                                 goto insert;            /* after last */
 104                         }
 105                         ap = ap->av_forw;
 106                 }
 107                 /*
 108                  * No inversions... we will go after the last, and
 109                  * be the first request in the second request list.
 110                  */
 111                 goto insert;
 112         }
 113         /*
 114          * Request is at/after the current request...
 115          * sort in the first request list.
 116          */
 117         while (ap->av_forw) {
 118                 /*
 119                  * We want to go after the current request
 120                  * if there is an inversion after it (i.e. it is
 121                  * the end of the first request list), or if
 122                  * the next request is a larger cylinder than our request.
 123                  */
 124                 if (ap->av_forw->b_cylin < ap->b_cylin ||
 125                     bp->b_cylin < ap->av_forw->b_cylin)
 126                         goto insert;
 127                 ap = ap->av_forw;
 128         }
 129         /*
 130          * Neither a second list nor a larger
 131          * request... we go at the end of the first list,
 132          * which is the same as the end of the whole schebang.
 133          */
 134 insert:
 135         bp->av_forw = ap->av_forw;
 136         ap->av_forw = bp;
 137         if (ap == dp->b_actl)
 138                 dp->b_actl = bp;
 139 }