1 /* $NetBSD: rf_dagffrd.c,v 1.22 2021/07/23 00:54:45 oster Exp $ */
2 /*
3 * Copyright (c) 1995 Carnegie-Mellon University.
4 * All rights reserved.
5 *
6 * Author: Mark Holland, Daniel Stodolsky, William V. Courtright II
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 * rf_dagffrd.c
31 *
32 * code for creating fault-free read DAGs
33 *
34 */
35
36 #include <sys/cdefs.h>
37 __KERNEL_RCSID(0, "$NetBSD: rf_dagffrd.c,v 1.22 2021/07/23 00:54:45 oster Exp $");
38
39 #include <dev/raidframe/raidframevar.h>
40
41 #include "rf_raid.h"
42 #include "rf_dag.h"
43 #include "rf_dagutils.h"
44 #include "rf_dagfuncs.h"
45 #include "rf_debugMem.h"
46 #include "rf_general.h"
47 #include "rf_dagffrd.h"
48
49 /******************************************************************************
50 *
51 * General comments on DAG creation:
52 *
53 * All DAGs in this file use roll-away error recovery. Each DAG has a single
54 * commit node, usually called "Cmt." If an error occurs before the Cmt node
55 * is reached, the execution engine will halt forward execution and work
56 * backward through the graph, executing the undo functions. Assuming that
57 * each node in the graph prior to the Cmt node are undoable and atomic - or -
58 * does not make changes to permanent state, the graph will fail atomically.
59 * If an error occurs after the Cmt node executes, the engine will roll-forward
60 * through the graph, blindly executing nodes until it reaches the end.
61 * If a graph reaches the end, it is assumed to have completed successfully.
62 *
63 * A graph has only 1 Cmt node.
64 *
65 */
66
67
68 /******************************************************************************
69 *
70 * The following wrappers map the standard DAG creation interface to the
71 * DAG creation routines. Additionally, these wrappers enable experimentation
72 * with new DAG structures by providing an extra level of indirection, allowing
73 * the DAG creation routines to be replaced at this single point.
74 */
75
76 void
rf_CreateFaultFreeReadDAG(RF_Raid_t * raidPtr,RF_AccessStripeMap_t * asmap,RF_DagHeader_t * dag_h,void * bp,RF_RaidAccessFlags_t flags,RF_AllocListElem_t * allocList)77 rf_CreateFaultFreeReadDAG(RF_Raid_t *raidPtr, RF_AccessStripeMap_t *asmap,
78 RF_DagHeader_t *dag_h, void *bp,
79 RF_RaidAccessFlags_t flags,
80 RF_AllocListElem_t *allocList)
81 {
82 rf_CreateNonredundantDAG(raidPtr, asmap, dag_h, bp, flags, allocList,
83 RF_IO_TYPE_READ);
84 }
85
86
87 /******************************************************************************
88 *
89 * DAG creation code begins here
90 */
91
92 /******************************************************************************
93 *
94 * creates a DAG to perform a nonredundant read or write of data within one
95 * stripe.
96 * For reads, this DAG is as follows:
97 *
98 * /---- read ----\
99 * Header -- Block ---- read ---- Commit -- Terminate
100 * \---- read ----/
101 *
102 * For writes, this DAG is as follows:
103 *
104 * /---- write ----\
105 * Header -- Commit ---- write ---- Block -- Terminate
106 * \---- write ----/
107 *
108 * There is one disk node per stripe unit accessed, and all disk nodes are in
109 * parallel.
110 *
111 * Tricky point here: The first disk node (read or write) is created
112 * normally. Subsequent disk nodes are created by copying the first one,
113 * and modifying a few params. The "succedents" and "antecedents" fields are
114 * _not_ re-created in each node, but rather left pointing to the same array
115 * that was malloc'd when the first node was created. Thus, it's essential
116 * that when this DAG is freed, the succedents and antecedents fields be freed
117 * in ONLY ONE of the read nodes. This does not apply to the "params" field
118 * because it is recreated for each READ node.
119 *
120 * Note that normal-priority accesses do not need to be tagged with their
121 * parity stripe ID, because they will never be promoted. Hence, I've
122 * commented-out the code to do this, and marked it with UNNEEDED.
123 *
124 *****************************************************************************/
125
126 void
rf_CreateNonredundantDAG(RF_Raid_t * raidPtr,RF_AccessStripeMap_t * asmap,RF_DagHeader_t * dag_h,void * bp,RF_RaidAccessFlags_t flags,RF_AllocListElem_t * allocList,RF_IoType_t type)127 rf_CreateNonredundantDAG(RF_Raid_t *raidPtr,
128 RF_AccessStripeMap_t *asmap, RF_DagHeader_t *dag_h, void *bp,
129 RF_RaidAccessFlags_t flags, RF_AllocListElem_t *allocList,
130 RF_IoType_t type)
131 {
132 RF_DagNode_t *diskNodes, *blockNode, *commitNode, *termNode;
133 RF_DagNode_t *tmpNode, *tmpdiskNode;
134 RF_PhysDiskAddr_t *pda = asmap->physInfo;
135 void (*doFunc) (RF_DagNode_t *), (*undoFunc) (RF_DagNode_t *);
136 int i, n;
137 const char *name;
138
139 n = asmap->numStripeUnitsAccessed;
140 dag_h->creator = "NonredundantDAG";
141
142 doFunc = rf_NullNodeFunc;
143 undoFunc = rf_NullNodeUndoFunc;
144 name = NULL;
145
146 RF_ASSERT(RF_IO_IS_R_OR_W(type));
147 switch (type) {
148 case RF_IO_TYPE_READ:
149 doFunc = rf_DiskReadFunc;
150 undoFunc = rf_DiskReadUndoFunc;
151 name = "R ";
152 #if RF_DEBUG_DAG
153 if (rf_dagDebug)
154 printf("[Creating non-redundant read DAG]\n");
155 #endif
156 break;
157 case RF_IO_TYPE_WRITE:
158 doFunc = rf_DiskWriteFunc;
159 undoFunc = rf_DiskWriteUndoFunc;
160 name = "W ";
161 #if RF_DEBUG_DAG
162 if (rf_dagDebug)
163 printf("[Creating non-redundant write DAG]\n");
164 #endif
165 break;
166 default:
167 RF_PANIC();
168 }
169
170 /*
171 * For reads, the dag can not commit until the block node is reached.
172 * for writes, the dag commits immediately.
173 */
174 dag_h->numCommitNodes = 1;
175 dag_h->numCommits = 0;
176 dag_h->numSuccedents = 1;
177
178 /*
179 * Node count:
180 * 1 block node
181 * n data reads (or writes)
182 * 1 commit node
183 * 1 terminator node
184 */
185 RF_ASSERT(n > 0);
186
187 for (i = 0; i < n; i++) {
188 tmpNode = rf_AllocDAGNode(raidPtr);
189 tmpNode->list_next = dag_h->nodes;
190 dag_h->nodes = tmpNode;
191 }
192 diskNodes = dag_h->nodes;
193
194 blockNode = rf_AllocDAGNode(raidPtr);
195 blockNode->list_next = dag_h->nodes;
196 dag_h->nodes = blockNode;
197
198 commitNode = rf_AllocDAGNode(raidPtr);
199 commitNode->list_next = dag_h->nodes;
200 dag_h->nodes = commitNode;
201
202 termNode = rf_AllocDAGNode(raidPtr);
203 termNode->list_next = dag_h->nodes;
204 dag_h->nodes = termNode;
205
206 /* initialize nodes */
207 switch (type) {
208 case RF_IO_TYPE_READ:
209 rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
210 NULL, n, 0, 0, 0, dag_h, "Nil", allocList);
211 rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
212 NULL, 1, n, 0, 0, dag_h, "Cmt", allocList);
213 rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc,
214 NULL, 0, 1, 0, 0, dag_h, "Trm", allocList);
215 break;
216 case RF_IO_TYPE_WRITE:
217 rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
218 NULL, 1, 0, 0, 0, dag_h, "Nil", allocList);
219 rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc, rf_NullNodeUndoFunc,
220 NULL, n, 1, 0, 0, dag_h, "Cmt", allocList);
221 rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc, rf_TerminateUndoFunc,
222 NULL, 0, n, 0, 0, dag_h, "Trm", allocList);
223 break;
224 default:
225 RF_PANIC();
226 }
227
228 tmpdiskNode = diskNodes;
229 for (i = 0; i < n; i++) {
230 RF_ASSERT(pda != NULL);
231 rf_InitNode(tmpdiskNode, rf_wait, RF_FALSE, doFunc, undoFunc, rf_GenericWakeupFunc,
232 1, 1, 4, 0, dag_h, name, allocList);
233 tmpdiskNode->params[0].p = pda;
234 tmpdiskNode->params[1].p = pda->bufPtr;
235 /* parity stripe id is not necessary */
236 tmpdiskNode->params[2].v = 0;
237 tmpdiskNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0);
238 pda = pda->next;
239 tmpdiskNode = tmpdiskNode->list_next;
240 }
241
242 /*
243 * Connect nodes.
244 */
245
246 /* connect hdr to block node */
247 RF_ASSERT(blockNode->numAntecedents == 0);
248 dag_h->succedents[0] = blockNode;
249
250 if (type == RF_IO_TYPE_READ) {
251 /* connecting a nonredundant read DAG */
252 RF_ASSERT(blockNode->numSuccedents == n);
253 RF_ASSERT(commitNode->numAntecedents == n);
254 tmpdiskNode = diskNodes;
255 for (i = 0; i < n; i++) {
256 /* connect block node to each read node */
257 RF_ASSERT(tmpdiskNode->numAntecedents == 1);
258 blockNode->succedents[i] = tmpdiskNode;
259 tmpdiskNode->antecedents[0] = blockNode;
260 tmpdiskNode->antType[0] = rf_control;
261
262 /* connect each read node to the commit node */
263 RF_ASSERT(tmpdiskNode->numSuccedents == 1);
264 tmpdiskNode->succedents[0] = commitNode;
265 commitNode->antecedents[i] = tmpdiskNode;
266 commitNode->antType[i] = rf_control;
267 tmpdiskNode = tmpdiskNode->list_next;
268 }
269 /* connect the commit node to the term node */
270 RF_ASSERT(commitNode->numSuccedents == 1);
271 RF_ASSERT(termNode->numAntecedents == 1);
272 RF_ASSERT(termNode->numSuccedents == 0);
273 commitNode->succedents[0] = termNode;
274 termNode->antecedents[0] = commitNode;
275 termNode->antType[0] = rf_control;
276 } else {
277 /* connecting a nonredundant write DAG */
278 /* connect the block node to the commit node */
279 RF_ASSERT(blockNode->numSuccedents == 1);
280 RF_ASSERT(commitNode->numAntecedents == 1);
281 blockNode->succedents[0] = commitNode;
282 commitNode->antecedents[0] = blockNode;
283 commitNode->antType[0] = rf_control;
284
285 RF_ASSERT(commitNode->numSuccedents == n);
286 RF_ASSERT(termNode->numAntecedents == n);
287 RF_ASSERT(termNode->numSuccedents == 0);
288 tmpdiskNode = diskNodes;
289 for (i = 0; i < n; i++) {
290 /* connect the commit node to each write node */
291 RF_ASSERT(tmpdiskNode->numAntecedents == 1);
292 commitNode->succedents[i] = tmpdiskNode;
293 tmpdiskNode->antecedents[0] = commitNode;
294 tmpdiskNode->antType[0] = rf_control;
295
296 /* connect each write node to the term node */
297 RF_ASSERT(tmpdiskNode->numSuccedents == 1);
298 tmpdiskNode->succedents[0] = termNode;
299 termNode->antecedents[i] = tmpdiskNode;
300 termNode->antType[i] = rf_control;
301 tmpdiskNode = tmpdiskNode->list_next;
302 }
303 }
304 }
305 /******************************************************************************
306 * Create a fault-free read DAG for RAID level 1
307 *
308 * Hdr -> Nil -> Rmir -> Cmt -> Trm
309 *
310 * The "Rmir" node schedules a read from the disk in the mirror pair with the
311 * shortest disk queue. the proper queue is selected at Rmir execution. this
312 * deferred mapping is unlike other archs in RAIDframe which generally fix
313 * mapping at DAG creation time.
314 *
315 * Parameters: raidPtr - description of the physical array
316 * asmap - logical & physical addresses for this access
317 * bp - buffer ptr (for holding read data)
318 * flags - general flags (e.g. disk locking)
319 * allocList - list of memory allocated in DAG creation
320 *****************************************************************************/
321
322 static void
CreateMirrorReadDAG(RF_Raid_t * raidPtr,RF_AccessStripeMap_t * asmap,RF_DagHeader_t * dag_h,void * bp,RF_RaidAccessFlags_t flags,RF_AllocListElem_t * allocList,void (* readfunc)(RF_DagNode_t * node))323 CreateMirrorReadDAG(RF_Raid_t *raidPtr, RF_AccessStripeMap_t *asmap,
324 RF_DagHeader_t *dag_h, void *bp,
325 RF_RaidAccessFlags_t flags, RF_AllocListElem_t *allocList,
326 void (*readfunc) (RF_DagNode_t * node))
327 {
328 RF_DagNode_t *readNodes, *blockNode, *commitNode, *termNode;
329 RF_DagNode_t *tmpNode, *tmpreadNode;
330 RF_PhysDiskAddr_t *data_pda = asmap->physInfo;
331 RF_PhysDiskAddr_t *parity_pda = asmap->parityInfo;
332 int i, n;
333
334 n = asmap->numStripeUnitsAccessed;
335 dag_h->creator = "RaidOneReadDAG";
336 #if RF_DEBUG_DAG
337 if (rf_dagDebug) {
338 printf("[Creating RAID level 1 read DAG]\n");
339 }
340 #endif
341 /*
342 * This dag can not commit until the commit node is reached
343 * errors prior to the commit point imply the dag has failed.
344 */
345 dag_h->numCommitNodes = 1;
346 dag_h->numCommits = 0;
347 dag_h->numSuccedents = 1;
348
349 /*
350 * Node count:
351 * n data reads
352 * 1 block node
353 * 1 commit node
354 * 1 terminator node
355 */
356 RF_ASSERT(n > 0);
357
358 for (i = 0; i < n; i++) {
359 tmpNode = rf_AllocDAGNode(raidPtr);
360 tmpNode->list_next = dag_h->nodes;
361 dag_h->nodes = tmpNode;
362 }
363 readNodes = dag_h->nodes;
364
365 blockNode = rf_AllocDAGNode(raidPtr);
366 blockNode->list_next = dag_h->nodes;
367 dag_h->nodes = blockNode;
368
369 commitNode = rf_AllocDAGNode(raidPtr);
370 commitNode->list_next = dag_h->nodes;
371 dag_h->nodes = commitNode;
372
373 termNode = rf_AllocDAGNode(raidPtr);
374 termNode->list_next = dag_h->nodes;
375 dag_h->nodes = termNode;
376
377 /* initialize nodes */
378 rf_InitNode(blockNode, rf_wait, RF_FALSE, rf_NullNodeFunc,
379 rf_NullNodeUndoFunc, NULL, n, 0, 0, 0, dag_h, "Nil", allocList);
380 rf_InitNode(commitNode, rf_wait, RF_TRUE, rf_NullNodeFunc,
381 rf_NullNodeUndoFunc, NULL, 1, n, 0, 0, dag_h, "Cmt", allocList);
382 rf_InitNode(termNode, rf_wait, RF_FALSE, rf_TerminateFunc,
383 rf_TerminateUndoFunc, NULL, 0, 1, 0, 0, dag_h, "Trm", allocList);
384
385 tmpreadNode = readNodes;
386 for (i = 0; i < n; i++) {
387 RF_ASSERT(data_pda != NULL);
388 RF_ASSERT(parity_pda != NULL);
389 rf_InitNode(tmpreadNode, rf_wait, RF_FALSE, readfunc,
390 rf_DiskReadMirrorUndoFunc, rf_GenericWakeupFunc, 1, 1, 5, 0, dag_h,
391 "Rmir", allocList);
392 tmpreadNode->params[0].p = data_pda;
393 tmpreadNode->params[1].p = data_pda->bufPtr;
394 /* parity stripe id is not necessary */
395 tmpreadNode->params[2].p = 0;
396 tmpreadNode->params[3].v = RF_CREATE_PARAM3(RF_IO_NORMAL_PRIORITY, 0);
397 tmpreadNode->params[4].p = parity_pda;
398 data_pda = data_pda->next;
399 parity_pda = parity_pda->next;
400 tmpreadNode = tmpreadNode->list_next;
401 }
402
403 /*
404 * Connect nodes
405 */
406
407 /* connect hdr to block node */
408 RF_ASSERT(blockNode->numAntecedents == 0);
409 dag_h->succedents[0] = blockNode;
410
411 /* connect block node to read nodes */
412 RF_ASSERT(blockNode->numSuccedents == n);
413 tmpreadNode = readNodes;
414 for (i = 0; i < n; i++) {
415 RF_ASSERT(tmpreadNode->numAntecedents == 1);
416 blockNode->succedents[i] = tmpreadNode;
417 tmpreadNode->antecedents[0] = blockNode;
418 tmpreadNode->antType[0] = rf_control;
419 tmpreadNode = tmpreadNode->list_next;
420 }
421
422 /* connect read nodes to commit node */
423 RF_ASSERT(commitNode->numAntecedents == n);
424 tmpreadNode = readNodes;
425 for (i = 0; i < n; i++) {
426 RF_ASSERT(tmpreadNode->numSuccedents == 1);
427 tmpreadNode->succedents[0] = commitNode;
428 commitNode->antecedents[i] = tmpreadNode;
429 commitNode->antType[i] = rf_control;
430 tmpreadNode = tmpreadNode->list_next;
431 }
432
433 /* connect commit node to term node */
434 RF_ASSERT(commitNode->numSuccedents == 1);
435 RF_ASSERT(termNode->numAntecedents == 1);
436 RF_ASSERT(termNode->numSuccedents == 0);
437 commitNode->succedents[0] = termNode;
438 termNode->antecedents[0] = commitNode;
439 termNode->antType[0] = rf_control;
440 }
441
442 void
rf_CreateMirrorIdleReadDAG(RF_Raid_t * raidPtr,RF_AccessStripeMap_t * asmap,RF_DagHeader_t * dag_h,void * bp,RF_RaidAccessFlags_t flags,RF_AllocListElem_t * allocList)443 rf_CreateMirrorIdleReadDAG(
444 RF_Raid_t * raidPtr,
445 RF_AccessStripeMap_t * asmap,
446 RF_DagHeader_t * dag_h,
447 void *bp,
448 RF_RaidAccessFlags_t flags,
449 RF_AllocListElem_t * allocList)
450 {
451 CreateMirrorReadDAG(raidPtr, asmap, dag_h, bp, flags, allocList,
452 rf_DiskReadMirrorIdleFunc);
453 }
454
455 #if (RF_INCLUDE_CHAINDECLUSTER > 0) || (RF_INCLUDE_INTERDECLUSTER > 0)
456
457 void
rf_CreateMirrorPartitionReadDAG(RF_Raid_t * raidPtr,RF_AccessStripeMap_t * asmap,RF_DagHeader_t * dag_h,void * bp,RF_RaidAccessFlags_t flags,RF_AllocListElem_t * allocList)458 rf_CreateMirrorPartitionReadDAG(RF_Raid_t *raidPtr,
459 RF_AccessStripeMap_t *asmap,
460 RF_DagHeader_t *dag_h, void *bp,
461 RF_RaidAccessFlags_t flags,
462 RF_AllocListElem_t *allocList)
463 {
464 CreateMirrorReadDAG(raidPtr, asmap, dag_h, bp, flags, allocList,
465 rf_DiskReadMirrorPartitionFunc);
466 }
467 #endif
468