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_ */ 352