dev/raidframe/rf_evenodd_dagfuncs.c

/*	$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);
}