1 /* $OpenBSD: rf_aselect.c,v 1.3 2002/12/16 07:01:03 tdeval Exp $ */
2 /* $NetBSD: rf_aselect.c,v 1.3 1999/02/05 00:06:06 oster Exp $ */
3
4 /*
5 * Copyright (c) 1995 Carnegie-Mellon University.
6 * All rights reserved.
7 *
8 * Author: Mark Holland, William V. Courtright II
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 * aselect.c -- algorithm selection code
34 *
35 *****************************************************************************/
36
37
38 #include "rf_archs.h"
39 #include "rf_types.h"
40 #include "rf_raid.h"
41 #include "rf_dag.h"
42 #include "rf_dagutils.h"
43 #include "rf_dagfuncs.h"
44 #include "rf_general.h"
45 #include "rf_desc.h"
46 #include "rf_map.h"
47
48 #if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
49 /* The function below is not used... so don't define it! */
50 #else
51 void rf_TransferDagMemory(RF_DagHeader_t *, RF_DagHeader_t *);
52 #endif
53
54 int rf_InitHdrNode(RF_DagHeader_t **, RF_Raid_t *, int);
55 void rf_UpdateNodeHdrPtr(RF_DagHeader_t *, RF_DagNode_t *);
56 int rf_SelectAlgorithm(RF_RaidAccessDesc_t *, RF_RaidAccessFlags_t);
57
58
59 /*****************************************************************************
60 *
61 * Create and Initialize a dag header and termination node.
62 *
63 *****************************************************************************/
64 int
65 rf_InitHdrNode(RF_DagHeader_t **hdr, RF_Raid_t *raidPtr, int memChunkEnable)
66 {
67 /* Create and initialize dag hdr. */
68 *hdr = rf_AllocDAGHeader();
69 rf_MakeAllocList((*hdr)->allocList);
70 if ((*hdr)->allocList == NULL) {
71 rf_FreeDAGHeader(*hdr);
72 return (ENOMEM);
73 }
74 (*hdr)->status = rf_enable;
75 (*hdr)->numSuccedents = 0;
76 (*hdr)->raidPtr = raidPtr;
77 (*hdr)->next = NULL;
78 return (0);
79 }
80
81
82 /*****************************************************************************
83 *
84 * Transfer allocation list and mem chunks from one dag to another.
85 *
86 *****************************************************************************/
87 #if (defined(__NetBSD__) || defined(__OpenBSD__)) && defined(_KERNEL)
88 /* The function below is not used... so don't define it! */
89 #else
90 void
91 rf_TransferDagMemory(RF_DagHeader_t *daga, RF_DagHeader_t *dagb)
92 {
93 RF_AccessStripeMapHeader_t *end;
94 RF_AllocListElem_t *p;
95 int i, memChunksXfrd = 0, xtraChunksXfrd = 0;
96
97 /* Transfer allocList from dagb to daga. */
98 for (p = dagb->allocList; p; p = p->next) {
99 for (i = 0; i < p->numPointers; i++) {
100 rf_AddToAllocList(daga->allocList, p->pointers[i],
101 p->sizes[i]);
102 p->pointers[i] = NULL;
103 p->sizes[i] = 0;
104 }
105 p->numPointers = 0;
106 }
107
108 /* Transfer chunks from dagb to daga. */
109 while ((memChunksXfrd + xtraChunksXfrd <
110 dagb->chunkIndex + dagb->xtraChunkIndex) &&
111 (daga->chunkIndex < RF_MAXCHUNKS)) {
112 /* Stuff chunks into daga's memChunk array. */
113 if (memChunksXfrd < dagb->chunkIndex) {
114 daga->memChunk[daga->chunkIndex++] =
115 dagb->memChunk[memChunksXfrd];
116 dagb->memChunk[memChunksXfrd++] = NULL;
117 } else {
118 daga->memChunk[daga->xtraChunkIndex++] =
119 dagb->xtraMemChunk[xtraChunksXfrd];
120 dagb->xtraMemChunk[xtraChunksXfrd++] = NULL;
121 }
122 }
123 /* Use escape hatch to hold excess chunks. */
124 while (memChunksXfrd + xtraChunksXfrd <
125 dagb->chunkIndex + dagb->xtraChunkIndex) {
126 if (memChunksXfrd < dagb->chunkIndex) {
127 daga->xtraMemChunk[daga->xtraChunkIndex++] =
128 dagb->memChunk[memChunksXfrd];
129 dagb->memChunk[memChunksXfrd++] = NULL;
130 } else {
131 daga->xtraMemChunk[daga->xtraChunkIndex++] =
132 dagb->xtraMemChunk[xtraChunksXfrd];
133 dagb->xtraMemChunk[xtraChunksXfrd++] = NULL;
134 }
135 }
136 RF_ASSERT((memChunksXfrd == dagb->chunkIndex) &&
137 (xtraChunksXfrd == dagb->xtraChunkIndex));
138 RF_ASSERT(daga->chunkIndex <= RF_MAXCHUNKS);
139 RF_ASSERT(daga->xtraChunkIndex <= daga->xtraChunkCnt);
140 dagb->chunkIndex = 0;
141 dagb->xtraChunkIndex = 0;
142
143 /* Transfer asmList from dagb to daga. */
144 if (dagb->asmList) {
145 if (daga->asmList) {
146 end = daga->asmList;
147 while (end->next)
148 end = end->next;
149 end->next = dagb->asmList;
150 } else
151 daga->asmList = dagb->asmList;
152 dagb->asmList = NULL;
153 }
154 }
155 #endif /* __NetBSD__ || __OpenBSD__ */
156
157
158 /*****************************************************************************
159 *
160 * Ensure that all node->dagHdr fields in a dag are consistent.
161 *
162 * IMPORTANT: This routine recursively searches all succedents of the node.
163 * If a succedent is encountered whose dagHdr ptr does not require adjusting,
164 * that node's succedents WILL NOT BE EXAMINED.
165 *
166 *****************************************************************************/
167 void
168 rf_UpdateNodeHdrPtr(RF_DagHeader_t *hdr, RF_DagNode_t *node)
169 {
170 int i;
171 RF_ASSERT(hdr != NULL && node != NULL);
172 for (i = 0; i < node->numSuccedents; i++)
173 if (node->succedents[i]->dagHdr != hdr)
174 rf_UpdateNodeHdrPtr(hdr, node->succedents[i]);
175 node->dagHdr = hdr;
176 }
177
178
179 /*****************************************************************************
180 *
181 * Create a DAG to do a read or write operation.
182 *
183 * Create an array of dagLists, one list per parity stripe.
184 * Return the lists in the array desc->dagArray.
185 *
186 * Normally, each list contains one dag for the entire stripe. In some
187 * tricky cases, we break this into multiple dags, either one per stripe
188 * unit or one per block (sector). When this occurs, these dags are returned
189 * as a linked list (dagList) which is executed sequentially (to preserve
190 * atomic parity updates in the stripe).
191 *
192 * Dags that operate on independent parity goups (stripes) are returned in
193 * independent dagLists (distinct elements in desc->dagArray) and may be
194 * executed concurrently.
195 *
196 * Finally, if the SelectionFunc fails to create a dag for a block, we punt
197 * and return 1.
198 *
199 * The above process is performed in two phases:
200 * 1) create an array(s) of creation functions (eg stripeFuncs)
201 * 2) create dags and concatenate/merge to form the final dag.
202 *
203 * Because dag's are basic blocks (single entry, single exit, unconditional
204 * control flow), we can add the following optimizations (future work):
205 * first-pass optimizer to allow max concurrency (need all data dependencies)
206 * second-pass optimizer to eliminate common subexpressions (need true
207 * data dependencies)
208 * third-pass optimizer to eliminate dead code (need true data dependencies)
209 *****************************************************************************/
210
211 #define MAXNSTRIPES 50
212
213 int
214 rf_SelectAlgorithm(RF_RaidAccessDesc_t *desc, RF_RaidAccessFlags_t flags)
215 {
216 RF_AccessStripeMapHeader_t *asm_h = desc->asmap;
217 RF_IoType_t type = desc->type;
218 RF_Raid_t *raidPtr = desc->raidPtr;
219 void *bp = desc->bp;
220
221 RF_AccessStripeMap_t *asmap = asm_h->stripeMap;
222 RF_AccessStripeMap_t *asm_p;
223 RF_DagHeader_t *dag_h = NULL, *tempdag_h, *lastdag_h;
224 int i, j, k;
225 RF_VoidFuncPtr *stripeFuncs, normalStripeFuncs[MAXNSTRIPES];
226 RF_AccessStripeMap_t *asm_up, *asm_bp;
227 RF_AccessStripeMapHeader_t ***asmh_u, *endASMList;
228 RF_AccessStripeMapHeader_t ***asmh_b;
229 RF_VoidFuncPtr **stripeUnitFuncs, uFunc;
230 RF_VoidFuncPtr **blockFuncs, bFunc;
231 int numStripesBailed = 0, cantCreateDAGs = RF_FALSE;
232 int numStripeUnitsBailed = 0;
233 int stripeNum, numUnitDags = 0, stripeUnitNum, numBlockDags = 0;
234 RF_StripeNum_t numStripeUnits;
235 RF_SectorNum_t numBlocks;
236 RF_RaidAddr_t address;
237 int length;
238 RF_PhysDiskAddr_t *physPtr;
239 caddr_t buffer;
240
241 lastdag_h = NULL;
242 asmh_u = asmh_b = NULL;
243 stripeUnitFuncs = NULL;
244 blockFuncs = NULL;
245
246 /*
247 * Get an array of dag-function creation pointers.
248 * Try to avoid calling malloc.
249 */
250 if (asm_h->numStripes <= MAXNSTRIPES)
251 stripeFuncs = normalStripeFuncs;
252 else
253 RF_Calloc(stripeFuncs, asm_h->numStripes,
254 sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr *));
255
256 /*
257 * Walk through the asm list once collecting information.
258 * Attempt to find a single creation function for each stripe.
259 */
260 desc->numStripes = 0;
261 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
262 desc->numStripes++;
263 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_p,
264 &stripeFuncs[i]);
265 /* Check to see if we found a creation func for this stripe. */
266 if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) {
267 /*
268 * Could not find creation function for entire stripe.
269 * So, let's see if we can find one for each stripe
270 * unit in the stripe.
271 */
272
273 if (numStripesBailed == 0) {
274 /*
275 * One stripe map header for each stripe we
276 * bail on.
277 */
278 RF_Malloc(asmh_u,
279 sizeof(RF_AccessStripeMapHeader_t **) *
280 asm_h->numStripes,
281 (RF_AccessStripeMapHeader_t ***));
282 /*
283 * Create an array of ptrs to arrays of
284 * stripeFuncs.
285 */
286 RF_Calloc(stripeUnitFuncs, asm_h->numStripes,
287 sizeof(RF_VoidFuncPtr),
288 (RF_VoidFuncPtr **));
289 }
290 /*
291 * Create an array of creation funcs (called
292 * stripeFuncs) for this stripe.
293 */
294 numStripeUnits = asm_p->numStripeUnitsAccessed;
295 RF_Calloc(stripeUnitFuncs[numStripesBailed],
296 numStripeUnits, sizeof(RF_VoidFuncPtr),
297 (RF_VoidFuncPtr *));
298 RF_Malloc(asmh_u[numStripesBailed], numStripeUnits *
299 sizeof(RF_AccessStripeMapHeader_t *),
300 (RF_AccessStripeMapHeader_t **));
301
302 /* Lookup array of stripeUnitFuncs for this stripe. */
303 for (j = 0, physPtr = asm_p->physInfo; physPtr;
304 physPtr = physPtr->next, j++) {
305 /*
306 * Remap for series of single stripe-unit
307 * accesses.
308 */
309 address = physPtr->raidAddress;
310 length = physPtr->numSector;
311 buffer = physPtr->bufPtr;
312
313 asmh_u[numStripesBailed][j] =
314 rf_MapAccess(raidPtr, address, length,
315 buffer, RF_DONT_REMAP);
316 asm_up = asmh_u[numStripesBailed][j]->stripeMap;
317
318 /*
319 * Get the creation func for this
320 * stripe unit.
321 */
322 (raidPtr->Layout.map->SelectionFunc) (raidPtr,
323 type, asm_up,
324 &(stripeUnitFuncs[numStripesBailed][j]));
325
326 /*
327 * Check to see if we found a creation func
328 * for this stripe unit.
329 */
330 if (stripeUnitFuncs[numStripesBailed][j] ==
331 (RF_VoidFuncPtr) NULL) {
332 /*
333 * Could not find creation function
334 * for stripe unit. So, let's see if
335 * we can find one for each block in
336 * the stripe unit.
337 */
338 if (numStripeUnitsBailed == 0) {
339 /*
340 * one stripe map header for
341 * each stripe unit we bail on.
342 */
343 RF_Malloc(asmh_b,
344 sizeof(RF_AccessStripeMapHeader_t **) *
345 asm_h->numStripes *
346 raidPtr->Layout.numDataCol,
347 (RF_AccessStripeMapHeader_t ***));
348 /*
349 * Create an array of ptrs to
350 * arrays of blockFuncs.
351 */
352 RF_Calloc(blockFuncs,
353 asm_h->numStripes *
354 raidPtr->Layout.numDataCol,
355 sizeof(RF_VoidFuncPtr),
356 (RF_VoidFuncPtr **));
357 }
358 /*
359 * Create an array of creation funcs
360 * (called blockFuncs) for this stripe
361 * unit.
362 */
363 numBlocks = physPtr->numSector;
364 numBlockDags += numBlocks;
365 RF_Calloc(
366 blockFuncs[numStripeUnitsBailed],
367 numBlocks, sizeof(RF_VoidFuncPtr),
368 (RF_VoidFuncPtr *));
369 RF_Malloc(asmh_b[numStripeUnitsBailed],
370 numBlocks *
371 sizeof(RF_AccessStripeMapHeader_t *),
372 (RF_AccessStripeMapHeader_t **));
373
374 /*
375 * Lookup array of blockFuncs for this
376 * stripe unit.
377 */
378 for (k = 0; k < numBlocks; k++) {
379 /*
380 * Remap for series of single
381 * stripe-unit accesses.
382 */
383 address = physPtr->raidAddress
384 + k;
385 length = 1;
386 buffer = physPtr->bufPtr +
387 (k * (1 <<
388 raidPtr->logBytesPerSector));
389
390 asmh_b[numStripeUnitsBailed][k]
391 = rf_MapAccess(raidPtr,
392 address, length, buffer,
393 RF_DONT_REMAP);
394 asm_bp =
395 asmh_b[numStripeUnitsBailed][k]->stripeMap;
396
397 /*
398 * Get the creation func for
399 * this stripe unit.
400 */
401 (raidPtr->Layout.map->
402 SelectionFunc) (raidPtr,
403 type, asm_bp,
404 &(blockFuncs[numStripeUnitsBailed][k]));
405
406 /*
407 * Check to see if we found a
408 * creation func for this
409 * stripe unit.
410 */
411 if (blockFuncs
412 [numStripeUnitsBailed][k]
413 == NULL)
414 cantCreateDAGs =
415 RF_TRUE;
416 }
417 numStripeUnitsBailed++;
418 } else {
419 numUnitDags++;
420 }
421 }
422 RF_ASSERT(j == numStripeUnits);
423 numStripesBailed++;
424 }
425 }
426
427 if (cantCreateDAGs) {
428 /* Free memory and punt. */
429 if (asm_h->numStripes > MAXNSTRIPES)
430 RF_Free(stripeFuncs, asm_h->numStripes *
431 sizeof(RF_VoidFuncPtr));
432 if (numStripesBailed > 0) {
433 stripeNum = 0;
434 for (i = 0, asm_p = asmap; asm_p;
435 asm_p = asm_p->next, i++)
436 if (stripeFuncs[i] == NULL) {
437 numStripeUnits =
438 asm_p->numStripeUnitsAccessed;
439 for (j = 0; j < numStripeUnits; j++)
440 rf_FreeAccessStripeMap(
441 asmh_u[stripeNum][j]);
442 RF_Free(asmh_u[stripeNum],
443 numStripeUnits *
444 sizeof(RF_AccessStripeMapHeader_t *));
445 RF_Free(stripeUnitFuncs[stripeNum],
446 numStripeUnits *
447 sizeof(RF_VoidFuncPtr));
448 stripeNum++;
449 }
450 RF_ASSERT(stripeNum == numStripesBailed);
451 RF_Free(stripeUnitFuncs, asm_h->numStripes *
452 sizeof(RF_VoidFuncPtr));
453 RF_Free(asmh_u, asm_h->numStripes *
454 sizeof(RF_AccessStripeMapHeader_t **));
455 }
456 return (1);
457 } else {
458 /* Begin dag creation. */
459 stripeNum = 0;
460 stripeUnitNum = 0;
461
462 /* Create an array of dagLists and fill them in. */
463 RF_CallocAndAdd(desc->dagArray, desc->numStripes,
464 sizeof(RF_DagList_t), (RF_DagList_t *), desc->cleanupList);
465
466 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) {
467 /* Grab dag header for this stripe. */
468 dag_h = NULL;
469 desc->dagArray[i].desc = desc;
470
471 if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) {
472 /* Use bailout functions for this stripe. */
473 for (j = 0, physPtr = asm_p->physInfo; physPtr;
474 physPtr = physPtr->next, j++) {
475 uFunc = stripeUnitFuncs[stripeNum][j];
476 if (uFunc == (RF_VoidFuncPtr) NULL) {
477 /*
478 * Use bailout functions for
479 * this stripe unit.
480 */
481 for (k = 0; k <
482 physPtr->numSector; k++) {
483 /*
484 * Create a dag for
485 * this block.
486 */
487 rf_InitHdrNode(
488 &tempdag_h,
489 raidPtr,
490 rf_useMemChunks);
491 desc->dagArray[i].
492 numDags++;
493 if (dag_h == NULL) {
494 dag_h =
495 tempdag_h;
496 } else {
497 lastdag_h->next
498 = tempdag_h;
499 }
500 lastdag_h = tempdag_h;
501
502 bFunc = blockFuncs
503 [stripeUnitNum][k];
504 RF_ASSERT(bFunc);
505 asm_bp = asmh_b
506 [stripeUnitNum][k]
507 ->stripeMap;
508 (*bFunc) (raidPtr,
509 asm_bp, tempdag_h,
510 bp, flags,
511 tempdag_h
512 ->allocList);
513 }
514 stripeUnitNum++;
515 } else {
516 /*
517 * Create a dag for this unit.
518 */
519 rf_InitHdrNode(&tempdag_h,
520 raidPtr, rf_useMemChunks);
521 desc->dagArray[i].numDags++;
522 if (dag_h == NULL) {
523 dag_h = tempdag_h;
524 } else {
525 lastdag_h->next =
526 tempdag_h;
527 }
528 lastdag_h = tempdag_h;
529
530 asm_up = asmh_u[stripeNum][j]
531 ->stripeMap;
532 (*uFunc) (raidPtr, asm_up,
533 tempdag_h, bp, flags,
534 tempdag_h->allocList);
535 }
536 }
537 RF_ASSERT(j == asm_p->numStripeUnitsAccessed);
538 /*
539 * Merge linked bailout dag to existing dag
540 * collection.
541 */
542 stripeNum++;
543 } else {
544 /* Create a dag for this parity stripe. */
545 rf_InitHdrNode(&tempdag_h, raidPtr,
546 rf_useMemChunks);
547 desc->dagArray[i].numDags++;
548 if (dag_h == NULL) {
549 dag_h = tempdag_h;
550 } else {
551 lastdag_h->next = tempdag_h;
552 }
553 lastdag_h = tempdag_h;
554
555 (stripeFuncs[i]) (raidPtr, asm_p, tempdag_h,
556 bp, flags, tempdag_h->allocList);
557 }
558 desc->dagArray[i].dags = dag_h;
559 }
560 RF_ASSERT(i == desc->numStripes);
561
562 /* Free memory. */
563 if (asm_h->numStripes > MAXNSTRIPES)
564 RF_Free(stripeFuncs, asm_h->numStripes *
565 sizeof(RF_VoidFuncPtr));
566 if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) {
567 stripeNum = 0;
568 stripeUnitNum = 0;
569 if (dag_h->asmList) {
570 endASMList = dag_h->asmList;
571 while (endASMList->next)
572 endASMList = endASMList->next;
573 } else
574 endASMList = NULL;
575 /* Walk through io, stripe by stripe. */
576 for (i = 0, asm_p = asmap; asm_p;
577 asm_p = asm_p->next, i++)
578 if (stripeFuncs[i] == NULL) {
579 numStripeUnits =
580 asm_p->numStripeUnitsAccessed;
581 /*
582 * Walk through stripe, stripe unit by
583 * stripe unit.
584 */
585 for (j = 0, physPtr = asm_p->physInfo;
586 physPtr;
587 physPtr = physPtr->next, j++) {
588 if (stripeUnitFuncs[stripeNum]
589 [j] == NULL) {
590 numBlocks =
591 physPtr->numSector;
592 /*
593 * Walk through stripe
594 * unit, block by
595 * block.
596 */
597 for (k = 0; k <
598 numBlocks; k++)
599 if (dag_h
600 ->asmList
601 == NULL) {
602 dag_h->asmList =
603 asmh_b[stripeUnitNum][k];
604 endASMList = dag_h->asmList;
605 } else {
606 endASMList->next =
607 asmh_b[stripeUnitNum][k];
608 endASMList = endASMList->next;
609 }
610 RF_Free(asmh_b
611 [stripeUnitNum], numBlocks *
612 sizeof(RF_AccessStripeMapHeader_t *));
613 RF_Free(blockFuncs
614 [stripeUnitNum], numBlocks *
615 sizeof(RF_VoidFuncPtr));
616 stripeUnitNum++;
617 }
618 if (dag_h->asmList == NULL) {
619 dag_h->asmList = asmh_u
620 [stripeNum][j];
621 endASMList = dag_h
622 ->asmList;
623 } else {
624 endASMList->next =
625 asmh_u[stripeNum]
626 [j];
627 endASMList = endASMList
628 ->next;
629 }
630 }
631 RF_Free(asmh_u[stripeNum],
632 numStripeUnits *
633 sizeof(
634 RF_AccessStripeMapHeader_t *));
635 RF_Free(stripeUnitFuncs[stripeNum],
636 numStripeUnits *
637 sizeof(RF_VoidFuncPtr));
638 stripeNum++;
639 }
640 RF_ASSERT(stripeNum == numStripesBailed);
641 RF_Free(stripeUnitFuncs, asm_h->numStripes *
642 sizeof(RF_VoidFuncPtr));
643 RF_Free(asmh_u, asm_h->numStripes *
644 sizeof(RF_AccessStripeMapHeader_t **));
645 if (numStripeUnitsBailed > 0) {
646 RF_ASSERT(stripeUnitNum ==
647 numStripeUnitsBailed);
648 RF_Free(blockFuncs, raidPtr->Layout.numDataCol
649 * asm_h->numStripes *
650 sizeof(RF_VoidFuncPtr));
651 RF_Free(asmh_b, raidPtr->Layout.numDataCol *
652 asm_h->numStripes *
653 sizeof(RF_AccessStripeMapHeader_t **));
654 }
655 }
656 return (0);
657 }
658 }