/* $OpenBSD: rf_aselect.c,v 1.3 2002/12/16 07:01:03 tdeval Exp $ */
/* $NetBSD: rf_aselect.c,v 1.3 1999/02/05 00:06:06 oster Exp $ */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Author: Mark Holland, William V. Courtright II
*
* 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.
*/
/****************************************************************************
*
* aselect.c -- algorithm selection code
*
*****************************************************************************/
#include "rf_archs.h"
#include "rf_types.h"
#include "rf_raid.h"
#include "rf_dag.h"
#include "rf_dagutils.h"
#include "rf_dagfuncs.h"
#include "rf_general.h"
#include "rf_desc.h"
#include "rf_map.h"
#if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
/* The function below is not used... so don't define it! */
#else
void rf_TransferDagMemory(RF_DagHeader_t *, RF_DagHeader_t *);
#endif
int rf_InitHdrNode(RF_DagHeader_t **, RF_Raid_t *, int);
void rf_UpdateNodeHdrPtr(RF_DagHeader_t *, RF_DagNode_t *);
int rf_SelectAlgorithm(RF_RaidAccessDesc_t *, RF_RaidAccessFlags_t);
/*****************************************************************************
*
* Create and Initialize a dag header and termination node.
*
*****************************************************************************/
int
rf_InitHdrNode(RF_DagHeader_t **hdr, RF_Raid_t *raidPtr, int memChunkEnable)
{
/* Create and initialize dag hdr. */
*hdr = rf_AllocDAGHeader();
rf_MakeAllocList((*hdr)->allocList);
if ((*hdr)->allocList == NULL) {
rf_FreeDAGHeader(*hdr);
return (ENOMEM);
}
(*hdr)->status = rf_enable;
(*hdr)->numSuccedents = 0;
(*hdr)->raidPtr = raidPtr;
(*hdr)->next = NULL;
return (0);
}
/*****************************************************************************
*
* Transfer allocation list and mem chunks from one dag to another.
*
*****************************************************************************/
#if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
/* The function below is not used... so don't define it! */
#else
void
rf_TransferDagMemory(RF_DagHeader_t *daga, RF_DagHeader_t *dagb)
{
RF_AccessStripeMapHeader_t *end;
RF_AllocListElem_t *p;
int i, memChunksXfrd = 0, xtraChunksXfrd = 0;
/* Transfer allocList from dagb to daga. */
for (p = dagb->allocList; p; p = p->next) {
for (i = 0; i < p->numPointers; i++) {
rf_AddToAllocList(daga->allocList, p->pointers[i],
p->sizes[i]);
p->pointers[i] = NULL;
p->sizes[i] = 0;
}
p->numPointers = 0;
}
/* Transfer chunks from dagb to daga. */
while ((memChunksXfrd + xtraChunksXfrd <
dagb->chunkIndex + dagb->xtraChunkIndex) &&
(daga->chunkIndex < RF_MAXCHUNKS)) {
/* Stuff chunks into daga's memChunk array. */
if (memChunksXfrd < dagb->chunkIndex) {
daga->memChunk[daga->chunkIndex++] =
dagb->memChunk[memChunksXfrd];
dagb->memChunk[memChunksXfrd++] = NULL;
} else {
daga->memChunk[daga->xtraChunkIndex++] =
dagb->xtraMemChunk[xtraChunksXfrd];
dagb->xtraMemChunk[xtraChunksXfrd++] = NULL;
}
}
/* Use escape hatch to hold excess chunks. */
while (memChunksXfrd + xtraChunksXfrd <
dagb->chunkIndex + dagb->xtraChunkIndex) {
if (memChunksXfrd < dagb->chunkIndex) {
daga->xtraMemChunk[daga->xtraChunkIndex++] =
dagb->memChunk[memChunksXfrd];
dagb->memChunk[memChunksXfrd++] = NULL;
} else {
daga->xtraMemChunk[daga->xtraChunkIndex++] =
dagb->xtraMemChunk[xtraChunksXfrd];
dagb->xtraMemChunk[xtraChunksXfrd++] = NULL;
}
}
RF_ASSERT((memChunksXfrd == dagb->chunkIndex) &&
(xtraChunksXfrd == dagb->xtraChunkIndex));
RF_ASSERT(daga->chunkIndex <= RF_MAXCHUNKS);
RF_ASSERT(daga->xtraChunkIndex <= daga->xtraChunkCnt);
dagb->chunkIndex = 0;
dagb->xtraChunkIndex = 0;
/* Transfer asmList from dagb to daga. */
if (dagb->asmList) {
if (daga->asmList) {
end = daga->asmList;
while (end->next)
end = end->next;
end->next = dagb->asmList;
} else
daga->asmList = dagb->asmList;
dagb->asmList = NULL;
}
}
#endif /* __NetBSD__ || __OpenBSD__ */
/*****************************************************************************
*
* Ensure that all node->dagHdr fields in a dag are consistent.
*
* IMPORTANT: This routine recursively searches all succedents of the node.
* If a succedent is encountered whose dagHdr ptr does not require adjusting,
* that node's succedents WILL NOT BE EXAMINED.
*
*****************************************************************************/
void
rf_UpdateNodeHdrPtr(RF_DagHeader_t *hdr, RF_DagNode_t *node)
{
int i;
RF_ASSERT(hdr != NULL && node != NULL);
for (i = 0; i < node->numSuccedents; i++)
if (node->succedents[i]->dagHdr != hdr)
rf_UpdateNodeHdrPtr(hdr, node->succedents[i]);
node->dagHdr = hdr;
}
/*****************************************************************************
*
* Create a DAG to do a read or write operation.
*
* Create an array of dagLists, one list per parity stripe.
* Return the lists in the array desc->dagArray.
*
* Normally, each list contains one dag for the entire stripe. In some
* tricky cases, we break this into multiple dags, either one per stripe
* unit or one per block (sector). When this occurs, these dags are returned
* as a linked list (dagList) which is executed sequentially (to preserve
* atomic parity updates in the stripe).
*
* Dags that operate on independent parity goups (stripes) are returned in
* independent dagLists (distinct elements in desc->dagArray) and may be
* executed concurrently.
*
* Finally, if the SelectionFunc fails to create a dag for a block, we punt
* and return 1.
*
* The above process is performed in two phases:
* 1) create an array(s) of creation functions (eg stripeFuncs)
* 2) create dags and concatenate/merge to form the final dag.
*
* Because dag's are basic blocks (single entry, single exit, unconditional
* control flow), we can add the following optimizations (future work):
* first-pass optimizer to allow max concurrency (need all data dependencies)
* second-pass optimizer to eliminate common subexpressions (need true
* data dependencies)
* third-pass optimizer to eliminate dead code (need true data dependencies)
*****************************************************************************/
#define MAXNSTRIPES 50
int
rf_SelectAlgorithm(RF_RaidAccessDesc_t *desc, RF_RaidAccessFlags_t flags)
{
RF_AccessStripeMapHeader_t *asm_h = desc->asmap;
RF_IoType_t type = desc->type;
RF_Raid_t *raidPtr = desc->raidPtr;
void *bp = desc->bp;
RF_AccessStripeMap_t *asmap = asm_h->stripeMap;
RF_AccessStripeMap_t *asm_p;
RF_DagHeader_t *dag_h = NULL, *tempdag_h, *lastdag_h;
int i, j, k;
RF_VoidFuncPtr *stripeFuncs, normalStripeFuncs[MAXNSTRIPES];
RF_AccessStripeMap_t *asm_up, *asm_bp;
RF_AccessStripeMapHeader_t ***asmh_u, *endASMList;
RF_AccessStripeMapHeader_t ***asmh_b;
RF_VoidFuncPtr **stripeUnitFuncs, uFunc;
RF_VoidFuncPtr **blockFuncs, bFunc;
int numStripesBailed = 0, cantCreateDAGs = RF_FALSE;
int numStripeUnitsBailed = 0;
int stripeNum, numUnitDags = 0, stripeUnitNum, numBlockDags = 0;
RF_StripeNum_t numStripeUnits;
RF_SectorNum_t numBlocks;
RF_RaidAddr_t address;
int length;
RF_PhysDiskAddr_t *physPtr;
caddr_t buffer;
lastdag_h = NULL;
asmh_u = asmh_b = NULL;
stripeUnitFuncs = NULL;
blockFuncs = NULL;
/*
* Get an array of dag-function creation pointers.
* Try to avoid calling malloc.
*/
if (asm_h->numStripes <= MAXNSTRIPES)
stripeFuncs = normalStripeFuncs;
else
RF_Calloc(stripeFuncs, asm_h->numStripes,
sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr *));
/*
* Walk through the asm list once collecting information.
* Attempt to find a single creation function for each stripe.
*/
desc->numStripes = 0;
for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
desc->numStripes++;
(raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_p,
&stripeFuncs[i]);
/* Check to see if we found a creation func for this stripe. */
if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) {
/*
* Could not find creation function for entire stripe.
* So, let's see if we can find one for each stripe
* unit in the stripe.
*/
if (numStripesBailed == 0) {
/*
* One stripe map header for each stripe we
* bail on.
*/
RF_Malloc(asmh_u,
sizeof(RF_AccessStripeMapHeader_t **) *
asm_h->numStripes,
(RF_AccessStripeMapHeader_t ***));
/*
* Create an array of ptrs to arrays of
* stripeFuncs.
*/
RF_Calloc(stripeUnitFuncs, asm_h->numStripes,
sizeof(RF_VoidFuncPtr),
(RF_VoidFuncPtr **));
}
/*
* Create an array of creation funcs (called
* stripeFuncs) for this stripe.
*/
numStripeUnits = asm_p->numStripeUnitsAccessed;
RF_Calloc(stripeUnitFuncs[numStripesBailed],
numStripeUnits, sizeof(RF_VoidFuncPtr),
(RF_VoidFuncPtr *));
RF_Malloc(asmh_u[numStripesBailed], numStripeUnits *
sizeof(RF_AccessStripeMapHeader_t *),
(RF_AccessStripeMapHeader_t **));
/* Lookup array of stripeUnitFuncs for this stripe. */
for (j = 0, physPtr = asm_p->physInfo; physPtr;
physPtr = physPtr->next, j++) {
/*
* Remap for series of single stripe-unit
* accesses.
*/
address = physPtr->raidAddress;
length = physPtr->numSector;
buffer = physPtr->bufPtr;
asmh_u[numStripesBailed][j] =
rf_MapAccess(raidPtr, address, length,
buffer, RF_DONT_REMAP);
asm_up = asmh_u[numStripesBailed][j]->stripeMap;
/*
* Get the creation func for this
* stripe unit.
*/
(raidPtr->Layout.map->SelectionFunc) (raidPtr,
type, asm_up,
&(stripeUnitFuncs[numStripesBailed][j]));
/*
* Check to see if we found a creation func
* for this stripe unit.
*/
if (stripeUnitFuncs[numStripesBailed][j] ==
(RF_VoidFuncPtr) NULL) {
/*
* Could not find creation function
* for stripe unit. So, let's see if
* we can find one for each block in
* the stripe unit.
*/
if (numStripeUnitsBailed == 0) {
/*
* one stripe map header for
* each stripe unit we bail on.
*/
RF_Malloc(asmh_b,
sizeof(RF_AccessStripeMapHeader_t **) *
asm_h->numStripes *
raidPtr->Layout.numDataCol,
(RF_AccessStripeMapHeader_t ***));
/*
* Create an array of ptrs to
* arrays of blockFuncs.
*/
RF_Calloc(blockFuncs,
asm_h->numStripes *
raidPtr->Layout.numDataCol,
sizeof(RF_VoidFuncPtr),
(RF_VoidFuncPtr **));
}
/*
* Create an array of creation funcs
* (called blockFuncs) for this stripe
* unit.
*/
numBlocks = physPtr->numSector;
numBlockDags += numBlocks;
RF_Calloc(
blockFuncs[numStripeUnitsBailed],
numBlocks, sizeof(RF_VoidFuncPtr),
(RF_VoidFuncPtr *));
RF_Malloc(asmh_b[numStripeUnitsBailed],
numBlocks *
sizeof(RF_AccessStripeMapHeader_t *),
(RF_AccessStripeMapHeader_t **));
/*
* Lookup array of blockFuncs for this
* stripe unit.
*/
for (k = 0; k < numBlocks; k++) {
/*
* Remap for series of single
* stripe-unit accesses.
*/
address = physPtr->raidAddress
+ k;
length = 1;
buffer = physPtr->bufPtr +
(k * (1 <<
raidPtr->logBytesPerSector));
asmh_b[numStripeUnitsBailed][k]
= rf_MapAccess(raidPtr,
address, length, buffer,
RF_DONT_REMAP);
asm_bp =
asmh_b[numStripeUnitsBailed][k]->stripeMap;
/*
* Get the creation func for
* this stripe unit.
*/
(raidPtr->Layout.map->
SelectionFunc) (raidPtr,
type, asm_bp,
&(blockFuncs[numStripeUnitsBailed][k]));
/*
* Check to see if we found a
* creation func for this
* stripe unit.
*/
if (blockFuncs
[numStripeUnitsBailed][k]
== NULL)
cantCreateDAGs =
RF_TRUE;
}
numStripeUnitsBailed++;
} else {
numUnitDags++;
}
}
RF_ASSERT(j == numStripeUnits);
numStripesBailed++;
}
}
if (cantCreateDAGs) {
/* Free memory and punt. */
if (asm_h->numStripes > MAXNSTRIPES)
RF_Free(stripeFuncs, asm_h->numStripes *
sizeof(RF_VoidFuncPtr));
if (numStripesBailed > 0) {
stripeNum = 0;
for (i = 0, asm_p = asmap; asm_p;
asm_p = asm_p->next, i++)
if (stripeFuncs[i] == NULL) {
numStripeUnits =
asm_p->numStripeUnitsAccessed;
for (j = 0; j < numStripeUnits; j++)
rf_FreeAccessStripeMap(
asmh_u[stripeNum][j]);
RF_Free(asmh_u[stripeNum],
numStripeUnits *
sizeof(RF_AccessStripeMapHeader_t *));
RF_Free(stripeUnitFuncs[stripeNum],
numStripeUnits *
sizeof(RF_VoidFuncPtr));
stripeNum++;
}
RF_ASSERT(stripeNum == numStripesBailed);
RF_Free(stripeUnitFuncs, asm_h->numStripes *
sizeof(RF_VoidFuncPtr));
RF_Free(asmh_u, asm_h->numStripes *
sizeof(RF_AccessStripeMapHeader_t **));
}
return (1);
} else {
/* Begin dag creation. */
stripeNum = 0;
stripeUnitNum = 0;
/* Create an array of dagLists and fill them in. */
RF_CallocAndAdd(desc->dagArray, desc->numStripes,
sizeof(RF_DagList_t), (RF_DagList_t *), desc->cleanupList);
for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
/* Grab dag header for this stripe. */
dag_h = NULL;
desc->dagArray[i].desc = desc;
if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) {
/* Use bailout functions for this stripe. */
for (j = 0, physPtr = asm_p->physInfo; physPtr;
physPtr = physPtr->next, j++) {
uFunc = stripeUnitFuncs[stripeNum][j];
if (uFunc == (RF_VoidFuncPtr) NULL) {
/*
* Use bailout functions for
* this stripe unit.
*/
for (k = 0; k <
physPtr->numSector; k++) {
/*
* Create a dag for
* this block.
*/
rf_InitHdrNode(
&tempdag_h,
raidPtr,
rf_useMemChunks);
desc->dagArray[i].
numDags++;
if (dag_h == NULL) {
dag_h =
tempdag_h;
} else {
lastdag_h->next
= tempdag_h;
}
lastdag_h = tempdag_h;
bFunc = blockFuncs
[stripeUnitNum][k];
RF_ASSERT(bFunc);
asm_bp = asmh_b
[stripeUnitNum][k]
->stripeMap;
(*bFunc) (raidPtr,
asm_bp, tempdag_h,
bp, flags,
tempdag_h
->allocList);
}
stripeUnitNum++;
} else {
/*
* Create a dag for this unit.
*/
rf_InitHdrNode(&tempdag_h,
raidPtr, rf_useMemChunks);
desc->dagArray[i].numDags++;
if (dag_h == NULL) {
dag_h = tempdag_h;
} else {
lastdag_h->next =
tempdag_h;
}
lastdag_h = tempdag_h;
asm_up = asmh_u[stripeNum][j]
->stripeMap;
(*uFunc) (raidPtr, asm_up,
tempdag_h, bp, flags,
tempdag_h->allocList);
}
}
RF_ASSERT(j == asm_p->numStripeUnitsAccessed);
/*
* Merge linked bailout dag to existing dag
* collection.
*/
stripeNum++;
} else {
/* Create a dag for this parity stripe. */
rf_InitHdrNode(&tempdag_h, raidPtr,
rf_useMemChunks);
desc->dagArray[i].numDags++;
if (dag_h == NULL) {
dag_h = tempdag_h;
} else {
lastdag_h->next = tempdag_h;
}
lastdag_h = tempdag_h;
(stripeFuncs[i]) (raidPtr, asm_p, tempdag_h,
bp, flags, tempdag_h->allocList);
}
desc->dagArray[i].dags = dag_h;
}
RF_ASSERT(i == desc->numStripes);
/* Free memory. */
if (asm_h->numStripes > MAXNSTRIPES)
RF_Free(stripeFuncs, asm_h->numStripes *
sizeof(RF_VoidFuncPtr));
if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) {
stripeNum = 0;
stripeUnitNum = 0;
if (dag_h->asmList) {
endASMList = dag_h->asmList;
while (endASMList->next)
endASMList = endASMList->next;
} else
endASMList = NULL;
/* Walk through io, stripe by stripe. */
for (i = 0, asm_p = asmap; asm_p;
asm_p = asm_p->next, i++)
if (stripeFuncs[i] == NULL) {
numStripeUnits =
asm_p->numStripeUnitsAccessed;
/*
* Walk through stripe, stripe unit by
* stripe unit.
*/
for (j = 0, physPtr = asm_p->physInfo;
physPtr;
physPtr = physPtr->next, j++) {
if (stripeUnitFuncs[stripeNum]
[j] == NULL) {
numBlocks =
physPtr->numSector;
/*
* Walk through stripe
* unit, block by
* block.
*/
for (k = 0; k <
numBlocks; k++)
if (dag_h
->asmList
== NULL) {
dag_h->asmList =
asmh_b[stripeUnitNum][k];
endASMList = dag_h->asmList;
} else {
endASMList->next =
asmh_b[stripeUnitNum][k];
endASMList = endASMList->next;
}
RF_Free(asmh_b
[stripeUnitNum], numBlocks *
sizeof(RF_AccessStripeMapHeader_t *));
RF_Free(blockFuncs
[stripeUnitNum], numBlocks *
sizeof(RF_VoidFuncPtr));
stripeUnitNum++;
}
if (dag_h->asmList == NULL) {
dag_h->asmList = asmh_u
[stripeNum][j];
endASMList = dag_h
->asmList;
} else {
endASMList->next =
asmh_u[stripeNum]
[j];
endASMList = endASMList
->next;
}
}
RF_Free(asmh_u[stripeNum],
numStripeUnits *
sizeof(
RF_AccessStripeMapHeader_t *));
RF_Free(stripeUnitFuncs[stripeNum],
numStripeUnits *
sizeof(RF_VoidFuncPtr));
stripeNum++;
}
RF_ASSERT(stripeNum == numStripesBailed);
RF_Free(stripeUnitFuncs, asm_h->numStripes *
sizeof(RF_VoidFuncPtr));
RF_Free(asmh_u, asm_h->numStripes *
sizeof(RF_AccessStripeMapHeader_t **));
if (numStripeUnitsBailed > 0) {
RF_ASSERT(stripeUnitNum ==
numStripeUnitsBailed);
RF_Free(blockFuncs, raidPtr->Layout.numDataCol
* asm_h->numStripes *
sizeof(RF_VoidFuncPtr));
RF_Free(asmh_b, raidPtr->Layout.numDataCol *
asm_h->numStripes *
sizeof(RF_AccessStripeMapHeader_t **));
}
}
return (0);
}
}
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_aselect.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe