Annotation of sys/dev/raidframe/rf_pq.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: rf_pq.c,v 1.6 2002/12/16 07:01:04 tdeval Exp $ */
! 2: /* $NetBSD: rf_pq.c,v 1.7 2000/01/07 03:41:02 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: * Code for RAID level 6 (P + Q) disk array architecture.
! 33: */
! 34:
! 35: #include "rf_archs.h"
! 36: #include "rf_types.h"
! 37: #include "rf_raid.h"
! 38: #include "rf_dag.h"
! 39: #include "rf_dagffrd.h"
! 40: #include "rf_dagffwr.h"
! 41: #include "rf_dagdegrd.h"
! 42: #include "rf_dagdegwr.h"
! 43: #include "rf_dagutils.h"
! 44: #include "rf_dagfuncs.h"
! 45: #include "rf_etimer.h"
! 46: #include "rf_pqdeg.h"
! 47: #include "rf_general.h"
! 48: #include "rf_map.h"
! 49: #include "rf_pq.h"
! 50:
! 51: RF_RedFuncs_t rf_pFuncs = {
! 52: rf_RegularONPFunc, "Regular Old-New P",
! 53: rf_SimpleONPFunc, "Simple Old-New P"
! 54: };
! 55: RF_RedFuncs_t rf_pRecoveryFuncs = {
! 56: rf_RecoveryPFunc, "Recovery P Func",
! 57: rf_RecoveryPFunc, "Recovery P Func"
! 58: };
! 59:
! 60: int
! 61: rf_RegularONPFunc(RF_DagNode_t *node)
! 62: {
! 63: return (rf_RegularXorFunc(node));
! 64: }
! 65:
! 66:
! 67: /*
! 68: * Same as simpleONQ func, but the coefficient is always 1.
! 69: */
! 70:
! 71: int
! 72: rf_SimpleONPFunc(RF_DagNode_t *node)
! 73: {
! 74: return (rf_SimpleXorFunc(node));
! 75: }
! 76:
! 77: int
! 78: rf_RecoveryPFunc(RF_DagNode_t *node)
! 79: {
! 80: return (rf_RecoveryXorFunc(node));
! 81: }
! 82:
! 83: int
! 84: rf_RegularPFunc(RF_DagNode_t *node)
! 85: {
! 86: return (rf_RegularXorFunc(node));
! 87: }
! 88:
! 89:
! 90: #if (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0)
! 91:
! 92: void rf_QDelta(char *dest, char *obuf, char *nbuf, unsigned length,
! 93: unsigned char coeff);
! 94: void rf_InvertQ(unsigned long *qbuf, unsigned long *abuf, unsigned length,
! 95: unsigned coeff);
! 96:
! 97: RF_RedFuncs_t rf_qFuncs = {
! 98: rf_RegularONQFunc, "Regular Old-New Q",
! 99: rf_SimpleONQFunc, "Simple Old-New Q"
! 100: };
! 101: RF_RedFuncs_t rf_qRecoveryFuncs = {
! 102: rf_RecoveryQFunc, "Recovery Q Func",
! 103: rf_RecoveryQFunc, "Recovery Q Func"
! 104: };
! 105: RF_RedFuncs_t rf_pqRecoveryFuncs = {
! 106: rf_RecoveryPQFunc, "Recovery PQ Func",
! 107: rf_RecoveryPQFunc, "Recovery PQ Func"
! 108: };
! 109:
! 110: void
! 111: rf_PQDagSelect(RF_Raid_t *raidPtr, RF_IoType_t type,
! 112: RF_AccessStripeMap_t *asmap, RF_VoidFuncPtr *createFunc)
! 113: {
! 114: RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout);
! 115: unsigned ndfail = asmap->numDataFailed;
! 116: unsigned npfail = asmap->numParityFailed;
! 117: unsigned ntfail = npfail + ndfail;
! 118:
! 119: RF_ASSERT(RF_IO_IS_R_OR_W(type));
! 120: if (ntfail > 2) {
! 121: RF_ERRORMSG("more than two disks failed in a single group !"
! 122: " Aborting I/O operation.\n");
! 123: /* *infoFunc = */ *createFunc = NULL;
! 124: return;
! 125: }
! 126: /* Ok, we can do this I/O. */
! 127: if (type == RF_IO_TYPE_READ) {
! 128: switch (ndfail) {
! 129: case 0:
! 130: /* Fault free read. */
! 131: *createFunc = (RF_VoidFuncPtr)
! 132: rf_CreateFaultFreeReadDAG; /* Same as raid 5. */
! 133: break;
! 134: case 1:
! 135: /* Lost a single data unit. */
! 136: /*
! 137: * Two cases:
! 138: * (1) Parity is not lost. Do a normal raid 5
! 139: * reconstruct read.
! 140: * (2) Parity is lost. Do a reconstruct read using "q".
! 141: */
! 142: if (ntfail == 2) { /* Also lost redundancy. */
! 143: if (asmap->failedPDAs[1]->type ==
! 144: RF_PDA_TYPE_PARITY)
! 145: *createFunc = (RF_VoidFuncPtr)
! 146: rf_PQ_110_CreateReadDAG;
! 147: else
! 148: *createFunc = (RF_VoidFuncPtr)
! 149: rf_PQ_101_CreateReadDAG;
! 150: } else {
! 151: /*
! 152: * P and Q are ok. But is there a failure in
! 153: * some unaccessed data unit ?
! 154: */
! 155: if (rf_NumFailedDataUnitsInStripe(raidPtr,
! 156: asmap) == 2)
! 157: *createFunc = (RF_VoidFuncPtr)
! 158: rf_PQ_200_CreateReadDAG;
! 159: else
! 160: *createFunc = (RF_VoidFuncPtr)
! 161: rf_PQ_100_CreateReadDAG;
! 162: }
! 163: break;
! 164: case 2:
! 165: /* Lost two data units. */
! 166: /* *infoFunc = rf_PQOneTwo; */
! 167: *createFunc = (RF_VoidFuncPtr) rf_PQ_200_CreateReadDAG;
! 168: break;
! 169: }
! 170: return;
! 171: }
! 172: /* A write. */
! 173: switch (ntfail) {
! 174: case 0: /* Fault free. */
! 175: if (rf_suppressLocksAndLargeWrites ||
! 176: (((asmap->numStripeUnitsAccessed <=
! 177: (layoutPtr->numDataCol / 2)) &&
! 178: (layoutPtr->numDataCol != 1)) ||
! 179: (asmap->parityInfo->next != NULL) ||
! 180: (asmap->qInfo->next != NULL) ||
! 181: rf_CheckStripeForFailures(raidPtr, asmap))) {
! 182:
! 183: *createFunc = (RF_VoidFuncPtr) rf_PQCreateSmallWriteDAG;
! 184: } else {
! 185: *createFunc = (RF_VoidFuncPtr) rf_PQCreateLargeWriteDAG;
! 186: }
! 187: break;
! 188:
! 189: case 1: /* Single disk fault. */
! 190: if (npfail == 1) {
! 191: RF_ASSERT((asmap->failedPDAs[0]->type ==
! 192: RF_PDA_TYPE_PARITY) ||
! 193: (asmap->failedPDAs[0]->type == RF_PDA_TYPE_Q));
! 194: if (asmap->failedPDAs[0]->type == RF_PDA_TYPE_Q) {
! 195: /*
! 196: * Q died, treat like normal mode raid5 write.
! 197: */
! 198: if (((asmap->numStripeUnitsAccessed <=
! 199: (layoutPtr->numDataCol / 2)) ||
! 200: (asmap->numStripeUnitsAccessed == 1)) ||
! 201: rf_NumFailedDataUnitsInStripe(raidPtr,
! 202: asmap))
! 203: *createFunc = (RF_VoidFuncPtr)
! 204: rf_PQ_001_CreateSmallWriteDAG;
! 205: else
! 206: *createFunc = (RF_VoidFuncPtr)
! 207: rf_PQ_001_CreateLargeWriteDAG;
! 208: } else {/* Parity died, small write only updating Q. */
! 209: if (((asmap->numStripeUnitsAccessed <=
! 210: (layoutPtr->numDataCol / 2)) ||
! 211: (asmap->numStripeUnitsAccessed == 1)) ||
! 212: rf_NumFailedDataUnitsInStripe(raidPtr,
! 213: asmap))
! 214: *createFunc = (RF_VoidFuncPtr)
! 215: rf_PQ_010_CreateSmallWriteDAG;
! 216: else
! 217: *createFunc = (RF_VoidFuncPtr)
! 218: rf_PQ_010_CreateLargeWriteDAG;
! 219: }
! 220: } else { /*
! 221: * Data missing. Do a P reconstruct write if
! 222: * only a single data unit is lost in the
! 223: * stripe, otherwise a PQ reconstruct write.
! 224: */
! 225: if (rf_NumFailedDataUnitsInStripe(raidPtr, asmap) == 2)
! 226: *createFunc = (RF_VoidFuncPtr)
! 227: rf_PQ_200_CreateWriteDAG;
! 228: else
! 229: *createFunc = (RF_VoidFuncPtr)
! 230: rf_PQ_100_CreateWriteDAG;
! 231: }
! 232: break;
! 233:
! 234: case 2: /* Two disk faults. */
! 235: switch (npfail) {
! 236: case 2: /* Both p and q dead. */
! 237: *createFunc = (RF_VoidFuncPtr) rf_PQ_011_CreateWriteDAG;
! 238: break;
! 239: case 1: /* Either p or q and dead data. */
! 240: RF_ASSERT(asmap->failedPDAs[0]->type ==
! 241: RF_PDA_TYPE_DATA);
! 242: RF_ASSERT((asmap->failedPDAs[1]->type ==
! 243: RF_PDA_TYPE_PARITY) ||
! 244: (asmap->failedPDAs[1]->type ==
! 245: RF_PDA_TYPE_Q));
! 246: if (asmap->failedPDAs[1]->type == RF_PDA_TYPE_Q)
! 247: *createFunc = (RF_VoidFuncPtr)
! 248: rf_PQ_101_CreateWriteDAG;
! 249: else
! 250: *createFunc = (RF_VoidFuncPtr)
! 251: rf_PQ_110_CreateWriteDAG;
! 252: break;
! 253: case 0: /* Double data loss. */
! 254: *createFunc = (RF_VoidFuncPtr) rf_PQ_200_CreateWriteDAG;
! 255: break;
! 256: }
! 257: break;
! 258:
! 259: default: /* More than 2 disk faults. */
! 260: *createFunc = NULL;
! 261: RF_PANIC();
! 262: }
! 263: return;
! 264: }
! 265:
! 266:
! 267: /*
! 268: * Used as a stop gap info function.
! 269: */
! 270: #if 0
! 271: void
! 272: rf_PQOne(RF_Raid_t *raidPtr, int *nSucc, int *nAnte,
! 273: RF_AccessStripeMap_t *asmap)
! 274: {
! 275: *nSucc = *nAnte = 1;
! 276: }
! 277:
! 278: void
! 279: rf_PQOneTwo(RF_Raid_t *raidPtr, int *nSucc, int *nAnte,
! 280: RF_AccessStripeMap_t *asmap)
! 281: {
! 282: *nSucc = 1;
! 283: *nAnte = 2;
! 284: }
! 285: #endif
! 286:
! 287: RF_CREATE_DAG_FUNC_DECL(rf_PQCreateLargeWriteDAG)
! 288: {
! 289: rf_CommonCreateLargeWriteDAG(raidPtr, asmap, dag_h, bp, flags,
! 290: allocList, 2, rf_RegularPQFunc, RF_FALSE);
! 291: }
! 292:
! 293: int
! 294: rf_RegularONQFunc(RF_DagNode_t *node)
! 295: {
! 296: int np = node->numParams;
! 297: int d;
! 298: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
! 299: int i;
! 300: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 301: RF_Etimer_t timer;
! 302: char *qbuf, *qpbuf;
! 303: char *obuf, *nbuf;
! 304: RF_PhysDiskAddr_t *old, *new;
! 305: unsigned long coeff;
! 306: unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
! 307:
! 308: RF_ETIMER_START(timer);
! 309:
! 310: d = (np - 3) / 4;
! 311: RF_ASSERT(4 * d + 3 == np);
! 312: qbuf = (char *) node->params[2 * d + 1].p; /* Q buffer. */
! 313: for (i = 0; i < d; i++) {
! 314: old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
! 315: obuf = (char *) node->params[2 * i + 1].p;
! 316: new = (RF_PhysDiskAddr_t *) node->params[2 * (d + 1 + i)].p;
! 317: nbuf = (char *) node->params[2 * (d + 1 + i) + 1].p;
! 318: RF_ASSERT(new->numSector == old->numSector);
! 319: RF_ASSERT(new->raidAddress == old->raidAddress);
! 320: /*
! 321: * The stripe unit within the stripe tells us the coefficient
! 322: * to use for the multiply.
! 323: */
! 324: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 325: new->raidAddress);
! 326: /*
! 327: * Compute the data unit offset within the column, then add
! 328: * one.
! 329: */
! 330: coeff = (coeff % raidPtr->Layout.numDataCol);
! 331: qpbuf = qbuf + rf_RaidAddressToByte(raidPtr,
! 332: old->startSector % secPerSU);
! 333: rf_QDelta(qpbuf, obuf, nbuf, rf_RaidAddressToByte(raidPtr,
! 334: old->numSector), coeff);
! 335: }
! 336:
! 337: RF_ETIMER_STOP(timer);
! 338: RF_ETIMER_EVAL(timer);
! 339: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 340: rf_GenericWakeupFunc(node, 0); /*
! 341: * Call wake func explicitly since no
! 342: * I/O in this node.
! 343: */
! 344: return (0);
! 345: }
! 346:
! 347:
! 348: /*
! 349: * See the SimpleXORFunc for the difference between a simple and regular func.
! 350: * These Q functions should be used for
! 351: * new q = Q(data, old data, old q)
! 352: * style updates and not for
! 353: * q = (new data, new data, ...)
! 354: * computations.
! 355: *
! 356: * The simple q takes 2(2d+1)+1 params, where d is the number
! 357: * of stripes written. The order of params is
! 358: * old data pda_0, old data buffer_0, old data pda_1, old data buffer_1, ...
! 359: * old data pda_d, old data buffer_d
! 360: * [2d] old q pda_0, old q buffer
! 361: * [2d_2] new data pda_0, new data buffer_0, ...
! 362: * new data pda_d, new data buffer_d
! 363: * raidPtr
! 364: */
! 365:
! 366: int
! 367: rf_SimpleONQFunc(RF_DagNode_t *node)
! 368: {
! 369: int np = node->numParams;
! 370: int d;
! 371: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
! 372: int i;
! 373: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 374: RF_Etimer_t timer;
! 375: char *qbuf;
! 376: char *obuf, *nbuf;
! 377: RF_PhysDiskAddr_t *old, *new;
! 378: unsigned long coeff;
! 379:
! 380: RF_ETIMER_START(timer);
! 381:
! 382: d = (np - 3) / 4;
! 383: RF_ASSERT(4 * d + 3 == np);
! 384: qbuf = (char *) node->params[2 * d + 1].p; /* Q buffer. */
! 385: for (i = 0; i < d; i++) {
! 386: old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
! 387: obuf = (char *) node->params[2 * i + 1].p;
! 388: new = (RF_PhysDiskAddr_t *) node->params[2 * (d + 1 + i)].p;
! 389: nbuf = (char *) node->params[2 * (d + 1 + i) + 1].p;
! 390: RF_ASSERT(new->numSector == old->numSector);
! 391: RF_ASSERT(new->raidAddress == old->raidAddress);
! 392: /*
! 393: * The stripe unit within the stripe tells us the coefficient
! 394: * to use for the multiply.
! 395: */
! 396: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 397: new->raidAddress);
! 398: /*
! 399: * Compute the data unit offset within the column, then add
! 400: * one.
! 401: */
! 402: coeff = (coeff % raidPtr->Layout.numDataCol);
! 403: rf_QDelta(qbuf, obuf, nbuf, rf_RaidAddressToByte(raidPtr,
! 404: old->numSector), coeff);
! 405: }
! 406:
! 407: RF_ETIMER_STOP(timer);
! 408: RF_ETIMER_EVAL(timer);
! 409: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 410: rf_GenericWakeupFunc(node, 0); /*
! 411: * Call wake func explicitly since no
! 412: * I/O in this node.
! 413: */
! 414: return (0);
! 415: }
! 416:
! 417: RF_CREATE_DAG_FUNC_DECL(rf_PQCreateSmallWriteDAG)
! 418: {
! 419: rf_CommonCreateSmallWriteDAG(raidPtr, asmap, dag_h, bp, flags,
! 420: allocList, &rf_pFuncs, &rf_qFuncs);
! 421: }
! 422:
! 423:
! 424: void rf_RegularQSubr(RF_DagNode_t *, char *);
! 425:
! 426: void
! 427: rf_RegularQSubr(RF_DagNode_t *node, char *qbuf)
! 428: {
! 429: int np = node->numParams;
! 430: int d;
! 431: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
! 432: unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
! 433: int i;
! 434: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 435: RF_Etimer_t timer;
! 436: char *obuf, *qpbuf;
! 437: RF_PhysDiskAddr_t *old;
! 438: unsigned long coeff;
! 439:
! 440: RF_ETIMER_START(timer);
! 441:
! 442: d = (np - 1) / 2;
! 443: RF_ASSERT(2 * d + 1 == np);
! 444: for (i = 0; i < d; i++) {
! 445: old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
! 446: obuf = (char *) node->params[2 * i + 1].p;
! 447: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 448: old->raidAddress);
! 449: /*
! 450: * Compute the data unit offset within the column, then add
! 451: * one.
! 452: */
! 453: coeff = (coeff % raidPtr->Layout.numDataCol);
! 454: /*
! 455: * The input buffers may not all be aligned with the start of
! 456: * the stripe. So shift by their sector offset within the
! 457: * stripe unit.
! 458: */
! 459: qpbuf = qbuf + rf_RaidAddressToByte(raidPtr,
! 460: old->startSector % secPerSU);
! 461: rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
! 462: rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
! 463: }
! 464:
! 465: RF_ETIMER_STOP(timer);
! 466: RF_ETIMER_EVAL(timer);
! 467: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 468: }
! 469:
! 470:
! 471: /*
! 472: * Used in degraded writes.
! 473: */
! 474:
! 475: void rf_DegrQSubr(RF_DagNode_t *);
! 476:
! 477: void
! 478: rf_DegrQSubr(RF_DagNode_t *node)
! 479: {
! 480: int np = node->numParams;
! 481: int d;
! 482: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
! 483: unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
! 484: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 485: RF_Etimer_t timer;
! 486: char *qbuf = node->results[1];
! 487: char *obuf, *qpbuf;
! 488: RF_PhysDiskAddr_t *old;
! 489: unsigned long coeff;
! 490: unsigned fail_start;
! 491: int i, j;
! 492:
! 493: old = (RF_PhysDiskAddr_t *) node->params[np - 2].p;
! 494: fail_start = old->startSector % secPerSU;
! 495:
! 496: RF_ETIMER_START(timer);
! 497:
! 498: d = (np - 2) / 2;
! 499: RF_ASSERT(2 * d + 2 == np);
! 500: for (i = 0; i < d; i++) {
! 501: old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
! 502: obuf = (char *) node->params[2 * i + 1].p;
! 503: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 504: old->raidAddress);
! 505: /*
! 506: * Compute the data unit offset within the column, then add
! 507: * one.
! 508: */
! 509: coeff = (coeff % raidPtr->Layout.numDataCol);
! 510: /*
! 511: * The input buffers may not all be aligned with the start of
! 512: * the stripe. So shift by their sector offset within the
! 513: * stripe unit.
! 514: */
! 515: j = old->startSector % secPerSU;
! 516: RF_ASSERT(j >= fail_start);
! 517: qpbuf = qbuf + rf_RaidAddressToByte(raidPtr, j - fail_start);
! 518: rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
! 519: rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
! 520: }
! 521:
! 522: RF_ETIMER_STOP(timer);
! 523: RF_ETIMER_EVAL(timer);
! 524: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 525: }
! 526:
! 527:
! 528: /*
! 529: * Called by large write code to compute the new parity and the new q.
! 530: *
! 531: * Structure of the params:
! 532: *
! 533: * pda_0, buffer_0, pda_1 , buffer_1, ..., pda_d, buffer_d (d = numDataCol)
! 534: * raidPtr
! 535: *
! 536: * For a total of 2d+1 arguments.
! 537: * The result buffers results[0], results[1] are the buffers for the p and q,
! 538: * respectively.
! 539: *
! 540: * We compute Q first, then compute P. The P calculation may try to reuse
! 541: * one of the input buffers for its output, so if we computed P first, we would
! 542: * corrupt the input for the q calculation.
! 543: */
! 544:
! 545: int
! 546: rf_RegularPQFunc(RF_DagNode_t *node)
! 547: {
! 548: rf_RegularQSubr(node, node->results[1]);
! 549: return (rf_RegularXorFunc(node)); /* Does the wakeup. */
! 550: }
! 551:
! 552: int
! 553: rf_RegularQFunc(RF_DagNode_t *node)
! 554: {
! 555: /* Almost ... adjust Qsubr args. */
! 556: rf_RegularQSubr(node, node->results[0]);
! 557: rf_GenericWakeupFunc(node, 0); /*
! 558: * Call wake func explicitly since no
! 559: * I/O in this node.
! 560: */
! 561: return (0);
! 562: }
! 563:
! 564:
! 565: /*
! 566: * Called by singly degraded write code to compute the new parity and
! 567: * the new q.
! 568: *
! 569: * Structure of the params:
! 570: *
! 571: * pda_0, buffer_0, pda_1 , buffer_1, ..., pda_d, buffer_d
! 572: * failedPDA raidPtr
! 573: *
! 574: * for a total of 2d+2 arguments.
! 575: * The result buffers results[0], results[1] are the buffers for the parity
! 576: * and q, respectively.
! 577: *
! 578: * We compute Q first, then compute parity. The parity calculation may try
! 579: * to reuse one of the input buffers for its output, so if we computed parity
! 580: * first, we would corrupt the input for the q calculation.
! 581: *
! 582: * We treat this identically to the regularPQ case, ignoring the failedPDA
! 583: * extra argument.
! 584: */
! 585:
! 586: void
! 587: rf_Degraded_100_PQFunc(RF_DagNode_t *node)
! 588: {
! 589: int np = node->numParams;
! 590:
! 591: RF_ASSERT(np >= 2);
! 592: rf_DegrQSubr(node);
! 593: rf_RecoveryXorFunc(node);
! 594: }
! 595:
! 596:
! 597: /*
! 598: * The two below are used when reading a stripe with a single lost data unit.
! 599: * The parameters are
! 600: *
! 601: * pda_0, buffer_0, ..., pda_n, buffer_n, P pda, P buffer, failedPDA, raidPtr
! 602: *
! 603: * and results[0] contains the data buffer, which is originally zero-filled.
! 604: */
! 605:
! 606: /*
! 607: * This Q func is used by the degraded-mode dag functions to recover lost data.
! 608: * The second-to-last parameter is the PDA for the failed portion of the
! 609: * access. The code here looks at this PDA and assumes that the xor target
! 610: * buffer is equal in size to the number of sectors in the failed PDA. It then
! 611: * uses the other PDAs in the parameter list to determine where within the
! 612: * target buffer the corresponding data should be xored.
! 613: *
! 614: * Recall the basic equation is
! 615: *
! 616: * Q = (data_1 + 2 * data_2 ... + k * data_k) mod 256
! 617: *
! 618: * so to recover data_j we need
! 619: *
! 620: * J data_j = (Q - data_1 - 2 data_2 ... - k * data_k) mod 256
! 621: *
! 622: * So the coefficient for each buffer is (255 - data_col), and j should be
! 623: * initialized by copying Q into it. Then we need to do a table lookup to
! 624: * convert to solve
! 625: * data_j /= J
! 626: *
! 627: */
! 628:
! 629: int
! 630: rf_RecoveryQFunc(RF_DagNode_t *node)
! 631: {
! 632: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
! 633: RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
! 634: RF_PhysDiskAddr_t *failedPDA =
! 635: (RF_PhysDiskAddr_t *) node->params[node->numParams - 2].p;
! 636: int i;
! 637: RF_PhysDiskAddr_t *pda;
! 638: RF_RaidAddr_t suoffset;
! 639: RF_RaidAddr_t failedSUOffset =
! 640: rf_StripeUnitOffset(layoutPtr, failedPDA->startSector);
! 641: char *srcbuf, *destbuf;
! 642: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 643: RF_Etimer_t timer;
! 644: unsigned long coeff;
! 645:
! 646: RF_ETIMER_START(timer);
! 647: /* Start by copying Q into the buffer. */
! 648: bcopy(node->params[node->numParams - 3].p, node->results[0],
! 649: rf_RaidAddressToByte(raidPtr, failedPDA->numSector));
! 650: for (i = 0; i < node->numParams - 4; i += 2) {
! 651: RF_ASSERT(node->params[i + 1].p != node->results[0]);
! 652: pda = (RF_PhysDiskAddr_t *) node->params[i].p;
! 653: srcbuf = (char *) node->params[i + 1].p;
! 654: suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
! 655: destbuf = ((char *) node->results[0]) +
! 656: rf_RaidAddressToByte(raidPtr, suoffset - failedSUOffset);
! 657: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 658: pda->raidAddress);
! 659: /* Compute the data unit offset within the column. */
! 660: coeff = (coeff % raidPtr->Layout.numDataCol);
! 661: rf_IncQ((unsigned long *) destbuf, (unsigned long *) srcbuf,
! 662: rf_RaidAddressToByte(raidPtr, pda->numSector), coeff);
! 663: }
! 664: /* Do the nasty inversion now. */
! 665: coeff = (rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 666: failedPDA->startSector) % raidPtr->Layout.numDataCol);
! 667: rf_InvertQ(node->results[0], node->results[0],
! 668: rf_RaidAddressToByte(raidPtr, pda->numSector), coeff);
! 669: RF_ETIMER_STOP(timer);
! 670: RF_ETIMER_EVAL(timer);
! 671: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 672: rf_GenericWakeupFunc(node, 0);
! 673: return (0);
! 674: }
! 675:
! 676: int
! 677: rf_RecoveryPQFunc(RF_DagNode_t *node)
! 678: {
! 679: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
! 680: printf("raid%d: Recovery from PQ not implemented.\n", raidPtr->raidid);
! 681: return (1);
! 682: }
! 683:
! 684:
! 685: /*
! 686: * Degraded write Q subroutine.
! 687: * Used when P is dead.
! 688: * Large-write style Q computation.
! 689: * Parameters:
! 690: *
! 691: * (pda, buf), (pda, buf), ..., (failedPDA, bufPtr), failedPDA, raidPtr.
! 692: *
! 693: * We ignore failedPDA.
! 694: *
! 695: * This is a "simple style" recovery func.
! 696: */
! 697:
! 698: void
! 699: rf_PQ_DegradedWriteQFunc(RF_DagNode_t *node)
! 700: {
! 701: int np = node->numParams;
! 702: int d;
! 703: RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
! 704: unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
! 705: RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
! 706: RF_Etimer_t timer;
! 707: char *qbuf = node->results[0];
! 708: char *obuf, *qpbuf;
! 709: RF_PhysDiskAddr_t *old;
! 710: unsigned long coeff;
! 711: int fail_start, i, j;
! 712:
! 713: old = (RF_PhysDiskAddr_t *) node->params[np - 2].p;
! 714: fail_start = old->startSector % secPerSU;
! 715:
! 716: RF_ETIMER_START(timer);
! 717:
! 718: d = (np - 2) / 2;
! 719: RF_ASSERT(2 * d + 2 == np);
! 720:
! 721: for (i = 0; i < d; i++) {
! 722: old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
! 723: obuf = (char *) node->params[2 * i + 1].p;
! 724: coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
! 725: old->raidAddress);
! 726: /*
! 727: * Compute the data unit offset within the column, then add
! 728: * one.
! 729: */
! 730: coeff = (coeff % raidPtr->Layout.numDataCol);
! 731: j = old->startSector % secPerSU;
! 732: RF_ASSERT(j >= fail_start);
! 733: qpbuf = qbuf + rf_RaidAddressToByte(raidPtr, j - fail_start);
! 734: rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
! 735: rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
! 736: }
! 737:
! 738: RF_ETIMER_STOP(timer);
! 739: RF_ETIMER_EVAL(timer);
! 740: tracerec->q_us += RF_ETIMER_VAL_US(timer);
! 741: rf_GenericWakeupFunc(node, 0);
! 742: }
! 743:
! 744:
! 745: /* Q computations. */
! 746:
! 747: /*
! 748: * Coeff - colummn;
! 749: *
! 750: * Compute dest ^= qfor[28-coeff][rn[coeff+1] a]
! 751: *
! 752: * On 5-bit basis;
! 753: * Length in bytes;
! 754: */
! 755:
! 756: void
! 757: rf_IncQ(unsigned long *dest, unsigned long *buf, unsigned length,
! 758: unsigned coeff)
! 759: {
! 760: unsigned long a, d, new;
! 761: unsigned long a1, a2;
! 762: unsigned int *q = &(rf_qfor[28 - coeff][0]);
! 763: unsigned r = rf_rn[coeff + 1];
! 764:
! 765: #define EXTRACT(a,i) ((a >> (5L*i)) & 0x1f)
! 766: #define INSERT(a,i) (a << (5L*i))
! 767:
! 768: length /= 8;
! 769: /* 13 5 bit quants in a 64 bit word. */
! 770: while (length) {
! 771: a = *buf++;
! 772: d = *dest;
! 773: a1 = EXTRACT(a, 0) ^ r;
! 774: a2 = EXTRACT(a, 1) ^ r;
! 775: new = INSERT(a2, 1) | a1;
! 776: a1 = EXTRACT(a, 2) ^ r;
! 777: a2 = EXTRACT(a, 3) ^ r;
! 778: a1 = q[a1];
! 779: a2 = q[a2];
! 780: new = new | INSERT(a1, 2) | INSERT(a2, 3);
! 781: a1 = EXTRACT(a, 4) ^ r;
! 782: a2 = EXTRACT(a, 5) ^ r;
! 783: a1 = q[a1];
! 784: a2 = q[a2];
! 785: new = new | INSERT(a1, 4) | INSERT(a2, 5);
! 786: a1 = EXTRACT(a, 5) ^ r;
! 787: a2 = EXTRACT(a, 6) ^ r;
! 788: a1 = q[a1];
! 789: a2 = q[a2];
! 790: new = new | INSERT(a1, 5) | INSERT(a2, 6);
! 791: #if RF_LONGSHIFT > 2
! 792: a1 = EXTRACT(a, 7) ^ r;
! 793: a2 = EXTRACT(a, 8) ^ r;
! 794: a1 = q[a1];
! 795: a2 = q[a2];
! 796: new = new | INSERT(a1, 7) | INSERT(a2, 8);
! 797: a1 = EXTRACT(a, 9) ^ r;
! 798: a2 = EXTRACT(a, 10) ^ r;
! 799: a1 = q[a1];
! 800: a2 = q[a2];
! 801: new = new | INSERT(a1, 9) | INSERT(a2, 10);
! 802: a1 = EXTRACT(a, 11) ^ r;
! 803: a2 = EXTRACT(a, 12) ^ r;
! 804: a1 = q[a1];
! 805: a2 = q[a2];
! 806: new = new | INSERT(a1, 11) | INSERT(a2, 12);
! 807: #endif /* RF_LONGSHIFT > 2 */
! 808: d ^= new;
! 809: *dest++ = d;
! 810: length--;
! 811: }
! 812: }
! 813:
! 814:
! 815: /*
! 816: * Compute.
! 817: *
! 818: * dest ^= rf_qfor[28-coeff][rf_rn[coeff+1] (old^new)]
! 819: *
! 820: * On a five bit basis.
! 821: * Optimization: compute old ^ new on 64 bit basis.
! 822: *
! 823: * Length in bytes.
! 824: */
! 825:
! 826: void
! 827: rf_QDelta(char *dest, char *obuf, char *nbuf, unsigned length,
! 828: unsigned char coeff)
! 829: {
! 830: unsigned long a, d, new;
! 831: unsigned long a1, a2;
! 832: unsigned int *q = &(rf_qfor[28 - coeff][0]);
! 833: unsigned int r = rf_rn[coeff + 1];
! 834:
! 835: r = a1 = a2 = new = d = a = 0; /* XXX For now... */
! 836: q = NULL; /* XXX For now */
! 837:
! 838: #ifdef _KERNEL
! 839: /*
! 840: * PQ in kernel currently not supported because the encoding/decoding
! 841: * table is not present.
! 842: */
! 843: bzero(dest, length);
! 844: #else /* _KERNEL */
! 845: /* This code probably doesn't work and should be rewritten. -wvcii */
! 846: /* 13 5 bit quants in a 64 bit word. */
! 847: length /= 8;
! 848: while (length) {
! 849: a = *obuf++; /*
! 850: * XXX Need to reorg to avoid cache conflicts.
! 851: */
! 852: a ^= *nbuf++;
! 853: d = *dest;
! 854: a1 = EXTRACT(a, 0) ^ r;
! 855: a2 = EXTRACT(a, 1) ^ r;
! 856: a1 = q[a1];
! 857: a2 = q[a2];
! 858: new = INSERT(a2, 1) | a1;
! 859: a1 = EXTRACT(a, 2) ^ r;
! 860: a2 = EXTRACT(a, 3) ^ r;
! 861: a1 = q[a1];
! 862: a2 = q[a2];
! 863: new = new | INSERT(a1, 2) | INSERT(a2, 3);
! 864: a1 = EXTRACT(a, 4) ^ r;
! 865: a2 = EXTRACT(a, 5) ^ r;
! 866: a1 = q[a1];
! 867: a2 = q[a2];
! 868: new = new | INSERT(a1, 4) | INSERT(a2, 5);
! 869: a1 = EXTRACT(a, 5) ^ r;
! 870: a2 = EXTRACT(a, 6) ^ r;
! 871: a1 = q[a1];
! 872: a2 = q[a2];
! 873: new = new | INSERT(a1, 5) | INSERT(a2, 6);
! 874: #if RF_LONGSHIFT > 2
! 875: a1 = EXTRACT(a, 7) ^ r;
! 876: a2 = EXTRACT(a, 8) ^ r;
! 877: a1 = q[a1];
! 878: a2 = q[a2];
! 879: new = new | INSERT(a1, 7) | INSERT(a2, 8);
! 880: a1 = EXTRACT(a, 9) ^ r;
! 881: a2 = EXTRACT(a, 10) ^ r;
! 882: a1 = q[a1];
! 883: a2 = q[a2];
! 884: new = new | INSERT(a1, 9) | INSERT(a2, 10);
! 885: a1 = EXTRACT(a, 11) ^ r;
! 886: a2 = EXTRACT(a, 12) ^ r;
! 887: a1 = q[a1];
! 888: a2 = q[a2];
! 889: new = new | INSERT(a1, 11) | INSERT(a2, 12);
! 890: #endif /* RF_LONGSHIFT > 2 */
! 891: d ^= new;
! 892: *dest++ = d;
! 893: length--;
! 894: }
! 895: #endif /* _KERNEL */
! 896: }
! 897:
! 898:
! 899: /*
! 900: * Recover columns a and b from the given p and q into
! 901: * bufs abuf and bbuf. All bufs are word aligned.
! 902: * Length is in bytes.
! 903: */
! 904:
! 905: /*
! 906: * XXX
! 907: *
! 908: * Everything about this seems wrong.
! 909: */
! 910:
! 911: void
! 912: rf_PQ_recover(unsigned long *pbuf, unsigned long *qbuf, unsigned long *abuf,
! 913: unsigned long *bbuf, unsigned length, unsigned coeff_a, unsigned coeff_b)
! 914: {
! 915: unsigned long p, q, a, a0, a1;
! 916: int col = (29 * coeff_a) + coeff_b;
! 917: unsigned char *q0 = &(rf_qinv[col][0]);
! 918:
! 919: length /= 8;
! 920: while (length) {
! 921: p = *pbuf++;
! 922: q = *qbuf++;
! 923: a0 = EXTRACT(p, 0);
! 924: a1 = EXTRACT(q, 0);
! 925: a = q0[a0 << 5 | a1];
! 926:
! 927: #define MF(i) \
! 928: do { \
! 929: a0 = EXTRACT(p, i); \
! 930: a1 = EXTRACT(q, i); \
! 931: a = a | INSERT(q0[a0<<5 | a1], i); \
! 932: } while (0)
! 933:
! 934: MF(1);
! 935: MF(2);
! 936: MF(3);
! 937: MF(4);
! 938: MF(5);
! 939: MF(6);
! 940: #if 0
! 941: MF(7);
! 942: MF(8);
! 943: MF(9);
! 944: MF(10);
! 945: MF(11);
! 946: MF(12);
! 947: #endif /* 0 */
! 948: *abuf++ = a;
! 949: *bbuf++ = a ^ p;
! 950: length--;
! 951: }
! 952: }
! 953:
! 954:
! 955: /*
! 956: * Lost parity and a data column. Recover that data column.
! 957: * Assume col coeff is lost. Let q the contents of Q after
! 958: * all surviving data columns have been q-xored out of it.
! 959: * Then we have the equation
! 960: *
! 961: * q[28-coeff][a_i ^ r_i+1] = q
! 962: *
! 963: * but q is cyclic with period 31.
! 964: * So q[3+coeff][q[28-coeff][a_i ^ r_{i+1}]] =
! 965: * q[31][a_i ^ r_{i+1}] = a_i ^ r_{i+1} .
! 966: *
! 967: * so a_i = r_{coeff+1} ^ q[3+coeff][q]
! 968: *
! 969: * The routine is passed q buffer and the buffer
! 970: * the data is to be recoverd into. They can be the same.
! 971: */
! 972:
! 973: void
! 974: rf_InvertQ(unsigned long *qbuf, unsigned long *abuf, unsigned length,
! 975: unsigned coeff)
! 976: {
! 977: unsigned long a, new;
! 978: unsigned long a1, a2;
! 979: unsigned int *q = &(rf_qfor[3 + coeff][0]);
! 980: unsigned r = rf_rn[coeff + 1];
! 981:
! 982: /* 13 5 bit quants in a 64 bit word. */
! 983: length /= 8;
! 984: while (length) {
! 985: a = *qbuf++;
! 986: a1 = EXTRACT(a, 0);
! 987: a2 = EXTRACT(a, 1);
! 988: a1 = r ^ q[a1];
! 989: a2 = r ^ q[a2];
! 990: new = INSERT(a2, 1) | a1;
! 991:
! 992: #define M(i,j) \
! 993: do { \
! 994: a1 = EXTRACT(a, i); \
! 995: a2 = EXTRACT(a, j); \
! 996: a1 = r ^ q[a1]; \
! 997: a2 = r ^ q[a2]; \
! 998: new = new | INSERT(a1, i) | INSERT(a2, j); \
! 999: } while (0)
! 1000:
! 1001: M(2, 3);
! 1002: M(4, 5);
! 1003: M(5, 6);
! 1004: #if RF_LONGSHIFT > 2
! 1005: M(7, 8);
! 1006: M(9, 10);
! 1007: M(11, 12);
! 1008: #endif /* RF_LONGSHIFT > 2 */
! 1009: *abuf++ = new;
! 1010: length--;
! 1011: }
! 1012: }
! 1013: #endif /* (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_pq.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe