Annotation of sys/dev/raidframe/rf_reconmap.c, Revision 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