gen_bitmap64.c revision 6a26b38ac46a0489bd477832dcaebd276c2f489b
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 ext2fs_free_mem(&bitmap); 132 return 1; 133 } 134 bitmap->stats.type = type; 135#endif 136 137 /* XXX factor out, repeated in copy_bmap */ 138 bitmap->magic = magic; 139 bitmap->fs = fs; 140 bitmap->start = start; 141 bitmap->end = end; 142 bitmap->real_end = real_end; 143 bitmap->bitmap_ops = ops; 144 bitmap->cluster_bits = 0; 145 switch (magic) { 146 case EXT2_ET_MAGIC_INODE_BITMAP64: 147 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; 148 break; 149 case EXT2_ET_MAGIC_BLOCK_BITMAP64: 150 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; 151 bitmap->cluster_bits = fs->cluster_ratio_bits; 152 break; 153 default: 154 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; 155 } 156 if (descr) { 157 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); 158 if (retval) { 159 ext2fs_free_mem(&bitmap); 160 return retval; 161 } 162 strcpy(bitmap->description, descr); 163 } else 164 bitmap->description = 0; 165 166 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap); 167 if (retval) { 168 ext2fs_free_mem(&bitmap->description); 169 ext2fs_free_mem(&bitmap); 170 return retval; 171 } 172 173 *ret = bitmap; 174 return 0; 175} 176 177#ifdef BMAP_STATS 178static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap) 179{ 180 struct ext2_bmap_statistics *stats = &bitmap->stats; 181#ifdef BMAP_STATS_OPS 182 float mark_seq_perc = 0.0, test_seq_perc = 0.0; 183 float mark_back_perc = 0.0, test_back_perc = 0.0; 184#endif 185 double inuse; 186 struct timeval now; 187 188#ifdef BMAP_STATS_OPS 189 if (stats->test_count) { 190 test_seq_perc = ((float)stats->test_seq / 191 stats->test_count) * 100; 192 test_back_perc = ((float)stats->test_back / 193 stats->test_count) * 100; 194 } 195 196 if (stats->mark_count) { 197 mark_seq_perc = ((float)stats->mark_seq / 198 stats->mark_count) * 100; 199 mark_back_perc = ((float)stats->mark_back / 200 stats->mark_count) * 100; 201 } 202#endif 203 204 if (gettimeofday(&now, (struct timezone *) NULL) == -1) { 205 perror("gettimeofday"); 206 return; 207 } 208 209 inuse = (double) now.tv_sec + \ 210 (((double) now.tv_usec) * 0.000001); 211 inuse -= (double) stats->created.tv_sec + \ 212 (((double) stats->created.tv_usec) * 0.000001); 213 214 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description, 215 stats->type); 216 fprintf(stderr, "=================================================\n"); 217#ifdef BMAP_STATS_OPS 218 fprintf(stderr, "%16llu bits long\n", 219 bitmap->real_end - bitmap->start); 220 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n", 221 stats->copy_count, stats->resize_count); 222 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n", 223 stats->mark_count, stats->unmark_count); 224 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n", 225 stats->test_count, stats->mark_ext_count); 226 fprintf(stderr, "%16lu unmark_bmap_extent\n" 227 "%16lu test_clear_bmap_extent\n", 228 stats->unmark_ext_count, stats->test_ext_count); 229 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n", 230 stats->set_range_count, stats->get_range_count); 231 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n", 232 stats->clear_count, stats->test_seq, test_seq_perc); 233 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n" 234 "%16llu bits tested backwards (%.2f%%)\n", 235 stats->mark_seq, mark_seq_perc, 236 stats->test_back, test_back_perc); 237 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n" 238 "%16.2f seconds in use\n", 239 stats->mark_back, mark_back_perc, inuse); 240#endif /* BMAP_STATS_OPS */ 241} 242#endif 243 244void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap) 245{ 246 if (!bmap) 247 return; 248 249 if (EXT2FS_IS_32_BITMAP(bmap)) { 250 ext2fs_free_generic_bitmap(bmap); 251 return; 252 } 253 254 if (!EXT2FS_IS_64_BITMAP(bmap)) 255 return; 256 257#ifdef BMAP_STATS 258 if (getenv("E2FSPROGS_BITMAP_STATS")) { 259 ext2fs_print_bmap_statistics(bmap); 260 bmap->bitmap_ops->print_stats(bmap); 261 } 262#endif 263 264 bmap->bitmap_ops->free_bmap(bmap); 265 266 if (bmap->description) { 267 ext2fs_free_mem(&bmap->description); 268 bmap->description = 0; 269 } 270 bmap->magic = 0; 271 ext2fs_free_mem(&bmap); 272} 273 274errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src, 275 ext2fs_generic_bitmap *dest) 276{ 277 char *descr, *new_descr; 278 ext2fs_generic_bitmap new_bmap; 279 errcode_t retval; 280 281 if (!src) 282 return EINVAL; 283 284 if (EXT2FS_IS_32_BITMAP(src)) 285 return ext2fs_copy_generic_bitmap(src, dest); 286 287 if (!EXT2FS_IS_64_BITMAP(src)) 288 return EINVAL; 289 290 /* Allocate a new bitmap struct */ 291 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap), 292 &new_bmap); 293 if (retval) 294 return retval; 295 296 297#ifdef BMAP_STATS_OPS 298 src->stats.copy_count++; 299#endif 300#ifdef BMAP_STATS 301 if (gettimeofday(&new_bmap->stats.created, 302 (struct timezone *) NULL) == -1) { 303 perror("gettimeofday"); 304 ext2fs_free_mem(&new_bmap); 305 return 1; 306 } 307 new_bmap->stats.type = src->stats.type; 308#endif 309 310 /* Copy all the high-level parts over */ 311 new_bmap->magic = src->magic; 312 new_bmap->fs = src->fs; 313 new_bmap->start = src->start; 314 new_bmap->end = src->end; 315 new_bmap->real_end = src->real_end; 316 new_bmap->bitmap_ops = src->bitmap_ops; 317 new_bmap->base_error_code = src->base_error_code; 318 new_bmap->cluster_bits = src->cluster_bits; 319 320 descr = src->description; 321 if (descr) { 322 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr); 323 if (retval) { 324 ext2fs_free_mem(&new_bmap); 325 return retval; 326 } 327 sprintf(new_descr, "copy of %s", descr); 328 new_bmap->description = new_descr; 329 } 330 331 retval = src->bitmap_ops->copy_bmap(src, new_bmap); 332 if (retval) { 333 ext2fs_free_mem(&new_bmap->description); 334 ext2fs_free_mem(&new_bmap); 335 return retval; 336 } 337 338 *dest = new_bmap; 339 340 return 0; 341} 342 343errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, 344 __u64 new_end, 345 __u64 new_real_end) 346{ 347 if (!bmap) 348 return EINVAL; 349 350 if (EXT2FS_IS_32_BITMAP(bmap)) 351 return ext2fs_resize_generic_bitmap(bmap->magic, new_end, 352 new_real_end, bmap); 353 354 if (!EXT2FS_IS_64_BITMAP(bmap)) 355 return EINVAL; 356 357 INC_STAT(bmap, resize_count); 358 359 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); 360} 361 362errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, 363 errcode_t neq, 364 __u64 end, __u64 *oend) 365{ 366 if (!bitmap) 367 return EINVAL; 368 369 if (EXT2FS_IS_32_BITMAP(bitmap)) { 370 ext2_ino_t tmp_oend; 371 int retval; 372 373 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic, 374 neq, end, &tmp_oend); 375 if (oend) 376 *oend = tmp_oend; 377 return retval; 378 } 379 380 if (!EXT2FS_IS_64_BITMAP(bitmap)) 381 return EINVAL; 382 383 if (end > bitmap->real_end) 384 return neq; 385 if (oend) 386 *oend = bitmap->end; 387 bitmap->end = end; 388 return 0; 389} 390 391__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap) 392{ 393 if (!bitmap) 394 return EINVAL; 395 396 if (EXT2FS_IS_32_BITMAP(bitmap)) 397 return ext2fs_get_generic_bitmap_start(bitmap); 398 399 if (!EXT2FS_IS_64_BITMAP(bitmap)) 400 return EINVAL; 401 402 return bitmap->start; 403} 404 405__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap) 406{ 407 if (!bitmap) 408 return EINVAL; 409 410 if (EXT2FS_IS_32_BITMAP(bitmap)) 411 return ext2fs_get_generic_bitmap_end(bitmap); 412 413 if (!EXT2FS_IS_64_BITMAP(bitmap)) 414 return EINVAL; 415 416 return bitmap->end; 417} 418 419void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap) 420{ 421 if (EXT2FS_IS_32_BITMAP(bitmap)) 422 ext2fs_clear_generic_bitmap(bitmap); 423 else 424 bitmap->bitmap_ops->clear_bmap (bitmap); 425} 426 427int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, 428 __u64 arg) 429{ 430 if (!bitmap) 431 return 0; 432 433 if (EXT2FS_IS_32_BITMAP(bitmap)) { 434 if (arg & ~0xffffffffULL) { 435 ext2fs_warn_bitmap2(bitmap, 436 EXT2FS_MARK_ERROR, 0xffffffff); 437 return 0; 438 } 439 return ext2fs_mark_generic_bitmap(bitmap, arg); 440 } 441 442 if (!EXT2FS_IS_64_BITMAP(bitmap)) 443 return 0; 444 445 arg >>= bitmap->cluster_bits; 446 447#ifdef BMAP_STATS_OPS 448 if (arg == bitmap->stats.last_marked + 1) 449 bitmap->stats.mark_seq++; 450 if (arg < bitmap->stats.last_marked) 451 bitmap->stats.mark_back++; 452 bitmap->stats.last_marked = arg; 453 bitmap->stats.mark_count++; 454#endif 455 456 if ((arg < bitmap->start) || (arg > bitmap->end)) { 457 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); 458 return 0; 459 } 460 461 return bitmap->bitmap_ops->mark_bmap(bitmap, arg); 462} 463 464int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, 465 __u64 arg) 466{ 467 if (!bitmap) 468 return 0; 469 470 if (EXT2FS_IS_32_BITMAP(bitmap)) { 471 if (arg & ~0xffffffffULL) { 472 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, 473 0xffffffff); 474 return 0; 475 } 476 return ext2fs_unmark_generic_bitmap(bitmap, arg); 477 } 478 479 if (!EXT2FS_IS_64_BITMAP(bitmap)) 480 return 0; 481 482 arg >>= bitmap->cluster_bits; 483 484 INC_STAT(bitmap, unmark_count); 485 486 if ((arg < bitmap->start) || (arg > bitmap->end)) { 487 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); 488 return 0; 489 } 490 491 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); 492} 493 494int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, 495 __u64 arg) 496{ 497 if (!bitmap) 498 return 0; 499 500 if (EXT2FS_IS_32_BITMAP(bitmap)) { 501 if (arg & ~0xffffffffULL) { 502 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, 503 0xffffffff); 504 return 0; 505 } 506 return ext2fs_test_generic_bitmap(bitmap, arg); 507 } 508 509 if (!EXT2FS_IS_64_BITMAP(bitmap)) 510 return 0; 511 512 arg >>= bitmap->cluster_bits; 513 514#ifdef BMAP_STATS_OPS 515 bitmap->stats.test_count++; 516 if (arg == bitmap->stats.last_tested + 1) 517 bitmap->stats.test_seq++; 518 if (arg < bitmap->stats.last_tested) 519 bitmap->stats.test_back++; 520 bitmap->stats.last_tested = arg; 521#endif 522 523 if ((arg < bitmap->start) || (arg > bitmap->end)) { 524 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); 525 return 0; 526 } 527 528 return bitmap->bitmap_ops->test_bmap(bitmap, arg); 529} 530 531errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap, 532 __u64 start, unsigned int num, 533 void *in) 534{ 535 if (!bmap) 536 return EINVAL; 537 538 if (EXT2FS_IS_32_BITMAP(bmap)) { 539 if ((start+num-1) & ~0xffffffffULL) { 540 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR, 541 0xffffffff); 542 return EINVAL; 543 } 544 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic, 545 start, num, in); 546 } 547 548 if (!EXT2FS_IS_64_BITMAP(bmap)) 549 return EINVAL; 550 551 INC_STAT(bmap, set_range_count); 552 553 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); 554} 555 556errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap, 557 __u64 start, unsigned int num, 558 void *out) 559{ 560 if (!bmap) 561 return EINVAL; 562 563 if (EXT2FS_IS_32_BITMAP(bmap)) { 564 if ((start+num-1) & ~0xffffffffULL) { 565 ext2fs_warn_bitmap2(bmap, 566 EXT2FS_UNMARK_ERROR, 0xffffffff); 567 return EINVAL; 568 } 569 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic, 570 start, num, out); 571 } 572 573 if (!EXT2FS_IS_64_BITMAP(bmap)) 574 return EINVAL; 575 576 INC_STAT(bmap, get_range_count); 577 578 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); 579} 580 581errcode_t ext2fs_compare_generic_bmap(errcode_t neq, 582 ext2fs_generic_bitmap bm1, 583 ext2fs_generic_bitmap bm2) 584{ 585 blk64_t i; 586 587 if (!bm1 || !bm2) 588 return EINVAL; 589 if (bm1->magic != bm2->magic) 590 return EINVAL; 591 592 /* Now we know both bitmaps have the same magic */ 593 if (EXT2FS_IS_32_BITMAP(bm1)) 594 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2); 595 596 if (!EXT2FS_IS_64_BITMAP(bm1)) 597 return EINVAL; 598 599 if ((bm1->start != bm2->start) || 600 (bm1->end != bm2->end)) 601 return neq; 602 603 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 604 if (ext2fs_test_generic_bmap(bm1, i) != 605 ext2fs_test_generic_bmap(bm2, i)) 606 return neq; 607 608 return 0; 609} 610 611void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap) 612{ 613 __u64 start, num; 614 615 if (EXT2FS_IS_32_BITMAP(bmap)) { 616 ext2fs_set_generic_bitmap_padding(bmap); 617 return; 618 } 619 620 start = bmap->end + 1; 621 num = bmap->real_end - bmap->end; 622 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); 623 /* XXX ought to warn on error */ 624} 625 626int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap, 627 blk64_t block, unsigned int num) 628{ 629 __u64 end = block + num; 630 631 if (!bmap) 632 return EINVAL; 633 634 if (num == 1) 635 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) 636 bmap, block); 637 638 if (EXT2FS_IS_32_BITMAP(bmap)) { 639 if ((block+num-1) & ~0xffffffffULL) { 640 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 641 EXT2FS_UNMARK_ERROR, 0xffffffff); 642 return EINVAL; 643 } 644 return ext2fs_test_block_bitmap_range( 645 (ext2fs_generic_bitmap) bmap, block, num); 646 } 647 648 if (!EXT2FS_IS_64_BITMAP(bmap)) 649 return EINVAL; 650 651 INC_STAT(bmap, test_ext_count); 652 653 /* convert to clusters if necessary */ 654 block >>= bmap->cluster_bits; 655 end += (1 << bmap->cluster_bits) - 1; 656 end >>= bmap->cluster_bits; 657 num = end - block; 658 659 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 660 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block, 661 bmap->description); 662 return EINVAL; 663 } 664 665 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); 666} 667 668void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap, 669 blk64_t block, unsigned int num) 670{ 671 __u64 end = block + num; 672 673 if (!bmap) 674 return; 675 676 if (EXT2FS_IS_32_BITMAP(bmap)) { 677 if ((block+num-1) & ~0xffffffffULL) { 678 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 679 EXT2FS_UNMARK_ERROR, 0xffffffff); 680 return; 681 } 682 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 683 block, num); 684 } 685 686 if (!EXT2FS_IS_64_BITMAP(bmap)) 687 return; 688 689 INC_STAT(bmap, mark_ext_count); 690 691 /* convert to clusters if necessary */ 692 block >>= bmap->cluster_bits; 693 end += (1 << bmap->cluster_bits) - 1; 694 end >>= bmap->cluster_bits; 695 num = end - block; 696 697 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 698 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 699 bmap->description); 700 return; 701 } 702 703 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); 704} 705 706void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap, 707 blk64_t block, unsigned int num) 708{ 709 __u64 end = block + num; 710 711 if (!bmap) 712 return; 713 714 if (EXT2FS_IS_32_BITMAP(bmap)) { 715 if ((block+num-1) & ~0xffffffffULL) { 716 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 717 EXT2FS_UNMARK_ERROR, 0xffffffff); 718 return; 719 } 720 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 721 block, num); 722 } 723 724 if (!EXT2FS_IS_64_BITMAP(bmap)) 725 return; 726 727 INC_STAT(bmap, unmark_ext_count); 728 729 /* convert to clusters if necessary */ 730 block >>= bmap->cluster_bits; 731 end += (1 << bmap->cluster_bits) - 1; 732 end >>= bmap->cluster_bits; 733 num = end - block; 734 735 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 736 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 737 bmap->description); 738 return; 739 } 740 741 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); 742} 743 744void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func) 745{ 746#ifndef OMIT_COM_ERR 747 if (bitmap && bitmap->description) 748 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 749 "called %s with 64-bit bitmap for %s", func, 750 bitmap->description); 751 else 752 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 753 "called %s with 64-bit bitmap", func); 754#endif 755} 756 757errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs, 758 ext2fs_block_bitmap *bitmap) 759{ 760 ext2fs_block_bitmap cmap, bmap; 761 errcode_t retval; 762 blk64_t i, b_end, c_end; 763 int n, ratio; 764 765 bmap = *bitmap; 766 767 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap)) 768 return 0; /* Nothing to do */ 769 770 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap", 771 &cmap); 772 if (retval) 773 return retval; 774 775 i = bmap->start; 776 b_end = bmap->end; 777 bmap->end = bmap->real_end; 778 c_end = cmap->end; 779 cmap->end = cmap->real_end; 780 n = 0; 781 ratio = 1 << fs->cluster_ratio_bits; 782 while (i < bmap->real_end) { 783 if (ext2fs_test_block_bitmap2(bmap, i)) { 784 ext2fs_mark_block_bitmap2(cmap, i); 785 i += ratio - n; 786 n = 0; 787 continue; 788 } 789 i++; n++; 790 if (n >= ratio) 791 n = 0; 792 } 793 bmap->end = b_end; 794 cmap->end = c_end; 795 ext2fs_free_block_bitmap(bmap); 796 *bitmap = cmap; 797 return 0; 798} 799 800errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap, 801 __u64 start, __u64 end, __u64 *out) 802{ 803 int b; 804 805 if (!bitmap) 806 return EINVAL; 807 808 if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero) 809 return bitmap->bitmap_ops->find_first_zero(bitmap, start, 810 end, out); 811 812 if (EXT2FS_IS_32_BITMAP(bitmap)) { 813 blk_t blk = 0; 814 errcode_t retval; 815 816 if (((start) & ~0xffffffffULL) || 817 ((end) & ~0xffffffffULL)) { 818 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 819 return EINVAL; 820 } 821 822 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start, 823 end, &blk); 824 if (retval == 0) 825 *out = blk; 826 return retval; 827 } 828 829 if (!EXT2FS_IS_64_BITMAP(bitmap)) 830 return EINVAL; 831 832 start >>= bitmap->cluster_bits; 833 end >>= bitmap->cluster_bits; 834 835 if (start < bitmap->start || end > bitmap->end || start > end) { 836 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start); 837 return EINVAL; 838 } 839 840 while (start <= end) { 841 b = bitmap->bitmap_ops->test_bmap(bitmap, start); 842 if (!b) { 843 *out = start << bitmap->cluster_bits; 844 return 0; 845 } 846 start++; 847 } 848 849 return ENOENT; 850} 851