1 /* $NetBSD: rf_raid5.c,v 1.4 2000/01/08 22:57:30 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 * rf_raid5.c -- implements RAID Level 5 32 * 33 *****************************************************************************/ 34 35 #include "rf_types.h" 36 #include "rf_raid.h" 37 #include "rf_raid5.h" 38 #include "rf_dag.h" 39 #include "rf_dagffrd.h" 40 #include "rf_dagffwr.h" 41 #include "rf_dagdegrd.h" 42 #include "rf_dagdegwr.h" 43 #include "rf_dagutils.h" 44 #include "rf_general.h" 45 #include "rf_map.h" 46 #include "rf_utils.h" 47 48 typedef struct RF_Raid5ConfigInfo_s { 49 RF_RowCol_t **stripeIdentifier; /* filled in at config time and used 50 * by IdentifyStripe */ 51 } RF_Raid5ConfigInfo_t; 52 53 int 54 rf_ConfigureRAID5( 55 RF_ShutdownList_t ** listp, 56 RF_Raid_t * raidPtr, 57 RF_Config_t * cfgPtr) 58 { 59 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 60 RF_Raid5ConfigInfo_t *info; 61 RF_RowCol_t i, j, startdisk; 62 63 /* create a RAID level 5 configuration structure */ 64 RF_MallocAndAdd(info, sizeof(RF_Raid5ConfigInfo_t), (RF_Raid5ConfigInfo_t *), raidPtr->cleanupList); 65 if (info == NULL) 66 return (ENOMEM); 67 layoutPtr->layoutSpecificInfo = (void *) info; 68 69 RF_ASSERT(raidPtr->numRow == 1); 70 71 /* the stripe identifier must identify the disks in each stripe, IN 72 * THE ORDER THAT THEY APPEAR IN THE STRIPE. */ 73 info->stripeIdentifier = rf_make_2d_array(raidPtr->numCol, raidPtr->numCol, raidPtr->cleanupList); 74 if (info->stripeIdentifier == NULL) 75 return (ENOMEM); 76 startdisk = 0; 77 for (i = 0; i < raidPtr->numCol; i++) { 78 for (j = 0; j < raidPtr->numCol; j++) { 79 info->stripeIdentifier[i][j] = (startdisk + j) % raidPtr->numCol; 80 } 81 if ((--startdisk) < 0) 82 startdisk = raidPtr->numCol - 1; 83 } 84 85 /* fill in the remaining layout parameters */ 86 layoutPtr->numStripe = layoutPtr->stripeUnitsPerDisk; 87 layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit << raidPtr->logBytesPerSector; 88 layoutPtr->numDataCol = raidPtr->numCol - 1; 89 layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; 90 layoutPtr->numParityCol = 1; 91 layoutPtr->dataStripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk; 92 93 raidPtr->totalSectors = layoutPtr->stripeUnitsPerDisk * layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; 94 95 return (0); 96 } 97 98 int 99 rf_GetDefaultNumFloatingReconBuffersRAID5(RF_Raid_t * raidPtr) 100 { 101 return (20); 102 } 103 104 RF_HeadSepLimit_t 105 rf_GetDefaultHeadSepLimitRAID5(RF_Raid_t * raidPtr) 106 { 107 return (10); 108 } 109 #if !defined(__NetBSD__) && !defined(_KERNEL) 110 /* not currently used */ 111 int 112 rf_ShutdownRAID5(RF_Raid_t * raidPtr) 113 { 114 return (0); 115 } 116 #endif 117 118 void 119 rf_MapSectorRAID5( 120 RF_Raid_t * raidPtr, 121 RF_RaidAddr_t raidSector, 122 RF_RowCol_t * row, 123 RF_RowCol_t * col, 124 RF_SectorNum_t * diskSector, 125 int remap) 126 { 127 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 128 *row = 0; 129 *col = (SUID % raidPtr->numCol); 130 *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit + 131 (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 132 } 133 134 void 135 rf_MapParityRAID5( 136 RF_Raid_t * raidPtr, 137 RF_RaidAddr_t raidSector, 138 RF_RowCol_t * row, 139 RF_RowCol_t * col, 140 RF_SectorNum_t * diskSector, 141 int remap) 142 { 143 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 144 145 *row = 0; 146 *col = raidPtr->Layout.numDataCol - (SUID / raidPtr->Layout.numDataCol) % raidPtr->numCol; 147 *diskSector = (SUID / (raidPtr->Layout.numDataCol)) * raidPtr->Layout.sectorsPerStripeUnit + 148 (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 149 } 150 151 void 152 rf_IdentifyStripeRAID5( 153 RF_Raid_t * raidPtr, 154 RF_RaidAddr_t addr, 155 RF_RowCol_t ** diskids, 156 RF_RowCol_t * outRow) 157 { 158 RF_StripeNum_t stripeID = rf_RaidAddressToStripeID(&raidPtr->Layout, addr); 159 RF_Raid5ConfigInfo_t *info = (RF_Raid5ConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 160 161 *outRow = 0; 162 *diskids = info->stripeIdentifier[stripeID % raidPtr->numCol]; 163 } 164 165 void 166 rf_MapSIDToPSIDRAID5( 167 RF_RaidLayout_t * layoutPtr, 168 RF_StripeNum_t stripeID, 169 RF_StripeNum_t * psID, 170 RF_ReconUnitNum_t * which_ru) 171 { 172 *which_ru = 0; 173 *psID = stripeID; 174 } 175 /* select an algorithm for performing an access. Returns two pointers, 176 * one to a function that will return information about the DAG, and 177 * another to a function that will create the dag. 178 */ 179 void 180 rf_RaidFiveDagSelect( 181 RF_Raid_t * raidPtr, 182 RF_IoType_t type, 183 RF_AccessStripeMap_t * asmap, 184 RF_VoidFuncPtr * createFunc) 185 { 186 RF_RaidLayout_t *layoutPtr = &(raidPtr->Layout); 187 RF_PhysDiskAddr_t *failedPDA = NULL; 188 RF_RowCol_t frow, fcol; 189 RF_RowStatus_t rstat; 190 int prior_recon; 191 192 RF_ASSERT(RF_IO_IS_R_OR_W(type)); 193 194 if (asmap->numDataFailed + asmap->numParityFailed > 1) { 195 RF_ERRORMSG("Multiple disks failed in a single group! Aborting I/O operation.\n"); 196 /* *infoFunc = */ *createFunc = NULL; 197 return; 198 } else 199 if (asmap->numDataFailed + asmap->numParityFailed == 1) { 200 201 /* if under recon & already reconstructed, redirect 202 * the access to the spare drive and eliminate the 203 * failure indication */ 204 failedPDA = asmap->failedPDAs[0]; 205 frow = failedPDA->row; 206 fcol = failedPDA->col; 207 rstat = raidPtr->status[failedPDA->row]; 208 prior_recon = (rstat == rf_rs_reconfigured) || ( 209 (rstat == rf_rs_reconstructing) ? 210 rf_CheckRUReconstructed(raidPtr->reconControl[frow]->reconMap, failedPDA->startSector) : 0 211 ); 212 if (prior_recon) { 213 RF_RowCol_t or = failedPDA->row, oc = failedPDA->col; 214 RF_SectorNum_t oo = failedPDA->startSector; 215 216 if (layoutPtr->map->flags & RF_DISTRIBUTE_SPARE) { /* redirect to dist 217 * spare space */ 218 219 if (failedPDA == asmap->parityInfo) { 220 221 /* parity has failed */ 222 (layoutPtr->map->MapParity) (raidPtr, failedPDA->raidAddress, &failedPDA->row, 223 &failedPDA->col, &failedPDA->startSector, RF_REMAP); 224 225 if (asmap->parityInfo->next) { /* redir 2nd component, 226 * if any */ 227 RF_PhysDiskAddr_t *p = asmap->parityInfo->next; 228 RF_SectorNum_t SUoffs = p->startSector % layoutPtr->sectorsPerStripeUnit; 229 p->row = failedPDA->row; 230 p->col = failedPDA->col; 231 p->startSector = rf_RaidAddressOfPrevStripeUnitBoundary(layoutPtr, failedPDA->startSector) + 232 SUoffs; /* cheating: 233 * startSector is not 234 * really a RAID address */ 235 } 236 } else 237 if (asmap->parityInfo->next && failedPDA == asmap->parityInfo->next) { 238 RF_ASSERT(0); /* should not ever 239 * happen */ 240 } else { 241 242 /* data has failed */ 243 (layoutPtr->map->MapSector) (raidPtr, failedPDA->raidAddress, &failedPDA->row, 244 &failedPDA->col, &failedPDA->startSector, RF_REMAP); 245 246 } 247 248 } else { /* redirect to dedicated spare 249 * space */ 250 251 failedPDA->row = raidPtr->Disks[frow][fcol].spareRow; 252 failedPDA->col = raidPtr->Disks[frow][fcol].spareCol; 253 254 /* the parity may have two distinct 255 * components, both of which may need 256 * to be redirected */ 257 if (asmap->parityInfo->next) { 258 if (failedPDA == asmap->parityInfo) { 259 failedPDA->next->row = failedPDA->row; 260 failedPDA->next->col = failedPDA->col; 261 } else 262 if (failedPDA == asmap->parityInfo->next) { /* paranoid: should 263 * never occur */ 264 asmap->parityInfo->row = failedPDA->row; 265 asmap->parityInfo->col = failedPDA->col; 266 } 267 } 268 } 269 270 RF_ASSERT(failedPDA->col != -1); 271 272 if (rf_dagDebug || rf_mapDebug) { 273 printf("raid%d: Redirected type '%c' r %d c %d o %ld -> r %d c %d o %ld\n", 274 raidPtr->raidid, type, or, oc, 275 (long) oo, failedPDA->row, 276 failedPDA->col, 277 (long) failedPDA->startSector); 278 } 279 asmap->numDataFailed = asmap->numParityFailed = 0; 280 } 281 } 282 /* all dags begin/end with block/unblock node therefore, hdrSucc & 283 * termAnt counts should always be 1 also, these counts should not be 284 * visible outside dag creation routines - manipulating the counts 285 * here should be removed */ 286 if (type == RF_IO_TYPE_READ) { 287 if (asmap->numDataFailed == 0) 288 *createFunc = (RF_VoidFuncPtr) rf_CreateFaultFreeReadDAG; 289 else 290 *createFunc = (RF_VoidFuncPtr) rf_CreateRaidFiveDegradedReadDAG; 291 } else { 292 293 294 /* if mirroring, always use large writes. If the access 295 * requires two distinct parity updates, always do a small 296 * write. If the stripe contains a failure but the access 297 * does not, do a small write. The first conditional 298 * (numStripeUnitsAccessed <= numDataCol/2) uses a 299 * less-than-or-equal rather than just a less-than because 300 * when G is 3 or 4, numDataCol/2 is 1, and I want 301 * single-stripe-unit updates to use just one disk. */ 302 if ((asmap->numDataFailed + asmap->numParityFailed) == 0) { 303 if (rf_suppressLocksAndLargeWrites || 304 (((asmap->numStripeUnitsAccessed <= (layoutPtr->numDataCol / 2)) && (layoutPtr->numDataCol != 1)) || 305 (asmap->parityInfo->next != NULL) || rf_CheckStripeForFailures(raidPtr, asmap))) { 306 *createFunc = (RF_VoidFuncPtr) rf_CreateSmallWriteDAG; 307 } else 308 *createFunc = (RF_VoidFuncPtr) rf_CreateLargeWriteDAG; 309 } else { 310 if (asmap->numParityFailed == 1) 311 *createFunc = (RF_VoidFuncPtr) rf_CreateNonRedundantWriteDAG; 312 else 313 if (asmap->numStripeUnitsAccessed != 1 && failedPDA->numSector != layoutPtr->sectorsPerStripeUnit) 314 *createFunc = NULL; 315 else 316 *createFunc = (RF_VoidFuncPtr) rf_CreateDegradedWriteDAG; 317 } 318 } 319 } 320