ea_refcount.c revision 65f0aab98b20b5994a726ab90d355248bcddfffd
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 */ 26struct ea_refcount_el { 27 blk_t ea_blk; 28 int ea_count; 29}; 30 31struct ea_refcount { 32 blk_t count; 33 blk_t size; 34 blk_t cursor; 35 struct ea_refcount_el *list; 36}; 37 38void 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 48errcode_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 78errout: 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 */ 87static 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 */ 112static 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 */ 154static 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; 163retry: 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 234errcode_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 248errcode_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 262errcode_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 277errcode_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 291blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount) 292{ 293 if (!refcount) 294 return 0; 295 296 return refcount->size; 297} 298 299void ea_refcount_intr_begin(ext2_refcount_t refcount) 300{ 301 refcount->cursor = 0; 302} 303 304 305blk_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 326errcode_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 358int 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 393int 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