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