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