1 /* $NetBSD: rf_map.c,v 1.5 2000/06/29 00:22:27 oster Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Author: Mark Holland 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 * map.c -- main code for mapping RAID addresses to physical disk addresses 32 * 33 **************************************************************************/ 34 35 #include "rf_types.h" 36 #include "rf_threadstuff.h" 37 #include "rf_raid.h" 38 #include "rf_general.h" 39 #include "rf_map.h" 40 #include "rf_freelist.h" 41 #include "rf_shutdown.h" 42 43 static void rf_FreePDAList(RF_PhysDiskAddr_t * start, RF_PhysDiskAddr_t * end, int count); 44 static void 45 rf_FreeASMList(RF_AccessStripeMap_t * start, RF_AccessStripeMap_t * end, 46 int count); 47 48 /***************************************************************************************** 49 * 50 * MapAccess -- main 1st order mapping routine. 51 * 52 * Maps an access in the RAID address space to the corresponding set of physical disk 53 * addresses. The result is returned as a list of AccessStripeMap structures, one per 54 * stripe accessed. Each ASM structure contains a pointer to a list of PhysDiskAddr 55 * structures, which describe the physical locations touched by the user access. Note 56 * that this routine returns only static mapping information, i.e. the list of physical 57 * addresses returned does not necessarily identify the set of physical locations that 58 * will actually be read or written. 59 * 60 * The routine also maps the parity. The physical disk location returned always 61 * indicates the entire parity unit, even when only a subset of it is being accessed. 62 * This is because an access that is not stripe unit aligned but that spans a stripe 63 * unit boundary may require access two distinct portions of the parity unit, and we 64 * can't yet tell which portion(s) we'll actually need. We leave it up to the algorithm 65 * selection code to decide what subset of the parity unit to access. 66 * 67 * Note that addresses in the RAID address space must always be maintained as 68 * longs, instead of ints. 69 * 70 * This routine returns NULL if numBlocks is 0 71 * 72 ****************************************************************************************/ 73 74 RF_AccessStripeMapHeader_t * 75 rf_MapAccess(raidPtr, raidAddress, numBlocks, buffer, remap) 76 RF_Raid_t *raidPtr; 77 RF_RaidAddr_t raidAddress; /* starting address in RAID address 78 * space */ 79 RF_SectorCount_t numBlocks; /* number of blocks in RAID address 80 * space to access */ 81 caddr_t buffer; /* buffer to supply/receive data */ 82 int remap; /* 1 => remap addresses to spare space */ 83 { 84 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 85 RF_AccessStripeMapHeader_t *asm_hdr = NULL; 86 RF_AccessStripeMap_t *asm_list = NULL, *asm_p = NULL; 87 int faultsTolerated = layoutPtr->map->faultsTolerated; 88 RF_RaidAddr_t startAddress = raidAddress; /* we'll change 89 * raidAddress along the 90 * way */ 91 RF_RaidAddr_t endAddress = raidAddress + numBlocks; 92 RF_RaidDisk_t **disks = raidPtr->Disks; 93 94 RF_PhysDiskAddr_t *pda_p, *pda_q; 95 RF_StripeCount_t numStripes = 0; 96 RF_RaidAddr_t stripeRealEndAddress, stripeEndAddress, nextStripeUnitAddress; 97 RF_RaidAddr_t startAddrWithinStripe, lastRaidAddr; 98 RF_StripeCount_t totStripes; 99 RF_StripeNum_t stripeID, lastSID, SUID, lastSUID; 100 RF_AccessStripeMap_t *asmList, *t_asm; 101 RF_PhysDiskAddr_t *pdaList, *t_pda; 102 103 /* allocate all the ASMs and PDAs up front */ 104 lastRaidAddr = raidAddress + numBlocks - 1; 105 stripeID = rf_RaidAddressToStripeID(layoutPtr, raidAddress); 106 lastSID = rf_RaidAddressToStripeID(layoutPtr, lastRaidAddr); 107 totStripes = lastSID - stripeID + 1; 108 SUID = rf_RaidAddressToStripeUnitID(layoutPtr, raidAddress); 109 lastSUID = rf_RaidAddressToStripeUnitID(layoutPtr, lastRaidAddr); 110 111 asmList = rf_AllocASMList(totStripes); 112 pdaList = rf_AllocPDAList(lastSUID - SUID + 1 + faultsTolerated * totStripes); /* may also need pda(s) 113 * per stripe for parity */ 114 115 if (raidAddress + numBlocks > raidPtr->totalSectors) { 116 RF_ERRORMSG1("Unable to map access because offset (%d) was invalid\n", 117 (int) raidAddress); 118 return (NULL); 119 } 120 if (rf_mapDebug) 121 rf_PrintRaidAddressInfo(raidPtr, raidAddress, numBlocks); 122 for (; raidAddress < endAddress;) { 123 /* make the next stripe structure */ 124 RF_ASSERT(asmList); 125 t_asm = asmList; 126 asmList = asmList->next; 127 bzero((char *) t_asm, sizeof(RF_AccessStripeMap_t)); 128 if (!asm_p) 129 asm_list = asm_p = t_asm; 130 else { 131 asm_p->next = t_asm; 132 asm_p = asm_p->next; 133 } 134 numStripes++; 135 136 /* map SUs from current location to the end of the stripe */ 137 asm_p->stripeID = /* rf_RaidAddressToStripeID(layoutPtr, 138 raidAddress) */ stripeID++; 139 stripeRealEndAddress = rf_RaidAddressOfNextStripeBoundary(layoutPtr, raidAddress); 140 stripeEndAddress = RF_MIN(endAddress, stripeRealEndAddress); 141 asm_p->raidAddress = raidAddress; 142 asm_p->endRaidAddress = stripeEndAddress; 143 144 /* map each stripe unit in the stripe */ 145 pda_p = NULL; 146 startAddrWithinStripe = raidAddress; /* Raid addr of start of 147 * portion of access 148 * that is within this 149 * stripe */ 150 for (; raidAddress < stripeEndAddress;) { 151 RF_ASSERT(pdaList); 152 t_pda = pdaList; 153 pdaList = pdaList->next; 154 bzero((char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 155 if (!pda_p) 156 asm_p->physInfo = pda_p = t_pda; 157 else { 158 pda_p->next = t_pda; 159 pda_p = pda_p->next; 160 } 161 162 pda_p->type = RF_PDA_TYPE_DATA; 163 (layoutPtr->map->MapSector) (raidPtr, raidAddress, &(pda_p->row), &(pda_p->col), &(pda_p->startSector), remap); 164 165 /* mark any failures we find. failedPDA is don't-care 166 * if there is more than one failure */ 167 pda_p->raidAddress = raidAddress; /* the RAID address 168 * corresponding to this 169 * physical disk address */ 170 nextStripeUnitAddress = rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, raidAddress); 171 pda_p->numSector = RF_MIN(endAddress, nextStripeUnitAddress) - raidAddress; 172 RF_ASSERT(pda_p->numSector != 0); 173 rf_ASMCheckStatus(raidPtr, pda_p, asm_p, disks, 0); 174 pda_p->bufPtr = buffer + rf_RaidAddressToByte(raidPtr, (raidAddress - startAddress)); 175 asm_p->totalSectorsAccessed += pda_p->numSector; 176 asm_p->numStripeUnitsAccessed++; 177 asm_p->origRow = pda_p->row; /* redundant but 178 * harmless to do this 179 * in every loop 180 * iteration */ 181 182 raidAddress = RF_MIN(endAddress, nextStripeUnitAddress); 183 } 184 185 /* Map the parity. At this stage, the startSector and 186 * numSector fields for the parity unit are always set to 187 * indicate the entire parity unit. We may modify this after 188 * mapping the data portion. */ 189 switch (faultsTolerated) { 190 case 0: 191 break; 192 case 1: /* single fault tolerant */ 193 RF_ASSERT(pdaList); 194 t_pda = pdaList; 195 pdaList = pdaList->next; 196 bzero((char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 197 pda_p = asm_p->parityInfo = t_pda; 198 pda_p->type = RF_PDA_TYPE_PARITY; 199 (layoutPtr->map->MapParity) (raidPtr, rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe), 200 &(pda_p->row), &(pda_p->col), &(pda_p->startSector), remap); 201 pda_p->numSector = layoutPtr->sectorsPerStripeUnit; 202 /* raidAddr may be needed to find unit to redirect to */ 203 pda_p->raidAddress = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe); 204 rf_ASMCheckStatus(raidPtr, pda_p, asm_p, disks, 1); 205 rf_ASMParityAdjust(asm_p->parityInfo, startAddrWithinStripe, endAddress, layoutPtr, asm_p); 206 207 break; 208 case 2: /* two fault tolerant */ 209 RF_ASSERT(pdaList && pdaList->next); 210 t_pda = pdaList; 211 pdaList = pdaList->next; 212 bzero((char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 213 pda_p = asm_p->parityInfo = t_pda; 214 pda_p->type = RF_PDA_TYPE_PARITY; 215 t_pda = pdaList; 216 pdaList = pdaList->next; 217 bzero((char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 218 pda_q = asm_p->qInfo = t_pda; 219 pda_q->type = RF_PDA_TYPE_Q; 220 (layoutPtr->map->MapParity) (raidPtr, rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe), 221 &(pda_p->row), &(pda_p->col), &(pda_p->startSector), remap); 222 (layoutPtr->map->MapQ) (raidPtr, rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe), 223 &(pda_q->row), &(pda_q->col), &(pda_q->startSector), remap); 224 pda_q->numSector = pda_p->numSector = layoutPtr->sectorsPerStripeUnit; 225 /* raidAddr may be needed to find unit to redirect to */ 226 pda_p->raidAddress = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe); 227 pda_q->raidAddress = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, startAddrWithinStripe); 228 /* failure mode stuff */ 229 rf_ASMCheckStatus(raidPtr, pda_p, asm_p, disks, 1); 230 rf_ASMCheckStatus(raidPtr, pda_q, asm_p, disks, 1); 231 rf_ASMParityAdjust(asm_p->parityInfo, startAddrWithinStripe, endAddress, layoutPtr, asm_p); 232 rf_ASMParityAdjust(asm_p->qInfo, startAddrWithinStripe, endAddress, layoutPtr, asm_p); 233 break; 234 } 235 } 236 RF_ASSERT(asmList == NULL && pdaList == NULL); 237 /* make the header structure */ 238 asm_hdr = rf_AllocAccessStripeMapHeader(); 239 RF_ASSERT(numStripes == totStripes); 240 asm_hdr->numStripes = numStripes; 241 asm_hdr->stripeMap = asm_list; 242 243 if (rf_mapDebug) 244 rf_PrintAccessStripeMap(asm_hdr); 245 return (asm_hdr); 246 } 247 /***************************************************************************************** 248 * This routine walks through an ASM list and marks the PDAs that have failed. 249 * It's called only when a disk failure causes an in-flight DAG to fail. 250 * The parity may consist of two components, but we want to use only one failedPDA 251 * pointer. Thus we set failedPDA to point to the first parity component, and rely 252 * on the rest of the code to do the right thing with this. 253 ****************************************************************************************/ 254 255 void 256 rf_MarkFailuresInASMList(raidPtr, asm_h) 257 RF_Raid_t *raidPtr; 258 RF_AccessStripeMapHeader_t *asm_h; 259 { 260 RF_RaidDisk_t **disks = raidPtr->Disks; 261 RF_AccessStripeMap_t *asmap; 262 RF_PhysDiskAddr_t *pda; 263 264 for (asmap = asm_h->stripeMap; asmap; asmap = asmap->next) { 265 asmap->numDataFailed = asmap->numParityFailed = asmap->numQFailed = 0; 266 asmap->numFailedPDAs = 0; 267 bzero((char *) asmap->failedPDAs, 268 RF_MAX_FAILED_PDA * sizeof(RF_PhysDiskAddr_t *)); 269 for (pda = asmap->physInfo; pda; pda = pda->next) { 270 if (RF_DEAD_DISK(disks[pda->row][pda->col].status)) { 271 asmap->numDataFailed++; 272 asmap->failedPDAs[asmap->numFailedPDAs] = pda; 273 asmap->numFailedPDAs++; 274 } 275 } 276 pda = asmap->parityInfo; 277 if (pda && RF_DEAD_DISK(disks[pda->row][pda->col].status)) { 278 asmap->numParityFailed++; 279 asmap->failedPDAs[asmap->numFailedPDAs] = pda; 280 asmap->numFailedPDAs++; 281 } 282 pda = asmap->qInfo; 283 if (pda && RF_DEAD_DISK(disks[pda->row][pda->col].status)) { 284 asmap->numQFailed++; 285 asmap->failedPDAs[asmap->numFailedPDAs] = pda; 286 asmap->numFailedPDAs++; 287 } 288 } 289 } 290 /***************************************************************************************** 291 * 292 * DuplicateASM -- duplicates an ASM and returns the new one 293 * 294 ****************************************************************************************/ 295 RF_AccessStripeMap_t * 296 rf_DuplicateASM(asmap) 297 RF_AccessStripeMap_t *asmap; 298 { 299 RF_AccessStripeMap_t *new_asm; 300 RF_PhysDiskAddr_t *pda, *new_pda, *t_pda; 301 302 new_pda = NULL; 303 new_asm = rf_AllocAccessStripeMapComponent(); 304 bcopy((char *) asmap, (char *) new_asm, sizeof(RF_AccessStripeMap_t)); 305 new_asm->numFailedPDAs = 0; /* ??? */ 306 new_asm->failedPDAs[0] = NULL; 307 new_asm->physInfo = NULL; 308 new_asm->parityInfo = NULL; 309 new_asm->next = NULL; 310 311 for (pda = asmap->physInfo; pda; pda = pda->next) { /* copy the physInfo 312 * list */ 313 t_pda = rf_AllocPhysDiskAddr(); 314 bcopy((char *) pda, (char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 315 t_pda->next = NULL; 316 if (!new_asm->physInfo) { 317 new_asm->physInfo = t_pda; 318 new_pda = t_pda; 319 } else { 320 new_pda->next = t_pda; 321 new_pda = new_pda->next; 322 } 323 if (pda == asmap->failedPDAs[0]) 324 new_asm->failedPDAs[0] = t_pda; 325 } 326 for (pda = asmap->parityInfo; pda; pda = pda->next) { /* copy the parityInfo 327 * list */ 328 t_pda = rf_AllocPhysDiskAddr(); 329 bcopy((char *) pda, (char *) t_pda, sizeof(RF_PhysDiskAddr_t)); 330 t_pda->next = NULL; 331 if (!new_asm->parityInfo) { 332 new_asm->parityInfo = t_pda; 333 new_pda = t_pda; 334 } else { 335 new_pda->next = t_pda; 336 new_pda = new_pda->next; 337 } 338 if (pda == asmap->failedPDAs[0]) 339 new_asm->failedPDAs[0] = t_pda; 340 } 341 return (new_asm); 342 } 343 /***************************************************************************************** 344 * 345 * DuplicatePDA -- duplicates a PDA and returns the new one 346 * 347 ****************************************************************************************/ 348 RF_PhysDiskAddr_t * 349 rf_DuplicatePDA(pda) 350 RF_PhysDiskAddr_t *pda; 351 { 352 RF_PhysDiskAddr_t *new; 353 354 new = rf_AllocPhysDiskAddr(); 355 bcopy((char *) pda, (char *) new, sizeof(RF_PhysDiskAddr_t)); 356 return (new); 357 } 358 /***************************************************************************************** 359 * 360 * routines to allocate and free list elements. All allocation routines zero the 361 * structure before returning it. 362 * 363 * FreePhysDiskAddr is static. It should never be called directly, because 364 * FreeAccessStripeMap takes care of freeing the PhysDiskAddr list. 365 * 366 ****************************************************************************************/ 367 368 static RF_FreeList_t *rf_asmhdr_freelist; 369 #define RF_MAX_FREE_ASMHDR 128 370 #define RF_ASMHDR_INC 16 371 #define RF_ASMHDR_INITIAL 32 372 373 static RF_FreeList_t *rf_asm_freelist; 374 #define RF_MAX_FREE_ASM 192 375 #define RF_ASM_INC 24 376 #define RF_ASM_INITIAL 64 377 378 static RF_FreeList_t *rf_pda_freelist; 379 #define RF_MAX_FREE_PDA 192 380 #define RF_PDA_INC 24 381 #define RF_PDA_INITIAL 64 382 383 /* called at shutdown time. So far, all that is necessary is to release all the free lists */ 384 static void rf_ShutdownMapModule(void *); 385 static void 386 rf_ShutdownMapModule(ignored) 387 void *ignored; 388 { 389 RF_FREELIST_DESTROY(rf_asmhdr_freelist, next, (RF_AccessStripeMapHeader_t *)); 390 RF_FREELIST_DESTROY(rf_pda_freelist, next, (RF_PhysDiskAddr_t *)); 391 RF_FREELIST_DESTROY(rf_asm_freelist, next, (RF_AccessStripeMap_t *)); 392 } 393 394 int 395 rf_ConfigureMapModule(listp) 396 RF_ShutdownList_t **listp; 397 { 398 int rc; 399 400 RF_FREELIST_CREATE(rf_asmhdr_freelist, RF_MAX_FREE_ASMHDR, 401 RF_ASMHDR_INC, sizeof(RF_AccessStripeMapHeader_t)); 402 if (rf_asmhdr_freelist == NULL) { 403 return (ENOMEM); 404 } 405 RF_FREELIST_CREATE(rf_asm_freelist, RF_MAX_FREE_ASM, 406 RF_ASM_INC, sizeof(RF_AccessStripeMap_t)); 407 if (rf_asm_freelist == NULL) { 408 RF_FREELIST_DESTROY(rf_asmhdr_freelist, next, (RF_AccessStripeMapHeader_t *)); 409 return (ENOMEM); 410 } 411 RF_FREELIST_CREATE(rf_pda_freelist, RF_MAX_FREE_PDA, 412 RF_PDA_INC, sizeof(RF_PhysDiskAddr_t)); 413 if (rf_pda_freelist == NULL) { 414 RF_FREELIST_DESTROY(rf_asmhdr_freelist, next, (RF_AccessStripeMapHeader_t *)); 415 RF_FREELIST_DESTROY(rf_pda_freelist, next, (RF_PhysDiskAddr_t *)); 416 return (ENOMEM); 417 } 418 rc = rf_ShutdownCreate(listp, rf_ShutdownMapModule, NULL); 419 if (rc) { 420 RF_ERRORMSG3("Unable to add to shutdown list file %s line %d rc=%d\n", __FILE__, 421 __LINE__, rc); 422 rf_ShutdownMapModule(NULL); 423 return (rc); 424 } 425 RF_FREELIST_PRIME(rf_asmhdr_freelist, RF_ASMHDR_INITIAL, next, 426 (RF_AccessStripeMapHeader_t *)); 427 RF_FREELIST_PRIME(rf_asm_freelist, RF_ASM_INITIAL, next, 428 (RF_AccessStripeMap_t *)); 429 RF_FREELIST_PRIME(rf_pda_freelist, RF_PDA_INITIAL, next, 430 (RF_PhysDiskAddr_t *)); 431 432 return (0); 433 } 434 435 RF_AccessStripeMapHeader_t * 436 rf_AllocAccessStripeMapHeader() 437 { 438 RF_AccessStripeMapHeader_t *p; 439 440 RF_FREELIST_GET(rf_asmhdr_freelist, p, next, (RF_AccessStripeMapHeader_t *)); 441 bzero((char *) p, sizeof(RF_AccessStripeMapHeader_t)); 442 443 return (p); 444 } 445 446 447 void 448 rf_FreeAccessStripeMapHeader(p) 449 RF_AccessStripeMapHeader_t *p; 450 { 451 RF_FREELIST_FREE(rf_asmhdr_freelist, p, next); 452 } 453 454 RF_PhysDiskAddr_t * 455 rf_AllocPhysDiskAddr() 456 { 457 RF_PhysDiskAddr_t *p; 458 459 RF_FREELIST_GET(rf_pda_freelist, p, next, (RF_PhysDiskAddr_t *)); 460 bzero((char *) p, sizeof(RF_PhysDiskAddr_t)); 461 462 return (p); 463 } 464 /* allocates a list of PDAs, locking the free list only once 465 * when we have to call calloc, we do it one component at a time to simplify 466 * the process of freeing the list at program shutdown. This should not be 467 * much of a performance hit, because it should be very infrequently executed. 468 */ 469 RF_PhysDiskAddr_t * 470 rf_AllocPDAList(count) 471 int count; 472 { 473 RF_PhysDiskAddr_t *p = NULL; 474 475 RF_FREELIST_GET_N(rf_pda_freelist, p, next, (RF_PhysDiskAddr_t *), count); 476 return (p); 477 } 478 479 void 480 rf_FreePhysDiskAddr(p) 481 RF_PhysDiskAddr_t *p; 482 { 483 RF_FREELIST_FREE(rf_pda_freelist, p, next); 484 } 485 486 static void 487 rf_FreePDAList(l_start, l_end, count) 488 RF_PhysDiskAddr_t *l_start, *l_end; /* pointers to start and end 489 * of list */ 490 int count; /* number of elements in list */ 491 { 492 RF_FREELIST_FREE_N(rf_pda_freelist, l_start, next, (RF_PhysDiskAddr_t *), count); 493 } 494 495 RF_AccessStripeMap_t * 496 rf_AllocAccessStripeMapComponent() 497 { 498 RF_AccessStripeMap_t *p; 499 500 RF_FREELIST_GET(rf_asm_freelist, p, next, (RF_AccessStripeMap_t *)); 501 bzero((char *) p, sizeof(RF_AccessStripeMap_t)); 502 503 return (p); 504 } 505 /* this is essentially identical to AllocPDAList. I should combine the two. 506 * when we have to call calloc, we do it one component at a time to simplify 507 * the process of freeing the list at program shutdown. This should not be 508 * much of a performance hit, because it should be very infrequently executed. 509 */ 510 RF_AccessStripeMap_t * 511 rf_AllocASMList(count) 512 int count; 513 { 514 RF_AccessStripeMap_t *p = NULL; 515 516 RF_FREELIST_GET_N(rf_asm_freelist, p, next, (RF_AccessStripeMap_t *), count); 517 return (p); 518 } 519 520 void 521 rf_FreeAccessStripeMapComponent(p) 522 RF_AccessStripeMap_t *p; 523 { 524 RF_FREELIST_FREE(rf_asm_freelist, p, next); 525 } 526 527 static void 528 rf_FreeASMList(l_start, l_end, count) 529 RF_AccessStripeMap_t *l_start, *l_end; 530 int count; 531 { 532 RF_FREELIST_FREE_N(rf_asm_freelist, l_start, next, (RF_AccessStripeMap_t *), count); 533 } 534 535 void 536 rf_FreeAccessStripeMap(hdr) 537 RF_AccessStripeMapHeader_t *hdr; 538 { 539 RF_AccessStripeMap_t *p, *pt = NULL; 540 RF_PhysDiskAddr_t *pdp, *trailer, *pdaList = NULL, *pdaEnd = NULL; 541 int count = 0, t, asm_count = 0; 542 543 for (p = hdr->stripeMap; p; p = p->next) { 544 545 /* link the 3 pda lists into the accumulating pda list */ 546 547 if (!pdaList) 548 pdaList = p->qInfo; 549 else 550 pdaEnd->next = p->qInfo; 551 for (trailer = NULL, pdp = p->qInfo; pdp;) { 552 trailer = pdp; 553 pdp = pdp->next; 554 count++; 555 } 556 if (trailer) 557 pdaEnd = trailer; 558 559 if (!pdaList) 560 pdaList = p->parityInfo; 561 else 562 pdaEnd->next = p->parityInfo; 563 for (trailer = NULL, pdp = p->parityInfo; pdp;) { 564 trailer = pdp; 565 pdp = pdp->next; 566 count++; 567 } 568 if (trailer) 569 pdaEnd = trailer; 570 571 if (!pdaList) 572 pdaList = p->physInfo; 573 else 574 pdaEnd->next = p->physInfo; 575 for (trailer = NULL, pdp = p->physInfo; pdp;) { 576 trailer = pdp; 577 pdp = pdp->next; 578 count++; 579 } 580 if (trailer) 581 pdaEnd = trailer; 582 583 pt = p; 584 asm_count++; 585 } 586 587 /* debug only */ 588 for (t = 0, pdp = pdaList; pdp; pdp = pdp->next) 589 t++; 590 RF_ASSERT(t == count); 591 592 if (pdaList) 593 rf_FreePDAList(pdaList, pdaEnd, count); 594 rf_FreeASMList(hdr->stripeMap, pt, asm_count); 595 rf_FreeAccessStripeMapHeader(hdr); 596 } 597 /* We can't use the large write optimization if there are any failures in the stripe. 598 * In the declustered layout, there is no way to immediately determine what disks 599 * constitute a stripe, so we actually have to hunt through the stripe looking for failures. 600 * The reason we map the parity instead of just using asm->parityInfo->col is because 601 * the latter may have been already redirected to a spare drive, which would 602 * mess up the computation of the stripe offset. 603 * 604 * ASSUMES AT MOST ONE FAILURE IN THE STRIPE. 605 */ 606 int 607 rf_CheckStripeForFailures(raidPtr, asmap) 608 RF_Raid_t *raidPtr; 609 RF_AccessStripeMap_t *asmap; 610 { 611 RF_RowCol_t trow, tcol, prow, pcol, *diskids, row, i; 612 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 613 RF_StripeCount_t stripeOffset; 614 int numFailures; 615 RF_RaidAddr_t sosAddr; 616 RF_SectorNum_t diskOffset, poffset; 617 RF_RowCol_t testrow; 618 619 /* quick out in the fault-free case. */ 620 RF_LOCK_MUTEX(raidPtr->mutex); 621 numFailures = raidPtr->numFailures; 622 RF_UNLOCK_MUTEX(raidPtr->mutex); 623 if (numFailures == 0) 624 return (0); 625 626 sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress); 627 row = asmap->physInfo->row; 628 (layoutPtr->map->IdentifyStripe) (raidPtr, asmap->raidAddress, &diskids, &testrow); 629 (layoutPtr->map->MapParity) (raidPtr, asmap->raidAddress, &prow, &pcol, &poffset, 0); /* get pcol */ 630 631 /* this need not be true if we've redirected the access to a spare in 632 * another row RF_ASSERT(row == testrow); */ 633 stripeOffset = 0; 634 for (i = 0; i < layoutPtr->numDataCol + layoutPtr->numParityCol; i++) { 635 if (diskids[i] != pcol) { 636 if (RF_DEAD_DISK(raidPtr->Disks[testrow][diskids[i]].status)) { 637 if (raidPtr->status[testrow] != rf_rs_reconstructing) 638 return (1); 639 RF_ASSERT(raidPtr->reconControl[testrow]->fcol == diskids[i]); 640 layoutPtr->map->MapSector(raidPtr, 641 sosAddr + stripeOffset * layoutPtr->sectorsPerStripeUnit, 642 &trow, &tcol, &diskOffset, 0); 643 RF_ASSERT((trow == testrow) && (tcol == diskids[i])); 644 if (!rf_CheckRUReconstructed(raidPtr->reconControl[testrow]->reconMap, diskOffset)) 645 return (1); 646 asmap->flags |= RF_ASM_REDIR_LARGE_WRITE; 647 return (0); 648 } 649 stripeOffset++; 650 } 651 } 652 return (0); 653 } 654 /* 655 return the number of failed data units in the stripe. 656 */ 657 658 int 659 rf_NumFailedDataUnitsInStripe(raidPtr, asmap) 660 RF_Raid_t *raidPtr; 661 RF_AccessStripeMap_t *asmap; 662 { 663 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 664 RF_RowCol_t trow, tcol, row, i; 665 RF_SectorNum_t diskOffset; 666 RF_RaidAddr_t sosAddr; 667 int numFailures; 668 669 /* quick out in the fault-free case. */ 670 RF_LOCK_MUTEX(raidPtr->mutex); 671 numFailures = raidPtr->numFailures; 672 RF_UNLOCK_MUTEX(raidPtr->mutex); 673 if (numFailures == 0) 674 return (0); 675 numFailures = 0; 676 677 sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, asmap->raidAddress); 678 row = asmap->physInfo->row; 679 for (i = 0; i < layoutPtr->numDataCol; i++) { 680 (layoutPtr->map->MapSector) (raidPtr, sosAddr + i * layoutPtr->sectorsPerStripeUnit, 681 &trow, &tcol, &diskOffset, 0); 682 if (RF_DEAD_DISK(raidPtr->Disks[trow][tcol].status)) 683 numFailures++; 684 } 685 686 return numFailures; 687 } 688 689 690 /***************************************************************************************** 691 * 692 * debug routines 693 * 694 ****************************************************************************************/ 695 696 void 697 rf_PrintAccessStripeMap(asm_h) 698 RF_AccessStripeMapHeader_t *asm_h; 699 { 700 rf_PrintFullAccessStripeMap(asm_h, 0); 701 } 702 703 void 704 rf_PrintFullAccessStripeMap(asm_h, prbuf) 705 RF_AccessStripeMapHeader_t *asm_h; 706 int prbuf; /* flag to print buffer pointers */ 707 { 708 int i; 709 RF_AccessStripeMap_t *asmap = asm_h->stripeMap; 710 RF_PhysDiskAddr_t *p; 711 printf("%d stripes total\n", (int) asm_h->numStripes); 712 for (; asmap; asmap = asmap->next) { 713 /* printf("Num failures: %d\n",asmap->numDataFailed); */ 714 /* printf("Num sectors: 715 * %d\n",(int)asmap->totalSectorsAccessed); */ 716 printf("Stripe %d (%d sectors), failures: %d data, %d parity: ", 717 (int) asmap->stripeID, 718 (int) asmap->totalSectorsAccessed, 719 (int) asmap->numDataFailed, 720 (int) asmap->numParityFailed); 721 if (asmap->parityInfo) { 722 printf("Parity [r%d c%d s%d-%d", asmap->parityInfo->row, asmap->parityInfo->col, 723 (int) asmap->parityInfo->startSector, 724 (int) (asmap->parityInfo->startSector + 725 asmap->parityInfo->numSector - 1)); 726 if (prbuf) 727 printf(" b0x%lx", (unsigned long) asmap->parityInfo->bufPtr); 728 if (asmap->parityInfo->next) { 729 printf(", r%d c%d s%d-%d", asmap->parityInfo->next->row, 730 asmap->parityInfo->next->col, 731 (int) asmap->parityInfo->next->startSector, 732 (int) (asmap->parityInfo->next->startSector + 733 asmap->parityInfo->next->numSector - 1)); 734 if (prbuf) 735 printf(" b0x%lx", (unsigned long) asmap->parityInfo->next->bufPtr); 736 RF_ASSERT(asmap->parityInfo->next->next == NULL); 737 } 738 printf("]\n\t"); 739 } 740 for (i = 0, p = asmap->physInfo; p; p = p->next, i++) { 741 printf("SU r%d c%d s%d-%d ", p->row, p->col, (int) p->startSector, 742 (int) (p->startSector + p->numSector - 1)); 743 if (prbuf) 744 printf("b0x%lx ", (unsigned long) p->bufPtr); 745 if (i && !(i & 1)) 746 printf("\n\t"); 747 } 748 printf("\n"); 749 p = asm_h->stripeMap->failedPDAs[0]; 750 if (asm_h->stripeMap->numDataFailed + asm_h->stripeMap->numParityFailed > 1) 751 printf("[multiple failures]\n"); 752 else 753 if (asm_h->stripeMap->numDataFailed + asm_h->stripeMap->numParityFailed > 0) 754 printf("\t[Failed PDA: r%d c%d s%d-%d]\n", p->row, p->col, 755 (int) p->startSector, (int) (p->startSector + p->numSector - 1)); 756 } 757 } 758 759 void 760 rf_PrintRaidAddressInfo(raidPtr, raidAddr, numBlocks) 761 RF_Raid_t *raidPtr; 762 RF_RaidAddr_t raidAddr; 763 RF_SectorCount_t numBlocks; 764 { 765 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 766 RF_RaidAddr_t ra, sosAddr = rf_RaidAddressOfPrevStripeBoundary(layoutPtr, raidAddr); 767 768 printf("Raid addrs of SU boundaries from start of stripe to end of access:\n\t"); 769 for (ra = sosAddr; ra <= raidAddr + numBlocks; ra += layoutPtr->sectorsPerStripeUnit) { 770 printf("%d (0x%x), ", (int) ra, (int) ra); 771 } 772 printf("\n"); 773 printf("Offset into stripe unit: %d (0x%x)\n", 774 (int) (raidAddr % layoutPtr->sectorsPerStripeUnit), 775 (int) (raidAddr % layoutPtr->sectorsPerStripeUnit)); 776 } 777 /* 778 given a parity descriptor and the starting address within a stripe, 779 range restrict the parity descriptor to touch only the correct stuff. 780 */ 781 void 782 rf_ASMParityAdjust( 783 RF_PhysDiskAddr_t * toAdjust, 784 RF_StripeNum_t startAddrWithinStripe, 785 RF_SectorNum_t endAddress, 786 RF_RaidLayout_t * layoutPtr, 787 RF_AccessStripeMap_t * asm_p) 788 { 789 RF_PhysDiskAddr_t *new_pda; 790 791 /* when we're accessing only a portion of one stripe unit, we want the 792 * parity descriptor to identify only the chunk of parity associated 793 * with the data. When the access spans exactly one stripe unit 794 * boundary and is less than a stripe unit in size, it uses two 795 * disjoint regions of the parity unit. When an access spans more 796 * than one stripe unit boundary, it uses all of the parity unit. 797 * 798 * To better handle the case where stripe units are small, we may 799 * eventually want to change the 2nd case so that if the SU size is 800 * below some threshold, we just read/write the whole thing instead of 801 * breaking it up into two accesses. */ 802 if (asm_p->numStripeUnitsAccessed == 1) { 803 int x = (startAddrWithinStripe % layoutPtr->sectorsPerStripeUnit); 804 toAdjust->startSector += x; 805 toAdjust->raidAddress += x; 806 toAdjust->numSector = asm_p->physInfo->numSector; 807 RF_ASSERT(toAdjust->numSector != 0); 808 } else 809 if (asm_p->numStripeUnitsAccessed == 2 && asm_p->totalSectorsAccessed < layoutPtr->sectorsPerStripeUnit) { 810 int x = (startAddrWithinStripe % layoutPtr->sectorsPerStripeUnit); 811 812 /* create a second pda and copy the parity map info 813 * into it */ 814 RF_ASSERT(toAdjust->next == NULL); 815 new_pda = toAdjust->next = rf_AllocPhysDiskAddr(); 816 *new_pda = *toAdjust; /* structure assignment */ 817 new_pda->next = NULL; 818 819 /* adjust the start sector & number of blocks for the 820 * first parity pda */ 821 toAdjust->startSector += x; 822 toAdjust->raidAddress += x; 823 toAdjust->numSector = rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, startAddrWithinStripe) - startAddrWithinStripe; 824 RF_ASSERT(toAdjust->numSector != 0); 825 826 /* adjust the second pda */ 827 new_pda->numSector = endAddress - rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, endAddress); 828 /* new_pda->raidAddress = 829 * rf_RaidAddressOfNextStripeUnitBoundary(layoutPtr, 830 * toAdjust->raidAddress); */ 831 RF_ASSERT(new_pda->numSector != 0); 832 } 833 } 834 /* 835 Check if a disk has been spared or failed. If spared, 836 redirect the I/O. 837 If it has been failed, record it in the asm pointer. 838 Fourth arg is whether data or parity. 839 */ 840 void 841 rf_ASMCheckStatus( 842 RF_Raid_t * raidPtr, 843 RF_PhysDiskAddr_t * pda_p, 844 RF_AccessStripeMap_t * asm_p, 845 RF_RaidDisk_t ** disks, 846 int parity) 847 { 848 RF_DiskStatus_t dstatus; 849 RF_RowCol_t frow, fcol; 850 851 dstatus = disks[pda_p->row][pda_p->col].status; 852 853 if (dstatus == rf_ds_spared) { 854 /* if the disk has been spared, redirect access to the spare */ 855 frow = pda_p->row; 856 fcol = pda_p->col; 857 pda_p->row = disks[frow][fcol].spareRow; 858 pda_p->col = disks[frow][fcol].spareCol; 859 } else 860 if (dstatus == rf_ds_dist_spared) { 861 /* ditto if disk has been spared to dist spare space */ 862 RF_RowCol_t or = pda_p->row, oc = pda_p->col; 863 RF_SectorNum_t oo = pda_p->startSector; 864 865 if (pda_p->type == RF_PDA_TYPE_DATA) 866 raidPtr->Layout.map->MapSector(raidPtr, pda_p->raidAddress, &pda_p->row, &pda_p->col, &pda_p->startSector, RF_REMAP); 867 else 868 raidPtr->Layout.map->MapParity(raidPtr, pda_p->raidAddress, &pda_p->row, &pda_p->col, &pda_p->startSector, RF_REMAP); 869 870 if (rf_mapDebug) { 871 printf("Redirected r %d c %d o %d -> r%d c %d o %d\n", or, oc, (int) oo, 872 pda_p->row, pda_p->col, (int) pda_p->startSector); 873 } 874 } else 875 if (RF_DEAD_DISK(dstatus)) { 876 /* if the disk is inaccessible, mark the 877 * failure */ 878 if (parity) 879 asm_p->numParityFailed++; 880 else { 881 asm_p->numDataFailed++; 882 #if 0 883 /* XXX Do we really want this spewing 884 * out on the console? GO */ 885 printf("DATA_FAILED!\n"); 886 #endif 887 } 888 asm_p->failedPDAs[asm_p->numFailedPDAs] = pda_p; 889 asm_p->numFailedPDAs++; 890 #if 0 891 switch (asm_p->numParityFailed + asm_p->numDataFailed) { 892 case 1: 893 asm_p->failedPDAs[0] = pda_p; 894 break; 895 case 2: 896 asm_p->failedPDAs[1] = pda_p; 897 default: 898 break; 899 } 900 #endif 901 } 902 /* the redirected access should never span a stripe unit boundary */ 903 RF_ASSERT(rf_RaidAddressToStripeUnitID(&raidPtr->Layout, pda_p->raidAddress) == 904 rf_RaidAddressToStripeUnitID(&raidPtr->Layout, pda_p->raidAddress + pda_p->numSector - 1)); 905 RF_ASSERT(pda_p->col != -1); 906 } 907