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