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