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