Annotation of sys/dev/raidframe/rf_reconmap.c, Revision 1.1.1.1
1.1 nbrk 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 *
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
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
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
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 *
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
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
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
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
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
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
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
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
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: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rf_reconmap.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe