/*	$OpenBSD: rf_aselect.c,v 1.2 1999/02/16 00:02:23 niklas 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
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(__OpenBSD__)) && 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__ || __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.
 *
 ****************************************************************************************/
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 50

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);
	}
}