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