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