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