summaryrefslogtreecommitdiffstats
path: root/sys/dev/raidframe/rf_aselect.c
diff options
context:
space:
mode:
Diffstat (limited to 'sys/dev/raidframe/rf_aselect.c')
-rw-r--r--sys/dev/raidframe/rf_aselect.c494
1 files changed, 494 insertions, 0 deletions
diff --git a/sys/dev/raidframe/rf_aselect.c b/sys/dev/raidframe/rf_aselect.c
new file mode 100644
index 0000000..4fe69e3
--- /dev/null
+++ b/sys/dev/raidframe/rf_aselect.c
@@ -0,0 +1,494 @@
+/* $FreeBSD$ */
+/* $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 <dev/raidframe/rf_archs.h>
+#include <dev/raidframe/rf_types.h>
+#include <dev/raidframe/rf_raid.h>
+#include <dev/raidframe/rf_dag.h>
+#include <dev/raidframe/rf_dagutils.h>
+#include <dev/raidframe/rf_dagfuncs.h>
+#include <dev/raidframe/rf_general.h>
+#include <dev/raidframe/rf_desc.h>
+#include <dev/raidframe/rf_map.h>
+
+#if defined(__NetBSD__) || defined(__FreeBSD__) && defined(_KERNEL)
+/* the function below is not used... so don't define it! */
+#else
+static void TransferDagMemory(RF_DagHeader_t *, RF_DagHeader_t *);
+#endif
+
+static int InitHdrNode(RF_DagHeader_t **, RF_Raid_t *, int);
+static void UpdateNodeHdrPtr(RF_DagHeader_t *, RF_DagNode_t *);
+int rf_SelectAlgorithm(RF_RaidAccessDesc_t *, RF_RaidAccessFlags_t);
+
+
+/******************************************************************************
+ *
+ * Create and Initialiaze a dag header and termination node
+ *
+ *****************************************************************************/
+static int
+InitHdrNode(hdr, raidPtr, memChunkEnable)
+ 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(__FreeBSD__) && defined(_KERNEL)
+/* the function below is not used... so don't define it! */
+#else
+static void
+TransferDagMemory(daga, dagb)
+ 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__ */
+
+/*****************************************************************************************
+ *
+ * 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.
+ *
+ ****************************************************************************************/
+static void
+UpdateNodeHdrPtr(hdr, node)
+ 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)
+ 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 which 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 5
+
+int
+rf_SelectAlgorithm(desc, flags)
+ 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 */
+ 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 */
+ 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 */
+ 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);
+ }
+}
OpenPOWER on IntegriCloud