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