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