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
disksort(dp,bp)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