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 (at) 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 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 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
Indexes created Sun Sep 21 19:09:51 GMT 2025