Annotation of sys/dev/raidframe/rf_pqdegdags.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: rf_pqdegdags.c,v 1.5 2002/12/16 07:01:04 tdeval Exp $ */
! 2: /* $NetBSD: rf_pqdegdags.c,v 1.5 1999/08/15 02:36:40 oster Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1995 Carnegie-Mellon University.
! 6: * All rights reserved.
! 7: *
! 8: * Author: Daniel Stodolsky
! 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: * rf_pqdegdags.c
! 33: * Degraded mode dags for double fault cases.
! 34: */
! 35:
! 36:
! 37: #include "rf_archs.h"
! 38:
! 39: #if (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0)
! 40:
! 41: #include "rf_types.h"
! 42: #include "rf_raid.h"
! 43: #include "rf_dag.h"
! 44: #include "rf_dagdegrd.h"
! 45: #include "rf_dagdegwr.h"
! 46: #include "rf_dagfuncs.h"
! 47: #include "rf_dagutils.h"
! 48: #include "rf_etimer.h"
! 49: #include "rf_acctrace.h"
! 50: #include "rf_general.h"
! 51: #include "rf_pqdegdags.h"
! 52: #include "rf_pq.h"
! 53:
! 54: void rf_applyPDA(RF_Raid_t *, RF_PhysDiskAddr_t *, RF_PhysDiskAddr_t *,
! 55: RF_PhysDiskAddr_t *, void *);
! 56:
! 57: /*
! 58: * Two data drives have failed, and we are doing a read that covers one of them.
! 59: * We may also be reading some of the surviving drives.
! 60: */
! 61:
! 62:
! 63: /*****************************************************************************
! 64: *
! 65: * Creates a DAG to perform a degraded-mode read of data within one stripe.
! 66: * This DAG is as follows:
! 67: *
! 68: * Hdr
! 69: * |
! 70: * Block
! 71: * / / \ \ \ \
! 72: * Rud ... Rud Rrd ... Rrd Rp Rq
! 73: * | \ | \ | \ | \ | \ | \
! 74: *
! 75: * | |
! 76: * Unblock X
! 77: * \ /
! 78: * ------ T ------
! 79: *
! 80: * Each R node is a successor of the L node.
! 81: * One successor arc from each R node goes to U, and the other to X.
! 82: * There is one Rud for each chunk of surviving user data requested by the
! 83: * user, and one Rrd for each chunk of surviving user data _not_ being read
! 84: * by the user.
! 85: * R = read, ud = user data, rd = recovery (surviving) data, p = P data,
! 86: * q = Qdata, X = pq recovery node, T = terminate
! 87: *
! 88: * The block & unblock nodes are leftovers from a previous version. They
! 89: * do nothing, but I haven't deleted them because it would be a tremendous
! 90: * effort to put them back in.
! 91: *
! 92: * Note: The target buffer for the XOR node is set to the actual user buffer
! 93: * where the failed data is supposed to end up. This buffer is zero'd by the
! 94: * code here. Thus, if you create a degraded read dag, use it, and then
! 95: * re-use. You have to be sure to zero the target buffer prior to the re-use.
! 96: *
! 97: * Every buffer read is passed to the pq recovery node, whose job it is to
! 98: * sort out what's needed and what's not.
! 99: *****************************************************************************/
! 100:
! 101: /* Init a disk node with 2 successors and one predecessor. */
! 102: #define INIT_DISK_NODE(node,name) \
! 103: do { \
! 104: rf_InitNode(node, rf_wait, RF_FALSE, rf_DiskReadFunc, \
! 105: rf_DiskReadUndoFunc, rf_GenericWakeupFunc, 2, 1, 4, 0, \
! 106: dag_h, name, allocList); \
! 107: (node)->succedents[0] = unblockNode; \
! 108: (node)->succedents[1] = recoveryNode; \
! 109: (node)->antecedents[0] = blockNode; \
! 110: (node)->antType[0] = rf_control; \
! 111: } while (0)
! 112:
! 113: #define DISK_NODE_PARAMS(_node_,_p_) \
! 114: do { \
! 115: (_node_).params[0].p = _p_ ; \
! 116: (_node_).params[1].p = (_p_)->bufPtr; \
! 117: (_node_).params[2].v = parityStripeID; \
! 118: (_node_).params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, \
! 119: 0, 0, which_ru); \
! 120: } while (0)
! 121:
! 122: #define DISK_NODE_PDA(node) ((node)->params[0].p)
! 123:
! 124: RF_CREATE_DAG_FUNC_DECL(rf_PQ_DoubleDegRead)
! 125: {
! 126: rf_DoubleDegRead(raidPtr, asmap, dag_h, bp, flags, allocList,
! 127: "Rq", "PQ Recovery", rf_PQDoubleRecoveryFunc);
! 128: }
! 129:
! 130: void
! 131: rf_applyPDA(RF_Raid_t *raidPtr, RF_PhysDiskAddr_t *pda,
! 132: RF_PhysDiskAddr_t *ppda, RF_PhysDiskAddr_t *qpda, void *bp)
! 133: {
! 134: RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
! 135: RF_RaidAddr_t s0off = rf_StripeUnitOffset(layoutPtr, ppda->startSector);
! 136: RF_SectorCount_t s0len = ppda->numSector, len;
! 137: RF_SectorNum_t suoffset;
! 138: unsigned coeff;
! 139: char *pbuf = ppda->bufPtr;
! 140: char *qbuf = qpda->bufPtr;
! 141: char *buf;
! 142: int delta;
! 143:
! 144: suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
! 145: len = pda->numSector;
! 146: /* See if pda intersects a recovery pda. */
! 147: if ((suoffset < s0off + s0len) && (suoffset + len > s0off)) {
! 148: buf = pda->bufPtr;
! 149: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 150: pda->raidAddress);
! 151: coeff = (coeff % raidPtr->Layout.numDataCol);
! 152:
! 153: if (suoffset < s0off) {
! 154: delta = s0off - suoffset;
! 155: buf += rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 156: delta);
! 157: suoffset = s0off;
! 158: len -= delta;
! 159: }
! 160: if (suoffset > s0off) {
! 161: delta = suoffset - s0off;
! 162: pbuf += rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 163: delta);
! 164: qbuf += rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 165: delta);
! 166: }
! 167: if ((suoffset + len) > (s0len + s0off))
! 168: len = s0len + s0off - suoffset;
! 169:
! 170: /* Src, dest, len. */
! 171: rf_bxor(buf, pbuf, rf_RaidAddressToByte(raidPtr, len), bp);
! 172:
! 173: /* Dest, src, len, coeff. */
! 174: rf_IncQ((unsigned long *) qbuf, (unsigned long *) buf,
! 175: rf_RaidAddressToByte(raidPtr, len), coeff);
! 176: }
! 177: }
! 178:
! 179:
! 180: /*
! 181: * Recover data in the case of a double failure. There can be two
! 182: * result buffers, one for each chunk of data trying to be recovered.
! 183: * The params are pda's that have not been range restricted or otherwise
! 184: * politely massaged - this should be done here. The last params are the
! 185: * pdas of P and Q, followed by the raidPtr. The list can look like
! 186: *
! 187: * pda, pda, ..., p pda, q pda, raidptr, asm
! 188: *
! 189: * or
! 190: *
! 191: * pda, pda, ..., p_1 pda, p_2 pda, q_1 pda, q_2 pda, raidptr, asm
! 192: *
! 193: * depending on whether two chunks of recovery data were required.
! 194: *
! 195: * The second condition only arises if there are two failed buffers
! 196: * whose lengths do not add up a stripe unit.
! 197: */
! 198:
! 199: int
! 200: rf_PQDoubleRecoveryFunc(RF_DagNode_t *node)
! 201: {
! 202: int np = node->numParams;
! 203: RF_AccessStripeMap_t *asmap =
! 204: (RF_AccessStripeMap_t *) node->params[np - 1].p;
! 205: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 2].p;
! 206: RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & (raidPtr->Layout);
! 207: int d, i;
! 208: unsigned coeff;
! 209: RF_RaidAddr_t sosAddr, suoffset;
! 210: RF_SectorCount_t len, secPerSU = layoutPtr->sectorsPerStripeUnit;
! 211: int two = 0;
! 212: RF_PhysDiskAddr_t *ppda, *ppda2, *qpda, *qpda2, *pda, npda;
! 213: char *buf;
! 214: int numDataCol = layoutPtr->numDataCol;
! 215: RF_Etimer_t timer;
! 216: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 217:
! 218: RF_ETIMER_START(timer);
! 219:
! 220: if (asmap->failedPDAs[1] &&
! 221: (asmap->failedPDAs[1]->numSector +
! 222: asmap->failedPDAs[0]->numSector < secPerSU)) {
! 223: RF_ASSERT(0);
! 224: ppda = node->params[np - 6].p;
! 225: ppda2 = node->params[np - 5].p;
! 226: qpda = node->params[np - 4].p;
! 227: qpda2 = node->params[np - 3].p;
! 228: d = (np - 6);
! 229: two = 1;
! 230: } else {
! 231: ppda = node->params[np - 4].p;
! 232: qpda = node->params[np - 3].p;
! 233: d = (np - 4);
! 234: }
! 235:
! 236: for (i = 0; i < d; i++) {
! 237: pda = node->params[i].p;
! 238: buf = pda->bufPtr;
! 239: suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
! 240: len = pda->numSector;
! 241: coeff = rf_RaidAddressToStripeUnitID(layoutPtr,
! 242: pda->raidAddress);
! 243: /* Compute the data unit offset within the column. */
! 244: coeff = (coeff % raidPtr->Layout.numDataCol);
! 245: /* See if pda intersects a recovery pda. */
! 246: rf_applyPDA(raidPtr, pda, ppda, qpda, node->dagHdr->bp);
! 247: if (two)
! 248: rf_applyPDA(raidPtr, pda, ppda, qpda, node->dagHdr->bp);
! 249: }
! 250:
! 251: /*
! 252: * Ok, we got the parity back to the point where we can recover. We
! 253: * now need to determine the coeff of the columns that need to be
! 254: * recovered. We can also only need to recover a single stripe unit.
! 255: */
! 256:
! 257: if (asmap->failedPDAs[1] == NULL) { /*
! 258: * Only a single stripe unit
! 259: * to recover.
! 260: */
! 261: pda = asmap->failedPDAs[0];
! 262: sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
! 263: asmap->raidAddress);
! 264: /* Need to determine the column of the other failed disk. */
! 265: coeff = rf_RaidAddressToStripeUnitID(layoutPtr,
! 266: pda->raidAddress);
! 267: /* Compute the data unit offset within the column. */
! 268: coeff = (coeff % raidPtr->Layout.numDataCol);
! 269: for (i = 0; i < numDataCol; i++) {
! 270: npda.raidAddress = sosAddr + (i * secPerSU);
! 271: (raidPtr->Layout.map->MapSector) (raidPtr,
! 272: npda.raidAddress, &(npda.row), &(npda.col),
! 273: &(npda.startSector), 0);
! 274: /* Skip over dead disks. */
! 275: if (RF_DEAD_DISK(raidPtr->Disks[npda.row][npda.col]
! 276: .status))
! 277: if (i != coeff)
! 278: break;
! 279: }
! 280: RF_ASSERT(i < numDataCol);
! 281: RF_ASSERT(two == 0);
! 282: /*
! 283: * Recover the data. Since we need only to recover one
! 284: * column, we overwrite the parity with the other one.
! 285: */
! 286: if (coeff < i) /* Recovering 'a'. */
! 287: rf_PQ_recover((unsigned long *) ppda->bufPtr,
! 288: (unsigned long *) qpda->bufPtr,
! 289: (unsigned long *) pda->bufPtr,
! 290: (unsigned long *) ppda->bufPtr,
! 291: rf_RaidAddressToByte(raidPtr, pda->numSector),
! 292: coeff, i);
! 293: else /* Recovering 'b'. */
! 294: rf_PQ_recover((unsigned long *) ppda->bufPtr,
! 295: (unsigned long *) qpda->bufPtr,
! 296: (unsigned long *) ppda->bufPtr,
! 297: (unsigned long *) pda->bufPtr,
! 298: rf_RaidAddressToByte(raidPtr, pda->numSector),
! 299: i, coeff);
! 300: } else
! 301: RF_PANIC();
! 302:
! 303: RF_ETIMER_STOP(timer);
! 304: RF_ETIMER_EVAL(timer);
! 305: if (tracerec)
! 306: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 307: rf_GenericWakeupFunc(node, 0);
! 308: return (0);
! 309: }
! 310:
! 311: int
! 312: rf_PQWriteDoubleRecoveryFunc(RF_DagNode_t *node)
! 313: {
! 314: /*
! 315: * The situation:
! 316: *
! 317: * We are doing a write that hits only one failed data unit. The other
! 318: * failed data unit is not being overwritten, so we need to generate
! 319: * it.
! 320: *
! 321: * For the moment, we assume all the nonfailed data being written is in
! 322: * the shadow of the failed data unit. (i.e., either a single data
! 323: * unit write or the entire failed stripe unit is being overwritten.)
! 324: *
! 325: * Recovery strategy: apply the recovery data to the parity and Q.
! 326: * Use P & Q to recover the second failed data unit in P. Zero fill
! 327: * Q, then apply the recovered data to P. Then apply the data being
! 328: * written to the failed drive. Then walk through the surviving drives,
! 329: * applying new data when it exists, othewise the recovery data.
! 330: * Quite a mess.
! 331: *
! 332: *
! 333: * The params:
! 334: *
! 335: * read pda0, read pda1, ..., read pda (numDataCol-3),
! 336: * write pda0, ..., write pda (numStripeUnitAccess - numDataFailed),
! 337: * failed pda, raidPtr, asmap
! 338: */
! 339:
! 340: int np = node->numParams;
! 341: RF_AccessStripeMap_t *asmap = (RF_AccessStripeMap_t *)
! 342: node->params[np - 1].p;
! 343: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 2].p;
! 344: RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & (raidPtr->Layout);
! 345: int i;
! 346: RF_RaidAddr_t sosAddr;
! 347: unsigned coeff;
! 348: RF_StripeCount_t secPerSU = layoutPtr->sectorsPerStripeUnit;
! 349: RF_PhysDiskAddr_t *ppda, *qpda, *pda, npda;
! 350: int numDataCol = layoutPtr->numDataCol;
! 351: RF_Etimer_t timer;
! 352: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 353:
! 354: RF_ASSERT(node->numResults == 2);
! 355: RF_ASSERT(asmap->failedPDAs[1] == NULL);
! 356: RF_ETIMER_START(timer);
! 357: ppda = node->results[0];
! 358: qpda = node->results[1];
! 359: /* apply the recovery data */
! 360: for (i = 0; i < numDataCol - 2; i++)
! 361: rf_applyPDA(raidPtr, node->params[i].p, ppda, qpda,
! 362: node->dagHdr->bp);
! 363:
! 364: /* Determine the other failed data unit. */
! 365: pda = asmap->failedPDAs[0];
! 366: sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
! 367: asmap->raidAddress);
! 368: /* Need to determine the column of the other failed disk. */
! 369: coeff = rf_RaidAddressToStripeUnitID(layoutPtr, pda->raidAddress);
! 370: /* Compute the data unit offset within the column. */
! 371: coeff = (coeff % raidPtr->Layout.numDataCol);
! 372: for (i = 0; i < numDataCol; i++) {
! 373: npda.raidAddress = sosAddr + (i * secPerSU);
! 374: (raidPtr->Layout.map->MapSector) (raidPtr, npda.raidAddress,
! 375: &(npda.row), &(npda.col), &(npda.startSector), 0);
! 376: /* Skip over dead disks. */
! 377: if (RF_DEAD_DISK(raidPtr->Disks[npda.row][npda.col].status))
! 378: if (i != coeff)
! 379: break;
! 380: }
! 381: RF_ASSERT(i < numDataCol);
! 382: /*
! 383: * Recover the data. The column we want to recover, we write over the
! 384: * parity. The column we don't care about, we dump in q.
! 385: */
! 386: if (coeff < i) /* Recovering 'a'. */
! 387: rf_PQ_recover((unsigned long *) ppda->bufPtr,
! 388: (unsigned long *) qpda->bufPtr,
! 389: (unsigned long *) ppda->bufPtr,
! 390: (unsigned long *) qpda->bufPtr,
! 391: rf_RaidAddressToByte(raidPtr, pda->numSector), coeff, i);
! 392: else /* Recovering 'b'. */
! 393: rf_PQ_recover((unsigned long *) ppda->bufPtr,
! 394: (unsigned long *) qpda->bufPtr,
! 395: (unsigned long *) qpda->bufPtr,
! 396: (unsigned long *) ppda->bufPtr,
! 397: rf_RaidAddressToByte(raidPtr, pda->numSector), i, coeff);
! 398:
! 399: /* OK. The valid data is in P. Zero fill Q, then inc it into it. */
! 400: bzero(qpda->bufPtr, rf_RaidAddressToByte(raidPtr, qpda->numSector));
! 401: rf_IncQ((unsigned long *) qpda->bufPtr, (unsigned long *) ppda->bufPtr,
! 402: rf_RaidAddressToByte(raidPtr, qpda->numSector), i);
! 403:
! 404: /* Now apply all the write data to the buffer. */
! 405: /*
! 406: * Single stripe unit write case: The failed data is the only thing
! 407: * we are writing.
! 408: */
! 409: RF_ASSERT(asmap->numStripeUnitsAccessed == 1);
! 410: /* Dest, src, len, coeff. */
! 411: rf_IncQ((unsigned long *) qpda->bufPtr,
! 412: (unsigned long *) asmap->failedPDAs[0]->bufPtr,
! 413: rf_RaidAddressToByte(raidPtr, qpda->numSector), coeff);
! 414: rf_bxor(asmap->failedPDAs[0]->bufPtr, ppda->bufPtr,
! 415: rf_RaidAddressToByte(raidPtr, ppda->numSector), node->dagHdr->bp);
! 416:
! 417: /* Now apply all the recovery data. */
! 418: for (i = 0; i < numDataCol - 2; i++)
! 419: rf_applyPDA(raidPtr, node->params[i].p, ppda, qpda,
! 420: node->dagHdr->bp);
! 421:
! 422: RF_ETIMER_STOP(timer);
! 423: RF_ETIMER_EVAL(timer);
! 424: if (tracerec)
! 425: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 426:
! 427: rf_GenericWakeupFunc(node, 0);
! 428: return (0);
! 429: }
! 430:
! 431: RF_CREATE_DAG_FUNC_DECL(rf_PQ_DDLargeWrite)
! 432: {
! 433: RF_PANIC();
! 434: }
! 435:
! 436:
! 437: /*
! 438: * Two lost data unit write case.
! 439: *
! 440: * There are really two cases here:
! 441: *
! 442: * (1) The write completely covers the two lost data units.
! 443: * In that case, a reconstruct write that doesn't write the
! 444: * failed data units will do the correct thing. So in this case,
! 445: * the dag looks like
! 446: *
! 447: * Full stripe read of surviving data units (not being overwritten)
! 448: * Write new data (ignoring failed units)
! 449: * Compute P&Q
! 450: * Write P&Q
! 451: *
! 452: *
! 453: * (2) The write does not completely cover both failed data units
! 454: * (but touches at least one of them). Then we need to do the
! 455: * equivalent of a reconstruct read to recover the missing data
! 456: * unit from the other stripe.
! 457: *
! 458: * For any data we are writing that is not in the "shadow"
! 459: * of the failed units, we need to do a four cycle update.
! 460: * PANIC on this case. For now.
! 461: *
! 462: */
! 463:
! 464: RF_CREATE_DAG_FUNC_DECL(rf_PQ_200_CreateWriteDAG)
! 465: {
! 466: RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
! 467: RF_SectorCount_t sectorsPerSU = layoutPtr->sectorsPerStripeUnit;
! 468: int sum;
! 469: int nf = asmap->numDataFailed;
! 470:
! 471: sum = asmap->failedPDAs[0]->numSector;
! 472: if (nf == 2)
! 473: sum += asmap->failedPDAs[1]->numSector;
! 474:
! 475: if ((nf == 2) && (sum == (2 * sectorsPerSU))) {
! 476: /* Large write case. */
! 477: rf_PQ_DDLargeWrite(raidPtr, asmap, dag_h, bp, flags, allocList);
! 478: return;
! 479: }
! 480: if ((nf == asmap->numStripeUnitsAccessed) || (sum >= sectorsPerSU)) {
! 481: /* Small write case, no user data not in shadow. */
! 482: rf_PQ_DDSimpleSmallWrite(raidPtr, asmap, dag_h, bp, flags,
! 483: allocList);
! 484: return;
! 485: }
! 486: RF_PANIC();
! 487: }
! 488:
! 489: RF_CREATE_DAG_FUNC_DECL(rf_PQ_DDSimpleSmallWrite)
! 490: {
! 491: rf_DoubleDegSmallWrite(raidPtr, asmap, dag_h, bp, flags, allocList,
! 492: "Rq", "Wq", "PQ Recovery", rf_PQWriteDoubleRecoveryFunc);
! 493: }
! 494:
! 495: #endif /* (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_pqdegdags.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe