1 /* $NetBSD: rf_aselect.c,v 1.31 2022/03/20 19:26:27 andvar 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 */
28
29 /*****************************************************************************
30 *
31 * aselect.c -- algorithm selection code
32 *
33 *****************************************************************************/
34
35 #include <sys/cdefs.h>
36 __KERNEL_RCSID(0, "$NetBSD: rf_aselect.c,v 1.31 2022/03/20 19:26:27 andvar Exp $");
37
38 #include <dev/raidframe/raidframevar.h>
39
40 #include "rf_archs.h"
41 #include "rf_raid.h"
42 #include "rf_dag.h"
43 #include "rf_dagutils.h"
44 #include "rf_dagfuncs.h"
45 #include "rf_general.h"
46 #include "rf_desc.h"
47 #include "rf_map.h"
48
49 static void InitHdrNode(RF_DagHeader_t **, RF_Raid_t *, RF_RaidAccessDesc_t *);
50 int rf_SelectAlgorithm(RF_RaidAccessDesc_t *, RF_RaidAccessFlags_t);
51
52 /******************************************************************************
53 *
54 * Create and Initialize a dag header and termination node
55 *
56 *****************************************************************************/
57 static void
InitHdrNode(RF_DagHeader_t ** hdr,RF_Raid_t * raidPtr,RF_RaidAccessDesc_t * desc)58 InitHdrNode(RF_DagHeader_t **hdr, RF_Raid_t *raidPtr, RF_RaidAccessDesc_t *desc)
59 {
60 /* create and initialize dag hdr */
61 *hdr = rf_AllocDAGHeader(raidPtr);
62 rf_MakeAllocList((*hdr)->allocList);
63 (*hdr)->status = rf_enable;
64 (*hdr)->numSuccedents = 0;
65 (*hdr)->nodes = NULL;
66 (*hdr)->raidPtr = raidPtr;
67 (*hdr)->next = NULL;
68 (*hdr)->desc = desc;
69 }
70
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 *****************************************************************************/
102
103 int
rf_SelectAlgorithm(RF_RaidAccessDesc_t * desc,RF_RaidAccessFlags_t flags)104 rf_SelectAlgorithm(RF_RaidAccessDesc_t *desc, RF_RaidAccessFlags_t flags)
105 {
106 RF_AccessStripeMapHeader_t *asm_h = desc->asmap;
107 RF_IoType_t type = desc->type;
108 RF_Raid_t *raidPtr = desc->raidPtr;
109 void *bp = desc->bp;
110
111 RF_AccessStripeMap_t *asmap = asm_h->stripeMap;
112 RF_AccessStripeMap_t *asm_p;
113 RF_DagHeader_t *dag_h = NULL, *tempdag_h, *lastdag_h;
114 RF_DagList_t *dagList, *dagListend;
115 int i, j, k;
116 RF_FuncList_t *stripeFuncsList, *stripeFuncs, *stripeFuncsEnd, *temp;
117 RF_AccessStripeMap_t *asm_up, *asm_bp;
118 RF_AccessStripeMapHeader_t *endASMList;
119 RF_ASMHeaderListElem_t *asmhle, *tmpasmhle;
120 RF_VoidFunctionPointerListElem_t *vfple, *tmpvfple;
121 RF_FailedStripe_t *failed_stripes_list, *failed_stripes_list_end;
122 RF_FailedStripe_t *tmpfailed_stripe, *failed_stripe = NULL;
123 RF_ASMHeaderListElem_t *failed_stripes_asmh_u_end = NULL;
124 RF_ASMHeaderListElem_t *failed_stripes_asmh_b_end = NULL;
125 RF_VoidFunctionPointerListElem_t *failed_stripes_vfple_end = NULL;
126 RF_VoidFunctionPointerListElem_t *failed_stripes_bvfple_end = NULL;
127 RF_VoidFuncPtr uFunc;
128 RF_VoidFuncPtr bFunc;
129 int numStripesBailed = 0, cantCreateDAGs = RF_FALSE;
130 int numStripeUnitsBailed = 0;
131 int stripeNum, stripeUnitNum, numBlockDags = 0;
132 RF_StripeNum_t numStripeUnits;
133 RF_SectorNum_t numBlocks;
134 RF_RaidAddr_t address;
135 int length;
136 RF_PhysDiskAddr_t *physPtr;
137 void *buffer;
138
139 lastdag_h = NULL;
140
141 stripeFuncsList = NULL;
142 stripeFuncsEnd = NULL;
143
144 failed_stripes_list = NULL;
145 failed_stripes_list_end = NULL;
146
147 /* walk through the asm list once collecting information */
148 /* attempt to find a single creation function for each stripe */
149 desc->numStripes = 0;
150 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
151 desc->numStripes++;
152 stripeFuncs = rf_AllocFuncList(raidPtr);
153
154 if (stripeFuncsEnd == NULL) {
155 stripeFuncsList = stripeFuncs;
156 } else {
157 stripeFuncsEnd->next = stripeFuncs;
158 }
159 stripeFuncsEnd = stripeFuncs;
160
161 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_p, &(stripeFuncs->fp));
162 /* check to see if we found a creation func for this stripe */
163 if (stripeFuncs->fp == NULL) {
164 /* could not find creation function for entire stripe
165 * so, let's see if we can find one for each stripe
166 * unit in the stripe */
167
168 /* create a failed stripe structure to attempt to deal with the failure */
169 failed_stripe = rf_AllocFailedStripeStruct(raidPtr);
170 if (failed_stripes_list == NULL) {
171 failed_stripes_list = failed_stripe;
172 failed_stripes_list_end = failed_stripe;
173 } else {
174 failed_stripes_list_end->next = failed_stripe;
175 failed_stripes_list_end = failed_stripe;
176 }
177
178 /* create an array of creation funcs (called
179 * stripeFuncs) for this stripe */
180 numStripeUnits = asm_p->numStripeUnitsAccessed;
181
182 /* lookup array of stripeUnitFuncs for this stripe */
183 failed_stripes_asmh_u_end = NULL;
184 failed_stripes_vfple_end = NULL;
185 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) {
186 /* remap for series of single stripe-unit
187 * accesses */
188 address = physPtr->raidAddress;
189 length = physPtr->numSector;
190 buffer = physPtr->bufPtr;
191
192 asmhle = rf_AllocASMHeaderListElem(raidPtr);
193 if (failed_stripe->asmh_u == NULL) {
194 failed_stripe->asmh_u = asmhle; /* we're the head... */
195 failed_stripes_asmh_u_end = asmhle; /* and the tail */
196 } else {
197 /* tack us onto the end of the list */
198 failed_stripes_asmh_u_end->next = asmhle;
199 failed_stripes_asmh_u_end = asmhle;
200 }
201
202
203 asmhle->asmh = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP);
204 asm_up = asmhle->asmh->stripeMap;
205
206 vfple = rf_AllocVFPListElem(raidPtr);
207 if (failed_stripe->vfple == NULL) {
208 failed_stripe->vfple = vfple;
209 failed_stripes_vfple_end = vfple;
210 } else {
211 failed_stripes_vfple_end->next = vfple;
212 failed_stripes_vfple_end = vfple;
213 }
214
215 /* get the creation func for this stripe unit */
216 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_up, &(vfple->fn));
217
218 /* check to see if we found a creation func
219 * for this stripe unit */
220
221 if (vfple->fn == NULL) {
222 /* could not find creation function
223 * for stripe unit so, let's see if we
224 * can find one for each block in the
225 * stripe unit */
226
227 numBlocks = physPtr->numSector;
228 numBlockDags += numBlocks;
229
230 /* lookup array of blockFuncs for this
231 * stripe unit */
232 for (k = 0; k < numBlocks; k++) {
233 /* remap for series of single
234 * stripe-unit accesses */
235 address = physPtr->raidAddress + k;
236 length = 1;
237 buffer = (char *)physPtr->bufPtr + (k * (1 << raidPtr->logBytesPerSector));
238
239 asmhle = rf_AllocASMHeaderListElem(raidPtr);
240 if (failed_stripe->asmh_b == NULL) {
241 failed_stripe->asmh_b = asmhle;
242 failed_stripes_asmh_b_end = asmhle;
243 } else {
244 failed_stripes_asmh_b_end->next = asmhle;
245 failed_stripes_asmh_b_end = asmhle;
246 }
247
248 asmhle->asmh = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP);
249 asm_bp = asmhle->asmh->stripeMap;
250
251 vfple = rf_AllocVFPListElem(raidPtr);
252 if (failed_stripe->bvfple == NULL) {
253 failed_stripe->bvfple = vfple;
254 failed_stripes_bvfple_end = vfple;
255 } else {
256 failed_stripes_bvfple_end->next = vfple;
257 failed_stripes_bvfple_end = vfple;
258 }
259 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_bp, &(vfple->fn));
260
261 /* check to see if we found a
262 * creation func for this
263 * stripe unit */
264
265 if (vfple->fn == NULL)
266 cantCreateDAGs = RF_TRUE;
267 }
268 numStripeUnitsBailed++;
269 }
270 }
271 RF_ASSERT(j == numStripeUnits);
272 numStripesBailed++;
273 }
274 }
275
276 if (cantCreateDAGs) {
277 /* free memory and punt */
278 if (numStripesBailed > 0) {
279 stripeNum = 0;
280 stripeFuncs = stripeFuncsList;
281 failed_stripe = failed_stripes_list;
282 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
283 if (stripeFuncs->fp == NULL) {
284
285 asmhle = failed_stripe->asmh_u;
286 while (asmhle) {
287 tmpasmhle= asmhle;
288 asmhle = tmpasmhle->next;
289 rf_FreeAccessStripeMap(raidPtr, tmpasmhle->asmh);
290 rf_FreeASMHeaderListElem(raidPtr, tmpasmhle);
291 }
292
293 asmhle = failed_stripe->asmh_b;
294 while (asmhle) {
295 tmpasmhle= asmhle;
296 asmhle = tmpasmhle->next;
297 rf_FreeAccessStripeMap(raidPtr, tmpasmhle->asmh);
298 rf_FreeASMHeaderListElem(raidPtr, tmpasmhle);
299 }
300
301 vfple = failed_stripe->vfple;
302 while (vfple) {
303 tmpvfple = vfple;
304 vfple = tmpvfple->next;
305 rf_FreeVFPListElem(raidPtr, tmpvfple);
306 }
307
308 vfple = failed_stripe->bvfple;
309 while (vfple) {
310 tmpvfple = vfple;
311 vfple = tmpvfple->next;
312 rf_FreeVFPListElem(raidPtr, tmpvfple);
313 }
314
315 stripeNum++;
316 /* only move to the next failed stripe slot if the current one was used */
317 tmpfailed_stripe = failed_stripe;
318 failed_stripe = failed_stripe->next;
319 rf_FreeFailedStripeStruct(raidPtr, tmpfailed_stripe);
320 }
321 stripeFuncs = stripeFuncs->next;
322 }
323 RF_ASSERT(stripeNum == numStripesBailed);
324 }
325 while (stripeFuncsList != NULL) {
326 temp = stripeFuncsList;
327 stripeFuncsList = stripeFuncsList->next;
328 rf_FreeFuncList(raidPtr, temp);
329 }
330 desc->numStripes = 0;
331 return (1);
332 } else {
333 /* begin dag creation */
334 stripeNum = 0;
335 stripeUnitNum = 0;
336
337 /* create a list of dagLists and fill them in */
338
339 dagListend = NULL;
340
341 stripeFuncs = stripeFuncsList;
342 failed_stripe = failed_stripes_list;
343 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
344 /* grab dag header for this stripe */
345 dag_h = NULL;
346
347 dagList = rf_AllocDAGList(raidPtr);
348
349 /* always tack the new dagList onto the end of the list... */
350 if (dagListend == NULL) {
351 desc->dagList = dagList;
352 } else {
353 dagListend->next = dagList;
354 }
355 dagListend = dagList;
356
357 dagList->desc = desc;
358
359 if (stripeFuncs->fp == NULL) {
360 /* use bailout functions for this stripe */
361 asmhle = failed_stripe->asmh_u;
362 vfple = failed_stripe->vfple;
363 /* the following two may contain asm headers and
364 block function pointers for multiple asm within
365 this access. We initialize tmpasmhle and tmpvfple
366 here in order to allow for that, and for correct
367 operation below */
368 tmpasmhle = failed_stripe->asmh_b;
369 tmpvfple = failed_stripe->bvfple;
370 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) {
371 uFunc = vfple->fn; /* stripeUnitFuncs[stripeNum][j]; */
372 if (uFunc == NULL) {
373 /* use bailout functions for
374 * this stripe unit */
375 for (k = 0; k < physPtr->numSector; k++) {
376 /* create a dag for
377 * this block */
378 InitHdrNode(&tempdag_h, raidPtr, desc);
379 dagList->numDags++;
380 if (dag_h == NULL) {
381 dag_h = tempdag_h;
382 } else {
383 lastdag_h->next = tempdag_h;
384 }
385 lastdag_h = tempdag_h;
386
387 bFunc = tmpvfple->fn; /* blockFuncs[stripeUnitNum][k]; */
388 RF_ASSERT(bFunc);
389 asm_bp = tmpasmhle->asmh->stripeMap; /* asmh_b[stripeUnitNum][k]->stripeMap; */
390 (*bFunc) (raidPtr, asm_bp, tempdag_h, bp, flags, tempdag_h->allocList);
391
392 tmpasmhle = tmpasmhle->next;
393 tmpvfple = tmpvfple->next;
394 }
395 stripeUnitNum++;
396 } else {
397 /* create a dag for this unit */
398 InitHdrNode(&tempdag_h, raidPtr, desc);
399 dagList->numDags++;
400 if (dag_h == NULL) {
401 dag_h = tempdag_h;
402 } else {
403 lastdag_h->next = tempdag_h;
404 }
405 lastdag_h = tempdag_h;
406
407 asm_up = asmhle->asmh->stripeMap; /* asmh_u[stripeNum][j]->stripeMap; */
408 (*uFunc) (raidPtr, asm_up, tempdag_h, bp, flags, tempdag_h->allocList);
409 }
410 asmhle = asmhle->next;
411 vfple = vfple->next;
412 }
413 RF_ASSERT(j == asm_p->numStripeUnitsAccessed);
414 /* merge linked bailout dag to existing dag
415 * collection */
416 stripeNum++;
417 failed_stripe = failed_stripe->next;
418 } else {
419 /* Create a dag for this parity stripe */
420 InitHdrNode(&tempdag_h, raidPtr, desc);
421 dagList->numDags++;
422 dag_h = tempdag_h;
423 lastdag_h = tempdag_h;
424
425 (stripeFuncs->fp) (raidPtr, asm_p, tempdag_h, bp, flags, tempdag_h->allocList);
426 }
427 dagList->dags = dag_h;
428 stripeFuncs = stripeFuncs->next;
429 }
430 RF_ASSERT(i == desc->numStripes);
431
432 /* free memory */
433 if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) {
434 stripeNum = 0;
435 stripeUnitNum = 0;
436 /* walk through io, stripe by stripe */
437 /* here we build up dag_h->asmList for this dag...
438 we need all of these asm's to do the IO, and
439 want them in a convenient place for freeing at a
440 later time */
441 stripeFuncs = stripeFuncsList;
442 failed_stripe = failed_stripes_list;
443 dagList = desc->dagList;
444
445 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
446
447 dag_h = dagList->dags;
448 if (dag_h->asmList) {
449 endASMList = dag_h->asmList;
450 while (endASMList->next)
451 endASMList = endASMList->next;
452 } else
453 endASMList = NULL;
454
455 if (stripeFuncs->fp == NULL) {
456 numStripeUnits = asm_p->numStripeUnitsAccessed;
457 /* walk through stripe, stripe unit by
458 * stripe unit */
459 asmhle = failed_stripe->asmh_u;
460 vfple = failed_stripe->vfple;
461 /* this contains all of the asm headers for block funcs,
462 so we have to initialize this here instead of below.*/
463 tmpasmhle = failed_stripe->asmh_b;
464 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) {
465 if (vfple->fn == NULL) {
466 numBlocks = physPtr->numSector;
467 /* walk through stripe
468 * unit, block by
469 * block */
470 for (k = 0; k < numBlocks; k++) {
471 if (dag_h->asmList == NULL) {
472 dag_h->asmList = tmpasmhle->asmh; /* asmh_b[stripeUnitNum][k];*/
473 endASMList = dag_h->asmList;
474 } else {
475 endASMList->next = tmpasmhle->asmh;
476 endASMList = endASMList->next;
477 }
478 tmpasmhle = tmpasmhle->next;
479 }
480 stripeUnitNum++;
481 }
482 if (dag_h->asmList == NULL) {
483 dag_h->asmList = asmhle->asmh;
484 endASMList = dag_h->asmList;
485 } else {
486 endASMList->next = asmhle->asmh;
487 endASMList = endASMList->next;
488 }
489 asmhle = asmhle->next;
490 vfple = vfple->next;
491 }
492 stripeNum++;
493 failed_stripe = failed_stripe->next;
494 }
495 dagList = dagList->next; /* need to move in stride with stripeFuncs */
496 stripeFuncs = stripeFuncs->next;
497 }
498 RF_ASSERT(stripeNum == numStripesBailed);
499 RF_ASSERT(stripeUnitNum == numStripeUnitsBailed);
500
501 failed_stripe = failed_stripes_list;
502 while (failed_stripe) {
503
504 asmhle = failed_stripe->asmh_u;
505 while (asmhle) {
506 tmpasmhle= asmhle;
507 asmhle = tmpasmhle->next;
508 rf_FreeASMHeaderListElem(raidPtr, tmpasmhle);
509 }
510
511 asmhle = failed_stripe->asmh_b;
512 while (asmhle) {
513 tmpasmhle= asmhle;
514 asmhle = tmpasmhle->next;
515 rf_FreeASMHeaderListElem(raidPtr, tmpasmhle);
516 }
517 vfple = failed_stripe->vfple;
518 while (vfple) {
519 tmpvfple = vfple;
520 vfple = tmpvfple->next;
521 rf_FreeVFPListElem(raidPtr, tmpvfple);
522 }
523
524 vfple = failed_stripe->bvfple;
525 while (vfple) {
526 tmpvfple = vfple;
527 vfple = tmpvfple->next;
528 rf_FreeVFPListElem(raidPtr, tmpvfple);
529 }
530
531 tmpfailed_stripe = failed_stripe;
532 failed_stripe = tmpfailed_stripe->next;
533 rf_FreeFailedStripeStruct(raidPtr, tmpfailed_stripe);
534 }
535 }
536 while (stripeFuncsList != NULL) {
537 temp = stripeFuncsList;
538 stripeFuncsList = stripeFuncsList->next;
539 rf_FreeFuncList(raidPtr, temp);
540 }
541 return (0);
542 }
543 }
544