1 /* $NetBSD: rf_dag.h,v 1.4 2001/10/04 15:58:51 oster Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Author: William V. Courtright II, Mark Holland 7 * 8 * Permission to use, copy, modify and distribute this software and 9 * its documentation is hereby granted, provided that both the copyright 10 * notice and this permission notice appear in all copies of the 11 * software, derivative works or modified versions, and any portions 12 * thereof, and that both notices appear in supporting documentation. 13 * 14 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 15 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 16 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 17 * 18 * Carnegie Mellon requests users of this software to return to 19 * 20 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 21 * School of Computer Science 22 * Carnegie Mellon University 23 * Pittsburgh PA 15213-3890 24 * 25 * any improvements or extensions that they make and grant Carnegie the 26 * rights to redistribute these changes. 27 */ 28 29 /**************************************************************************** 30 * * 31 * dag.h -- header file for DAG-related data structures * 32 * * 33 ****************************************************************************/ 34 35 #ifndef _RF__RF_DAG_H_ 36 #define _RF__RF_DAG_H_ 37 38 #include <dev/raidframe/raidframevar.h> 39 40 #include "rf_threadstuff.h" 41 #include "rf_alloclist.h" 42 #include "rf_stripelocks.h" 43 #include "rf_layout.h" 44 #include "rf_dagflags.h" 45 #include "rf_acctrace.h" 46 #include "rf_memchunk.h" 47 48 #define RF_THREAD_CONTEXT 0 /* we were invoked from thread context */ 49 #define RF_INTR_CONTEXT 1 /* we were invoked from interrupt context */ 50 #define RF_MAX_ANTECEDENTS 20 /* max num of antecedents a node may posses */ 51 52 #include <sys/buf.h> 53 54 struct RF_PropHeader_s { /* structure for propagation of results */ 55 int resultNum; /* bind result # resultNum */ 56 int paramNum; /* to parameter # paramNum */ 57 RF_PropHeader_t *next; /* linked list for multiple results/params */ 58 }; 59 60 typedef enum RF_NodeStatus_e { 61 rf_bwd1, /* node is ready for undo logging (backward 62 * error recovery only) */ 63 rf_bwd2, /* node has completed undo logging (backward 64 * error recovery only) */ 65 rf_wait, /* node is waiting to be executed */ 66 rf_fired, /* node is currently executing its do function */ 67 rf_good, /* node successfully completed execution of 68 * its do function */ 69 rf_bad, /* node failed to successfully execute its do 70 * function */ 71 rf_skipped, /* not used anymore, used to imply a node was 72 * not executed */ 73 rf_recover, /* node is currently executing its undo 74 * function */ 75 rf_panic, /* node failed to successfully execute its 76 * undo function */ 77 rf_undone /* node successfully executed its undo 78 * function */ 79 } RF_NodeStatus_t; 80 /* 81 * These were used to control skipping a node. 82 * Now, these are only used as comments. 83 */ 84 typedef enum RF_AntecedentType_e { 85 rf_trueData, 86 rf_antiData, 87 rf_outputData, 88 rf_control 89 } RF_AntecedentType_t; 90 #define RF_DAG_PTRCACHESIZE 40 91 #define RF_DAG_PARAMCACHESIZE 12 92 93 typedef RF_uint8 RF_DagNodeFlags_t; 94 95 struct RF_DagNode_s { 96 RF_NodeStatus_t status; /* current status of this node */ 97 int (*doFunc) (RF_DagNode_t *); /* normal function */ 98 int (*undoFunc) (RF_DagNode_t *); /* func to remove effect of 99 * doFunc */ 100 int (*wakeFunc) (RF_DagNode_t *, int status); /* func called when the 101 * node completes an I/O */ 102 int numParams; /* number of parameters required by *funcPtr */ 103 int numResults; /* number of results produced by *funcPtr */ 104 int numAntecedents; /* number of antecedents */ 105 int numAntDone; /* number of antecedents which have finished */ 106 int numSuccedents; /* number of succedents */ 107 int numSuccFired; /* incremented when a succedent is fired 108 * during forward execution */ 109 int numSuccDone; /* incremented when a succedent finishes 110 * during rollBackward */ 111 int commitNode; /* boolean flag - if true, this is a commit 112 * node */ 113 RF_DagNode_t **succedents; /* succedents, array size 114 * numSuccedents */ 115 RF_DagNode_t **antecedents; /* antecedents, array size 116 * numAntecedents */ 117 RF_AntecedentType_t antType[RF_MAX_ANTECEDENTS]; /* type of each 118 * antecedent */ 119 void **results; /* array of results produced by *funcPtr */ 120 RF_DagParam_t *params; /* array of parameters required by *funcPtr */ 121 RF_PropHeader_t **propList; /* propagation list, size 122 * numSuccedents */ 123 RF_DagHeader_t *dagHdr; /* ptr to head of dag containing this node */ 124 void *dagFuncData; /* dag execution func uses this for whatever 125 * it wants */ 126 RF_DagNode_t *next; 127 int nodeNum; /* used by PrintDAG for debug only */ 128 int visited; /* used to avoid re-visiting nodes on DAG 129 * walks */ 130 /* ANY CODE THAT USES THIS FIELD MUST MAINTAIN THE PROPERTY THAT AFTER 131 * IT FINISHES, ALL VISITED FLAGS IN THE DAG ARE IDENTICAL */ 132 char *name; /* debug only */ 133 RF_DagNodeFlags_t flags;/* see below */ 134 RF_DagNode_t *dag_ptrs[RF_DAG_PTRCACHESIZE]; /* cache for performance */ 135 RF_DagParam_t dag_params[RF_DAG_PARAMCACHESIZE]; /* cache for performance */ 136 }; 137 /* 138 * Bit values for flags field of RF_DagNode_t 139 */ 140 #define RF_DAGNODE_FLAG_NONE 0x00 141 #define RF_DAGNODE_FLAG_YIELD 0x01 /* in the kernel, yield the processor 142 * before firing this node */ 143 144 /* enable - DAG ready for normal execution, no errors encountered 145 * rollForward - DAG encountered an error after commit point, rolling forward 146 * rollBackward - DAG encountered an error prior to commit point, rolling backward 147 */ 148 typedef enum RF_DagStatus_e { 149 rf_enable, 150 rf_rollForward, 151 rf_rollBackward 152 } RF_DagStatus_t; 153 #define RF_MAX_HDR_SUCC 1 154 155 #define RF_MAXCHUNKS 10 156 157 struct RF_DagHeader_s { 158 RF_DagStatus_t status; /* status of this DAG */ 159 int numSuccedents; /* DAG may be a tree, i.e. may have > 1 root */ 160 int numCommitNodes; /* number of commit nodes in graph */ 161 int numCommits; /* number of commit nodes which have been 162 * fired */ 163 RF_DagNode_t *succedents[RF_MAX_HDR_SUCC]; /* array of succedents, 164 * size numSuccedents */ 165 RF_DagHeader_t *next; /* ptr to allow a list of dags */ 166 RF_AllocListElem_t *allocList; /* ptr to list of ptrs to be freed 167 * prior to freeing DAG */ 168 RF_AccessStripeMapHeader_t *asmList; /* list of access stripe maps 169 * to be freed */ 170 int nodeNum; /* used by PrintDAG for debug only */ 171 int numNodesCompleted; 172 RF_AccTraceEntry_t *tracerec; /* perf mon only */ 173 174 void (*cbFunc) (void *); /* function to call when the dag 175 * completes */ 176 void *cbArg; /* argument for cbFunc */ 177 char *creator; /* name of function used to create this dag */ 178 179 RF_Raid_t *raidPtr; /* the descriptor for the RAID device this DAG 180 * is for */ 181 void *bp; /* the bp for this I/O passed down from the 182 * file system. ignored outside kernel */ 183 184 RF_ChunkDesc_t *memChunk[RF_MAXCHUNKS]; /* experimental- Chunks of 185 * memory to be retained upon 186 * DAG free for re-use */ 187 int chunkIndex; /* the idea is to avoid calls to alloc and 188 * free */ 189 190 RF_ChunkDesc_t **xtraMemChunk; /* escape hatch which allows 191 * SelectAlgorithm to merge memChunks 192 * from several dags */ 193 int xtraChunkIndex; /* number of ptrs to valid chunks */ 194 int xtraChunkCnt; /* number of ptrs to chunks allocated */ 195 196 }; 197 198 struct RF_DagList_s { 199 /* common info for a list of dags which will be fired sequentially */ 200 int numDags; /* number of dags in the list */ 201 int numDagsFired; /* number of dags in list which have initiated 202 * execution */ 203 int numDagsDone; /* number of dags in list which have completed 204 * execution */ 205 RF_DagHeader_t *dags; /* list of dags */ 206 RF_RaidAccessDesc_t *desc; /* ptr to descriptor for this access */ 207 RF_AccTraceEntry_t tracerec; /* perf mon info for dags (not user 208 * info) */ 209 }; 210 /* resets a node so that it can be fired again */ 211 #define RF_ResetNode(_n_) { \ 212 (_n_)->status = rf_wait; \ 213 (_n_)->numAntDone = 0; \ 214 (_n_)->numSuccFired = 0; \ 215 (_n_)->numSuccDone = 0; \ 216 (_n_)->next = NULL; \ 217 } 218 219 #define RF_ResetDagHeader(_h_) { \ 220 (_h_)->numNodesCompleted = 0; \ 221 (_h_)->numCommits = 0; \ 222 (_h_)->status = rf_enable; \ 223 } 224 225 /* convience macro for declaring a create dag function */ 226 227 #define RF_CREATE_DAG_FUNC_DECL(_name_) \ 228 void _name_ ( \ 229 RF_Raid_t *raidPtr, \ 230 RF_AccessStripeMap_t *asmap, \ 231 RF_DagHeader_t *dag_h, \ 232 void *bp, \ 233 RF_RaidAccessFlags_t flags, \ 234 RF_AllocListElem_t *allocList) 235 236 #endif /* !_RF__RF_DAG_H_ */ 237