1 /* $NetBSD: rf_chaindecluster.c,v 1.6 2001/01/26 04:27:16 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_chaindecluster.c -- implements chained declustering 32 * 33 *****************************************************************************/ 34 35 #include "rf_archs.h" 36 37 #if (RF_INCLUDE_CHAINDECLUSTER > 0) 38 39 #include "rf_types.h" 40 #include "rf_raid.h" 41 #include "rf_chaindecluster.h" 42 #include "rf_dag.h" 43 #include "rf_dagutils.h" 44 #include "rf_dagffrd.h" 45 #include "rf_dagffwr.h" 46 #include "rf_dagdegrd.h" 47 #include "rf_dagfuncs.h" 48 #include "rf_general.h" 49 #include "rf_utils.h" 50 51 typedef struct RF_ChaindeclusterConfigInfo_s { 52 RF_RowCol_t **stripeIdentifier; /* filled in at config time and used 53 * by IdentifyStripe */ 54 RF_StripeCount_t numSparingRegions; 55 RF_StripeCount_t stripeUnitsPerSparingRegion; 56 RF_SectorNum_t mirrorStripeOffset; 57 } RF_ChaindeclusterConfigInfo_t; 58 59 int 60 rf_ConfigureChainDecluster( 61 RF_ShutdownList_t ** listp, 62 RF_Raid_t * raidPtr, 63 RF_Config_t * cfgPtr) 64 { 65 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 66 RF_StripeCount_t num_used_stripeUnitsPerDisk; 67 RF_ChaindeclusterConfigInfo_t *info; 68 RF_RowCol_t i; 69 70 /* create a Chained Declustering configuration structure */ 71 RF_MallocAndAdd(info, sizeof(RF_ChaindeclusterConfigInfo_t), (RF_ChaindeclusterConfigInfo_t *), raidPtr->cleanupList); 72 if (info == NULL) 73 return (ENOMEM); 74 layoutPtr->layoutSpecificInfo = (void *) info; 75 76 /* fill in the config structure. */ 77 info->stripeIdentifier = rf_make_2d_array(raidPtr->numCol, 2, raidPtr->cleanupList); 78 if (info->stripeIdentifier == NULL) 79 return (ENOMEM); 80 for (i = 0; i < raidPtr->numCol; i++) { 81 info->stripeIdentifier[i][0] = i % raidPtr->numCol; 82 info->stripeIdentifier[i][1] = (i + 1) % raidPtr->numCol; 83 } 84 85 RF_ASSERT(raidPtr->numRow == 1); 86 87 /* fill in the remaining layout parameters */ 88 num_used_stripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk - (layoutPtr->stripeUnitsPerDisk % 89 (2 * raidPtr->numCol - 2)); 90 info->numSparingRegions = num_used_stripeUnitsPerDisk / (2 * raidPtr->numCol - 2); 91 info->stripeUnitsPerSparingRegion = raidPtr->numCol * (raidPtr->numCol - 1); 92 info->mirrorStripeOffset = info->numSparingRegions * (raidPtr->numCol - 1); 93 layoutPtr->numStripe = info->numSparingRegions * info->stripeUnitsPerSparingRegion; 94 layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit << raidPtr->logBytesPerSector; 95 layoutPtr->numDataCol = 1; 96 layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol * layoutPtr->sectorsPerStripeUnit; 97 layoutPtr->numParityCol = 1; 98 99 layoutPtr->dataStripeUnitsPerDisk = num_used_stripeUnitsPerDisk; 100 101 raidPtr->sectorsPerDisk = 102 num_used_stripeUnitsPerDisk * layoutPtr->sectorsPerStripeUnit; 103 104 raidPtr->totalSectors = 105 (layoutPtr->numStripe) * layoutPtr->sectorsPerStripeUnit; 106 107 layoutPtr->stripeUnitsPerDisk = raidPtr->sectorsPerDisk / layoutPtr->sectorsPerStripeUnit; 108 109 return (0); 110 } 111 112 RF_ReconUnitCount_t 113 rf_GetNumSpareRUsChainDecluster(raidPtr) 114 RF_Raid_t *raidPtr; 115 { 116 RF_ChaindeclusterConfigInfo_t *info = (RF_ChaindeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 117 118 /* 119 * The layout uses two stripe units per disk as spare within each 120 * sparing region. 121 */ 122 return (2 * info->numSparingRegions); 123 } 124 125 126 /* Maps to the primary copy of the data, i.e. the first mirror pair */ 127 void 128 rf_MapSectorChainDecluster( 129 RF_Raid_t * raidPtr, 130 RF_RaidAddr_t raidSector, 131 RF_RowCol_t * row, 132 RF_RowCol_t * col, 133 RF_SectorNum_t * diskSector, 134 int remap) 135 { 136 RF_ChaindeclusterConfigInfo_t *info = (RF_ChaindeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 137 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 138 RF_SectorNum_t index_within_region, index_within_disk; 139 RF_StripeNum_t sparing_region_id; 140 int col_before_remap; 141 142 *row = 0; 143 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion; 144 index_within_region = SUID % info->stripeUnitsPerSparingRegion; 145 index_within_disk = index_within_region / raidPtr->numCol; 146 col_before_remap = SUID % raidPtr->numCol; 147 148 if (!remap) { 149 *col = col_before_remap; 150 *diskSector = (index_within_disk + ((raidPtr->numCol - 1) * sparing_region_id)) * 151 raidPtr->Layout.sectorsPerStripeUnit; 152 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 153 } else { 154 /* remap sector to spare space... */ 155 *diskSector = sparing_region_id * (raidPtr->numCol + 1) * raidPtr->Layout.sectorsPerStripeUnit; 156 *diskSector += (raidPtr->numCol - 1) * raidPtr->Layout.sectorsPerStripeUnit; 157 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 158 index_within_disk = index_within_region / raidPtr->numCol; 159 if (index_within_disk < col_before_remap) 160 *col = index_within_disk; 161 else 162 if (index_within_disk == raidPtr->numCol - 2) { 163 *col = (col_before_remap + raidPtr->numCol - 1) % raidPtr->numCol; 164 *diskSector += raidPtr->Layout.sectorsPerStripeUnit; 165 } else 166 *col = (index_within_disk + 2) % raidPtr->numCol; 167 } 168 169 } 170 171 172 173 /* Maps to the second copy of the mirror pair, which is chain declustered. The second copy is contained 174 in the next disk (mod numCol) after the disk containing the primary copy. 175 The offset into the disk is one-half disk down */ 176 void 177 rf_MapParityChainDecluster( 178 RF_Raid_t * raidPtr, 179 RF_RaidAddr_t raidSector, 180 RF_RowCol_t * row, 181 RF_RowCol_t * col, 182 RF_SectorNum_t * diskSector, 183 int remap) 184 { 185 RF_ChaindeclusterConfigInfo_t *info = (RF_ChaindeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 186 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit; 187 RF_SectorNum_t index_within_region, index_within_disk; 188 RF_StripeNum_t sparing_region_id; 189 int col_before_remap; 190 191 *row = 0; 192 if (!remap) { 193 *col = SUID % raidPtr->numCol; 194 *col = (*col + 1) % raidPtr->numCol; 195 *diskSector = info->mirrorStripeOffset * raidPtr->Layout.sectorsPerStripeUnit; 196 *diskSector += (SUID / raidPtr->numCol) * raidPtr->Layout.sectorsPerStripeUnit; 197 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 198 } else { 199 /* remap parity to spare space ... */ 200 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion; 201 index_within_region = SUID % info->stripeUnitsPerSparingRegion; 202 index_within_disk = index_within_region / raidPtr->numCol; 203 *diskSector = sparing_region_id * (raidPtr->numCol + 1) * raidPtr->Layout.sectorsPerStripeUnit; 204 *diskSector += (raidPtr->numCol) * raidPtr->Layout.sectorsPerStripeUnit; 205 *diskSector += (raidSector % raidPtr->Layout.sectorsPerStripeUnit); 206 col_before_remap = SUID % raidPtr->numCol; 207 if (index_within_disk < col_before_remap) 208 *col = index_within_disk; 209 else 210 if (index_within_disk == raidPtr->numCol - 2) { 211 *col = (col_before_remap + 2) % raidPtr->numCol; 212 *diskSector -= raidPtr->Layout.sectorsPerStripeUnit; 213 } else 214 *col = (index_within_disk + 2) % raidPtr->numCol; 215 } 216 217 } 218 219 void 220 rf_IdentifyStripeChainDecluster( 221 RF_Raid_t * raidPtr, 222 RF_RaidAddr_t addr, 223 RF_RowCol_t ** diskids, 224 RF_RowCol_t * outRow) 225 { 226 RF_ChaindeclusterConfigInfo_t *info = (RF_ChaindeclusterConfigInfo_t *) raidPtr->Layout.layoutSpecificInfo; 227 RF_StripeNum_t SUID; 228 RF_RowCol_t col; 229 230 SUID = addr / raidPtr->Layout.sectorsPerStripeUnit; 231 col = SUID % raidPtr->numCol; 232 *outRow = 0; 233 *diskids = info->stripeIdentifier[col]; 234 } 235 236 void 237 rf_MapSIDToPSIDChainDecluster( 238 RF_RaidLayout_t * layoutPtr, 239 RF_StripeNum_t stripeID, 240 RF_StripeNum_t * psID, 241 RF_ReconUnitNum_t * which_ru) 242 { 243 *which_ru = 0; 244 *psID = stripeID; 245 } 246 /****************************************************************************** 247 * select a graph to perform a single-stripe access 248 * 249 * Parameters: raidPtr - description of the physical array 250 * type - type of operation (read or write) requested 251 * asmap - logical & physical addresses for this access 252 * createFunc - function to use to create the graph (return value) 253 *****************************************************************************/ 254 255 void 256 rf_RAIDCDagSelect( 257 RF_Raid_t * raidPtr, 258 RF_IoType_t type, 259 RF_AccessStripeMap_t * asmap, 260 RF_VoidFuncPtr * createFunc) 261 #if 0 262 void (**createFunc) (RF_Raid_t *, RF_AccessStripeMap_t *, 263 RF_DagHeader_t *, void *, RF_RaidAccessFlags_t, 264 RF_AllocListElem_t *) 265 #endif 266 { 267 RF_ASSERT(RF_IO_IS_R_OR_W(type)); 268 RF_ASSERT(raidPtr->numRow == 1); 269 270 if (asmap->numDataFailed + asmap->numParityFailed > 1) { 271 RF_ERRORMSG("Multiple disks failed in a single group! Aborting I/O operation.\n"); 272 *createFunc = NULL; 273 return; 274 } 275 *createFunc = (type == RF_IO_TYPE_READ) ? (RF_VoidFuncPtr) rf_CreateFaultFreeReadDAG : (RF_VoidFuncPtr) rf_CreateRaidOneWriteDAG; 276 277 if (type == RF_IO_TYPE_READ) { 278 if ((raidPtr->status[0] == rf_rs_degraded) || (raidPtr->status[0] == rf_rs_reconstructing)) 279 *createFunc = (RF_VoidFuncPtr) rf_CreateRaidCDegradedReadDAG; /* array status is 280 * degraded, implement 281 * workload shifting */ 282 else 283 *createFunc = (RF_VoidFuncPtr) rf_CreateMirrorPartitionReadDAG; /* array status not 284 * degraded, so use 285 * mirror partition dag */ 286 } else 287 *createFunc = (RF_VoidFuncPtr) rf_CreateRaidOneWriteDAG; 288 } 289 #endif /* (RF_INCLUDE_CHAINDECLUSTER > 0) */ 290