/* $OpenBSD: rf_evenodd_dagfuncs.c,v 1.7 2002/12/16 07:01:04 tdeval Exp $ */
/* $NetBSD: rf_evenodd_dagfuncs.c,v 1.6 2000/03/30 12:45:40 augustss Exp $ */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Author: ChangMing 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.
*/
/*
* Code for RAID-EVENODD architecture.
*/
#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_configure.h"
#include "rf_parityscan.h"
#include "rf_evenodd.h"
#include "rf_evenodd_dagfuncs.h"
/* These redundant functions are for small write. */
RF_RedFuncs_t rf_EOSmallWritePFuncs = {
rf_RegularXorFunc, "Regular Old-New P",
rf_SimpleXorFunc, "Simple Old-New P"
};
RF_RedFuncs_t rf_EOSmallWriteEFuncs = {
rf_RegularONEFunc, "Regular Old-New E",
rf_SimpleONEFunc, "Regular Old-New E"
};
/* These redundant functions are for degraded read. */
RF_RedFuncs_t rf_eoPRecoveryFuncs = {
rf_RecoveryXorFunc, "Recovery Xr",
rf_RecoveryXorFunc, "Recovery Xr"
};
RF_RedFuncs_t rf_eoERecoveryFuncs = {
rf_RecoveryEFunc, "Recovery E Func",
rf_RecoveryEFunc, "Recovery E Func"
};
/*****************************************************************************
* The following encoding node functions is used in
* EO_000_CreateLargeWriteDAG.
*****************************************************************************/
int
rf_RegularPEFunc(RF_DagNode_t *node)
{
rf_RegularESubroutine(node, node->results[1]);
rf_RegularXorFunc(node); /* Do the wakeup here ! */
#if 1
return (0); /* XXX This was missing... GO */
#endif
}
/*****************************************************************************
* For EO_001_CreateSmallWriteDAG, there are (i) RegularONEFunc() and
* (ii) SimpleONEFunc() to be used. The previous case is when write accesses
* at least sectors of full stripe unit.
* The later function is used when the write accesses two stripe units but
* with total sectors less than sectors per SU. In this case, the access of
* parity and 'E' are shown as disconnected areas in their stripe unit and
* parity write and 'E' write are both divided into two distinct writes
* (totally four). This simple old-new write and regular old-new write happen
* as in RAID-5.
*****************************************************************************/
/*
* Algorithm:
* 1. Store the difference of old data and new data in the Rod buffer.
* 2. Then encode this buffer into the buffer that already have old 'E'
* information inside it, the result can be shown to be the new 'E'
* information.
* 3. Xor the Wnd buffer into the difference buffer to recover the original
* old data.
* Here we have another alternative: to allocate a temporary buffer for
* storing the difference of old data and new data, then encode temp buf
* into old 'E' buf to form new 'E', but this approach takes the same speed
* as the previous, and needs more memory.
*/
int
rf_RegularONEFunc(RF_DagNode_t *node)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
int EpdaIndex = (node->numParams - 1) / 2 - 1; /*
* The parameter of node
* where you can find
* e-pda.
*/
int i, k, retcode = 0;
int suoffset, length;
RF_RowCol_t scol;
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
RF_PhysDiskAddr_t *pda, *EPDA = (RF_PhysDiskAddr_t *)
node->params[EpdaIndex].p;
/* Generally zero. */
int ESUOffset = rf_StripeUnitOffset(layoutPtr, EPDA->startSector);
RF_ASSERT(EPDA->type == RF_PDA_TYPE_Q);
RF_ASSERT(ESUOffset == 0);
RF_ETIMER_START(timer);
/*
* Xor the Wnd buffer into Rod buffer. The difference of old data and
* new data is stored in Rod buffer.
*/
for (k = 0; k < EpdaIndex; k += 2) {
length = rf_RaidAddressToByte(raidPtr,
((RF_PhysDiskAddr_t *) node->params[k].p)->numSector);
retcode = rf_bxor(node->params[k + EpdaIndex + 3].p,
node->params[k + 1].p, length, node->dagHdr->bp);
}
/*
* Start to encode the buffer, storing the difference of old data and
* new data into 'E' buffer.
*/
for (i = 0; i < EpdaIndex; i += 2)
if (node->params[i + 1].p != node->results[0]) {
/* results[0] is buf ptr of E. */
pda = (RF_PhysDiskAddr_t *) node->params[i].p;
srcbuf = (char *) node->params[i + 1].p;
scol = rf_EUCol(layoutPtr, pda->raidAddress);
suoffset = rf_StripeUnitOffset(layoutPtr,
pda->startSector);
destbuf = ((char *) node->results[0]) +
rf_RaidAddressToByte(raidPtr, suoffset);
rf_e_encToBuf(raidPtr, scol, srcbuf,
RF_EO_MATRIX_DIM - 2, destbuf, pda->numSector);
}
/*
* Recover the original old data to be used by parity encoding
* function in XorNode.
*/
for (k = 0; k < EpdaIndex; k += 2) {
length = rf_RaidAddressToByte(raidPtr,
((RF_PhysDiskAddr_t *) node->params[k].p)->numSector);
retcode = rf_bxor(node->params[k + EpdaIndex + 3].p,
node->params[k + 1].p, length, node->dagHdr->bp);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
rf_GenericWakeupFunc(node, 0);
#if 1
return (0); /* XXX This was missing... GO */
#endif
}
int
rf_SimpleONEFunc(RF_DagNode_t *node)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
RF_PhysDiskAddr_t *pda = (RF_PhysDiskAddr_t *) node->params[0].p;
int retcode = 0;
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
int length;
RF_RowCol_t scol;
RF_Etimer_t timer;
RF_ASSERT(((RF_PhysDiskAddr_t *) node->params[2].p)->type ==
RF_PDA_TYPE_Q);
if (node->dagHdr->status == rf_enable) {
RF_ETIMER_START(timer);
/* This is a pda of writeDataNodes. */
length = rf_RaidAddressToByte(raidPtr,
((RF_PhysDiskAddr_t *) node->params[4].p)->numSector);
/* bxor to buffer of readDataNodes. */
retcode = rf_bxor(node->params[5].p, node->params[1].p,
length, node->dagHdr->bp);
/*
* Find out the corresponding column in encoding matrix for
* write column to be encoded into redundant disk 'E'.
*/
scol = rf_EUCol(layoutPtr, pda->raidAddress);
srcbuf = node->params[1].p;
destbuf = node->params[3].p;
/* Start encoding process. */
rf_e_encToBuf(raidPtr, scol, srcbuf, RF_EO_MATRIX_DIM - 2,
destbuf, pda->numSector);
rf_bxor(node->params[5].p, node->params[1].p, length,
node->dagHdr->bp);
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
return (rf_GenericWakeupFunc(node, retcode)); /*
* Call wake func
* explicitly since no
* I/O in this node.
*/
}
/*
* Called by rf_RegularPEFunc(node) and rf_RegularEFunc(node)
* in f.f. large write.
*/
void
rf_RegularESubroutine(RF_DagNode_t *node, char *ebuf)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
RF_PhysDiskAddr_t *pda;
int i, suoffset;
RF_RowCol_t scol;
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
RF_ETIMER_START(timer);
for (i = 0; i < node->numParams - 2; i += 2) {
RF_ASSERT(node->params[i + 1].p != ebuf);
pda = (RF_PhysDiskAddr_t *) node->params[i].p;
suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
scol = rf_EUCol(layoutPtr, pda->raidAddress);
srcbuf = (char *) node->params[i + 1].p;
destbuf = ebuf + rf_RaidAddressToByte(raidPtr, suoffset);
rf_e_encToBuf(raidPtr, scol, srcbuf, RF_EO_MATRIX_DIM - 2,
destbuf, pda->numSector);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->xor_us += RF_ETIMER_VAL_US(timer);
}
/*****************************************************************************
* Used in EO_001_CreateLargeWriteDAG.
*****************************************************************************/
int
rf_RegularEFunc(RF_DagNode_t *node)
{
rf_RegularESubroutine(node, node->results[0]);
rf_GenericWakeupFunc(node, 0);
#if 1
return (0); /* XXX This was missing... GO */
#endif
}
/*****************************************************************************
* This degraded function allow only two cases:
* 1. When write accesses the full failed stripe unit, then the access can
* be more than one stripe unit.
* 2. When write accesses only part of the failed SU, we assume accesses of
* more than one stripe unit are not allowed so that the write can be
* dealt with like a large write.
* The following function is based on these assumptions. So except in the
* second case, it looks the same as a large write encoding function. But
* this is not exactly the normal way of doing a degraded write, since
* RAIDframe has to break cases of accesses other than the above two into
* smaller accesses. We may have to change DegrESubroutin in the future.
*****************************************************************************/
void
rf_DegrESubroutine(RF_DagNode_t *node, char *ebuf)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
RF_PhysDiskAddr_t *failedPDA = (RF_PhysDiskAddr_t *) node->params[node->numParams - 2].p;
RF_PhysDiskAddr_t *pda;
int i, suoffset, failedSUOffset = rf_StripeUnitOffset(layoutPtr, failedPDA->startSector);
RF_RowCol_t scol;
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
RF_ETIMER_START(timer);
for (i = 0; i < node->numParams - 2; i += 2) {
RF_ASSERT(node->params[i + 1].p != ebuf);
pda = (RF_PhysDiskAddr_t *) node->params[i].p;
suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
scol = rf_EUCol(layoutPtr, pda->raidAddress);
srcbuf = (char *) node->params[i + 1].p;
destbuf = ebuf + rf_RaidAddressToByte(raidPtr, suoffset - failedSUOffset);
rf_e_encToBuf(raidPtr, scol, srcbuf, RF_EO_MATRIX_DIM - 2, destbuf, pda->numSector);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
/*****************************************************************************
* This function is used in case where one data disk failed and both redundant
* disks are alive. It is used in the EO_100_CreateWriteDAG. Note: if there is
* another disk failed in the stripe but not accessed at this time, then we
* should, instead, use the rf_EOWriteDoubleRecoveryFunc().
*****************************************************************************/
int
rf_Degraded_100_EOFunc(RF_DagNode_t *node)
{
rf_DegrESubroutine(node, node->results[1]);
rf_RecoveryXorFunc(node); /* Does the wakeup here ! */
#if 1
return (0); /* XXX This was missing... Should these be
* void functions ??? GO */
#endif
}
/*****************************************************************************
* This function is to encode one sector in one of the data disks to the E
* disk. However, in evenodd this function can also be used as decoding
* function to recover data from dead disk in the case of parity failure and
* a single data failure.
*****************************************************************************/
void
rf_e_EncOneSect(RF_RowCol_t srcLogicCol, char *srcSecbuf,
RF_RowCol_t destLogicCol, char *destSecbuf, int bytesPerSector)
{
int S_index; /*
* Index of the EU in the src col which need
* be Xored into all EUs in a dest sector.
*/
int numRowInEncMatrix = (RF_EO_MATRIX_DIM) - 1;
RF_RowCol_t j, indexInDest; /*
* Row index of an encoding unit in
* the destination column of encoding
* matrix.
*/
RF_RowCol_t indexInSrc; /*
* Row index of an encoding unit in the source
* column used for recovery.
*/
int bytesPerEU = bytesPerSector / numRowInEncMatrix;
#if RF_EO_MATRIX_DIM > 17
int shortsPerEU = bytesPerEU / sizeof(short);
short *destShortBuf, *srcShortBuf1, *srcShortBuf2;
short temp1;
#elif RF_EO_MATRIX_DIM == 17
int longsPerEU = bytesPerEU / sizeof(long);
long *destLongBuf, *srcLongBuf1, *srcLongBuf2;
long temp1;
#endif
#if RF_EO_MATRIX_DIM > 17
RF_ASSERT(sizeof(short) == 2 || sizeof(short) == 1);
RF_ASSERT(bytesPerEU % sizeof(short) == 0);
#elif RF_EO_MATRIX_DIM == 17
RF_ASSERT(sizeof(long) == 8 || sizeof(long) == 4);
RF_ASSERT(bytesPerEU % sizeof(long) == 0);
#endif
S_index = rf_EO_Mod((RF_EO_MATRIX_DIM - 1 + destLogicCol - srcLogicCol), RF_EO_MATRIX_DIM);
#if RF_EO_MATRIX_DIM > 17
srcShortBuf1 = (short *) (srcSecbuf + S_index * bytesPerEU);
#elif RF_EO_MATRIX_DIM == 17
srcLongBuf1 = (long *) (srcSecbuf + S_index * bytesPerEU);
#endif
for (indexInDest = 0; indexInDest < numRowInEncMatrix; indexInDest++) {
indexInSrc = rf_EO_Mod((indexInDest + destLogicCol - srcLogicCol), RF_EO_MATRIX_DIM);
#if RF_EO_MATRIX_DIM > 17
destShortBuf = (short *) (destSecbuf + indexInDest * bytesPerEU);
srcShortBuf2 = (short *) (srcSecbuf + indexInSrc * bytesPerEU);
for (j = 0; j < shortsPerEU; j++) {
temp1 = destShortBuf[j] ^ srcShortBuf1[j];
/* Note: S_index won't be at the end row for any src
* col ! */
if (indexInSrc != RF_EO_MATRIX_DIM - 1)
destShortBuf[j] = (srcShortBuf2[j]) ^ temp1;
/* if indexInSrc is at the end row, ie.
* RF_EO_MATRIX_DIM -1, then all elements are zero ! */
else
destShortBuf[j] = temp1;
}
#elif RF_EO_MATRIX_DIM == 17
destLongBuf = (long *) (destSecbuf + indexInDest * bytesPerEU);
srcLongBuf2 = (long *) (srcSecbuf + indexInSrc * bytesPerEU);
for (j = 0; j < longsPerEU; j++) {
temp1 = destLongBuf[j] ^ srcLongBuf1[j];
if (indexInSrc != RF_EO_MATRIX_DIM - 1)
destLongBuf[j] = (srcLongBuf2[j]) ^ temp1;
else
destLongBuf[j] = temp1;
}
#endif
}
}
void
rf_e_encToBuf(RF_Raid_t *raidPtr, RF_RowCol_t srcLogicCol, char *srcbuf,
RF_RowCol_t destLogicCol, char *destbuf, int numSector)
{
int i, bytesPerSector = rf_RaidAddressToByte(raidPtr, 1);
for (i = 0; i < numSector; i++) {
rf_e_EncOneSect(srcLogicCol, srcbuf, destLogicCol, destbuf, bytesPerSector);
srcbuf += bytesPerSector;
destbuf += bytesPerSector;
}
}
/*****************************************************************************
* when parity die and one data die, We use second redundant information, 'E',
* to recover the data in dead disk. This function is used in the recovery node of
* for EO_110_CreateReadDAG
*****************************************************************************/
int
rf_RecoveryEFunc(RF_DagNode_t *node)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & raidPtr->Layout;
RF_PhysDiskAddr_t *failedPDA = (RF_PhysDiskAddr_t *) node->params[node->numParams - 2].p;
RF_RowCol_t scol; /* source logical column */
RF_RowCol_t fcol = rf_EUCol(layoutPtr, failedPDA->raidAddress); /* logical column of
* failed SU */
int i;
RF_PhysDiskAddr_t *pda;
int suoffset, failedSUOffset = rf_StripeUnitOffset(layoutPtr, failedPDA->startSector);
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
bzero((char *) node->results[0], rf_RaidAddressToByte(raidPtr, failedPDA->numSector));
if (node->dagHdr->status == rf_enable) {
RF_ETIMER_START(timer);
for (i = 0; i < node->numParams - 2; i += 2)
if (node->params[i + 1].p != node->results[0]) {
pda = (RF_PhysDiskAddr_t *) node->params[i].p;
if (i == node->numParams - 4)
scol = RF_EO_MATRIX_DIM - 2; /* the colume of
* redundant E */
else
scol = rf_EUCol(layoutPtr, pda->raidAddress);
srcbuf = (char *) node->params[i + 1].p;
suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
destbuf = ((char *) node->results[0]) + rf_RaidAddressToByte(raidPtr, suoffset - failedSUOffset);
rf_e_encToBuf(raidPtr, scol, srcbuf, fcol, destbuf, pda->numSector);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->xor_us += RF_ETIMER_VAL_US(timer);
}
return (rf_GenericWakeupFunc(node, 0)); /* node execute successfully */
}
/*****************************************************************************
* This function is used in the case where one data and the parity have filed.
* (in EO_110_CreateWriteDAG)
*****************************************************************************/
int
rf_EO_DegradedWriteEFunc(RF_DagNode_t *node)
{
rf_DegrESubroutine(node, node->results[0]);
rf_GenericWakeupFunc(node, 0);
#if 1
return (0); /* XXX Yet another one !!! GO */
#endif
}
/*****************************************************************************
* THE FUNCTION IS FOR DOUBLE DEGRADED READ AND WRITE CASES.
*****************************************************************************/
void
rf_doubleEOdecode(RF_Raid_t *raidPtr, char **rrdbuf, char **dest,
RF_RowCol_t *fcol, char *pbuf, char *ebuf)
{
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) &(raidPtr->Layout);
int i, j, k, f1, f2, row;
int rrdrow, erow, count = 0;
int bytesPerSector = rf_RaidAddressToByte(raidPtr, 1);
int numRowInEncMatrix = (RF_EO_MATRIX_DIM) - 1;
#if 0
int pcol = (RF_EO_MATRIX_DIM) - 1;
#endif
int ecol = (RF_EO_MATRIX_DIM) - 2;
int bytesPerEU = bytesPerSector / numRowInEncMatrix;
int numDataCol = layoutPtr->numDataCol;
#if RF_EO_MATRIX_DIM > 17
int shortsPerEU = bytesPerEU / sizeof(short);
short *rrdbuf_current, *pbuf_current, *ebuf_current;
short *dest_smaller, *dest_smaller_current;
short *dest_larger, *dest_larger_current;
short *temp;
short *P;
RF_ASSERT(bytesPerEU % sizeof(short) == 0);
RF_Malloc(P, bytesPerEU, (short *));
RF_Malloc(temp, bytesPerEU, (short *));
#elif RF_EO_MATRIX_DIM == 17
int longsPerEU = bytesPerEU / sizeof(long);
long *rrdbuf_current, *pbuf_current, *ebuf_current;
long *dest_smaller, *dest_smaller_current;
long *dest_larger, *dest_larger_current;
long *temp;
long *P;
RF_ASSERT(bytesPerEU % sizeof(long) == 0);
RF_Malloc(P, bytesPerEU, (long *));
RF_Malloc(temp, bytesPerEU, (long *));
#endif
RF_ASSERT(*((long *) dest[0]) == 0);
RF_ASSERT(*((long *) dest[1]) == 0);
bzero((char *) P, bytesPerEU);
bzero((char *) temp, bytesPerEU);
RF_ASSERT(*P == 0);
/*
* Calculate the 'P' parameter, which, not parity, is the Xor of all
* elements in the last two column, ie. 'E' and 'parity' columns, see
* the Ref. paper by Blaum, et al 1993.
*/
for (i = 0; i < numRowInEncMatrix; i++)
for (k = 0; k < longsPerEU; k++) {
#if RF_EO_MATRIX_DIM > 17
ebuf_current = ((short *) ebuf) + i * shortsPerEU + k;
pbuf_current = ((short *) pbuf) + i * shortsPerEU + k;
#elif RF_EO_MATRIX_DIM == 17
ebuf_current = ((long *) ebuf) + i * longsPerEU + k;
pbuf_current = ((long *) pbuf) + i * longsPerEU + k;
#endif
P[k] ^= *ebuf_current;
P[k] ^= *pbuf_current;
}
RF_ASSERT(fcol[0] != fcol[1]);
if (fcol[0] < fcol[1]) {
#if RF_EO_MATRIX_DIM > 17
dest_smaller = (short *) (dest[0]);
dest_larger = (short *) (dest[1]);
#elif RF_EO_MATRIX_DIM == 17
dest_smaller = (long *) (dest[0]);
dest_larger = (long *) (dest[1]);
#endif
f1 = fcol[0];
f2 = fcol[1];
} else {
#if RF_EO_MATRIX_DIM > 17
dest_smaller = (short *) (dest[1]);
dest_larger = (short *) (dest[0]);
#elif RF_EO_MATRIX_DIM == 17
dest_smaller = (long *) (dest[1]);
dest_larger = (long *) (dest[0]);
#endif
f1 = fcol[1];
f2 = fcol[0];
}
row = (RF_EO_MATRIX_DIM) - 1;
while ((row = rf_EO_Mod((row + f1 - f2), RF_EO_MATRIX_DIM)) !=
((RF_EO_MATRIX_DIM) - 1)) {
#if RF_EO_MATRIX_DIM > 17
dest_larger_current = dest_larger + row * shortsPerEU;
dest_smaller_current = dest_smaller + row * shortsPerEU;
#elif RF_EO_MATRIX_DIM == 17
dest_larger_current = dest_larger + row * longsPerEU;
dest_smaller_current = dest_smaller + row * longsPerEU;
#endif
/*
* Do the diagonal recovery. Initially, temp[k] = (failed 1),
* which is the failed data in the column that has smaller
* col index.
*/
/* Step 1: ^(SUM of nonfailed in-diagonal A(rrdrow,0..m-3)) */
for (j = 0; j < numDataCol; j++) {
if (j == f1 || j == f2)
continue;
rrdrow = rf_EO_Mod((row + f2 - j), RF_EO_MATRIX_DIM);
if (rrdrow != (RF_EO_MATRIX_DIM) - 1) {
#if RF_EO_MATRIX_DIM > 17
rrdbuf_current = (short *) (rrdbuf[j]) +
rrdrow * shortsPerEU;
for (k = 0; k < shortsPerEU; k++)
temp[k] ^= *(rrdbuf_current + k);
#elif RF_EO_MATRIX_DIM == 17
rrdbuf_current = (long *) (rrdbuf[j]) +
rrdrow * longsPerEU;
for (k = 0; k < longsPerEU; k++)
temp[k] ^= *(rrdbuf_current + k);
#endif
}
}
/*
* Step 2: ^E(erow,m-2), If erow is at the bottom row, don't
* Xor into it. E(erow,m-2) = (principle diagonal) ^ (failed
* 1) ^ (failed 2) ^ (SUM of nonfailed in-diagonal
* A(rrdrow,0..m-3))
* After this step, temp[k] = (principle diagonal) ^ (failed 2).
*/
erow = rf_EO_Mod((row + f2 - ecol), (RF_EO_MATRIX_DIM));
if (erow != (RF_EO_MATRIX_DIM) - 1) {
#if RF_EO_MATRIX_DIM > 17
ebuf_current = (short *) ebuf + shortsPerEU * erow;
for (k = 0; k < shortsPerEU; k++)
temp[k] ^= *(ebuf_current + k);
#elif RF_EO_MATRIX_DIM == 17
ebuf_current = (long *) ebuf + longsPerEU * erow;
for (k = 0; k < longsPerEU; k++)
temp[k] ^= *(ebuf_current + k);
#endif
}
/*
* Step 3: ^P to obtain the failed data (failed 2). P can be
* proved to be actually (principal diagonal). After this
* step, temp[k] = (failed 2), the failed data to be recovered.
*/
#if RF_EO_MATRIX_DIM > 17
for (k = 0; k < shortsPerEU; k++)
temp[k] ^= P[k];
/* Put the data into the destination buffer. */
for (k = 0; k < shortsPerEU; k++)
dest_larger_current[k] = temp[k];
#elif RF_EO_MATRIX_DIM == 17
for (k = 0; k < longsPerEU; k++)
temp[k] ^= P[k];
/* Put the data into the destination buffer. */
for (k = 0; k < longsPerEU; k++)
dest_larger_current[k] = temp[k];
#endif
/* THE FOLLOWING DO THE HORIZONTAL XOR. */
/*
* Step 1: ^(SUM of A(row,0..m-3)), ie. all nonfailed data
* columns.
*/
for (j = 0; j < numDataCol; j++) {
if (j == f1 || j == f2)
continue;
#if RF_EO_MATRIX_DIM > 17
rrdbuf_current = (short *) (rrdbuf[j]) +
row * shortsPerEU;
for (k = 0; k < shortsPerEU; k++)
temp[k] ^= *(rrdbuf_current + k);
#elif RF_EO_MATRIX_DIM == 17
rrdbuf_current = (long *) (rrdbuf[j]) +
row * longsPerEU;
for (k = 0; k < longsPerEU; k++)
temp[k] ^= *(rrdbuf_current + k);
#endif
}
/* Step 2: ^A(row,m-1) */
/* Step 3: Put the data into the destination buffer. */
#if RF_EO_MATRIX_DIM > 17
pbuf_current = (short *) pbuf + shortsPerEU * row;
for (k = 0; k < shortsPerEU; k++)
temp[k] ^= *(pbuf_current + k);
for (k = 0; k < shortsPerEU; k++)
dest_smaller_current[k] = temp[k];
#elif RF_EO_MATRIX_DIM == 17
pbuf_current = (long *) pbuf + longsPerEU * row;
for (k = 0; k < longsPerEU; k++)
temp[k] ^= *(pbuf_current + k);
for (k = 0; k < longsPerEU; k++)
dest_smaller_current[k] = temp[k];
#endif
count++;
}
/*
* Check if all Encoding Unit in the data buffer have been decoded ?
* According to EvenOdd theory, if "RF_EO_MATRIX_DIM" is a prime
* number, this algorithm will covered all buffer.
*/
RF_ASSERT(count == numRowInEncMatrix);
RF_Free((char *) P, bytesPerEU);
RF_Free((char *) temp, bytesPerEU);
}
/*****************************************************************************
* This function is called by double degraded read EO_200_CreateReadDAG.
*****************************************************************************/
int
rf_EvenOddDoubleRecoveryFunc(RF_DagNode_t *node)
{
int ndataParam = 0;
int np = node->numParams;
RF_AccessStripeMap_t *asmap = (RF_AccessStripeMap_t *)
node->params[np - 1].p;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 2].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) & (raidPtr->Layout);
int i, prm, sector, nresults = node->numResults;
RF_SectorCount_t secPerSU = layoutPtr->sectorsPerStripeUnit;
unsigned sosAddr;
int two = 0, mallc_one = 0, mallc_two = 0; /*
* Flags to indicate if
* memory is allocated.
*/
int bytesPerSector = rf_RaidAddressToByte(raidPtr, 1);
RF_PhysDiskAddr_t *ppda, *ppda2, *epda, *epda2, *pda, *pda0, *pda1,
npda;
RF_RowCol_t fcol[2], fsuoff[2], fsuend[2],
numDataCol = layoutPtr->numDataCol;
char **buf, *ebuf, *pbuf, *dest[2];
long *suoff = NULL, *suend = NULL, *prmToCol = NULL, psuoff, esuoff;
RF_SectorNum_t startSector, endSector;
RF_Etimer_t timer;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_ETIMER_START(timer);
/*
* Find out the number of parameters that are pdas for data
* information.
*/
for (i = 0; i <= np; i++)
if (((RF_PhysDiskAddr_t *) node->params[i].p)->type !=
RF_PDA_TYPE_DATA) {
ndataParam = i;
break;
}
RF_Malloc(buf, numDataCol * sizeof(char *), (char **));
if (ndataParam != 0) {
RF_Malloc(suoff, ndataParam * sizeof(long), (long *));
RF_Malloc(suend, ndataParam * sizeof(long), (long *));
RF_Malloc(prmToCol, ndataParam * sizeof(long), (long *));
}
if (asmap->failedPDAs[1] &&
(asmap->failedPDAs[1]->numSector +
asmap->failedPDAs[0]->numSector) < secPerSU) {
RF_ASSERT(0); /* Currently, no support for this situation. */
ppda = node->params[np - 6].p;
ppda2 = node->params[np - 5].p;
RF_ASSERT(ppda2->type == RF_PDA_TYPE_PARITY);
epda = node->params[np - 4].p;
epda2 = node->params[np - 3].p;
RF_ASSERT(epda2->type == RF_PDA_TYPE_Q);
two = 1;
} else {
ppda = node->params[np - 4].p;
epda = node->params[np - 3].p;
psuoff = rf_StripeUnitOffset(layoutPtr, ppda->startSector);
esuoff = rf_StripeUnitOffset(layoutPtr, epda->startSector);
RF_ASSERT(psuoff == esuoff);
}
/*
* The followings have three goals:
* 1. Determine the startSector to begin decoding and endSector
* to end decoding.
* 2. Determine the column numbers of the two failed disks.
* 3. Determine the offset and end offset of the access within
* each failed stripe unit.
*/
if (nresults == 1) {
/* Find the startSector to begin decoding. */
pda = node->results[0];
bzero(pda->bufPtr, bytesPerSector * pda->numSector);
fsuoff[0] = rf_StripeUnitOffset(layoutPtr, pda->startSector);
fsuend[0] = fsuoff[0] + pda->numSector;
startSector = fsuoff[0];
endSector = fsuend[0];
/* Find out the column of failed disk being accessed. */
fcol[0] = rf_EUCol(layoutPtr, pda->raidAddress);
/* Find out the other failed column not accessed. */
sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
asmap->raidAddress);
for (i = 0; i < numDataCol; i++) {
npda.raidAddress = sosAddr + (i * secPerSU);
(raidPtr->Layout.map->MapSector) (raidPtr,
npda.raidAddress, &(npda.row), &(npda.col),
&(npda.startSector), 0);
/* Skip over dead disks. */
if (RF_DEAD_DISK(raidPtr
->Disks[npda.row][npda.col].status))
if (i != fcol[0])
break;
}
RF_ASSERT(i < numDataCol);
fcol[1] = i;
} else {
RF_ASSERT(nresults == 2);
pda0 = node->results[0];
bzero(pda0->bufPtr, bytesPerSector * pda0->numSector);
pda1 = node->results[1];
bzero(pda1->bufPtr, bytesPerSector * pda1->numSector);
/*
* Determine the failed column numbers of the two failed
* disks.
*/
fcol[0] = rf_EUCol(layoutPtr, pda0->raidAddress);
fcol[1] = rf_EUCol(layoutPtr, pda1->raidAddress);
/*
* Determine the offset and end offset of the access within
* each failed stripe unit.
*/
fsuoff[0] = rf_StripeUnitOffset(layoutPtr, pda0->startSector);
fsuend[0] = fsuoff[0] + pda0->numSector;
fsuoff[1] = rf_StripeUnitOffset(layoutPtr, pda1->startSector);
fsuend[1] = fsuoff[1] + pda1->numSector;
/* Determine the startSector to begin decoding. */
startSector = RF_MIN(pda0->startSector, pda1->startSector);
/* Determine the endSector to end decoding. */
endSector = RF_MAX(fsuend[0], fsuend[1]);
}
/*
* Assign the beginning sector and the end sector for each parameter.
* Find out the corresponding column # for each parameter.
*/
for (prm = 0; prm < ndataParam; prm++) {
pda = node->params[prm].p;
suoff[prm] = rf_StripeUnitOffset(layoutPtr, pda->startSector);
suend[prm] = suoff[prm] + pda->numSector;
prmToCol[prm] = rf_EUCol(layoutPtr, pda->raidAddress);
}
/*
* 'sector' is the sector for the current decoding algorithm. For each
* sector in the failed SU
* 1. Find out the corresponding parameters that cover the current
* sector and that are needed for the decoding of this sector in
* failed SU.
* 2. Find out if sector is in the shadow of any accessed failed SU.
* If not, malloc a temporary space of a sector in size.
*/
for (sector = startSector; sector < endSector; sector++) {
if (nresults == 2)
if (!(fsuoff[0] <= sector && sector < fsuend[0]) &&
!(fsuoff[1] <= sector && sector < fsuend[1]))
continue;
for (prm = 0; prm < ndataParam; prm++)
if (suoff[prm] <= sector && sector < suend[prm])
buf[(prmToCol[prm])] = ((RF_PhysDiskAddr_t *)
node->params[prm].p)->bufPtr +
rf_RaidAddressToByte(raidPtr,
sector - suoff[prm]);
/*
* Find out if sector is in the shadow of any accessed failed
* SU. If yes, assign dest[0], dest[1] to point at suitable
* position of the buffer corresponding to failed SUs. If no,
* malloc a temporary space of a sector in size for
* destination of decoding.
*/
RF_ASSERT(nresults == 1 || nresults == 2);
if (nresults == 1) {
dest[0] = ((RF_PhysDiskAddr_t *)
node->results[0])->bufPtr +
rf_RaidAddressToByte(raidPtr, sector - fsuoff[0]);
/* Always malloc temp buffer to dest[1]. */
RF_Malloc(dest[1], bytesPerSector, (char *));
bzero(dest[1], bytesPerSector);
mallc_two = 1;
} else {
if (fsuoff[0] <= sector && sector < fsuend[0])
dest[0] = ((RF_PhysDiskAddr_t *)
node->results[0])->bufPtr +
rf_RaidAddressToByte(raidPtr,
sector - fsuoff[0]);
else {
RF_Malloc(dest[0], bytesPerSector, (char *));
bzero(dest[0], bytesPerSector);
mallc_one = 1;
}
if (fsuoff[1] <= sector && sector < fsuend[1])
dest[1] = ((RF_PhysDiskAddr_t *)
node->results[1])->bufPtr +
rf_RaidAddressToByte(raidPtr,
sector - fsuoff[1]);
else {
RF_Malloc(dest[1], bytesPerSector, (char *));
bzero(dest[1], bytesPerSector);
mallc_two = 1;
}
RF_ASSERT(mallc_one == 0 || mallc_two == 0);
}
pbuf = ppda->bufPtr + rf_RaidAddressToByte(raidPtr,
sector - psuoff);
ebuf = epda->bufPtr + rf_RaidAddressToByte(raidPtr,
sector - esuoff);
/*
* After finish finding all needed sectors, call doubleEOdecode
* function for decoding one sector to destination.
*/
rf_doubleEOdecode(raidPtr, buf, dest, fcol, pbuf, ebuf);
/*
* Free all allocated memory, and mark flag to indicate no
* memory is being allocated.
*/
if (mallc_one == 1)
RF_Free(dest[0], bytesPerSector);
if (mallc_two == 1)
RF_Free(dest[1], bytesPerSector);
mallc_one = mallc_two = 0;
}
RF_Free(buf, numDataCol * sizeof(char *));
if (ndataParam != 0) {
RF_Free(suoff, ndataParam * sizeof(long));
RF_Free(suend, ndataParam * sizeof(long));
RF_Free(prmToCol, ndataParam * sizeof(long));
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
if (tracerec) {
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
rf_GenericWakeupFunc(node, 0);
#if 1
return (0); /* XXX Is this even close !!?!?!!? GO */
#endif
}
/*
* Currently, only access of one of the two failed SU is allowed in this
* function. Also, asmap->numStripeUnitsAccessed is limited to be one,
* the RAIDframe will break large access into many accesses of single
* stripe unit.
*/
int
rf_EOWriteDoubleRecoveryFunc(RF_DagNode_t *node)
{
int np = node->numParams;
RF_AccessStripeMap_t *asmap =
(RF_AccessStripeMap_t *) node->params[np - 1].p;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 2].p;
RF_RaidLayout_t *layoutPtr = (RF_RaidLayout_t *) &(raidPtr->Layout);
RF_SectorNum_t sector;
RF_RowCol_t col, scol;
int prm, i, j;
RF_SectorCount_t secPerSU = layoutPtr->sectorsPerStripeUnit;
unsigned sosAddr;
unsigned bytesPerSector = rf_RaidAddressToByte(raidPtr, 1);
RF_int64 numbytes;
RF_SectorNum_t startSector, endSector;
RF_PhysDiskAddr_t *ppda, *epda, *pda, *fpda, npda;
RF_RowCol_t fcol[2], numDataCol = layoutPtr->numDataCol;
char **buf; /*
* buf[0], buf[1], buf[2], ... etc, point to
* buffer storing data read from col0, col1,
* col2.
*/
char *ebuf, *pbuf, *dest[2], *olddata[2];
RF_Etimer_t timer;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_ASSERT(asmap->numDataFailed == 1); /*
* Currently only support this
* case, the other failed SU
* is not being accessed.
*/
RF_ETIMER_START(timer);
RF_Malloc(buf, numDataCol * sizeof(char *), (char **));
ppda = node->results[0]; /*
* Instead of being buffers,
* node->results[0] and [1]
* are Ppda and Epda.
*/
epda = node->results[1];
fpda = asmap->failedPDAs[0];
/* First, recovery the failed old SU using EvenOdd double decoding. */
/* Determine the startSector and endSector for decoding. */
startSector = rf_StripeUnitOffset(layoutPtr, fpda->startSector);
endSector = startSector + fpda->numSector;
/*
* Assign buf[col] pointers to point to each non-failed column and
* initialize the pbuf and ebuf to point at the beginning of each
* source buffers and destination buffers. */
for (prm = 0; prm < numDataCol - 2; prm++) {
pda = (RF_PhysDiskAddr_t *) node->params[prm].p;
col = rf_EUCol(layoutPtr, pda->raidAddress);
buf[col] = pda->bufPtr;
}
/*
* pbuf and ebuf: They will change values as double recovery decoding
* goes on.
*/
pbuf = ppda->bufPtr;
ebuf = epda->bufPtr;
/*
* Find out the logical column numbers in the encoding matrix of the
* two failed columns.
*/
fcol[0] = rf_EUCol(layoutPtr, fpda->raidAddress);
/* Find out the other failed column not accessed this time. */
sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr,
asmap->raidAddress);
for (i = 0; i < numDataCol; i++) {
npda.raidAddress = sosAddr + (i * secPerSU);
(raidPtr->Layout.map->MapSector) (raidPtr, npda.raidAddress,
&(npda.row), &(npda.col), &(npda.startSector), 0);
/* Skip over dead disks. */
if (RF_DEAD_DISK(raidPtr->Disks[npda.row][npda.col].status))
if (i != fcol[0])
break;
}
RF_ASSERT(i < numDataCol);
fcol[1] = i;
/* Assign temporary space to put recovered failed SU. */
numbytes = fpda->numSector * bytesPerSector;
RF_Malloc(olddata[0], numbytes, (char *));
RF_Malloc(olddata[1], numbytes, (char *));
dest[0] = olddata[0];
dest[1] = olddata[1];
bzero(olddata[0], numbytes);
bzero(olddata[1], numbytes);
/*
* Begin the recovery decoding, initially buf[j], ebuf, pbuf, dest[j]
* have already pointed at the beginning of each source buffers and
* destination buffers.
*/
for (sector = startSector, i = 0; sector < endSector; sector++, i++) {
rf_doubleEOdecode(raidPtr, buf, dest, fcol, pbuf, ebuf);
for (j = 0; j < numDataCol; j++)
if ((j != fcol[0]) && (j != fcol[1]))
buf[j] += bytesPerSector;
dest[0] += bytesPerSector;
dest[1] += bytesPerSector;
ebuf += bytesPerSector;
pbuf += bytesPerSector;
}
/*
* After recovery, the buffer pointed by olddata[0] is the old failed
* data. With new writing data and this old data, use small write to
* calculate the new redundant informations.
*/
/*
* node->params[ 0, ... PDAPerDisk * (numDataCol - 2)-1 ] are Pdas of
* Rrd; params[ PDAPerDisk*(numDataCol - 2), ... PDAPerDisk*numDataCol
* -1 ] are Pdas of Rp, ( Rp2 ), Re, ( Re2 ) ; params[
* PDAPerDisk*numDataCol, ... PDAPerDisk*numDataCol
* +asmap->numStripeUnitsAccessed -asmap->numDataFailed-1] are Pdas of
* wudNodes; For current implementation, we assume the simplest case:
* asmap->numStripeUnitsAccessed == 1 and asmap->numDataFailed == 1
* ie. PDAPerDisk = 1 then node->params[numDataCol] must be the new
* data to be written to the failed disk. We first bxor the new data
* into the old recovered data, then do the same things as small
* write.
*/
rf_bxor(((RF_PhysDiskAddr_t *) node->params[numDataCol].p)->bufPtr,
olddata[0], numbytes, node->dagHdr->bp);
/* Do new 'E' calculation. */
/*
* Find out the corresponding column in encoding matrix for write
* column to be encoded into redundant disk 'E'.
*/
scol = rf_EUCol(layoutPtr, fpda->raidAddress);
/*
* olddata[0] now is source buffer pointer; epda->bufPtr is the dest
* buffer pointer.
*/
rf_e_encToBuf(raidPtr, scol, olddata[0], RF_EO_MATRIX_DIM - 2,
epda->bufPtr, fpda->numSector);
/* Do new 'P' calculation. */
rf_bxor(olddata[0], ppda->bufPtr, numbytes, node->dagHdr->bp);
/* Free the allocated buffer. */
RF_Free(olddata[0], numbytes);
RF_Free(olddata[1], numbytes);
RF_Free(buf, numDataCol * sizeof(char *));
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
if (tracerec) {
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
rf_GenericWakeupFunc(node, 0);
return (0);
}
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_evenodd_dagfuncs.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe