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 (at) 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 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 * 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 * 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 * 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 * 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 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 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 * 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 * 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 * 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 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
Indexes created Sat Sep 20 22:09:52 GMT 2025