1 /* $NetBSD: rf_aselect.c,v 1.26 2009/02/07 20:41:30 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.26 2009/02/07 20:41:30 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 int 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 ***asmh_u, *endASMList; 119 RF_AccessStripeMapHeader_t ***asmh_b; 120 RF_ASMHeaderListElem_t *asmhle, *tmpasmhle; 121 RF_VoidFunctionPointerListElem_t *vfple, *tmpvfple; 122 RF_FailedStripe_t *failed_stripes_list, *failed_stripes_list_end; 123 RF_FailedStripe_t *tmpfailed_stripe, *failed_stripe = NULL; 124 RF_ASMHeaderListElem_t *failed_stripes_asmh_u_end = NULL; 125 RF_ASMHeaderListElem_t *failed_stripes_asmh_b_end = NULL; 126 RF_VoidFunctionPointerListElem_t *failed_stripes_vfple_end = NULL; 127 RF_VoidFunctionPointerListElem_t *failed_stripes_bvfple_end = NULL; 128 RF_VoidFuncPtr **stripeUnitFuncs, uFunc; 129 RF_VoidFuncPtr **blockFuncs, bFunc; 130 int numStripesBailed = 0, cantCreateDAGs = RF_FALSE; 131 int numStripeUnitsBailed = 0; 132 int stripeNum, numUnitDags = 0, stripeUnitNum, numBlockDags = 0; 133 RF_StripeNum_t numStripeUnits; 134 RF_SectorNum_t numBlocks; 135 RF_RaidAddr_t address; 136 int length; 137 RF_PhysDiskAddr_t *physPtr; 138 void *buffer; 139 140 lastdag_h = NULL; 141 asmh_u = asmh_b = NULL; 142 stripeUnitFuncs = NULL; 143 blockFuncs = NULL; 144 145 stripeFuncsList = NULL; 146 stripeFuncsEnd = NULL; 147 148 failed_stripes_list = NULL; 149 failed_stripes_list_end = NULL; 150 151 /* walk through the asm list once collecting information */ 152 /* attempt to find a single creation function for each stripe */ 153 desc->numStripes = 0; 154 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 155 desc->numStripes++; 156 stripeFuncs = rf_AllocFuncList(); 157 158 if (stripeFuncsEnd == NULL) { 159 stripeFuncsList = stripeFuncs; 160 } else { 161 stripeFuncsEnd->next = stripeFuncs; 162 } 163 stripeFuncsEnd = stripeFuncs; 164 165 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_p, &(stripeFuncs->fp)); 166 /* check to see if we found a creation func for this stripe */ 167 if (stripeFuncs->fp == NULL) { 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 */ 171 172 /* create a failed stripe structure to attempt to deal with the failure */ 173 failed_stripe = rf_AllocFailedStripeStruct(); 174 if (failed_stripes_list == NULL) { 175 failed_stripes_list = failed_stripe; 176 failed_stripes_list_end = failed_stripe; 177 } else { 178 failed_stripes_list_end->next = failed_stripe; 179 failed_stripes_list_end = failed_stripe; 180 } 181 182 /* create an array of creation funcs (called 183 * stripeFuncs) for this stripe */ 184 numStripeUnits = asm_p->numStripeUnitsAccessed; 185 186 /* lookup array of stripeUnitFuncs for this stripe */ 187 failed_stripes_asmh_u_end = NULL; 188 failed_stripes_vfple_end = NULL; 189 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 190 /* remap for series of single stripe-unit 191 * accesses */ 192 address = physPtr->raidAddress; 193 length = physPtr->numSector; 194 buffer = physPtr->bufPtr; 195 196 asmhle = rf_AllocASMHeaderListElem(); 197 if (failed_stripe->asmh_u == NULL) { 198 failed_stripe->asmh_u = asmhle; /* we're the head... */ 199 failed_stripes_asmh_u_end = asmhle; /* and the tail */ 200 } else { 201 /* tack us onto the end of the list */ 202 failed_stripes_asmh_u_end->next = asmhle; 203 failed_stripes_asmh_u_end = asmhle; 204 } 205 206 207 asmhle->asmh = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP); 208 asm_up = asmhle->asmh->stripeMap; 209 210 vfple = rf_AllocVFPListElem(); 211 if (failed_stripe->vfple == NULL) { 212 failed_stripe->vfple = vfple; 213 failed_stripes_vfple_end = vfple; 214 } else { 215 failed_stripes_vfple_end->next = vfple; 216 failed_stripes_vfple_end = vfple; 217 } 218 219 /* get the creation func for this stripe unit */ 220 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_up, &(vfple->fn)); 221 222 /* check to see if we found a creation func 223 * for this stripe unit */ 224 225 if (vfple->fn == (RF_VoidFuncPtr) NULL) { 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 */ 230 231 numBlocks = physPtr->numSector; 232 numBlockDags += numBlocks; 233 234 /* lookup array of blockFuncs for this 235 * stripe unit */ 236 for (k = 0; k < numBlocks; k++) { 237 /* remap for series of single 238 * stripe-unit accesses */ 239 address = physPtr->raidAddress + k; 240 length = 1; 241 buffer = (char *)physPtr->bufPtr + (k * (1 << raidPtr->logBytesPerSector)); 242 243 asmhle = rf_AllocASMHeaderListElem(); 244 if (failed_stripe->asmh_b == NULL) { 245 failed_stripe->asmh_b = asmhle; 246 failed_stripes_asmh_b_end = asmhle; 247 } else { 248 failed_stripes_asmh_b_end->next = asmhle; 249 failed_stripes_asmh_b_end = asmhle; 250 } 251 252 asmhle->asmh = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP); 253 asm_bp = asmhle->asmh->stripeMap; 254 255 vfple = rf_AllocVFPListElem(); 256 if (failed_stripe->bvfple == NULL) { 257 failed_stripe->bvfple = vfple; 258 failed_stripes_bvfple_end = vfple; 259 } else { 260 failed_stripes_bvfple_end->next = vfple; 261 failed_stripes_bvfple_end = vfple; 262 } 263 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_bp, &(vfple->fn)); 264 265 /* check to see if we found a 266 * creation func for this 267 * stripe unit */ 268 269 if (vfple->fn == NULL) 270 cantCreateDAGs = RF_TRUE; 271 } 272 numStripeUnitsBailed++; 273 } else { 274 numUnitDags++; 275 } 276 } 277 RF_ASSERT(j == numStripeUnits); 278 numStripesBailed++; 279 } 280 } 281 282 if (cantCreateDAGs) { 283 /* free memory and punt */ 284 if (numStripesBailed > 0) { 285 stripeNum = 0; 286 stripeFuncs = stripeFuncsList; 287 failed_stripe = failed_stripes_list; 288 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 289 if (stripeFuncs->fp == NULL) { 290 291 asmhle = failed_stripe->asmh_u; 292 while (asmhle) { 293 tmpasmhle= asmhle; 294 asmhle = tmpasmhle->next; 295 rf_FreeAccessStripeMap(tmpasmhle->asmh); 296 rf_FreeASMHeaderListElem(tmpasmhle); 297 } 298 299 asmhle = failed_stripe->asmh_b; 300 while (asmhle) { 301 tmpasmhle= asmhle; 302 asmhle = tmpasmhle->next; 303 rf_FreeAccessStripeMap(tmpasmhle->asmh); 304 rf_FreeASMHeaderListElem(tmpasmhle); 305 } 306 307 vfple = failed_stripe->vfple; 308 while (vfple) { 309 tmpvfple = vfple; 310 vfple = tmpvfple->next; 311 rf_FreeVFPListElem(tmpvfple); 312 } 313 314 vfple = failed_stripe->bvfple; 315 while (vfple) { 316 tmpvfple = vfple; 317 vfple = tmpvfple->next; 318 rf_FreeVFPListElem(tmpvfple); 319 } 320 321 stripeNum++; 322 /* only move to the next failed stripe slot if the current one was used */ 323 tmpfailed_stripe = failed_stripe; 324 failed_stripe = failed_stripe->next; 325 rf_FreeFailedStripeStruct(tmpfailed_stripe); 326 } 327 stripeFuncs = stripeFuncs->next; 328 } 329 RF_ASSERT(stripeNum == numStripesBailed); 330 } 331 while (stripeFuncsList != NULL) { 332 temp = stripeFuncsList; 333 stripeFuncsList = stripeFuncsList->next; 334 rf_FreeFuncList(temp); 335 } 336 desc->numStripes = 0; 337 return (1); 338 } else { 339 /* begin dag creation */ 340 stripeNum = 0; 341 stripeUnitNum = 0; 342 343 /* create a list of dagLists and fill them in */ 344 345 dagListend = NULL; 346 347 stripeFuncs = stripeFuncsList; 348 failed_stripe = failed_stripes_list; 349 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 350 /* grab dag header for this stripe */ 351 dag_h = NULL; 352 353 dagList = rf_AllocDAGList(); 354 355 /* always tack the new dagList onto the end of the list... */ 356 if (dagListend == NULL) { 357 desc->dagList = dagList; 358 } else { 359 dagListend->next = dagList; 360 } 361 dagListend = dagList; 362 363 dagList->desc = desc; 364 365 if (stripeFuncs->fp == NULL) { 366 /* use bailout functions for this stripe */ 367 asmhle = failed_stripe->asmh_u; 368 vfple = failed_stripe->vfple; 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 */ 374 tmpasmhle = failed_stripe->asmh_b; 375 tmpvfple = failed_stripe->bvfple; 376 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 377 uFunc = vfple->fn; /* stripeUnitFuncs[stripeNum][j]; */ 378 if (uFunc == (RF_VoidFuncPtr) NULL) { 379 /* use bailout functions for 380 * this stripe unit */ 381 for (k = 0; k < physPtr->numSector; k++) { 382 /* create a dag for 383 * this block */ 384 InitHdrNode(&tempdag_h, raidPtr, desc); 385 dagList->numDags++; 386 if (dag_h == NULL) { 387 dag_h = tempdag_h; 388 } else { 389 lastdag_h->next = tempdag_h; 390 } 391 lastdag_h = tempdag_h; 392 393 bFunc = tmpvfple->fn; /* blockFuncs[stripeUnitNum][k]; */ 394 RF_ASSERT(bFunc); 395 asm_bp = tmpasmhle->asmh->stripeMap; /* asmh_b[stripeUnitNum][k]->stripeMap; */ 396 (*bFunc) (raidPtr, asm_bp, tempdag_h, bp, flags, tempdag_h->allocList); 397 398 tmpasmhle = tmpasmhle->next; 399 tmpvfple = tmpvfple->next; 400 } 401 stripeUnitNum++; 402 } else { 403 /* create a dag for this unit */ 404 InitHdrNode(&tempdag_h, raidPtr, desc); 405 dagList->numDags++; 406 if (dag_h == NULL) { 407 dag_h = tempdag_h; 408 } else { 409 lastdag_h->next = tempdag_h; 410 } 411 lastdag_h = tempdag_h; 412 413 asm_up = asmhle->asmh->stripeMap; /* asmh_u[stripeNum][j]->stripeMap; */ 414 (*uFunc) (raidPtr, asm_up, tempdag_h, bp, flags, tempdag_h->allocList); 415 } 416 asmhle = asmhle->next; 417 vfple = vfple->next; 418 } 419 RF_ASSERT(j == asm_p->numStripeUnitsAccessed); 420 /* merge linked bailout dag to existing dag 421 * collection */ 422 stripeNum++; 423 failed_stripe = failed_stripe->next; 424 } else { 425 /* Create a dag for this parity stripe */ 426 InitHdrNode(&tempdag_h, raidPtr, desc); 427 dagList->numDags++; 428 dag_h = tempdag_h; 429 lastdag_h = tempdag_h; 430 431 (stripeFuncs->fp) (raidPtr, asm_p, tempdag_h, bp, flags, tempdag_h->allocList); 432 } 433 dagList->dags = dag_h; 434 stripeFuncs = stripeFuncs->next; 435 } 436 RF_ASSERT(i == desc->numStripes); 437 438 /* free memory */ 439 if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) { 440 stripeNum = 0; 441 stripeUnitNum = 0; 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 */ 447 stripeFuncs = stripeFuncsList; 448 failed_stripe = failed_stripes_list; 449 dagList = desc->dagList; 450 451 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 452 453 dag_h = dagList->dags; 454 if (dag_h->asmList) { 455 endASMList = dag_h->asmList; 456 while (endASMList->next) 457 endASMList = endASMList->next; 458 } else 459 endASMList = NULL; 460 461 if (stripeFuncs->fp == NULL) { 462 numStripeUnits = asm_p->numStripeUnitsAccessed; 463 /* walk through stripe, stripe unit by 464 * stripe unit */ 465 asmhle = failed_stripe->asmh_u; 466 vfple = failed_stripe->vfple; 467 /* this contains all of the asm headers for block funcs, 468 so we have to initialize this here instead of below.*/ 469 tmpasmhle = failed_stripe->asmh_b; 470 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 471 if (vfple->fn == NULL) { 472 numBlocks = physPtr->numSector; 473 /* walk through stripe 474 * unit, block by 475 * block */ 476 for (k = 0; k < numBlocks; k++) { 477 if (dag_h->asmList == NULL) { 478 dag_h->asmList = tmpasmhle->asmh; /* asmh_b[stripeUnitNum][k];*/ 479 endASMList = dag_h->asmList; 480 } else { 481 endASMList->next = tmpasmhle->asmh; 482 endASMList = endASMList->next; 483 } 484 tmpasmhle = tmpasmhle->next; 485 } 486 stripeUnitNum++; 487 } 488 if (dag_h->asmList == NULL) { 489 dag_h->asmList = asmhle->asmh; 490 endASMList = dag_h->asmList; 491 } else { 492 endASMList->next = asmhle->asmh; 493 endASMList = endASMList->next; 494 } 495 asmhle = asmhle->next; 496 vfple = vfple->next; 497 } 498 stripeNum++; 499 failed_stripe = failed_stripe->next; 500 } 501 dagList = dagList->next; /* need to move in stride with stripeFuncs */ 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