1 /* $NetBSD: rf_sstf.c,v 1.18 2021/07/23 20:18:24 oster Exp $ */
2 /*
3 * Copyright (c) 1995 Carnegie-Mellon University.
4 * All rights reserved.
5 *
6 * Author: Jim Zelenka
7 *
8 * Permission to use, copy, modify and distribute this software and
9 * its documentation is hereby granted, provided that both the copyright
10 * notice and this permission notice appear in all copies of the
11 * software, derivative works or modified versions, and any portions
12 * thereof, and that both notices appear in supporting documentation.
13 *
14 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
15 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
16 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
17 *
18 * Carnegie Mellon requests users of this software to return to
19 *
20 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
21 * School of Computer Science
22 * Carnegie Mellon University
23 * Pittsburgh PA 15213-3890
24 *
25 * any improvements or extensions that they make and grant Carnegie the
26 * rights to redistribute these changes.
27 */
28
29 /*******************************************************************************
30 *
31 * sstf.c -- prioritized shortest seek time first disk queueing code
32 *
33 ******************************************************************************/
34
35 #include <sys/cdefs.h>
36 __KERNEL_RCSID(0, "$NetBSD: rf_sstf.c,v 1.18 2021/07/23 20:18:24 oster Exp $");
37
38 #include <dev/raidframe/raidframevar.h>
39
40 #include "rf_alloclist.h"
41 #include "rf_stripelocks.h"
42 #include "rf_layout.h"
43 #include "rf_diskqueue.h"
44 #include "rf_sstf.h"
45 #include "rf_debugMem.h"
46 #include "rf_general.h"
47 #include "rf_options.h"
48 #include "rf_raid.h"
49
50 #define DIR_LEFT 1
51 #define DIR_RIGHT 2
52 #define DIR_EITHER 3
53
54 #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
55
56 #define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen))
57
58
59 static void
60 do_sstf_ord_q(RF_DiskQueueData_t **,
61 RF_DiskQueueData_t **,
62 RF_DiskQueueData_t *);
63
64 static RF_DiskQueueData_t *
65 closest_to_arm(RF_SstfQ_t *,
66 RF_SectorNum_t,
67 int *,
68 int);
69 static void do_dequeue(RF_SstfQ_t *, RF_DiskQueueData_t *);
70
71
72 static void
do_sstf_ord_q(RF_DiskQueueData_t ** queuep,RF_DiskQueueData_t ** tailp,RF_DiskQueueData_t * req)73 do_sstf_ord_q(RF_DiskQueueData_t **queuep, RF_DiskQueueData_t **tailp, RF_DiskQueueData_t *req)
74 {
75 RF_DiskQueueData_t *r, *s;
76
77 if (*queuep == NULL) {
78 *queuep = req;
79 *tailp = req;
80 req->next = NULL;
81 req->prev = NULL;
82 return;
83 }
84 if (req->sectorOffset <= (*queuep)->sectorOffset) {
85 req->next = *queuep;
86 req->prev = NULL;
87 (*queuep)->prev = req;
88 *queuep = req;
89 return;
90 }
91 if (req->sectorOffset > (*tailp)->sectorOffset) {
92 /* optimization */
93 r = NULL;
94 s = *tailp;
95 goto q_at_end;
96 }
97 for (s = NULL, r = *queuep; r; s = r, r = r->next) {
98 if (r->sectorOffset >= req->sectorOffset) {
99 /* insert after s, before r */
100 RF_ASSERT(s);
101 req->next = r;
102 r->prev = req;
103 s->next = req;
104 req->prev = s;
105 return;
106 }
107 }
108 q_at_end:
109 /* insert after s, at end of queue */
110 RF_ASSERT(r == NULL);
111 RF_ASSERT(s);
112 RF_ASSERT(s == (*tailp));
113 req->next = NULL;
114 req->prev = s;
115 s->next = req;
116 *tailp = req;
117 }
118 /* for removing from head-of-queue */
119 #define DO_HEAD_DEQ(_r_,_q_) { \
120 _r_ = (_q_)->queue; \
121 RF_ASSERT((_r_) != NULL); \
122 (_q_)->queue = (_r_)->next; \
123 (_q_)->qlen--; \
124 if ((_q_)->qlen == 0) { \
125 RF_ASSERT((_r_) == (_q_)->qtail); \
126 RF_ASSERT((_q_)->queue == NULL); \
127 (_q_)->qtail = NULL; \
128 } \
129 else { \
130 RF_ASSERT((_q_)->queue->prev == (_r_)); \
131 (_q_)->queue->prev = NULL; \
132 } \
133 }
134
135 /* for removing from end-of-queue */
136 #define DO_TAIL_DEQ(_r_,_q_) { \
137 _r_ = (_q_)->qtail; \
138 RF_ASSERT((_r_) != NULL); \
139 (_q_)->qtail = (_r_)->prev; \
140 (_q_)->qlen--; \
141 if ((_q_)->qlen == 0) { \
142 RF_ASSERT((_r_) == (_q_)->queue); \
143 RF_ASSERT((_q_)->qtail == NULL); \
144 (_q_)->queue = NULL; \
145 } \
146 else { \
147 RF_ASSERT((_q_)->qtail->next == (_r_)); \
148 (_q_)->qtail->next = NULL; \
149 } \
150 }
151
152 #define DO_BEST_DEQ(_l_,_r_,_q_) { \
153 if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \
154 < SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \
155 { \
156 DO_HEAD_DEQ(_r_,_q_); \
157 } \
158 else { \
159 DO_TAIL_DEQ(_r_,_q_); \
160 } \
161 }
162
163 static RF_DiskQueueData_t *
closest_to_arm(RF_SstfQ_t * queue,RF_SectorNum_t arm_pos,int * dir,int allow_reverse)164 closest_to_arm(RF_SstfQ_t *queue, RF_SectorNum_t arm_pos, int *dir, int allow_reverse)
165 {
166 RF_SectorNum_t best_pos_l = 0, this_pos_l = 0, last_pos = 0;
167 RF_SectorNum_t best_pos_r = 0, this_pos_r = 0;
168 RF_DiskQueueData_t *r, *best_l, *best_r;
169
170 best_r = best_l = NULL;
171 for (r = queue->queue; r; r = r->next) {
172 if (r->sectorOffset < arm_pos) {
173 if (best_l == NULL) {
174 best_l = r;
175 last_pos = best_pos_l = this_pos_l;
176 } else {
177 this_pos_l = arm_pos - r->sectorOffset;
178 if (this_pos_l < best_pos_l) {
179 best_l = r;
180 last_pos = best_pos_l = this_pos_l;
181 } else {
182 last_pos = this_pos_l;
183 }
184 }
185 } else {
186 if (best_r == NULL) {
187 best_r = r;
188 last_pos = best_pos_r = this_pos_r;
189 } else {
190 this_pos_r = r->sectorOffset - arm_pos;
191 if (this_pos_r < best_pos_r) {
192 best_r = r;
193 last_pos = best_pos_r = this_pos_r;
194 } else {
195 last_pos = this_pos_r;
196 }
197 if (this_pos_r > last_pos) {
198 /* getting farther away */
199 break;
200 }
201 }
202 }
203 }
204 if ((best_r == NULL) && (best_l == NULL))
205 return (NULL);
206 if ((*dir == DIR_RIGHT) && best_r)
207 return (best_r);
208 if ((*dir == DIR_LEFT) && best_l)
209 return (best_l);
210 if (*dir == DIR_EITHER) {
211 if (best_l == NULL)
212 return (best_r);
213 if (best_r == NULL)
214 return (best_l);
215 if (best_pos_r < best_pos_l)
216 return (best_r);
217 else
218 return (best_l);
219 }
220 /*
221 * Nothing in the direction we want to go. Reverse or
222 * reset the arm. We know we have an I/O in the other
223 * direction.
224 */
225 if (allow_reverse) {
226 if (*dir == DIR_RIGHT) {
227 *dir = DIR_LEFT;
228 return (best_l);
229 } else {
230 *dir = DIR_RIGHT;
231 return (best_r);
232 }
233 }
234 /*
235 * Reset (beginning of queue).
236 */
237 RF_ASSERT(*dir == DIR_RIGHT);
238 return (queue->queue);
239 }
240
241 void *
rf_SstfCreate(RF_SectorCount_t sect_per_disk,RF_AllocListElem_t * cl_list,RF_ShutdownList_t ** listp)242 rf_SstfCreate(
243 RF_SectorCount_t sect_per_disk,
244 RF_AllocListElem_t *cl_list,
245 RF_ShutdownList_t **listp)
246 {
247 RF_Sstf_t *sstfq;
248
249 sstfq = RF_MallocAndAdd(sizeof(*sstfq), cl_list);
250 sstfq->dir = DIR_EITHER;
251 sstfq->allow_reverse = 1;
252 return ((void *) sstfq);
253 }
254
255 void *
rf_ScanCreate(RF_SectorCount_t sect_per_disk,RF_AllocListElem_t * cl_list,RF_ShutdownList_t ** listp)256 rf_ScanCreate(
257 RF_SectorCount_t sect_per_disk,
258 RF_AllocListElem_t *cl_list,
259 RF_ShutdownList_t **listp)
260 {
261 RF_Sstf_t *scanq;
262
263 scanq = RF_MallocAndAdd(sizeof(*scanq), cl_list);
264 scanq->dir = DIR_RIGHT;
265 scanq->allow_reverse = 1;
266 return ((void *) scanq);
267 }
268
269 void *
rf_CscanCreate(RF_SectorCount_t sect_per_disk,RF_AllocListElem_t * cl_list,RF_ShutdownList_t ** listp)270 rf_CscanCreate(
271 RF_SectorCount_t sect_per_disk,
272 RF_AllocListElem_t *cl_list,
273 RF_ShutdownList_t **listp)
274 {
275 RF_Sstf_t *cscanq;
276
277 cscanq = RF_MallocAndAdd(sizeof(*cscanq), cl_list);
278 cscanq->dir = DIR_RIGHT;
279 return ((void *) cscanq);
280 }
281
282 void
rf_SstfEnqueue(void * qptr,RF_DiskQueueData_t * req,int priority)283 rf_SstfEnqueue(void *qptr, RF_DiskQueueData_t *req, int priority)
284 {
285 RF_Sstf_t *sstfq;
286
287 sstfq = (RF_Sstf_t *) qptr;
288
289 if (priority == RF_IO_LOW_PRIORITY) {
290 #if RF_DEBUG_QUEUE
291 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
292 RF_DiskQueue_t *dq;
293 dq = (RF_DiskQueue_t *) req->queue;
294 printf("raid%d: ENQ lopri %d queues are %d,%d,%d\n",
295 req->raidPtr->raidid,
296 dq->col,
297 sstfq->left.qlen, sstfq->right.qlen,
298 sstfq->lopri.qlen);
299 }
300 #endif
301 do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req);
302 sstfq->lopri.qlen++;
303 } else {
304 if (req->sectorOffset < sstfq->last_sector) {
305 do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req);
306 sstfq->left.qlen++;
307 } else {
308 do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req);
309 sstfq->right.qlen++;
310 }
311 }
312 }
313
314 static void
do_dequeue(RF_SstfQ_t * queue,RF_DiskQueueData_t * req)315 do_dequeue(RF_SstfQ_t *queue, RF_DiskQueueData_t *req)
316 {
317 RF_DiskQueueData_t *req2;
318
319 #if RF_DEBUG_QUEUE
320 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
321 printf("raid%d: do_dequeue\n", req->raidPtr->raidid);
322 }
323 #endif
324 if (req == queue->queue) {
325 DO_HEAD_DEQ(req2, queue);
326 RF_ASSERT(req2 == req);
327 } else
328 if (req == queue->qtail) {
329 DO_TAIL_DEQ(req2, queue);
330 RF_ASSERT(req2 == req);
331 } else {
332 /* dequeue from middle of list */
333 RF_ASSERT(req->next);
334 RF_ASSERT(req->prev);
335 queue->qlen--;
336 req->next->prev = req->prev;
337 req->prev->next = req->next;
338 req->next = req->prev = NULL;
339 }
340 }
341
342 RF_DiskQueueData_t *
rf_SstfDequeue(void * qptr)343 rf_SstfDequeue(void *qptr)
344 {
345 RF_DiskQueueData_t *req = NULL;
346 RF_Sstf_t *sstfq;
347
348 sstfq = (RF_Sstf_t *) qptr;
349
350 #if RF_DEBUG_QUEUE
351 if (rf_sstfDebug) {
352 RF_DiskQueue_t *dq;
353 dq = (RF_DiskQueue_t *) req->queue;
354 RF_ASSERT(QSUM(sstfq) == dq->queueLength);
355 printf("raid%d: sstf: Dequeue %d queues are %d,%d,%d\n",
356 req->raidPtr->raidid, dq->col,
357 sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen);
358 }
359 #endif
360 if (sstfq->left.queue == NULL) {
361 RF_ASSERT(sstfq->left.qlen == 0);
362 if (sstfq->right.queue == NULL) {
363 RF_ASSERT(sstfq->right.qlen == 0);
364 if (sstfq->lopri.queue == NULL) {
365 RF_ASSERT(sstfq->lopri.qlen == 0);
366 return (NULL);
367 }
368 #if RF_DEBUG_QUEUE
369 if (rf_sstfDebug) {
370 printf("raid%d: sstf: check for close lopri",
371 req->raidPtr->raidid);
372 }
373 #endif
374 req = closest_to_arm(&sstfq->lopri, sstfq->last_sector,
375 &sstfq->dir, sstfq->allow_reverse);
376 #if RF_DEBUG_QUEUE
377 if (rf_sstfDebug) {
378 printf("raid%d: sstf: closest_to_arm said %lx",
379 req->raidPtr->raidid, (long) req);
380 }
381 #endif
382 if (req == NULL)
383 return (NULL);
384 do_dequeue(&sstfq->lopri, req);
385 } else {
386 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->right);
387 }
388 } else {
389 if (sstfq->right.queue == NULL) {
390 RF_ASSERT(sstfq->right.qlen == 0);
391 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->left);
392 } else {
393 if (SNUM_DIFF(sstfq->last_sector, sstfq->right.queue->sectorOffset)
394 < SNUM_DIFF(sstfq->last_sector, sstfq->left.qtail->sectorOffset)) {
395 DO_HEAD_DEQ(req, &sstfq->right);
396 } else {
397 DO_TAIL_DEQ(req, &sstfq->left);
398 }
399 }
400 }
401 RF_ASSERT(req);
402 sstfq->last_sector = req->sectorOffset;
403 return (req);
404 }
405
406 RF_DiskQueueData_t *
rf_ScanDequeue(void * qptr)407 rf_ScanDequeue(void *qptr)
408 {
409 RF_DiskQueueData_t *req = NULL;
410 RF_Sstf_t *scanq;
411
412 scanq = (RF_Sstf_t *) qptr;
413
414 #if RF_DEBUG_QUEUE
415 if (rf_scanDebug) {
416 RF_DiskQueue_t *dq;
417 dq = (RF_DiskQueue_t *) req->queue;
418 RF_ASSERT(QSUM(scanq) == dq->queueLength);
419 printf("raid%d: scan: Dequeue %d queues are %d,%d,%d\n",
420 req->raidPtr->raidid, dq->col,
421 scanq->left.qlen, scanq->right.qlen, scanq->lopri.qlen);
422 }
423 #endif
424 if (scanq->left.queue == NULL) {
425 RF_ASSERT(scanq->left.qlen == 0);
426 if (scanq->right.queue == NULL) {
427 RF_ASSERT(scanq->right.qlen == 0);
428 if (scanq->lopri.queue == NULL) {
429 RF_ASSERT(scanq->lopri.qlen == 0);
430 return (NULL);
431 }
432 req = closest_to_arm(&scanq->lopri, scanq->last_sector,
433 &scanq->dir, scanq->allow_reverse);
434 if (req == NULL)
435 return (NULL);
436 do_dequeue(&scanq->lopri, req);
437 } else {
438 scanq->dir = DIR_RIGHT;
439 DO_HEAD_DEQ(req, &scanq->right);
440 }
441 } else
442 if (scanq->right.queue == NULL) {
443 RF_ASSERT(scanq->right.qlen == 0);
444 RF_ASSERT(scanq->left.queue);
445 scanq->dir = DIR_LEFT;
446 DO_TAIL_DEQ(req, &scanq->left);
447 } else {
448 RF_ASSERT(scanq->right.queue);
449 RF_ASSERT(scanq->left.queue);
450 if (scanq->dir == DIR_RIGHT) {
451 DO_HEAD_DEQ(req, &scanq->right);
452 } else {
453 DO_TAIL_DEQ(req, &scanq->left);
454 }
455 }
456 RF_ASSERT(req);
457 scanq->last_sector = req->sectorOffset;
458 return (req);
459 }
460
461 RF_DiskQueueData_t *
rf_CscanDequeue(void * qptr)462 rf_CscanDequeue(void *qptr)
463 {
464 RF_DiskQueueData_t *req = NULL;
465 RF_Sstf_t *cscanq;
466
467 cscanq = (RF_Sstf_t *) qptr;
468
469 RF_ASSERT(cscanq->dir == DIR_RIGHT);
470 #if RF_DEBUG_QUEUE
471 if (rf_cscanDebug) {
472 RF_DiskQueue_t *dq;
473 dq = (RF_DiskQueue_t *) req->queue;
474 RF_ASSERT(QSUM(cscanq) == dq->queueLength);
475 printf("raid%d: scan: Dequeue %d queues are %d,%d,%d\n",
476 req->raidPtr->raidid, dq->col,
477 cscanq->left.qlen, cscanq->right.qlen,
478 cscanq->lopri.qlen);
479 }
480 #endif
481 if (cscanq->right.queue) {
482 DO_HEAD_DEQ(req, &cscanq->right);
483 } else {
484 RF_ASSERT(cscanq->right.qlen == 0);
485 if (cscanq->left.queue == NULL) {
486 RF_ASSERT(cscanq->left.qlen == 0);
487 if (cscanq->lopri.queue == NULL) {
488 RF_ASSERT(cscanq->lopri.qlen == 0);
489 return (NULL);
490 }
491 req = closest_to_arm(&cscanq->lopri, cscanq->last_sector,
492 &cscanq->dir, cscanq->allow_reverse);
493 if (req == NULL)
494 return (NULL);
495 do_dequeue(&cscanq->lopri, req);
496 } else {
497 /*
498 * There's I/Os to the left of the arm. Swing
499 * on back (swap queues).
500 */
501 cscanq->right = cscanq->left;
502 cscanq->left.qlen = 0;
503 cscanq->left.queue = cscanq->left.qtail = NULL;
504 DO_HEAD_DEQ(req, &cscanq->right);
505 }
506 }
507 RF_ASSERT(req);
508 cscanq->last_sector = req->sectorOffset;
509 return (req);
510 }
511
512 int
rf_SstfPromote(void * qptr,RF_StripeNum_t parityStripeID,RF_ReconUnitNum_t which_ru)513 rf_SstfPromote(void *qptr, RF_StripeNum_t parityStripeID, RF_ReconUnitNum_t which_ru)
514 {
515 RF_DiskQueueData_t *r, *next;
516 RF_Sstf_t *sstfq;
517 int n;
518
519 sstfq = (RF_Sstf_t *) qptr;
520
521 n = 0;
522 for (r = sstfq->lopri.queue; r; r = next) {
523 next = r->next;
524 #if RF_DEBUG_QUEUE
525 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
526 printf("raid%d: check promote %lx\n",
527 r->raidPtr->raidid, (long) r);
528 }
529 #endif
530 if ((r->parityStripeID == parityStripeID)
531 && (r->which_ru == which_ru)) {
532 do_dequeue(&sstfq->lopri, r);
533 rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY);
534 n++;
535 }
536 }
537 #if RF_DEBUG_QUEUE
538 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) {
539 printf("raid%d: promoted %d matching I/Os queues are %d,%d,%d\n",
540 r->raidPtr->raidid, n, sstfq->left.qlen,
541 sstfq->right.qlen, sstfq->lopri.qlen);
542 }
543 #endif
544 return (n);
545 }
546