1 /* $NetBSD: rf_aselect.c,v 1.28 2013/09/15 12:11:16 martin 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.28 2013/09/15 12:11:16 martin 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 *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, numUnitDags = 0, 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(); 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(); 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(); 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(); 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(); 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(); 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 } else { 270 numUnitDags++; 271 } 272 } 273 RF_ASSERT(j == numStripeUnits); 274 numStripesBailed++; 275 } 276 } 277 278 if (cantCreateDAGs) { 279 /* free memory and punt */ 280 if (numStripesBailed > 0) { 281 stripeNum = 0; 282 stripeFuncs = stripeFuncsList; 283 failed_stripe = failed_stripes_list; 284 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 285 if (stripeFuncs->fp == NULL) { 286 287 asmhle = failed_stripe->asmh_u; 288 while (asmhle) { 289 tmpasmhle= asmhle; 290 asmhle = tmpasmhle->next; 291 rf_FreeAccessStripeMap(tmpasmhle->asmh); 292 rf_FreeASMHeaderListElem(tmpasmhle); 293 } 294 295 asmhle = failed_stripe->asmh_b; 296 while (asmhle) { 297 tmpasmhle= asmhle; 298 asmhle = tmpasmhle->next; 299 rf_FreeAccessStripeMap(tmpasmhle->asmh); 300 rf_FreeASMHeaderListElem(tmpasmhle); 301 } 302 303 vfple = failed_stripe->vfple; 304 while (vfple) { 305 tmpvfple = vfple; 306 vfple = tmpvfple->next; 307 rf_FreeVFPListElem(tmpvfple); 308 } 309 310 vfple = failed_stripe->bvfple; 311 while (vfple) { 312 tmpvfple = vfple; 313 vfple = tmpvfple->next; 314 rf_FreeVFPListElem(tmpvfple); 315 } 316 317 stripeNum++; 318 /* only move to the next failed stripe slot if the current one was used */ 319 tmpfailed_stripe = failed_stripe; 320 failed_stripe = failed_stripe->next; 321 rf_FreeFailedStripeStruct(tmpfailed_stripe); 322 } 323 stripeFuncs = stripeFuncs->next; 324 } 325 RF_ASSERT(stripeNum == numStripesBailed); 326 } 327 while (stripeFuncsList != NULL) { 328 temp = stripeFuncsList; 329 stripeFuncsList = stripeFuncsList->next; 330 rf_FreeFuncList(temp); 331 } 332 desc->numStripes = 0; 333 return (1); 334 } else { 335 /* begin dag creation */ 336 stripeNum = 0; 337 stripeUnitNum = 0; 338 339 /* create a list of dagLists and fill them in */ 340 341 dagListend = NULL; 342 343 stripeFuncs = stripeFuncsList; 344 failed_stripe = failed_stripes_list; 345 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 346 /* grab dag header for this stripe */ 347 dag_h = NULL; 348 349 dagList = rf_AllocDAGList(); 350 351 /* always tack the new dagList onto the end of the list... */ 352 if (dagListend == NULL) { 353 desc->dagList = dagList; 354 } else { 355 dagListend->next = dagList; 356 } 357 dagListend = dagList; 358 359 dagList->desc = desc; 360 361 if (stripeFuncs->fp == NULL) { 362 /* use bailout functions for this stripe */ 363 asmhle = failed_stripe->asmh_u; 364 vfple = failed_stripe->vfple; 365 /* the following two may contain asm headers and 366 block function pointers for multiple asm within 367 this access. We initialize tmpasmhle and tmpvfple 368 here in order to allow for that, and for correct 369 operation below */ 370 tmpasmhle = failed_stripe->asmh_b; 371 tmpvfple = failed_stripe->bvfple; 372 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 373 uFunc = vfple->fn; /* stripeUnitFuncs[stripeNum][j]; */ 374 if (uFunc == NULL) { 375 /* use bailout functions for 376 * this stripe unit */ 377 for (k = 0; k < physPtr->numSector; k++) { 378 /* create a dag for 379 * this block */ 380 InitHdrNode(&tempdag_h, raidPtr, desc); 381 dagList->numDags++; 382 if (dag_h == NULL) { 383 dag_h = tempdag_h; 384 } else { 385 lastdag_h->next = tempdag_h; 386 } 387 lastdag_h = tempdag_h; 388 389 bFunc = tmpvfple->fn; /* blockFuncs[stripeUnitNum][k]; */ 390 RF_ASSERT(bFunc); 391 asm_bp = tmpasmhle->asmh->stripeMap; /* asmh_b[stripeUnitNum][k]->stripeMap; */ 392 (*bFunc) (raidPtr, asm_bp, tempdag_h, bp, flags, tempdag_h->allocList); 393 394 tmpasmhle = tmpasmhle->next; 395 tmpvfple = tmpvfple->next; 396 } 397 stripeUnitNum++; 398 } else { 399 /* create a dag for this unit */ 400 InitHdrNode(&tempdag_h, raidPtr, desc); 401 dagList->numDags++; 402 if (dag_h == NULL) { 403 dag_h = tempdag_h; 404 } else { 405 lastdag_h->next = tempdag_h; 406 } 407 lastdag_h = tempdag_h; 408 409 asm_up = asmhle->asmh->stripeMap; /* asmh_u[stripeNum][j]->stripeMap; */ 410 (*uFunc) (raidPtr, asm_up, tempdag_h, bp, flags, tempdag_h->allocList); 411 } 412 asmhle = asmhle->next; 413 vfple = vfple->next; 414 } 415 RF_ASSERT(j == asm_p->numStripeUnitsAccessed); 416 /* merge linked bailout dag to existing dag 417 * collection */ 418 stripeNum++; 419 failed_stripe = failed_stripe->next; 420 } else { 421 /* Create a dag for this parity stripe */ 422 InitHdrNode(&tempdag_h, raidPtr, desc); 423 dagList->numDags++; 424 dag_h = tempdag_h; 425 lastdag_h = tempdag_h; 426 427 (stripeFuncs->fp) (raidPtr, asm_p, tempdag_h, bp, flags, tempdag_h->allocList); 428 } 429 dagList->dags = dag_h; 430 stripeFuncs = stripeFuncs->next; 431 } 432 RF_ASSERT(i == desc->numStripes); 433 434 /* free memory */ 435 if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) { 436 stripeNum = 0; 437 stripeUnitNum = 0; 438 /* walk through io, stripe by stripe */ 439 /* here we build up dag_h->asmList for this dag... 440 we need all of these asm's to do the IO, and 441 want them in a convenient place for freeing at a 442 later time */ 443 stripeFuncs = stripeFuncsList; 444 failed_stripe = failed_stripes_list; 445 dagList = desc->dagList; 446 447 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 448 449 dag_h = dagList->dags; 450 if (dag_h->asmList) { 451 endASMList = dag_h->asmList; 452 while (endASMList->next) 453 endASMList = endASMList->next; 454 } else 455 endASMList = NULL; 456 457 if (stripeFuncs->fp == NULL) { 458 numStripeUnits = asm_p->numStripeUnitsAccessed; 459 /* walk through stripe, stripe unit by 460 * stripe unit */ 461 asmhle = failed_stripe->asmh_u; 462 vfple = failed_stripe->vfple; 463 /* this contains all of the asm headers for block funcs, 464 so we have to initialize this here instead of below.*/ 465 tmpasmhle = failed_stripe->asmh_b; 466 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 467 if (vfple->fn == NULL) { 468 numBlocks = physPtr->numSector; 469 /* walk through stripe 470 * unit, block by 471 * block */ 472 for (k = 0; k < numBlocks; k++) { 473 if (dag_h->asmList == NULL) { 474 dag_h->asmList = tmpasmhle->asmh; /* asmh_b[stripeUnitNum][k];*/ 475 endASMList = dag_h->asmList; 476 } else { 477 endASMList->next = tmpasmhle->asmh; 478 endASMList = endASMList->next; 479 } 480 tmpasmhle = tmpasmhle->next; 481 } 482 stripeUnitNum++; 483 } 484 if (dag_h->asmList == NULL) { 485 dag_h->asmList = asmhle->asmh; 486 endASMList = dag_h->asmList; 487 } else { 488 endASMList->next = asmhle->asmh; 489 endASMList = endASMList->next; 490 } 491 asmhle = asmhle->next; 492 vfple = vfple->next; 493 } 494 stripeNum++; 495 failed_stripe = failed_stripe->next; 496 } 497 dagList = dagList->next; /* need to move in stride with stripeFuncs */ 498 stripeFuncs = stripeFuncs->next; 499 } 500 RF_ASSERT(stripeNum == numStripesBailed); 501 RF_ASSERT(stripeUnitNum == numStripeUnitsBailed); 502 503 failed_stripe = failed_stripes_list; 504 while (failed_stripe) { 505 506 asmhle = failed_stripe->asmh_u; 507 while (asmhle) { 508 tmpasmhle= asmhle; 509 asmhle = tmpasmhle->next; 510 rf_FreeASMHeaderListElem(tmpasmhle); 511 } 512 513 asmhle = failed_stripe->asmh_b; 514 while (asmhle) { 515 tmpasmhle= asmhle; 516 asmhle = tmpasmhle->next; 517 rf_FreeASMHeaderListElem(tmpasmhle); 518 } 519 vfple = failed_stripe->vfple; 520 while (vfple) { 521 tmpvfple = vfple; 522 vfple = tmpvfple->next; 523 rf_FreeVFPListElem(tmpvfple); 524 } 525 526 vfple = failed_stripe->bvfple; 527 while (vfple) { 528 tmpvfple = vfple; 529 vfple = tmpvfple->next; 530 rf_FreeVFPListElem(tmpvfple); 531 } 532 533 tmpfailed_stripe = failed_stripe; 534 failed_stripe = tmpfailed_stripe->next; 535 rf_FreeFailedStripeStruct(tmpfailed_stripe); 536 } 537 } 538 while (stripeFuncsList != NULL) { 539 temp = stripeFuncsList; 540 stripeFuncsList = stripeFuncsList->next; 541 rf_FreeFuncList(temp); 542 } 543 return (0); 544 } 545 } 546