rf_sstf.c revision 1.1 1 1.1 oster /* $NetBSD: rf_sstf.c,v 1.1 1998/11/13 04:20:34 oster Exp $ */
2 1.1 oster /*
3 1.1 oster * Copyright (c) 1995 Carnegie-Mellon University.
4 1.1 oster * All rights reserved.
5 1.1 oster *
6 1.1 oster * Author: Jim Zelenka
7 1.1 oster *
8 1.1 oster * Permission to use, copy, modify and distribute this software and
9 1.1 oster * its documentation is hereby granted, provided that both the copyright
10 1.1 oster * notice and this permission notice appear in all copies of the
11 1.1 oster * software, derivative works or modified versions, and any portions
12 1.1 oster * thereof, and that both notices appear in supporting documentation.
13 1.1 oster *
14 1.1 oster * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
15 1.1 oster * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
16 1.1 oster * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
17 1.1 oster *
18 1.1 oster * Carnegie Mellon requests users of this software to return to
19 1.1 oster *
20 1.1 oster * Software Distribution Coordinator or Software.Distribution (at) CS.CMU.EDU
21 1.1 oster * School of Computer Science
22 1.1 oster * Carnegie Mellon University
23 1.1 oster * Pittsburgh PA 15213-3890
24 1.1 oster *
25 1.1 oster * any improvements or extensions that they make and grant Carnegie the
26 1.1 oster * rights to redistribute these changes.
27 1.1 oster */
28 1.1 oster
29 1.1 oster /*******************************************************************************
30 1.1 oster *
31 1.1 oster * sstf.c -- prioritized shortest seek time first disk queueing code
32 1.1 oster *
33 1.1 oster ******************************************************************************/
34 1.1 oster
35 1.1 oster /*
36 1.1 oster * :
37 1.1 oster * Log: rf_sstf.c,v
38 1.1 oster * Revision 1.7 1996/06/19 14:09:56 jimz
39 1.1 oster * SstfPeek wasn't calling closest_to_arm() properly- would bogart
40 1.1 oster * low priority I/Os
41 1.1 oster *
42 1.1 oster * Revision 1.6 1996/06/18 20:53:11 jimz
43 1.1 oster * fix up disk queueing (remove configure routine,
44 1.1 oster * add shutdown list arg to create routines)
45 1.1 oster *
46 1.1 oster * Revision 1.5 1996/06/13 20:42:13 jimz
47 1.1 oster * add scan, cscan
48 1.1 oster *
49 1.1 oster * Revision 1.4 1996/06/07 22:26:27 jimz
50 1.1 oster * type-ify which_ru (RF_ReconUnitNum_t)
51 1.1 oster *
52 1.1 oster * Revision 1.3 1996/06/07 21:33:04 jimz
53 1.1 oster * begin using consistent types for sector numbers,
54 1.1 oster * stripe numbers, row+col numbers, recon unit numbers
55 1.1 oster *
56 1.1 oster * Revision 1.2 1996/06/06 01:11:35 jimz
57 1.1 oster * fixed many priority-related bugs
58 1.1 oster *
59 1.1 oster * Revision 1.1 1996/06/05 19:17:40 jimz
60 1.1 oster * Initial revision
61 1.1 oster *
62 1.1 oster */
63 1.1 oster
64 1.1 oster #include "rf_alloclist.h"
65 1.1 oster #include "rf_stripelocks.h"
66 1.1 oster #include "rf_layout.h"
67 1.1 oster #include "rf_diskqueue.h"
68 1.1 oster #include "rf_sstf.h"
69 1.1 oster #include "rf_debugMem.h"
70 1.1 oster #include "rf_general.h"
71 1.1 oster #include "rf_threadid.h"
72 1.1 oster #include "rf_options.h"
73 1.1 oster
74 1.1 oster #define DIR_LEFT 1
75 1.1 oster #define DIR_RIGHT 2
76 1.1 oster #define DIR_EITHER 3
77 1.1 oster
78 1.1 oster #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
79 1.1 oster
80 1.1 oster #define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen))
81 1.1 oster
82 1.1 oster
83 1.1 oster static void do_sstf_ord_q(RF_DiskQueueData_t **,
84 1.1 oster RF_DiskQueueData_t **,
85 1.1 oster RF_DiskQueueData_t *);
86 1.1 oster
87 1.1 oster static RF_DiskQueueData_t *closest_to_arm(RF_SstfQ_t *,
88 1.1 oster RF_SectorNum_t,
89 1.1 oster int *,
90 1.1 oster int);
91 1.1 oster static void do_dequeue(RF_SstfQ_t *, RF_DiskQueueData_t *);
92 1.1 oster
93 1.1 oster
94 1.1 oster static void do_sstf_ord_q(queuep, tailp, req)
95 1.1 oster RF_DiskQueueData_t **queuep;
96 1.1 oster RF_DiskQueueData_t **tailp;
97 1.1 oster RF_DiskQueueData_t *req;
98 1.1 oster {
99 1.1 oster RF_DiskQueueData_t *r, *s;
100 1.1 oster
101 1.1 oster if (*queuep == NULL) {
102 1.1 oster *queuep = req;
103 1.1 oster *tailp = req;
104 1.1 oster req->next = NULL;
105 1.1 oster req->prev = NULL;
106 1.1 oster return;
107 1.1 oster }
108 1.1 oster if (req->sectorOffset <= (*queuep)->sectorOffset) {
109 1.1 oster req->next = *queuep;
110 1.1 oster req->prev = NULL;
111 1.1 oster (*queuep)->prev = req;
112 1.1 oster *queuep = req;
113 1.1 oster return;
114 1.1 oster }
115 1.1 oster if (req->sectorOffset > (*tailp)->sectorOffset) {
116 1.1 oster /* optimization */
117 1.1 oster r = NULL;
118 1.1 oster s = *tailp;
119 1.1 oster goto q_at_end;
120 1.1 oster }
121 1.1 oster for(s=NULL,r=*queuep;r;s=r,r=r->next) {
122 1.1 oster if (r->sectorOffset >= req->sectorOffset) {
123 1.1 oster /* insert after s, before r */
124 1.1 oster RF_ASSERT(s);
125 1.1 oster req->next = r;
126 1.1 oster r->prev = req;
127 1.1 oster s->next = req;
128 1.1 oster req->prev = s;
129 1.1 oster return;
130 1.1 oster }
131 1.1 oster }
132 1.1 oster q_at_end:
133 1.1 oster /* insert after s, at end of queue */
134 1.1 oster RF_ASSERT(r == NULL);
135 1.1 oster RF_ASSERT(s);
136 1.1 oster RF_ASSERT(s == (*tailp));
137 1.1 oster req->next = NULL;
138 1.1 oster req->prev = s;
139 1.1 oster s->next = req;
140 1.1 oster *tailp = req;
141 1.1 oster }
142 1.1 oster
143 1.1 oster /* for removing from head-of-queue */
144 1.1 oster #define DO_HEAD_DEQ(_r_,_q_) { \
145 1.1 oster _r_ = (_q_)->queue; \
146 1.1 oster RF_ASSERT((_r_) != NULL); \
147 1.1 oster (_q_)->queue = (_r_)->next; \
148 1.1 oster (_q_)->qlen--; \
149 1.1 oster if ((_q_)->qlen == 0) { \
150 1.1 oster RF_ASSERT((_r_) == (_q_)->qtail); \
151 1.1 oster RF_ASSERT((_q_)->queue == NULL); \
152 1.1 oster (_q_)->qtail = NULL; \
153 1.1 oster } \
154 1.1 oster else { \
155 1.1 oster RF_ASSERT((_q_)->queue->prev == (_r_)); \
156 1.1 oster (_q_)->queue->prev = NULL; \
157 1.1 oster } \
158 1.1 oster }
159 1.1 oster
160 1.1 oster /* for removing from end-of-queue */
161 1.1 oster #define DO_TAIL_DEQ(_r_,_q_) { \
162 1.1 oster _r_ = (_q_)->qtail; \
163 1.1 oster RF_ASSERT((_r_) != NULL); \
164 1.1 oster (_q_)->qtail = (_r_)->prev; \
165 1.1 oster (_q_)->qlen--; \
166 1.1 oster if ((_q_)->qlen == 0) { \
167 1.1 oster RF_ASSERT((_r_) == (_q_)->queue); \
168 1.1 oster RF_ASSERT((_q_)->qtail == NULL); \
169 1.1 oster (_q_)->queue = NULL; \
170 1.1 oster } \
171 1.1 oster else { \
172 1.1 oster RF_ASSERT((_q_)->qtail->next == (_r_)); \
173 1.1 oster (_q_)->qtail->next = NULL; \
174 1.1 oster } \
175 1.1 oster }
176 1.1 oster
177 1.1 oster #define DO_BEST_DEQ(_l_,_r_,_q_) { \
178 1.1 oster if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
179 1.1 oster < SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
180 1.1 oster { \
181 1.1 oster DO_HEAD_DEQ(_r_,_q_); \
182 1.1 oster } \
183 1.1 oster else { \
184 1.1 oster DO_TAIL_DEQ(_r_,_q_); \
185 1.1 oster } \
186 1.1 oster }
187 1.1 oster
188 1.1 oster static RF_DiskQueueData_t *closest_to_arm(queue, arm_pos, dir, allow_reverse)
189 1.1 oster RF_SstfQ_t *queue;
190 1.1 oster RF_SectorNum_t arm_pos;
191 1.1 oster int *dir;
192 1.1 oster int allow_reverse;
193 1.1 oster {
194 1.1 oster RF_SectorNum_t best_pos_l=0, this_pos_l=0, last_pos=0;
195 1.1 oster RF_SectorNum_t best_pos_r=0, this_pos_r=0;
196 1.1 oster RF_DiskQueueData_t *r, *best_l, *best_r;
197 1.1 oster
198 1.1 oster best_r = best_l = NULL;
199 1.1 oster for(r=queue->queue;r;r=r->next) {
200 1.1 oster if (r->sectorOffset < arm_pos) {
201 1.1 oster if (best_l == NULL) {
202 1.1 oster best_l = r;
203 1.1 oster last_pos = best_pos_l = this_pos_l;
204 1.1 oster }
205 1.1 oster else {
206 1.1 oster this_pos_l = arm_pos - r->sectorOffset;
207 1.1 oster if (this_pos_l < best_pos_l) {
208 1.1 oster best_l = r;
209 1.1 oster last_pos = best_pos_l = this_pos_l;
210 1.1 oster }
211 1.1 oster else {
212 1.1 oster last_pos = this_pos_l;
213 1.1 oster }
214 1.1 oster }
215 1.1 oster }
216 1.1 oster else {
217 1.1 oster if (best_r == NULL) {
218 1.1 oster best_r = r;
219 1.1 oster last_pos = best_pos_r = this_pos_r;
220 1.1 oster }
221 1.1 oster else {
222 1.1 oster this_pos_r = r->sectorOffset - arm_pos;
223 1.1 oster if (this_pos_r < best_pos_r) {
224 1.1 oster best_r = r;
225 1.1 oster last_pos = best_pos_r = this_pos_r;
226 1.1 oster }
227 1.1 oster else {
228 1.1 oster last_pos = this_pos_r;
229 1.1 oster }
230 1.1 oster if (this_pos_r > last_pos) {
231 1.1 oster /* getting farther away */
232 1.1 oster break;
233 1.1 oster }
234 1.1 oster }
235 1.1 oster }
236 1.1 oster }
237 1.1 oster if ((best_r == NULL) && (best_l == NULL))
238 1.1 oster return(NULL);
239 1.1 oster if ((*dir == DIR_RIGHT) && best_r)
240 1.1 oster return(best_r);
241 1.1 oster if ((*dir == DIR_LEFT) && best_l)
242 1.1 oster return(best_l);
243 1.1 oster if (*dir == DIR_EITHER) {
244 1.1 oster if (best_l == NULL)
245 1.1 oster return(best_r);
246 1.1 oster if (best_r == NULL)
247 1.1 oster return(best_l);
248 1.1 oster if (best_pos_r < best_pos_l)
249 1.1 oster return(best_r);
250 1.1 oster else
251 1.1 oster return(best_l);
252 1.1 oster }
253 1.1 oster /*
254 1.1 oster * Nothing in the direction we want to go. Reverse or
255 1.1 oster * reset the arm. We know we have an I/O in the other
256 1.1 oster * direction.
257 1.1 oster */
258 1.1 oster if (allow_reverse) {
259 1.1 oster if (*dir == DIR_RIGHT) {
260 1.1 oster *dir = DIR_LEFT;
261 1.1 oster return(best_l);
262 1.1 oster }
263 1.1 oster else {
264 1.1 oster *dir = DIR_RIGHT;
265 1.1 oster return(best_r);
266 1.1 oster }
267 1.1 oster }
268 1.1 oster /*
269 1.1 oster * Reset (beginning of queue).
270 1.1 oster */
271 1.1 oster RF_ASSERT(*dir == DIR_RIGHT);
272 1.1 oster return(queue->queue);
273 1.1 oster }
274 1.1 oster
275 1.1 oster void *rf_SstfCreate(sect_per_disk, cl_list, listp)
276 1.1 oster RF_SectorCount_t sect_per_disk;
277 1.1 oster RF_AllocListElem_t *cl_list;
278 1.1 oster RF_ShutdownList_t **listp;
279 1.1 oster {
280 1.1 oster RF_Sstf_t *sstfq;
281 1.1 oster
282 1.1 oster RF_CallocAndAdd(sstfq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
283 1.1 oster sstfq->dir = DIR_EITHER;
284 1.1 oster sstfq->allow_reverse = 1;
285 1.1 oster return((void *)sstfq);
286 1.1 oster }
287 1.1 oster
288 1.1 oster void *rf_ScanCreate(sect_per_disk, cl_list, listp)
289 1.1 oster RF_SectorCount_t sect_per_disk;
290 1.1 oster RF_AllocListElem_t *cl_list;
291 1.1 oster RF_ShutdownList_t **listp;
292 1.1 oster {
293 1.1 oster RF_Sstf_t *scanq;
294 1.1 oster
295 1.1 oster RF_CallocAndAdd(scanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
296 1.1 oster scanq->dir = DIR_RIGHT;
297 1.1 oster scanq->allow_reverse = 1;
298 1.1 oster return((void *)scanq);
299 1.1 oster }
300 1.1 oster
301 1.1 oster void *rf_CscanCreate(sect_per_disk, cl_list, listp)
302 1.1 oster RF_SectorCount_t sect_per_disk;
303 1.1 oster RF_AllocListElem_t *cl_list;
304 1.1 oster RF_ShutdownList_t **listp;
305 1.1 oster {
306 1.1 oster RF_Sstf_t *cscanq;
307 1.1 oster
308 1.1 oster RF_CallocAndAdd(cscanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list);
309 1.1 oster cscanq->dir = DIR_RIGHT;
310 1.1 oster return((void *)cscanq);
311 1.1 oster }
312 1.1 oster
313 1.1 oster void rf_SstfEnqueue(qptr, req, priority)
314 1.1 oster void *qptr;
315 1.1 oster RF_DiskQueueData_t *req;
316 1.1 oster int priority;
317 1.1 oster {
318 1.1 oster RF_Sstf_t *sstfq;
319 1.1 oster
320 1.1 oster sstfq = (RF_Sstf_t *)qptr;
321 1.1 oster
322 1.1 oster if (priority == RF_IO_LOW_PRIORITY) {
323 1.1 oster if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
324 1.1 oster RF_DiskQueue_t *dq;
325 1.1 oster int tid;
326 1.1 oster rf_get_threadid(tid);
327 1.1 oster dq = (RF_DiskQueue_t *)req->queue;
328 1.1 oster printf("[%d] ENQ lopri %d,%d queues are %d,%d,%d\n",
329 1.1 oster tid, dq->row, dq->col, sstfq->left.qlen, sstfq->right.qlen,
330 1.1 oster sstfq->lopri.qlen);
331 1.1 oster }
332 1.1 oster do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
333 1.1 oster sstfq->lopri.qlen++;
334 1.1 oster }
335 1.1 oster else {
336 1.1 oster if (req->sectorOffset < sstfq->last_sector) {
337 1.1 oster do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req);
338 1.1 oster sstfq->left.qlen++;
339 1.1 oster }
340 1.1 oster else {
341 1.1 oster do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req);
342 1.1 oster sstfq->right.qlen++;
343 1.1 oster }
344 1.1 oster }
345 1.1 oster }
346 1.1 oster
347 1.1 oster static void do_dequeue(queue, req)
348 1.1 oster RF_SstfQ_t *queue;
349 1.1 oster RF_DiskQueueData_t *req;
350 1.1 oster {
351 1.1 oster RF_DiskQueueData_t *req2;
352 1.1 oster
353 1.1 oster if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
354 1.1 oster int tid;
355 1.1 oster rf_get_threadid(tid);
356 1.1 oster printf("[%d] do_dequeue\n", tid);
357 1.1 oster }
358 1.1 oster if (req == queue->queue) {
359 1.1 oster DO_HEAD_DEQ(req2,queue);
360 1.1 oster RF_ASSERT(req2 == req);
361 1.1 oster }
362 1.1 oster else if (req == queue->qtail) {
363 1.1 oster DO_TAIL_DEQ(req2,queue);
364 1.1 oster RF_ASSERT(req2 == req);
365 1.1 oster }
366 1.1 oster else {
367 1.1 oster /* dequeue from middle of list */
368 1.1 oster RF_ASSERT(req->next);
369 1.1 oster RF_ASSERT(req->prev);
370 1.1 oster queue->qlen--;
371 1.1 oster req->next->prev = req->prev;
372 1.1 oster req->prev->next = req->next;
373 1.1 oster req->next = req->prev = NULL;
374 1.1 oster }
375 1.1 oster }
376 1.1 oster
377 1.1 oster RF_DiskQueueData_t *rf_SstfDequeue(qptr)
378 1.1 oster void *qptr;
379 1.1 oster {
380 1.1 oster RF_DiskQueueData_t *req=NULL;
381 1.1 oster RF_Sstf_t *sstfq;
382 1.1 oster
383 1.1 oster sstfq = (RF_Sstf_t *)qptr;
384 1.1 oster
385 1.1 oster if (rf_sstfDebug) {
386 1.1 oster RF_DiskQueue_t *dq;
387 1.1 oster int tid;
388 1.1 oster rf_get_threadid(tid);
389 1.1 oster dq = (RF_DiskQueue_t *)req->queue;
390 1.1 oster RF_ASSERT(QSUM(sstfq)==dq->queueLength);
391 1.1 oster printf("[%d] sstf: Dequeue %d,%d queues are %d,%d,%d\n", tid,
392 1.1 oster dq->row, dq->col, sstfq->left.qlen, sstfq->right.qlen,
393 1.1 oster sstfq->lopri.qlen);
394 1.1 oster }
395 1.1 oster if (sstfq->left.queue == NULL) {
396 1.1 oster RF_ASSERT(sstfq->left.qlen == 0);
397 1.1 oster if (sstfq->right.queue == NULL) {
398 1.1 oster RF_ASSERT(sstfq->right.qlen == 0);
399 1.1 oster if (sstfq->lopri.queue == NULL) {
400 1.1 oster RF_ASSERT(sstfq->lopri.qlen == 0);
401 1.1 oster return(NULL);
402 1.1 oster }
403 1.1 oster if (rf_sstfDebug) {
404 1.1 oster int tid;
405 1.1 oster rf_get_threadid(tid);
406 1.1 oster printf("[%d] sstf: check for close lopri", tid);
407 1.1 oster }
408 1.1 oster req = closest_to_arm(&sstfq->lopri, sstfq->last_sector,
409 1.1 oster &sstfq->dir, sstfq->allow_reverse);
410 1.1 oster if (rf_sstfDebug) {
411 1.1 oster int tid;
412 1.1 oster rf_get_threadid(tid);
413 1.1 oster printf("[%d] sstf: closest_to_arm said %lx", tid, (long)req);
414 1.1 oster }
415 1.1 oster if (req == NULL)
416 1.1 oster return(NULL);
417 1.1 oster do_dequeue(&sstfq->lopri, req);
418 1.1 oster }
419 1.1 oster else {
420 1.1 oster DO_BEST_DEQ(sstfq->last_sector,req,&sstfq->right);
421 1.1 oster }
422 1.1 oster }
423 1.1 oster else {
424 1.1 oster if (sstfq->right.queue == NULL) {
425 1.1 oster RF_ASSERT(sstfq->right.qlen == 0);
426 1.1 oster DO_BEST_DEQ(sstfq->last_sector,req,&sstfq->left);
427 1.1 oster }
428 1.1 oster else {
429 1.1 oster if (SNUM_DIFF(sstfq->last_sector,sstfq->right.queue->sectorOffset)
430 1.1 oster < SNUM_DIFF(sstfq->last_sector,sstfq->left.qtail->sectorOffset))
431 1.1 oster {
432 1.1 oster DO_HEAD_DEQ(req,&sstfq->right);
433 1.1 oster }
434 1.1 oster else {
435 1.1 oster DO_TAIL_DEQ(req,&sstfq->left);
436 1.1 oster }
437 1.1 oster }
438 1.1 oster }
439 1.1 oster RF_ASSERT(req);
440 1.1 oster sstfq->last_sector = req->sectorOffset;
441 1.1 oster return(req);
442 1.1 oster }
443 1.1 oster
444 1.1 oster RF_DiskQueueData_t *rf_ScanDequeue(qptr)
445 1.1 oster void *qptr;
446 1.1 oster {
447 1.1 oster RF_DiskQueueData_t *req=NULL;
448 1.1 oster RF_Sstf_t *scanq;
449 1.1 oster
450 1.1 oster scanq = (RF_Sstf_t *)qptr;
451 1.1 oster
452 1.1 oster if (rf_scanDebug) {
453 1.1 oster RF_DiskQueue_t *dq;
454 1.1 oster int tid;
455 1.1 oster rf_get_threadid(tid);
456 1.1 oster dq = (RF_DiskQueue_t *)req->queue;
457 1.1 oster RF_ASSERT(QSUM(scanq)==dq->queueLength);
458 1.1 oster printf("[%d] scan: Dequeue %d,%d queues are %d,%d,%d\n", tid,
459 1.1 oster dq->row, dq->col, scanq->left.qlen, scanq->right.qlen,
460 1.1 oster scanq->lopri.qlen);
461 1.1 oster }
462 1.1 oster if (scanq->left.queue == NULL) {
463 1.1 oster RF_ASSERT(scanq->left.qlen == 0);
464 1.1 oster if (scanq->right.queue == NULL) {
465 1.1 oster RF_ASSERT(scanq->right.qlen == 0);
466 1.1 oster if (scanq->lopri.queue == NULL) {
467 1.1 oster RF_ASSERT(scanq->lopri.qlen == 0);
468 1.1 oster return(NULL);
469 1.1 oster }
470 1.1 oster req = closest_to_arm(&scanq->lopri, scanq->last_sector,
471 1.1 oster &scanq->dir, scanq->allow_reverse);
472 1.1 oster if (req == NULL)
473 1.1 oster return(NULL);
474 1.1 oster do_dequeue(&scanq->lopri, req);
475 1.1 oster }
476 1.1 oster else {
477 1.1 oster scanq->dir = DIR_RIGHT;
478 1.1 oster DO_HEAD_DEQ(req,&scanq->right);
479 1.1 oster }
480 1.1 oster }
481 1.1 oster else if (scanq->right.queue == NULL) {
482 1.1 oster RF_ASSERT(scanq->right.qlen == 0);
483 1.1 oster RF_ASSERT(scanq->left.queue);
484 1.1 oster scanq->dir = DIR_LEFT;
485 1.1 oster DO_TAIL_DEQ(req,&scanq->left);
486 1.1 oster }
487 1.1 oster else {
488 1.1 oster RF_ASSERT(scanq->right.queue);
489 1.1 oster RF_ASSERT(scanq->left.queue);
490 1.1 oster if (scanq->dir == DIR_RIGHT) {
491 1.1 oster DO_HEAD_DEQ(req,&scanq->right);
492 1.1 oster }
493 1.1 oster else {
494 1.1 oster DO_TAIL_DEQ(req,&scanq->left);
495 1.1 oster }
496 1.1 oster }
497 1.1 oster RF_ASSERT(req);
498 1.1 oster scanq->last_sector = req->sectorOffset;
499 1.1 oster return(req);
500 1.1 oster }
501 1.1 oster
502 1.1 oster RF_DiskQueueData_t *rf_CscanDequeue(qptr)
503 1.1 oster void *qptr;
504 1.1 oster {
505 1.1 oster RF_DiskQueueData_t *req=NULL;
506 1.1 oster RF_Sstf_t *cscanq;
507 1.1 oster
508 1.1 oster cscanq = (RF_Sstf_t *)qptr;
509 1.1 oster
510 1.1 oster RF_ASSERT(cscanq->dir == DIR_RIGHT);
511 1.1 oster if (rf_cscanDebug) {
512 1.1 oster RF_DiskQueue_t *dq;
513 1.1 oster int tid;
514 1.1 oster rf_get_threadid(tid);
515 1.1 oster dq = (RF_DiskQueue_t *)req->queue;
516 1.1 oster RF_ASSERT(QSUM(cscanq)==dq->queueLength);
517 1.1 oster printf("[%d] scan: Dequeue %d,%d queues are %d,%d,%d\n", tid,
518 1.1 oster dq->row, dq->col, cscanq->left.qlen, cscanq->right.qlen,
519 1.1 oster cscanq->lopri.qlen);
520 1.1 oster }
521 1.1 oster if (cscanq->right.queue) {
522 1.1 oster DO_HEAD_DEQ(req,&cscanq->right);
523 1.1 oster }
524 1.1 oster else {
525 1.1 oster RF_ASSERT(cscanq->right.qlen == 0);
526 1.1 oster if (cscanq->left.queue == NULL) {
527 1.1 oster RF_ASSERT(cscanq->left.qlen == 0);
528 1.1 oster if (cscanq->lopri.queue == NULL) {
529 1.1 oster RF_ASSERT(cscanq->lopri.qlen == 0);
530 1.1 oster return(NULL);
531 1.1 oster }
532 1.1 oster req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
533 1.1 oster &cscanq->dir, cscanq->allow_reverse);
534 1.1 oster if (req == NULL)
535 1.1 oster return(NULL);
536 1.1 oster do_dequeue(&cscanq->lopri, req);
537 1.1 oster }
538 1.1 oster else {
539 1.1 oster /*
540 1.1 oster * There's I/Os to the left of the arm. Swing
541 1.1 oster * on back (swap queues).
542 1.1 oster */
543 1.1 oster cscanq->right = cscanq->left;
544 1.1 oster cscanq->left.qlen = 0;
545 1.1 oster cscanq->left.queue = cscanq->left.qtail = NULL;
546 1.1 oster DO_HEAD_DEQ(req,&cscanq->right);
547 1.1 oster }
548 1.1 oster }
549 1.1 oster RF_ASSERT(req);
550 1.1 oster cscanq->last_sector = req->sectorOffset;
551 1.1 oster return(req);
552 1.1 oster }
553 1.1 oster
554 1.1 oster RF_DiskQueueData_t *rf_SstfPeek(qptr)
555 1.1 oster void *qptr;
556 1.1 oster {
557 1.1 oster RF_DiskQueueData_t *req;
558 1.1 oster RF_Sstf_t *sstfq;
559 1.1 oster
560 1.1 oster sstfq = (RF_Sstf_t *)qptr;
561 1.1 oster
562 1.1 oster if ((sstfq->left.queue == NULL) && (sstfq->right.queue == NULL)) {
563 1.1 oster req = closest_to_arm(&sstfq->lopri, sstfq->last_sector, &sstfq->dir,
564 1.1 oster sstfq->allow_reverse);
565 1.1 oster }
566 1.1 oster else {
567 1.1 oster if (sstfq->left.queue == NULL)
568 1.1 oster req = sstfq->right.queue;
569 1.1 oster else {
570 1.1 oster if (sstfq->right.queue == NULL)
571 1.1 oster req = sstfq->left.queue;
572 1.1 oster else {
573 1.1 oster if (SNUM_DIFF(sstfq->last_sector,sstfq->right.queue->sectorOffset)
574 1.1 oster <SNUM_DIFF(sstfq->last_sector,sstfq->left.qtail->sectorOffset))
575 1.1 oster {
576 1.1 oster req = sstfq->right.queue;
577 1.1 oster }
578 1.1 oster else {
579 1.1 oster req = sstfq->left.qtail;
580 1.1 oster }
581 1.1 oster }
582 1.1 oster }
583 1.1 oster }
584 1.1 oster if (req == NULL) {
585 1.1 oster RF_ASSERT(QSUM(sstfq) == 0);
586 1.1 oster }
587 1.1 oster return(req);
588 1.1 oster }
589 1.1 oster
590 1.1 oster RF_DiskQueueData_t *rf_ScanPeek(qptr)
591 1.1 oster void *qptr;
592 1.1 oster {
593 1.1 oster RF_DiskQueueData_t *req;
594 1.1 oster RF_Sstf_t *scanq;
595 1.1 oster int dir;
596 1.1 oster
597 1.1 oster scanq = (RF_Sstf_t *)qptr;
598 1.1 oster dir = scanq->dir;
599 1.1 oster
600 1.1 oster if (scanq->left.queue == NULL) {
601 1.1 oster RF_ASSERT(scanq->left.qlen == 0);
602 1.1 oster if (scanq->right.queue == NULL) {
603 1.1 oster RF_ASSERT(scanq->right.qlen == 0);
604 1.1 oster if (scanq->lopri.queue == NULL) {
605 1.1 oster RF_ASSERT(scanq->lopri.qlen == 0);
606 1.1 oster return(NULL);
607 1.1 oster }
608 1.1 oster req = closest_to_arm(&scanq->lopri, scanq->last_sector,
609 1.1 oster &dir, scanq->allow_reverse);
610 1.1 oster }
611 1.1 oster else {
612 1.1 oster req = scanq->right.queue;
613 1.1 oster }
614 1.1 oster }
615 1.1 oster else if (scanq->right.queue == NULL) {
616 1.1 oster RF_ASSERT(scanq->right.qlen == 0);
617 1.1 oster RF_ASSERT(scanq->left.queue);
618 1.1 oster req = scanq->left.qtail;
619 1.1 oster }
620 1.1 oster else {
621 1.1 oster RF_ASSERT(scanq->right.queue);
622 1.1 oster RF_ASSERT(scanq->left.queue);
623 1.1 oster if (scanq->dir == DIR_RIGHT) {
624 1.1 oster req = scanq->right.queue;
625 1.1 oster }
626 1.1 oster else {
627 1.1 oster req = scanq->left.qtail;
628 1.1 oster }
629 1.1 oster }
630 1.1 oster if (req == NULL) {
631 1.1 oster RF_ASSERT(QSUM(scanq) == 0);
632 1.1 oster }
633 1.1 oster return(req);
634 1.1 oster }
635 1.1 oster
636 1.1 oster RF_DiskQueueData_t *rf_CscanPeek(qptr)
637 1.1 oster void *qptr;
638 1.1 oster {
639 1.1 oster RF_DiskQueueData_t *req;
640 1.1 oster RF_Sstf_t *cscanq;
641 1.1 oster
642 1.1 oster cscanq = (RF_Sstf_t *)qptr;
643 1.1 oster
644 1.1 oster RF_ASSERT(cscanq->dir == DIR_RIGHT);
645 1.1 oster if (cscanq->right.queue) {
646 1.1 oster req = cscanq->right.queue;
647 1.1 oster }
648 1.1 oster else {
649 1.1 oster RF_ASSERT(cscanq->right.qlen == 0);
650 1.1 oster if (cscanq->left.queue == NULL) {
651 1.1 oster RF_ASSERT(cscanq->left.qlen == 0);
652 1.1 oster if (cscanq->lopri.queue == NULL) {
653 1.1 oster RF_ASSERT(cscanq->lopri.qlen == 0);
654 1.1 oster return(NULL);
655 1.1 oster }
656 1.1 oster req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
657 1.1 oster &cscanq->dir, cscanq->allow_reverse);
658 1.1 oster }
659 1.1 oster else {
660 1.1 oster /*
661 1.1 oster * There's I/Os to the left of the arm. We'll end
662 1.1 oster * up swinging on back.
663 1.1 oster */
664 1.1 oster req = cscanq->left.queue;
665 1.1 oster }
666 1.1 oster }
667 1.1 oster if (req == NULL) {
668 1.1 oster RF_ASSERT(QSUM(cscanq) == 0);
669 1.1 oster }
670 1.1 oster return(req);
671 1.1 oster }
672 1.1 oster
673 1.1 oster int rf_SstfPromote(qptr, parityStripeID, which_ru)
674 1.1 oster void *qptr;
675 1.1 oster RF_StripeNum_t parityStripeID;
676 1.1 oster RF_ReconUnitNum_t which_ru;
677 1.1 oster {
678 1.1 oster RF_DiskQueueData_t *r, *next;
679 1.1 oster RF_Sstf_t *sstfq;
680 1.1 oster int n;
681 1.1 oster
682 1.1 oster sstfq = (RF_Sstf_t *)qptr;
683 1.1 oster
684 1.1 oster n = 0;
685 1.1 oster if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
686 1.1 oster int tid;
687 1.1 oster rf_get_threadid(tid);
688 1.1 oster printf("[%d] promote %ld %d queues are %d,%d,%d\n",
689 1.1 oster tid, (long)parityStripeID, (int)which_ru,
690 1.1 oster sstfq->left.qlen,
691 1.1 oster sstfq->right.qlen,
692 1.1 oster sstfq->lopri.qlen);
693 1.1 oster }
694 1.1 oster for(r=sstfq->lopri.queue;r;r=next) {
695 1.1 oster next = r->next;
696 1.1 oster if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
697 1.1 oster int tid;
698 1.1 oster rf_get_threadid(tid);
699 1.1 oster printf("[%d] check promote %lx\n", tid, (long)r);
700 1.1 oster }
701 1.1 oster if ((r->parityStripeID == parityStripeID)
702 1.1 oster && (r->which_ru == which_ru))
703 1.1 oster {
704 1.1 oster do_dequeue(&sstfq->lopri, r);
705 1.1 oster rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY);
706 1.1 oster n++;
707 1.1 oster }
708 1.1 oster }
709 1.1 oster if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
710 1.1 oster int tid;
711 1.1 oster rf_get_threadid(tid);
712 1.1 oster printf("[%d] promoted %d matching I/Os queues are %d,%d,%d\n",
713 1.1 oster tid, n, sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen);
714 1.1 oster }
715 1.1 oster return(n);
716 1.1 oster }
717