1 /* $NetBSD: rf_interdecluster.c,v 1.1 1998/11/13 04:20:30 oster Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Author: Khalil Amiri 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_interdecluster.c -- implements interleaved declustering 32 * 33 ************************************************************/ 34 35 /* : 36 * Log: rf_interdecluster.c,v 37 * Revision 1.24 1996/08/02 13:20:38 jimz 38 * get rid of bogus (long) casts 39 * 40 * Revision 1.23 1996/07/31 16:56:18 jimz 41 * dataBytesPerStripe, sectorsPerDisk init arch-indep. 42 * 43 * Revision 1.22 1996/07/29 14:05:12 jimz 44 * fix numPUs/numRUs confusion (everything is now numRUs) 45 * clean up some commenting, return values 46 * 47 * Revision 1.21 1996/07/22 19:52:16 jimz 48 * switched node params to RF_DagParam_t, a union of 49 * a 64-bit int and a void *, for better portability 50 * attempted hpux port, but failed partway through for 51 * lack of a single C compiler capable of compiling all 52 * source files 53 * 54 * Revision 1.20 1996/07/18 22:57:14 jimz 55 * port simulator to AIX 56 * 57 * Revision 1.19 1996/07/13 00:00:59 jimz 58 * sanitized generalized reconstruction architecture 59 * cleaned up head sep, rbuf problems 60 * 61 * Revision 1.18 1996/06/19 17:53:48 jimz 62 * move GetNumSparePUs, InstallSpareTable ops into layout switch 63 * 64 * Revision 1.17 1996/06/11 15:17:55 wvcii 65 * added include of rf_interdecluster.h 66 * fixed parameter list of rf_ConfigureInterDecluster 67 * fixed return type of rf_GetNumSparePUsInterDecluster 68 * removed include of rf_raid1.h 69 * 70 * Revision 1.16 1996/06/11 08:55:15 jimz 71 * improved error-checking at configuration time 72 * 73 * Revision 1.15 1996/06/10 11:55:47 jimz 74 * Straightened out some per-array/not-per-array distinctions, fixed 75 * a couple bugs related to confusion. Added shutdown lists. Removed 76 * layout shutdown function (now subsumed by shutdown lists). 77 * 78 * Revision 1.14 1996/06/07 22:26:27 jimz 79 * type-ify which_ru (RF_ReconUnitNum_t) 80 * 81 * Revision 1.13 1996/06/07 21:33:04 jimz 82 * begin using consistent types for sector numbers, 83 * stripe numbers, row+col numbers, recon unit numbers 84 * 85 * Revision 1.12 1996/06/06 18:41:48 jimz 86 * add interleaved declustering dag selection 87 * 88 * Revision 1.11 1996/06/02 17:31:48 jimz 89 * Moved a lot of global stuff into array structure, where it belongs. 90 * Fixed up paritylogging, pss modules in this manner. Some general 91 * code cleanup. Removed lots of dead code, some dead files. 92 * 93 * Revision 1.10 1996/05/31 22:26:54 jimz 94 * fix a lot of mapping problems, memory allocation problems 95 * found some weird lock issues, fixed 'em 96 * more code cleanup 97 * 98 * Revision 1.9 1996/05/31 05:03:01 amiri 99 * fixed a bug related to sparing layout. 100 * 101 * Revision 1.8 1996/05/27 18:56:37 jimz 102 * more code cleanup 103 * better typing 104 * compiles in all 3 environments 105 * 106 * Revision 1.7 1996/05/24 01:59:45 jimz 107 * another checkpoint in code cleanup for release 108 * time to sync kernel tree 109 * 110 * Revision 1.6 1996/05/23 00:33:23 jimz 111 * code cleanup: move all debug decls to rf_options.c, all extern 112 * debug decls to rf_options.h, all debug vars preceded by rf_ 113 * 114 * Revision 1.5 1996/05/18 19:51:34 jimz 115 * major code cleanup- fix syntax, make some types consistent, 116 * add prototypes, clean out dead code, et cetera 117 * 118 * Revision 1.4 1996/05/03 19:50:38 wvcii 119 * removed include of rf_redstripe.h 120 * fixed change log parameters in header 121 * 122 */ 123 124 #include "rf_types.h" 125 #include "rf_raid.h" 126 #include "rf_interdecluster.h" 127 #include "rf_dag.h" 128 #include "rf_dagutils.h" 129 #include "rf_dagfuncs.h" 130 #include "rf_threadid.h" 131 #include "rf_general.h" 132 #include "rf_utils.h" 133 #include "rf_dagffrd.h" 134 #include "rf_dagdegrd.h" 135 #include "rf_dagffwr.h" 136 #include "rf_dagdegwr.h" 137 138 typedef struct RF_InterdeclusterConfigInfo_s { 139 RF_RowCol_t **stripeIdentifier; /* filled in at config time 140 * and used by IdentifyStripe */ 141 RF_StripeCount_t numSparingRegions; 142 RF_StripeCount_t stripeUnitsPerSparingRegion; 143 RF_SectorNum_t mirrorStripeOffset; 144 } RF_InterdeclusterConfigInfo_t; 145 146 int rf_ConfigureInterDecluster( 147 RF_ShutdownList_t **listp, 148 RF_Raid_t *raidPtr, 149 RF_Config_t *cfgPtr) 150 { 151 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 152 RF_StripeCount_t num_used_stripeUnitsPerDisk; 153 RF_InterdeclusterConfigInfo_t *info; 154 RF_RowCol_t i, tmp, SUs_per_region; 155 156 /* create an Interleaved Declustering configuration structure */ 157 RF_MallocAndAdd(info, sizeof(RF_InterdeclusterConfigInfo_t), (RF_InterdeclusterConfigInfo_t *), 158 raidPtr->cleanupList); 159 if (info == NULL) 160 return(ENOMEM); 161 layoutPtr->layoutSpecificInfo = (void *) info; 162 163 /* fill in the config structure. */ 164 SUs_per_region = raidPtr->numCol * (raidPtr->numCol - 1); 165 info->stripeIdentifier = rf_make_2d_array(SUs_per_region, 2 , raidPtr->cleanupList); 166 if (info->stripeIdentifier == NULL) 167 return(ENOMEM); 168 for (i=0; i< SUs_per_region; i++) { 169 info->stripeIdentifier[i][0] = i / (raidPtr->numCol-1); 170 tmp = i / raidPtr->numCol; 171 info->stripeIdentifier[i][1] = (i+1+tmp) % raidPtr->numCol; 172 } 173 174 /* no spare tables */ 175 RF_ASSERT(raidPtr->numRow == 1); 176 177 /* fill in the remaining layout parameters */ 178 179 /* total number of stripes should a multiple of 2*numCol: Each sparing region consists of 180 2*numCol stripes: n-1 primary copy, n-1 secondary copy and 2 for spare .. */ 181 num_used_stripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk - (layoutPtr->stripeUnitsPerDisk % 182 (2*raidPtr->numCol) ); 183 info->numSparingRegions = num_used_stripeUnitsPerDisk / (2*raidPtr->numCol); 184 /* this is in fact the number of stripe units (that are primary data copies) in the sparing region */ 185 info->stripeUnitsPerSparingRegion = raidPtr->numCol * (raidPtr->numCol - 1); 186 info->mirrorStripeOffset = info->numSparingRegions * (raidPtr->numCol+1); 187 layoutPtr->numStripe = info->numSparingRegions * info->stripeUnitsPerSparingRegion; 188 layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit << raidPtr->logBytesPerSector; 189 layoutPtr->numDataCol = 1; 190 layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; 191 layoutPtr->numParityCol = 1; 192 193 layoutPtr->dataStripeUnitsPerDisk = num_used_stripeUnitsPerDisk; 194 195 raidPtr->sectorsPerDisk = 196 num_used_stripeUnitsPerDisk * layoutPtr->sectorsPerStripeUnit; 197 198 raidPtr->totalSectors = 199 (layoutPtr->numStripe) * layoutPtr->sectorsPerStripeUnit; 200 201 layoutPtr->stripeUnitsPerDisk = raidPtr->sectorsPerDisk / layoutPtr->sectorsPerStripeUnit; 202 203 return(0); 204 } 205 206 int rf_GetDefaultNumFloatingReconBuffersInterDecluster(RF_Raid_t *raidPtr) 207 { 208 return(30); 209 } 210 211 RF_HeadSepLimit_t rf_GetDefaultHeadSepLimitInterDecluster(RF_Raid_t *raidPtr) 212 { 213 return(raidPtr->sectorsPerDisk); 214 } 215 216 RF_ReconUnitCount_t rf_GetNumSpareRUsInterDecluster( 217 RF_Raid_t *raidPtr) 218 { 219 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 220 221 return ( 2 * ((RF_ReconUnitCount_t) info->numSparingRegions) ); 222 /* the layout uses two stripe units per disk as spare within each sparing region */ 223 } 224 225 /* Maps to the primary copy of the data, i.e. the first mirror pair */ 226 void rf_MapSectorInterDecluster( 227 RF_Raid_t *raidPtr, 228 RF_RaidAddr_t raidSector, 229 RF_RowCol_t *row, 230 RF_RowCol_t *col, 231 RF_SectorNum_t *diskSector, 232 int remap) 233 { 234 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 235 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 236 RF_StripeNum_t su_offset_into_disk, mirror_su_offset_into_disk; 237 RF_StripeNum_t sparing_region_id, index_within_region; 238 int col_before_remap; 239 240 *row = 0; 241 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion; 242 index_within_region = SUID % info->stripeUnitsPerSparingRegion; 243 su_offset_into_disk = index_within_region % (raidPtr->numCol-1); 244 mirror_su_offset_into_disk = index_within_region / raidPtr->numCol; 245 col_before_remap = index_within_region / (raidPtr->numCol-1); 246 247 if (!remap) { 248 *col = col_before_remap;; 249 *diskSector = ( su_offset_into_disk + ( (raidPtr->numCol-1) * sparing_region_id) ) * 250 raidPtr->Layout.sectorsPerStripeUnit; 251 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 252 } 253 else { 254 /* remap sector to spare space...*/ 255 *diskSector = sparing_region_id * (raidPtr->numCol+1) * raidPtr->Layout.sectorsPerStripeUnit; 256 *diskSector += (raidPtr->numCol-1) * raidPtr->Layout.sectorsPerStripeUnit; 257 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 258 *col = (index_within_region + 1 + mirror_su_offset_into_disk) % raidPtr->numCol; 259 *col = (*col + 1) % raidPtr->numCol; 260 if (*col == col_before_remap) *col = (*col + 1) % raidPtr->numCol; 261 } 262 } 263 264 /* Maps to the second copy of the mirror pair. */ 265 void rf_MapParityInterDecluster( 266 RF_Raid_t *raidPtr, 267 RF_RaidAddr_t raidSector, 268 RF_RowCol_t *row, 269 RF_RowCol_t *col, 270 RF_SectorNum_t *diskSector, 271 int remap) 272 { 273 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 274 RF_StripeNum_t sparing_region_id, index_within_region, mirror_su_offset_into_disk; 275 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 276 int col_before_remap; 277 278 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion; 279 index_within_region = SUID % info->stripeUnitsPerSparingRegion; 280 mirror_su_offset_into_disk = index_within_region / raidPtr->numCol; 281 col_before_remap = (index_within_region + 1 + mirror_su_offset_into_disk) % raidPtr->numCol; 282 283 *row = 0; 284 if (!remap) { 285 *col = col_before_remap; 286 *diskSector = info->mirrorStripeOffset * raidPtr->Layout.sectorsPerStripeUnit; 287 *diskSector += sparing_region_id * (raidPtr->numCol-1) * raidPtr->Layout.sectorsPerStripeUnit; 288 *diskSector += mirror_su_offset_into_disk * raidPtr->Layout.sectorsPerStripeUnit; 289 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 290 } 291 else { 292 /* remap parity to spare space ... */ 293 *diskSector = sparing_region_id * (raidPtr->numCol+1) * raidPtr->Layout.sectorsPerStripeUnit; 294 *diskSector += (raidPtr->numCol) * raidPtr->Layout.sectorsPerStripeUnit; 295 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 296 *col = index_within_region / (raidPtr->numCol-1); 297 *col = (*col + 1) % raidPtr->numCol; 298 if (*col == col_before_remap) *col = (*col + 1) % raidPtr->numCol; 299 } 300 } 301 302 void rf_IdentifyStripeInterDecluster( 303 RF_Raid_t *raidPtr, 304 RF_RaidAddr_t addr, 305 RF_RowCol_t **diskids, 306 RF_RowCol_t *outRow) 307 { 308 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 309 RF_StripeNum_t SUID; 310 311 SUID = addr / raidPtr->Layout.sectorsPerStripeUnit; 312 SUID = SUID % info->stripeUnitsPerSparingRegion; 313 314 *outRow = 0; 315 *diskids = info->stripeIdentifier[ SUID ]; 316 } 317 318 void rf_MapSIDToPSIDInterDecluster( 319 RF_RaidLayout_t *layoutPtr, 320 RF_StripeNum_t stripeID, 321 RF_StripeNum_t *psID, 322 RF_ReconUnitNum_t *which_ru) 323 { 324 *which_ru = 0; 325 *psID = stripeID; 326 } 327 328 /****************************************************************************** 329 * select a graph to perform a single-stripe access 330 * 331 * Parameters: raidPtr - description of the physical array 332 * type - type of operation (read or write) requested 333 * asmap - logical & physical addresses for this access 334 * createFunc - name of function to use to create the graph 335 *****************************************************************************/ 336 337 void rf_RAIDIDagSelect( 338 RF_Raid_t *raidPtr, 339 RF_IoType_t type, 340 RF_AccessStripeMap_t *asmap, 341 RF_VoidFuncPtr *createFunc) 342 { 343 RF_ASSERT(RF_IO_IS_R_OR_W(type)); 344 345 if (asmap->numDataFailed + asmap->numParityFailed > 1) { 346 RF_ERRORMSG("Multiple disks failed in a single group! Aborting I/O operation.\n"); 347 *createFunc = NULL; 348 return; 349 } 350 351 *createFunc = (type == RF_IO_TYPE_READ) ? (RF_VoidFuncPtr)rf_CreateFaultFreeReadDAG : (RF_VoidFuncPtr)rf_CreateRaidOneWriteDAG; 352 if (type == RF_IO_TYPE_READ) { 353 if (asmap->numDataFailed == 0) 354 *createFunc = (RF_VoidFuncPtr)rf_CreateMirrorPartitionReadDAG; 355 else 356 *createFunc = (RF_VoidFuncPtr)rf_CreateRaidOneDegradedReadDAG; 357 } 358 else 359 *createFunc = (RF_VoidFuncPtr)rf_CreateRaidOneWriteDAG; 360 } 361