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