Annotation of sys/dev/raidframe/rf_dagutils.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: rf_dagutils.c,v 1.4 2002/12/16 07:01:03 tdeval Exp $ */
! 2: /* $NetBSD: rf_dagutils.c,v 1.6 1999/12/09 02:26:09 oster Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1995 Carnegie-Mellon University.
! 6: * All rights reserved.
! 7: *
! 8: * Authors: Mark Holland, William V. Courtright II, Jim Zelenka
! 9: *
! 10: * Permission to use, copy, modify and distribute this software and
! 11: * its documentation is hereby granted, provided that both the copyright
! 12: * notice and this permission notice appear in all copies of the
! 13: * software, derivative works or modified versions, and any portions
! 14: * thereof, and that both notices appear in supporting documentation.
! 15: *
! 16: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
! 17: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
! 18: * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
! 19: *
! 20: * Carnegie Mellon requests users of this software to return to
! 21: *
! 22: * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
! 23: * School of Computer Science
! 24: * Carnegie Mellon University
! 25: * Pittsburgh PA 15213-3890
! 26: *
! 27: * any improvements or extensions that they make and grant Carnegie the
! 28: * rights to redistribute these changes.
! 29: */
! 30:
! 31: /*****************************************************************************
! 32: *
! 33: * rf_dagutils.c -- Utility routines for manipulating dags.
! 34: *
! 35: *****************************************************************************/
! 36:
! 37: #include "rf_archs.h"
! 38: #include "rf_types.h"
! 39: #include "rf_threadstuff.h"
! 40: #include "rf_raid.h"
! 41: #include "rf_dag.h"
! 42: #include "rf_dagutils.h"
! 43: #include "rf_dagfuncs.h"
! 44: #include "rf_general.h"
! 45: #include "rf_freelist.h"
! 46: #include "rf_map.h"
! 47: #include "rf_shutdown.h"
! 48:
! 49: #define SNUM_DIFF(_a_,_b_) (((_a_)>(_b_))?((_a_)-(_b_)):((_b_)-(_a_)))
! 50:
! 51: RF_RedFuncs_t rf_xorFuncs = {
! 52: rf_RegularXorFunc, "Reg Xr", rf_SimpleXorFunc, "Simple Xr"
! 53: };
! 54:
! 55: RF_RedFuncs_t rf_xorRecoveryFuncs = {
! 56: rf_RecoveryXorFunc, "Recovery Xr", rf_RecoveryXorFunc, "Recovery Xr"
! 57: };
! 58:
! 59: void rf_RecurPrintDAG(RF_DagNode_t *, int, int);
! 60: void rf_PrintDAG(RF_DagHeader_t *);
! 61: int rf_ValidateBranch(RF_DagNode_t *, int *, int *, RF_DagNode_t **, int);
! 62: void rf_ValidateBranchVisitedBits(RF_DagNode_t *, int, int);
! 63: 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 *),
! 79: int (*undoFunc) (RF_DagNode_t *node),
! 80: int (*wakeFunc) (RF_DagNode_t *node, int),
! 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: {
! 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.
! 119: * Hopefully, 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
! 123: * RF_DAG_PTRCACHESIZE (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 **)
! 133: (ptrs + nSucc + nAnte + nResult) : NULL;
! 134:
! 135: if (nParam) {
! 136: if (nParam <= RF_DAG_PARAMCACHESIZE) {
! 137: node->params = (RF_DagParam_t *) node->dag_params;
! 138: } else {
! 139: RF_CallocAndAdd(node->params, nParam,
! 140: sizeof(RF_DagParam_t), (RF_DagParam_t *), alist);
! 141: }
! 142: } else {
! 143: node->params = NULL;
! 144: }
! 145: }
! 146:
! 147:
! 148:
! 149: /*****************************************************************************
! 150: *
! 151: * Allocation and deallocation routines.
! 152: *
! 153: *****************************************************************************/
! 154:
! 155: void
! 156: rf_FreeDAG(RF_DagHeader_t *dag_h)
! 157: {
! 158: RF_AccessStripeMapHeader_t *asmap, *t_asmap;
! 159: RF_DagHeader_t *nextDag;
! 160: int i;
! 161:
! 162: while (dag_h) {
! 163: nextDag = dag_h->next;
! 164: for (i = 0; dag_h->memChunk[i] && i < RF_MAXCHUNKS; i++) {
! 165: /* Release mem chunks. */
! 166: rf_ReleaseMemChunk(dag_h->memChunk[i]);
! 167: dag_h->memChunk[i] = NULL;
! 168: }
! 169:
! 170: RF_ASSERT(i == dag_h->chunkIndex);
! 171: if (dag_h->xtraChunkCnt > 0) {
! 172: /* Free xtraMemChunks. */
! 173: for (i = 0; dag_h->xtraMemChunk[i] &&
! 174: i < dag_h->xtraChunkIndex; i++) {
! 175: rf_ReleaseMemChunk(dag_h->xtraMemChunk[i]);
! 176: dag_h->xtraMemChunk[i] = NULL;
! 177: }
! 178: RF_ASSERT(i == dag_h->xtraChunkIndex);
! 179: /* Free ptrs to xtraMemChunks. */
! 180: RF_Free(dag_h->xtraMemChunk, dag_h->xtraChunkCnt *
! 181: 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(RF_DagHeader_t *dag_h, int resultNum, int paramNum,
! 196: RF_PropHeader_t *next, RF_AllocListElem_t *allocList)
! 197: {
! 198: RF_PropHeader_t *p;
! 199:
! 200: RF_CallocAndAdd(p, 1, sizeof(RF_PropHeader_t), (RF_PropHeader_t *),
! 201: 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: void rf_ShutdownDAGs(void *);
! 215: void
! 216: rf_ShutdownDAGs(void *ignored)
! 217: {
! 218: RF_FREELIST_DESTROY(rf_dagh_freelist, next, (RF_DagHeader_t *));
! 219: }
! 220:
! 221: int
! 222: rf_ConfigureDAGs(RF_ShutdownList_t **listp)
! 223: {
! 224: int rc;
! 225:
! 226: RF_FREELIST_CREATE(rf_dagh_freelist, RF_MAX_FREE_DAGH, RF_DAGH_INC,
! 227: sizeof(RF_DagHeader_t));
! 228: if (rf_dagh_freelist == NULL)
! 229: return (ENOMEM);
! 230: rc = rf_ShutdownCreate(listp, rf_ShutdownDAGs, NULL);
! 231: if (rc) {
! 232: RF_ERRORMSG3("Unable to add to shutdown list file %s line"
! 233: " %d rc=%d\n", __FILE__, __LINE__, rc);
! 234: rf_ShutdownDAGs(NULL);
! 235: return (rc);
! 236: }
! 237: RF_FREELIST_PRIME(rf_dagh_freelist, RF_DAGH_INITIAL, next,
! 238: (RF_DagHeader_t *));
! 239: return (0);
! 240: }
! 241:
! 242: RF_DagHeader_t *
! 243: rf_AllocDAGHeader(void)
! 244: {
! 245: RF_DagHeader_t *dh;
! 246:
! 247: RF_FREELIST_GET(rf_dagh_freelist, dh, next, (RF_DagHeader_t *));
! 248: if (dh) {
! 249: bzero((char *) dh, sizeof(RF_DagHeader_t));
! 250: }
! 251: return (dh);
! 252: }
! 253:
! 254: void
! 255: rf_FreeDAGHeader(RF_DagHeader_t *dh)
! 256: {
! 257: RF_FREELIST_FREE(rf_dagh_freelist, dh, next);
! 258: }
! 259:
! 260: /* Allocate a buffer big enough to hold the data described by pda. */
! 261: void *
! 262: rf_AllocBuffer(RF_Raid_t *raidPtr, RF_DagHeader_t *dag_h,
! 263: RF_PhysDiskAddr_t *pda, RF_AllocListElem_t *allocList)
! 264: {
! 265: char *p;
! 266:
! 267: RF_MallocAndAdd(p, pda->numSector << raidPtr->logBytesPerSector,
! 268: (char *), allocList);
! 269: return ((void *) p);
! 270: }
! 271:
! 272:
! 273: /*****************************************************************************
! 274: *
! 275: * Debug routines.
! 276: *
! 277: *****************************************************************************/
! 278:
! 279: char *
! 280: rf_NodeStatusString(RF_DagNode_t *node)
! 281: {
! 282: switch (node->status) {
! 283: case rf_wait:
! 284: return ("wait");
! 285: case rf_fired:
! 286: return ("fired");
! 287: case rf_good:
! 288: return ("good");
! 289: case rf_bad:
! 290: return ("bad");
! 291: default:
! 292: return ("?");
! 293: }
! 294: }
! 295:
! 296: void
! 297: rf_PrintNodeInfoString(RF_DagNode_t *node)
! 298: {
! 299: RF_PhysDiskAddr_t *pda;
! 300: int (*df) (RF_DagNode_t *) = node->doFunc;
! 301: int i, lk, unlk;
! 302: void *bufPtr;
! 303:
! 304: if ((df == rf_DiskReadFunc) || (df == rf_DiskWriteFunc) ||
! 305: (df == rf_DiskReadMirrorIdleFunc) ||
! 306: (df == rf_DiskReadMirrorPartitionFunc)) {
! 307: pda = (RF_PhysDiskAddr_t *) node->params[0].p;
! 308: bufPtr = (void *) node->params[1].p;
! 309: lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
! 310: unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
! 311: RF_ASSERT(!(lk && unlk));
! 312: printf("r %d c %d offs %ld nsect %d buf 0x%lx %s\n", pda->row,
! 313: pda->col, (long) pda->startSector, (int) pda->numSector,
! 314: (long) bufPtr, (lk) ? "LOCK" : ((unlk) ? "UNLK" : " "));
! 315: return;
! 316: }
! 317: if (df == rf_DiskUnlockFunc) {
! 318: pda = (RF_PhysDiskAddr_t *) node->params[0].p;
! 319: lk = RF_EXTRACT_LOCK_FLAG(node->params[3].v);
! 320: unlk = RF_EXTRACT_UNLOCK_FLAG(node->params[3].v);
! 321: RF_ASSERT(!(lk && unlk));
! 322: printf("r %d c %d %s\n", pda->row, pda->col,
! 323: (lk) ? "LOCK" : ((unlk) ? "UNLK" : "nop"));
! 324: return;
! 325: }
! 326: if ((df == rf_SimpleXorFunc) || (df == rf_RegularXorFunc)
! 327: || (df == rf_RecoveryXorFunc)) {
! 328: printf("result buf 0x%lx\n", (long) node->results[0]);
! 329: for (i = 0; i < node->numParams - 1; i += 2) {
! 330: pda = (RF_PhysDiskAddr_t *) node->params[i].p;
! 331: bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p;
! 332: printf(" buf 0x%lx r%d c%d offs %ld nsect %d\n",
! 333: (long) bufPtr, pda->row, pda->col,
! 334: (long) pda->startSector, (int) pda->numSector);
! 335: }
! 336: return;
! 337: }
! 338: #if RF_INCLUDE_PARITYLOGGING > 0
! 339: if (df == rf_ParityLogOverwriteFunc || df == rf_ParityLogUpdateFunc) {
! 340: for (i = 0; i < node->numParams - 1; i += 2) {
! 341: pda = (RF_PhysDiskAddr_t *) node->params[i].p;
! 342: bufPtr = (RF_PhysDiskAddr_t *) node->params[i + 1].p;
! 343: printf(" r%d c%d offs %ld nsect %d buf 0x%lx\n",
! 344: pda->row, pda->col, (long) pda->startSector,
! 345: (int) pda->numSector, (long) bufPtr);
! 346: }
! 347: return;
! 348: }
! 349: #endif /* RF_INCLUDE_PARITYLOGGING > 0 */
! 350:
! 351: if ((df == rf_TerminateFunc) || (df == rf_NullNodeFunc)) {
! 352: printf("\n");
! 353: return;
! 354: }
! 355: printf("?\n");
! 356: }
! 357:
! 358: void
! 359: rf_RecurPrintDAG(RF_DagNode_t *node, int depth, int unvisited)
! 360: {
! 361: char *anttype;
! 362: int i;
! 363:
! 364: node->visited = (unvisited) ? 0 : 1;
! 365: printf("(%d) %d C%d %s: %s,s%d %d/%d,a%d/%d,p%d,r%d S{", depth,
! 366: node->nodeNum, node->commitNode, node->name,
! 367: rf_NodeStatusString(node), node->numSuccedents,
! 368: node->numSuccFired, node->numSuccDone,
! 369: node->numAntecedents, node->numAntDone,
! 370: node->numParams, node->numResults);
! 371: for (i = 0; i < node->numSuccedents; i++) {
! 372: printf("%d%s", node->succedents[i]->nodeNum,
! 373: ((i == node->numSuccedents - 1) ? "\0" : " "));
! 374: }
! 375: printf("} A{");
! 376: for (i = 0; i < node->numAntecedents; i++) {
! 377: switch (node->antType[i]) {
! 378: case rf_trueData:
! 379: anttype = "T";
! 380: break;
! 381: case rf_antiData:
! 382: anttype = "A";
! 383: break;
! 384: case rf_outputData:
! 385: anttype = "O";
! 386: break;
! 387: case rf_control:
! 388: anttype = "C";
! 389: break;
! 390: default:
! 391: anttype = "?";
! 392: break;
! 393: }
! 394: printf("%d(%s)%s", node->antecedents[i]->nodeNum, anttype,
! 395: (i == node->numAntecedents - 1) ? "\0" : " ");
! 396: }
! 397: printf("}; ");
! 398: rf_PrintNodeInfoString(node);
! 399: for (i = 0; i < node->numSuccedents; i++) {
! 400: if (node->succedents[i]->visited == unvisited)
! 401: rf_RecurPrintDAG(node->succedents[i], depth + 1,
! 402: unvisited);
! 403: }
! 404: }
! 405:
! 406: void
! 407: rf_PrintDAG(RF_DagHeader_t *dag_h)
! 408: {
! 409: int unvisited, i;
! 410: char *status;
! 411:
! 412: /* Set dag status. */
! 413: switch (dag_h->status) {
! 414: case rf_enable:
! 415: status = "enable";
! 416: break;
! 417: case rf_rollForward:
! 418: status = "rollForward";
! 419: break;
! 420: case rf_rollBackward:
! 421: status = "rollBackward";
! 422: break;
! 423: default:
! 424: status = "illegal !";
! 425: break;
! 426: }
! 427: /* Find out if visited bits are currently set or cleared. */
! 428: unvisited = dag_h->succedents[0]->visited;
! 429:
! 430: printf("DAG type: %s\n", dag_h->creator);
! 431: printf("format is (depth) num commit type: status,nSucc nSuccFired/n"
! 432: "SuccDone,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,
! 435: 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:
! 447: /* Assign node numbers. */
! 448: int
! 449: rf_AssignNodeNums(RF_DagHeader_t *dag_h)
! 450: {
! 451: int unvisited, i, nnum;
! 452: RF_DagNode_t *node;
! 453:
! 454: nnum = 0;
! 455: unvisited = dag_h->succedents[0]->visited;
! 456:
! 457: dag_h->nodeNum = nnum++;
! 458: for (i = 0; i < dag_h->numSuccedents; i++) {
! 459: node = dag_h->succedents[i];
! 460: if (node->visited == unvisited) {
! 461: nnum = rf_RecurAssignNodeNums(dag_h->succedents[i],
! 462: nnum, unvisited);
! 463: }
! 464: }
! 465: return (nnum);
! 466: }
! 467:
! 468: int
! 469: rf_RecurAssignNodeNums(RF_DagNode_t *node, int num, 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],
! 479: num, unvisited);
! 480: }
! 481: }
! 482: return (num);
! 483: }
! 484:
! 485: /* Set the header pointers in each node to "newptr". */
! 486: void
! 487: rf_ResetDAGHeaderPointers(RF_DagHeader_t *dag_h, RF_DagHeader_t *newptr)
! 488: {
! 489: int i;
! 490:
! 491: for (i = 0; i < dag_h->numSuccedents; i++)
! 492: if (dag_h->succedents[i]->dagHdr != newptr)
! 493: rf_RecurResetDAGHeaderPointers(dag_h->succedents[i],
! 494: newptr);
! 495: }
! 496:
! 497: void
! 498: rf_RecurResetDAGHeaderPointers(RF_DagNode_t *node, RF_DagHeader_t *newptr)
! 499: {
! 500: int i;
! 501:
! 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],
! 506: newptr);
! 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: int
! 522: rf_ValidateBranch(RF_DagNode_t *node, int *scount, int *acount,
! 523: RF_DagNode_t **nodes, int unvisited)
! 524: {
! 525: int i, retcode = 0;
! 526:
! 527: /* Construct an array of node pointers indexed by node num. */
! 528: node->visited = (unvisited) ? 0 : 1;
! 529: nodes[node->nodeNum] = node;
! 530:
! 531: if (node->next != NULL) {
! 532: printf("INVALID DAG: next pointer in node is not NULL.\n");
! 533: retcode = 1;
! 534: }
! 535: if (node->status != rf_wait) {
! 536: printf("INVALID DAG: Node status is not wait.\n");
! 537: retcode = 1;
! 538: }
! 539: if (node->numAntDone != 0) {
! 540: printf("INVALID DAG: numAntDone is not zero.\n");
! 541: retcode = 1;
! 542: }
! 543: if (node->doFunc == rf_TerminateFunc) {
! 544: if (node->numSuccedents != 0) {
! 545: printf("INVALID DAG: Terminator node has"
! 546: " succedents.\n");
! 547: retcode = 1;
! 548: }
! 549: } else {
! 550: if (node->numSuccedents == 0) {
! 551: printf("INVALID DAG: Non-terminator node has no"
! 552: " succedents\n");
! 553: retcode = 1;
! 554: }
! 555: }
! 556: for (i = 0; i < node->numSuccedents; i++) {
! 557: if (!node->succedents[i]) {
! 558: printf("INVALID DAG: succedent %d of node %s"
! 559: " 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"
! 567: " 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: void
! 584: rf_ValidateBranchVisitedBits(RF_DagNode_t *node, int unvisited, int rl)
! 585: {
! 586: int i;
! 587:
! 588: RF_ASSERT(node->visited == unvisited);
! 589: for (i = 0; i < node->numSuccedents; i++) {
! 590: if (node->succedents[i] == NULL) {
! 591: printf("node=%lx node->succedents[%d] is NULL.\n",
! 592: (long) node, i);
! 593: RF_ASSERT(0);
! 594: }
! 595: rf_ValidateBranchVisitedBits(node->succedents[i],
! 596: unvisited, rl + 1);
! 597: }
! 598: }
! 599:
! 600: /*
! 601: * NOTE: Never call this on a big dag, because it is exponential
! 602: * in execution time.
! 603: */
! 604: void
! 605: rf_ValidateVisitedBits(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",
! 614: (long) dag, i);
! 615: RF_ASSERT(0);
! 616: }
! 617: rf_ValidateBranchVisitedBits(dag->succedents[i], unvisited, 0);
! 618: }
! 619: }
! 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(RF_DagHeader_t *dag_h)
! 640: {
! 641: int i, nodecount;
! 642: int *scount, *acount; /* Per-node successor and antecedent counts. */
! 643: RF_DagNode_t **nodes; /* Array of ptrs to nodes in dag. */
! 644: int retcode = 0;
! 645: int unvisited;
! 646: int commitNodeCount = 0;
! 647:
! 648: if (rf_validateVisitedDebug)
! 649: rf_ValidateVisitedBits(dag_h);
! 650:
! 651: if (dag_h->numNodesCompleted != 0) {
! 652: printf("INVALID DAG: num nodes completed is %d, should be 0.\n",
! 653: 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",
! 664: dag_h->numCommits);
! 665: retcode = 1;
! 666: goto validate_dag_bad;
! 667: }
! 668: if (dag_h->numSuccedents != 1) {
! 669: /* Currently, all dags must have only one succedent. */
! 670: printf("INVALID DAG: numSuccedents != 1 (%d).\n",
! 671: dag_h->numSuccedents);
! 672: retcode = 1;
! 673: goto validate_dag_bad;
! 674: }
! 675: nodecount = rf_AssignNodeNums(dag_h);
! 676:
! 677: unvisited = dag_h->succedents[0]->visited;
! 678:
! 679: RF_Calloc(scount, nodecount, sizeof(int), (int *));
! 680: RF_Calloc(acount, nodecount, sizeof(int), (int *));
! 681: RF_Calloc(nodes, nodecount, sizeof(RF_DagNode_t *), (RF_DagNode_t **));
! 682: for (i = 0; i < dag_h->numSuccedents; i++) {
! 683: if ((dag_h->succedents[i]->visited == unvisited)
! 684: && rf_ValidateBranch(dag_h->succedents[i], scount,
! 685: acount, nodes, unvisited)) {
! 686: retcode = 1;
! 687: }
! 688: }
! 689: /* Start at 1 to skip the header node. */
! 690: for (i = 1; i < nodecount; i++) {
! 691: if (nodes[i]->commitNode)
! 692: commitNodeCount++;
! 693: if (nodes[i]->doFunc == NULL) {
! 694: printf("INVALID DAG: node %s has an undefined"
! 695: " doFunc.\n", nodes[i]->name);
! 696: retcode = 1;
! 697: goto validate_dag_out;
! 698: }
! 699: if (nodes[i]->undoFunc == NULL) {
! 700: printf("INVALID DAG: node %s has an undefined"
! 701: " doFunc.\n", nodes[i]->name);
! 702: retcode = 1;
! 703: goto validate_dag_out;
! 704: }
! 705: if (nodes[i]->numAntecedents != scount[nodes[i]->nodeNum]) {
! 706: printf("INVALID DAG: node %s has %d antecedents but"
! 707: " appears as a succedent %d times.\n",
! 708: nodes[i]->name, nodes[i]->numAntecedents,
! 709: scount[nodes[i]->nodeNum]);
! 710: retcode = 1;
! 711: goto validate_dag_out;
! 712: }
! 713: if (nodes[i]->numSuccedents != acount[nodes[i]->nodeNum]) {
! 714: printf("INVALID DAG: node %s has %d succedents but"
! 715: " appears as an antecedent %d times.\n",
! 716: nodes[i]->name, nodes[i]->numSuccedents,
! 717: acount[nodes[i]->nodeNum]);
! 718: retcode = 1;
! 719: goto validate_dag_out;
! 720: }
! 721: }
! 722:
! 723: if (dag_h->numCommitNodes != commitNodeCount) {
! 724: printf("INVALID DAG: incorrect commit node count. "
! 725: "hdr->numCommitNodes (%d) found (%d) commit nodes"
! 726: " in graph.\n",
! 727: dag_h->numCommitNodes, commitNodeCount);
! 728: retcode = 1;
! 729: goto validate_dag_out;
! 730: }
! 731:
! 732: validate_dag_out:
! 733: RF_Free(scount, nodecount * sizeof(int));
! 734: RF_Free(acount, nodecount * sizeof(int));
! 735: RF_Free(nodes, nodecount * sizeof(RF_DagNode_t *));
! 736: if (retcode)
! 737: rf_PrintDAGList(dag_h);
! 738:
! 739: if (rf_validateVisitedDebug)
! 740: rf_ValidateVisitedBits(dag_h);
! 741:
! 742: return (retcode);
! 743:
! 744: validate_dag_bad:
! 745: rf_PrintDAGList(dag_h);
! 746: return (retcode);
! 747: }
! 748:
! 749:
! 750: /*****************************************************************************
! 751: *
! 752: * Misc construction routines.
! 753: *
! 754: *****************************************************************************/
! 755:
! 756: void
! 757: rf_redirect_asm(RF_Raid_t *raidPtr, RF_AccessStripeMap_t *asmap)
! 758: {
! 759: int ds = (raidPtr->Layout.map->flags & RF_DISTRIBUTE_SPARE) ? 1 : 0;
! 760: int row = asmap->physInfo->row;
! 761: int fcol = raidPtr->reconControl[row]->fcol;
! 762: int srow = raidPtr->reconControl[row]->spareRow;
! 763: int scol = raidPtr->reconControl[row]->spareCol;
! 764: RF_PhysDiskAddr_t *pda;
! 765:
! 766: RF_ASSERT(raidPtr->status[row] == rf_rs_reconstructing);
! 767: for (pda = asmap->physInfo; pda; pda = pda->next) {
! 768: if (pda->col == fcol) {
! 769: if (rf_dagDebug) {
! 770: if (!rf_CheckRUReconstructed(
! 771: raidPtr->reconControl[row]->reconMap,
! 772: pda->startSector)) {
! 773: RF_PANIC();
! 774: }
! 775: }
! 776: /*printf("Remapped data for large write\n");*/
! 777: if (ds) {
! 778: raidPtr->Layout.map->MapSector(raidPtr,
! 779: pda->raidAddress, &pda->row, &pda->col,
! 780: &pda->startSector, RF_REMAP);
! 781: } else {
! 782: pda->row = srow;
! 783: pda->col = scol;
! 784: }
! 785: }
! 786: }
! 787: for (pda = asmap->parityInfo; pda; pda = pda->next) {
! 788: if (pda->col == fcol) {
! 789: if (rf_dagDebug) {
! 790: if (!rf_CheckRUReconstructed(
! 791: raidPtr->reconControl[row]->reconMap,
! 792: pda->startSector)) {
! 793: RF_PANIC();
! 794: }
! 795: }
! 796: }
! 797: if (ds) {
! 798: (raidPtr->Layout.map->MapParity) (raidPtr,
! 799: pda->raidAddress, &pda->row, &pda->col,
! 800: &pda->startSector, RF_REMAP);
! 801: } else {
! 802: pda->row = srow;
! 803: pda->col = scol;
! 804: }
! 805: }
! 806: }
! 807:
! 808:
! 809: /*
! 810: * This routine allocates read buffers and generates stripe maps for the
! 811: * regions of the array from the start of the stripe to the start of the
! 812: * access, and from the end of the access to the end of the stripe. It also
! 813: * computes and returns the number of DAG nodes needed to read all this data.
! 814: * Note that this routine does the wrong thing if the access is fully
! 815: * contained within one stripe unit, so we RF_ASSERT against this case at the
! 816: * start.
! 817: */
! 818: void
! 819: rf_MapUnaccessedPortionOfStripe(
! 820: RF_Raid_t *raidPtr,
! 821: RF_RaidLayout_t *layoutPtr, /* in: layout information */
! 822: RF_AccessStripeMap_t *asmap, /* in: access stripe map */
! 823: RF_DagHeader_t *dag_h, /* in: header of the dag */
! 824: /* to create */
! 825: RF_AccessStripeMapHeader_t **new_asm_h, /* in: ptr to array of 2 */
! 826: /* headers, to be */
! 827: /* filled in */
! 828: int *nRodNodes, /* out: num nodes to be */
! 829: /* generated to read */
! 830: /* unaccessed data */
! 831: char **sosBuffer, /* out: pointers to newly */
! 832: /* allocated buffer */
! 833: char **eosBuffer,
! 834: RF_AllocListElem_t *allocList
! 835: )
! 836: {
! 837: RF_RaidAddr_t sosRaidAddress, eosRaidAddress;
! 838: RF_SectorNum_t sosNumSector, eosNumSector;
! 839:
! 840: RF_ASSERT(asmap->numStripeUnitsAccessed > (layoutPtr->numDataCol / 2));
! 841: /*
! 842: * Generate an access map for the region of the array from start of
! 843: * stripe to start of access.
! 844: */
! 845: new_asm_h[0] = new_asm_h[1] = NULL;
! 846: *nRodNodes = 0;
! 847: if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->raidAddress)) {
! 848: sosRaidAddress = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
! 849: asmap->raidAddress);
! 850: sosNumSector = asmap->raidAddress - sosRaidAddress;
! 851: RF_MallocAndAdd(*sosBuffer, rf_RaidAddressToByte(raidPtr,
! 852: sosNumSector), (char *), allocList);
! 853: new_asm_h[0] = rf_MapAccess(raidPtr, sosRaidAddress,
! 854: sosNumSector, *sosBuffer, RF_DONT_REMAP);
! 855: new_asm_h[0]->next = dag_h->asmList;
! 856: dag_h->asmList = new_asm_h[0];
! 857: *nRodNodes += new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
! 858:
! 859: RF_ASSERT(new_asm_h[0]->stripeMap->next == NULL);
! 860: /* We're totally within one stripe here. */
! 861: if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
! 862: rf_redirect_asm(raidPtr, new_asm_h[0]->stripeMap);
! 863: }
! 864: /*
! 865: * Generate an access map for the region of the array from end of
! 866: * access to end of stripe.
! 867: */
! 868: if (!rf_RaidAddressStripeAligned(layoutPtr, asmap->endRaidAddress)) {
! 869: eosRaidAddress = asmap->endRaidAddress;
! 870: eosNumSector = rf_RaidAddressOfNextStripeBoundary(layoutPtr,
! 871: eosRaidAddress) - eosRaidAddress;
! 872: RF_MallocAndAdd(*eosBuffer, rf_RaidAddressToByte(raidPtr,
! 873: eosNumSector), (char *), allocList);
! 874: new_asm_h[1] = rf_MapAccess(raidPtr, eosRaidAddress,
! 875: eosNumSector, *eosBuffer, RF_DONT_REMAP);
! 876: new_asm_h[1]->next = dag_h->asmList;
! 877: dag_h->asmList = new_asm_h[1];
! 878: *nRodNodes += new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
! 879:
! 880: RF_ASSERT(new_asm_h[1]->stripeMap->next == NULL);
! 881: /* We're totally within one stripe here. */
! 882: if (asmap->flags & RF_ASM_REDIR_LARGE_WRITE)
! 883: rf_redirect_asm(raidPtr, new_asm_h[1]->stripeMap);
! 884: }
! 885: }
! 886:
! 887:
! 888: /* Returns non-zero if the indicated ranges of stripe unit offsets overlap. */
! 889: int
! 890: rf_PDAOverlap(RF_RaidLayout_t *layoutPtr, RF_PhysDiskAddr_t *src,
! 891: RF_PhysDiskAddr_t *dest)
! 892: {
! 893: RF_SectorNum_t soffs =
! 894: rf_StripeUnitOffset(layoutPtr, src->startSector);
! 895: RF_SectorNum_t doffs =
! 896: rf_StripeUnitOffset(layoutPtr, dest->startSector);
! 897: /* Use -1 to be sure we stay within SU. */
! 898: RF_SectorNum_t send =
! 899: rf_StripeUnitOffset(layoutPtr, src->startSector +
! 900: src->numSector - 1);
! 901: RF_SectorNum_t dend =
! 902: rf_StripeUnitOffset(layoutPtr, dest->startSector +
! 903: dest->numSector - 1);
! 904:
! 905: return ((RF_MAX(soffs, doffs) <= RF_MIN(send, dend)) ? 1 : 0);
! 906: }
! 907:
! 908:
! 909: /*
! 910: * GenerateFailedAccessASMs
! 911: *
! 912: * This routine figures out what portion of the stripe needs to be read
! 913: * to effect the degraded read or write operation. It's primary function
! 914: * is to identify everything required to recover the data, and then
! 915: * eliminate anything that is already being accessed by the user.
! 916: *
! 917: * The main result is two new ASMs, one for the region from the start of the
! 918: * stripe to the start of the access, and one for the region from the end of
! 919: * the access to the end of the stripe. These ASMs describe everything that
! 920: * needs to be read to effect the degraded access. Other results are:
! 921: * nXorBufs -- The total number of buffers that need to be XORed together
! 922: * to recover the lost data,
! 923: * rpBufPtr -- Ptr to a newly-allocated buffer to hold the parity. If NULL
! 924: * at entry, not allocated.
! 925: * overlappingPDAs --
! 926: * Describes which of the non-failed PDAs, in the user access,
! 927: * overlap data that needs to be read to effect recovery.
! 928: * overlappingPDAs[i]==1 if and only if, neglecting the failed
! 929: * PDA, the i'th pda in the input asm overlaps data that needs
! 930: * to be read for recovery.
! 931: */
! 932: /* in: asmap - ASM for the actual access, one stripe only. */
! 933: /* in: faildPDA - Which component of the access has failed. */
! 934: /* in: dag_h - Header of the DAG we're going to create. */
! 935: /* out: new_asm_h - The two new ASMs. */
! 936: /* out: nXorBufs - The total number of xor bufs required. */
! 937: /* out: rpBufPtr - A buffer for the parity read. */
! 938: void
! 939: rf_GenerateFailedAccessASMs(
! 940: RF_Raid_t *raidPtr,
! 941: RF_AccessStripeMap_t *asmap,
! 942: RF_PhysDiskAddr_t *failedPDA,
! 943: RF_DagHeader_t *dag_h,
! 944: RF_AccessStripeMapHeader_t **new_asm_h,
! 945: int *nXorBufs,
! 946: char **rpBufPtr,
! 947: char *overlappingPDAs,
! 948: RF_AllocListElem_t *allocList
! 949: )
! 950: {
! 951: RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
! 952:
! 953: /* s=start, e=end, s=stripe, a=access, f=failed, su=stripe unit */
! 954: RF_RaidAddr_t sosAddr, sosEndAddr, eosStartAddr, eosAddr;
! 955:
! 956: RF_SectorCount_t numSect[2], numParitySect;
! 957: RF_PhysDiskAddr_t *pda;
! 958: char *rdBuf, *bufP;
! 959: int foundit, i;
! 960:
! 961: bufP = NULL;
! 962: foundit = 0;
! 963: /*
! 964: * First compute the following raid addresses:
! 965: * - Start of stripe
! 966: * - (sosAddr) MIN(start of access, start of failed SU)
! 967: * - (sosEndAddr) MAX(end of access, end of failed SU)
! 968: * - (eosStartAddr) end of stripe (i.e. start of next stripe)
! 969: * (eosAddr)
! 970: */
! 971: sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
! 972: asmap->raidAddress);
! 973: sosEndAddr = RF_MIN(asmap->raidAddress,
! 974: rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr,
! 975: failedPDA->raidAddress));
! 976: eosStartAddr = RF_MAX(asmap->endRaidAddress,
! 977: rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr,
! 978: failedPDA->raidAddress));
! 979: eosAddr = rf_RaidAddressOfNextStripeBoundary(layoutPtr,
! 980: asmap->raidAddress);
! 981:
! 982: /*
! 983: * Now generate access stripe maps for each of the above regions of
! 984: * the stripe. Use a dummy (NULL) buf ptr for now.
! 985: */
! 986:
! 987: new_asm_h[0] = (sosAddr != sosEndAddr) ?
! 988: rf_MapAccess(raidPtr, sosAddr, sosEndAddr - sosAddr, NULL,
! 989: RF_DONT_REMAP) : NULL;
! 990: new_asm_h[1] = (eosStartAddr != eosAddr) ?
! 991: rf_MapAccess(raidPtr, eosStartAddr, eosAddr - eosStartAddr, NULL,
! 992: RF_DONT_REMAP) : NULL;
! 993:
! 994: /*
! 995: * Walk through the PDAs and range-restrict each SU to the region of
! 996: * the SU touched on the failed PDA. Also compute total data buffer
! 997: * space requirements in this step. Ignore the parity for now.
! 998: */
! 999:
! 1000: numSect[0] = numSect[1] = 0;
! 1001: if (new_asm_h[0]) {
! 1002: new_asm_h[0]->next = dag_h->asmList;
! 1003: dag_h->asmList = new_asm_h[0];
! 1004: for (pda = new_asm_h[0]->stripeMap->physInfo; pda;
! 1005: pda = pda->next) {
! 1006: rf_RangeRestrictPDA(raidPtr, failedPDA, pda,
! 1007: RF_RESTRICT_NOBUFFER, 0);
! 1008: numSect[0] += pda->numSector;
! 1009: }
! 1010: }
! 1011: if (new_asm_h[1]) {
! 1012: new_asm_h[1]->next = dag_h->asmList;
! 1013: dag_h->asmList = new_asm_h[1];
! 1014: for (pda = new_asm_h[1]->stripeMap->physInfo;
! 1015: pda; pda = pda->next) {
! 1016: rf_RangeRestrictPDA(raidPtr, failedPDA, pda,
! 1017: RF_RESTRICT_NOBUFFER, 0);
! 1018: numSect[1] += pda->numSector;
! 1019: }
! 1020: }
! 1021: numParitySect = failedPDA->numSector;
! 1022:
! 1023: /*
! 1024: * Allocate buffer space for the data & parity we have to read to
! 1025: * recover from the failure.
! 1026: */
! 1027:
! 1028: if (numSect[0] + numSect[1] + ((rpBufPtr) ? numParitySect : 0)) {
! 1029: /* Don't allocate parity buf if not needed. */
! 1030: RF_MallocAndAdd(rdBuf, rf_RaidAddressToByte(raidPtr,
! 1031: numSect[0] + numSect[1] + numParitySect), (char *),
! 1032: allocList);
! 1033: bufP = rdBuf;
! 1034: if (rf_degDagDebug)
! 1035: printf("Newly allocated buffer (%d bytes) is 0x%lx\n",
! 1036: (int) rf_RaidAddressToByte(raidPtr,
! 1037: numSect[0] + numSect[1] + numParitySect),
! 1038: (unsigned long) bufP);
! 1039: }
! 1040: /*
! 1041: * Now walk through the pdas one last time and assign buffer pointers
! 1042: * (ugh!). Again, ignore the parity. Also, count nodes to find out
! 1043: * how many bufs need to be xored together.
! 1044: */
! 1045: (*nXorBufs) = 1; /* In read case, 1 is for parity. */
! 1046: /* In write case, 1 is for failed data. */
! 1047: if (new_asm_h[0]) {
! 1048: for (pda = new_asm_h[0]->stripeMap->physInfo; pda;
! 1049: pda = pda->next) {
! 1050: pda->bufPtr = bufP;
! 1051: bufP += rf_RaidAddressToByte(raidPtr, pda->numSector);
! 1052: }
! 1053: *nXorBufs += new_asm_h[0]->stripeMap->numStripeUnitsAccessed;
! 1054: }
! 1055: if (new_asm_h[1]) {
! 1056: for (pda = new_asm_h[1]->stripeMap->physInfo; pda;
! 1057: pda = pda->next) {
! 1058: pda->bufPtr = bufP;
! 1059: bufP += rf_RaidAddressToByte(raidPtr, pda->numSector);
! 1060: }
! 1061: (*nXorBufs) += new_asm_h[1]->stripeMap->numStripeUnitsAccessed;
! 1062: }
! 1063: if (rpBufPtr)
! 1064: /* The rest of the buffer is for parity. */
! 1065: *rpBufPtr = bufP;
! 1066:
! 1067: /*
! 1068: * The last step is to figure out how many more distinct buffers need
! 1069: * to get xor'd to produce the missing unit. there's one for each
! 1070: * user-data read node that overlaps the portion of the failed unit
! 1071: * being accessed.
! 1072: */
! 1073:
! 1074: for (foundit = i = 0, pda = asmap->physInfo;
! 1075: pda; i++, pda = pda->next) {
! 1076: if (pda == failedPDA) {
! 1077: i--;
! 1078: foundit = 1;
! 1079: continue;
! 1080: }
! 1081: if (rf_PDAOverlap(layoutPtr, pda, failedPDA)) {
! 1082: overlappingPDAs[i] = 1;
! 1083: (*nXorBufs)++;
! 1084: }
! 1085: }
! 1086: if (!foundit) {
! 1087: RF_ERRORMSG("GenerateFailedAccessASMs: did not find failedPDA"
! 1088: " in asm list.\n");
! 1089: RF_ASSERT(0);
! 1090: }
! 1091: if (rf_degDagDebug) {
! 1092: if (new_asm_h[0]) {
! 1093: printf("First asm:\n");
! 1094: rf_PrintFullAccessStripeMap(new_asm_h[0], 1);
! 1095: }
! 1096: if (new_asm_h[1]) {
! 1097: printf("Second asm:\n");
! 1098: rf_PrintFullAccessStripeMap(new_asm_h[1], 1);
! 1099: }
! 1100: }
! 1101: }
! 1102:
! 1103:
! 1104: /*
! 1105: * Adjust the offset and number of sectors in the destination pda so that
! 1106: * it covers at most the region of the SU covered by the source PDA. This
! 1107: * is exclusively a restriction: the number of sectors indicated by the
! 1108: * target PDA can only shrink.
! 1109: *
! 1110: * For example: s = sectors within SU indicated by source PDA
! 1111: * d = sectors within SU indicated by dest PDA
! 1112: * r = results, stored in dest PDA
! 1113: *
! 1114: * |--------------- one stripe unit ---------------------|
! 1115: * | sssssssssssssssssssssssssssssssss |
! 1116: * | ddddddddddddddddddddddddddddddddddddddddddddd |
! 1117: * | rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr |
! 1118: *
! 1119: * Another example:
! 1120: *
! 1121: * |--------------- one stripe unit ---------------------|
! 1122: * | sssssssssssssssssssssssssssssssss |
! 1123: * | ddddddddddddddddddddddd |
! 1124: * | rrrrrrrrrrrrrrrr |
! 1125: *
! 1126: */
! 1127: void
! 1128: rf_RangeRestrictPDA(RF_Raid_t *raidPtr, RF_PhysDiskAddr_t *src,
! 1129: RF_PhysDiskAddr_t *dest, int dobuffer, int doraidaddr)
! 1130: {
! 1131: RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
! 1132: RF_SectorNum_t soffs =
! 1133: rf_StripeUnitOffset(layoutPtr, src->startSector);
! 1134: RF_SectorNum_t doffs =
! 1135: rf_StripeUnitOffset(layoutPtr, dest->startSector);
! 1136: RF_SectorNum_t send =
! 1137: rf_StripeUnitOffset(layoutPtr, src->startSector +
! 1138: src->numSector - 1); /* Use -1 to be sure we stay within SU. */
! 1139: RF_SectorNum_t dend =
! 1140: rf_StripeUnitOffset(layoutPtr, dest->startSector +
! 1141: dest->numSector - 1);
! 1142: RF_SectorNum_t subAddr =
! 1143: rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr,
! 1144: dest->startSector); /* Stripe unit boundary. */
! 1145:
! 1146: dest->startSector = subAddr + RF_MAX(soffs, doffs);
! 1147: dest->numSector = subAddr + RF_MIN(send, dend) + 1 - dest->startSector;
! 1148:
! 1149: if (dobuffer)
! 1150: dest->bufPtr += (soffs > doffs) ?
! 1151: rf_RaidAddressToByte(raidPtr, soffs - doffs) : 0;
! 1152: if (doraidaddr) {
! 1153: dest->raidAddress =
! 1154: rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr,
! 1155: dest->raidAddress) +
! 1156: rf_StripeUnitOffset(layoutPtr, dest->startSector);
! 1157: }
! 1158: }
! 1159:
! 1160: /*
! 1161: * Want the highest of these primes to be the largest one
! 1162: * less than the max expected number of columns (won't hurt
! 1163: * to be too small or too large, but won't be optimal, either)
! 1164: * --jimz
! 1165: */
! 1166: #define NLOWPRIMES 8
! 1167: static int lowprimes[NLOWPRIMES] = {2, 3, 5, 7, 11, 13, 17, 19};
! 1168:
! 1169: /*****************************************************************************
! 1170: * Compute the workload shift factor. (chained declustering)
! 1171: *
! 1172: * Return nonzero if access should shift to secondary, otherwise,
! 1173: * access is to primary.
! 1174: *****************************************************************************/
! 1175: int
! 1176: rf_compute_workload_shift(RF_Raid_t *raidPtr, RF_PhysDiskAddr_t *pda)
! 1177: {
! 1178: /*
! 1179: * Variables:
! 1180: * d = Column of disk containing primary.
! 1181: * f = Column of failed disk.
! 1182: * n = Number of disks in array.
! 1183: * sd = "shift distance"
! 1184: * (number of columns that d is to the right of f).
! 1185: * row = Row of array the access is in.
! 1186: * v = Numerator of redirection ratio.
! 1187: * k = Denominator of redirection ratio.
! 1188: */
! 1189: RF_RowCol_t d, f, sd, row, n;
! 1190: int k, v, ret, i;
! 1191:
! 1192: row = pda->row;
! 1193: n = raidPtr->numCol;
! 1194:
! 1195: /* Assign column of primary copy to d. */
! 1196: d = pda->col;
! 1197:
! 1198: /* Assign column of dead disk to f. */
! 1199: for (f = 0; ((!RF_DEAD_DISK(raidPtr->Disks[row][f].status)) &&
! 1200: (f < n)); f++);
! 1201:
! 1202: RF_ASSERT(f < n);
! 1203: RF_ASSERT(f != d);
! 1204:
! 1205: sd = (f > d) ? (n + d - f) : (d - f);
! 1206: RF_ASSERT(sd < n);
! 1207:
! 1208: /*
! 1209: * v of every k accesses should be redirected.
! 1210: *
! 1211: * v/k := (n-1-sd)/(n-1)
! 1212: */
! 1213: v = (n - 1 - sd);
! 1214: k = (n - 1);
! 1215:
! 1216: #if 1
! 1217: /*
! 1218: * XXX
! 1219: * Is this worth it ?
! 1220: *
! 1221: * Now reduce the fraction, by repeatedly factoring
! 1222: * out primes (just like they teach in elementary school !).
! 1223: */
! 1224: for (i = 0; i < NLOWPRIMES; i++) {
! 1225: if (lowprimes[i] > v)
! 1226: break;
! 1227: while (((v % lowprimes[i]) == 0) && ((k % lowprimes[i]) == 0)) {
! 1228: v /= lowprimes[i];
! 1229: k /= lowprimes[i];
! 1230: }
! 1231: }
! 1232: #endif
! 1233:
! 1234: raidPtr->hist_diskreq[row][d]++;
! 1235: if (raidPtr->hist_diskreq[row][d] > v) {
! 1236: ret = 0; /* Do not redirect. */
! 1237: } else {
! 1238: ret = 1; /* Redirect. */
! 1239: }
! 1240:
! 1241: #if 0
! 1242: printf("d=%d f=%d sd=%d v=%d k=%d ret=%d h=%d\n", d, f, sd, v, k, ret,
! 1243: raidPtr->hist_diskreq[row][d]);
! 1244: #endif
! 1245:
! 1246: if (raidPtr->hist_diskreq[row][d] >= k) {
! 1247: /* Reset counter. */
! 1248: raidPtr->hist_diskreq[row][d] = 0;
! 1249: }
! 1250: return (ret);
! 1251: }
! 1252:
! 1253: /*
! 1254: * Disk selection routines.
! 1255: */
! 1256:
! 1257: /*
! 1258: * Select the disk with the shortest queue from a mirror pair.
! 1259: * Both the disk I/Os queued in RAIDframe as well as those at the physical
! 1260: * disk are counted as members of the "queue".
! 1261: */
! 1262: void
! 1263: rf_SelectMirrorDiskIdle(RF_DagNode_t *node)
! 1264: {
! 1265: RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr;
! 1266: RF_RowCol_t rowData, colData, rowMirror, colMirror;
! 1267: int dataQueueLength, mirrorQueueLength, usemirror;
! 1268: RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p;
! 1269: RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p;
! 1270: RF_PhysDiskAddr_t *tmp_pda;
! 1271: RF_RaidDisk_t **disks = raidPtr->Disks;
! 1272: RF_DiskQueue_t **dqs = raidPtr->Queues, *dataQueue, *mirrorQueue;
! 1273:
! 1274: /* Return the [row col] of the disk with the shortest queue. */
! 1275: rowData = data_pda->row;
! 1276: colData = data_pda->col;
! 1277: rowMirror = mirror_pda->row;
! 1278: colMirror = mirror_pda->col;
! 1279: dataQueue = &(dqs[rowData][colData]);
! 1280: mirrorQueue = &(dqs[rowMirror][colMirror]);
! 1281:
! 1282: #ifdef RF_LOCK_QUEUES_TO_READ_LEN
! 1283: RF_LOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle");
! 1284: #endif /* RF_LOCK_QUEUES_TO_READ_LEN */
! 1285: dataQueueLength = dataQueue->queueLength + dataQueue->numOutstanding;
! 1286: #ifdef RF_LOCK_QUEUES_TO_READ_LEN
! 1287: RF_UNLOCK_QUEUE_MUTEX(dataQueue, "SelectMirrorDiskIdle");
! 1288: RF_LOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle");
! 1289: #endif /* RF_LOCK_QUEUES_TO_READ_LEN */
! 1290: mirrorQueueLength = mirrorQueue->queueLength +
! 1291: mirrorQueue->numOutstanding;
! 1292: #ifdef RF_LOCK_QUEUES_TO_READ_LEN
! 1293: RF_UNLOCK_QUEUE_MUTEX(mirrorQueue, "SelectMirrorDiskIdle");
! 1294: #endif /* RF_LOCK_QUEUES_TO_READ_LEN */
! 1295:
! 1296: usemirror = 0;
! 1297: if (RF_DEAD_DISK(disks[rowMirror][colMirror].status)) {
! 1298: usemirror = 0;
! 1299: } else
! 1300: if (RF_DEAD_DISK(disks[rowData][colData].status)) {
! 1301: usemirror = 1;
! 1302: } else
! 1303: if (raidPtr->parity_good == RF_RAID_DIRTY) {
! 1304: /* Trust only the main disk. */
! 1305: usemirror = 0;
! 1306: } else
! 1307: if (dataQueueLength < mirrorQueueLength) {
! 1308: usemirror = 0;
! 1309: } else
! 1310: if (mirrorQueueLength < dataQueueLength) {
! 1311: usemirror = 1;
! 1312: } else {
! 1313: /* Queues are equal length. */
! 1314: /* Attempt cleverness. */
! 1315: if (SNUM_DIFF(dataQueue
! 1316: ->last_deq_sector, data_pda
! 1317: ->startSector) <=
! 1318: SNUM_DIFF(mirrorQueue
! 1319: ->last_deq_sector, mirror_pda
! 1320: ->startSector)) {
! 1321: usemirror = 0;
! 1322: } else {
! 1323: usemirror = 1;
! 1324: }
! 1325: }
! 1326:
! 1327: if (usemirror) {
! 1328: /* Use mirror (parity) disk, swap params 0 & 4. */
! 1329: tmp_pda = data_pda;
! 1330: node->params[0].p = mirror_pda;
! 1331: node->params[4].p = tmp_pda;
! 1332: } else {
! 1333: /* Use data disk, leave param 0 unchanged. */
! 1334: }
! 1335: /*printf("dataQueueLength %d, mirrorQueueLength %d\n", dataQueueLength,
! 1336: mirrorQueueLength);*/
! 1337: }
! 1338:
! 1339: /*
! 1340: * Do simple partitioning. This assumes that
! 1341: * the data and parity disks are laid out identically.
! 1342: */
! 1343: void
! 1344: rf_SelectMirrorDiskPartition(RF_DagNode_t *node)
! 1345: {
! 1346: RF_Raid_t *raidPtr = (RF_Raid_t *) node->dagHdr->raidPtr;
! 1347: RF_RowCol_t rowData, colData, rowMirror, colMirror;
! 1348: RF_PhysDiskAddr_t *data_pda = (RF_PhysDiskAddr_t *) node->params[0].p;
! 1349: RF_PhysDiskAddr_t *mirror_pda = (RF_PhysDiskAddr_t *) node->params[4].p;
! 1350: RF_PhysDiskAddr_t *tmp_pda;
! 1351: RF_RaidDisk_t **disks = raidPtr->Disks;
! 1352: RF_DiskQueue_t **dqs = raidPtr->Queues, *dataQueue, *mirrorQueue;
! 1353: int usemirror;
! 1354:
! 1355: /* Return the [row col] of the disk with the shortest queue. */
! 1356: rowData = data_pda->row;
! 1357: colData = data_pda->col;
! 1358: rowMirror = mirror_pda->row;
! 1359: colMirror = mirror_pda->col;
! 1360: dataQueue = &(dqs[rowData][colData]);
! 1361: mirrorQueue = &(dqs[rowMirror][colMirror]);
! 1362:
! 1363: usemirror = 0;
! 1364: if (RF_DEAD_DISK(disks[rowMirror][colMirror].status)) {
! 1365: usemirror = 0;
! 1366: } else
! 1367: if (RF_DEAD_DISK(disks[rowData][colData].status)) {
! 1368: usemirror = 1;
! 1369: } else
! 1370: if (raidPtr->parity_good == RF_RAID_DIRTY) {
! 1371: /* Trust only the main disk. */
! 1372: usemirror = 0;
! 1373: } else
! 1374: if (data_pda->startSector <
! 1375: (disks[rowData][colData].numBlocks / 2)) {
! 1376: usemirror = 0;
! 1377: } else {
! 1378: usemirror = 1;
! 1379: }
! 1380:
! 1381: if (usemirror) {
! 1382: /* Use mirror (parity) disk, swap params 0 & 4. */
! 1383: tmp_pda = data_pda;
! 1384: node->params[0].p = mirror_pda;
! 1385: node->params[4].p = tmp_pda;
! 1386: } else {
! 1387: /* Use data disk, leave param 0 unchanged. */
! 1388: }
! 1389: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_dagutils.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe