Annotation of sys/dev/raidframe/rf_dag.h, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: rf_dag.h,v 1.4 2002/12/16 07:01:03 tdeval Exp $ */
! 2: /* $NetBSD: rf_dag.h,v 1.3 1999/02/05 00:06:07 oster Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1995 Carnegie-Mellon University.
! 6: * All rights reserved.
! 7: *
! 8: * Author: William V. Courtright II, Mark Holland
! 9: *
! 10: * Permission to use, copy, modify and distribute this software and
! 11: * its documentation is hereby granted, provided that both the copyright
! 12: * notice and this permission notice appear in all copies of the
! 13: * software, derivative works or modified versions, and any portions
! 14: * thereof, and that both notices appear in supporting documentation.
! 15: *
! 16: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
! 17: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
! 18: * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
! 19: *
! 20: * Carnegie Mellon requests users of this software to return to
! 21: *
! 22: * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
! 23: * School of Computer Science
! 24: * Carnegie Mellon University
! 25: * Pittsburgh PA 15213-3890
! 26: *
! 27: * any improvements or extensions that they make and grant Carnegie the
! 28: * rights to redistribute these changes.
! 29: */
! 30:
! 31: /****************************************************************************
! 32: * *
! 33: * dag.h -- header file for DAG-related data structures *
! 34: * *
! 35: ****************************************************************************/
! 36:
! 37: #ifndef _RF__RF_DAG_H_
! 38: #define _RF__RF_DAG_H_
! 39:
! 40: #include "rf_types.h"
! 41: #include "rf_threadstuff.h"
! 42: #include "rf_alloclist.h"
! 43: #include "rf_stripelocks.h"
! 44: #include "rf_layout.h"
! 45: #include "rf_dagflags.h"
! 46: #include "rf_acctrace.h"
! 47: #include "rf_memchunk.h"
! 48:
! 49: #define RF_THREAD_CONTEXT 0 /* We were invoked from thread context. */
! 50: #define RF_INTR_CONTEXT 1 /* We were invoked from interrupt context. */
! 51: #define RF_MAX_ANTECEDENTS 20 /* Max num of antecedents a node may possess. */
! 52:
! 53: #include <sys/buf.h>
! 54:
! 55: struct RF_PropHeader_s { /* Structure for propagation of results. */
! 56: int resultNum; /* Bind result # resultNum. */
! 57: int paramNum; /* To parameter # paramNum. */
! 58: RF_PropHeader_t *next; /* Linked list for multiple
! 59: * results/params. */
! 60: };
! 61:
! 62: typedef enum RF_NodeStatus_e {
! 63: rf_bwd1, /*
! 64: * Node is ready for undo logging
! 65: * (backward error recovery only).
! 66: */
! 67: rf_bwd2, /*
! 68: * Node has completed undo logging
! 69: * (backward error recovery only).
! 70: */
! 71: rf_wait, /* Node is waiting to be executed. */
! 72: rf_fired, /* Node is currently executing its do function. */
! 73: rf_good, /*
! 74: * Node successfully completed execution
! 75: * of its do function.
! 76: */
! 77: rf_bad, /*
! 78: * Node failed to successfully execute
! 79: * its do function.
! 80: */
! 81: rf_skipped, /*
! 82: * Not used anymore, used to imply a node
! 83: * was not executed.
! 84: */
! 85: rf_recover, /* Node is currently executing its undo function. */
! 86: rf_panic, /*
! 87: * Node failed to successfully execute
! 88: * its undo function.
! 89: */
! 90: rf_undone /* Node successfully executed its undo function. */
! 91: } RF_NodeStatus_t;
! 92:
! 93: /*
! 94: * These were used to control skipping a node.
! 95: * Now, these are only used as comments.
! 96: */
! 97: typedef enum RF_AntecedentType_e {
! 98: rf_trueData,
! 99: rf_antiData,
! 100: rf_outputData,
! 101: rf_control
! 102: } RF_AntecedentType_t;
! 103: #define RF_DAG_PTRCACHESIZE 40
! 104: #define RF_DAG_PARAMCACHESIZE 12
! 105:
! 106: typedef RF_uint8 RF_DagNodeFlags_t;
! 107:
! 108: struct RF_DagNode_s {
! 109: RF_NodeStatus_t status; /* Current status of this node. */
! 110: int (*doFunc) (RF_DagNode_t *);
! 111: /* Normal function. */
! 112: int (*undoFunc) (RF_DagNode_t *);
! 113: /* Func to remove effect of doFunc. */
! 114: int (*wakeFunc) (RF_DagNode_t *, int status);
! 115: /*
! 116: * Func called when the node completes
! 117: * an I/O.
! 118: */
! 119: int numParams; /*
! 120: * Number of parameters required
! 121: * by *funcPtr.
! 122: */
! 123: int numResults; /*
! 124: * Number of results produced
! 125: * by *funcPtr.
! 126: */
! 127: int numAntecedents; /* Number of antecedents. */
! 128: int numAntDone; /*
! 129: * Number of antecedents that
! 130: * have finished.
! 131: */
! 132: int numSuccedents; /* Number of succedents. */
! 133: int numSuccFired; /*
! 134: * Incremented when a succedent
! 135: * is fired during forward execution.
! 136: */
! 137: int numSuccDone; /*
! 138: * Incremented when a succedent
! 139: * finishes during rollBackward.
! 140: */
! 141: int commitNode; /*
! 142: * Boolean flag - if true, this is
! 143: * a commit node.
! 144: */
! 145: RF_DagNode_t **succedents; /*
! 146: * Succedents, array size
! 147: * numSuccedents.
! 148: */
! 149: RF_DagNode_t **antecedents; /*
! 150: * Antecedents, array size
! 151: * numAntecedents.
! 152: */
! 153: RF_AntecedentType_t antType[RF_MAX_ANTECEDENTS];
! 154: /* Type of each antecedent. */
! 155: void **results; /*
! 156: * Array of results produced
! 157: * by *funcPtr.
! 158: */
! 159: RF_DagParam_t *params; /*
! 160: * Array of parameters required
! 161: * by *funcPtr.
! 162: */
! 163: RF_PropHeader_t **propList; /*
! 164: * Propagation list,
! 165: * size numSuccedents.
! 166: */
! 167: RF_DagHeader_t *dagHdr; /*
! 168: * Ptr to head of dag containing
! 169: * this node.
! 170: */
! 171: void *dagFuncData; /*
! 172: * Dag execution func uses this
! 173: * for whatever it wants.
! 174: */
! 175: RF_DagNode_t *next;
! 176: int nodeNum; /* Used by PrintDAG for debug only. */
! 177: int visited; /*
! 178: * Used to avoid re-visiting
! 179: * nodes on DAG walks.
! 180: */
! 181: /*
! 182: * ANY CODE THAT USES THIS FIELD MUST MAINTAIN THE PROPERTY THAT
! 183: * AFTER IT FINISHES, ALL VISITED FLAGS IN THE DAG ARE IDENTICAL.
! 184: */
! 185:
! 186: char *name; /* Debug only. */
! 187: RF_DagNodeFlags_t flags; /* See below. */
! 188: RF_DagNode_t *dag_ptrs[RF_DAG_PTRCACHESIZE];
! 189: /* Cache for performance. */
! 190: RF_DagParam_t dag_params[RF_DAG_PARAMCACHESIZE];
! 191: /* Cache for performance. */
! 192: };
! 193:
! 194: /*
! 195: * Bit values for flags field of RF_DagNode_t.
! 196: */
! 197: #define RF_DAGNODE_FLAG_NONE 0x00
! 198: #define RF_DAGNODE_FLAG_YIELD 0x01 /*
! 199: * In the kernel, yield the processor
! 200: * before firing this node.
! 201: */
! 202:
! 203: /*
! 204: * rf_enable - DAG ready for normal execution, no errors encountered.
! 205: * rf_rollForward - DAG encountered an error after commit point, rolling
! 206: * forward.
! 207: * rf_rollBackward - DAG encountered an error prior to commit point, rolling
! 208: * backward.
! 209: */
! 210: typedef enum RF_DagStatus_e {
! 211: rf_enable,
! 212: rf_rollForward,
! 213: rf_rollBackward
! 214: } RF_DagStatus_t;
! 215:
! 216: #define RF_MAX_HDR_SUCC 1
! 217:
! 218: #define RF_MAXCHUNKS 10
! 219:
! 220: struct RF_DagHeader_s {
! 221: RF_DagStatus_t status; /* Status of this DAG. */
! 222: int numSuccedents; /*
! 223: * DAG may be a tree,
! 224: * i.e. may have > 1 root.
! 225: */
! 226: int numCommitNodes; /*
! 227: * Number of commit nodes
! 228: * in graph.
! 229: */
! 230: int numCommits; /*
! 231: * Number of commit nodes
! 232: * that have been fired.
! 233: */
! 234: RF_DagNode_t *succedents[RF_MAX_HDR_SUCC]; /*
! 235: * Array of succedents,
! 236: * size numSuccedents.
! 237: */
! 238: RF_DagHeader_t *next; /*
! 239: * Ptr to allow a list
! 240: * of dags.
! 241: */
! 242: RF_AllocListElem_t *allocList; /*
! 243: * Ptr to list of ptrs
! 244: * to be freed prior to
! 245: * freeing DAG.
! 246: */
! 247: RF_AccessStripeMapHeader_t *asmList; /*
! 248: * List of access stripe maps
! 249: * to be freed.
! 250: */
! 251: int nodeNum; /*
! 252: * Used by PrintDAG for
! 253: * debug only.
! 254: */
! 255: int numNodesCompleted;
! 256: RF_AccTraceEntry_t *tracerec; /* Perf mon only. */
! 257:
! 258: void (*cbFunc) (void *); /*
! 259: * Function to call when
! 260: * the dag completes.
! 261: */
! 262: void *cbArg; /* Argument for cbFunc. */
! 263: char *creator; /*
! 264: * Name of function used
! 265: * to create this dag.
! 266: */
! 267:
! 268: RF_Raid_t *raidPtr; /*
! 269: * The descriptor for the
! 270: * RAID device this DAG
! 271: * is for.
! 272: */
! 273: void *bp; /*
! 274: * The bp for this I/O passed
! 275: * down from the file system.
! 276: * ignored outside kernel.
! 277: */
! 278:
! 279: RF_ChunkDesc_t *memChunk[RF_MAXCHUNKS]; /*
! 280: * Experimental- Chunks of
! 281: * memory to be retained upon
! 282: * DAG free for re-use.
! 283: */
! 284: int chunkIndex; /*
! 285: * The idea is to avoid calls
! 286: * to alloc and free.
! 287: */
! 288:
! 289: RF_ChunkDesc_t **xtraMemChunk; /*
! 290: * Escape hatch that allows
! 291: * SelectAlgorithm to merge
! 292: * memChunks from several dags.
! 293: */
! 294: int xtraChunkIndex; /*
! 295: * Number of ptrs to valid
! 296: * chunks.
! 297: */
! 298: int xtraChunkCnt; /*
! 299: * Number of ptrs to chunks
! 300: * allocated.
! 301: */
! 302: };
! 303:
! 304: struct RF_DagList_s {
! 305: /* Common info for a list of dags that will be fired sequentially. */
! 306: int numDags; /* Number of dags in the list. */
! 307: int numDagsFired; /*
! 308: * Number of dags in list that
! 309: * have initiated execution.
! 310: */
! 311: int numDagsDone; /*
! 312: * Number of dags in list that
! 313: * have completed execution.
! 314: */
! 315: RF_DagHeader_t *dags; /* List of dags. */
! 316: RF_RaidAccessDesc_t *desc; /* Ptr to descriptor for this access. */
! 317: RF_AccTraceEntry_t tracerec; /*
! 318: * Perf mon info for dags (not user
! 319: * info).
! 320: */
! 321: };
! 322:
! 323: /* Reset a node so that it can be fired again. */
! 324: #define RF_ResetNode(_n_) do { \
! 325: (_n_)->status = rf_wait; \
! 326: (_n_)->numAntDone = 0; \
! 327: (_n_)->numSuccFired = 0; \
! 328: (_n_)->numSuccDone = 0; \
! 329: (_n_)->next = NULL; \
! 330: } while (0)
! 331:
! 332: #define RF_ResetDagHeader(_h_) do { \
! 333: (_h_)->numNodesCompleted = 0; \
! 334: (_h_)->numCommits = 0; \
! 335: (_h_)->status = rf_enable; \
! 336: } while (0)
! 337:
! 338: /* Convenience macro for declaring a create dag function. */
! 339: #define RF_CREATE_DAG_FUNC_DECL(_name_) \
! 340: void _name_ (RF_Raid_t *, RF_AccessStripeMap_t *, RF_DagHeader_t *, \
! 341: void *, RF_RaidAccessFlags_t, RF_AllocListElem_t *); \
! 342: void _name_ ( \
! 343: RF_Raid_t *raidPtr, \
! 344: RF_AccessStripeMap_t *asmap, \
! 345: RF_DagHeader_t *dag_h, \
! 346: void *bp, \
! 347: RF_RaidAccessFlags_t flags, \
! 348: RF_AllocListElem_t *allocList \
! 349: )
! 350:
! 351: #endif /* !_RF__RF_DAG_H_ */
CVSweb