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