/* $OpenBSD: rf_evenodd.c,v 1.6 2011/06/21 16:46:00 tedu Exp $ */ /* $NetBSD: rf_evenodd.c,v 1.4 2000/01/07 03:40:59 oster Exp $ */ /* * Copyright (c) 1995 Carnegie-Mellon University. * All rights reserved. * * Author: Chang-Ming Wu * * Permission to use, copy, modify and distribute this software and * its documentation is hereby granted, provided that both the copyright * notice and this permission notice appear in all copies of the * software, derivative works or modified versions, and any portions * thereof, and that both notices appear in supporting documentation. * * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. * * Carnegie Mellon requests users of this software to return to * * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU * School of Computer Science * Carnegie Mellon University * Pittsburgh PA 15213-3890 * * any improvements or extensions that they make and grant Carnegie the * rights to redistribute these changes. */ /***************************************************************************** * * rf_evenodd.c -- implements EVENODD array architecture * *****************************************************************************/ #include "rf_archs.h" #if RF_INCLUDE_EVENODD > 0 #include "rf_types.h" #include "rf_raid.h" #include "rf_dag.h" #include "rf_dagffrd.h" #include "rf_dagffwr.h" #include "rf_dagdegrd.h" #include "rf_dagdegwr.h" #include "rf_dagutils.h" #include "rf_dagfuncs.h" #include "rf_etimer.h" #include "rf_general.h" #include "rf_evenodd.h" #include "rf_configure.h" #include "rf_parityscan.h" #include "rf_utils.h" #include "rf_map.h" #include "rf_pq.h" #include "rf_mcpair.h" #include "rf_evenodd.h" #include "rf_evenodd_dagfuncs.h" #include "rf_evenodd_dags.h" #include "rf_engine.h" typedef struct RF_EvenOddConfigInfo_s { RF_RowCol_t **stripeIdentifier; /* * Filled in at config time & used by * IdentifyStripe. */ } RF_EvenOddConfigInfo_t; int rf_ConfigureEvenOdd(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr, RF_Config_t *cfgPtr) { RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; RF_EvenOddConfigInfo_t *info; RF_RowCol_t i, j, startdisk; RF_MallocAndAdd(info, sizeof(RF_EvenOddConfigInfo_t), (RF_EvenOddConfigInfo_t *), raidPtr->cleanupList); layoutPtr->layoutSpecificInfo = (void *) info; RF_ASSERT(raidPtr->numRow == 1); info->stripeIdentifier = rf_make_2d_array(raidPtr->numCol, raidPtr->numCol, raidPtr->cleanupList); startdisk = 0; for (i = 0; i < raidPtr->numCol; i++) { for (j = 0; j < raidPtr->numCol; j++) { info->stripeIdentifier[i][j] = (startdisk + j) % raidPtr->numCol; } if ((startdisk -= 2) < 0) startdisk += raidPtr->numCol; } /* Fill in the remaining layout parameters. */ layoutPtr->numStripe = layoutPtr->stripeUnitsPerDisk; layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit << raidPtr->logBytesPerSector; layoutPtr->numDataCol = raidPtr->numCol - 2; /* * ORIG: * layoutPtr->numDataCol * = raidPtr->numCol-1; */ #if RF_EO_MATRIX_DIM > 17 if (raidPtr->numCol <= 17) { printf("Number of stripe units in a parity stripe is smaller" " than 17. Please\ndefine the macro RF_EO_MATRIX_DIM in" " file rf_evenodd_dagfuncs.h to\nbe 17 to increase" " performance.\n"); return (EINVAL); } #elif RF_EO_MATRIX_DIM == 17 if (raidPtr->numCol > 17) { printf("Number of stripe units in a parity stripe is bigger" " than 17. Please\ndefine the macro RF_EO_MATRIX_DIM in" " file rf_evenodd_dagfuncs.h to\nbe 257 for encoding and" " decoding functions to work.\n"); return (EINVAL); } #endif layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; layoutPtr->numParityCol = 2; layoutPtr->dataStripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk; raidPtr->sectorsPerDisk = layoutPtr->stripeUnitsPerDisk * layoutPtr->sectorsPerStripeUnit; raidPtr->totalSectors = layoutPtr->stripeUnitsPerDisk * layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; return (0); } int rf_GetDefaultNumFloatingReconBuffersEvenOdd(RF_Raid_t *raidPtr) { return (20); } RF_HeadSepLimit_t rf_GetDefaultHeadSepLimitEvenOdd(RF_Raid_t *raidPtr) { return (10); } void rf_IdentifyStripeEvenOdd(RF_Raid_t *raidPtr, RF_RaidAddr_t addr, RF_RowCol_t **diskids, RF_RowCol_t *outRow) { RF_StripeNum_t stripeID = rf_RaidAddressToStripeID(&raidPtr->Layout, addr); RF_EvenOddConfigInfo_t *info = (RF_EvenOddConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; *outRow = 0; *diskids = info->stripeIdentifier[stripeID % raidPtr->numCol]; } /* * The layout of stripe unit on the disks are: c0 c1 c2 c3 c4 * * 0 1 2 E P * 5 E P 3 4 * P 6 7 8 E * 10 11 E P 9 * E P 12 13 14 * .... * * We use the MapSectorRAID5 to map data information because the routine can * be shown to map exactly the layout of data stripe unit as shown above, * although we have 2 redundant information now. * But for E and P, we use rf_MapEEvenOdd and rf_MapParityEvenOdd which are * different method from raid-5. */ void rf_MapParityEvenOdd( RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector, RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t *diskSector, int remap ) { RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; RF_StripeNum_t endSUIDofthisStrip = (SUID / raidPtr->Layout.numDataCol + 1) * raidPtr->Layout.numDataCol - 1; *row = 0; *col = (endSUIDofthisStrip + 2) % raidPtr->numCol; *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit + (raidSector % raidPtr->Layout.sectorsPerStripeUnit); } void rf_MapEEvenOdd( RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector, RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t *diskSector, int remap ) { RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; RF_StripeNum_t endSUIDofthisStrip = (SUID / raidPtr->Layout.numDataCol + 1) * raidPtr->Layout.numDataCol - 1; *row = 0; *col = (endSUIDofthisStrip + 1) % raidPtr->numCol; *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit + (raidSector % raidPtr->Layout.sectorsPerStripeUnit); } void rf_EODagSelect( RF_Raid_t *raidPtr, RF_IoType_t type, RF_AccessStripeMap_t *asmap, RF_VoidFuncPtr *createFunc ) { RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); unsigned ndfail = asmap->numDataFailed; unsigned npfail = asmap->numParityFailed + asmap->numQFailed; unsigned ntfail = npfail + ndfail; RF_ASSERT(RF_IO_IS_R_OR_W(type)); if (ntfail > 2) { RF_ERRORMSG("more than two disks failed in a single group !" " Aborting I/O operation.\n"); /* *infoFunc = */ *createFunc = NULL; return; } /* Ok, we can do this I/O. */ if (type == RF_IO_TYPE_READ) { switch (ndfail) { case 0: /* Fault free read. */ *createFunc = (RF_VoidFuncPtr) rf_CreateFaultFreeReadDAG; /* Same as raid 5. */ break; case 1: /* Lost a single data unit. */ /* * Two cases: * (1) Parity is not lost. Do a normal raid 5 * reconstruct read. * (2) Parity is lost. Do a reconstruct read using "e". */ if (ntfail == 2) { /* Also lost redundancy. */ if (asmap->failedPDAs[1]->type == RF_PDA_TYPE_PARITY) *createFunc = (RF_VoidFuncPtr) rf_EO_110_CreateReadDAG; else *createFunc = (RF_VoidFuncPtr) rf_EO_101_CreateReadDAG; } else { /* * P and E are ok. But is there a failure in * some unaccessed data unit ? */ if (rf_NumFailedDataUnitsInStripe(raidPtr, asmap) == 2) *createFunc = (RF_VoidFuncPtr) rf_EO_200_CreateReadDAG; else *createFunc = (RF_VoidFuncPtr) rf_EO_100_CreateReadDAG; } break; case 2: /* *createFunc = rf_EO_200_CreateReadDAG; */ *createFunc = NULL; break; } return; } /* A write. */ switch (ntfail) { case 0: /* Fault free. */ if (rf_suppressLocksAndLargeWrites || (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) && (layoutPtr->numDataCol != 1)) || (asmap->parityInfo->next != NULL) || (asmap->qInfo->next != NULL) || rf_CheckStripeForFailures(raidPtr, asmap))) { *createFunc = (RF_VoidFuncPtr) rf_EOCreateSmallWriteDAG; } else { *createFunc = (RF_VoidFuncPtr) rf_EOCreateLargeWriteDAG; } break; case 1: /* Single disk fault. */ if (npfail == 1) { RF_ASSERT((asmap->failedPDAs[0]->type == RF_PDA_TYPE_PARITY) || (asmap->failedPDAs[0]->type == RF_PDA_TYPE_Q)); if (asmap->failedPDAs[0]->type == RF_PDA_TYPE_Q) { /* * q died, treat like normal mode raid5 * write. */ if (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) || (asmap->numStripeUnitsAccessed == 1)) || (asmap->parityInfo->next != NULL) || rf_NumFailedDataUnitsInStripe(raidPtr, asmap)) *createFunc = (RF_VoidFuncPtr) rf_EO_001_CreateSmallWriteDAG; else *createFunc = (RF_VoidFuncPtr) rf_EO_001_CreateLargeWriteDAG; } else { /* Parity died, small write only updating Q. */ if (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) || (asmap->numStripeUnitsAccessed == 1)) || (asmap->qInfo->next != NULL) || rf_NumFailedDataUnitsInStripe(raidPtr, asmap)) *createFunc = (RF_VoidFuncPtr) rf_EO_010_CreateSmallWriteDAG; else *createFunc = (RF_VoidFuncPtr) rf_EO_010_CreateLargeWriteDAG; } } else { /* * Data missing. Do a P reconstruct write if * only a single data unit is lost in the * stripe, otherwise a reconstruct write which * is employing both P and E units. */ if (rf_NumFailedDataUnitsInStripe(raidPtr, asmap) == 2) { if (asmap->numStripeUnitsAccessed == 1) *createFunc = (RF_VoidFuncPtr) rf_EO_200_CreateWriteDAG; else /* * No direct support for this case now, * like that in Raid-5. */ *createFunc = NULL; } else { if (asmap->numStripeUnitsAccessed != 1 && asmap->failedPDAs[0]->numSector != layoutPtr->sectorsPerStripeUnit) /* * No direct support for this case now, * like that in Raid-5. */ *createFunc = NULL; else *createFunc = (RF_VoidFuncPtr) rf_EO_100_CreateWriteDAG; } } break; case 2: /* Two disk faults. */ switch (npfail) { case 2: /* Both p and q dead. */ *createFunc = (RF_VoidFuncPtr) rf_EO_011_CreateWriteDAG; break; case 1: /* Either p or q and dead data. */ RF_ASSERT(asmap->failedPDAs[0]->type == RF_PDA_TYPE_DATA); RF_ASSERT((asmap->failedPDAs[1]->type == RF_PDA_TYPE_PARITY) || (asmap->failedPDAs[1]->type == RF_PDA_TYPE_Q)); if (asmap->failedPDAs[1]->type == RF_PDA_TYPE_Q) { if (asmap->numStripeUnitsAccessed != 1 && asmap->failedPDAs[0]->numSector != layoutPtr->sectorsPerStripeUnit) /* * In both PQ and EvenOdd, no direct * support for this case now, like that * in Raid-5. */ *createFunc = NULL; else *createFunc = (RF_VoidFuncPtr) rf_EO_101_CreateWriteDAG; } else { if (asmap->numStripeUnitsAccessed != 1 && asmap->failedPDAs[0]->numSector != layoutPtr->sectorsPerStripeUnit) /* * No direct support for this case, * like that in Raid-5. */ *createFunc = NULL; else *createFunc = (RF_VoidFuncPtr) rf_EO_110_CreateWriteDAG; } break; case 0: /* Double data loss. */ /* * if(asmap->failedPDAs[0]->numSector + * asmap->failedPDAs[1]->numSector == 2 * * layoutPtr->sectorsPerStripeUnit ) createFunc = * rf_EOCreateLargeWriteDAG; else */ *createFunc = NULL; /* * Currently, in Evenodd, no * support for simultaneous * access of both failed SUs. */ break; } break; default: /* More than 2 disk faults. */ *createFunc = NULL; RF_PANIC(); } return; } int rf_VerifyParityEvenOdd( RF_Raid_t *raidPtr, RF_RaidAddr_t raidAddr, RF_PhysDiskAddr_t *parityPDA, int correct_it, RF_RaidAccessFlags_t flags ) { RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); RF_RaidAddr_t startAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, raidAddr); RF_SectorCount_t numsector = parityPDA->numSector; int numbytes = rf_RaidAddressToByte(raidPtr, numsector); int bytesPerStripe = numbytes * layoutPtr->numDataCol; RF_DagHeader_t *rd_dag_h, *wr_dag_h; /* Read, write dag. */ RF_DagNode_t *blockNode, *unblockNode, *wrBlock, *wrUnblock; RF_AccessStripeMapHeader_t *asm_h; RF_AccessStripeMap_t *asmap; RF_AllocListElem_t *alloclist; RF_PhysDiskAddr_t *pda; char *pbuf, *buf, *end_p, *p; char *redundantbuf2; int redundantTwoErr = 0, redundantOneErr = 0; int parity_cant_correct = RF_FALSE, red2_cant_correct = RF_FALSE, parity_corrected = RF_FALSE, red2_corrected = RF_FALSE; int i, retcode; RF_ReconUnitNum_t which_ru; RF_StripeNum_t psID = rf_RaidAddressToParityStripeID(layoutPtr, raidAddr, &which_ru); int stripeWidth = layoutPtr->numDataCol + layoutPtr->numParityCol; RF_AccTraceEntry_t tracerec; RF_MCPair_t *mcpair; retcode = RF_PARITY_OKAY; mcpair = rf_AllocMCPair(); rf_MakeAllocList(alloclist); RF_MallocAndAdd(buf, numbytes * (layoutPtr->numDataCol + layoutPtr->numParityCol), (char *), alloclist); /* Use calloc to make sure buffer is zeroed. */ RF_CallocAndAdd(pbuf, 1, numbytes, (char *), alloclist); end_p = buf + bytesPerStripe; /* Use calloc to make sure buffer is zeroed. */ RF_CallocAndAdd(redundantbuf2, 1, numbytes, (char *), alloclist); rd_dag_h = rf_MakeSimpleDAG(raidPtr, stripeWidth, numbytes, buf, rf_DiskReadFunc, rf_DiskReadUndoFunc, "Rod", alloclist, flags, RF_IO_NORMAL_PRIORITY); blockNode = rd_dag_h->succedents[0]; unblockNode = blockNode->succedents[0]->succedents[0]; /* Map the stripe and fill in the PDAs in the dag. */ asm_h = rf_MapAccess(raidPtr, startAddr, layoutPtr->dataSectorsPerStripe, buf, RF_DONT_REMAP); asmap = asm_h->stripeMap; for (pda = asmap->physInfo, i = 0; i < layoutPtr->numDataCol; i++, pda = pda->next) { RF_ASSERT(pda); rf_RangeRestrictPDA(raidPtr, parityPDA, pda, 0, 1); RF_ASSERT(pda->numSector != 0); if (rf_TryToRedirectPDA(raidPtr, pda, 0)) /* * No way to verify parity if disk is dead. * Return w/ good status. */ goto out; blockNode->succedents[i]->params[0].p = pda; blockNode->succedents[i]->params[2].v = psID; blockNode->succedents[i]->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); } RF_ASSERT(!asmap->parityInfo->next); rf_RangeRestrictPDA(raidPtr, parityPDA, asmap->parityInfo, 0, 1); RF_ASSERT(asmap->parityInfo->numSector != 0); if (rf_TryToRedirectPDA(raidPtr, asmap->parityInfo, 1)) goto out; blockNode->succedents[layoutPtr->numDataCol]->params[0].p = asmap->parityInfo; RF_ASSERT(!asmap->qInfo->next); rf_RangeRestrictPDA(raidPtr, parityPDA, asmap->qInfo, 0, 1); RF_ASSERT(asmap->qInfo->numSector != 0); if (rf_TryToRedirectPDA(raidPtr, asmap->qInfo, 1)) goto out; /* * If disk is dead, b/c no reconstruction is implemented right now, * the function "rf_TryToRedirectPDA" always return one, which causes * go to out and return w/ good status. */ blockNode->succedents[layoutPtr->numDataCol + 1]->params[0].p = asmap->qInfo; /* Fire off the DAG. */ bzero(&tracerec, sizeof(tracerec)); rd_dag_h->tracerec = &tracerec; if (rf_verifyParityDebug) { printf("Parity verify read dag:\n"); rf_PrintDAGList(rd_dag_h); } RF_LOCK_MUTEX(mcpair->mutex); mcpair->flag = 0; rf_DispatchDAG(rd_dag_h, (void (*) (void *)) rf_MCPairWakeupFunc, (void *) mcpair); while (!mcpair->flag) RF_WAIT_COND(mcpair->cond, mcpair->mutex); RF_UNLOCK_MUTEX(mcpair->mutex); if (rd_dag_h->status != rf_enable) { RF_ERRORMSG("Unable to verify parity: can't read" " the stripe\n"); retcode = RF_PARITY_COULD_NOT_VERIFY; goto out; } for (p = buf, i = 0; p < end_p; p += numbytes, i++) { rf_e_encToBuf(raidPtr, i, p, RF_EO_MATRIX_DIM - 2, redundantbuf2, numsector); /* * The corresponding columns in EvenOdd encoding Matrix for * these p pointers that point to the databuffer in a full * stripe are sequential from 0 to layoutPtr->numDataCol-1. */ rf_bxor(p, pbuf, numbytes, NULL); } RF_ASSERT(i == layoutPtr->numDataCol); for (i = 0; i < numbytes; i++) { if (pbuf[i] != buf[bytesPerStripe + i]) { if (!correct_it) { RF_ERRORMSG3("Parity verify error: byte %d of" " parity is 0x%x should be 0x%x\n", i, (u_char) buf[bytesPerStripe + i], (u_char) pbuf[i]); } } redundantOneErr = 1; break; } for (i = 0; i < numbytes; i++) { if (redundantbuf2[i] != buf[bytesPerStripe + numbytes + i]) { if (!correct_it) { RF_ERRORMSG3("Parity verify error: byte %d of" " second redundant information is 0x%x" " should be 0x%x\n", i, (u_char) buf[bytesPerStripe + numbytes + i], (u_char) redundantbuf2[i]); } redundantTwoErr = 1; break; } } if (redundantOneErr || redundantTwoErr) retcode = RF_PARITY_BAD; /* Correct the first redundant disk, ie parity if it is error. */ if (redundantOneErr && correct_it) { wr_dag_h = rf_MakeSimpleDAG(raidPtr, 1, numbytes, pbuf, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, "Wnp", alloclist, flags, RF_IO_NORMAL_PRIORITY); wrBlock = wr_dag_h->succedents[0]; wrUnblock = wrBlock->succedents[0]->succedents[0]; wrBlock->succedents[0]->params[0].p = asmap->parityInfo; wrBlock->succedents[0]->params[2].v = psID; wrBlock->succedents[0]->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); bzero(&tracerec, sizeof(tracerec)); wr_dag_h->tracerec = &tracerec; if (rf_verifyParityDebug) { printf("Parity verify write dag:\n"); rf_PrintDAGList(wr_dag_h); } RF_LOCK_MUTEX(mcpair->mutex); mcpair->flag = 0; rf_DispatchDAG(wr_dag_h, (void (*) (void *)) rf_MCPairWakeupFunc, (void *) mcpair); while (!mcpair->flag) RF_WAIT_COND(mcpair->cond, mcpair->mutex); RF_UNLOCK_MUTEX(mcpair->mutex); if (wr_dag_h->status != rf_enable) { RF_ERRORMSG("Unable to correct parity in VerifyParity:" " can't write the stripe\n"); parity_cant_correct = RF_TRUE; } else { parity_corrected = RF_TRUE; } rf_FreeDAG(wr_dag_h); } if (redundantTwoErr && correct_it) { wr_dag_h = rf_MakeSimpleDAG(raidPtr, 1, numbytes, redundantbuf2, rf_DiskWriteFunc, rf_DiskWriteUndoFunc, "Wnred2", alloclist, flags, RF_IO_NORMAL_PRIORITY); wrBlock = wr_dag_h->succedents[0]; wrUnblock = wrBlock->succedents[0]->succedents[0]; wrBlock->succedents[0]->params[0].p = asmap->qInfo; wrBlock->succedents[0]->params[2].v = psID; wrBlock->succedents[0]->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0, 0, which_ru); bzero(&tracerec, sizeof(tracerec)); wr_dag_h->tracerec = &tracerec; if (rf_verifyParityDebug) { printf("Dag of write new second redundant information" " in parity verify :\n"); rf_PrintDAGList(wr_dag_h); } RF_LOCK_MUTEX(mcpair->mutex); mcpair->flag = 0; rf_DispatchDAG(wr_dag_h, (void (*) (void *)) rf_MCPairWakeupFunc, (void *) mcpair); while (!mcpair->flag) RF_WAIT_COND(mcpair->cond, mcpair->mutex); RF_UNLOCK_MUTEX(mcpair->mutex); if (wr_dag_h->status != rf_enable) { RF_ERRORMSG("Unable to correct second redundant" " information in VerifyParity: can't write the" " stripe\n"); red2_cant_correct = RF_TRUE; } else { red2_corrected = RF_TRUE; } rf_FreeDAG(wr_dag_h); } if ((redundantOneErr && parity_cant_correct) || (redundantTwoErr && red2_cant_correct)) retcode = RF_PARITY_COULD_NOT_CORRECT; if ((retcode = RF_PARITY_BAD) && parity_corrected && red2_corrected) retcode = RF_PARITY_CORRECTED; out: rf_FreeAccessStripeMap(asm_h); rf_FreeAllocList(alloclist); rf_FreeDAG(rd_dag_h); rf_FreeMCPair(mcpair); return (retcode); } #endif /* RF_INCLUDE_EVENODD > 0 */