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