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