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