1 /* $NetBSD: rf_reconmap.c,v 1.22 2003/12/30 21:59:03 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.22 2003/12/30 21:59:03 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 * ru_sectors - size of reconstruction unit in sectors 82 * disk_sectors - size of disk in sectors 83 * spareUnitsPerDisk - zero unless distributed sparing 84 *-------------------------------------------------------------------------*/ 85 86 RF_ReconMap_t * 87 rf_MakeReconMap(RF_Raid_t *raidPtr, RF_SectorCount_t ru_sectors, 88 RF_SectorCount_t disk_sectors, 89 RF_ReconUnitCount_t spareUnitsPerDisk) 90 { 91 RF_RaidLayout_t *layoutPtr = &raidPtr->Layout; 92 RF_ReconUnitCount_t num_rus = layoutPtr->stripeUnitsPerDisk / layoutPtr->SUsPerRU; 93 RF_ReconMap_t *p; 94 95 RF_Malloc(p, sizeof(RF_ReconMap_t), (RF_ReconMap_t *)); 96 p->sectorsPerReconUnit = ru_sectors; 97 p->sectorsInDisk = disk_sectors; 98 99 p->totalRUs = num_rus; 100 p->spareRUs = spareUnitsPerDisk; 101 p->unitsLeft = num_rus - spareUnitsPerDisk; 102 103 RF_Malloc(p->status, num_rus * sizeof(RF_ReconMapListElem_t *), (RF_ReconMapListElem_t **)); 104 RF_ASSERT(p->status != (RF_ReconMapListElem_t **) NULL); 105 106 (void) memset((char *) p->status, 0, 107 num_rus * sizeof(RF_ReconMapListElem_t *)); 108 109 110 pool_init(&p->elem_pool, sizeof(RF_ReconMapListElem_t), 0, 111 0, 0, "raidreconpl", NULL); 112 pool_prime(&p->elem_pool, RF_NUM_RECON_POOL_ELEM); 113 114 rf_mutex_init(&p->mutex); 115 return (p); 116 } 117 118 119 /*--------------------------------------------------------------------------- 120 * 121 * marks a new set of sectors as reconstructed. All the possible 122 * mergings get complicated. To simplify matters, the approach I take 123 * is to just dump something into the list, and then clean it up 124 * (i.e. merge elements and eliminate redundant ones) in a second pass 125 * over the list (compact_stat_entry()). Not 100% efficient, since a 126 * structure can be allocated and then immediately freed, but it keeps 127 * this code from becoming (more of) a nightmare of special cases. 128 * The only thing that compact_stat_entry() assumes is that the list 129 * is sorted by startSector, and so this is the only condition I 130 * maintain here. (MCH) 131 * 132 * This code now uses a pool instead of the previous malloc/free 133 * stuff. 134 *-------------------------------------------------------------------------*/ 135 136 void 137 rf_ReconMapUpdate(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, 138 RF_SectorNum_t startSector, RF_SectorNum_t stopSector) 139 { 140 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit; 141 RF_SectorNum_t i, first_in_RU, last_in_RU; 142 RF_ReconMapListElem_t *p, *pt; 143 144 RF_LOCK_MUTEX(mapPtr->mutex); 145 RF_ASSERT(startSector >= 0 && stopSector < mapPtr->sectorsInDisk && 146 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) { 155 /* insert at front of list */ 156 157 mapPtr->status[i] = MakeReconMapListElem(mapPtr,startSector, RF_MIN(stopSector, last_in_RU), (p == RU_NOTHING) ? NULL : p); 158 159 } else {/* general case */ 160 do { /* search for place to insert */ 161 pt = p; 162 p = p->next; 163 } while (p && (p->startSector < startSector)); 164 pt->next = MakeReconMapListElem(mapPtr,startSector, RF_MIN(stopSector, last_in_RU), p); 165 166 } 167 compact_stat_entry(raidPtr, mapPtr, i); 168 } 169 startSector = RF_MIN(stopSector, last_in_RU) + 1; 170 } 171 RF_UNLOCK_MUTEX(mapPtr->mutex); 172 } 173 174 175 176 /*--------------------------------------------------------------------------- 177 * 178 * performs whatever list compactions can be done, and frees any space 179 * that is no longer necessary. Assumes only that the list is sorted 180 * by startSector. crunch_list() compacts a single list as much as 181 * possible, and the second block of code deletes the entire list if 182 * possible. crunch_list() is also called from 183 * 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 188 * (but harmless) when compact_stat_entry is called from the 189 * reconstruction code, but necessary when called from the user-write 190 * code. 191 * 192 *-------------------------------------------------------------------------*/ 193 194 static void 195 compact_stat_entry(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, int i) 196 { 197 RF_SectorCount_t sectorsPerReconUnit = mapPtr->sectorsPerReconUnit; 198 RF_ReconMapListElem_t *p = mapPtr->status[i]; 199 200 crunch_list(mapPtr, p); 201 202 if ((p->startSector == i * sectorsPerReconUnit) && 203 (p->stopSector == i * sectorsPerReconUnit + 204 sectorsPerReconUnit - 1)) { 205 mapPtr->status[i] = RU_ALL; 206 mapPtr->unitsLeft--; 207 FreeReconMapListElem(mapPtr, p); 208 } 209 } 210 211 static void 212 crunch_list(RF_ReconMap_t *mapPtr, 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(RF_ReconMap_t *mapPtr, RF_SectorNum_t startSector, 240 RF_SectorNum_t stopSector, RF_ReconMapListElem_t *next) 241 { 242 RF_ReconMapListElem_t *p; 243 244 p = pool_get(&mapPtr->elem_pool, PR_WAITOK); 245 246 if (p == NULL) 247 return (NULL); 248 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(RF_ReconMap_t *mapPtr, RF_ReconMapListElem_t *p) 262 { 263 pool_put(&mapPtr->elem_pool, p); 264 } 265 /*--------------------------------------------------------------------------- 266 * 267 * Free an entire status structure. Inefficient, but can be called at 268 * any time. 269 * 270 *-------------------------------------------------------------------------*/ 271 void 272 rf_FreeReconMap(RF_ReconMap_t *mapPtr) 273 { 274 RF_ReconMapListElem_t *p, *q; 275 RF_ReconUnitCount_t numRUs; 276 RF_ReconUnitNum_t i; 277 278 numRUs = mapPtr->sectorsInDisk / mapPtr->sectorsPerReconUnit; 279 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit) 280 numRUs++; 281 282 for (i = 0; i < numRUs; i++) { 283 p = mapPtr->status[i]; 284 while (p != RU_NOTHING && p != RU_ALL) { 285 q = p; 286 p = p->next; 287 RF_Free(q, sizeof(*q)); 288 } 289 } 290 pool_destroy(&mapPtr->elem_pool); 291 RF_Free(mapPtr->status, mapPtr->totalRUs * 292 sizeof(RF_ReconMapListElem_t *)); 293 RF_Free(mapPtr, sizeof(RF_ReconMap_t)); 294 } 295 /*--------------------------------------------------------------------------- 296 * 297 * returns nonzero if the indicated RU has been reconstructed already 298 * 299 *-------------------------------------------------------------------------*/ 300 301 int 302 rf_CheckRUReconstructed(RF_ReconMap_t *mapPtr, RF_SectorNum_t startSector) 303 { 304 RF_ReconMapListElem_t *l; /* used for searching */ 305 RF_ReconUnitNum_t i; 306 307 i = startSector / mapPtr->sectorsPerReconUnit; 308 l = mapPtr->status[i]; 309 return ((l == RU_ALL) ? 1 : 0); 310 } 311 312 RF_ReconUnitCount_t 313 rf_UnitsLeftToReconstruct(RF_ReconMap_t *mapPtr) 314 { 315 RF_ASSERT(mapPtr != NULL); 316 return (mapPtr->unitsLeft); 317 } 318 319 #if 0 320 static void 321 PrintList(RF_ReconMapListElem_t *listPtr) 322 { 323 while (listPtr) { 324 printf("%d,%d -> ", (int) listPtr->startSector, 325 (int) listPtr->stopSector); 326 listPtr = listPtr->next; 327 } 328 printf("\n"); 329 } 330 331 void 332 rf_PrintReconMap(RF_Raid_t *raidPtr, RF_ReconMap_t *mapPtr, RF_RowCol_t fcol) 333 { 334 RF_ReconUnitCount_t numRUs; 335 RF_ReconMapListElem_t *p; 336 RF_ReconUnitNum_t i; 337 338 numRUs = mapPtr->totalRUs; 339 if (mapPtr->sectorsInDisk % mapPtr->sectorsPerReconUnit) 340 numRUs++; 341 342 for (i = 0; i < numRUs; i++) { 343 p = mapPtr->status[i]; 344 if (p == RU_ALL)/* printf("[%d] ALL\n",i) */ 345 ; 346 else 347 if (p == RU_NOTHING) { 348 printf("%d: Unreconstructed\n", i); 349 } else { 350 printf("%d: ", i); 351 PrintList(p); 352 } 353 } 354 } 355 #endif 356 357 #if RF_DEBUG_RECON 358 void 359 rf_PrintReconSchedule(RF_ReconMap_t *mapPtr, struct timeval *starttime) 360 { 361 static int old_pctg = -1; 362 struct timeval tv, diff; 363 int new_pctg; 364 365 new_pctg = 100 - (rf_UnitsLeftToReconstruct(mapPtr) * 366 100 / mapPtr->totalRUs); 367 if (new_pctg != old_pctg) { 368 RF_GETTIME(tv); 369 RF_TIMEVAL_DIFF(starttime, &tv, &diff); 370 printf("%d %d.%06d\n", (int) new_pctg, (int) diff.tv_sec, 371 (int) diff.tv_usec); 372 old_pctg = new_pctg; 373 } 374 } 375 #endif 376 377