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