Annotation of sys/dev/raidframe/rf_dag.h, Revision 1.1.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