gen_bitmap64.c revision 3e1816b8cc9086354453bd75aaaeade558f98b3e
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 71static void warn_bitmap(ext2fs_generic_bitmap 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", arg, bitmap->description); 78 else 79 com_err(0, bitmap->base_error_code + code, "#%llu", arg); 80#endif 81} 82 83#ifdef BMAP_STATS_OPS 84#define INC_STAT(map, name) map->stats.name 85#else 86#define INC_STAT(map, name) ;; 87#endif 88 89 90errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic, 91 int type, __u64 start, __u64 end, 92 __u64 real_end, 93 const char *descr, 94 ext2fs_generic_bitmap *ret) 95{ 96 ext2fs_generic_bitmap bitmap; 97 struct ext2_bitmap_ops *ops; 98 ext2_ino_t num_dirs; 99 errcode_t retval; 100 101 if (!type) 102 type = EXT2FS_BMAP64_BITARRAY; 103 104 switch (type) { 105 case EXT2FS_BMAP64_BITARRAY: 106 ops = &ext2fs_blkmap64_bitarray; 107 break; 108 case EXT2FS_BMAP64_RBTREE: 109 ops = &ext2fs_blkmap64_rbtree; 110 break; 111 case EXT2FS_BMAP64_AUTODIR: 112 retval = ext2fs_get_num_dirs(fs, &num_dirs); 113 if (retval || num_dirs > (fs->super->s_inodes_count / 320)) 114 ops = &ext2fs_blkmap64_bitarray; 115 else 116 ops = &ext2fs_blkmap64_rbtree; 117 break; 118 default: 119 return EINVAL; 120 } 121 122 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap), 123 &bitmap); 124 if (retval) 125 return retval; 126 127#ifdef BMAP_STATS 128 if (gettimeofday(&bitmap->stats.created, 129 (struct timezone *) NULL) == -1) { 130 perror("gettimeofday"); 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 177void 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 return 1; 304 } 305 new_bmap->stats.type = src->stats.type; 306#endif 307 308 /* Copy all the high-level parts over */ 309 new_bmap->magic = src->magic; 310 new_bmap->fs = src->fs; 311 new_bmap->start = src->start; 312 new_bmap->end = src->end; 313 new_bmap->real_end = src->real_end; 314 new_bmap->bitmap_ops = src->bitmap_ops; 315 new_bmap->base_error_code = src->base_error_code; 316 new_bmap->cluster_bits = src->cluster_bits; 317 318 descr = src->description; 319 if (descr) { 320 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr); 321 if (retval) { 322 ext2fs_free_mem(&new_bmap); 323 return retval; 324 } 325 sprintf(new_descr, "copy of %s", descr); 326 new_bmap->description = new_descr; 327 } 328 329 retval = src->bitmap_ops->copy_bmap(src, new_bmap); 330 if (retval) { 331 ext2fs_free_mem(&new_bmap->description); 332 ext2fs_free_mem(&new_bmap); 333 return retval; 334 } 335 336 *dest = new_bmap; 337 338 return 0; 339} 340 341errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, 342 __u64 new_end, 343 __u64 new_real_end) 344{ 345 if (!bmap) 346 return EINVAL; 347 348 if (EXT2FS_IS_32_BITMAP(bmap)) 349 return ext2fs_resize_generic_bitmap(bmap->magic, new_end, 350 new_real_end, bmap); 351 352 if (!EXT2FS_IS_64_BITMAP(bmap)) 353 return EINVAL; 354 355 INC_STAT(bmap, resize_count); 356 357 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); 358} 359 360errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, 361 errcode_t neq, 362 __u64 end, __u64 *oend) 363{ 364 if (!bitmap) 365 return EINVAL; 366 367 if (EXT2FS_IS_32_BITMAP(bitmap)) { 368 ext2_ino_t tmp_oend; 369 int retval; 370 371 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic, 372 neq, end, &tmp_oend); 373 if (oend) 374 *oend = tmp_oend; 375 return retval; 376 } 377 378 if (!EXT2FS_IS_64_BITMAP(bitmap)) 379 return EINVAL; 380 381 if (end > bitmap->real_end) 382 return neq; 383 if (oend) 384 *oend = bitmap->end; 385 bitmap->end = end; 386 return 0; 387} 388 389__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap) 390{ 391 if (!bitmap) 392 return EINVAL; 393 394 if (EXT2FS_IS_32_BITMAP(bitmap)) 395 return ext2fs_get_generic_bitmap_start(bitmap); 396 397 if (!EXT2FS_IS_64_BITMAP(bitmap)) 398 return EINVAL; 399 400 return bitmap->start; 401} 402 403__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap) 404{ 405 if (!bitmap) 406 return EINVAL; 407 408 if (EXT2FS_IS_32_BITMAP(bitmap)) 409 return ext2fs_get_generic_bitmap_end(bitmap); 410 411 if (!EXT2FS_IS_64_BITMAP(bitmap)) 412 return EINVAL; 413 414 return bitmap->end; 415} 416 417void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap) 418{ 419 if (EXT2FS_IS_32_BITMAP(bitmap)) 420 ext2fs_clear_generic_bitmap(bitmap); 421 else 422 bitmap->bitmap_ops->clear_bmap (bitmap); 423} 424 425int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, 426 __u64 arg) 427{ 428 if (!bitmap) 429 return 0; 430 431 if (EXT2FS_IS_32_BITMAP(bitmap)) { 432 if (arg & ~0xffffffffULL) { 433 ext2fs_warn_bitmap2(bitmap, 434 EXT2FS_MARK_ERROR, 0xffffffff); 435 return 0; 436 } 437 return ext2fs_mark_generic_bitmap(bitmap, arg); 438 } 439 440 if (!EXT2FS_IS_64_BITMAP(bitmap)) 441 return 0; 442 443 arg >>= bitmap->cluster_bits; 444 445#ifdef BMAP_STATS_OPS 446 if (arg == bitmap->stats.last_marked + 1) 447 bitmap->stats.mark_seq++; 448 if (arg < bitmap->stats.last_marked) 449 bitmap->stats.mark_back++; 450 bitmap->stats.last_marked = arg; 451 bitmap->stats.mark_count++; 452#endif 453 454 if ((arg < bitmap->start) || (arg > bitmap->end)) { 455 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); 456 return 0; 457 } 458 459 return bitmap->bitmap_ops->mark_bmap(bitmap, arg); 460} 461 462int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, 463 __u64 arg) 464{ 465 if (!bitmap) 466 return 0; 467 468 if (EXT2FS_IS_32_BITMAP(bitmap)) { 469 if (arg & ~0xffffffffULL) { 470 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, 471 0xffffffff); 472 return 0; 473 } 474 return ext2fs_unmark_generic_bitmap(bitmap, arg); 475 } 476 477 if (!EXT2FS_IS_64_BITMAP(bitmap)) 478 return 0; 479 480 arg >>= bitmap->cluster_bits; 481 482 INC_STAT(bitmap, unmark_count); 483 484 if ((arg < bitmap->start) || (arg > bitmap->end)) { 485 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); 486 return 0; 487 } 488 489 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); 490} 491 492int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, 493 __u64 arg) 494{ 495 if (!bitmap) 496 return 0; 497 498 if (EXT2FS_IS_32_BITMAP(bitmap)) { 499 if (arg & ~0xffffffffULL) { 500 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, 501 0xffffffff); 502 return 0; 503 } 504 return ext2fs_test_generic_bitmap(bitmap, arg); 505 } 506 507 if (!EXT2FS_IS_64_BITMAP(bitmap)) 508 return 0; 509 510 arg >>= bitmap->cluster_bits; 511 512#ifdef BMAP_STATS_OPS 513 bitmap->stats.test_count++; 514 if (arg == bitmap->stats.last_tested + 1) 515 bitmap->stats.test_seq++; 516 if (arg < bitmap->stats.last_tested) 517 bitmap->stats.test_back++; 518 bitmap->stats.last_tested = arg; 519#endif 520 521 if ((arg < bitmap->start) || (arg > bitmap->end)) { 522 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); 523 return 0; 524 } 525 526 return bitmap->bitmap_ops->test_bmap(bitmap, arg); 527} 528 529errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap, 530 __u64 start, unsigned int num, 531 void *in) 532{ 533 if (!bmap) 534 return EINVAL; 535 536 if (EXT2FS_IS_32_BITMAP(bmap)) { 537 if ((start+num-1) & ~0xffffffffULL) { 538 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR, 539 0xffffffff); 540 return EINVAL; 541 } 542 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic, 543 start, num, in); 544 } 545 546 if (!EXT2FS_IS_64_BITMAP(bmap)) 547 return EINVAL; 548 549 INC_STAT(bmap, set_range_count); 550 551 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); 552} 553 554errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap, 555 __u64 start, unsigned int num, 556 void *out) 557{ 558 if (!bmap) 559 return EINVAL; 560 561 if (EXT2FS_IS_32_BITMAP(bmap)) { 562 if ((start+num-1) & ~0xffffffffULL) { 563 ext2fs_warn_bitmap2(bmap, 564 EXT2FS_UNMARK_ERROR, 0xffffffff); 565 return EINVAL; 566 } 567 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic, 568 start, num, out); 569 } 570 571 if (!EXT2FS_IS_64_BITMAP(bmap)) 572 return EINVAL; 573 574 INC_STAT(bmap, get_range_count); 575 576 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); 577} 578 579errcode_t ext2fs_compare_generic_bmap(errcode_t neq, 580 ext2fs_generic_bitmap bm1, 581 ext2fs_generic_bitmap bm2) 582{ 583 blk64_t i; 584 585 if (!bm1 || !bm2) 586 return EINVAL; 587 if (bm1->magic != bm2->magic) 588 return EINVAL; 589 590 /* Now we know both bitmaps have the same magic */ 591 if (EXT2FS_IS_32_BITMAP(bm1)) 592 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2); 593 594 if (!EXT2FS_IS_64_BITMAP(bm1)) 595 return EINVAL; 596 597 if ((bm1->start != bm2->start) || 598 (bm1->end != bm2->end)) 599 return neq; 600 601 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 602 if (ext2fs_test_generic_bmap(bm1, i) != 603 ext2fs_test_generic_bmap(bm2, i)) 604 return neq; 605 606 return 0; 607} 608 609void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap) 610{ 611 __u64 start, num; 612 613 if (EXT2FS_IS_32_BITMAP(bmap)) { 614 ext2fs_set_generic_bitmap_padding(bmap); 615 return; 616 } 617 618 start = bmap->end + 1; 619 num = bmap->real_end - bmap->end; 620 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); 621 /* XXX ought to warn on error */ 622} 623 624int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap, 625 blk64_t block, unsigned int num) 626{ 627 __u64 end = block + num; 628 629 if (!bmap) 630 return EINVAL; 631 632 if (num == 1) 633 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) 634 bmap, block); 635 636 if (EXT2FS_IS_32_BITMAP(bmap)) { 637 if ((block+num-1) & ~0xffffffffULL) { 638 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 639 EXT2FS_UNMARK_ERROR, 0xffffffff); 640 return EINVAL; 641 } 642 return ext2fs_test_block_bitmap_range( 643 (ext2fs_generic_bitmap) bmap, block, num); 644 } 645 646 if (!EXT2FS_IS_64_BITMAP(bmap)) 647 return EINVAL; 648 649 INC_STAT(bmap, test_ext_count); 650 651 /* convert to clusters if necessary */ 652 block >>= bmap->cluster_bits; 653 end += (1 << bmap->cluster_bits) - 1; 654 end >>= bmap->cluster_bits; 655 num = end - block; 656 657 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 658 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block, 659 bmap->description); 660 return; 661 } 662 663 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); 664} 665 666void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap, 667 blk64_t block, unsigned int num) 668{ 669 __u64 end = block + num; 670 671 if (!bmap) 672 return; 673 674 if (EXT2FS_IS_32_BITMAP(bmap)) { 675 if ((block+num-1) & ~0xffffffffULL) { 676 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 677 EXT2FS_UNMARK_ERROR, 0xffffffff); 678 return; 679 } 680 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 681 block, num); 682 } 683 684 if (!EXT2FS_IS_64_BITMAP(bmap)) 685 return; 686 687 INC_STAT(bmap, mark_ext_count); 688 689 /* convert to clusters if necessary */ 690 block >>= bmap->cluster_bits; 691 end += (1 << bmap->cluster_bits) - 1; 692 end >>= bmap->cluster_bits; 693 num = end - block; 694 695 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 696 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 697 bmap->description); 698 return; 699 } 700 701 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); 702} 703 704void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap, 705 blk64_t block, unsigned int num) 706{ 707 __u64 end = block + num; 708 709 if (!bmap) 710 return; 711 712 if (EXT2FS_IS_32_BITMAP(bmap)) { 713 if ((block+num-1) & ~0xffffffffULL) { 714 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 715 EXT2FS_UNMARK_ERROR, 0xffffffff); 716 return; 717 } 718 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 719 block, num); 720 } 721 722 if (!EXT2FS_IS_64_BITMAP(bmap)) 723 return; 724 725 INC_STAT(bmap, unmark_ext_count); 726 727 /* convert to clusters if necessary */ 728 block >>= bmap->cluster_bits; 729 end += (1 << bmap->cluster_bits) - 1; 730 end >>= bmap->cluster_bits; 731 num = end - block; 732 733 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 734 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 735 bmap->description); 736 return; 737 } 738 739 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); 740} 741 742void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func) 743{ 744#ifndef OMIT_COM_ERR 745 if (bitmap && bitmap->description) 746 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 747 "called %s with 64-bit bitmap for %s", func, 748 bitmap->description); 749 else 750 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 751 "called %s with 64-bit bitmap", func); 752#endif 753} 754 755errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs, 756 ext2fs_block_bitmap *bitmap) 757{ 758 ext2fs_block_bitmap cmap, bmap; 759 errcode_t retval; 760 blk64_t i, b_end, c_end; 761 int n, ratio; 762 763 bmap = *bitmap; 764 765 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap)) 766 return 0; /* Nothing to do */ 767 768 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap", 769 &cmap); 770 if (retval) 771 return retval; 772 773 i = bmap->start; 774 b_end = bmap->end; 775 bmap->end = bmap->real_end; 776 c_end = cmap->end; 777 cmap->end = cmap->real_end; 778 n = 0; 779 ratio = 1 << fs->cluster_ratio_bits; 780 while (i < bmap->real_end) { 781 if (ext2fs_test_block_bitmap2(bmap, i)) { 782 ext2fs_mark_block_bitmap2(cmap, i); 783 i += ratio - n; 784 n = 0; 785 continue; 786 } 787 i++; n++; 788 if (n >= ratio) 789 n = 0; 790 } 791 bmap->end = b_end; 792 cmap->end = c_end; 793 ext2fs_free_block_bitmap(bmap); 794 *bitmap = cmap; 795 return 0; 796} 797 798errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap, 799 __u64 start, __u64 end, __u64 *out) 800{ 801 int b; 802 803 if (!bitmap) 804 return EINVAL; 805 806 if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero) 807 return bitmap->bitmap_ops->find_first_zero(bitmap, start, 808 end, out); 809 810 if (EXT2FS_IS_32_BITMAP(bitmap)) { 811 blk_t blk = 0; 812 errcode_t retval; 813 814 if (((start) & ~0xffffffffULL) || 815 ((end) & ~0xffffffffULL)) { 816 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 817 return EINVAL; 818 } 819 820 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start, 821 end, &blk); 822 if (retval == 0) 823 *out = blk; 824 return retval; 825 } 826 827 if (!EXT2FS_IS_64_BITMAP(bitmap)) 828 return EINVAL; 829 830 start >>= bitmap->cluster_bits; 831 end >>= bitmap->cluster_bits; 832 833 if (start < bitmap->start || end > bitmap->end || start > end) { 834 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start); 835 return EINVAL; 836 } 837 838 while (start <= end) { 839 b = bitmap->bitmap_ops->test_bmap(bitmap, start); 840 if (!b) { 841 *out = start << bitmap->cluster_bits; 842 return 0; 843 } 844 start++; 845 } 846 847 return ENOENT; 848} 849