1 /* $NetBSD: rf_dagutils.c,v 1.57 2019/10/10 03:43:59 christos Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Authors: Mark Holland, William V. Courtright II, 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 * rf_dagutils.c -- utility routines for manipulating dags 32 * 33 *****************************************************************************/ 34 35 #include <sys/cdefs.h> 36 __KERNEL_RCSID(0, "$NetBSD: rf_dagutils.c,v 1.57 2019/10/10 03:43:59 christos Exp $"); 37 38 #include <dev/raidframe/raidframevar.h> 39 40 #include "rf_archs.h" 41 #include "rf_threadstuff.h" 42 #include "rf_raid.h" 43 #include "rf_dag.h" 44 #include "rf_dagutils.h" 45 #include "rf_dagfuncs.h" 46 #include "rf_general.h" 47 #include "rf_map.h" 48 #include "rf_shutdown.h" 49 50 #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_))) 51 52 const RF_RedFuncs_t rf_xorFuncs = { 53 rf_RegularXorFunc, "Reg Xr", 54 rf_SimpleXorFunc, "Simple Xr"}; 55 56 const RF_RedFuncs_t rf_xorRecoveryFuncs = { 57 rf_RecoveryXorFunc, "Recovery Xr", 58 rf_RecoveryXorFunc, "Recovery Xr"}; 59 60 #if RF_DEBUG_VALIDATE_DAG 61 static void rf_RecurPrintDAG(RF_DagNode_t *, int, int); 62 static void rf_PrintDAG(RF_DagHeader_t *); 63 static int rf_ValidateBranch(RF_DagNode_t *, int *, int *, 64 RF_DagNode_t **, int); 65 static void rf_ValidateBranchVisitedBits(RF_DagNode_t *, int, int); 66 static void rf_ValidateVisitedBits(RF_DagHeader_t *); 67 #endif /* RF_DEBUG_VALIDATE_DAG */ 68 69 /* The maximum number of nodes in a DAG is bounded by 70 71 (2 * raidPtr->Layout->numDataCol) + (1 * layoutPtr->numParityCol) + 72 (1 * 2 * layoutPtr->numParityCol) + 3 73 74 which is: 2*RF_MAXCOL+1*2+1*2*2+3 75 76 For RF_MAXCOL of 40, this works out to 89. We use this value to provide an estimate 77 on the maximum size needed for RF_DAGPCACHE_SIZE. For RF_MAXCOL of 40, this structure 78 would be 534 bytes. Too much to have on-hand in a RF_DagNode_t, but should be ok to 79 have a few kicking around. 80 */ 81 #define RF_DAGPCACHE_SIZE ((2*RF_MAXCOL+1*2+1*2*2+3) *(RF_MAX(sizeof(RF_DagParam_t), sizeof(RF_DagNode_t *)))) 82 83 84 /****************************************************************************** 85 * 86 * InitNode - initialize a dag node 87 * 88 * the size of the propList array is always the same as that of the 89 * successors array. 90 * 91 *****************************************************************************/ 92 void 93 rf_InitNode(RF_DagNode_t *node, RF_NodeStatus_t initstatus, int commit, 94 void (*doFunc) (RF_DagNode_t *node), 95 void (*undoFunc) (RF_DagNode_t *node), 96 void (*wakeFunc) (void *node, int status), 97 int nSucc, int nAnte, int nParam, int nResult, 98 RF_DagHeader_t *hdr, const char *name, RF_AllocListElem_t *alist) 99 { 100 void **ptrs; 101 int nptrs; 102 103 if (nAnte > RF_MAX_ANTECEDENTS) 104 RF_PANIC(); 105 node->status = initstatus; 106 node->commitNode = commit; 107 node->doFunc = doFunc; 108 node->undoFunc = undoFunc; 109 node->wakeFunc = wakeFunc; 110 node->numParams = nParam; 111 node->numResults = nResult; 112 node->numAntecedents = nAnte; 113 node->numAntDone = 0; 114 node->next = NULL; 115 /* node->list_next = NULL */ /* Don't touch this here! 116 It may already be 117 in use by the caller! */ 118 node->numSuccedents = nSucc; 119 node->name = name; 120 node->dagHdr = hdr; 121 node->big_dag_ptrs = NULL; 122 node->big_dag_params = NULL; 123 node->visited = 0; 124 125 /* allocate all the pointers with one call to malloc */ 126 nptrs = nSucc + nAnte + nResult + nSucc; 127 128 if (nptrs <= RF_DAG_PTRCACHESIZE) { 129 /* 130 * The dag_ptrs field of the node is basically some scribble 131 * space to be used here. We could get rid of it, and always 132 * allocate the range of pointers, but that's expensive. So, 133 * we pick a "common case" size for the pointer cache. Hopefully, 134 * we'll find that: 135 * (1) Generally, nptrs doesn't exceed RF_DAG_PTRCACHESIZE by 136 * only a little bit (least efficient case) 137 * (2) Generally, ntprs isn't a lot less than RF_DAG_PTRCACHESIZE 138 * (wasted memory) 139 */ 140 ptrs = (void **) node->dag_ptrs; 141 } else if (nptrs <= (RF_DAGPCACHE_SIZE / sizeof(RF_DagNode_t *))) { 142 node->big_dag_ptrs = rf_AllocDAGPCache(); 143 ptrs = (void **) node->big_dag_ptrs; 144 } else { 145 ptrs = RF_MallocAndAdd(nptrs * sizeof(*ptrs), alist); 146 } 147 node->succedents = (nSucc) ? (RF_DagNode_t **) ptrs : NULL; 148 node->antecedents = (nAnte) ? (RF_DagNode_t **) (ptrs + nSucc) : NULL; 149 node->results = (nResult) ? (void **) (ptrs + nSucc + nAnte) : NULL; 150 node->propList = (nSucc) ? (RF_PropHeader_t **) (ptrs + nSucc + nAnte + nResult) : NULL; 151 152 if (nParam) { 153 if (nParam <= RF_DAG_PARAMCACHESIZE) { 154 node->params = (RF_DagParam_t *) node->dag_params; 155 } else if (nParam <= (RF_DAGPCACHE_SIZE / sizeof(RF_DagParam_t))) { 156 node->big_dag_params = rf_AllocDAGPCache(); 157 node->params = node->big_dag_params; 158 } else { 159 node->params = RF_MallocAndAdd( 160 nParam * sizeof(*node->params), alist); 161 } 162 } else { 163 node->params = NULL; 164 } 165 } 166 167 168 169 /****************************************************************************** 170 * 171 * allocation and deallocation routines 172 * 173 *****************************************************************************/ 174 175 void 176 rf_FreeDAG(RF_DagHeader_t *dag_h) 177 { 178 RF_AccessStripeMapHeader_t *asmap, *t_asmap; 179 RF_PhysDiskAddr_t *pda; 180 RF_DagNode_t *tmpnode; 181 RF_DagHeader_t *nextDag; 182 183 while (dag_h) { 184 nextDag = dag_h->next; 185 rf_FreeAllocList(dag_h->allocList); 186 for (asmap = dag_h->asmList; asmap;) { 187 t_asmap = asmap; 188 asmap = asmap->next; 189 rf_FreeAccessStripeMap(t_asmap); 190 } 191 while (dag_h->pda_cleanup_list) { 192 pda = dag_h->pda_cleanup_list; 193 dag_h->pda_cleanup_list = dag_h->pda_cleanup_list->next; 194 rf_FreePhysDiskAddr(pda); 195 } 196 while (dag_h->nodes) { 197 tmpnode = dag_h->nodes; 198 dag_h->nodes = dag_h->nodes->list_next; 199 rf_FreeDAGNode(tmpnode); 200 } 201 rf_FreeDAGHeader(dag_h); 202 dag_h = nextDag; 203 } 204 } 205 206 #define RF_MAX_FREE_DAGH 128 207 #define RF_MIN_FREE_DAGH 32 208 209 #define RF_MAX_FREE_DAGNODE 512 /* XXX Tune this... */ 210 #define RF_MIN_FREE_DAGNODE 128 /* XXX Tune this... */ 211 212 #define RF_MAX_FREE_DAGLIST 128 213 #define RF_MIN_FREE_DAGLIST 32 214 215 #define RF_MAX_FREE_DAGPCACHE 128 216 #define RF_MIN_FREE_DAGPCACHE 8 217 218 #define RF_MAX_FREE_FUNCLIST 128 219 #define RF_MIN_FREE_FUNCLIST 32 220 221 #define RF_MAX_FREE_BUFFERS 128 222 #define RF_MIN_FREE_BUFFERS 32 223 224 static void rf_ShutdownDAGs(void *); 225 static void 226 rf_ShutdownDAGs(void *ignored) 227 { 228 pool_destroy(&rf_pools.dagh); 229 pool_destroy(&rf_pools.dagnode); 230 pool_destroy(&rf_pools.daglist); 231 pool_destroy(&rf_pools.dagpcache); 232 pool_destroy(&rf_pools.funclist); 233 } 234 235 int 236 rf_ConfigureDAGs(RF_ShutdownList_t **listp) 237 { 238 239 rf_pool_init(&rf_pools.dagnode, sizeof(RF_DagNode_t), 240 "rf_dagnode_pl", RF_MIN_FREE_DAGNODE, RF_MAX_FREE_DAGNODE); 241 rf_pool_init(&rf_pools.dagh, sizeof(RF_DagHeader_t), 242 "rf_dagh_pl", RF_MIN_FREE_DAGH, RF_MAX_FREE_DAGH); 243 rf_pool_init(&rf_pools.daglist, sizeof(RF_DagList_t), 244 "rf_daglist_pl", RF_MIN_FREE_DAGLIST, RF_MAX_FREE_DAGLIST); 245 rf_pool_init(&rf_pools.dagpcache, RF_DAGPCACHE_SIZE, 246 "rf_dagpcache_pl", RF_MIN_FREE_DAGPCACHE, RF_MAX_FREE_DAGPCACHE); 247 rf_pool_init(&rf_pools.funclist, sizeof(RF_FuncList_t), 248 "rf_funclist_pl", RF_MIN_FREE_FUNCLIST, RF_MAX_FREE_FUNCLIST); 249 rf_ShutdownCreate(listp, rf_ShutdownDAGs, NULL); 250 251 return (0); 252 } 253 254 RF_DagHeader_t * 255 rf_AllocDAGHeader(void) 256 { 257 return pool_get(&rf_pools.dagh, PR_WAITOK | PR_ZERO); 258 } 259 260 void 261 rf_FreeDAGHeader(RF_DagHeader_t * dh) 262 { 263 pool_put(&rf_pools.dagh, dh); 264 } 265 266 RF_DagNode_t * 267 rf_AllocDAGNode(void) 268 { 269 return pool_get(&rf_pools.dagnode, PR_WAITOK | PR_ZERO); 270 } 271 272 void 273 rf_FreeDAGNode(RF_DagNode_t *node) 274 { 275 if (node->big_dag_ptrs) { 276 rf_FreeDAGPCache(node->big_dag_ptrs); 277 } 278 if (node->big_dag_params) { 279 rf_FreeDAGPCache(node->big_dag_params); 280 } 281 pool_put(&rf_pools.dagnode, node); 282 } 283 284 RF_DagList_t * 285 rf_AllocDAGList(void) 286 { 287 return pool_get(&rf_pools.daglist, PR_WAITOK | PR_ZERO); 288 } 289 290 void 291 rf_FreeDAGList(RF_DagList_t *dagList) 292 { 293 pool_put(&rf_pools.daglist, dagList); 294 } 295 296 void * 297 rf_AllocDAGPCache(void) 298 { 299 return pool_get(&rf_pools.dagpcache, PR_WAITOK | PR_ZERO); 300 } 301 302 void 303 rf_FreeDAGPCache(void *p) 304 { 305 pool_put(&rf_pools.dagpcache, p); 306 } 307 308 RF_FuncList_t * 309 rf_AllocFuncList(void) 310 { 311 return pool_get(&rf_pools.funclist, PR_WAITOK | PR_ZERO); 312 } 313 314 void 315 rf_FreeFuncList(RF_FuncList_t *funcList) 316 { 317 pool_put(&rf_pools.funclist, funcList); 318 } 319 320 /* allocates a stripe buffer -- a buffer large enough to hold all the data 321 in an entire stripe. 322 */ 323 324 void * 325 rf_AllocStripeBuffer(RF_Raid_t *raidPtr, RF_DagHeader_t *dag_h, 326 int size) 327 { 328 RF_VoidPointerListElem_t *vple; 329 void *p; 330 331 RF_ASSERT((size <= (raidPtr->numCol * (raidPtr->Layout.sectorsPerStripeUnit << 332 raidPtr->logBytesPerSector)))); 333 334 p = malloc( raidPtr->numCol * (raidPtr->Layout.sectorsPerStripeUnit << 335 raidPtr->logBytesPerSector), 336 M_RAIDFRAME, M_NOWAIT); 337 if (!p) { 338 rf_lock_mutex2(raidPtr->mutex); 339 if (raidPtr->stripebuf_count > 0) { 340 vple = raidPtr->stripebuf; 341 raidPtr->stripebuf = vple->next; 342 p = vple->p; 343 rf_FreeVPListElem(vple); 344 raidPtr->stripebuf_count--; 345 } else { 346 #ifdef DIAGNOSTIC 347 printf("raid%d: Help! Out of emergency full-stripe buffers!\n", raidPtr->raidid); 348 #endif 349 } 350 rf_unlock_mutex2(raidPtr->mutex); 351 if (!p) { 352 /* We didn't get a buffer... not much we can do other than wait, 353 and hope that someone frees up memory for us.. */ 354 p = malloc( raidPtr->numCol * (raidPtr->Layout.sectorsPerStripeUnit << 355 raidPtr->logBytesPerSector), M_RAIDFRAME, M_WAITOK); 356 } 357 } 358 memset(p, 0, raidPtr->numCol * (raidPtr->Layout.sectorsPerStripeUnit << raidPtr->logBytesPerSector)); 359 360 vple = rf_AllocVPListElem(); 361 vple->p = p; 362 vple->next = dag_h->desc->stripebufs; 363 dag_h->desc->stripebufs = vple; 364 365 return (p); 366 } 367 368 369 void 370 rf_FreeStripeBuffer(RF_Raid_t *raidPtr, RF_VoidPointerListElem_t *vple) 371 { 372 rf_lock_mutex2(raidPtr->mutex); 373 if (raidPtr->stripebuf_count < raidPtr->numEmergencyStripeBuffers) { 374 /* just tack it in */ 375 vple->next = raidPtr->stripebuf; 376 raidPtr->stripebuf = vple; 377 raidPtr->stripebuf_count++; 378 } else { 379 free(vple->p, M_RAIDFRAME); 380 rf_FreeVPListElem(vple); 381 } 382 rf_unlock_mutex2(raidPtr->mutex); 383 } 384 385 /* allocates a buffer big enough to hold the data described by the 386 caller (ie. the data of the associated PDA). Glue this buffer 387 into our dag_h cleanup structure. */ 388 389 void * 390 rf_AllocBuffer(RF_Raid_t *raidPtr, RF_DagHeader_t *dag_h, int size) 391 { 392 RF_VoidPointerListElem_t *vple; 393 void *p; 394 395 p = rf_AllocIOBuffer(raidPtr, size); 396 vple = rf_AllocVPListElem(); 397 vple->p = p; 398 vple->next = dag_h->desc->iobufs; 399 dag_h->desc->iobufs = vple; 400 401 return (p); 402 } 403 404 void * 405 rf_AllocIOBuffer(RF_Raid_t *raidPtr, int size) 406 { 407 RF_VoidPointerListElem_t *vple; 408 void *p; 409 410 RF_ASSERT((size <= (raidPtr->Layout.sectorsPerStripeUnit << 411 raidPtr->logBytesPerSector))); 412 413 p = malloc( raidPtr->Layout.sectorsPerStripeUnit << 414 raidPtr->logBytesPerSector, 415 M_RAIDFRAME, M_NOWAIT); 416 if (!p) { 417 rf_lock_mutex2(raidPtr->mutex); 418 if (raidPtr->iobuf_count > 0) { 419 vple = raidPtr->iobuf; 420 raidPtr->iobuf = vple->next; 421 p = vple->p; 422 rf_FreeVPListElem(vple); 423 raidPtr->iobuf_count--; 424 } else { 425 #ifdef DIAGNOSTIC 426 printf("raid%d: Help! Out of emergency buffers!\n", raidPtr->raidid); 427 #endif 428 } 429 rf_unlock_mutex2(raidPtr->mutex); 430 if (!p) { 431 /* We didn't get a buffer... not much we can do other than wait, 432 and hope that someone frees up memory for us.. */ 433 p = malloc( raidPtr->Layout.sectorsPerStripeUnit << 434 raidPtr->logBytesPerSector, 435 M_RAIDFRAME, M_WAITOK); 436 } 437 } 438 memset(p, 0, raidPtr->Layout.sectorsPerStripeUnit << raidPtr->logBytesPerSector); 439 return (p); 440 } 441 442 void 443 rf_FreeIOBuffer(RF_Raid_t *raidPtr, RF_VoidPointerListElem_t *vple) 444 { 445 rf_lock_mutex2(raidPtr->mutex); 446 if (raidPtr->iobuf_count < raidPtr->numEmergencyBuffers) { 447 /* just tack it in */ 448 vple->next = raidPtr->iobuf; 449 raidPtr->iobuf = vple; 450 raidPtr->iobuf_count++; 451 } else { 452 free(vple->p, M_RAIDFRAME); 453 rf_FreeVPListElem(vple); 454 } 455 rf_unlock_mutex2(raidPtr->mutex); 456 } 457 458 459 460 #if RF_DEBUG_VALIDATE_DAG 461 /****************************************************************************** 462 * 463 * debug routines 464 * 465 *****************************************************************************/ 466 467 char * 468 rf_NodeStatusString(RF_DagNode_t *node) 469 { 470 switch (node->status) { 471 case rf_wait: 472 return ("wait"); 473 case rf_fired: 474 return ("fired"); 475 case rf_good: 476 return ("good"); 477 case rf_bad: 478 return ("bad"); 479 default: 480 return ("?"); 481 } 482 } 483 484 void 485 rf_PrintNodeInfoString(RF_DagNode_t *node) 486 { 487 RF_PhysDiskAddr_t *pda; 488 int (*df) (RF_DagNode_t *) = node->doFunc; 489 int i, lk, unlk; 490 void *bufPtr; 491 492 if ((df == rf_DiskReadFunc) || (df == rf_DiskWriteFunc) 493 || (df == rf_DiskReadMirrorIdleFunc) 494 || (df == rf_DiskReadMirrorPartitionFunc)) { 495 pda = (RF_PhysDiskAddr_t *) node->params[0].p; 496 bufPtr = (void *) node->params[1].p; 497 lk = 0; 498 unlk = 0; 499 RF_ASSERT(!(lk && unlk)); 500 printf("c %d offs %ld nsect %d buf 0x%lx %s\n", pda->col, 501 (long) pda->startSector, (int) pda->numSector, (long) bufPtr, 502 (lk) ? "LOCK" : ((unlk) ? "UNLK" : " ")); 503 return; 504 } 505 if ((df == rf_SimpleXorFunc) || (df == rf_RegularXorFunc) 506 || (df == rf_RecoveryXorFunc)) { 507 printf("result buf 0x%lx\n", (long) node->results[0]); 508 for (i = 0; i < node->numParams - 1; i += 2) { 509 pda = (RF_PhysDiskAddr_t *) node->params[i].p; 510 bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p; 511 printf(" buf 0x%lx c%d offs %ld nsect %d\n", 512 (long) bufPtr, pda->col, 513 (long) pda->startSector, (int) pda->numSector); 514 } 515 return; 516 } 517 #if RF_INCLUDE_PARITYLOGGING > 0 518 if (df == rf_ParityLogOverwriteFunc || df == rf_ParityLogUpdateFunc) { 519 for (i = 0; i < node->numParams - 1; i += 2) { 520 pda = (RF_PhysDiskAddr_t *) node->params[i].p; 521 bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p; 522 printf(" c%d offs %ld nsect %d buf 0x%lx\n", 523 pda->col, (long) pda->startSector, 524 (int) pda->numSector, (long) bufPtr); 525 } 526 return; 527 } 528 #endif /* RF_INCLUDE_PARITYLOGGING > 0 */ 529 530 if ((df == rf_TerminateFunc) || (df == rf_NullNodeFunc)) { 531 printf("\n"); 532 return; 533 } 534 printf("?\n"); 535 } 536 #ifdef DEBUG 537 static void 538 rf_RecurPrintDAG(RF_DagNode_t *node, int depth, int unvisited) 539 { 540 char *anttype; 541 int i; 542 543 node->visited = (unvisited) ? 0 : 1; 544 printf("(%d) %d C%d %s: %s,s%d %d/%d,a%d/%d,p%d,r%d S{", depth, 545 node->nodeNum, node->commitNode, node->name, rf_NodeStatusString(node), 546 node->numSuccedents, node->numSuccFired, node->numSuccDone, 547 node->numAntecedents, node->numAntDone, node->numParams, node->numResults); 548 for (i = 0; i < node->numSuccedents; i++) { 549 printf("%d%s", node->succedents[i]->nodeNum, 550 ((i == node->numSuccedents - 1) ? "\0" : " ")); 551 } 552 printf("} A{"); 553 for (i = 0; i < node->numAntecedents; i++) { 554 switch (node->antType[i]) { 555 case rf_trueData: 556 anttype = "T"; 557 break; 558 case rf_antiData: 559 anttype = "A"; 560 break; 561 case rf_outputData: 562 anttype = "O"; 563 break; 564 case rf_control: 565 anttype = "C"; 566 break; 567 default: 568 anttype = "?"; 569 break; 570 } 571 printf("%d(%s)%s", node->antecedents[i]->nodeNum, anttype, (i == node->numAntecedents - 1) ? "\0" : " "); 572 } 573 printf("}; "); 574 rf_PrintNodeInfoString(node); 575 for (i = 0; i < node->numSuccedents; i++) { 576 if (node->succedents[i]->visited == unvisited) 577 rf_RecurPrintDAG(node->succedents[i], depth + 1, unvisited); 578 } 579 } 580 581 static void 582 rf_PrintDAG(RF_DagHeader_t *dag_h) 583 { 584 int unvisited, i; 585 char *status; 586 587 /* set dag status */ 588 switch (dag_h->status) { 589 case rf_enable: 590 status = "enable"; 591 break; 592 case rf_rollForward: 593 status = "rollForward"; 594 break; 595 case rf_rollBackward: 596 status = "rollBackward"; 597 break; 598 default: 599 status = "illegal!"; 600 break; 601 } 602 /* find out if visited bits are currently set or clear */ 603 unvisited = dag_h->succedents[0]->visited; 604 605 printf("DAG type: %s\n", dag_h->creator); 606 printf("format is (depth) num commit type: status,nSucc nSuccFired/nSuccDone,nAnte/nAnteDone,nParam,nResult S{x} A{x(type)}; info\n"); 607 printf("(0) %d Hdr: %s, s%d, (commit %d/%d) S{", dag_h->nodeNum, 608 status, dag_h->numSuccedents, dag_h->numCommitNodes, dag_h->numCommits); 609 for (i = 0; i < dag_h->numSuccedents; i++) { 610 printf("%d%s", dag_h->succedents[i]->nodeNum, 611 ((i == dag_h->numSuccedents - 1) ? "\0" : " ")); 612 } 613 printf("};\n"); 614 for (i = 0; i < dag_h->numSuccedents; i++) { 615 if (dag_h->succedents[i]->visited == unvisited) 616 rf_RecurPrintDAG(dag_h->succedents[i], 1, unvisited); 617 } 618 } 619 #endif 620 /* assigns node numbers */ 621 int 622 rf_AssignNodeNums(RF_DagHeader_t * dag_h) 623 { 624 int unvisited, i, nnum; 625 RF_DagNode_t *node; 626 627 nnum = 0; 628 unvisited = dag_h->succedents[0]->visited; 629 630 dag_h->nodeNum = nnum++; 631 for (i = 0; i < dag_h->numSuccedents; i++) { 632 node = dag_h->succedents[i]; 633 if (node->visited == unvisited) { 634 nnum = rf_RecurAssignNodeNums(dag_h->succedents[i], nnum, unvisited); 635 } 636 } 637 return (nnum); 638 } 639 640 int 641 rf_RecurAssignNodeNums(RF_DagNode_t *node, int num, int unvisited) 642 { 643 int i; 644 645 node->visited = (unvisited) ? 0 : 1; 646 647 node->nodeNum = num++; 648 for (i = 0; i < node->numSuccedents; i++) { 649 if (node->succedents[i]->visited == unvisited) { 650 num = rf_RecurAssignNodeNums(node->succedents[i], num, unvisited); 651 } 652 } 653 return (num); 654 } 655 /* set the header pointers in each node to "newptr" */ 656 void 657 rf_ResetDAGHeaderPointers(RF_DagHeader_t *dag_h, RF_DagHeader_t *newptr) 658 { 659 int i; 660 for (i = 0; i < dag_h->numSuccedents; i++) 661 if (dag_h->succedents[i]->dagHdr != newptr) 662 rf_RecurResetDAGHeaderPointers(dag_h->succedents[i], newptr); 663 } 664 665 void 666 rf_RecurResetDAGHeaderPointers(RF_DagNode_t *node, RF_DagHeader_t *newptr) 667 { 668 int i; 669 node->dagHdr = newptr; 670 for (i = 0; i < node->numSuccedents; i++) 671 if (node->succedents[i]->dagHdr != newptr) 672 rf_RecurResetDAGHeaderPointers(node->succedents[i], newptr); 673 } 674 675 676 void 677 rf_PrintDAGList(RF_DagHeader_t * dag_h) 678 { 679 int i = 0; 680 681 for (; dag_h; dag_h = dag_h->next) { 682 rf_AssignNodeNums(dag_h); 683 printf("\n\nDAG %d IN LIST:\n", i++); 684 rf_PrintDAG(dag_h); 685 } 686 } 687 688 static int 689 rf_ValidateBranch(RF_DagNode_t *node, int *scount, int *acount, 690 RF_DagNode_t **nodes, int unvisited) 691 { 692 int i, retcode = 0; 693 694 /* construct an array of node pointers indexed by node num */ 695 node->visited = (unvisited) ? 0 : 1; 696 nodes[node->nodeNum] = node; 697 698 if (node->next != NULL) { 699 printf("INVALID DAG: next pointer in node is not NULL\n"); 700 retcode = 1; 701 } 702 if (node->status != rf_wait) { 703 printf("INVALID DAG: Node status is not wait\n"); 704 retcode = 1; 705 } 706 if (node->numAntDone != 0) { 707 printf("INVALID DAG: numAntDone is not zero\n"); 708 retcode = 1; 709 } 710 if (node->doFunc == rf_TerminateFunc) { 711 if (node->numSuccedents != 0) { 712 printf("INVALID DAG: Terminator node has succedents\n"); 713 retcode = 1; 714 } 715 } else { 716 if (node->numSuccedents == 0) { 717 printf("INVALID DAG: Non-terminator node has no succedents\n"); 718 retcode = 1; 719 } 720 } 721 for (i = 0; i < node->numSuccedents; i++) { 722 if (!node->succedents[i]) { 723 printf("INVALID DAG: succedent %d of node %s is NULL\n", i, node->name); 724 retcode = 1; 725 } 726 scount[node->succedents[i]->nodeNum]++; 727 } 728 for (i = 0; i < node->numAntecedents; i++) { 729 if (!node->antecedents[i]) { 730 printf("INVALID DAG: antecedent %d of node %s is NULL\n", i, node->name); 731 retcode = 1; 732 } 733 acount[node->antecedents[i]->nodeNum]++; 734 } 735 for (i = 0; i < node->numSuccedents; i++) { 736 if (node->succedents[i]->visited == unvisited) { 737 if (rf_ValidateBranch(node->succedents[i], scount, 738 acount, nodes, unvisited)) { 739 retcode = 1; 740 } 741 } 742 } 743 return (retcode); 744 } 745 746 static void 747 rf_ValidateBranchVisitedBits(RF_DagNode_t *node, int unvisited, int rl) 748 { 749 int i; 750 751 RF_ASSERT(node->visited == unvisited); 752 for (i = 0; i < node->numSuccedents; i++) { 753 if (node->succedents[i] == NULL) { 754 printf("node=%lx node->succedents[%d] is NULL\n", (long) node, i); 755 RF_ASSERT(0); 756 } 757 rf_ValidateBranchVisitedBits(node->succedents[i], unvisited, rl + 1); 758 } 759 } 760 /* NOTE: never call this on a big dag, because it is exponential 761 * in execution time 762 */ 763 static void 764 rf_ValidateVisitedBits(RF_DagHeader_t *dag) 765 { 766 int i, unvisited; 767 768 unvisited = dag->succedents[0]->visited; 769 770 for (i = 0; i < dag->numSuccedents; i++) { 771 if (dag->succedents[i] == NULL) { 772 printf("dag=%lx dag->succedents[%d] is NULL\n", (long) dag, i); 773 RF_ASSERT(0); 774 } 775 rf_ValidateBranchVisitedBits(dag->succedents[i], unvisited, 0); 776 } 777 } 778 /* validate a DAG. _at entry_ verify that: 779 * -- numNodesCompleted is zero 780 * -- node queue is null 781 * -- dag status is rf_enable 782 * -- next pointer is null on every node 783 * -- all nodes have status wait 784 * -- numAntDone is zero in all nodes 785 * -- terminator node has zero successors 786 * -- no other node besides terminator has zero successors 787 * -- no successor or antecedent pointer in a node is NULL 788 * -- number of times that each node appears as a successor of another node 789 * is equal to the antecedent count on that node 790 * -- number of times that each node appears as an antecedent of another node 791 * is equal to the succedent count on that node 792 * -- what else? 793 */ 794 int 795 rf_ValidateDAG(RF_DagHeader_t *dag_h) 796 { 797 int i, nodecount; 798 int *scount, *acount;/* per-node successor and antecedent counts */ 799 RF_DagNode_t **nodes; /* array of ptrs to nodes in dag */ 800 int retcode = 0; 801 int unvisited; 802 int commitNodeCount = 0; 803 804 if (rf_validateVisitedDebug) 805 rf_ValidateVisitedBits(dag_h); 806 807 if (dag_h->numNodesCompleted != 0) { 808 printf("INVALID DAG: num nodes completed is %d, should be 0\n", dag_h->numNodesCompleted); 809 retcode = 1; 810 goto validate_dag_bad; 811 } 812 if (dag_h->status != rf_enable) { 813 printf("INVALID DAG: not enabled\n"); 814 retcode = 1; 815 goto validate_dag_bad; 816 } 817 if (dag_h->numCommits != 0) { 818 printf("INVALID DAG: numCommits != 0 (%d)\n", dag_h->numCommits); 819 retcode = 1; 820 goto validate_dag_bad; 821 } 822 if (dag_h->numSuccedents != 1) { 823 /* currently, all dags must have only one succedent */ 824 printf("INVALID DAG: numSuccedents !1 (%d)\n", dag_h->numSuccedents); 825 retcode = 1; 826 goto validate_dag_bad; 827 } 828 nodecount = rf_AssignNodeNums(dag_h); 829 830 unvisited = dag_h->succedents[0]->visited; 831 832 scount = RF_Malloc(nodecount * sizeof(*scount)); 833 acount = RF_Malloc(nodecount * sizeof(*acount)); 834 nodes = RF_Malloc(nodecount * sizeof(*nodes)); 835 for (i = 0; i < dag_h->numSuccedents; i++) { 836 if ((dag_h->succedents[i]->visited == unvisited) 837 && rf_ValidateBranch(dag_h->succedents[i], scount, 838 acount, nodes, unvisited)) { 839 retcode = 1; 840 } 841 } 842 /* start at 1 to skip the header node */ 843 for (i = 1; i < nodecount; i++) { 844 if (nodes[i]->commitNode) 845 commitNodeCount++; 846 if (nodes[i]->doFunc == NULL) { 847 printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name); 848 retcode = 1; 849 goto validate_dag_out; 850 } 851 if (nodes[i]->undoFunc == NULL) { 852 printf("INVALID DAG: node %s has an undefined doFunc\n", nodes[i]->name); 853 retcode = 1; 854 goto validate_dag_out; 855 } 856 if (nodes[i]->numAntecedents != scount[nodes[i]->nodeNum]) { 857 printf("INVALID DAG: node %s has %d antecedents but appears as a succedent %d times\n", 858 nodes[i]->name, nodes[i]->numAntecedents, scount[nodes[i]->nodeNum]); 859 retcode = 1; 860 goto validate_dag_out; 861 } 862 if (nodes[i]->numSuccedents != acount[nodes[i]->nodeNum]) { 863 printf("INVALID DAG: node %s has %d succedents but appears as an antecedent %d times\n", 864 nodes[i]->name, nodes[i]->numSuccedents, acount[nodes[i]->nodeNum]); 865 retcode = 1; 866 goto validate_dag_out; 867 } 868 } 869 870 if (dag_h->numCommitNodes != commitNodeCount) { 871 printf("INVALID DAG: incorrect commit node count. hdr->numCommitNodes (%d) found (%d) commit nodes in graph\n", 872 dag_h->numCommitNodes, commitNodeCount); 873 retcode = 1; 874 goto validate_dag_out; 875 } 876 validate_dag_out: 877 RF_Free(scount, nodecount * sizeof(int)); 878 RF_Free(acount, nodecount * sizeof(int)); 879 RF_Free(nodes, nodecount * sizeof(RF_DagNode_t *)); 880 if (retcode) 881 rf_PrintDAGList(dag_h); 882 883 if (rf_validateVisitedDebug) 884 rf_ValidateVisitedBits(dag_h); 885 886 return (retcode); 887 888 validate_dag_bad: 889 rf_PrintDAGList(dag_h); 890 return (retcode); 891 } 892 893 #endif /* RF_DEBUG_VALIDATE_DAG */ 894 895 /****************************************************************************** 896 * 897 * misc construction routines 898 * 899 *****************************************************************************/ 900 901 void 902 rf_redirect_asm(RF_Raid_t *raidPtr, RF_AccessStripeMap_t *asmap) 903 { 904 int ds = (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) ? 1 : 0; 905 int fcol = raidPtr->reconControl->fcol; 906 int scol = raidPtr->reconControl->spareCol; 907 RF_PhysDiskAddr_t *pda; 908 909 RF_ASSERT(raidPtr->status == rf_rs_reconstructing); 910 for (pda = asmap->physInfo; pda; pda = pda->next) { 911 if (pda->col == fcol) { 912 #if RF_DEBUG_DAG 913 if (rf_dagDebug) { 914 if (!rf_CheckRUReconstructed(raidPtr->reconControl->reconMap, 915 pda->startSector)) { 916 RF_PANIC(); 917 } 918 } 919 #endif 920 /* printf("Remapped data for large write\n"); */ 921 if (ds) { 922 raidPtr->Layout.map->MapSector(raidPtr, pda->raidAddress, 923 &pda->col, &pda->startSector, RF_REMAP); 924 } else { 925 pda->col = scol; 926 } 927 } 928 } 929 for (pda = asmap->parityInfo; pda; pda = pda->next) { 930 if (pda->col == fcol) { 931 #if RF_DEBUG_DAG 932 if (rf_dagDebug) { 933 if (!rf_CheckRUReconstructed(raidPtr->reconControl->reconMap, pda->startSector)) { 934 RF_PANIC(); 935 } 936 } 937 #endif 938 } 939 if (ds) { 940 (raidPtr->Layout.map->MapParity) (raidPtr, pda->raidAddress, &pda->col, &pda->startSector, RF_REMAP); 941 } else { 942 pda->col = scol; 943 } 944 } 945 } 946 947 948 /* this routine allocates read buffers and generates stripe maps for the 949 * regions of the array from the start of the stripe to the start of the 950 * access, and from the end of the access to the end of the stripe. It also 951 * computes and returns the number of DAG nodes needed to read all this data. 952 * Note that this routine does the wrong thing if the access is fully 953 * contained within one stripe unit, so we RF_ASSERT against this case at the 954 * start. 955 * 956 * layoutPtr - in: layout information 957 * asmap - in: access stripe map 958 * dag_h - in: header of the dag to create 959 * new_asm_h - in: ptr to array of 2 headers. to be filled in 960 * nRodNodes - out: num nodes to be generated to read unaccessed data 961 * sosBuffer, eosBuffer - out: pointers to newly allocated buffer 962 */ 963 void 964 rf_MapUnaccessedPortionOfStripe(RF_Raid_t *raidPtr, 965 RF_RaidLayout_t *layoutPtr, 966 RF_AccessStripeMap_t *asmap, 967 RF_DagHeader_t *dag_h, 968 RF_AccessStripeMapHeader_t **new_asm_h, 969 int *nRodNodes, 970 char **sosBuffer, char **eosBuffer, 971 RF_AllocListElem_t *allocList) 972 { 973 RF_RaidAddr_t sosRaidAddress, eosRaidAddress; 974 RF_SectorNum_t sosNumSector, eosNumSector; 975 976 RF_ASSERT(asmap->numStripeUnitsAccessed > (layoutPtr->numDataCol / 2)); 977 /* generate an access map for the region of the array from start of 978 * stripe to start of access */ 979 new_asm_h[0] = new_asm_h[1] = NULL; 980 *nRodNodes = 0; 981 if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->raidAddress)) { 982 sosRaidAddress = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress); 983 sosNumSector = asmap->raidAddress - sosRaidAddress; 984 *sosBuffer = rf_AllocStripeBuffer(raidPtr, dag_h, rf_RaidAddressToByte(raidPtr, sosNumSector)); 985 new_asm_h[0] = rf_MapAccess(raidPtr, sosRaidAddress, sosNumSector, *sosBuffer, RF_DONT_REMAP); 986 new_asm_h[0]->next = dag_h->asmList; 987 dag_h->asmList = new_asm_h[0]; 988 *nRodNodes += new_asm_h[0]->stripeMap->numStripeUnitsAccessed; 989 990 RF_ASSERT(new_asm_h[0]->stripeMap->next == NULL); 991 /* we're totally within one stripe here */ 992 if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE) 993 rf_redirect_asm(raidPtr, new_asm_h[0]->stripeMap); 994 } 995 /* generate an access map for the region of the array from end of 996 * access to end of stripe */ 997 if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->endRaidAddress)) { 998 eosRaidAddress = asmap->endRaidAddress; 999 eosNumSector = rf_RaidAddressOfNextStripeBoundary(layoutPtr, eosRaidAddress) - eosRaidAddress; 1000 *eosBuffer = rf_AllocStripeBuffer(raidPtr, dag_h, rf_RaidAddressToByte(raidPtr, eosNumSector)); 1001 new_asm_h[1] = rf_MapAccess(raidPtr, eosRaidAddress, eosNumSector, *eosBuffer, RF_DONT_REMAP); 1002 new_asm_h[1]->next = dag_h->asmList; 1003 dag_h->asmList = new_asm_h[1]; 1004 *nRodNodes += new_asm_h[1]->stripeMap->numStripeUnitsAccessed; 1005 1006 RF_ASSERT(new_asm_h[1]->stripeMap->next == NULL); 1007 /* we're totally within one stripe here */ 1008 if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE) 1009 rf_redirect_asm(raidPtr, new_asm_h[1]->stripeMap); 1010 } 1011 } 1012 1013 1014 1015 /* returns non-zero if the indicated ranges of stripe unit offsets overlap */ 1016 int 1017 rf_PDAOverlap(RF_RaidLayout_t *layoutPtr, 1018 RF_PhysDiskAddr_t *src, RF_PhysDiskAddr_t *dest) 1019 { 1020 RF_SectorNum_t soffs = rf_StripeUnitOffset(layoutPtr, src->startSector); 1021 RF_SectorNum_t doffs = rf_StripeUnitOffset(layoutPtr, dest->startSector); 1022 /* use -1 to be sure we stay within SU */ 1023 RF_SectorNum_t send = rf_StripeUnitOffset(layoutPtr, src->startSector + src->numSector - 1); 1024 RF_SectorNum_t dend = rf_StripeUnitOffset(layoutPtr, dest->startSector + dest->numSector - 1); 1025 return ((RF_MAX(soffs, doffs) <= RF_MIN(send, dend)) ? 1 : 0); 1026 } 1027 1028 1029 /* GenerateFailedAccessASMs 1030 * 1031 * this routine figures out what portion of the stripe needs to be read 1032 * to effect the degraded read or write operation. It's primary function 1033 * is to identify everything required to recover the data, and then 1034 * eliminate anything that is already being accessed by the user. 1035 * 1036 * The main result is two new ASMs, one for the region from the start of the 1037 * stripe to the start of the access, and one for the region from the end of 1038 * the access to the end of the stripe. These ASMs describe everything that 1039 * needs to be read to effect the degraded access. Other results are: 1040 * nXorBufs -- the total number of buffers that need to be XORed together to 1041 * recover the lost data, 1042 * rpBufPtr -- ptr to a newly-allocated buffer to hold the parity. If NULL 1043 * at entry, not allocated. 1044 * overlappingPDAs -- 1045 * describes which of the non-failed PDAs in the user access 1046 * overlap data that needs to be read to effect recovery. 1047 * overlappingPDAs[i]==1 if and only if, neglecting the failed 1048 * PDA, the ith pda in the input asm overlaps data that needs 1049 * to be read for recovery. 1050 */ 1051 /* in: asm - ASM for the actual access, one stripe only */ 1052 /* in: failedPDA - which component of the access has failed */ 1053 /* in: dag_h - header of the DAG we're going to create */ 1054 /* out: new_asm_h - the two new ASMs */ 1055 /* out: nXorBufs - the total number of xor bufs required */ 1056 /* out: rpBufPtr - a buffer for the parity read */ 1057 void 1058 rf_GenerateFailedAccessASMs(RF_Raid_t *raidPtr, RF_AccessStripeMap_t *asmap, 1059 RF_PhysDiskAddr_t *failedPDA, 1060 RF_DagHeader_t *dag_h, 1061 RF_AccessStripeMapHeader_t **new_asm_h, 1062 int *nXorBufs, char **rpBufPtr, 1063 char *overlappingPDAs, 1064 RF_AllocListElem_t *allocList) 1065 { 1066 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 1067 1068 /* s=start, e=end, s=stripe, a=access, f=failed, su=stripe unit */ 1069 RF_RaidAddr_t sosAddr, sosEndAddr, eosStartAddr, eosAddr; 1070 RF_PhysDiskAddr_t *pda; 1071 int foundit, i; 1072 1073 foundit = 0; 1074 /* first compute the following raid addresses: start of stripe, 1075 * (sosAddr) MIN(start of access, start of failed SU), (sosEndAddr) 1076 * MAX(end of access, end of failed SU), (eosStartAddr) end of 1077 * stripe (i.e. start of next stripe) (eosAddr) */ 1078 sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress); 1079 sosEndAddr = RF_MIN(asmap->raidAddress, rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, failedPDA->raidAddress)); 1080 eosStartAddr = RF_MAX(asmap->endRaidAddress, rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, failedPDA->raidAddress)); 1081 eosAddr = rf_RaidAddressOfNextStripeBoundary(layoutPtr, asmap->raidAddress); 1082 1083 /* now generate access stripe maps for each of the above regions of 1084 * the stripe. Use a dummy (NULL) buf ptr for now */ 1085 1086 new_asm_h[0] = (sosAddr != sosEndAddr) ? rf_MapAccess(raidPtr, sosAddr, sosEndAddr - sosAddr, NULL, RF_DONT_REMAP) : NULL; 1087 new_asm_h[1] = (eosStartAddr != eosAddr) ? rf_MapAccess(raidPtr, eosStartAddr, eosAddr - eosStartAddr, NULL, RF_DONT_REMAP) : NULL; 1088 1089 /* walk through the PDAs and range-restrict each SU to the region of 1090 * the SU touched on the failed PDA. also compute total data buffer 1091 * space requirements in this step. Ignore the parity for now. */ 1092 /* Also count nodes to find out how many bufs need to be xored together */ 1093 (*nXorBufs) = 1; /* in read case, 1 is for parity. In write 1094 * case, 1 is for failed data */ 1095 1096 if (new_asm_h[0]) { 1097 new_asm_h[0]->next = dag_h->asmList; 1098 dag_h->asmList = new_asm_h[0]; 1099 for (pda = new_asm_h[0]->stripeMap->physInfo; pda; pda = pda->next) { 1100 rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_NOBUFFER, 0); 1101 pda->bufPtr = rf_AllocBuffer(raidPtr, dag_h, pda->numSector << raidPtr->logBytesPerSector); 1102 } 1103 (*nXorBufs) += new_asm_h[0]->stripeMap->numStripeUnitsAccessed; 1104 } 1105 if (new_asm_h[1]) { 1106 new_asm_h[1]->next = dag_h->asmList; 1107 dag_h->asmList = new_asm_h[1]; 1108 for (pda = new_asm_h[1]->stripeMap->physInfo; pda; pda = pda->next) { 1109 rf_RangeRestrictPDA(raidPtr, failedPDA, pda, RF_RESTRICT_NOBUFFER, 0); 1110 pda->bufPtr = rf_AllocBuffer(raidPtr, dag_h, pda->numSector << raidPtr->logBytesPerSector); 1111 } 1112 (*nXorBufs) += new_asm_h[1]->stripeMap->numStripeUnitsAccessed; 1113 } 1114 1115 /* allocate a buffer for parity */ 1116 if (rpBufPtr) 1117 *rpBufPtr = rf_AllocBuffer(raidPtr, dag_h, failedPDA->numSector << raidPtr->logBytesPerSector); 1118 1119 /* the last step is to figure out how many more distinct buffers need 1120 * to get xor'd to produce the missing unit. there's one for each 1121 * user-data read node that overlaps the portion of the failed unit 1122 * being accessed */ 1123 1124 for (foundit = i = 0, pda = asmap->physInfo; pda; i++, pda = pda->next) { 1125 if (pda == failedPDA) { 1126 i--; 1127 foundit = 1; 1128 continue; 1129 } 1130 if (rf_PDAOverlap(layoutPtr, pda, failedPDA)) { 1131 overlappingPDAs[i] = 1; 1132 (*nXorBufs)++; 1133 } 1134 } 1135 if (!foundit) { 1136 RF_ERRORMSG("GenerateFailedAccessASMs: did not find failedPDA in asm list\n"); 1137 RF_ASSERT(0); 1138 } 1139 #if RF_DEBUG_DAG 1140 if (rf_degDagDebug) { 1141 if (new_asm_h[0]) { 1142 printf("First asm:\n"); 1143 rf_PrintFullAccessStripeMap(new_asm_h[0], 1); 1144 } 1145 if (new_asm_h[1]) { 1146 printf("Second asm:\n"); 1147 rf_PrintFullAccessStripeMap(new_asm_h[1], 1); 1148 } 1149 } 1150 #endif 1151 } 1152 1153 1154 /* adjusts the offset and number of sectors in the destination pda so that 1155 * it covers at most the region of the SU covered by the source PDA. This 1156 * is exclusively a restriction: the number of sectors indicated by the 1157 * target PDA can only shrink. 1158 * 1159 * For example: s = sectors within SU indicated by source PDA 1160 * d = sectors within SU indicated by dest PDA 1161 * r = results, stored in dest PDA 1162 * 1163 * |--------------- one stripe unit ---------------------| 1164 * | sssssssssssssssssssssssssssssssss | 1165 * | ddddddddddddddddddddddddddddddddddddddddddddd | 1166 * | rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr | 1167 * 1168 * Another example: 1169 * 1170 * |--------------- one stripe unit ---------------------| 1171 * | sssssssssssssssssssssssssssssssss | 1172 * | ddddddddddddddddddddddd | 1173 * | rrrrrrrrrrrrrrrr | 1174 * 1175 */ 1176 void 1177 rf_RangeRestrictPDA(RF_Raid_t *raidPtr, RF_PhysDiskAddr_t *src, 1178 RF_PhysDiskAddr_t *dest, int dobuffer, int doraidaddr) 1179 { 1180 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 1181 RF_SectorNum_t soffs = rf_StripeUnitOffset(layoutPtr, src->startSector); 1182 RF_SectorNum_t doffs = rf_StripeUnitOffset(layoutPtr, dest->startSector); 1183 RF_SectorNum_t send = rf_StripeUnitOffset(layoutPtr, src->startSector + src->numSector - 1); /* use -1 to be sure we 1184 * stay within SU */ 1185 RF_SectorNum_t dend = rf_StripeUnitOffset(layoutPtr, dest->startSector + dest->numSector - 1); 1186 RF_SectorNum_t subAddr = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, dest->startSector); /* stripe unit boundary */ 1187 1188 dest->startSector = subAddr + RF_MAX(soffs, doffs); 1189 dest->numSector = subAddr + RF_MIN(send, dend) + 1 - dest->startSector; 1190 1191 if (dobuffer) 1192 dest->bufPtr = (char *)(dest->bufPtr) + ((soffs > doffs) ? rf_RaidAddressToByte(raidPtr, soffs - doffs) : 0); 1193 if (doraidaddr) { 1194 dest->raidAddress = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, dest->raidAddress) + 1195 rf_StripeUnitOffset(layoutPtr, dest->startSector); 1196 } 1197 } 1198 1199 #if (RF_INCLUDE_CHAINDECLUSTER > 0) 1200 1201 /* 1202 * Want the highest of these primes to be the largest one 1203 * less than the max expected number of columns (won't hurt 1204 * to be too small or too large, but won't be optimal, either) 1205 * --jimz 1206 */ 1207 #define NLOWPRIMES 8 1208 static int lowprimes[NLOWPRIMES] = {2, 3, 5, 7, 11, 13, 17, 19}; 1209 /***************************************************************************** 1210 * compute the workload shift factor. (chained declustering) 1211 * 1212 * return nonzero if access should shift to secondary, otherwise, 1213 * access is to primary 1214 *****************************************************************************/ 1215 int 1216 rf_compute_workload_shift(RF_Raid_t *raidPtr, RF_PhysDiskAddr_t *pda) 1217 { 1218 /* 1219 * variables: 1220 * d = column of disk containing primary 1221 * f = column of failed disk 1222 * n = number of disks in array 1223 * sd = "shift distance" (number of columns that d is to the right of f) 1224 * v = numerator of redirection ratio 1225 * k = denominator of redirection ratio 1226 */ 1227 RF_RowCol_t d, f, sd, n; 1228 int k, v, ret, i; 1229 1230 n = raidPtr->numCol; 1231 1232 /* assign column of primary copy to d */ 1233 d = pda->col; 1234 1235 /* assign column of dead disk to f */ 1236 for (f = 0; ((!RF_DEAD_DISK(raidPtr->Disks[f].status)) && (f < n)); f++) 1237 continue; 1238 1239 RF_ASSERT(f < n); 1240 RF_ASSERT(f != d); 1241 1242 sd = (f > d) ? (n + d - f) : (d - f); 1243 RF_ASSERT(sd < n); 1244 1245 /* 1246 * v of every k accesses should be redirected 1247 * 1248 * v/k := (n-1-sd)/(n-1) 1249 */ 1250 v = (n - 1 - sd); 1251 k = (n - 1); 1252 1253 #if 1 1254 /* 1255 * XXX 1256 * Is this worth it? 1257 * 1258 * Now reduce the fraction, by repeatedly factoring 1259 * out primes (just like they teach in elementary school!) 1260 */ 1261 for (i = 0; i < NLOWPRIMES; i++) { 1262 if (lowprimes[i] > v) 1263 break; 1264 while (((v % lowprimes[i]) == 0) && ((k % lowprimes[i]) == 0)) { 1265 v /= lowprimes[i]; 1266 k /= lowprimes[i]; 1267 } 1268 } 1269 #endif 1270 1271 raidPtr->hist_diskreq[d]++; 1272 if (raidPtr->hist_diskreq[d] > v) { 1273 ret = 0; /* do not redirect */ 1274 } else { 1275 ret = 1; /* redirect */ 1276 } 1277 1278 #if 0 1279 printf("d=%d f=%d sd=%d v=%d k=%d ret=%d h=%d\n", d, f, sd, v, k, ret, 1280 raidPtr->hist_diskreq[d]); 1281 #endif 1282 1283 if (raidPtr->hist_diskreq[d] >= k) { 1284 /* reset counter */ 1285 raidPtr->hist_diskreq[d] = 0; 1286 } 1287 return (ret); 1288 } 1289 #endif /* (RF_INCLUDE_CHAINDECLUSTER > 0) */ 1290 1291 /* 1292 * Disk selection routines 1293 */ 1294 1295 /* 1296 * Selects the disk with the shortest queue from a mirror pair. 1297 * Both the disk I/Os queued in RAIDframe as well as those at the physical 1298 * disk are counted as members of the "queue" 1299 */ 1300 void 1301 rf_SelectMirrorDiskIdle(RF_DagNode_t * node) 1302 { 1303 RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr; 1304 RF_RowCol_t colData, colMirror; 1305 int dataQueueLength, mirrorQueueLength, usemirror; 1306 RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p; 1307 RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p; 1308 RF_PhysDiskAddr_t *tmp_pda; 1309 RF_RaidDisk_t *disks = raidPtr->Disks; 1310 RF_DiskQueue_t *dqs = raidPtr->Queues, *dataQueue, *mirrorQueue; 1311 1312 /* return the [row col] of the disk with the shortest queue */ 1313 colData = data_pda->col; 1314 colMirror = mirror_pda->col; 1315 dataQueue = &(dqs[colData]); 1316 mirrorQueue = &(dqs[colMirror]); 1317 1318 #ifdef RF_LOCK_QUEUES_TO_READ_LEN 1319 RF_LOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle"); 1320 #endif /* RF_LOCK_QUEUES_TO_READ_LEN */ 1321 dataQueueLength = dataQueue->queueLength + dataQueue->numOutstanding; 1322 #ifdef RF_LOCK_QUEUES_TO_READ_LEN 1323 RF_UNLOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle"); 1324 RF_LOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle"); 1325 #endif /* RF_LOCK_QUEUES_TO_READ_LEN */ 1326 mirrorQueueLength = mirrorQueue->queueLength + mirrorQueue->numOutstanding; 1327 #ifdef RF_LOCK_QUEUES_TO_READ_LEN 1328 RF_UNLOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle"); 1329 #endif /* RF_LOCK_QUEUES_TO_READ_LEN */ 1330 1331 usemirror = 0; 1332 if (RF_DEAD_DISK(disks[colMirror].status)) { 1333 usemirror = 0; 1334 } else 1335 if (RF_DEAD_DISK(disks[colData].status)) { 1336 usemirror = 1; 1337 } else 1338 if (raidPtr->parity_good == RF_RAID_DIRTY) { 1339 /* Trust only the main disk */ 1340 usemirror = 0; 1341 } else 1342 if (dataQueueLength < mirrorQueueLength) { 1343 usemirror = 0; 1344 } else 1345 if (mirrorQueueLength < dataQueueLength) { 1346 usemirror = 1; 1347 } else { 1348 /* queues are equal length. attempt 1349 * cleverness. */ 1350 if (SNUM_DIFF(dataQueue->last_deq_sector, data_pda->startSector) 1351 <= SNUM_DIFF(mirrorQueue->last_deq_sector, mirror_pda->startSector)) { 1352 usemirror = 0; 1353 } else { 1354 usemirror = 1; 1355 } 1356 } 1357 1358 if (usemirror) { 1359 /* use mirror (parity) disk, swap params 0 & 4 */ 1360 tmp_pda = data_pda; 1361 node->params[0].p = mirror_pda; 1362 node->params[4].p = tmp_pda; 1363 } else { 1364 /* use data disk, leave param 0 unchanged */ 1365 } 1366 /* printf("dataQueueLength %d, mirrorQueueLength 1367 * %d\n",dataQueueLength, mirrorQueueLength); */ 1368 } 1369 #if (RF_INCLUDE_CHAINDECLUSTER > 0) || (RF_INCLUDE_INTERDECLUSTER > 0) || (RF_DEBUG_VALIDATE_DAG > 0) 1370 /* 1371 * Do simple partitioning. This assumes that 1372 * the data and parity disks are laid out identically. 1373 */ 1374 void 1375 rf_SelectMirrorDiskPartition(RF_DagNode_t * node) 1376 { 1377 RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr; 1378 RF_RowCol_t colData, colMirror; 1379 RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p; 1380 RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p; 1381 RF_PhysDiskAddr_t *tmp_pda; 1382 RF_RaidDisk_t *disks = raidPtr->Disks; 1383 int usemirror; 1384 1385 /* return the [row col] of the disk with the shortest queue */ 1386 colData = data_pda->col; 1387 colMirror = mirror_pda->col; 1388 1389 usemirror = 0; 1390 if (RF_DEAD_DISK(disks[colMirror].status)) { 1391 usemirror = 0; 1392 } else 1393 if (RF_DEAD_DISK(disks[colData].status)) { 1394 usemirror = 1; 1395 } else 1396 if (raidPtr->parity_good == RF_RAID_DIRTY) { 1397 /* Trust only the main disk */ 1398 usemirror = 0; 1399 } else 1400 if (data_pda->startSector < 1401 (disks[colData].numBlocks / 2)) { 1402 usemirror = 0; 1403 } else { 1404 usemirror = 1; 1405 } 1406 1407 if (usemirror) { 1408 /* use mirror (parity) disk, swap params 0 & 4 */ 1409 tmp_pda = data_pda; 1410 node->params[0].p = mirror_pda; 1411 node->params[4].p = tmp_pda; 1412 } else { 1413 /* use data disk, leave param 0 unchanged */ 1414 } 1415 } 1416 #endif 1417