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