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