1 /* $NetBSD: rf_aselect.c,v 1.5 2001/11/13 07:11:12 lukem 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.5 2001/11/13 07:11:12 lukem 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 #if defined(__NetBSD__) && defined(_KERNEL) 50 /* the function below is not used... so don't define it! */ 51 #else 52 static void TransferDagMemory(RF_DagHeader_t *, RF_DagHeader_t *); 53 #endif 54 55 static int InitHdrNode(RF_DagHeader_t **, RF_Raid_t *, int); 56 static void UpdateNodeHdrPtr(RF_DagHeader_t *, RF_DagNode_t *); 57 int rf_SelectAlgorithm(RF_RaidAccessDesc_t *, RF_RaidAccessFlags_t); 58 59 60 /****************************************************************************** 61 * 62 * Create and Initialiaze a dag header and termination node 63 * 64 *****************************************************************************/ 65 static int 66 InitHdrNode(hdr, raidPtr, memChunkEnable) 67 RF_DagHeader_t **hdr; 68 RF_Raid_t *raidPtr; 69 int memChunkEnable; 70 { 71 /* create and initialize dag hdr */ 72 *hdr = rf_AllocDAGHeader(); 73 rf_MakeAllocList((*hdr)->allocList); 74 if ((*hdr)->allocList == NULL) { 75 rf_FreeDAGHeader(*hdr); 76 return (ENOMEM); 77 } 78 (*hdr)->status = rf_enable; 79 (*hdr)->numSuccedents = 0; 80 (*hdr)->raidPtr = raidPtr; 81 (*hdr)->next = NULL; 82 return (0); 83 } 84 /****************************************************************************** 85 * 86 * Transfer allocation list and mem chunks from one dag to another 87 * 88 *****************************************************************************/ 89 #if defined(__NetBSD__) && defined(_KERNEL) 90 /* the function below is not used... so don't define it! */ 91 #else 92 static void 93 TransferDagMemory(daga, dagb) 94 RF_DagHeader_t *daga; 95 RF_DagHeader_t *dagb; 96 { 97 RF_AccessStripeMapHeader_t *end; 98 RF_AllocListElem_t *p; 99 int i, memChunksXfrd = 0, xtraChunksXfrd = 0; 100 101 /* transfer allocList from dagb to daga */ 102 for (p = dagb->allocList; p; p = p->next) { 103 for (i = 0; i < p->numPointers; i++) { 104 rf_AddToAllocList(daga->allocList, p->pointers[i], p->sizes[i]); 105 p->pointers[i] = NULL; 106 p->sizes[i] = 0; 107 } 108 p->numPointers = 0; 109 } 110 111 /* transfer chunks from dagb to daga */ 112 while ((memChunksXfrd + xtraChunksXfrd < dagb->chunkIndex + dagb->xtraChunkIndex) && (daga->chunkIndex < RF_MAXCHUNKS)) { 113 /* stuff chunks into daga's memChunk array */ 114 if (memChunksXfrd < dagb->chunkIndex) { 115 daga->memChunk[daga->chunkIndex++] = dagb->memChunk[memChunksXfrd]; 116 dagb->memChunk[memChunksXfrd++] = NULL; 117 } else { 118 daga->memChunk[daga->xtraChunkIndex++] = dagb->xtraMemChunk[xtraChunksXfrd]; 119 dagb->xtraMemChunk[xtraChunksXfrd++] = NULL; 120 } 121 } 122 /* use escape hatch to hold excess chunks */ 123 while (memChunksXfrd + xtraChunksXfrd < dagb->chunkIndex + dagb->xtraChunkIndex) { 124 if (memChunksXfrd < dagb->chunkIndex) { 125 daga->xtraMemChunk[daga->xtraChunkIndex++] = dagb->memChunk[memChunksXfrd]; 126 dagb->memChunk[memChunksXfrd++] = NULL; 127 } else { 128 daga->xtraMemChunk[daga->xtraChunkIndex++] = dagb->xtraMemChunk[xtraChunksXfrd]; 129 dagb->xtraMemChunk[xtraChunksXfrd++] = NULL; 130 } 131 } 132 RF_ASSERT((memChunksXfrd == dagb->chunkIndex) && (xtraChunksXfrd == dagb->xtraChunkIndex)); 133 RF_ASSERT(daga->chunkIndex <= RF_MAXCHUNKS); 134 RF_ASSERT(daga->xtraChunkIndex <= daga->xtraChunkCnt); 135 dagb->chunkIndex = 0; 136 dagb->xtraChunkIndex = 0; 137 138 /* transfer asmList from dagb to daga */ 139 if (dagb->asmList) { 140 if (daga->asmList) { 141 end = daga->asmList; 142 while (end->next) 143 end = end->next; 144 end->next = dagb->asmList; 145 } else 146 daga->asmList = dagb->asmList; 147 dagb->asmList = NULL; 148 } 149 } 150 #endif /* __NetBSD__ */ 151 152 /***************************************************************************************** 153 * 154 * Ensure that all node->dagHdr fields in a dag are consistent 155 * 156 * IMPORTANT: This routine recursively searches all succedents of the node. If a 157 * succedent is encountered whose dagHdr ptr does not require adjusting, that node's 158 * succedents WILL NOT BE EXAMINED. 159 * 160 ****************************************************************************************/ 161 static void 162 UpdateNodeHdrPtr(hdr, node) 163 RF_DagHeader_t *hdr; 164 RF_DagNode_t *node; 165 { 166 int i; 167 RF_ASSERT(hdr != NULL && node != NULL); 168 for (i = 0; i < node->numSuccedents; i++) 169 if (node->succedents[i]->dagHdr != hdr) 170 UpdateNodeHdrPtr(hdr, node->succedents[i]); 171 node->dagHdr = hdr; 172 } 173 /****************************************************************************** 174 * 175 * Create a DAG to do a read or write operation. 176 * 177 * create an array of dagLists, one list per parity stripe. 178 * return the lists in the array desc->dagArray. 179 * 180 * Normally, each list contains one dag for the entire stripe. In some 181 * tricky cases, we break this into multiple dags, either one per stripe 182 * unit or one per block (sector). When this occurs, these dags are returned 183 * as a linked list (dagList) which is executed sequentially (to preserve 184 * atomic parity updates in the stripe). 185 * 186 * dags which operate on independent parity goups (stripes) are returned in 187 * independent dagLists (distinct elements in desc->dagArray) and may be 188 * executed concurrently. 189 * 190 * Finally, if the SelectionFunc fails to create a dag for a block, we punt 191 * and return 1. 192 * 193 * The above process is performed in two phases: 194 * 1) create an array(s) of creation functions (eg stripeFuncs) 195 * 2) create dags and concatenate/merge to form the final dag. 196 * 197 * Because dag's are basic blocks (single entry, single exit, unconditional 198 * control flow, we can add the following optimizations (future work): 199 * first-pass optimizer to allow max concurrency (need all data dependencies) 200 * second-pass optimizer to eliminate common subexpressions (need true 201 * data dependencies) 202 * third-pass optimizer to eliminate dead code (need true data dependencies) 203 *****************************************************************************/ 204 205 #define MAXNSTRIPES 50 206 207 int 208 rf_SelectAlgorithm(desc, flags) 209 RF_RaidAccessDesc_t *desc; 210 RF_RaidAccessFlags_t flags; 211 { 212 RF_AccessStripeMapHeader_t *asm_h = desc->asmap; 213 RF_IoType_t type = desc->type; 214 RF_Raid_t *raidPtr = desc->raidPtr; 215 void *bp = desc->bp; 216 217 RF_AccessStripeMap_t *asmap = asm_h->stripeMap; 218 RF_AccessStripeMap_t *asm_p; 219 RF_DagHeader_t *dag_h = NULL, *tempdag_h, *lastdag_h; 220 int i, j, k; 221 RF_VoidFuncPtr *stripeFuncs, normalStripeFuncs[MAXNSTRIPES]; 222 RF_AccessStripeMap_t *asm_up, *asm_bp; 223 RF_AccessStripeMapHeader_t ***asmh_u, *endASMList; 224 RF_AccessStripeMapHeader_t ***asmh_b; 225 RF_VoidFuncPtr **stripeUnitFuncs, uFunc; 226 RF_VoidFuncPtr **blockFuncs, bFunc; 227 int numStripesBailed = 0, cantCreateDAGs = RF_FALSE; 228 int numStripeUnitsBailed = 0; 229 int stripeNum, numUnitDags = 0, stripeUnitNum, numBlockDags = 0; 230 RF_StripeNum_t numStripeUnits; 231 RF_SectorNum_t numBlocks; 232 RF_RaidAddr_t address; 233 int length; 234 RF_PhysDiskAddr_t *physPtr; 235 caddr_t buffer; 236 237 lastdag_h = NULL; 238 asmh_u = asmh_b = NULL; 239 stripeUnitFuncs = NULL; 240 blockFuncs = NULL; 241 242 /* get an array of dag-function creation pointers, try to avoid 243 * calling malloc */ 244 if (asm_h->numStripes <= MAXNSTRIPES) 245 stripeFuncs = normalStripeFuncs; 246 else 247 RF_Calloc(stripeFuncs, asm_h->numStripes, sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr *)); 248 249 /* walk through the asm list once collecting information */ 250 /* attempt to find a single creation function for each stripe */ 251 desc->numStripes = 0; 252 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 253 desc->numStripes++; 254 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_p, &stripeFuncs[i]); 255 /* check to see if we found a creation func for this stripe */ 256 if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) { 257 /* could not find creation function for entire stripe 258 * so, let's see if we can find one for each stripe 259 * unit in the stripe */ 260 261 if (numStripesBailed == 0) { 262 /* one stripe map header for each stripe we 263 * bail on */ 264 RF_Malloc(asmh_u, sizeof(RF_AccessStripeMapHeader_t **) * asm_h->numStripes, (RF_AccessStripeMapHeader_t ***)); 265 /* create an array of ptrs to arrays of 266 * stripeFuncs */ 267 RF_Calloc(stripeUnitFuncs, asm_h->numStripes, sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr **)); 268 } 269 /* create an array of creation funcs (called 270 * stripeFuncs) for this stripe */ 271 numStripeUnits = asm_p->numStripeUnitsAccessed; 272 RF_Calloc(stripeUnitFuncs[numStripesBailed], numStripeUnits, sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr *)); 273 RF_Malloc(asmh_u[numStripesBailed], numStripeUnits * sizeof(RF_AccessStripeMapHeader_t *), (RF_AccessStripeMapHeader_t **)); 274 275 /* lookup array of stripeUnitFuncs for this stripe */ 276 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 277 /* remap for series of single stripe-unit 278 * accesses */ 279 address = physPtr->raidAddress; 280 length = physPtr->numSector; 281 buffer = physPtr->bufPtr; 282 283 asmh_u[numStripesBailed][j] = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP); 284 asm_up = asmh_u[numStripesBailed][j]->stripeMap; 285 286 /* get the creation func for this stripe unit */ 287 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_up, &(stripeUnitFuncs[numStripesBailed][j])); 288 289 /* check to see if we found a creation func 290 * for this stripe unit */ 291 if (stripeUnitFuncs[numStripesBailed][j] == (RF_VoidFuncPtr) NULL) { 292 /* could not find creation function 293 * for stripe unit so, let's see if we 294 * can find one for each block in the 295 * stripe unit */ 296 if (numStripeUnitsBailed == 0) { 297 /* one stripe map header for 298 * each stripe unit we bail on */ 299 RF_Malloc(asmh_b, sizeof(RF_AccessStripeMapHeader_t **) * asm_h->numStripes * raidPtr->Layout.numDataCol, (RF_AccessStripeMapHeader_t ***)); 300 /* create an array of ptrs to 301 * arrays of blockFuncs */ 302 RF_Calloc(blockFuncs, asm_h->numStripes * raidPtr->Layout.numDataCol, sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr **)); 303 } 304 /* create an array of creation funcs 305 * (called blockFuncs) for this stripe 306 * unit */ 307 numBlocks = physPtr->numSector; 308 numBlockDags += numBlocks; 309 RF_Calloc(blockFuncs[numStripeUnitsBailed], numBlocks, sizeof(RF_VoidFuncPtr), (RF_VoidFuncPtr *)); 310 RF_Malloc(asmh_b[numStripeUnitsBailed], numBlocks * sizeof(RF_AccessStripeMapHeader_t *), (RF_AccessStripeMapHeader_t **)); 311 312 /* lookup array of blockFuncs for this 313 * stripe unit */ 314 for (k = 0; k < numBlocks; k++) { 315 /* remap for series of single 316 * stripe-unit accesses */ 317 address = physPtr->raidAddress + k; 318 length = 1; 319 buffer = physPtr->bufPtr + (k * (1 << raidPtr->logBytesPerSector)); 320 321 asmh_b[numStripeUnitsBailed][k] = rf_MapAccess(raidPtr, address, length, buffer, RF_DONT_REMAP); 322 asm_bp = asmh_b[numStripeUnitsBailed][k]->stripeMap; 323 324 /* get the creation func for 325 * this stripe unit */ 326 (raidPtr->Layout.map->SelectionFunc) (raidPtr, type, asm_bp, &(blockFuncs[numStripeUnitsBailed][k])); 327 328 /* check to see if we found a 329 * creation func for this 330 * stripe unit */ 331 if (blockFuncs[numStripeUnitsBailed][k] == NULL) 332 cantCreateDAGs = RF_TRUE; 333 } 334 numStripeUnitsBailed++; 335 } else { 336 numUnitDags++; 337 } 338 } 339 RF_ASSERT(j == numStripeUnits); 340 numStripesBailed++; 341 } 342 } 343 344 if (cantCreateDAGs) { 345 /* free memory and punt */ 346 if (asm_h->numStripes > MAXNSTRIPES) 347 RF_Free(stripeFuncs, asm_h->numStripes * sizeof(RF_VoidFuncPtr)); 348 if (numStripesBailed > 0) { 349 stripeNum = 0; 350 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) 351 if (stripeFuncs[i] == NULL) { 352 numStripeUnits = asm_p->numStripeUnitsAccessed; 353 for (j = 0; j < numStripeUnits; j++) 354 rf_FreeAccessStripeMap(asmh_u[stripeNum][j]); 355 RF_Free(asmh_u[stripeNum], numStripeUnits * sizeof(RF_AccessStripeMapHeader_t *)); 356 RF_Free(stripeUnitFuncs[stripeNum], numStripeUnits * sizeof(RF_VoidFuncPtr)); 357 stripeNum++; 358 } 359 RF_ASSERT(stripeNum == numStripesBailed); 360 RF_Free(stripeUnitFuncs, asm_h->numStripes * sizeof(RF_VoidFuncPtr)); 361 RF_Free(asmh_u, asm_h->numStripes * sizeof(RF_AccessStripeMapHeader_t **)); 362 } 363 return (1); 364 } else { 365 /* begin dag creation */ 366 stripeNum = 0; 367 stripeUnitNum = 0; 368 369 /* create an array of dagLists and fill them in */ 370 RF_CallocAndAdd(desc->dagArray, desc->numStripes, sizeof(RF_DagList_t), (RF_DagList_t *), desc->cleanupList); 371 372 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) { 373 /* grab dag header for this stripe */ 374 dag_h = NULL; 375 desc->dagArray[i].desc = desc; 376 377 if (stripeFuncs[i] == (RF_VoidFuncPtr) NULL) { 378 /* use bailout functions for this stripe */ 379 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 380 uFunc = stripeUnitFuncs[stripeNum][j]; 381 if (uFunc == (RF_VoidFuncPtr) NULL) { 382 /* use bailout functions for 383 * this stripe unit */ 384 for (k = 0; k < physPtr->numSector; k++) { 385 /* create a dag for 386 * this block */ 387 InitHdrNode(&tempdag_h, raidPtr, rf_useMemChunks); 388 desc->dagArray[i].numDags++; 389 if (dag_h == NULL) { 390 dag_h = tempdag_h; 391 } else { 392 lastdag_h->next = tempdag_h; 393 } 394 lastdag_h = tempdag_h; 395 396 bFunc = blockFuncs[stripeUnitNum][k]; 397 RF_ASSERT(bFunc); 398 asm_bp = asmh_b[stripeUnitNum][k]->stripeMap; 399 (*bFunc) (raidPtr, asm_bp, tempdag_h, bp, flags, tempdag_h->allocList); 400 } 401 stripeUnitNum++; 402 } else { 403 /* create a dag for this unit */ 404 InitHdrNode(&tempdag_h, raidPtr, rf_useMemChunks); 405 desc->dagArray[i].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 = asmh_u[stripeNum][j]->stripeMap; 414 (*uFunc) (raidPtr, asm_up, tempdag_h, bp, flags, tempdag_h->allocList); 415 } 416 } 417 RF_ASSERT(j == asm_p->numStripeUnitsAccessed); 418 /* merge linked bailout dag to existing dag 419 * collection */ 420 stripeNum++; 421 } else { 422 /* Create a dag for this parity stripe */ 423 InitHdrNode(&tempdag_h, raidPtr, rf_useMemChunks); 424 desc->dagArray[i].numDags++; 425 if (dag_h == NULL) { 426 dag_h = tempdag_h; 427 } else { 428 lastdag_h->next = tempdag_h; 429 } 430 lastdag_h = tempdag_h; 431 432 (stripeFuncs[i]) (raidPtr, asm_p, tempdag_h, bp, flags, tempdag_h->allocList); 433 } 434 desc->dagArray[i].dags = dag_h; 435 } 436 RF_ASSERT(i == desc->numStripes); 437 438 /* free memory */ 439 if (asm_h->numStripes > MAXNSTRIPES) 440 RF_Free(stripeFuncs, asm_h->numStripes * sizeof(RF_VoidFuncPtr)); 441 if ((numStripesBailed > 0) || (numStripeUnitsBailed > 0)) { 442 stripeNum = 0; 443 stripeUnitNum = 0; 444 if (dag_h->asmList) { 445 endASMList = dag_h->asmList; 446 while (endASMList->next) 447 endASMList = endASMList->next; 448 } else 449 endASMList = NULL; 450 /* walk through io, stripe by stripe */ 451 for (i = 0, asm_p = asmap; asm_p; asm_p = asm_p->next, i++) 452 if (stripeFuncs[i] == NULL) { 453 numStripeUnits = asm_p->numStripeUnitsAccessed; 454 /* walk through stripe, stripe unit by 455 * stripe unit */ 456 for (j = 0, physPtr = asm_p->physInfo; physPtr; physPtr = physPtr->next, j++) { 457 if (stripeUnitFuncs[stripeNum][j] == NULL) { 458 numBlocks = physPtr->numSector; 459 /* walk through stripe 460 * unit, block by 461 * block */ 462 for (k = 0; k < numBlocks; k++) 463 if (dag_h->asmList == NULL) { 464 dag_h->asmList = asmh_b[stripeUnitNum][k]; 465 endASMList = dag_h->asmList; 466 } else { 467 endASMList->next = asmh_b[stripeUnitNum][k]; 468 endASMList = endASMList->next; 469 } 470 RF_Free(asmh_b[stripeUnitNum], numBlocks * sizeof(RF_AccessStripeMapHeader_t *)); 471 RF_Free(blockFuncs[stripeUnitNum], numBlocks * sizeof(RF_VoidFuncPtr)); 472 stripeUnitNum++; 473 } 474 if (dag_h->asmList == NULL) { 475 dag_h->asmList = asmh_u[stripeNum][j]; 476 endASMList = dag_h->asmList; 477 } else { 478 endASMList->next = asmh_u[stripeNum][j]; 479 endASMList = endASMList->next; 480 } 481 } 482 RF_Free(asmh_u[stripeNum], numStripeUnits * sizeof(RF_AccessStripeMapHeader_t *)); 483 RF_Free(stripeUnitFuncs[stripeNum], numStripeUnits * sizeof(RF_VoidFuncPtr)); 484 stripeNum++; 485 } 486 RF_ASSERT(stripeNum == numStripesBailed); 487 RF_Free(stripeUnitFuncs, asm_h->numStripes * sizeof(RF_VoidFuncPtr)); 488 RF_Free(asmh_u, asm_h->numStripes * sizeof(RF_AccessStripeMapHeader_t **)); 489 if (numStripeUnitsBailed > 0) { 490 RF_ASSERT(stripeUnitNum == numStripeUnitsBailed); 491 RF_Free(blockFuncs, raidPtr->Layout.numDataCol * asm_h->numStripes * sizeof(RF_VoidFuncPtr)); 492 RF_Free(asmh_b, raidPtr->Layout.numDataCol * asm_h->numStripes * sizeof(RF_AccessStripeMapHeader_t **)); 493 } 494 } 495 return (0); 496 } 497 } 498