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