1 /* 2 * ea_refcount.c 3 * 4 * Copyright (C) 2001 Theodore Ts'o. This file may be 5 * redistributed under the terms of the GNU Public License. 6 */ 7 8 #if HAVE_UNISTD_H 9 #include <unistd.h> 10 #endif 11 #include <string.h> 12 #include <stdio.h> 13 14 #ifdef TEST_PROGRAM 15 #undef ENABLE_NLS 16 #endif 17 #include "e2fsck.h" 18 19 /* 20 * The strategy we use for keeping track of EA refcounts is as 21 * follows. We keep a sorted array of first EA blocks and its 22 * reference counts. Once the refcount has dropped to zero, it is 23 * removed from the array to save memory space. Once the EA block is 24 * checked, its bit is set in the block_ea_map bitmap. 25 */ 26 struct ea_refcount_el { 27 blk_t ea_blk; 28 int ea_count; 29 }; 30 31 struct ea_refcount { 32 blk_t count; 33 blk_t size; 34 blk_t cursor; 35 struct ea_refcount_el *list; 36 }; 37 38 void ea_refcount_free(ext2_refcount_t refcount) 39 { 40 if (!refcount) 41 return; 42 43 if (refcount->list) 44 ext2fs_free_mem(&refcount->list); 45 ext2fs_free_mem(&refcount); 46 } 47 48 errcode_t ea_refcount_create(int size, ext2_refcount_t *ret) 49 { 50 ext2_refcount_t refcount; 51 errcode_t retval; 52 size_t bytes; 53 54 retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount); 55 if (retval) 56 return retval; 57 memset(refcount, 0, sizeof(struct ea_refcount)); 58 59 if (!size) 60 size = 500; 61 refcount->size = size; 62 bytes = (size_t) (size * sizeof(struct ea_refcount_el)); 63 #ifdef DEBUG 64 printf("Refcount allocated %d entries, %d bytes.\n", 65 refcount->size, bytes); 66 #endif 67 retval = ext2fs_get_mem(bytes, &refcount->list); 68 if (retval) 69 goto errout; 70 memset(refcount->list, 0, bytes); 71 72 refcount->count = 0; 73 refcount->cursor = 0; 74 75 *ret = refcount; 76 return 0; 77 78 errout: 79 ea_refcount_free(refcount); 80 return(retval); 81 } 82 83 /* 84 * collapse_refcount() --- go through the refcount array, and get rid 85 * of any count == zero entries 86 */ 87 static void refcount_collapse(ext2_refcount_t refcount) 88 { 89 unsigned int i, j; 90 struct ea_refcount_el *list; 91 92 list = refcount->list; 93 for (i = 0, j = 0; i < refcount->count; i++) { 94 if (list[i].ea_count) { 95 if (i != j) 96 list[j] = list[i]; 97 j++; 98 } 99 } 100 #if defined(DEBUG) || defined(TEST_PROGRAM) 101 printf("Refcount_collapse: size was %d, now %d\n", 102 refcount->count, j); 103 #endif 104 refcount->count = j; 105 } 106 107 108 /* 109 * insert_refcount_el() --- Insert a new entry into the sorted list at a 110 * specified position. 111 */ 112 static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount, 113 blk_t blk, int pos) 114 { 115 struct ea_refcount_el *el; 116 errcode_t retval; 117 blk_t new_size = 0; 118 int num; 119 120 if (refcount->count >= refcount->size) { 121 new_size = refcount->size + 100; 122 #ifdef DEBUG 123 printf("Reallocating refcount %d entries...\n", new_size); 124 #endif 125 retval = ext2fs_resize_mem((size_t) refcount->size * 126 sizeof(struct ea_refcount_el), 127 (size_t) new_size * 128 sizeof(struct ea_refcount_el), 129 &refcount->list); 130 if (retval) 131 return 0; 132 refcount->size = new_size; 133 } 134 num = (int) refcount->count - pos; 135 if (num < 0) 136 return 0; /* should never happen */ 137 if (num) { 138 memmove(&refcount->list[pos+1], &refcount->list[pos], 139 sizeof(struct ea_refcount_el) * num); 140 } 141 refcount->count++; 142 el = &refcount->list[pos]; 143 el->ea_count = 0; 144 el->ea_blk = blk; 145 return el; 146 } 147 148 149 /* 150 * get_refcount_el() --- given an block number, try to find refcount 151 * information in the sorted list. If the create flag is set, 152 * and we can't find an entry, create one in the sorted list. 153 */ 154 static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount, 155 blk_t blk, int create) 156 { 157 float range; 158 int low, high, mid; 159 blk_t lowval, highval; 160 161 if (!refcount || !refcount->list) 162 return 0; 163 retry: 164 low = 0; 165 high = (int) refcount->count-1; 166 if (create && ((refcount->count == 0) || 167 (blk > refcount->list[high].ea_blk))) { 168 if (refcount->count >= refcount->size) 169 refcount_collapse(refcount); 170 171 return insert_refcount_el(refcount, blk, 172 (unsigned) refcount->count); 173 } 174 if (refcount->count == 0) 175 return 0; 176 177 if (refcount->cursor >= refcount->count) 178 refcount->cursor = 0; 179 if (blk == refcount->list[refcount->cursor].ea_blk) 180 return &refcount->list[refcount->cursor++]; 181 #ifdef DEBUG 182 printf("Non-cursor get_refcount_el: %u\n", blk); 183 #endif 184 while (low <= high) { 185 #if 0 186 mid = (low+high)/2; 187 #else 188 if (low == high) 189 mid = low; 190 else { 191 /* Interpolate for efficiency */ 192 lowval = refcount->list[low].ea_blk; 193 highval = refcount->list[high].ea_blk; 194 195 if (blk < lowval) 196 range = 0; 197 else if (blk > highval) 198 range = 1; 199 else 200 range = ((float) (blk - lowval)) / 201 (highval - lowval); 202 mid = low + ((int) (range * (high-low))); 203 } 204 #endif 205 if (blk == refcount->list[mid].ea_blk) { 206 refcount->cursor = mid+1; 207 return &refcount->list[mid]; 208 } 209 if (blk < refcount->list[mid].ea_blk) 210 high = mid-1; 211 else 212 low = mid+1; 213 } 214 /* 215 * If we need to create a new entry, it should be right at 216 * low (where high will be left at low-1). 217 */ 218 if (create) { 219 if (refcount->count >= refcount->size) { 220 refcount_collapse(refcount); 221 if (refcount->count < refcount->size) 222 goto retry; 223 } 224 return insert_refcount_el(refcount, blk, low); 225 } 226 return 0; 227 } 228 229 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk, 230 int *ret) 231 { 232 struct ea_refcount_el *el; 233 234 el = get_refcount_el(refcount, blk, 0); 235 if (!el) { 236 *ret = 0; 237 return 0; 238 } 239 *ret = el->ea_count; 240 return 0; 241 } 242 243 errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret) 244 { 245 struct ea_refcount_el *el; 246 247 el = get_refcount_el(refcount, blk, 1); 248 if (!el) 249 return EXT2_ET_NO_MEMORY; 250 el->ea_count++; 251 252 if (ret) 253 *ret = el->ea_count; 254 return 0; 255 } 256 257 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret) 258 { 259 struct ea_refcount_el *el; 260 261 el = get_refcount_el(refcount, blk, 0); 262 if (!el || el->ea_count == 0) 263 return EXT2_ET_INVALID_ARGUMENT; 264 265 el->ea_count--; 266 267 if (ret) 268 *ret = el->ea_count; 269 return 0; 270 } 271 272 errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count) 273 { 274 struct ea_refcount_el *el; 275 276 /* 277 * Get the refcount element 278 */ 279 el = get_refcount_el(refcount, blk, count ? 1 : 0); 280 if (!el) 281 return count ? EXT2_ET_NO_MEMORY : 0; 282 el->ea_count = count; 283 return 0; 284 } 285 286 blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount) 287 { 288 if (!refcount) 289 return 0; 290 291 return refcount->size; 292 } 293 294 void ea_refcount_intr_begin(ext2_refcount_t refcount) 295 { 296 refcount->cursor = 0; 297 } 298 299 300 blk_t ea_refcount_intr_next(ext2_refcount_t refcount, 301 int *ret) 302 { 303 struct ea_refcount_el *list; 304 305 while (1) { 306 if (refcount->cursor >= refcount->count) 307 return 0; 308 list = refcount->list; 309 if (list[refcount->cursor].ea_count) { 310 if (ret) 311 *ret = list[refcount->cursor].ea_count; 312 return list[refcount->cursor++].ea_blk; 313 } 314 refcount->cursor++; 315 } 316 } 317 318 319 #ifdef TEST_PROGRAM 320 321 errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out) 322 { 323 errcode_t ret = 0; 324 int i; 325 const char *bad = "bad refcount"; 326 327 if (refcount->count > refcount->size) { 328 fprintf(out, "%s: count > size\n", bad); 329 return EXT2_ET_INVALID_ARGUMENT; 330 } 331 for (i=1; i < refcount->count; i++) { 332 if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) { 333 fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n", 334 bad, i-1, refcount->list[i-1].ea_blk, 335 i, refcount->list[i].ea_blk); 336 ret = EXT2_ET_INVALID_ARGUMENT; 337 } 338 } 339 return ret; 340 } 341 342 #define BCODE_END 0 343 #define BCODE_CREATE 1 344 #define BCODE_FREE 2 345 #define BCODE_STORE 3 346 #define BCODE_INCR 4 347 #define BCODE_DECR 5 348 #define BCODE_FETCH 6 349 #define BCODE_VALIDATE 7 350 #define BCODE_LIST 8 351 #define BCODE_COLLAPSE 9 352 353 int bcode_program[] = { 354 BCODE_CREATE, 5, 355 BCODE_STORE, 3, 3, 356 BCODE_STORE, 4, 4, 357 BCODE_STORE, 1, 1, 358 BCODE_STORE, 8, 8, 359 BCODE_STORE, 2, 2, 360 BCODE_STORE, 4, 0, 361 BCODE_STORE, 2, 0, 362 BCODE_STORE, 6, 6, 363 BCODE_VALIDATE, 364 BCODE_STORE, 4, 4, 365 BCODE_STORE, 2, 2, 366 BCODE_FETCH, 1, 367 BCODE_FETCH, 2, 368 BCODE_INCR, 3, 369 BCODE_INCR, 3, 370 BCODE_DECR, 4, 371 BCODE_STORE, 4, 4, 372 BCODE_VALIDATE, 373 BCODE_STORE, 20, 20, 374 BCODE_STORE, 40, 40, 375 BCODE_STORE, 30, 30, 376 BCODE_STORE, 10, 10, 377 BCODE_DECR, 30, 378 BCODE_FETCH, 30, 379 BCODE_DECR, 2, 380 BCODE_DECR, 2, 381 BCODE_COLLAPSE, 382 BCODE_LIST, 383 BCODE_VALIDATE, 384 BCODE_FREE, 385 BCODE_END 386 }; 387 388 int main(int argc, char **argv) 389 { 390 int i = 0; 391 ext2_refcount_t refcount; 392 int size, arg; 393 blk_t blk; 394 errcode_t retval; 395 396 while (1) { 397 switch (bcode_program[i++]) { 398 case BCODE_END: 399 exit(0); 400 case BCODE_CREATE: 401 size = bcode_program[i++]; 402 retval = ea_refcount_create(size, &refcount); 403 if (retval) { 404 com_err("ea_refcount_create", 405 retval, ""); 406 exit(1); 407 } else 408 printf("Creating refcount with size %d\n", 409 size); 410 break; 411 case BCODE_FREE: 412 ea_refcount_free(refcount); 413 refcount = 0; 414 printf("Freeing refcount\n"); 415 break; 416 case BCODE_STORE: 417 blk = (blk_t) bcode_program[i++]; 418 arg = bcode_program[i++]; 419 retval = ea_refcount_store(refcount, blk, arg); 420 printf("Storing blk %u with value %d\n", blk, arg); 421 if (retval) 422 com_err("ea_refcount_store", retval, ""); 423 break; 424 case BCODE_FETCH: 425 blk = (blk_t) bcode_program[i++]; 426 retval = ea_refcount_fetch(refcount, blk, &arg); 427 if (retval) 428 com_err("ea_refcount_fetch", retval, ""); 429 else 430 printf("bcode_fetch(%u) returns %d\n", 431 blk, arg); 432 break; 433 case BCODE_INCR: 434 blk = (blk_t) bcode_program[i++]; 435 retval = ea_refcount_increment(refcount, blk, 436 &arg); 437 if (retval) 438 com_err("ea_refcount_increment", retval, 439 ""); 440 else 441 printf("bcode_increment(%u) returns %d\n", 442 blk, arg); 443 break; 444 case BCODE_DECR: 445 blk = (blk_t) bcode_program[i++]; 446 retval = ea_refcount_decrement(refcount, blk, 447 &arg); 448 if (retval) 449 com_err("ea_refcount_decrement", retval, 450 "while decrementing blk %u", blk); 451 else 452 printf("bcode_decrement(%u) returns %d\n", 453 blk, arg); 454 break; 455 case BCODE_VALIDATE: 456 retval = ea_refcount_validate(refcount, stderr); 457 if (retval) 458 com_err("ea_refcount_validate", 459 retval, ""); 460 else 461 printf("Refcount validation OK.\n"); 462 break; 463 case BCODE_LIST: 464 ea_refcount_intr_begin(refcount); 465 while (1) { 466 blk = ea_refcount_intr_next(refcount, 467 &arg); 468 if (!blk) 469 break; 470 printf("\tblk=%u, count=%d\n", blk, 471 arg); 472 } 473 break; 474 case BCODE_COLLAPSE: 475 refcount_collapse(refcount); 476 break; 477 } 478 479 } 480 } 481 482 #endif 483
