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