1 /* $NetBSD: rf_reconmap.c,v 1.1 1998/11/13 04:20:33 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 /* : 37 * Log: rf_reconmap.c,v 38 * Revision 1.23 1996/07/27 23:36:08 jimz 39 * Solaris port of simulator 40 * 41 * Revision 1.22 1996/07/15 17:22:18 jimz 42 * nit-pick code cleanup 43 * resolve stdlib problems on DEC OSF 44 * 45 * Revision 1.21 1996/06/17 14:38:33 jimz 46 * properly #if out RF_DEMO code 47 * fix bug in MakeConfig that was causing weird behavior 48 * in configuration routines (config was not zeroed at start) 49 * clean up genplot handling of stacks 50 * 51 * Revision 1.20 1996/06/09 02:36:46 jimz 52 * lots of little crufty cleanup- fixup whitespace 53 * issues, comment #ifdefs, improve typing in some 54 * places (esp size-related) 55 * 56 * Revision 1.19 1996/06/07 21:33:04 jimz 57 * begin using consistent types for sector numbers, 58 * stripe numbers, row+col numbers, recon unit numbers 59 * 60 * Revision 1.18 1996/06/05 18:06:02 jimz 61 * Major code cleanup. The Great Renaming is now done. 62 * Better modularity. Better typing. Fixed a bunch of 63 * synchronization bugs. Made a lot of global stuff 64 * per-desc or per-array. Removed dead code. 65 * 66 * Revision 1.17 1996/05/31 22:26:54 jimz 67 * fix a lot of mapping problems, memory allocation problems 68 * found some weird lock issues, fixed 'em 69 * more code cleanup 70 * 71 * Revision 1.16 1996/05/30 23:22:16 jimz 72 * bugfixes of serialization, timing problems 73 * more cleanup 74 * 75 * Revision 1.15 1996/05/27 18:56:37 jimz 76 * more code cleanup 77 * better typing 78 * compiles in all 3 environments 79 * 80 * Revision 1.14 1996/05/24 22:17:04 jimz 81 * continue code + namespace cleanup 82 * typed a bunch of flags 83 * 84 * Revision 1.13 1996/05/24 04:40:57 jimz 85 * don't do recon meter demo stuff in kernel 86 * 87 * Revision 1.12 1996/05/23 00:33:23 jimz 88 * code cleanup: move all debug decls to rf_options.c, all extern 89 * debug decls to rf_options.h, all debug vars preceded by rf_ 90 * 91 * Revision 1.11 1996/05/20 16:14:50 jimz 92 * switch to rf_{mutex,cond}_{init,destroy} 93 * 94 * Revision 1.10 1996/05/18 19:51:34 jimz 95 * major code cleanup- fix syntax, make some types consistent, 96 * add prototypes, clean out dead code, et cetera 97 * 98 * Revision 1.9 1995/12/12 18:10:06 jimz 99 * MIN -> RF_MIN, MAX -> RF_MAX, ASSERT -> RF_ASSERT 100 * fix 80-column brain damage in comments 101 * 102 * Revision 1.8 1995/12/06 15:05:23 root 103 * added copyright info 104 * 105 */ 106 107 #include "rf_raid.h" 108 #include <sys/time.h> 109 #include "rf_general.h" 110 #include "rf_utils.h" 111 #if RF_DEMO > 0 112 #include "rf_demo.h" 113 #endif /* RF_DEMO > 0 */ 114 #include "rf_sys.h" 115 116 /* special pointer values indicating that a reconstruction unit 117 * has been either totally reconstructed or not at all. Both 118 * are illegal pointer values, so you have to be careful not to 119 * dereference through them. RU_NOTHING must be zero, since 120 * MakeReconMap uses bzero to initialize the structure. These are used 121 * only at the head of the list. 122 */ 123 #define RU_ALL ((RF_ReconMapListElem_t *) -1) 124 #define RU_NOTHING ((RF_ReconMapListElem_t *) 0) 125 126 /* used to mark the end of the list */ 127 #define RU_NIL ((RF_ReconMapListElem_t *) 0) 128 129 130 static void compact_stat_entry(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, 131 int i); 132 static void crunch_list(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *listPtr); 133 static RF_ReconMapListElem_t *MakeReconMapListElem(RF_SectorNum_t startSector, 134 RF_SectorNum_t stopSector, RF_ReconMapListElem_t *next); 135 static void FreeReconMapListElem(RF_ReconMap_t *mapPtr, 136 RF_ReconMapListElem_t *p); 137 static void update_size(RF_ReconMap_t *mapPtr, int size); 138 static void PrintList(RF_ReconMapListElem_t *listPtr); 139 140 /*----------------------------------------------------------------------------- 141 * 142 * Creates and initializes new Reconstruction map 143 * 144 *-----------------------------------------------------------------------------*/ 145 146 RF_ReconMap_t *rf_MakeReconMap(raidPtr, ru_sectors, disk_sectors, spareUnitsPerDisk) 147 RF_Raid_t *raidPtr; 148 RF_SectorCount_t ru_sectors; /* size of reconstruction unit in sectors */ 149 RF_SectorCount_t disk_sectors; /* size of disk in sectors */ 150 RF_ReconUnitCount_t spareUnitsPerDisk; /* zero unless distributed sparing */ 151 { 152 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 153 RF_ReconUnitCount_t num_rus = layoutPtr->stripeUnitsPerDisk / layoutPtr->SUsPerRU; 154 RF_ReconMap_t *p; 155 int rc; 156 157 RF_Malloc(p, sizeof(RF_ReconMap_t), (RF_ReconMap_t *)); 158 p->sectorsPerReconUnit = ru_sectors; 159 p->sectorsInDisk = disk_sectors; 160 161 p->totalRUs = num_rus; 162 p->spareRUs = spareUnitsPerDisk; 163 p->unitsLeft = num_rus - spareUnitsPerDisk; 164 165 RF_Malloc(p->status, num_rus * sizeof(RF_ReconMapListElem_t *), (RF_ReconMapListElem_t **)); 166 RF_ASSERT(p->status != (RF_ReconMapListElem_t **) NULL); 167 168 (void) bzero((char *) p->status, num_rus * sizeof(RF_ReconMapListElem_t *)); 169 170 p->size = sizeof(RF_ReconMap_t) + num_rus * sizeof(RF_ReconMapListElem_t *); 171 p->maxSize = p->size; 172 173 rc = rf_mutex_init(&p->mutex); 174 if (rc) { 175 RF_ERRORMSG3("Unable to init mutex file %s line %d rc=%d\n", __FILE__, 176 __LINE__, rc); 177 RF_Free(p->status, num_rus * sizeof(RF_ReconMapListElem_t *)); 178 RF_Free(p, sizeof(RF_ReconMap_t)); 179 return(NULL); 180 } 181 return(p); 182 } 183 184 185 /*----------------------------------------------------------------------------- 186 * 187 * marks a new set of sectors as reconstructed. All the possible mergings get 188 * complicated. To simplify matters, the approach I take is to just dump 189 * something into the list, and then clean it up (i.e. merge elements and 190 * eliminate redundant ones) in a second pass over the list (compact_stat_entry()). 191 * Not 100% efficient, since a structure can be allocated and then immediately 192 * freed, but it keeps this code from becoming (more of) a nightmare of 193 * special cases. The only thing that compact_stat_entry() assumes is that the 194 * list is sorted by startSector, and so this is the only condition I maintain 195 * here. (MCH) 196 * 197 *-----------------------------------------------------------------------------*/ 198 199 void rf_ReconMapUpdate(raidPtr, mapPtr, startSector, stopSector) 200 RF_Raid_t *raidPtr; 201 RF_ReconMap_t *mapPtr; 202 RF_SectorNum_t startSector; 203 RF_SectorNum_t stopSector; 204 { 205 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit; 206 RF_SectorNum_t i, first_in_RU, last_in_RU; 207 RF_ReconMapListElem_t *p, *pt; 208 209 RF_LOCK_MUTEX(mapPtr->mutex); 210 RF_ASSERT(startSector >=0 && stopSector < mapPtr->sectorsInDisk && stopSector > startSector); 211 212 while (startSector <= stopSector) { 213 i = startSector/mapPtr->sectorsPerReconUnit; 214 first_in_RU = i*sectorsPerReconUnit; 215 last_in_RU = first_in_RU + sectorsPerReconUnit -1 ; 216 p = mapPtr->status[i]; 217 if (p!=RU_ALL) { 218 if (p==RU_NOTHING || p->startSector > startSector ) { /* insert at front of list */ 219 220 mapPtr->status[i] = MakeReconMapListElem(startSector, RF_MIN(stopSector,last_in_RU), (p==RU_NOTHING) ? NULL : p); 221 update_size(mapPtr, sizeof(RF_ReconMapListElem_t)); 222 223 } else { /* general case */ 224 do { /* search for place to insert */ 225 pt = p; p = p->next; 226 } while (p && (p->startSector < startSector)); 227 pt->next = MakeReconMapListElem(startSector,RF_MIN(stopSector,last_in_RU),p); 228 update_size(mapPtr, sizeof(RF_ReconMapListElem_t)); 229 } 230 compact_stat_entry(raidPtr, mapPtr, i); 231 } 232 startSector = RF_MIN(stopSector, last_in_RU) +1; 233 } 234 RF_UNLOCK_MUTEX(mapPtr->mutex); 235 } 236 237 238 239 /*----------------------------------------------------------------------------- 240 * 241 * performs whatever list compactions can be done, and frees any space 242 * that is no longer necessary. Assumes only that the list is sorted 243 * by startSector. crunch_list() compacts a single list as much as possible, 244 * and the second block of code deletes the entire list if possible. 245 * crunch_list() is also called from MakeReconMapAccessList(). 246 * 247 * When a recon unit is detected to be fully reconstructed, we set the 248 * corresponding bit in the parity stripe map so that the head follow 249 * code will not select this parity stripe again. This is redundant (but 250 * harmless) when compact_stat_entry is called from the reconstruction code, 251 * but necessary when called from the user-write code. 252 * 253 *-----------------------------------------------------------------------------*/ 254 255 static void compact_stat_entry(raidPtr, mapPtr, i) 256 RF_Raid_t *raidPtr; 257 RF_ReconMap_t *mapPtr; 258 int i; 259 { 260 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit; 261 RF_ReconMapListElem_t *p = mapPtr->status[i]; 262 263 crunch_list(mapPtr, p); 264 265 if ((p->startSector == i*sectorsPerReconUnit) && 266 (p->stopSector == i*sectorsPerReconUnit +sectorsPerReconUnit -1)) { 267 mapPtr->status[i] = RU_ALL; 268 mapPtr->unitsLeft--; 269 FreeReconMapListElem(mapPtr,p); 270 } 271 } 272 273 static void crunch_list(mapPtr, listPtr) 274 RF_ReconMap_t *mapPtr; 275 RF_ReconMapListElem_t *listPtr; 276 { 277 RF_ReconMapListElem_t *pt, *p = listPtr; 278 279 if (!p) return; 280 pt = p; p = p->next; 281 while (p) { 282 if (pt->stopSector >= p->startSector-1) { 283 pt->stopSector = RF_MAX(pt->stopSector, p->stopSector); 284 pt->next = p->next; 285 FreeReconMapListElem(mapPtr, p); 286 p = pt->next; 287 } 288 else { 289 pt = p; 290 p = p->next; 291 } 292 } 293 } 294 295 /*----------------------------------------------------------------------------- 296 * 297 * Allocate and fill a new list element 298 * 299 *-----------------------------------------------------------------------------*/ 300 301 static RF_ReconMapListElem_t *MakeReconMapListElem( 302 RF_SectorNum_t startSector, 303 RF_SectorNum_t stopSector, 304 RF_ReconMapListElem_t *next) 305 { 306 RF_ReconMapListElem_t *p; 307 308 RF_Malloc(p, sizeof(RF_ReconMapListElem_t), (RF_ReconMapListElem_t *)); 309 if (p == NULL) 310 return(NULL); 311 p->startSector = startSector; 312 p->stopSector = stopSector; 313 p->next = next; 314 return(p); 315 } 316 317 /*----------------------------------------------------------------------------- 318 * 319 * Free a list element 320 * 321 *-----------------------------------------------------------------------------*/ 322 323 static void FreeReconMapListElem(mapPtr,p) 324 RF_ReconMap_t *mapPtr; 325 RF_ReconMapListElem_t *p; 326 { 327 int delta; 328 329 if (mapPtr) { 330 delta = 0 - (int)sizeof(RF_ReconMapListElem_t); 331 update_size(mapPtr, delta); 332 } 333 RF_Free(p, sizeof(*p)); 334 } 335 336 /*----------------------------------------------------------------------------- 337 * 338 * Free an entire status structure. Inefficient, but can be called at any time. 339 * 340 *-----------------------------------------------------------------------------*/ 341 void rf_FreeReconMap(mapPtr) 342 RF_ReconMap_t *mapPtr; 343 { 344 RF_ReconMapListElem_t *p, *q; 345 RF_ReconUnitCount_t numRUs; 346 RF_ReconUnitNum_t i; 347 348 numRUs = mapPtr->sectorsInDisk / mapPtr->sectorsPerReconUnit; 349 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit) 350 numRUs++; 351 352 for (i=0; i<numRUs; i++) { 353 p = mapPtr->status[i]; 354 while (p != RU_NOTHING && p != RU_ALL) { 355 q = p; p = p->next; 356 RF_Free(q, sizeof(*q)); 357 } 358 } 359 rf_mutex_destroy(&mapPtr->mutex); 360 RF_Free(mapPtr->status, mapPtr->totalRUs * sizeof(RF_ReconMapListElem_t *)); 361 RF_Free(mapPtr, sizeof(RF_ReconMap_t)); 362 } 363 364 /*----------------------------------------------------------------------------- 365 * 366 * returns nonzero if the indicated RU has been reconstructed already 367 * 368 *---------------------------------------------------------------------------*/ 369 370 int rf_CheckRUReconstructed(mapPtr, startSector) 371 RF_ReconMap_t *mapPtr; 372 RF_SectorNum_t startSector; 373 { 374 RF_ReconMapListElem_t *l; /* used for searching */ 375 RF_ReconUnitNum_t i; 376 377 i = startSector / mapPtr->sectorsPerReconUnit; 378 l = mapPtr->status[i]; 379 return( (l == RU_ALL) ? 1 : 0 ); 380 } 381 382 RF_ReconUnitCount_t rf_UnitsLeftToReconstruct(mapPtr) 383 RF_ReconMap_t *mapPtr; 384 { 385 RF_ASSERT(mapPtr != NULL); 386 return( mapPtr->unitsLeft ); 387 } 388 389 /* updates the size fields of a status descriptor */ 390 static void update_size(mapPtr, size) 391 RF_ReconMap_t *mapPtr; 392 int size; 393 { 394 mapPtr->size += size; 395 mapPtr->maxSize = RF_MAX(mapPtr->size, mapPtr->maxSize); 396 } 397 398 static void PrintList(listPtr) 399 RF_ReconMapListElem_t *listPtr; 400 { 401 while (listPtr) { 402 printf("%d,%d -> ",(int)listPtr->startSector,(int)listPtr->stopSector); 403 listPtr = listPtr->next; 404 } 405 printf("\n"); 406 } 407 408 void rf_PrintReconMap(raidPtr, mapPtr, frow, fcol) 409 RF_Raid_t *raidPtr; 410 RF_ReconMap_t *mapPtr; 411 RF_RowCol_t frow; 412 RF_RowCol_t fcol; 413 { 414 RF_ReconUnitCount_t numRUs; 415 RF_ReconMapListElem_t *p; 416 RF_ReconUnitNum_t i; 417 418 numRUs = mapPtr->totalRUs; 419 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit) 420 numRUs++; 421 422 for (i=0; i<numRUs; i++) { 423 p = mapPtr->status[i]; 424 if (p==RU_ALL) /*printf("[%d] ALL\n",i)*/; 425 else if (p == RU_NOTHING) { 426 printf("%d: Unreconstructed\n",i); 427 } else { 428 printf("%d: ", i); 429 PrintList(p); 430 } 431 } 432 } 433 434 void rf_PrintReconSchedule(mapPtr, starttime) 435 RF_ReconMap_t *mapPtr; 436 struct timeval *starttime; 437 { 438 static int old_pctg = -1; 439 struct timeval tv, diff; 440 int new_pctg; 441 442 new_pctg = 100 - (rf_UnitsLeftToReconstruct(mapPtr) * 100 / mapPtr->totalRUs); 443 if (new_pctg != old_pctg) { 444 RF_GETTIME(tv); 445 RF_TIMEVAL_DIFF(starttime, &tv, &diff); 446 #if RF_DEMO > 0 447 if (rf_demoMode) { 448 rf_update_recon_meter(new_pctg); 449 } 450 else { 451 printf("%d %d.%06d\n",new_pctg, diff.tv_sec, diff.tv_usec); 452 } 453 #else /* RF_DEMO > 0 */ 454 printf("%d %d.%06d\n",(int)new_pctg, (int)diff.tv_sec, (int)diff.tv_usec); 455 #endif /* RF_DEMO > 0 */ 456 old_pctg = new_pctg; 457 } 458 } 459