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