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 } 140