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 if (range > 0.9) 203 range = 0.9; 204 if (range < 0.1) 205 range = 0.1; 206 } 207 mid = low + ((int) (range * (high-low))); 208 } 209 #endif 210 if (blk == refcount->list[mid].ea_blk) { 211 refcount->cursor = mid+1; 212 return &refcount->list[mid]; 213 } 214 if (blk < refcount->list[mid].ea_blk) 215 high = mid-1; 216 else 217 low = mid+1; 218 } 219 /* 220 * If we need to create a new entry, it should be right at 221 * low (where high will be left at low-1). 222 */ 223 if (create) { 224 if (refcount->count >= refcount->size) { 225 refcount_collapse(refcount); 226 if (refcount->count < refcount->size) 227 goto retry; 228 } 229 return insert_refcount_el(refcount, blk, low); 230 } 231 return 0; 232 } 233 234 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk, 235 int *ret) 236 { 237 struct ea_refcount_el *el; 238 239 el = get_refcount_el(refcount, blk, 0); 240 if (!el) { 241 *ret = 0; 242 return 0; 243 } 244 *ret = el->ea_count; 245 return 0; 246 } 247 248 errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret) 249 { 250 struct ea_refcount_el *el; 251 252 el = get_refcount_el(refcount, blk, 1); 253 if (!el) 254 return EXT2_ET_NO_MEMORY; 255 el->ea_count++; 256 257 if (ret) 258 *ret = el->ea_count; 259 return 0; 260 } 261 262 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret) 263 { 264 struct ea_refcount_el *el; 265 266 el = get_refcount_el(refcount, blk, 0); 267 if (!el || el->ea_count == 0) 268 return EXT2_ET_INVALID_ARGUMENT; 269 270 el->ea_count--; 271 272 if (ret) 273 *ret = el->ea_count; 274 return 0; 275 } 276 277 errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count) 278 { 279 struct ea_refcount_el *el; 280 281 /* 282 * Get the refcount element 283 */ 284 el = get_refcount_el(refcount, blk, count ? 1 : 0); 285 if (!el) 286 return count ? EXT2_ET_NO_MEMORY : 0; 287 el->ea_count = count; 288 return 0; 289 } 290 291 blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount) 292 { 293 if (!refcount) 294 return 0; 295 296 return refcount->size; 297 } 298 299 void ea_refcount_intr_begin(ext2_refcount_t refcount) 300 { 301 refcount->cursor = 0; 302 } 303 304 305 blk_t ea_refcount_intr_next(ext2_refcount_t refcount, 306 int *ret) 307 { 308 struct ea_refcount_el *list; 309 310 while (1) { 311 if (refcount->cursor >= refcount->count) 312 return 0; 313 list = refcount->list; 314 if (list[refcount->cursor].ea_count) { 315 if (ret) 316 *ret = list[refcount->cursor].ea_count; 317 return list[refcount->cursor++].ea_blk; 318 } 319 refcount->cursor++; 320 } 321 } 322 323 324 #ifdef TEST_PROGRAM 325 326 errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out) 327 { 328 errcode_t ret = 0; 329 int i; 330 const char *bad = "bad refcount"; 331 332 if (refcount->count > refcount->size) { 333 fprintf(out, "%s: count > size\n", bad); 334 return EXT2_ET_INVALID_ARGUMENT; 335 } 336 for (i=1; i < refcount->count; i++) { 337 if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) { 338 fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n", 339 bad, i-1, refcount->list[i-1].ea_blk, 340 i, refcount->list[i].ea_blk); 341 ret = EXT2_ET_INVALID_ARGUMENT; 342 } 343 } 344 return ret; 345 } 346 347 #define BCODE_END 0 348 #define BCODE_CREATE 1 349 #define BCODE_FREE 2 350 #define BCODE_STORE 3 351 #define BCODE_INCR 4 352 #define BCODE_DECR 5 353 #define BCODE_FETCH 6 354 #define BCODE_VALIDATE 7 355 #define BCODE_LIST 8 356 #define BCODE_COLLAPSE 9 357 358 int bcode_program[] = { 359 BCODE_CREATE, 5, 360 BCODE_STORE, 3, 3, 361 BCODE_STORE, 4, 4, 362 BCODE_STORE, 1, 1, 363 BCODE_STORE, 8, 8, 364 BCODE_STORE, 2, 2, 365 BCODE_STORE, 4, 0, 366 BCODE_STORE, 2, 0, 367 BCODE_STORE, 6, 6, 368 BCODE_VALIDATE, 369 BCODE_STORE, 4, 4, 370 BCODE_STORE, 2, 2, 371 BCODE_FETCH, 1, 372 BCODE_FETCH, 2, 373 BCODE_INCR, 3, 374 BCODE_INCR, 3, 375 BCODE_DECR, 4, 376 BCODE_STORE, 4, 4, 377 BCODE_VALIDATE, 378 BCODE_STORE, 20, 20, 379 BCODE_STORE, 40, 40, 380 BCODE_STORE, 30, 30, 381 BCODE_STORE, 10, 10, 382 BCODE_DECR, 30, 383 BCODE_FETCH, 30, 384 BCODE_DECR, 2, 385 BCODE_DECR, 2, 386 BCODE_COLLAPSE, 387 BCODE_LIST, 388 BCODE_VALIDATE, 389 BCODE_FREE, 390 BCODE_END 391 }; 392 393 int main(int argc, char **argv) 394 { 395 int i = 0; 396 ext2_refcount_t refcount; 397 int size, arg; 398 blk_t blk; 399 errcode_t retval; 400 401 while (1) { 402 switch (bcode_program[i++]) { 403 case BCODE_END: 404 exit(0); 405 case BCODE_CREATE: 406 size = bcode_program[i++]; 407 retval = ea_refcount_create(size, &refcount); 408 if (retval) { 409 com_err("ea_refcount_create", 410 retval, ""); 411 exit(1); 412 } else 413 printf("Creating refcount with size %d\n", 414 size); 415 break; 416 case BCODE_FREE: 417 ea_refcount_free(refcount); 418 refcount = 0; 419 printf("Freeing refcount\n"); 420 break; 421 case BCODE_STORE: 422 blk = (blk_t) bcode_program[i++]; 423 arg = bcode_program[i++]; 424 retval = ea_refcount_store(refcount, blk, arg); 425 printf("Storing blk %u with value %d\n", blk, arg); 426 if (retval) 427 com_err("ea_refcount_store", retval, ""); 428 break; 429 case BCODE_FETCH: 430 blk = (blk_t) bcode_program[i++]; 431 retval = ea_refcount_fetch(refcount, blk, &arg); 432 if (retval) 433 com_err("ea_refcount_fetch", retval, ""); 434 else 435 printf("bcode_fetch(%u) returns %d\n", 436 blk, arg); 437 break; 438 case BCODE_INCR: 439 blk = (blk_t) bcode_program[i++]; 440 retval = ea_refcount_increment(refcount, blk, 441 &arg); 442 if (retval) 443 com_err("ea_refcount_increment", retval, 444 ""); 445 else 446 printf("bcode_increment(%u) returns %d\n", 447 blk, arg); 448 break; 449 case BCODE_DECR: 450 blk = (blk_t) bcode_program[i++]; 451 retval = ea_refcount_decrement(refcount, blk, 452 &arg); 453 if (retval) 454 com_err("ea_refcount_decrement", retval, 455 "while decrementing blk %u", blk); 456 else 457 printf("bcode_decrement(%u) returns %d\n", 458 blk, arg); 459 break; 460 case BCODE_VALIDATE: 461 retval = ea_refcount_validate(refcount, stderr); 462 if (retval) 463 com_err("ea_refcount_validate", 464 retval, ""); 465 else 466 printf("Refcount validation OK.\n"); 467 break; 468 case BCODE_LIST: 469 ea_refcount_intr_begin(refcount); 470 while (1) { 471 blk = ea_refcount_intr_next(refcount, 472 &arg); 473 if (!blk) 474 break; 475 printf("\tblk=%u, count=%d\n", blk, 476 arg); 477 } 478 break; 479 case BCODE_COLLAPSE: 480 refcount_collapse(refcount); 481 break; 482 } 483 484 } 485 } 486 487 #endif 488
