1 /* 2 * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and 3 * block bitmaps. 4 * 5 * Copyright (C) 2007, 2008 Theodore Ts'o. 6 * 7 * %Begin-Header% 8 * This file may be redistributed under the terms of the GNU Public 9 * License. 10 * %End-Header% 11 */ 12 13 #include "config.h" 14 #include <stdio.h> 15 #include <string.h> 16 #if HAVE_UNISTD_H 17 #include <unistd.h> 18 #endif 19 #include <fcntl.h> 20 #include <time.h> 21 #include <errno.h> 22 #if HAVE_SYS_STAT_H 23 #include <sys/stat.h> 24 #endif 25 #if HAVE_SYS_TYPES_H 26 #include <sys/types.h> 27 #endif 28 #ifdef HAVE_SYS_TIME_H 29 #include <sys/time.h> 30 #endif 31 32 #include "ext2_fs.h" 33 #include "ext2fsP.h" 34 #include "bmap64.h" 35 36 /* 37 * Design of 64-bit bitmaps 38 * 39 * In order maintain ABI compatibility with programs that don't 40 * understand about 64-bit blocks/inodes, 41 * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap() 42 * will create old-style bitmaps unless the application passes the 43 * flag EXT2_FLAG_64BITS to ext2fs_open(). If this flag is 44 * passed, then we know the application has been recompiled, so we can 45 * use the new-style bitmaps. If it is not passed, we have to return 46 * an error if trying to open a filesystem which needs 64-bit bitmaps. 47 * 48 * The new bitmaps use a new set of structure magic numbers, so that 49 * both the old-style and new-style interfaces can identify which 50 * version of the data structure was used. Both the old-style and 51 * new-style interfaces will support either type of bitmap, although 52 * of course 64-bit operation will only be possible when both the 53 * new-style interface and the new-style bitmap are used. 54 * 55 * For example, the new bitmap interfaces will check the structure 56 * magic numbers and so will be able to detect old-stype bitmap. If 57 * they see an old-style bitmap, they will pass it to the gen_bitmap.c 58 * functions for handling. The same will be true for the old 59 * interfaces as well. 60 * 61 * The new-style interfaces will have several different back-end 62 * implementations, so we can support different encodings that are 63 * appropriate for different applications. In general the default 64 * should be whatever makes sense, and what the application/library 65 * will use. However, e2fsck may need specialized implementations for 66 * its own uses. For example, when doing parent directory pointer 67 * loop detections in pass 3, the bitmap will *always* be sparse, so 68 * e2fsck can request an encoding which is optimized for that. 69 */ 70 71 static void warn_bitmap(ext2fs_generic_bitmap_64 bitmap, 72 int code, __u64 arg) 73 { 74 #ifndef OMIT_COM_ERR 75 if (bitmap->description) 76 com_err(0, bitmap->base_error_code+code, 77 "#%llu for %s", (unsigned long long) arg, 78 bitmap->description); 79 else 80 com_err(0, bitmap->base_error_code + code, "#%llu", 81 (unsigned long long) arg); 82 #endif 83 } 84 85 #ifdef ENABLE_BMAP_STATS_OPS 86 #define INC_STAT(map, name) map->stats.name 87 #else 88 #define INC_STAT(map, name) ;; 89 #endif 90 91 92 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic, 93 int type, __u64 start, __u64 end, 94 __u64 real_end, 95 const char *descr, 96 ext2fs_generic_bitmap *ret) 97 { 98 ext2fs_generic_bitmap_64 bitmap; 99 struct ext2_bitmap_ops *ops; 100 ext2_ino_t num_dirs; 101 errcode_t retval; 102 103 if (!type) 104 type = EXT2FS_BMAP64_BITARRAY; 105 106 switch (type) { 107 case EXT2FS_BMAP64_BITARRAY: 108 ops = &ext2fs_blkmap64_bitarray; 109 break; 110 case EXT2FS_BMAP64_RBTREE: 111 ops = &ext2fs_blkmap64_rbtree; 112 break; 113 case EXT2FS_BMAP64_AUTODIR: 114 retval = ext2fs_get_num_dirs(fs, &num_dirs); 115 if (retval || num_dirs > (fs->super->s_inodes_count / 320)) 116 ops = &ext2fs_blkmap64_bitarray; 117 else 118 ops = &ext2fs_blkmap64_rbtree; 119 break; 120 default: 121 return EINVAL; 122 } 123 124 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64), 125 &bitmap); 126 if (retval) 127 return retval; 128 129 #ifdef ENABLE_BMAP_STATS 130 if (gettimeofday(&bitmap->stats.created, 131 (struct timezone *) NULL) == -1) { 132 perror("gettimeofday"); 133 ext2fs_free_mem(&bitmap); 134 return 1; 135 } 136 bitmap->stats.type = type; 137 #endif 138 139 /* XXX factor out, repeated in copy_bmap */ 140 bitmap->magic = magic; 141 bitmap->fs = fs; 142 bitmap->start = start; 143 bitmap->end = end; 144 bitmap->real_end = real_end; 145 bitmap->bitmap_ops = ops; 146 bitmap->cluster_bits = 0; 147 switch (magic) { 148 case EXT2_ET_MAGIC_INODE_BITMAP64: 149 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; 150 break; 151 case EXT2_ET_MAGIC_BLOCK_BITMAP64: 152 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; 153 bitmap->cluster_bits = fs->cluster_ratio_bits; 154 break; 155 default: 156 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; 157 } 158 if (descr) { 159 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); 160 if (retval) { 161 ext2fs_free_mem(&bitmap); 162 return retval; 163 } 164 strcpy(bitmap->description, descr); 165 } else 166 bitmap->description = 0; 167 168 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap); 169 if (retval) { 170 ext2fs_free_mem(&bitmap->description); 171 ext2fs_free_mem(&bitmap); 172 return retval; 173 } 174 175 *ret = (ext2fs_generic_bitmap) bitmap; 176 return 0; 177 } 178 179 #ifdef ENABLE_BMAP_STATS 180 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap) 181 { 182 struct ext2_bmap_statistics *stats = &bitmap->stats; 183 #ifdef ENABLE_BMAP_STATS_OPS 184 float mark_seq_perc = 0.0, test_seq_perc = 0.0; 185 float mark_back_perc = 0.0, test_back_perc = 0.0; 186 #endif 187 double inuse; 188 struct timeval now; 189 190 #ifdef ENABLE_BMAP_STATS_OPS 191 if (stats->test_count) { 192 test_seq_perc = ((float)stats->test_seq / 193 stats->test_count) * 100; 194 test_back_perc = ((float)stats->test_back / 195 stats->test_count) * 100; 196 } 197 198 if (stats->mark_count) { 199 mark_seq_perc = ((float)stats->mark_seq / 200 stats->mark_count) * 100; 201 mark_back_perc = ((float)stats->mark_back / 202 stats->mark_count) * 100; 203 } 204 #endif 205 206 if (gettimeofday(&now, (struct timezone *) NULL) == -1) { 207 perror("gettimeofday"); 208 return; 209 } 210 211 inuse = (double) now.tv_sec + \ 212 (((double) now.tv_usec) * 0.000001); 213 inuse -= (double) stats->created.tv_sec + \ 214 (((double) stats->created.tv_usec) * 0.000001); 215 216 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description, 217 stats->type); 218 fprintf(stderr, "=================================================\n"); 219 #ifdef ENABLE_BMAP_STATS_OPS 220 fprintf(stderr, "%16llu bits long\n", 221 bitmap->real_end - bitmap->start); 222 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n", 223 stats->copy_count, stats->resize_count); 224 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n", 225 stats->mark_count, stats->unmark_count); 226 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n", 227 stats->test_count, stats->mark_ext_count); 228 fprintf(stderr, "%16lu unmark_bmap_extent\n" 229 "%16lu test_clear_bmap_extent\n", 230 stats->unmark_ext_count, stats->test_ext_count); 231 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n", 232 stats->set_range_count, stats->get_range_count); 233 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n", 234 stats->clear_count, stats->test_seq, test_seq_perc); 235 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n" 236 "%16llu bits tested backwards (%.2f%%)\n", 237 stats->mark_seq, mark_seq_perc, 238 stats->test_back, test_back_perc); 239 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n" 240 "%16.2f seconds in use\n", 241 stats->mark_back, mark_back_perc, inuse); 242 #endif /* ENABLE_BMAP_STATS_OPS */ 243 } 244 #endif 245 246 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap) 247 { 248 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 249 250 if (!bmap) 251 return; 252 253 if (EXT2FS_IS_32_BITMAP(bmap)) { 254 ext2fs_free_generic_bitmap(gen_bmap); 255 return; 256 } 257 258 if (!EXT2FS_IS_64_BITMAP(bmap)) 259 return; 260 261 #ifdef ENABLE_BMAP_STATS 262 if (getenv("E2FSPROGS_BITMAP_STATS")) { 263 ext2fs_print_bmap_statistics(bmap); 264 bmap->bitmap_ops->print_stats(bmap); 265 } 266 #endif 267 268 bmap->bitmap_ops->free_bmap(bmap); 269 270 if (bmap->description) { 271 ext2fs_free_mem(&bmap->description); 272 bmap->description = 0; 273 } 274 bmap->magic = 0; 275 ext2fs_free_mem(&bmap); 276 } 277 278 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src, 279 ext2fs_generic_bitmap *dest) 280 { 281 ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src; 282 char *descr, *new_descr; 283 ext2fs_generic_bitmap_64 new_bmap; 284 errcode_t retval; 285 286 if (!src) 287 return EINVAL; 288 289 if (EXT2FS_IS_32_BITMAP(src)) 290 return ext2fs_copy_generic_bitmap(gen_src, dest); 291 292 if (!EXT2FS_IS_64_BITMAP(src)) 293 return EINVAL; 294 295 /* Allocate a new bitmap struct */ 296 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64), 297 &new_bmap); 298 if (retval) 299 return retval; 300 301 302 #ifdef ENABLE_BMAP_STATS_OPS 303 src->stats.copy_count++; 304 #endif 305 #ifdef ENABLE_BMAP_STATS 306 if (gettimeofday(&new_bmap->stats.created, 307 (struct timezone *) NULL) == -1) { 308 perror("gettimeofday"); 309 ext2fs_free_mem(&new_bmap); 310 return 1; 311 } 312 new_bmap->stats.type = src->stats.type; 313 #endif 314 315 /* Copy all the high-level parts over */ 316 new_bmap->magic = src->magic; 317 new_bmap->fs = src->fs; 318 new_bmap->start = src->start; 319 new_bmap->end = src->end; 320 new_bmap->real_end = src->real_end; 321 new_bmap->bitmap_ops = src->bitmap_ops; 322 new_bmap->base_error_code = src->base_error_code; 323 new_bmap->cluster_bits = src->cluster_bits; 324 325 descr = src->description; 326 if (descr) { 327 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr); 328 if (retval) { 329 ext2fs_free_mem(&new_bmap); 330 return retval; 331 } 332 strcpy(new_descr, "copy of "); 333 strcat(new_descr, descr); 334 new_bmap->description = new_descr; 335 } 336 337 retval = src->bitmap_ops->copy_bmap(src, new_bmap); 338 if (retval) { 339 ext2fs_free_mem(&new_bmap->description); 340 ext2fs_free_mem(&new_bmap); 341 return retval; 342 } 343 344 *dest = (ext2fs_generic_bitmap) new_bmap; 345 346 return 0; 347 } 348 349 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap, 350 __u64 new_end, 351 __u64 new_real_end) 352 { 353 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 354 355 if (!bmap) 356 return EINVAL; 357 358 if (EXT2FS_IS_32_BITMAP(bmap)) 359 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end, 360 new_real_end, gen_bmap); 361 362 if (!EXT2FS_IS_64_BITMAP(bmap)) 363 return EINVAL; 364 365 INC_STAT(bmap, resize_count); 366 367 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); 368 } 369 370 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap, 371 errcode_t neq, 372 __u64 end, __u64 *oend) 373 { 374 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 375 376 if (!bitmap) 377 return EINVAL; 378 379 if (EXT2FS_IS_32_BITMAP(bitmap)) { 380 ext2_ino_t tmp_oend; 381 int retval; 382 383 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap, 384 bitmap->magic, 385 neq, end, &tmp_oend); 386 if (oend) 387 *oend = tmp_oend; 388 return retval; 389 } 390 391 if (!EXT2FS_IS_64_BITMAP(bitmap)) 392 return EINVAL; 393 394 if (end > bitmap->real_end) 395 return neq; 396 if (oend) 397 *oend = bitmap->end; 398 bitmap->end = end; 399 return 0; 400 } 401 402 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap) 403 { 404 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 405 406 if (!bitmap) 407 return EINVAL; 408 409 if (EXT2FS_IS_32_BITMAP(bitmap)) 410 return ext2fs_get_generic_bitmap_start(gen_bitmap); 411 412 if (!EXT2FS_IS_64_BITMAP(bitmap)) 413 return EINVAL; 414 415 return bitmap->start; 416 } 417 418 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap) 419 { 420 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 421 422 if (!bitmap) 423 return EINVAL; 424 425 if (EXT2FS_IS_32_BITMAP(bitmap)) 426 return ext2fs_get_generic_bitmap_end(gen_bitmap); 427 428 if (!EXT2FS_IS_64_BITMAP(bitmap)) 429 return EINVAL; 430 431 return bitmap->end; 432 } 433 434 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap) 435 { 436 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 437 438 if (EXT2FS_IS_32_BITMAP(bitmap)) 439 ext2fs_clear_generic_bitmap(gen_bitmap); 440 else 441 bitmap->bitmap_ops->clear_bmap(bitmap); 442 } 443 444 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap, 445 __u64 arg) 446 { 447 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 448 449 if (!bitmap) 450 return 0; 451 452 if (EXT2FS_IS_32_BITMAP(bitmap)) { 453 if (arg & ~0xffffffffULL) { 454 ext2fs_warn_bitmap2(gen_bitmap, 455 EXT2FS_MARK_ERROR, 0xffffffff); 456 return 0; 457 } 458 return ext2fs_mark_generic_bitmap(gen_bitmap, arg); 459 } 460 461 if (!EXT2FS_IS_64_BITMAP(bitmap)) 462 return 0; 463 464 arg >>= bitmap->cluster_bits; 465 466 #ifdef ENABLE_BMAP_STATS_OPS 467 if (arg == bitmap->stats.last_marked + 1) 468 bitmap->stats.mark_seq++; 469 if (arg < bitmap->stats.last_marked) 470 bitmap->stats.mark_back++; 471 bitmap->stats.last_marked = arg; 472 bitmap->stats.mark_count++; 473 #endif 474 475 if ((arg < bitmap->start) || (arg > bitmap->end)) { 476 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); 477 return 0; 478 } 479 480 return bitmap->bitmap_ops->mark_bmap(bitmap, arg); 481 } 482 483 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap, 484 __u64 arg) 485 { 486 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 487 488 if (!bitmap) 489 return 0; 490 491 if (EXT2FS_IS_32_BITMAP(bitmap)) { 492 if (arg & ~0xffffffffULL) { 493 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR, 494 0xffffffff); 495 return 0; 496 } 497 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg); 498 } 499 500 if (!EXT2FS_IS_64_BITMAP(bitmap)) 501 return 0; 502 503 arg >>= bitmap->cluster_bits; 504 505 INC_STAT(bitmap, unmark_count); 506 507 if ((arg < bitmap->start) || (arg > bitmap->end)) { 508 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); 509 return 0; 510 } 511 512 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); 513 } 514 515 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap, 516 __u64 arg) 517 { 518 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 519 if (!bitmap) 520 return 0; 521 522 if (EXT2FS_IS_32_BITMAP(bitmap)) { 523 if (arg & ~0xffffffffULL) { 524 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR, 525 0xffffffff); 526 return 0; 527 } 528 return ext2fs_test_generic_bitmap(gen_bitmap, arg); 529 } 530 531 if (!EXT2FS_IS_64_BITMAP(bitmap)) 532 return 0; 533 534 arg >>= bitmap->cluster_bits; 535 536 #ifdef ENABLE_BMAP_STATS_OPS 537 bitmap->stats.test_count++; 538 if (arg == bitmap->stats.last_tested + 1) 539 bitmap->stats.test_seq++; 540 if (arg < bitmap->stats.last_tested) 541 bitmap->stats.test_back++; 542 bitmap->stats.last_tested = arg; 543 #endif 544 545 if ((arg < bitmap->start) || (arg > bitmap->end)) { 546 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); 547 return 0; 548 } 549 550 return bitmap->bitmap_ops->test_bmap(bitmap, arg); 551 } 552 553 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap, 554 __u64 start, unsigned int num, 555 void *in) 556 { 557 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 558 559 if (!bmap) 560 return EINVAL; 561 562 if (EXT2FS_IS_32_BITMAP(bmap)) { 563 if ((start+num-1) & ~0xffffffffULL) { 564 ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR, 565 0xffffffff); 566 return EINVAL; 567 } 568 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic, 569 start, num, in); 570 } 571 572 if (!EXT2FS_IS_64_BITMAP(bmap)) 573 return EINVAL; 574 575 INC_STAT(bmap, set_range_count); 576 577 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); 578 } 579 580 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap, 581 __u64 start, unsigned int num, 582 void *out) 583 { 584 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 585 586 if (!bmap) 587 return EINVAL; 588 589 if (EXT2FS_IS_32_BITMAP(bmap)) { 590 if ((start+num-1) & ~0xffffffffULL) { 591 ext2fs_warn_bitmap2(gen_bmap, 592 EXT2FS_UNMARK_ERROR, 0xffffffff); 593 return EINVAL; 594 } 595 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic, 596 start, num, out); 597 } 598 599 if (!EXT2FS_IS_64_BITMAP(bmap)) 600 return EINVAL; 601 602 INC_STAT(bmap, get_range_count); 603 604 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); 605 } 606 607 errcode_t ext2fs_compare_generic_bmap(errcode_t neq, 608 ext2fs_generic_bitmap gen_bm1, 609 ext2fs_generic_bitmap gen_bm2) 610 { 611 ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1; 612 ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2; 613 blk64_t i; 614 615 if (!bm1 || !bm2) 616 return EINVAL; 617 if (bm1->magic != bm2->magic) 618 return EINVAL; 619 620 /* Now we know both bitmaps have the same magic */ 621 if (EXT2FS_IS_32_BITMAP(bm1)) 622 return ext2fs_compare_generic_bitmap(bm1->magic, neq, 623 gen_bm1, gen_bm2); 624 625 if (!EXT2FS_IS_64_BITMAP(bm1)) 626 return EINVAL; 627 628 if ((bm1->start != bm2->start) || 629 (bm1->end != bm2->end)) 630 return neq; 631 632 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 633 if (ext2fs_test_generic_bmap(gen_bm1, i) != 634 ext2fs_test_generic_bmap(gen_bm2, i)) 635 return neq; 636 637 return 0; 638 } 639 640 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap) 641 { 642 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 643 __u64 start, num; 644 645 if (EXT2FS_IS_32_BITMAP(bmap)) { 646 ext2fs_set_generic_bitmap_padding(gen_bmap); 647 return; 648 } 649 650 start = bmap->end + 1; 651 num = bmap->real_end - bmap->end; 652 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); 653 /* XXX ought to warn on error */ 654 } 655 656 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap, 657 blk64_t block, unsigned int num) 658 { 659 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 660 __u64 end = block + num; 661 662 if (!bmap) 663 return EINVAL; 664 665 if (num == 1) 666 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) 667 bmap, block); 668 669 if (EXT2FS_IS_32_BITMAP(bmap)) { 670 if ((block & ~0xffffffffULL) || 671 ((block+num-1) & ~0xffffffffULL)) { 672 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 673 EXT2FS_UNMARK_ERROR, 0xffffffff); 674 return EINVAL; 675 } 676 return ext2fs_test_block_bitmap_range( 677 (ext2fs_generic_bitmap) bmap, block, num); 678 } 679 680 if (!EXT2FS_IS_64_BITMAP(bmap)) 681 return EINVAL; 682 683 INC_STAT(bmap, test_ext_count); 684 685 /* convert to clusters if necessary */ 686 block >>= bmap->cluster_bits; 687 end += (1 << bmap->cluster_bits) - 1; 688 end >>= bmap->cluster_bits; 689 num = end - block; 690 691 if ((block < bmap->start) || (block > bmap->end) || 692 (block+num-1 > bmap->end)) { 693 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block, 694 bmap->description); 695 return EINVAL; 696 } 697 698 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); 699 } 700 701 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap, 702 blk64_t block, unsigned int num) 703 { 704 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 705 __u64 end = block + num; 706 707 if (!bmap) 708 return; 709 710 if (EXT2FS_IS_32_BITMAP(bmap)) { 711 if ((block & ~0xffffffffULL) || 712 ((block+num-1) & ~0xffffffffULL)) { 713 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 714 EXT2FS_UNMARK_ERROR, 0xffffffff); 715 return; 716 } 717 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 718 block, num); 719 } 720 721 if (!EXT2FS_IS_64_BITMAP(bmap)) 722 return; 723 724 INC_STAT(bmap, mark_ext_count); 725 726 /* convert to clusters if necessary */ 727 block >>= bmap->cluster_bits; 728 end += (1 << bmap->cluster_bits) - 1; 729 end >>= bmap->cluster_bits; 730 num = end - block; 731 732 if ((block < bmap->start) || (block > bmap->end) || 733 (block+num-1 > bmap->end)) { 734 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 735 bmap->description); 736 return; 737 } 738 739 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); 740 } 741 742 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap, 743 blk64_t block, unsigned int num) 744 { 745 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 746 __u64 end = block + num; 747 748 if (!bmap) 749 return; 750 751 if (EXT2FS_IS_32_BITMAP(bmap)) { 752 if ((block & ~0xffffffffULL) || 753 ((block+num-1) & ~0xffffffffULL)) { 754 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 755 EXT2FS_UNMARK_ERROR, 0xffffffff); 756 return; 757 } 758 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 759 block, num); 760 } 761 762 if (!EXT2FS_IS_64_BITMAP(bmap)) 763 return; 764 765 INC_STAT(bmap, unmark_ext_count); 766 767 /* convert to clusters if necessary */ 768 block >>= bmap->cluster_bits; 769 end += (1 << bmap->cluster_bits) - 1; 770 end >>= bmap->cluster_bits; 771 num = end - block; 772 773 if ((block < bmap->start) || (block > bmap->end) || 774 (block+num-1 > bmap->end)) { 775 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 776 bmap->description); 777 return; 778 } 779 780 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); 781 } 782 783 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func) 784 { 785 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap; 786 787 #ifndef OMIT_COM_ERR 788 if (bitmap && bitmap->description) 789 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 790 "called %s with 64-bit bitmap for %s", func, 791 bitmap->description); 792 else 793 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 794 "called %s with 64-bit bitmap", func); 795 #endif 796 } 797 798 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs, 799 ext2fs_block_bitmap *bitmap) 800 { 801 ext2fs_generic_bitmap_64 bmap, cmap; 802 ext2fs_block_bitmap gen_bmap = *bitmap, gen_cmap; 803 errcode_t retval; 804 blk64_t i, next, b_end, c_end; 805 806 bmap = (ext2fs_generic_bitmap_64) gen_bmap; 807 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap)) 808 return 0; /* Nothing to do */ 809 810 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap", 811 &gen_cmap); 812 if (retval) 813 return retval; 814 815 cmap = (ext2fs_generic_bitmap_64) gen_cmap; 816 i = bmap->start; 817 b_end = bmap->end; 818 bmap->end = bmap->real_end; 819 c_end = cmap->end; 820 cmap->end = cmap->real_end; 821 while (i < bmap->real_end) { 822 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap, 823 i, bmap->real_end, &next); 824 if (retval) 825 break; 826 ext2fs_mark_block_bitmap2(gen_cmap, next); 827 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1); 828 } 829 bmap->end = b_end; 830 cmap->end = c_end; 831 ext2fs_free_block_bitmap(gen_bmap); 832 *bitmap = (ext2fs_block_bitmap) cmap; 833 return 0; 834 } 835 836 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap, 837 __u64 start, __u64 end, __u64 *out) 838 { 839 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap; 840 __u64 cstart, cend, cout; 841 errcode_t retval; 842 843 if (!bitmap) 844 return EINVAL; 845 846 if (EXT2FS_IS_32_BITMAP(bitmap)) { 847 blk_t blk = 0; 848 849 if (((start) & ~0xffffffffULL) || 850 ((end) & ~0xffffffffULL)) { 851 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 852 return EINVAL; 853 } 854 855 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start, 856 end, &blk); 857 if (retval == 0) 858 *out = blk; 859 return retval; 860 } 861 862 if (!EXT2FS_IS_64_BITMAP(bitmap)) 863 return EINVAL; 864 865 cstart = start >> bmap64->cluster_bits; 866 cend = end >> bmap64->cluster_bits; 867 868 if (cstart < bmap64->start || cend > bmap64->end || start > end) { 869 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start); 870 return EINVAL; 871 } 872 873 if (bmap64->bitmap_ops->find_first_zero) { 874 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart, 875 cend, &cout); 876 if (retval) 877 return retval; 878 found: 879 cout <<= bmap64->cluster_bits; 880 *out = (cout >= start) ? cout : start; 881 return 0; 882 } 883 884 for (cout = cstart; cout <= cend; cout++) 885 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout)) 886 goto found; 887 888 return ENOENT; 889 } 890 891 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap, 892 __u64 start, __u64 end, __u64 *out) 893 { 894 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap; 895 __u64 cstart, cend, cout; 896 errcode_t retval; 897 898 if (!bitmap) 899 return EINVAL; 900 901 if (EXT2FS_IS_32_BITMAP(bitmap)) { 902 blk_t blk = 0; 903 904 if (((start) & ~0xffffffffULL) || 905 ((end) & ~0xffffffffULL)) { 906 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 907 return EINVAL; 908 } 909 910 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start, 911 end, &blk); 912 if (retval == 0) 913 *out = blk; 914 return retval; 915 } 916 917 if (!EXT2FS_IS_64_BITMAP(bitmap)) 918 return EINVAL; 919 920 cstart = start >> bmap64->cluster_bits; 921 cend = end >> bmap64->cluster_bits; 922 923 if (cstart < bmap64->start || cend > bmap64->end || start > end) { 924 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start); 925 return EINVAL; 926 } 927 928 if (bmap64->bitmap_ops->find_first_set) { 929 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart, 930 cend, &cout); 931 if (retval) 932 return retval; 933 found: 934 cout <<= bmap64->cluster_bits; 935 *out = (cout >= start) ? cout : start; 936 return 0; 937 } 938 939 for (cout = cstart; cout <= cend; cout++) 940 if (bmap64->bitmap_ops->test_bmap(bmap64, cout)) 941 goto found; 942 943 return ENOENT; 944 } 945 946 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start, 947 blk64_t end, blk64_t *out) 948 { 949 blk64_t next; 950 blk64_t tot_set = 0; 951 errcode_t retval; 952 953 while (start < end) { 954 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map, 955 start, end, &next); 956 if (retval) { 957 if (retval == ENOENT) 958 retval = 0; 959 break; 960 } 961 start = next; 962 963 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map, 964 start, end, &next); 965 if (retval == 0) { 966 tot_set += next - start; 967 start = next + 1; 968 } else if (retval == ENOENT) { 969 retval = 0; 970 tot_set += end - start + 1; 971 break; 972 } else 973 break; 974 } 975 976 if (!retval) 977 *out = EXT2FS_NUM_B2C(fs, tot_set); 978 return retval; 979 }