1 /* $OpenBSD: rf_reconmap.c,v 1.4 2002/12/16 07:01:05 tdeval Exp $ */
2 /* $NetBSD: rf_reconmap.c,v 1.6 1999/08/14 21:44:24 oster Exp $ */
3
4 /*
5 * Copyright (c) 1995 Carnegie-Mellon University.
6 * All rights reserved.
7 *
8 * Author: Mark Holland
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 * rf_reconmap.c
33 *
34 * Code to maintain a map of what sectors have/have not been reconstructed.
35 *
36 *****************************************************************************/
37
38 #include "rf_raid.h"
39 #include <sys/time.h>
40 #include "rf_general.h"
41 #include "rf_utils.h"
42
43 /*
44 * Special pointer values indicating that a reconstruction unit
45 * has been either totally reconstructed or not at all. Both
46 * are illegal pointer values, so you have to be careful not to
47 * dereference through them. RU_NOTHING must be zero, since
48 * MakeReconMap uses bzero to initialize the structure. These are used
49 * only at the head of the list.
50 */
51 #define RU_ALL ((RF_ReconMapListElem_t *) -1)
52 #define RU_NOTHING ((RF_ReconMapListElem_t *) 0)
53
54 /* Used to mark the end of the list. */
55 #define RU_NIL ((RF_ReconMapListElem_t *) 0)
56
57
58 void rf_compact_stat_entry(RF_Raid_t *, RF_ReconMap_t *, int);
59 void rf_crunch_list(RF_ReconMap_t *, RF_ReconMapListElem_t *);
60 RF_ReconMapListElem_t * rf_MakeReconMapListElem(RF_SectorNum_t, RF_SectorNum_t,
61 RF_ReconMapListElem_t *);
62 void rf_FreeReconMapListElem(RF_ReconMap_t *, RF_ReconMapListElem_t *);
63 void rf_update_size(RF_ReconMap_t *, int);
64 void rf_PrintList(RF_ReconMapListElem_t *);
65
66
67 /*****************************************************************************
68 *
69 * Creates and initializes new Reconstruction map.
70 *
71 *****************************************************************************/
72
73 RF_ReconMap_t *
rf_MakeReconMap(RF_Raid_t * raidPtr,RF_SectorCount_t ru_sectors,RF_SectorCount_t disk_sectors,RF_ReconUnitCount_t spareUnitsPerDisk)74 rf_MakeReconMap(
75 RF_Raid_t *raidPtr,
76 RF_SectorCount_t ru_sectors, /*
77 * Size of reconstruction unit
78 * in sectors.
79 */
80 RF_SectorCount_t disk_sectors, /* Size of disk in sectors. */
81 RF_ReconUnitCount_t spareUnitsPerDisk /*
82 * Zero unless distributed
83 * sparing.
84 */
85 )
86 {
87 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
88 RF_ReconUnitCount_t num_rus = layoutPtr->stripeUnitsPerDisk /
89 layoutPtr->SUsPerRU;
90 RF_ReconMap_t *p;
91 int rc;
92
93 RF_Malloc(p, sizeof(RF_ReconMap_t), (RF_ReconMap_t *));
94 p->sectorsPerReconUnit = ru_sectors;
95 p->sectorsInDisk = disk_sectors;
96
97 p->totalRUs = num_rus;
98 p->spareRUs = spareUnitsPerDisk;
99 p->unitsLeft = num_rus - spareUnitsPerDisk;
100
101 RF_Malloc(p->status, num_rus * sizeof(RF_ReconMapListElem_t *),
102 (RF_ReconMapListElem_t **));
103 RF_ASSERT(p->status != (RF_ReconMapListElem_t **) NULL);
104
105 (void) bzero((char *) p->status, num_rus *
106 sizeof(RF_ReconMapListElem_t *));
107
108 p->size = sizeof(RF_ReconMap_t) + num_rus *
109 sizeof(RF_ReconMapListElem_t *);
110 p->maxSize = p->size;
111
112 rc = rf_mutex_init(&p->mutex);
113 if (rc) {
114 RF_ERRORMSG3("Unable to init mutex file %s line %d rc=%d.\n",
115 __FILE__, __LINE__, rc);
116 RF_Free(p->status, num_rus * sizeof(RF_ReconMapListElem_t *));
117 RF_Free(p, sizeof(RF_ReconMap_t));
118 return (NULL);
119 }
120 return (p);
121 }
122
123
124 /*****************************************************************************
125 *
126 * Marks a new set of sectors as reconstructed. All the possible mergings get
127 * complicated. To simplify matters, the approach I take is to just dump
128 * something into the list, and then clean it up (i.e. merge elements and
129 * eliminate redundant ones) in a second pass over the list
130 * (rf_compact_stat_entry()).
131 * Not 100% efficient, since a structure can be allocated and then immediately
132 * freed, but it keeps this code from becoming (more of) a nightmare of
133 * special cases. The only thing that rf_compact_stat_entry() assumes is that
134 * the list is sorted by startSector, and so this is the only condition I
135 * maintain here. (MCH)
136 *
137 *****************************************************************************/
138
139 void
rf_ReconMapUpdate(RF_Raid_t * raidPtr,RF_ReconMap_t * mapPtr,RF_SectorNum_t startSector,RF_SectorNum_t stopSector)140 rf_ReconMapUpdate(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr,
141 RF_SectorNum_t startSector, RF_SectorNum_t stopSector)
142 {
143 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit;
144 RF_SectorNum_t i, first_in_RU, last_in_RU;
145 RF_ReconMapListElem_t *p, *pt;
146
147 RF_LOCK_MUTEX(mapPtr->mutex);
148 RF_ASSERT(startSector >= 0 && stopSector < mapPtr->sectorsInDisk &&
149 stopSector >= startSector);
150
151 while (startSector <= stopSector) {
152 i = startSector / mapPtr->sectorsPerReconUnit;
153 first_in_RU = i * sectorsPerReconUnit;
154 last_in_RU = first_in_RU + sectorsPerReconUnit - 1;
155 p = mapPtr->status[i];
156 if (p != RU_ALL) {
157 if (p == RU_NOTHING || p->startSector > startSector) {
158 /* Insert at front of list. */
159
160 mapPtr->status[i] =
161 rf_MakeReconMapListElem(startSector,
162 RF_MIN(stopSector, last_in_RU),
163 (p == RU_NOTHING) ? NULL : p);
164 rf_update_size(mapPtr,
165 sizeof(RF_ReconMapListElem_t));
166
167 } else {/* General case. */
168 do { /* Search for place to insert. */
169 pt = p;
170 p = p->next;
171 } while (p && (p->startSector < startSector));
172 pt->next = rf_MakeReconMapListElem(startSector,
173 RF_MIN(stopSector, last_in_RU), p);
174 rf_update_size(mapPtr,
175 sizeof(RF_ReconMapListElem_t));
176 }
177 rf_compact_stat_entry(raidPtr, mapPtr, i);
178 }
179 startSector = RF_MIN(stopSector, last_in_RU) + 1;
180 }
181 RF_UNLOCK_MUTEX(mapPtr->mutex);
182 }
183
184
185 /*****************************************************************************
186 *
187 * Performs whatever list compactions can be done, and frees any space
188 * that is no longer necessary. Assumes only that the list is sorted
189 * by startSector. rf_crunch_list() compacts a single list as much as possible,
190 * and the second block of code deletes the entire list if possible.
191 * rf_crunch_list() is also called from MakeReconMapAccessList().
192 *
193 * When a recon unit is detected to be fully reconstructed, we set the
194 * corresponding bit in the parity stripe map so that the head follow
195 * code will not select this parity stripe again. This is redundant (but
196 * harmless) when rf_compact_stat_entry is called from the reconstruction
197 * code, but necessary when called from the user-write code.
198 *
199 *****************************************************************************/
200
201 void
rf_compact_stat_entry(RF_Raid_t * raidPtr,RF_ReconMap_t * mapPtr,int i)202 rf_compact_stat_entry(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, int i)
203 {
204 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit;
205 RF_ReconMapListElem_t *p = mapPtr->status[i];
206
207 rf_crunch_list(mapPtr, p);
208
209 if ((p->startSector == i * sectorsPerReconUnit) &&
210 (p->stopSector == i * sectorsPerReconUnit +
211 sectorsPerReconUnit - 1)) {
212 mapPtr->status[i] = RU_ALL;
213 mapPtr->unitsLeft--;
214 rf_FreeReconMapListElem(mapPtr, p);
215 }
216 }
217
218 void
rf_crunch_list(RF_ReconMap_t * mapPtr,RF_ReconMapListElem_t * listPtr)219 rf_crunch_list(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *listPtr)
220 {
221 RF_ReconMapListElem_t *pt, *p = listPtr;
222
223 if (!p)
224 return;
225 pt = p;
226 p = p->next;
227 while (p) {
228 if (pt->stopSector >= p->startSector - 1) {
229 pt->stopSector = RF_MAX(pt->stopSector, p->stopSector);
230 pt->next = p->next;
231 rf_FreeReconMapListElem(mapPtr, p);
232 p = pt->next;
233 } else {
234 pt = p;
235 p = p->next;
236 }
237 }
238 }
239
240
241 /*****************************************************************************
242 *
243 * Allocate and fill a new list element.
244 *
245 *****************************************************************************/
246
247 RF_ReconMapListElem_t *
rf_MakeReconMapListElem(RF_SectorNum_t startSector,RF_SectorNum_t stopSector,RF_ReconMapListElem_t * next)248 rf_MakeReconMapListElem(RF_SectorNum_t startSector, RF_SectorNum_t stopSector,
249 RF_ReconMapListElem_t *next)
250 {
251 RF_ReconMapListElem_t *p;
252
253 RF_Malloc(p, sizeof(RF_ReconMapListElem_t), (RF_ReconMapListElem_t *));
254 if (p == NULL)
255 return (NULL);
256 p->startSector = startSector;
257 p->stopSector = stopSector;
258 p->next = next;
259 return (p);
260 }
261
262
263 /*****************************************************************************
264 *
265 * Free a list element.
266 *
267 *****************************************************************************/
268
269 void
rf_FreeReconMapListElem(RF_ReconMap_t * mapPtr,RF_ReconMapListElem_t * p)270 rf_FreeReconMapListElem(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *p)
271 {
272 int delta;
273
274 if (mapPtr) {
275 delta = 0 - (int) sizeof(RF_ReconMapListElem_t);
276 rf_update_size(mapPtr, delta);
277 }
278 RF_Free(p, sizeof(*p));
279 }
280
281
282 /*****************************************************************************
283 *
284 * Free an entire status structure. Inefficient, but can be called at any
285 * time.
286 *
287 *****************************************************************************/
288
289 void
rf_FreeReconMap(RF_ReconMap_t * mapPtr)290 rf_FreeReconMap(RF_ReconMap_t *mapPtr)
291 {
292 RF_ReconMapListElem_t *p, *q;
293 RF_ReconUnitCount_t numRUs;
294 RF_ReconUnitNum_t i;
295
296 numRUs = mapPtr->sectorsInDisk / mapPtr->sectorsPerReconUnit;
297 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit)
298 numRUs++;
299
300 for (i = 0; i < numRUs; i++) {
301 p = mapPtr->status[i];
302 while (p != RU_NOTHING && p != RU_ALL) {
303 q = p;
304 p = p->next;
305 RF_Free(q, sizeof(*q));
306 }
307 }
308 rf_mutex_destroy(&mapPtr->mutex);
309 RF_Free(mapPtr->status, mapPtr->totalRUs *
310 sizeof(RF_ReconMapListElem_t *));
311 RF_Free(mapPtr, sizeof(RF_ReconMap_t));
312 }
313
314
315 /*****************************************************************************
316 *
317 * Returns nonzero if the indicated RU has been reconstructed already.
318 *
319 *****************************************************************************/
320
321 int
rf_CheckRUReconstructed(RF_ReconMap_t * mapPtr,RF_SectorNum_t startSector)322 rf_CheckRUReconstructed(RF_ReconMap_t *mapPtr, RF_SectorNum_t startSector)
323 {
324 RF_ReconMapListElem_t *l; /* Used for searching. */
325 RF_ReconUnitNum_t i;
326
327 i = startSector / mapPtr->sectorsPerReconUnit;
328 l = mapPtr->status[i];
329 return ((l == RU_ALL) ? 1 : 0);
330 }
331
332 RF_ReconUnitCount_t
rf_UnitsLeftToReconstruct(RF_ReconMap_t * mapPtr)333 rf_UnitsLeftToReconstruct(RF_ReconMap_t *mapPtr)
334 {
335 RF_ASSERT(mapPtr != NULL);
336 return (mapPtr->unitsLeft);
337 }
338
339 /* Updates the size fields of a status descriptor. */
340 void
rf_update_size(RF_ReconMap_t * mapPtr,int size)341 rf_update_size(RF_ReconMap_t *mapPtr, int size)
342 {
343 mapPtr->size += size;
344 mapPtr->maxSize = RF_MAX(mapPtr->size, mapPtr->maxSize);
345 }
346
347 void
rf_PrintList(RF_ReconMapListElem_t * listPtr)348 rf_PrintList(RF_ReconMapListElem_t *listPtr)
349 {
350 while (listPtr) {
351 printf("%d,%d -> ", (int) listPtr->startSector,
352 (int) listPtr->stopSector);
353 listPtr = listPtr->next;
354 }
355 printf("\n");
356 }
357
358 void
rf_PrintReconMap(RF_Raid_t * raidPtr,RF_ReconMap_t * mapPtr,RF_RowCol_t frow,RF_RowCol_t fcol)359 rf_PrintReconMap(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, RF_RowCol_t frow,
360 RF_RowCol_t fcol)
361 {
362 RF_ReconUnitCount_t numRUs;
363 RF_ReconMapListElem_t *p;
364 RF_ReconUnitNum_t i;
365
366 numRUs = mapPtr->totalRUs;
367 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit)
368 numRUs++;
369
370 for (i = 0; i < numRUs; i++) {
371 p = mapPtr->status[i];
372 if (p == RU_ALL)
373 /* printf("[%d] ALL.\n", i) */;
374 else
375 if (p == RU_NOTHING) {
376 printf("%d: Unreconstructed.\n", i);
377 } else {
378 printf("%d: ", i);
379 rf_PrintList(p);
380 }
381 }
382 }
383
384 void
rf_PrintReconSchedule(RF_ReconMap_t * mapPtr,struct timeval * starttime)385 rf_PrintReconSchedule(RF_ReconMap_t *mapPtr, struct timeval *starttime)
386 {
387 static int old_pctg = -1;
388 struct timeval tv, diff;
389 int new_pctg;
390
391 new_pctg = 100 - (rf_UnitsLeftToReconstruct(mapPtr) * 100 /
392 mapPtr->totalRUs);
393 if (new_pctg != old_pctg) {
394 RF_GETTIME(tv);
395 RF_TIMEVAL_DIFF(starttime, &tv, &diff);
396 printf("%d %d.%06d\n", (int) new_pctg, (int) diff.tv_sec,
397 (int) diff.tv_usec);
398 old_pctg = new_pctg;
399 }
400 }
401