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