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