1 /* $NetBSD: rf_sstf.c,v 1.6 2001/01/27 20:18:55 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 "rf_alloclist.h" 36 #include "rf_stripelocks.h" 37 #include "rf_layout.h" 38 #include "rf_diskqueue.h" 39 #include "rf_sstf.h" 40 #include "rf_debugMem.h" 41 #include "rf_general.h" 42 #include "rf_options.h" 43 #include "rf_raid.h" 44 #include "rf_types.h" 45 46 #define DIR_LEFT 1 47 #define DIR_RIGHT 2 48 #define DIR_EITHER 3 49 50 #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_))) 51 52 #define QSUM(_sstfq_) (((_sstfq_)->lopri.qlen)+((_sstfq_)->left.qlen)+((_sstfq_)->right.qlen)) 53 54 55 static void 56 do_sstf_ord_q(RF_DiskQueueData_t **, 57 RF_DiskQueueData_t **, 58 RF_DiskQueueData_t *); 59 60 static RF_DiskQueueData_t * 61 closest_to_arm(RF_SstfQ_t *, 62 RF_SectorNum_t, 63 int *, 64 int); 65 static void do_dequeue(RF_SstfQ_t *, RF_DiskQueueData_t *); 66 67 68 static void 69 do_sstf_ord_q(queuep, tailp, req) 70 RF_DiskQueueData_t **queuep; 71 RF_DiskQueueData_t **tailp; 72 RF_DiskQueueData_t *req; 73 { 74 RF_DiskQueueData_t *r, *s; 75 76 if (*queuep == NULL) { 77 *queuep = req; 78 *tailp = req; 79 req->next = NULL; 80 req->prev = NULL; 81 return; 82 } 83 if (req->sectorOffset <= (*queuep)->sectorOffset) { 84 req->next = *queuep; 85 req->prev = NULL; 86 (*queuep)->prev = req; 87 *queuep = req; 88 return; 89 } 90 if (req->sectorOffset > (*tailp)->sectorOffset) { 91 /* optimization */ 92 r = NULL; 93 s = *tailp; 94 goto q_at_end; 95 } 96 for (s = NULL, r = *queuep; r; s = r, r = r->next) { 97 if (r->sectorOffset >= req->sectorOffset) { 98 /* insert after s, before r */ 99 RF_ASSERT(s); 100 req->next = r; 101 r->prev = req; 102 s->next = req; 103 req->prev = s; 104 return; 105 } 106 } 107 q_at_end: 108 /* insert after s, at end of queue */ 109 RF_ASSERT(r == NULL); 110 RF_ASSERT(s); 111 RF_ASSERT(s == (*tailp)); 112 req->next = NULL; 113 req->prev = s; 114 s->next = req; 115 *tailp = req; 116 } 117 /* for removing from head-of-queue */ 118 #define DO_HEAD_DEQ(_r_,_q_) { \ 119 _r_ = (_q_)->queue; \ 120 RF_ASSERT((_r_) != NULL); \ 121 (_q_)->queue = (_r_)->next; \ 122 (_q_)->qlen--; \ 123 if ((_q_)->qlen == 0) { \ 124 RF_ASSERT((_r_) == (_q_)->qtail); \ 125 RF_ASSERT((_q_)->queue == NULL); \ 126 (_q_)->qtail = NULL; \ 127 } \ 128 else { \ 129 RF_ASSERT((_q_)->queue->prev == (_r_)); \ 130 (_q_)->queue->prev = NULL; \ 131 } \ 132 } 133 134 /* for removing from end-of-queue */ 135 #define DO_TAIL_DEQ(_r_,_q_) { \ 136 _r_ = (_q_)->qtail; \ 137 RF_ASSERT((_r_) != NULL); \ 138 (_q_)->qtail = (_r_)->prev; \ 139 (_q_)->qlen--; \ 140 if ((_q_)->qlen == 0) { \ 141 RF_ASSERT((_r_) == (_q_)->queue); \ 142 RF_ASSERT((_q_)->qtail == NULL); \ 143 (_q_)->queue = NULL; \ 144 } \ 145 else { \ 146 RF_ASSERT((_q_)->qtail->next == (_r_)); \ 147 (_q_)->qtail->next = NULL; \ 148 } \ 149 } 150 151 #define DO_BEST_DEQ(_l_,_r_,_q_) { \ 152 if (SNUM_DIFF((_q_)->queue->sectorOffset,_l_) \ 153 < SNUM_DIFF((_q_)->qtail->sectorOffset,_l_)) \ 154 { \ 155 DO_HEAD_DEQ(_r_,_q_); \ 156 } \ 157 else { \ 158 DO_TAIL_DEQ(_r_,_q_); \ 159 } \ 160 } 161 162 static RF_DiskQueueData_t * 163 closest_to_arm(queue, arm_pos, dir, allow_reverse) 164 RF_SstfQ_t *queue; 165 RF_SectorNum_t arm_pos; 166 int *dir; 167 int allow_reverse; 168 { 169 RF_SectorNum_t best_pos_l = 0, this_pos_l = 0, last_pos = 0; 170 RF_SectorNum_t best_pos_r = 0, this_pos_r = 0; 171 RF_DiskQueueData_t *r, *best_l, *best_r; 172 173 best_r = best_l = NULL; 174 for (r = queue->queue; r; r = r->next) { 175 if (r->sectorOffset < arm_pos) { 176 if (best_l == NULL) { 177 best_l = r; 178 last_pos = best_pos_l = this_pos_l; 179 } else { 180 this_pos_l = arm_pos - r->sectorOffset; 181 if (this_pos_l < best_pos_l) { 182 best_l = r; 183 last_pos = best_pos_l = this_pos_l; 184 } else { 185 last_pos = this_pos_l; 186 } 187 } 188 } else { 189 if (best_r == NULL) { 190 best_r = r; 191 last_pos = best_pos_r = this_pos_r; 192 } else { 193 this_pos_r = r->sectorOffset - arm_pos; 194 if (this_pos_r < best_pos_r) { 195 best_r = r; 196 last_pos = best_pos_r = this_pos_r; 197 } else { 198 last_pos = this_pos_r; 199 } 200 if (this_pos_r > last_pos) { 201 /* getting farther away */ 202 break; 203 } 204 } 205 } 206 } 207 if ((best_r == NULL) && (best_l == NULL)) 208 return (NULL); 209 if ((*dir == DIR_RIGHT) && best_r) 210 return (best_r); 211 if ((*dir == DIR_LEFT) && best_l) 212 return (best_l); 213 if (*dir == DIR_EITHER) { 214 if (best_l == NULL) 215 return (best_r); 216 if (best_r == NULL) 217 return (best_l); 218 if (best_pos_r < best_pos_l) 219 return (best_r); 220 else 221 return (best_l); 222 } 223 /* 224 * Nothing in the direction we want to go. Reverse or 225 * reset the arm. We know we have an I/O in the other 226 * direction. 227 */ 228 if (allow_reverse) { 229 if (*dir == DIR_RIGHT) { 230 *dir = DIR_LEFT; 231 return (best_l); 232 } else { 233 *dir = DIR_RIGHT; 234 return (best_r); 235 } 236 } 237 /* 238 * Reset (beginning of queue). 239 */ 240 RF_ASSERT(*dir == DIR_RIGHT); 241 return (queue->queue); 242 } 243 244 void * 245 rf_SstfCreate(sect_per_disk, cl_list, listp) 246 RF_SectorCount_t sect_per_disk; 247 RF_AllocListElem_t *cl_list; 248 RF_ShutdownList_t **listp; 249 { 250 RF_Sstf_t *sstfq; 251 252 RF_CallocAndAdd(sstfq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list); 253 sstfq->dir = DIR_EITHER; 254 sstfq->allow_reverse = 1; 255 return ((void *) sstfq); 256 } 257 258 void * 259 rf_ScanCreate(sect_per_disk, cl_list, listp) 260 RF_SectorCount_t sect_per_disk; 261 RF_AllocListElem_t *cl_list; 262 RF_ShutdownList_t **listp; 263 { 264 RF_Sstf_t *scanq; 265 266 RF_CallocAndAdd(scanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list); 267 scanq->dir = DIR_RIGHT; 268 scanq->allow_reverse = 1; 269 return ((void *) scanq); 270 } 271 272 void * 273 rf_CscanCreate(sect_per_disk, cl_list, listp) 274 RF_SectorCount_t sect_per_disk; 275 RF_AllocListElem_t *cl_list; 276 RF_ShutdownList_t **listp; 277 { 278 RF_Sstf_t *cscanq; 279 280 RF_CallocAndAdd(cscanq, 1, sizeof(RF_Sstf_t), (RF_Sstf_t *), cl_list); 281 cscanq->dir = DIR_RIGHT; 282 return ((void *) cscanq); 283 } 284 285 void 286 rf_SstfEnqueue(qptr, req, priority) 287 void *qptr; 288 RF_DiskQueueData_t *req; 289 int priority; 290 { 291 RF_Sstf_t *sstfq; 292 293 sstfq = (RF_Sstf_t *) qptr; 294 295 if (priority == RF_IO_LOW_PRIORITY) { 296 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) { 297 RF_DiskQueue_t *dq; 298 dq = (RF_DiskQueue_t *) req->queue; 299 printf("raid%d: ENQ lopri %d,%d queues are %d,%d,%d\n", 300 req->raidPtr->raidid, 301 dq->row, dq->col, 302 sstfq->left.qlen, sstfq->right.qlen, 303 sstfq->lopri.qlen); 304 } 305 do_sstf_ord_q(&sstfq->lopri.queue, &sstfq->lopri.qtail, req); 306 sstfq->lopri.qlen++; 307 } else { 308 if (req->sectorOffset < sstfq->last_sector) { 309 do_sstf_ord_q(&sstfq->left.queue, &sstfq->left.qtail, req); 310 sstfq->left.qlen++; 311 } else { 312 do_sstf_ord_q(&sstfq->right.queue, &sstfq->right.qtail, req); 313 sstfq->right.qlen++; 314 } 315 } 316 } 317 318 static void 319 do_dequeue(queue, req) 320 RF_SstfQ_t *queue; 321 RF_DiskQueueData_t *req; 322 { 323 RF_DiskQueueData_t *req2; 324 325 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) { 326 printf("raid%d: do_dequeue\n", req->raidPtr->raidid); 327 } 328 if (req == queue->queue) { 329 DO_HEAD_DEQ(req2, queue); 330 RF_ASSERT(req2 == req); 331 } else 332 if (req == queue->qtail) { 333 DO_TAIL_DEQ(req2, queue); 334 RF_ASSERT(req2 == req); 335 } else { 336 /* dequeue from middle of list */ 337 RF_ASSERT(req->next); 338 RF_ASSERT(req->prev); 339 queue->qlen--; 340 req->next->prev = req->prev; 341 req->prev->next = req->next; 342 req->next = req->prev = NULL; 343 } 344 } 345 346 RF_DiskQueueData_t * 347 rf_SstfDequeue(qptr) 348 void *qptr; 349 { 350 RF_DiskQueueData_t *req = NULL; 351 RF_Sstf_t *sstfq; 352 353 sstfq = (RF_Sstf_t *) qptr; 354 355 if (rf_sstfDebug) { 356 RF_DiskQueue_t *dq; 357 dq = (RF_DiskQueue_t *) req->queue; 358 RF_ASSERT(QSUM(sstfq) == dq->queueLength); 359 printf("raid%d: sstf: Dequeue %d,%d queues are %d,%d,%d\n", 360 req->raidPtr->raidid, dq->row, dq->col, 361 sstfq->left.qlen, sstfq->right.qlen, sstfq->lopri.qlen); 362 } 363 if (sstfq->left.queue == NULL) { 364 RF_ASSERT(sstfq->left.qlen == 0); 365 if (sstfq->right.queue == NULL) { 366 RF_ASSERT(sstfq->right.qlen == 0); 367 if (sstfq->lopri.queue == NULL) { 368 RF_ASSERT(sstfq->lopri.qlen == 0); 369 return (NULL); 370 } 371 if (rf_sstfDebug) { 372 printf("raid%d: sstf: check for close lopri", 373 req->raidPtr->raidid); 374 } 375 req = closest_to_arm(&sstfq->lopri, sstfq->last_sector, 376 &sstfq->dir, sstfq->allow_reverse); 377 if (rf_sstfDebug) { 378 printf("raid%d: sstf: closest_to_arm said %lx", 379 req->raidPtr->raidid, (long) req); 380 } 381 if (req == NULL) 382 return (NULL); 383 do_dequeue(&sstfq->lopri, req); 384 } else { 385 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->right); 386 } 387 } else { 388 if (sstfq->right.queue == NULL) { 389 RF_ASSERT(sstfq->right.qlen == 0); 390 DO_BEST_DEQ(sstfq->last_sector, req, &sstfq->left); 391 } else { 392 if (SNUM_DIFF(sstfq->last_sector, sstfq->right.queue->sectorOffset) 393 < SNUM_DIFF(sstfq->last_sector, sstfq->left.qtail->sectorOffset)) { 394 DO_HEAD_DEQ(req, &sstfq->right); 395 } else { 396 DO_TAIL_DEQ(req, &sstfq->left); 397 } 398 } 399 } 400 RF_ASSERT(req); 401 sstfq->last_sector = req->sectorOffset; 402 return (req); 403 } 404 405 RF_DiskQueueData_t * 406 rf_ScanDequeue(qptr) 407 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_scanDebug) { 415 RF_DiskQueue_t *dq; 416 dq = (RF_DiskQueue_t *) req->queue; 417 RF_ASSERT(QSUM(scanq) == dq->queueLength); 418 printf("raid%d: scan: Dequeue %d,%d queues are %d,%d,%d\n", 419 req->raidPtr->raidid, dq->row, dq->col, 420 scanq->left.qlen, scanq->right.qlen, scanq->lopri.qlen); 421 } 422 if (scanq->left.queue == NULL) { 423 RF_ASSERT(scanq->left.qlen == 0); 424 if (scanq->right.queue == NULL) { 425 RF_ASSERT(scanq->right.qlen == 0); 426 if (scanq->lopri.queue == NULL) { 427 RF_ASSERT(scanq->lopri.qlen == 0); 428 return (NULL); 429 } 430 req = closest_to_arm(&scanq->lopri, scanq->last_sector, 431 &scanq->dir, scanq->allow_reverse); 432 if (req == NULL) 433 return (NULL); 434 do_dequeue(&scanq->lopri, req); 435 } else { 436 scanq->dir = DIR_RIGHT; 437 DO_HEAD_DEQ(req, &scanq->right); 438 } 439 } else 440 if (scanq->right.queue == NULL) { 441 RF_ASSERT(scanq->right.qlen == 0); 442 RF_ASSERT(scanq->left.queue); 443 scanq->dir = DIR_LEFT; 444 DO_TAIL_DEQ(req, &scanq->left); 445 } else { 446 RF_ASSERT(scanq->right.queue); 447 RF_ASSERT(scanq->left.queue); 448 if (scanq->dir == DIR_RIGHT) { 449 DO_HEAD_DEQ(req, &scanq->right); 450 } else { 451 DO_TAIL_DEQ(req, &scanq->left); 452 } 453 } 454 RF_ASSERT(req); 455 scanq->last_sector = req->sectorOffset; 456 return (req); 457 } 458 459 RF_DiskQueueData_t * 460 rf_CscanDequeue(qptr) 461 void *qptr; 462 { 463 RF_DiskQueueData_t *req = NULL; 464 RF_Sstf_t *cscanq; 465 466 cscanq = (RF_Sstf_t *) qptr; 467 468 RF_ASSERT(cscanq->dir == DIR_RIGHT); 469 if (rf_cscanDebug) { 470 RF_DiskQueue_t *dq; 471 dq = (RF_DiskQueue_t *) req->queue; 472 RF_ASSERT(QSUM(cscanq) == dq->queueLength); 473 printf("raid%d: scan: Dequeue %d,%d queues are %d,%d,%d\n", 474 req->raidPtr->raidid, dq->row, dq->col, 475 cscanq->left.qlen, cscanq->right.qlen, 476 cscanq->lopri.qlen); 477 } 478 if (cscanq->right.queue) { 479 DO_HEAD_DEQ(req, &cscanq->right); 480 } else { 481 RF_ASSERT(cscanq->right.qlen == 0); 482 if (cscanq->left.queue == NULL) { 483 RF_ASSERT(cscanq->left.qlen == 0); 484 if (cscanq->lopri.queue == NULL) { 485 RF_ASSERT(cscanq->lopri.qlen == 0); 486 return (NULL); 487 } 488 req = closest_to_arm(&cscanq->lopri, cscanq->last_sector, 489 &cscanq->dir, cscanq->allow_reverse); 490 if (req == NULL) 491 return (NULL); 492 do_dequeue(&cscanq->lopri, req); 493 } else { 494 /* 495 * There's I/Os to the left of the arm. Swing 496 * on back (swap queues). 497 */ 498 cscanq->right = cscanq->left; 499 cscanq->left.qlen = 0; 500 cscanq->left.queue = cscanq->left.qtail = NULL; 501 DO_HEAD_DEQ(req, &cscanq->right); 502 } 503 } 504 RF_ASSERT(req); 505 cscanq->last_sector = req->sectorOffset; 506 return (req); 507 } 508 509 RF_DiskQueueData_t * 510 rf_SstfPeek(qptr) 511 void *qptr; 512 { 513 RF_DiskQueueData_t *req; 514 RF_Sstf_t *sstfq; 515 516 sstfq = (RF_Sstf_t *) qptr; 517 518 if ((sstfq->left.queue == NULL) && (sstfq->right.queue == NULL)) { 519 req = closest_to_arm(&sstfq->lopri, sstfq->last_sector, &sstfq->dir, 520 sstfq->allow_reverse); 521 } else { 522 if (sstfq->left.queue == NULL) 523 req = sstfq->right.queue; 524 else { 525 if (sstfq->right.queue == NULL) 526 req = sstfq->left.queue; 527 else { 528 if (SNUM_DIFF(sstfq->last_sector, sstfq->right.queue->sectorOffset) 529 < SNUM_DIFF(sstfq->last_sector, sstfq->left.qtail->sectorOffset)) { 530 req = sstfq->right.queue; 531 } else { 532 req = sstfq->left.qtail; 533 } 534 } 535 } 536 } 537 if (req == NULL) { 538 RF_ASSERT(QSUM(sstfq) == 0); 539 } 540 return (req); 541 } 542 543 RF_DiskQueueData_t * 544 rf_ScanPeek(qptr) 545 void *qptr; 546 { 547 RF_DiskQueueData_t *req; 548 RF_Sstf_t *scanq; 549 int dir; 550 551 scanq = (RF_Sstf_t *) qptr; 552 dir = scanq->dir; 553 554 if (scanq->left.queue == NULL) { 555 RF_ASSERT(scanq->left.qlen == 0); 556 if (scanq->right.queue == NULL) { 557 RF_ASSERT(scanq->right.qlen == 0); 558 if (scanq->lopri.queue == NULL) { 559 RF_ASSERT(scanq->lopri.qlen == 0); 560 return (NULL); 561 } 562 req = closest_to_arm(&scanq->lopri, scanq->last_sector, 563 &dir, scanq->allow_reverse); 564 } else { 565 req = scanq->right.queue; 566 } 567 } else 568 if (scanq->right.queue == NULL) { 569 RF_ASSERT(scanq->right.qlen == 0); 570 RF_ASSERT(scanq->left.queue); 571 req = scanq->left.qtail; 572 } else { 573 RF_ASSERT(scanq->right.queue); 574 RF_ASSERT(scanq->left.queue); 575 if (scanq->dir == DIR_RIGHT) { 576 req = scanq->right.queue; 577 } else { 578 req = scanq->left.qtail; 579 } 580 } 581 if (req == NULL) { 582 RF_ASSERT(QSUM(scanq) == 0); 583 } 584 return (req); 585 } 586 587 RF_DiskQueueData_t * 588 rf_CscanPeek(qptr) 589 void *qptr; 590 { 591 RF_DiskQueueData_t *req; 592 RF_Sstf_t *cscanq; 593 594 cscanq = (RF_Sstf_t *) qptr; 595 596 RF_ASSERT(cscanq->dir == DIR_RIGHT); 597 if (cscanq->right.queue) { 598 req = cscanq->right.queue; 599 } else { 600 RF_ASSERT(cscanq->right.qlen == 0); 601 if (cscanq->left.queue == NULL) { 602 RF_ASSERT(cscanq->left.qlen == 0); 603 if (cscanq->lopri.queue == NULL) { 604 RF_ASSERT(cscanq->lopri.qlen == 0); 605 return (NULL); 606 } 607 req = closest_to_arm(&cscanq->lopri, cscanq->last_sector, 608 &cscanq->dir, cscanq->allow_reverse); 609 } else { 610 /* 611 * There's I/Os to the left of the arm. We'll end 612 * up swinging on back. 613 */ 614 req = cscanq->left.queue; 615 } 616 } 617 if (req == NULL) { 618 RF_ASSERT(QSUM(cscanq) == 0); 619 } 620 return (req); 621 } 622 623 int 624 rf_SstfPromote(qptr, parityStripeID, which_ru) 625 void *qptr; 626 RF_StripeNum_t parityStripeID; 627 RF_ReconUnitNum_t which_ru; 628 { 629 RF_DiskQueueData_t *r, *next; 630 RF_Sstf_t *sstfq; 631 int n; 632 633 sstfq = (RF_Sstf_t *) qptr; 634 635 n = 0; 636 for (r = sstfq->lopri.queue; r; r = next) { 637 next = r->next; 638 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) { 639 printf("raid%d: check promote %lx\n", 640 r->raidPtr->raidid, (long) r); 641 } 642 if ((r->parityStripeID == parityStripeID) 643 && (r->which_ru == which_ru)) { 644 do_dequeue(&sstfq->lopri, r); 645 rf_SstfEnqueue(qptr, r, RF_IO_NORMAL_PRIORITY); 646 n++; 647 } 648 } 649 if (rf_sstfDebug || rf_scanDebug || rf_cscanDebug) { 650 printf("raid%d: promoted %d matching I/Os queues are %d,%d,%d\n", 651 r->raidPtr->raidid, n, sstfq->left.qlen, 652 sstfq->right.qlen, sstfq->lopri.qlen); 653 } 654 return (n); 655 } 656