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