sys/dev/raidframe/rf_reconmap.c

   1 /*      $NetBSD: rf_reconmap.c,v 1.30 2007/03/12 18:18:31 ad Exp $      */
   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  *************************************************************************/
  35
  36 #include <sys/cdefs.h>
  37 __KERNEL_RCSID(0, "$NetBSD: rf_reconmap.c,v 1.30 2007/03/12 18:18:31 ad Exp $");
  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
  48  * MakeReconMap uses memset 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 /* For most reconstructs we need at most 3 RF_ReconMapListElem_t's.
  55  * Bounding the number we need is quite difficult, as it depends on how
  56  * badly the sectors to be reconstructed get divided up.  In the current
  57  * code, the reconstructed sectors appeared aligned on stripe boundaries,
  58  * and are always presented in stripe width units, so we're probably
  59  * allocating quite a bit more than we'll ever need.
  60  */
  61 #define RF_NUM_RECON_POOL_ELEM 100
  62
  63 static void
  64 compact_stat_entry(RF_Raid_t *, RF_ReconMap_t *, int, int);
  65 static void crunch_list(RF_ReconMap_t *, RF_ReconMapListElem_t *);
  66 static RF_ReconMapListElem_t *
  67 MakeReconMapListElem(RF_ReconMap_t *, RF_SectorNum_t, RF_SectorNum_t,
  68                      RF_ReconMapListElem_t *);
  69 static void
  70 FreeReconMapListElem(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t * p);
  71
  72 /*---------------------------------------------------------------------------
  73  *
  74  * Creates and initializes new Reconstruction map
  75  *
  76  * ru_sectors   - size of reconstruction unit in sectors
  77  * disk_sectors - size of disk in sectors
  78  * spareUnitsPerDisk - zero unless distributed sparing
  79  *-------------------------------------------------------------------------*/
  80
  81 RF_ReconMap_t *
  82 rf_MakeReconMap(RF_Raid_t *raidPtr, RF_SectorCount_t ru_sectors,
  83                 RF_SectorCount_t disk_sectors,
  84                 RF_ReconUnitCount_t spareUnitsPerDisk)
  85 {
  86         RF_RaidLayout_t *layoutPtr = &raidPtr->Layout;
  87         RF_ReconUnitCount_t num_rus = layoutPtr->stripeUnitsPerDisk / layoutPtr->SUsPerRU;
  88         RF_ReconMap_t *p;
  89
  90         RF_Malloc(p, sizeof(RF_ReconMap_t), (RF_ReconMap_t *));
  91         p->sectorsPerReconUnit = ru_sectors;
  92         p->sectorsInDisk = disk_sectors;
  93
  94         p->totalRUs = num_rus;
  95         p->spareRUs = spareUnitsPerDisk;
  96         p->unitsLeft = num_rus - spareUnitsPerDisk;
  97         p->low_ru = 0;
  98         p->status_size = RF_RECONMAP_SIZE;
  99         p->high_ru = p->status_size - 1;
 100         p->head = 0;
 101
 102         RF_Malloc(p->status, p->status_size * sizeof(RF_ReconMapListElem_t *), (RF_ReconMapListElem_t **));
 103         RF_ASSERT(p->status != (RF_ReconMapListElem_t **) NULL);
 104
 105         (void) memset((char *) p->status, 0,
 106             p->status_size * sizeof(RF_ReconMapListElem_t *));
 107
 108         pool_init(&p->elem_pool, sizeof(RF_ReconMapListElem_t), 0,
 109             0, 0, "raidreconpl", NULL, IPL_BIO);
 110         pool_prime(&p->elem_pool, RF_NUM_RECON_POOL_ELEM);
 111
 112         rf_mutex_init(&p->mutex);
 113         return (p);
 114 }
 115
 116
 117 /*---------------------------------------------------------------------------
 118  *
 119  * marks a new set of sectors as reconstructed.  All the possible
 120  * mergings get complicated.  To simplify matters, the approach I take
 121  * is to just dump something into the list, and then clean it up
 122  * (i.e. merge elements and eliminate redundant ones) in a second pass
 123  * over the list (compact_stat_entry()).  Not 100% efficient, since a
 124  * structure can be allocated and then immediately freed, but it keeps
 125  * this code from becoming (more of) a nightmare of special cases.
 126  * The only thing that compact_stat_entry() assumes is that the list
 127  * is sorted by startSector, and so this is the only condition I
 128  * maintain here.  (MCH)
 129  *
 130  * This code now uses a pool instead of the previous malloc/free
 131  * stuff.
 132  *-------------------------------------------------------------------------*/
 133
 134 void
 135 rf_ReconMapUpdate(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr,
 136                   RF_SectorNum_t startSector, RF_SectorNum_t stopSector)
 137 {
 138         RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit;
 139         RF_SectorNum_t i, first_in_RU, last_in_RU, ru;
 140         RF_ReconMapListElem_t *p, *pt;
 141
 142         RF_LOCK_MUTEX(mapPtr->mutex);
 143         while(mapPtr->lock) {
 144                 ltsleep(&mapPtr->lock, PRIBIO, "reconupdate", 0,
 145                         &mapPtr->mutex);
 146         }
 147         mapPtr->lock = 1;
 148         RF_UNLOCK_MUTEX(mapPtr->mutex);
 149         RF_ASSERT(startSector >= 0 && stopSector < mapPtr->sectorsInDisk &&
 150                   stopSector >= startSector);
 151
 152         while (startSector <= stopSector) {
 153                 i = startSector / mapPtr->sectorsPerReconUnit;
 154                 first_in_RU = i * sectorsPerReconUnit;
 155                 last_in_RU = first_in_RU + sectorsPerReconUnit - 1;
 156
 157                 /* do we need to move the queue? */
 158                 while (i > mapPtr->high_ru) {
 159 #ifdef DIAGNOSTIC
 160                         if (mapPtr->status[mapPtr->head]!=RU_ALL) {
 161                                 printf("\nraid%d: reconmap incorrect -- working on i %" PRIu64 "\n",
 162                                        raidPtr->raidid, i);
 163                                 printf("raid%d: ru %" PRIu64 " not completed!!!\n",
 164                                        raidPtr->raidid, mapPtr->head);
 165
 166                                 printf("raid%d: low: %" PRIu64 " high: %" PRIu64 "\n",
 167                                        raidPtr->raidid, mapPtr->low_ru, mapPtr->high_ru);
 168
 169                                 panic("reconmap incorrect");
 170                         }
 171 #endif
 172                         mapPtr->low_ru++;
 173                         mapPtr->high_ru++;
 174                         /* initialize "highest" RU status entry, which
 175                            will take over the current head postion */
 176                         mapPtr->status[mapPtr->head]=RU_NOTHING;
 177
 178                         /* move head too */
 179                         mapPtr->head++;
 180                         if (mapPtr->head >= mapPtr->status_size)
 181                                 mapPtr->head = 0;
 182
 183                 }
 184
 185                 ru = i - mapPtr->low_ru + mapPtr->head;
 186                 if (ru >= mapPtr->status_size)
 187                         ru = ru - mapPtr->status_size;
 188
 189                 if ((ru < 0) || (ru >= mapPtr->status_size)) {
 190                         printf("raid%d: ru is bogus %" PRIu64 "%" PRIu64 "%" PRIu64 "%" PRIu64 "%" PRIu64 "\n",
 191                                raidPtr->raidid, i, ru, mapPtr->head, mapPtr->low_ru, mapPtr->high_ru);
 192                         panic("bogus ru in reconmap");
 193                 }
 194
 195                 p = mapPtr->status[ru];
 196                 if (p != RU_ALL) {
 197                         if (p == RU_NOTHING || p->startSector > startSector) {
 198                                 /* insert at front of list */
 199
 200                                 mapPtr->status[ru] = MakeReconMapListElem(mapPtr,startSector, RF_MIN(stopSector, last_in_RU), (p == RU_NOTHING) ? NULL : p);
 201
 202                         } else {/* general case */
 203                                 do {    /* search for place to insert */
 204                                         pt = p;
 205                                         p = p->next;
 206                                 } while (p && (p->startSector < startSector));
 207                                 pt->next = MakeReconMapListElem(mapPtr,startSector, RF_MIN(stopSector, last_in_RU), p);
 208
 209                         }
 210                         compact_stat_entry(raidPtr, mapPtr, i, ru);
 211                 }
 212                 startSector = RF_MIN(stopSector, last_in_RU) + 1;
 213         }
 214         RF_LOCK_MUTEX(mapPtr->mutex);
 215         mapPtr->lock = 0;
 216         wakeup(&mapPtr->lock);
 217         RF_UNLOCK_MUTEX(mapPtr->mutex);
 218 }
 219
 220
 221
 222 /*---------------------------------------------------------------------------
 223  *
 224  * performs whatever list compactions can be done, and frees any space
 225  * that is no longer necessary.  Assumes only that the list is sorted
 226  * by startSector.  crunch_list() compacts a single list as much as
 227  * possible, and the second block of code deletes the entire list if
 228  * possible.  crunch_list() is also called from
 229  * MakeReconMapAccessList().
 230  *
 231  * When a recon unit is detected to be fully reconstructed, we set the
 232  * corresponding bit in the parity stripe map so that the head follow
 233  * code will not select this parity stripe again.  This is redundant
 234  * (but harmless) when compact_stat_entry is called from the
 235  * reconstruction code, but necessary when called from the user-write
 236  * code.
 237  *
 238  *-------------------------------------------------------------------------*/
 239
 240 static void
 241 compact_stat_entry(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, int i, int j)
 242 {
 243         RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit;
 244         RF_ReconMapListElem_t *p = mapPtr->status[j];
 245
 246         crunch_list(mapPtr, p);
 247
 248         if ((p->startSector == i * sectorsPerReconUnit) &&
 249             (p->stopSector == i * sectorsPerReconUnit +
 250                               sectorsPerReconUnit - 1)) {
 251                 mapPtr->status[j] = RU_ALL;
 252                 mapPtr->unitsLeft--;
 253                 FreeReconMapListElem(mapPtr, p);
 254         }
 255 }
 256
 257
 258 static void
 259 crunch_list(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *listPtr)
 260 {
 261         RF_ReconMapListElem_t *pt, *p = listPtr;
 262
 263         if (!p)
 264                 return;
 265         pt = p;
 266         p = p->next;
 267         while (p) {
 268                 if (pt->stopSector >= p->startSector - 1) {
 269                         pt->stopSector = RF_MAX(pt->stopSector, p->stopSector);
 270                         pt->next = p->next;
 271                         FreeReconMapListElem(mapPtr, p);
 272                         p = pt->next;
 273                 } else {
 274                         pt = p;
 275                         p = p->next;
 276                 }
 277         }
 278 }
 279 /*---------------------------------------------------------------------------
 280  *
 281  * Allocate and fill a new list element
 282  *
 283  *-------------------------------------------------------------------------*/
 284
 285 static RF_ReconMapListElem_t *
 286 MakeReconMapListElem(RF_ReconMap_t *mapPtr, RF_SectorNum_t startSector,
 287                      RF_SectorNum_t stopSector, RF_ReconMapListElem_t *next)
 288 {
 289         RF_ReconMapListElem_t *p;
 290
 291         p = pool_get(&mapPtr->elem_pool, PR_WAITOK);
 292         p->startSector = startSector;
 293         p->stopSector = stopSector;
 294         p->next = next;
 295         return (p);
 296 }
 297 /*---------------------------------------------------------------------------
 298  *
 299  * Free a list element
 300  *
 301  *-------------------------------------------------------------------------*/
 302
 303 static void
 304 FreeReconMapListElem(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *p)
 305 {
 306         pool_put(&mapPtr->elem_pool, p);
 307 }
 308 /*---------------------------------------------------------------------------
 309  *
 310  * Free an entire status structure.  Inefficient, but can be called at
 311  * any time.
 312  *
 313  *-------------------------------------------------------------------------*/
 314 void
 315 rf_FreeReconMap(RF_ReconMap_t *mapPtr)
 316 {
 317         RF_ReconMapListElem_t *p, *q;
 318         RF_ReconUnitCount_t numRUs;
 319         RF_ReconUnitNum_t i;
 320
 321         numRUs = mapPtr->sectorsInDisk / mapPtr->sectorsPerReconUnit;
 322         if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit)
 323                 numRUs++;
 324
 325         for (i = 0; i < mapPtr->status_size; i++) {
 326                 p = mapPtr->status[i];
 327                 while (p != RU_NOTHING && p != RU_ALL) {
 328                         q = p;
 329                         p = p->next;
 330                         RF_Free(q, sizeof(*q));
 331                 }
 332         }
 333
 334         pool_destroy(&mapPtr->elem_pool);
 335         RF_Free(mapPtr->status, mapPtr->status_size *
 336                 sizeof(RF_ReconMapListElem_t *));
 337         RF_Free(mapPtr, sizeof(RF_ReconMap_t));
 338 }
 339 /*---------------------------------------------------------------------------
 340  *
 341  * returns nonzero if the indicated RU has been reconstructed already
 342  *
 343  *-------------------------------------------------------------------------*/
 344
 345 int
 346 rf_CheckRUReconstructed(RF_ReconMap_t *mapPtr, RF_SectorNum_t startSector)
 347 {
 348         RF_ReconUnitNum_t i;
 349         int rv;
 350
 351         i = startSector / mapPtr->sectorsPerReconUnit;
 352
 353         if (i < mapPtr->low_ru)
 354                 rv = 1;
 355         else if (i > mapPtr->high_ru)
 356                 rv = 0;
 357         else {
 358                 i = i - mapPtr->low_ru + mapPtr->head;
 359                 if (i >= mapPtr->status_size)
 360                         i = i - mapPtr->status_size;
 361                 if (mapPtr->status[i] == RU_ALL)
 362                         rv = 1;
 363                 else
 364                         rv = 0;
 365         }
 366
 367         return rv;
 368 }
 369
 370 RF_ReconUnitCount_t
 371 rf_UnitsLeftToReconstruct(RF_ReconMap_t *mapPtr)
 372 {
 373         RF_ASSERT(mapPtr != NULL);
 374         return (mapPtr->unitsLeft);
 375 }
 376
 377 #if RF_DEBUG_RECON
 378 void
 379 rf_PrintReconSchedule(RF_ReconMap_t *mapPtr, struct timeval *starttime)
 380 {
 381         static int old_pctg = -1;
 382         struct timeval tv, diff;
 383         int     new_pctg;
 384
 385         new_pctg = 100 - (rf_UnitsLeftToReconstruct(mapPtr) *
 386                           100 / mapPtr->totalRUs);
 387         if (new_pctg != old_pctg) {
 388                 RF_GETTIME(tv);
 389                 RF_TIMEVAL_DIFF(starttime, &tv, &diff);
 390                 printf("%d %d.%06d\n", (int) new_pctg, (int) diff.tv_sec,
 391                        (int) diff.tv_usec);
 392                 old_pctg = new_pctg;
 393         }
 394 }
 395 #endif
 396