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