| blob | 51e9a5530f011a8e810e67f760efdb6aa8b29073 |
1 /* $NetBSD: rf_aselect.c,v 1.25 2007/03/04 06:02:36 christos Exp $ */
2 /*
3 * Copyright (c) 1995 Carnegie-Mellon University.
4 * All rights reserved.
5 *
6 * Author: Mark Holland, 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 */
29 /*****************************************************************************
30 *
31 * aselect.c -- algorithm selection code
32 *
33 *****************************************************************************/
35 #include <sys/cdefs.h>
38 #include <dev/raidframe/raidframevar.h>
52 /******************************************************************************
53 *
54 * Create and Initialiaze a dag header and termination node
55 *
56 *****************************************************************************/
57 static void
59 {
60 /* create and initialize dag hdr */
69 }
71 /******************************************************************************
72 *
73 * Create a DAG to do a read or write operation.
74 *
75 * create a list of dagLists, one list per parity stripe.
76 * return the lists in the desc->dagList (which is a list of lists).
77 *
78 * Normally, each list contains one dag for the entire stripe. In some
79 * tricky cases, we break this into multiple dags, either one per stripe
80 * unit or one per block (sector). When this occurs, these dags are returned
81 * as a linked list (dagList) which is executed sequentially (to preserve
82 * atomic parity updates in the stripe).
83 *
84 * dags which operate on independent parity goups (stripes) are returned in
85 * independent dagLists (distinct elements in desc->dagArray) and may be
86 * executed concurrently.
87 *
88 * Finally, if the SelectionFunc fails to create a dag for a block, we punt
89 * and return 1.
90 *
91 * The above process is performed in two phases:
92 * 1) create an array(s) of creation functions (eg stripeFuncs)
93 * 2) create dags and concatenate/merge to form the final dag.
94 *
95 * Because dag's are basic blocks (single entry, single exit, unconditional
96 * control flow, we can add the following optimizations (future work):
97 * first-pass optimizer to allow max concurrency (need all data dependencies)
98 * second-pass optimizer to eliminate common subexpressions (need true
99 * data dependencies)
100 * third-pass optimizer to eliminate dead code (need true data dependencies)
101 *****************************************************************************/
103 int
105 {
133 RF_StripeNum_t numStripeUnits;
134 RF_SectorNum_t numBlocks;
135 RF_RaidAddr_t address;
151 /* walk through the asm list once collecting information */
152 /* attempt to find a single creation function for each stripe */
162 }
166 /* check to see if we found a creation func for this stripe */
168 /* could not find creation function for entire stripe
169 * so, let's see if we can find one for each stripe
170 * unit in the stripe */
172 /* create a failed stripe structure to attempt to deal with the failure */
180 }
182 /* create an array of creation funcs (called
183 * stripeFuncs) for this stripe */
186 /* lookup array of stripeUnitFuncs for this stripe */
190 /* remap for series of single stripe-unit
191 * accesses */
201 /* tack us onto the end of the list */
204 }
217 }
219 /* get the creation func for this stripe unit */
222 /* check to see if we found a creation func
223 * for this stripe unit */
226 /* could not find creation function
227 * for stripe unit so, let's see if we
228 * can find one for each block in the
229 * stripe unit */
234 /* lookup array of blockFuncs for this
235 * stripe unit */
237 /* remap for series of single
238 * stripe-unit accesses */
250 }
262 }
265 /* check to see if we found a
266 * creation func for this
267 * stripe unit */
271 }
272 numStripeUnitsBailed++;
274 numUnitDags++;
275 }
276 }
278 numStripesBailed++;
279 }
280 }
283 /* free memory and punt */
297 }
305 }
312 }
319 }
321 stripeNum++;
322 /* only move to the next failed stripe slot if the current one was used */
326 }
328 }
330 }
335 }
339 /* begin dag creation */
343 /* create a list of dagLists and fill them in */
350 /* grab dag header for this stripe */
355 /* always tack the new dagList onto the end of the list... */
360 }
366 /* use bailout functions for this stripe */
369 /* the following two may contain asm headers and
370 block function pointers for multiple asm within
371 this access. We initialize tmpasmhle and tmpvfple
372 here in order to allow for that, and for correct
373 operation below */
379 /* use bailout functions for
380 * this stripe unit */
382 /* create a dag for
383 * this block */
390 }
400 }
401 stripeUnitNum++;
403 /* create a dag for this unit */
410 }
415 }
418 }
420 /* merge linked bailout dag to existing dag
421 * collection */
422 stripeNum++;
425 /* Create a dag for this parity stripe */
432 }
435 }
438 /* free memory */
442 /* walk through io, stripe by stripe */
443 /* here we build up dag_h->asmList for this dag...
444 we need all of these asm's to do the IO, and
445 want them in a convenient place for freeing at a
446 later time */
463 /* walk through stripe, stripe unit by
464 * stripe unit */
467 /* this contains all of the asm headers for block funcs,
468 so we have to initialize this here instead of below.*/
473 /* walk through stripe
474 * unit, block by
475 * block */
483 }
485 }
486 stripeUnitNum++;
487 }
494 }
497 }
498 stripeNum++;
500 }
503 }
515 }
522 }
528 }
535 }
540 }
541 }
546 }
548 }
549 }