/* $OpenBSD: rf_pq.c,v 1.6 2002/12/16 07:01:04 tdeval Exp $ */
/* $NetBSD: rf_pq.c,v 1.7 2000/01/07 03:41:02 oster Exp $ */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Author: Daniel Stodolsky
*
* 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 level 6 (P + Q) disk array architecture.
*/
#include "rf_archs.h"
#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_pqdeg.h"
#include "rf_general.h"
#include "rf_map.h"
#include "rf_pq.h"
RF_RedFuncs_t rf_pFuncs = {
rf_RegularONPFunc, "Regular Old-New P",
rf_SimpleONPFunc, "Simple Old-New P"
};
RF_RedFuncs_t rf_pRecoveryFuncs = {
rf_RecoveryPFunc, "Recovery P Func",
rf_RecoveryPFunc, "Recovery P Func"
};
int
rf_RegularONPFunc(RF_DagNode_t *node)
{
return (rf_RegularXorFunc(node));
}
/*
* Same as simpleONQ func, but the coefficient is always 1.
*/
int
rf_SimpleONPFunc(RF_DagNode_t *node)
{
return (rf_SimpleXorFunc(node));
}
int
rf_RecoveryPFunc(RF_DagNode_t *node)
{
return (rf_RecoveryXorFunc(node));
}
int
rf_RegularPFunc(RF_DagNode_t *node)
{
return (rf_RegularXorFunc(node));
}
#if (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0)
void rf_QDelta(char *dest, char *obuf, char *nbuf, unsigned length,
unsigned char coeff);
void rf_InvertQ(unsigned long *qbuf, unsigned long *abuf, unsigned length,
unsigned coeff);
RF_RedFuncs_t rf_qFuncs = {
rf_RegularONQFunc, "Regular Old-New Q",
rf_SimpleONQFunc, "Simple Old-New Q"
};
RF_RedFuncs_t rf_qRecoveryFuncs = {
rf_RecoveryQFunc, "Recovery Q Func",
rf_RecoveryQFunc, "Recovery Q Func"
};
RF_RedFuncs_t rf_pqRecoveryFuncs = {
rf_RecoveryPQFunc, "Recovery PQ Func",
rf_RecoveryPQFunc, "Recovery PQ Func"
};
void
rf_PQDagSelect(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;
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 "q".
*/
if (ntfail == 2) { /* Also lost redundancy. */
if (asmap->failedPDAs[1]->type ==
RF_PDA_TYPE_PARITY)
*createFunc = (RF_VoidFuncPtr)
rf_PQ_110_CreateReadDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_101_CreateReadDAG;
} else {
/*
* P and Q are ok. But is there a failure in
* some unaccessed data unit ?
*/
if (rf_NumFailedDataUnitsInStripe(raidPtr,
asmap) == 2)
*createFunc = (RF_VoidFuncPtr)
rf_PQ_200_CreateReadDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_100_CreateReadDAG;
}
break;
case 2:
/* Lost two data units. */
/* *infoFunc = rf_PQOneTwo; */
*createFunc = (RF_VoidFuncPtr) rf_PQ_200_CreateReadDAG;
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_PQCreateSmallWriteDAG;
} else {
*createFunc = (RF_VoidFuncPtr) rf_PQCreateLargeWriteDAG;
}
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)) ||
rf_NumFailedDataUnitsInStripe(raidPtr,
asmap))
*createFunc = (RF_VoidFuncPtr)
rf_PQ_001_CreateSmallWriteDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_001_CreateLargeWriteDAG;
} else {/* Parity died, small write only updating Q. */
if (((asmap->numStripeUnitsAccessed <=
(layoutPtr->numDataCol / 2)) ||
(asmap->numStripeUnitsAccessed == 1)) ||
rf_NumFailedDataUnitsInStripe(raidPtr,
asmap))
*createFunc = (RF_VoidFuncPtr)
rf_PQ_010_CreateSmallWriteDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_010_CreateLargeWriteDAG;
}
} else { /*
* Data missing. Do a P reconstruct write if
* only a single data unit is lost in the
* stripe, otherwise a PQ reconstruct write.
*/
if (rf_NumFailedDataUnitsInStripe(raidPtr, asmap) == 2)
*createFunc = (RF_VoidFuncPtr)
rf_PQ_200_CreateWriteDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_100_CreateWriteDAG;
}
break;
case 2: /* Two disk faults. */
switch (npfail) {
case 2: /* Both p and q dead. */
*createFunc = (RF_VoidFuncPtr) rf_PQ_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)
*createFunc = (RF_VoidFuncPtr)
rf_PQ_101_CreateWriteDAG;
else
*createFunc = (RF_VoidFuncPtr)
rf_PQ_110_CreateWriteDAG;
break;
case 0: /* Double data loss. */
*createFunc = (RF_VoidFuncPtr) rf_PQ_200_CreateWriteDAG;
break;
}
break;
default: /* More than 2 disk faults. */
*createFunc = NULL;
RF_PANIC();
}
return;
}
/*
* Used as a stop gap info function.
*/
#if 0
void
rf_PQOne(RF_Raid_t *raidPtr, int *nSucc, int *nAnte,
RF_AccessStripeMap_t *asmap)
{
*nSucc = *nAnte = 1;
}
void
rf_PQOneTwo(RF_Raid_t *raidPtr, int *nSucc, int *nAnte,
RF_AccessStripeMap_t *asmap)
{
*nSucc = 1;
*nAnte = 2;
}
#endif
RF_CREATE_DAG_FUNC_DECL(rf_PQCreateLargeWriteDAG)
{
rf_CommonCreateLargeWriteDAG(raidPtr, asmap, dag_h, bp, flags,
allocList, 2, rf_RegularPQFunc, RF_FALSE);
}
int
rf_RegularONQFunc(RF_DagNode_t *node)
{
int np = node->numParams;
int d;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
int i;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
char *qbuf, *qpbuf;
char *obuf, *nbuf;
RF_PhysDiskAddr_t *old, *new;
unsigned long coeff;
unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
RF_ETIMER_START(timer);
d = (np - 3) / 4;
RF_ASSERT(4 * d + 3 == np);
qbuf = (char *) node->params[2 * d + 1].p; /* Q buffer. */
for (i = 0; i < d; i++) {
old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
obuf = (char *) node->params[2 * i + 1].p;
new = (RF_PhysDiskAddr_t *) node->params[2 * (d + 1 + i)].p;
nbuf = (char *) node->params[2 * (d + 1 + i) + 1].p;
RF_ASSERT(new->numSector == old->numSector);
RF_ASSERT(new->raidAddress == old->raidAddress);
/*
* The stripe unit within the stripe tells us the coefficient
* to use for the multiply.
*/
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
new->raidAddress);
/*
* Compute the data unit offset within the column, then add
* one.
*/
coeff = (coeff % raidPtr->Layout.numDataCol);
qpbuf = qbuf + rf_RaidAddressToByte(raidPtr,
old->startSector % secPerSU);
rf_QDelta(qpbuf, obuf, nbuf, rf_RaidAddressToByte(raidPtr,
old->numSector), coeff);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
rf_GenericWakeupFunc(node, 0); /*
* Call wake func explicitly since no
* I/O in this node.
*/
return (0);
}
/*
* See the SimpleXORFunc for the difference between a simple and regular func.
* These Q functions should be used for
* new q = Q(data, old data, old q)
* style updates and not for
* q = (new data, new data, ...)
* computations.
*
* The simple q takes 2(2d+1)+1 params, where d is the number
* of stripes written. The order of params is
* old data pda_0, old data buffer_0, old data pda_1, old data buffer_1, ...
* old data pda_d, old data buffer_d
* [2d] old q pda_0, old q buffer
* [2d_2] new data pda_0, new data buffer_0, ...
* new data pda_d, new data buffer_d
* raidPtr
*/
int
rf_SimpleONQFunc(RF_DagNode_t *node)
{
int np = node->numParams;
int d;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
int i;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
char *qbuf;
char *obuf, *nbuf;
RF_PhysDiskAddr_t *old, *new;
unsigned long coeff;
RF_ETIMER_START(timer);
d = (np - 3) / 4;
RF_ASSERT(4 * d + 3 == np);
qbuf = (char *) node->params[2 * d + 1].p; /* Q buffer. */
for (i = 0; i < d; i++) {
old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
obuf = (char *) node->params[2 * i + 1].p;
new = (RF_PhysDiskAddr_t *) node->params[2 * (d + 1 + i)].p;
nbuf = (char *) node->params[2 * (d + 1 + i) + 1].p;
RF_ASSERT(new->numSector == old->numSector);
RF_ASSERT(new->raidAddress == old->raidAddress);
/*
* The stripe unit within the stripe tells us the coefficient
* to use for the multiply.
*/
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
new->raidAddress);
/*
* Compute the data unit offset within the column, then add
* one.
*/
coeff = (coeff % raidPtr->Layout.numDataCol);
rf_QDelta(qbuf, obuf, nbuf, rf_RaidAddressToByte(raidPtr,
old->numSector), coeff);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
rf_GenericWakeupFunc(node, 0); /*
* Call wake func explicitly since no
* I/O in this node.
*/
return (0);
}
RF_CREATE_DAG_FUNC_DECL(rf_PQCreateSmallWriteDAG)
{
rf_CommonCreateSmallWriteDAG(raidPtr, asmap, dag_h, bp, flags,
allocList, &rf_pFuncs, &rf_qFuncs);
}
void rf_RegularQSubr(RF_DagNode_t *, char *);
void
rf_RegularQSubr(RF_DagNode_t *node, char *qbuf)
{
int np = node->numParams;
int d;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
int i;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
char *obuf, *qpbuf;
RF_PhysDiskAddr_t *old;
unsigned long coeff;
RF_ETIMER_START(timer);
d = (np - 1) / 2;
RF_ASSERT(2 * d + 1 == np);
for (i = 0; i < d; i++) {
old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
obuf = (char *) node->params[2 * i + 1].p;
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
old->raidAddress);
/*
* Compute the data unit offset within the column, then add
* one.
*/
coeff = (coeff % raidPtr->Layout.numDataCol);
/*
* The input buffers may not all be aligned with the start of
* the stripe. So shift by their sector offset within the
* stripe unit.
*/
qpbuf = qbuf + rf_RaidAddressToByte(raidPtr,
old->startSector % secPerSU);
rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
/*
* Used in degraded writes.
*/
void rf_DegrQSubr(RF_DagNode_t *);
void
rf_DegrQSubr(RF_DagNode_t *node)
{
int np = node->numParams;
int d;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
char *qbuf = node->results[1];
char *obuf, *qpbuf;
RF_PhysDiskAddr_t *old;
unsigned long coeff;
unsigned fail_start;
int i, j;
old = (RF_PhysDiskAddr_t *) node->params[np - 2].p;
fail_start = old->startSector % secPerSU;
RF_ETIMER_START(timer);
d = (np - 2) / 2;
RF_ASSERT(2 * d + 2 == np);
for (i = 0; i < d; i++) {
old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
obuf = (char *) node->params[2 * i + 1].p;
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
old->raidAddress);
/*
* Compute the data unit offset within the column, then add
* one.
*/
coeff = (coeff % raidPtr->Layout.numDataCol);
/*
* The input buffers may not all be aligned with the start of
* the stripe. So shift by their sector offset within the
* stripe unit.
*/
j = old->startSector % secPerSU;
RF_ASSERT(j >= fail_start);
qpbuf = qbuf + rf_RaidAddressToByte(raidPtr, j - fail_start);
rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
}
/*
* Called by large write code to compute the new parity and the new q.
*
* Structure of the params:
*
* pda_0, buffer_0, pda_1 , buffer_1, ..., pda_d, buffer_d (d = numDataCol)
* raidPtr
*
* For a total of 2d+1 arguments.
* The result buffers results[0], results[1] are the buffers for the p and q,
* respectively.
*
* We compute Q first, then compute P. The P calculation may try to reuse
* one of the input buffers for its output, so if we computed P first, we would
* corrupt the input for the q calculation.
*/
int
rf_RegularPQFunc(RF_DagNode_t *node)
{
rf_RegularQSubr(node, node->results[1]);
return (rf_RegularXorFunc(node)); /* Does the wakeup. */
}
int
rf_RegularQFunc(RF_DagNode_t *node)
{
/* Almost ... adjust Qsubr args. */
rf_RegularQSubr(node, node->results[0]);
rf_GenericWakeupFunc(node, 0); /*
* Call wake func explicitly since no
* I/O in this node.
*/
return (0);
}
/*
* Called by singly degraded write code to compute the new parity and
* the new q.
*
* Structure of the params:
*
* pda_0, buffer_0, pda_1 , buffer_1, ..., pda_d, buffer_d
* failedPDA raidPtr
*
* for a total of 2d+2 arguments.
* The result buffers results[0], results[1] are the buffers for the parity
* and q, respectively.
*
* We compute Q first, then compute parity. The parity calculation may try
* to reuse one of the input buffers for its output, so if we computed parity
* first, we would corrupt the input for the q calculation.
*
* We treat this identically to the regularPQ case, ignoring the failedPDA
* extra argument.
*/
void
rf_Degraded_100_PQFunc(RF_DagNode_t *node)
{
int np = node->numParams;
RF_ASSERT(np >= 2);
rf_DegrQSubr(node);
rf_RecoveryXorFunc(node);
}
/*
* The two below are used when reading a stripe with a single lost data unit.
* The parameters are
*
* pda_0, buffer_0, ..., pda_n, buffer_n, P pda, P buffer, failedPDA, raidPtr
*
* and results[0] contains the data buffer, which is originally zero-filled.
*/
/*
* This Q func is used by the degraded-mode dag functions to recover lost data.
* The second-to-last parameter is the PDA for the failed portion of the
* access. The code here looks at this PDA and assumes that the xor target
* buffer is equal in size to the number of sectors in the failed PDA. It then
* uses the other PDAs in the parameter list to determine where within the
* target buffer the corresponding data should be xored.
*
* Recall the basic equation is
*
* Q = (data_1 + 2 * data_2 ... + k * data_k) mod 256
*
* so to recover data_j we need
*
* J data_j = (Q - data_1 - 2 data_2 ... - k * data_k) mod 256
*
* So the coefficient for each buffer is (255 - data_col), and j should be
* initialized by copying Q into it. Then we need to do a table lookup to
* convert to solve
* data_j /= J
*
*/
int
rf_RecoveryQFunc(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;
int i;
RF_PhysDiskAddr_t *pda;
RF_RaidAddr_t suoffset;
RF_RaidAddr_t failedSUOffset =
rf_StripeUnitOffset(layoutPtr, failedPDA->startSector);
char *srcbuf, *destbuf;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
unsigned long coeff;
RF_ETIMER_START(timer);
/* Start by copying Q into the buffer. */
bcopy(node->params[node->numParams - 3].p, node->results[0],
rf_RaidAddressToByte(raidPtr, failedPDA->numSector));
for (i = 0; i < node->numParams - 4; i += 2) {
RF_ASSERT(node->params[i + 1].p != node->results[0]);
pda = (RF_PhysDiskAddr_t *) node->params[i].p;
srcbuf = (char *) node->params[i + 1].p;
suoffset = rf_StripeUnitOffset(layoutPtr, pda->startSector);
destbuf = ((char *) node->results[0]) +
rf_RaidAddressToByte(raidPtr, suoffset - failedSUOffset);
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
pda->raidAddress);
/* Compute the data unit offset within the column. */
coeff = (coeff % raidPtr->Layout.numDataCol);
rf_IncQ((unsigned long *) destbuf, (unsigned long *) srcbuf,
rf_RaidAddressToByte(raidPtr, pda->numSector), coeff);
}
/* Do the nasty inversion now. */
coeff = (rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
failedPDA->startSector) % raidPtr->Layout.numDataCol);
rf_InvertQ(node->results[0], node->results[0],
rf_RaidAddressToByte(raidPtr, pda->numSector), coeff);
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
rf_GenericWakeupFunc(node, 0);
return (0);
}
int
rf_RecoveryPQFunc(RF_DagNode_t *node)
{
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[node->numParams - 1].p;
printf("raid%d: Recovery from PQ not implemented.\n", raidPtr->raidid);
return (1);
}
/*
* Degraded write Q subroutine.
* Used when P is dead.
* Large-write style Q computation.
* Parameters:
*
* (pda, buf), (pda, buf), ..., (failedPDA, bufPtr), failedPDA, raidPtr.
*
* We ignore failedPDA.
*
* This is a "simple style" recovery func.
*/
void
rf_PQ_DegradedWriteQFunc(RF_DagNode_t *node)
{
int np = node->numParams;
int d;
RF_Raid_t *raidPtr = (RF_Raid_t *) node->params[np - 1].p;
unsigned secPerSU = raidPtr->Layout.sectorsPerStripeUnit;
RF_AccTraceEntry_t *tracerec = node->dagHdr->tracerec;
RF_Etimer_t timer;
char *qbuf = node->results[0];
char *obuf, *qpbuf;
RF_PhysDiskAddr_t *old;
unsigned long coeff;
int fail_start, i, j;
old = (RF_PhysDiskAddr_t *) node->params[np - 2].p;
fail_start = old->startSector % secPerSU;
RF_ETIMER_START(timer);
d = (np - 2) / 2;
RF_ASSERT(2 * d + 2 == np);
for (i = 0; i < d; i++) {
old = (RF_PhysDiskAddr_t *) node->params[2 * i].p;
obuf = (char *) node->params[2 * i + 1].p;
coeff = rf_RaidAddressToStripeUnitID(&(raidPtr->Layout),
old->raidAddress);
/*
* Compute the data unit offset within the column, then add
* one.
*/
coeff = (coeff % raidPtr->Layout.numDataCol);
j = old->startSector % secPerSU;
RF_ASSERT(j >= fail_start);
qpbuf = qbuf + rf_RaidAddressToByte(raidPtr, j - fail_start);
rf_IncQ((unsigned long *) qpbuf, (unsigned long *) obuf,
rf_RaidAddressToByte(raidPtr, old->numSector), coeff);
}
RF_ETIMER_STOP(timer);
RF_ETIMER_EVAL(timer);
tracerec->q_us += RF_ETIMER_VAL_US(timer);
rf_GenericWakeupFunc(node, 0);
}
/* Q computations. */
/*
* Coeff - colummn;
*
* Compute dest ^= qfor[28-coeff][rn[coeff+1] a]
*
* On 5-bit basis;
* Length in bytes;
*/
void
rf_IncQ(unsigned long *dest, unsigned long *buf, unsigned length,
unsigned coeff)
{
unsigned long a, d, new;
unsigned long a1, a2;
unsigned int *q = &(rf_qfor[28 - coeff][0]);
unsigned r = rf_rn[coeff + 1];
#define EXTRACT(a,i) ((a >> (5L*i)) & 0x1f)
#define INSERT(a,i) (a << (5L*i))
length /= 8;
/* 13 5 bit quants in a 64 bit word. */
while (length) {
a = *buf++;
d = *dest;
a1 = EXTRACT(a, 0) ^ r;
a2 = EXTRACT(a, 1) ^ r;
new = INSERT(a2, 1) | a1;
a1 = EXTRACT(a, 2) ^ r;
a2 = EXTRACT(a, 3) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 2) | INSERT(a2, 3);
a1 = EXTRACT(a, 4) ^ r;
a2 = EXTRACT(a, 5) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 4) | INSERT(a2, 5);
a1 = EXTRACT(a, 5) ^ r;
a2 = EXTRACT(a, 6) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 5) | INSERT(a2, 6);
#if RF_LONGSHIFT > 2
a1 = EXTRACT(a, 7) ^ r;
a2 = EXTRACT(a, 8) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 7) | INSERT(a2, 8);
a1 = EXTRACT(a, 9) ^ r;
a2 = EXTRACT(a, 10) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 9) | INSERT(a2, 10);
a1 = EXTRACT(a, 11) ^ r;
a2 = EXTRACT(a, 12) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 11) | INSERT(a2, 12);
#endif /* RF_LONGSHIFT > 2 */
d ^= new;
*dest++ = d;
length--;
}
}
/*
* Compute.
*
* dest ^= rf_qfor[28-coeff][rf_rn[coeff+1] (old^new)]
*
* On a five bit basis.
* Optimization: compute old ^ new on 64 bit basis.
*
* Length in bytes.
*/
void
rf_QDelta(char *dest, char *obuf, char *nbuf, unsigned length,
unsigned char coeff)
{
unsigned long a, d, new;
unsigned long a1, a2;
unsigned int *q = &(rf_qfor[28 - coeff][0]);
unsigned int r = rf_rn[coeff + 1];
r = a1 = a2 = new = d = a = 0; /* XXX For now... */
q = NULL; /* XXX For now */
#ifdef _KERNEL
/*
* PQ in kernel currently not supported because the encoding/decoding
* table is not present.
*/
bzero(dest, length);
#else /* _KERNEL */
/* This code probably doesn't work and should be rewritten. -wvcii */
/* 13 5 bit quants in a 64 bit word. */
length /= 8;
while (length) {
a = *obuf++; /*
* XXX Need to reorg to avoid cache conflicts.
*/
a ^= *nbuf++;
d = *dest;
a1 = EXTRACT(a, 0) ^ r;
a2 = EXTRACT(a, 1) ^ r;
a1 = q[a1];
a2 = q[a2];
new = INSERT(a2, 1) | a1;
a1 = EXTRACT(a, 2) ^ r;
a2 = EXTRACT(a, 3) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 2) | INSERT(a2, 3);
a1 = EXTRACT(a, 4) ^ r;
a2 = EXTRACT(a, 5) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 4) | INSERT(a2, 5);
a1 = EXTRACT(a, 5) ^ r;
a2 = EXTRACT(a, 6) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 5) | INSERT(a2, 6);
#if RF_LONGSHIFT > 2
a1 = EXTRACT(a, 7) ^ r;
a2 = EXTRACT(a, 8) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 7) | INSERT(a2, 8);
a1 = EXTRACT(a, 9) ^ r;
a2 = EXTRACT(a, 10) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 9) | INSERT(a2, 10);
a1 = EXTRACT(a, 11) ^ r;
a2 = EXTRACT(a, 12) ^ r;
a1 = q[a1];
a2 = q[a2];
new = new | INSERT(a1, 11) | INSERT(a2, 12);
#endif /* RF_LONGSHIFT > 2 */
d ^= new;
*dest++ = d;
length--;
}
#endif /* _KERNEL */
}
/*
* Recover columns a and b from the given p and q into
* bufs abuf and bbuf. All bufs are word aligned.
* Length is in bytes.
*/
/*
* XXX
*
* Everything about this seems wrong.
*/
void
rf_PQ_recover(unsigned long *pbuf, unsigned long *qbuf, unsigned long *abuf,
unsigned long *bbuf, unsigned length, unsigned coeff_a, unsigned coeff_b)
{
unsigned long p, q, a, a0, a1;
int col = (29 * coeff_a) + coeff_b;
unsigned char *q0 = &(rf_qinv[col][0]);
length /= 8;
while (length) {
p = *pbuf++;
q = *qbuf++;
a0 = EXTRACT(p, 0);
a1 = EXTRACT(q, 0);
a = q0[a0 << 5 | a1];
#define MF(i) \
do { \
a0 = EXTRACT(p, i); \
a1 = EXTRACT(q, i); \
a = a | INSERT(q0[a0<<5 | a1], i); \
} while (0)
MF(1);
MF(2);
MF(3);
MF(4);
MF(5);
MF(6);
#if 0
MF(7);
MF(8);
MF(9);
MF(10);
MF(11);
MF(12);
#endif /* 0 */
*abuf++ = a;
*bbuf++ = a ^ p;
length--;
}
}
/*
* Lost parity and a data column. Recover that data column.
* Assume col coeff is lost. Let q the contents of Q after
* all surviving data columns have been q-xored out of it.
* Then we have the equation
*
* q[28-coeff][a_i ^ r_i+1] = q
*
* but q is cyclic with period 31.
* So q[3+coeff][q[28-coeff][a_i ^ r_{i+1}]] =
* q[31][a_i ^ r_{i+1}] = a_i ^ r_{i+1} .
*
* so a_i = r_{coeff+1} ^ q[3+coeff][q]
*
* The routine is passed q buffer and the buffer
* the data is to be recoverd into. They can be the same.
*/
void
rf_InvertQ(unsigned long *qbuf, unsigned long *abuf, unsigned length,
unsigned coeff)
{
unsigned long a, new;
unsigned long a1, a2;
unsigned int *q = &(rf_qfor[3 + coeff][0]);
unsigned r = rf_rn[coeff + 1];
/* 13 5 bit quants in a 64 bit word. */
length /= 8;
while (length) {
a = *qbuf++;
a1 = EXTRACT(a, 0);
a2 = EXTRACT(a, 1);
a1 = r ^ q[a1];
a2 = r ^ q[a2];
new = INSERT(a2, 1) | a1;
#define M(i,j) \
do { \
a1 = EXTRACT(a, i); \
a2 = EXTRACT(a, j); \
a1 = r ^ q[a1]; \
a2 = r ^ q[a2]; \
new = new | INSERT(a1, i) | INSERT(a2, j); \
} while (0)
M(2, 3);
M(4, 5);
M(5, 6);
#if RF_LONGSHIFT > 2
M(7, 8);
M(9, 10);
M(11, 12);
#endif /* RF_LONGSHIFT > 2 */
*abuf++ = new;
length--;
}
}
#endif /* (RF_INCLUDE_DECL_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_pq.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe