1 /* $OpenBSD: rf_interdecluster.c,v 1.4 2002/12/16 07:01:04 tdeval Exp $ */
2 /* $NetBSD: rf_interdecluster.c,v 1.4 2000/01/07 03:41:00 oster Exp $ */
3
4 /*
5 * Copyright (c) 1995 Carnegie-Mellon University.
6 * All rights reserved.
7 *
8 * Author: Khalil Amiri
9 *
10 * Permission to use, copy, modify and distribute this software and
11 * its documentation is hereby granted, provided that both the copyright
12 * notice and this permission notice appear in all copies of the
13 * software, derivative works or modified versions, and any portions
14 * thereof, and that both notices appear in supporting documentation.
15 *
16 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
17 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
18 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
19 *
20 * Carnegie Mellon requests users of this software to return to
21 *
22 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
23 * School of Computer Science
24 * Carnegie Mellon University
25 * Pittsburgh PA 15213-3890
26 *
27 * any improvements or extensions that they make and grant Carnegie the
28 * rights to redistribute these changes.
29 */
30
31 /*************************************************************
32 *
33 * rf_interdecluster.c -- Implements interleaved declustering.
34 *
35 *************************************************************/
36
37
38 #include "rf_types.h"
39 #include "rf_raid.h"
40 #include "rf_interdecluster.h"
41 #include "rf_dag.h"
42 #include "rf_dagutils.h"
43 #include "rf_dagfuncs.h"
44 #include "rf_general.h"
45 #include "rf_utils.h"
46 #include "rf_dagffrd.h"
47 #include "rf_dagdegrd.h"
48 #include "rf_dagffwr.h"
49 #include "rf_dagdegwr.h"
50
51 typedef struct RF_InterdeclusterConfigInfo_s {
52 /* Filled in at config time and used by IdentifyStripe. */
53 RF_RowCol_t **stripeIdentifier;
54 RF_StripeCount_t numSparingRegions;
55 RF_StripeCount_t stripeUnitsPerSparingRegion;
56 RF_SectorNum_t mirrorStripeOffset;
57 } RF_InterdeclusterConfigInfo_t;
58
59 int
rf_ConfigureInterDecluster(RF_ShutdownList_t ** listp,RF_Raid_t * raidPtr,RF_Config_t * cfgPtr)60 rf_ConfigureInterDecluster(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
61 RF_Config_t *cfgPtr)
62 {
63 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
64 RF_StripeCount_t num_used_stripeUnitsPerDisk;
65 RF_InterdeclusterConfigInfo_t *info;
66 RF_RowCol_t i, tmp, SUs_per_region;
67
68 /* Create an Interleaved Declustering configuration structure. */
69 RF_MallocAndAdd(info, sizeof(RF_InterdeclusterConfigInfo_t),
70 (RF_InterdeclusterConfigInfo_t *), raidPtr->cleanupList);
71 if (info == NULL)
72 return (ENOMEM);
73 layoutPtr->layoutSpecificInfo = (void *) info;
74
75 /* Fill in the config structure. */
76 SUs_per_region = raidPtr->numCol * (raidPtr->numCol - 1);
77 info->stripeIdentifier = rf_make_2d_array(SUs_per_region, 2,
78 raidPtr->cleanupList);
79 if (info->stripeIdentifier == NULL)
80 return (ENOMEM);
81 for (i = 0; i < SUs_per_region; i++) {
82 info->stripeIdentifier[i][0] = i / (raidPtr->numCol - 1);
83 tmp = i / raidPtr->numCol;
84 info->stripeIdentifier[i][1] = (i + 1 + tmp) % raidPtr->numCol;
85 }
86
87 /* No spare tables. */
88 RF_ASSERT(raidPtr->numRow == 1);
89
90 /* Fill in the remaining layout parameters. */
91
92 /*
93 * Total number of stripes should a multiple of 2*numCol: Each sparing
94 * region consists of 2*numCol stripes: n-1 primary copy, n-1
95 * secondary copy and 2 for spare...
96 */
97 num_used_stripeUnitsPerDisk = layoutPtr->stripeUnitsPerDisk -
98 (layoutPtr->stripeUnitsPerDisk % (2 * raidPtr->numCol));
99 info->numSparingRegions = num_used_stripeUnitsPerDisk /
100 (2 * raidPtr->numCol);
101 /*
102 * This is in fact the number of stripe units (that are primary data
103 * copies) in the sparing region.
104 */
105 info->stripeUnitsPerSparingRegion = raidPtr->numCol *
106 (raidPtr->numCol - 1);
107 info->mirrorStripeOffset = info->numSparingRegions *
108 (raidPtr->numCol + 1);
109 layoutPtr->numStripe = info->numSparingRegions *
110 info->stripeUnitsPerSparingRegion;
111 layoutPtr->bytesPerStripeUnit = layoutPtr->sectorsPerStripeUnit <<
112 raidPtr->logBytesPerSector;
113 layoutPtr->numDataCol = 1;
114 layoutPtr->dataSectorsPerStripe = layoutPtr->numDataCol *
115 layoutPtr->sectorsPerStripeUnit;
116 layoutPtr->numParityCol = 1;
117
118 layoutPtr->dataStripeUnitsPerDisk = num_used_stripeUnitsPerDisk;
119
120 raidPtr->sectorsPerDisk =
121 num_used_stripeUnitsPerDisk * layoutPtr->sectorsPerStripeUnit;
122
123 raidPtr->totalSectors =
124 (layoutPtr->numStripe) * layoutPtr->sectorsPerStripeUnit;
125
126 layoutPtr->stripeUnitsPerDisk = raidPtr->sectorsPerDisk /
127 layoutPtr->sectorsPerStripeUnit;
128
129 return (0);
130 }
131
132 int
rf_GetDefaultNumFloatingReconBuffersInterDecluster(RF_Raid_t * raidPtr)133 rf_GetDefaultNumFloatingReconBuffersInterDecluster(RF_Raid_t *raidPtr)
134 {
135 return (30);
136 }
137
138 RF_HeadSepLimit_t
rf_GetDefaultHeadSepLimitInterDecluster(RF_Raid_t * raidPtr)139 rf_GetDefaultHeadSepLimitInterDecluster(RF_Raid_t *raidPtr)
140 {
141 return (raidPtr->sectorsPerDisk);
142 }
143
144 RF_ReconUnitCount_t
rf_GetNumSpareRUsInterDecluster(RF_Raid_t * raidPtr)145 rf_GetNumSpareRUsInterDecluster(RF_Raid_t *raidPtr)
146 {
147 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *)
148 raidPtr->Layout.layoutSpecificInfo;
149
150 return (2 * ((RF_ReconUnitCount_t) info->numSparingRegions));
151 /*
152 * The layout uses two stripe units per disk as spare within each
153 * sparing region.
154 */
155 }
156
157 /* Maps to the primary copy of the data, i.e. the first mirror pair. */
158 void
rf_MapSectorInterDecluster(RF_Raid_t * raidPtr,RF_RaidAddr_t raidSector,RF_RowCol_t * row,RF_RowCol_t * col,RF_SectorNum_t * diskSector,int remap)159 rf_MapSectorInterDecluster(RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector,
160 RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t* diskSector, int remap)
161 {
162 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *)
163 raidPtr->Layout.layoutSpecificInfo;
164 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit;
165 RF_StripeNum_t su_offset_into_disk, mirror_su_offset_into_disk;
166 RF_StripeNum_t sparing_region_id, index_within_region;
167 int col_before_remap;
168
169 *row = 0;
170 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion;
171 index_within_region = SUID % info->stripeUnitsPerSparingRegion;
172 su_offset_into_disk = index_within_region % (raidPtr->numCol - 1);
173 mirror_su_offset_into_disk = index_within_region / raidPtr->numCol;
174 col_before_remap = index_within_region / (raidPtr->numCol - 1);
175
176 if (!remap) {
177 *col = col_before_remap;
178 *diskSector = (su_offset_into_disk + ((raidPtr->numCol - 1) *
179 sparing_region_id)) * raidPtr->Layout.sectorsPerStripeUnit;
180 *diskSector +=
181 (raidSector % raidPtr->Layout.sectorsPerStripeUnit);
182 } else {
183 /* Remap sector to spare space... */
184 *diskSector = sparing_region_id * (raidPtr->numCol + 1) *
185 raidPtr->Layout.sectorsPerStripeUnit;
186 *diskSector += (raidPtr->numCol - 1) *
187 raidPtr->Layout.sectorsPerStripeUnit;
188 *diskSector +=
189 (raidSector % raidPtr->Layout.sectorsPerStripeUnit);
190 *col = (index_within_region + 1 + mirror_su_offset_into_disk) %
191 raidPtr->numCol;
192 *col = (*col + 1) % raidPtr->numCol;
193 if (*col == col_before_remap)
194 *col = (*col + 1) % raidPtr->numCol;
195 }
196 }
197
198 /* Maps to the second copy of the mirror pair. */
199 void
rf_MapParityInterDecluster(RF_Raid_t * raidPtr,RF_RaidAddr_t raidSector,RF_RowCol_t * row,RF_RowCol_t * col,RF_SectorNum_t * diskSector,int remap)200 rf_MapParityInterDecluster(RF_Raid_t *raidPtr, RF_RaidAddr_t raidSector,
201 RF_RowCol_t *row, RF_RowCol_t *col, RF_SectorNum_t *diskSector, int remap)
202 {
203 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *)
204 raidPtr->Layout.layoutSpecificInfo;
205 RF_StripeNum_t sparing_region_id, index_within_region;
206 RF_StripeNum_t mirror_su_offset_into_disk;
207 RF_StripeNum_t SUID = raidSector / raidPtr->Layout.sectorsPerStripeUnit;
208 int col_before_remap;
209
210 sparing_region_id = SUID / info->stripeUnitsPerSparingRegion;
211 index_within_region = SUID % info->stripeUnitsPerSparingRegion;
212 mirror_su_offset_into_disk = index_within_region / raidPtr->numCol;
213 col_before_remap = (index_within_region + 1 +
214 mirror_su_offset_into_disk) % raidPtr->numCol;
215
216 *row = 0;
217 if (!remap) {
218 *col = col_before_remap;
219 *diskSector = info->mirrorStripeOffset *
220 raidPtr->Layout.sectorsPerStripeUnit;
221 *diskSector += sparing_region_id * (raidPtr->numCol - 1) *
222 raidPtr->Layout.sectorsPerStripeUnit;
223 *diskSector += mirror_su_offset_into_disk *
224 raidPtr->Layout.sectorsPerStripeUnit;
225 *diskSector +=
226 (raidSector % raidPtr->Layout.sectorsPerStripeUnit);
227 } else {
228 /* Remap parity to spare space... */
229 *diskSector = sparing_region_id * (raidPtr->numCol + 1) *
230 raidPtr->Layout.sectorsPerStripeUnit;
231 *diskSector += (raidPtr->numCol) *
232 raidPtr->Layout.sectorsPerStripeUnit;
233 *diskSector += (raidSector %
234 raidPtr->Layout.sectorsPerStripeUnit);
235 *col = index_within_region / (raidPtr->numCol - 1);
236 *col = (*col + 1) % raidPtr->numCol;
237 if (*col == col_before_remap)
238 *col = (*col + 1) % raidPtr->numCol;
239 }
240 }
241
242 void
rf_IdentifyStripeInterDecluster(RF_Raid_t * raidPtr,RF_RaidAddr_t addr,RF_RowCol_t ** diskids,RF_RowCol_t * outRow)243 rf_IdentifyStripeInterDecluster(RF_Raid_t *raidPtr, RF_RaidAddr_t addr,
244 RF_RowCol_t **diskids, RF_RowCol_t *outRow)
245 {
246 RF_InterdeclusterConfigInfo_t *info = (RF_InterdeclusterConfigInfo_t *)
247 raidPtr->Layout.layoutSpecificInfo;
248 RF_StripeNum_t SUID;
249
250 SUID = addr / raidPtr->Layout.sectorsPerStripeUnit;
251 SUID = SUID % info->stripeUnitsPerSparingRegion;
252
253 *outRow = 0;
254 *diskids = info->stripeIdentifier[SUID];
255 }
256
257 void
rf_MapSIDToPSIDInterDecluster(RF_RaidLayout_t * layoutPtr,RF_StripeNum_t stripeID,RF_StripeNum_t * psID,RF_ReconUnitNum_t * which_ru)258 rf_MapSIDToPSIDInterDecluster( RF_RaidLayout_t *layoutPtr,
259 RF_StripeNum_t stripeID, RF_StripeNum_t *psID, RF_ReconUnitNum_t *which_ru)
260 {
261 *which_ru = 0;
262 *psID = stripeID;
263 }
264
265
266 /*****************************************************************************
267 * Select a graph to perform a single-stripe access.
268 *
269 * Parameters: raidPtr - Description of the physical array.
270 * type - Type of operation (read or write) requested.
271 * asmap - Logical & physical addresses for this access.
272 * createFunc - Name of function to use to create the graph.
273 *****************************************************************************/
274
275 void
rf_RAIDIDagSelect(RF_Raid_t * raidPtr,RF_IoType_t type,RF_AccessStripeMap_t * asmap,RF_VoidFuncPtr * createFunc)276 rf_RAIDIDagSelect(RF_Raid_t *raidPtr, RF_IoType_t type,
277 RF_AccessStripeMap_t *asmap, RF_VoidFuncPtr *createFunc)
278 {
279 RF_ASSERT(RF_IO_IS_R_OR_W(type));
280
281 if (asmap->numDataFailed + asmap->numParityFailed > 1) {
282 RF_ERRORMSG("Multiple disks failed in a single group !"
283 " Aborting I/O operation.\n");
284 *createFunc = NULL;
285 return;
286 }
287 *createFunc = (type == RF_IO_TYPE_READ)
288 ? (RF_VoidFuncPtr) rf_CreateFaultFreeReadDAG
289 : (RF_VoidFuncPtr) rf_CreateRaidOneWriteDAG;
290 if (type == RF_IO_TYPE_READ) {
291 if (asmap->numDataFailed == 0)
292 *createFunc = (RF_VoidFuncPtr)
293 rf_CreateMirrorPartitionReadDAG;
294 else
295 *createFunc = (RF_VoidFuncPtr)
296 rf_CreateRaidOneDegradedReadDAG;
297 } else
298 *createFunc = (RF_VoidFuncPtr) rf_CreateRaidOneWriteDAG;
299 }
300