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