rf_dag.h revision 1.1
1 /* $NetBSD: rf_dag.h,v 1.1 1998/11/13 04:20:27 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 (at) 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 * 36 * : 37 * Log: rf_dag.h,v 38 * Revision 1.35 1996/11/05 18:38:37 jimz 39 * add patch from galvarez (at) cs.ucsd.edu (Guillermo Alvarez) 40 * to fix dag_params memory-sizing problem (should be an array 41 * of the type, not an array of pointers to the type) 42 * 43 * Revision 1.34 1996/07/28 20:31:39 jimz 44 * i386netbsd port 45 * true/false fixup 46 * 47 * Revision 1.33 1996/07/22 19:52:16 jimz 48 * switched node params to RF_DagParam_t, a union of 49 * a 64-bit int and a void *, for better portability 50 * attempted hpux port, but failed partway through for 51 * lack of a single C compiler capable of compiling all 52 * source files 53 * 54 * Revision 1.32 1996/06/10 22:22:13 wvcii 55 * added two node status types for use in backward error 56 * recovery experiments. 57 * 58 * Revision 1.31 1996/06/09 02:36:46 jimz 59 * lots of little crufty cleanup- fixup whitespace 60 * issues, comment #ifdefs, improve typing in some 61 * places (esp size-related) 62 * 63 * Revision 1.30 1996/06/07 22:49:18 jimz 64 * fix up raidPtr typing 65 * 66 * Revision 1.29 1996/05/27 18:56:37 jimz 67 * more code cleanup 68 * better typing 69 * compiles in all 3 environments 70 * 71 * Revision 1.28 1996/05/24 22:17:04 jimz 72 * continue code + namespace cleanup 73 * typed a bunch of flags 74 * 75 * Revision 1.27 1996/05/24 04:28:55 jimz 76 * release cleanup ckpt 77 * 78 * Revision 1.26 1996/05/23 21:46:35 jimz 79 * checkpoint in code cleanup (release prep) 80 * lots of types, function names have been fixed 81 * 82 * Revision 1.25 1996/05/23 00:33:23 jimz 83 * code cleanup: move all debug decls to rf_options.c, all extern 84 * debug decls to rf_options.h, all debug vars preceded by rf_ 85 * 86 * Revision 1.24 1996/05/18 19:51:34 jimz 87 * major code cleanup- fix syntax, make some types consistent, 88 * add prototypes, clean out dead code, et cetera 89 * 90 * Revision 1.23 1996/05/16 23:05:20 jimz 91 * Added dag_ptrs field, RF_DAG_PTRCACHESIZE 92 * 93 * The dag_ptrs field of the node is basically some scribble 94 * space to be used here. We could get rid of it, and always 95 * allocate the range of pointers, but that's expensive. So, 96 * we pick a "common case" size for the pointer cache. Hopefully, 97 * we'll find that: 98 * (1) Generally, nptrs doesn't exceed RF_DAG_PTRCACHESIZE by 99 * only a little bit (least efficient case) 100 * (2) Generally, ntprs isn't a lot less than RF_DAG_PTRCACHESIZE 101 * (wasted memory) 102 * 103 * Revision 1.22 1996/05/08 21:01:24 jimz 104 * fixed up enum type names that were conflicting with other 105 * enums and function names (ie, "panic") 106 * future naming trends will be towards RF_ and rf_ for 107 * everything raidframe-related 108 * 109 * Revision 1.21 1996/05/08 15:23:47 wvcii 110 * added new node states: undone, recover, panic 111 * 112 * Revision 1.20 1995/12/01 14:59:19 root 113 * increased MAX_ANTECEDENTS from 10 to 20 114 * should consider getting rid of this (eliminate static array) 115 * 116 * Revision 1.19 1995/11/30 15:58:59 wvcii 117 * added copyright info 118 * 119 * Revision 1.18 1995/11/19 16:27:03 wvcii 120 * created struct dagList 121 * 122 * Revision 1.17 1995/11/07 15:43:01 wvcii 123 * added static array to DAGnode: antType 124 * added commitNode type 125 * added commit node counts to dag header 126 * added ptr (firstDag) to support multi-dag requests 127 * added succedent done/fired counts to nodes to support rollback 128 * added node status type "skipped" 129 * added hdr status types "rollForward, rollBackward" 130 * deleted hdr status type "disable" 131 * updated ResetNode & ResetDAGHeader to zero new fields 132 * 133 */ 134 135 #ifndef _RF__RF_DAG_H_ 136 #define _RF__RF_DAG_H_ 137 138 #include "rf_types.h" 139 #include "rf_threadstuff.h" 140 #include "rf_alloclist.h" 141 #include "rf_stripelocks.h" 142 #include "rf_layout.h" 143 #include "rf_dagflags.h" 144 #include "rf_acctrace.h" 145 #include "rf_memchunk.h" 146 147 #define RF_THREAD_CONTEXT 0 /* we were invoked from thread context */ 148 #define RF_INTR_CONTEXT 1 /* we were invoked from interrupt context */ 149 #define RF_MAX_ANTECEDENTS 20 /* max num of antecedents a node may posses */ 150 151 #ifdef KERNEL 152 #include <sys/buf.h> 153 #endif /* KERNEL */ 154 155 struct RF_PropHeader_s { /* structure for propagation of results */ 156 int resultNum; /* bind result # resultNum */ 157 int paramNum; /* to parameter # paramNum */ 158 RF_PropHeader_t *next; /* linked list for multiple results/params */ 159 }; 160 161 typedef enum RF_NodeStatus_e { 162 rf_bwd1, /* node is ready for undo logging (backward error recovery only) */ 163 rf_bwd2, /* node has completed undo logging (backward error recovery only) */ 164 rf_wait, /* node is waiting to be executed */ 165 rf_fired, /* node is currently executing its do function */ 166 rf_good, /* node successfully completed execution of its do function */ 167 rf_bad, /* node failed to successfully execute its do function */ 168 rf_skipped, /* not used anymore, used to imply a node was not executed */ 169 rf_recover, /* node is currently executing its undo function */ 170 rf_panic, /* node failed to successfully execute its undo function */ 171 rf_undone /* node successfully executed its undo function */ 172 } RF_NodeStatus_t; 173 174 /* 175 * These were used to control skipping a node. 176 * Now, these are only used as comments. 177 */ 178 typedef enum RF_AntecedentType_e { 179 rf_trueData, 180 rf_antiData, 181 rf_outputData, 182 rf_control 183 } RF_AntecedentType_t; 184 185 #define RF_DAG_PTRCACHESIZE 40 186 #define RF_DAG_PARAMCACHESIZE 12 187 188 typedef RF_uint8 RF_DagNodeFlags_t; 189 190 struct RF_DagNode_s { 191 RF_NodeStatus_t status; /* current status of this node */ 192 int (*doFunc)(RF_DagNode_t *); /* normal function */ 193 int (*undoFunc)(RF_DagNode_t *); /* func to remove effect of doFunc */ 194 int (*wakeFunc)(RF_DagNode_t *, int status); /* func called when the node completes an I/O */ 195 int numParams; /* number of parameters required by *funcPtr */ 196 int numResults; /* number of results produced by *funcPtr */ 197 int numAntecedents; /* number of antecedents */ 198 int numAntDone; /* number of antecedents which have finished */ 199 int numSuccedents; /* number of succedents */ 200 int numSuccFired; /* incremented when a succedent is fired during forward execution */ 201 int numSuccDone; /* incremented when a succedent finishes during rollBackward */ 202 int commitNode; /* boolean flag - if true, this is a commit node */ 203 RF_DagNode_t **succedents; /* succedents, array size numSuccedents */ 204 RF_DagNode_t **antecedents; /* antecedents, array size numAntecedents */ 205 RF_AntecedentType_t antType[RF_MAX_ANTECEDENTS]; /* type of each antecedent */ 206 void **results; /* array of results produced by *funcPtr */ 207 RF_DagParam_t *params; /* array of parameters required by *funcPtr */ 208 RF_PropHeader_t **propList; /* propagation list, size numSuccedents */ 209 RF_DagHeader_t *dagHdr; /* ptr to head of dag containing this node */ 210 void *dagFuncData; /* dag execution func uses this for whatever it wants */ 211 RF_DagNode_t *next; 212 int nodeNum; /* used by PrintDAG for debug only */ 213 int visited; /* used to avoid re-visiting nodes on DAG walks */ 214 /* ANY CODE THAT USES THIS FIELD MUST MAINTAIN THE PROPERTY 215 * THAT AFTER IT FINISHES, ALL VISITED FLAGS IN THE DAG ARE IDENTICAL */ 216 char *name; /* debug only */ 217 RF_DagNodeFlags_t flags; /* see below */ 218 RF_DagNode_t *dag_ptrs[RF_DAG_PTRCACHESIZE]; /* cache for performance */ 219 RF_DagParam_t dag_params[RF_DAG_PARAMCACHESIZE]; /* cache for performance */ 220 }; 221 222 /* 223 * Bit values for flags field of RF_DagNode_t 224 */ 225 #define RF_DAGNODE_FLAG_NONE 0x00 226 #define RF_DAGNODE_FLAG_YIELD 0x01 /* in the kernel, yield the processor before firing this node */ 227 228 /* enable - DAG ready for normal execution, no errors encountered 229 * rollForward - DAG encountered an error after commit point, rolling forward 230 * rollBackward - DAG encountered an error prior to commit point, rolling backward 231 */ 232 typedef enum RF_DagStatus_e { 233 rf_enable, 234 rf_rollForward, 235 rf_rollBackward 236 } RF_DagStatus_t; 237 238 #define RF_MAX_HDR_SUCC 1 239 240 #define RF_MAXCHUNKS 10 241 242 struct RF_DagHeader_s { 243 RF_DagStatus_t status; /* status of this DAG */ 244 int numSuccedents; /* DAG may be a tree, i.e. may have > 1 root */ 245 int numCommitNodes; /* number of commit nodes in graph */ 246 int numCommits; /* number of commit nodes which have been fired */ 247 RF_DagNode_t *succedents[RF_MAX_HDR_SUCC]; /* array of succedents, size numSuccedents */ 248 RF_DagHeader_t *next; /* ptr to allow a list of dags */ 249 RF_AllocListElem_t *allocList; /* ptr to list of ptrs to be freed prior to freeing DAG */ 250 RF_AccessStripeMapHeader_t *asmList; /* list of access stripe maps to be freed */ 251 int nodeNum; /* used by PrintDAG for debug only */ 252 int numNodesCompleted; 253 RF_AccTraceEntry_t *tracerec; /* perf mon only */ 254 255 void (*cbFunc)(void *); /* function to call when the dag completes */ 256 void *cbArg; /* argument for cbFunc */ 257 char *creator; /* name of function used to create this dag */ 258 259 RF_Raid_t *raidPtr; /* the descriptor for the RAID device this DAG is for */ 260 void *bp; /* the bp for this I/O passed down from the file system. ignored outside kernel */ 261 262 RF_ChunkDesc_t *memChunk[RF_MAXCHUNKS]; /* experimental- Chunks of memory to be retained upon DAG free for re-use */ 263 int chunkIndex; /* the idea is to avoid calls to alloc and free */ 264 265 RF_ChunkDesc_t **xtraMemChunk; /* escape hatch which allows SelectAlgorithm to merge memChunks from several dags */ 266 int xtraChunkIndex; /* number of ptrs to valid chunks */ 267 int xtraChunkCnt; /* number of ptrs to chunks allocated */ 268 269 #ifdef SIMULATE 270 int done; /* Tag to tell if termination node has been fired */ 271 #endif /* SIMULATE */ 272 }; 273 274 struct RF_DagList_s { 275 /* common info for a list of dags which will be fired sequentially */ 276 int numDags; /* number of dags in the list */ 277 int numDagsFired; /* number of dags in list which have initiated execution */ 278 int numDagsDone; /* number of dags in list which have completed execution */ 279 RF_DagHeader_t *dags; /* list of dags */ 280 RF_RaidAccessDesc_t *desc; /* ptr to descriptor for this access */ 281 RF_AccTraceEntry_t tracerec; /* perf mon info for dags (not user info) */ 282 }; 283 284 /* resets a node so that it can be fired again */ 285 #define RF_ResetNode(_n_) { \ 286 (_n_)->status = rf_wait; \ 287 (_n_)->numAntDone = 0; \ 288 (_n_)->numSuccFired = 0; \ 289 (_n_)->numSuccDone = 0; \ 290 (_n_)->next = NULL; \ 291 } 292 293 #ifdef SIMULATE 294 #define RF_ResetDagHeader(_h_) { \ 295 (_h_)->done = RF_FALSE; \ 296 (_h_)->numNodesCompleted = 0; \ 297 (_h_)->numCommits = 0; \ 298 (_h_)->status = rf_enable; \ 299 } 300 #else /* SIMULATE */ 301 #define RF_ResetDagHeader(_h_) { \ 302 (_h_)->numNodesCompleted = 0; \ 303 (_h_)->numCommits = 0; \ 304 (_h_)->status = rf_enable; \ 305 } 306 #endif /* SIMULATE */ 307 308 /* convience macro for declaring a create dag function */ 309 310 #define RF_CREATE_DAG_FUNC_DECL(_name_) \ 311 void _name_ ( \ 312 RF_Raid_t *raidPtr, \ 313 RF_AccessStripeMap_t *asmap, \ 314 RF_DagHeader_t *dag_h, \ 315 void *bp, \ 316 RF_RaidAccessFlags_t flags, \ 317 RF_AllocListElem_t *allocList) 318 319 #endif /* !_RF__RF_DAG_H_ */ 320
Indexes created Fri Sep 26 20:09:58 GMT 2025