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