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