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 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 ENABLE_BMAP_STATS_OPS 84 #define INC_STAT(map, name) map->stats.name 85 #else 86 #define INC_STAT(map, name) ;; 87 #endif 88 89 90 errcode_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 ENABLE_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 ENABLE_BMAP_STATS 178 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap) 179 { 180 struct ext2_bmap_statistics *stats = &bitmap->stats; 181 #ifdef ENABLE_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 ENABLE_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 ENABLE_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 /* ENABLE_BMAP_STATS_OPS */ 241 } 242 #endif 243 244 void 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 ENABLE_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 274 errcode_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 ENABLE_BMAP_STATS_OPS 298 src->stats.copy_count++; 299 #endif 300 #ifdef ENABLE_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 strcpy(new_descr, "copy of "); 328 strcat(new_descr, descr); 329 new_bmap->description = new_descr; 330 } 331 332 retval = src->bitmap_ops->copy_bmap(src, new_bmap); 333 if (retval) { 334 ext2fs_free_mem(&new_bmap->description); 335 ext2fs_free_mem(&new_bmap); 336 return retval; 337 } 338 339 *dest = new_bmap; 340 341 return 0; 342 } 343 344 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, 345 __u64 new_end, 346 __u64 new_real_end) 347 { 348 if (!bmap) 349 return EINVAL; 350 351 if (EXT2FS_IS_32_BITMAP(bmap)) 352 return ext2fs_resize_generic_bitmap(bmap->magic, new_end, 353 new_real_end, bmap); 354 355 if (!EXT2FS_IS_64_BITMAP(bmap)) 356 return EINVAL; 357 358 INC_STAT(bmap, resize_count); 359 360 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); 361 } 362 363 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, 364 errcode_t neq, 365 __u64 end, __u64 *oend) 366 { 367 if (!bitmap) 368 return EINVAL; 369 370 if (EXT2FS_IS_32_BITMAP(bitmap)) { 371 ext2_ino_t tmp_oend; 372 int retval; 373 374 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic, 375 neq, end, &tmp_oend); 376 if (oend) 377 *oend = tmp_oend; 378 return retval; 379 } 380 381 if (!EXT2FS_IS_64_BITMAP(bitmap)) 382 return EINVAL; 383 384 if (end > bitmap->real_end) 385 return neq; 386 if (oend) 387 *oend = bitmap->end; 388 bitmap->end = end; 389 return 0; 390 } 391 392 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap) 393 { 394 if (!bitmap) 395 return EINVAL; 396 397 if (EXT2FS_IS_32_BITMAP(bitmap)) 398 return ext2fs_get_generic_bitmap_start(bitmap); 399 400 if (!EXT2FS_IS_64_BITMAP(bitmap)) 401 return EINVAL; 402 403 return bitmap->start; 404 } 405 406 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap) 407 { 408 if (!bitmap) 409 return EINVAL; 410 411 if (EXT2FS_IS_32_BITMAP(bitmap)) 412 return ext2fs_get_generic_bitmap_end(bitmap); 413 414 if (!EXT2FS_IS_64_BITMAP(bitmap)) 415 return EINVAL; 416 417 return bitmap->end; 418 } 419 420 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap) 421 { 422 if (EXT2FS_IS_32_BITMAP(bitmap)) 423 ext2fs_clear_generic_bitmap(bitmap); 424 else 425 bitmap->bitmap_ops->clear_bmap (bitmap); 426 } 427 428 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, 429 __u64 arg) 430 { 431 if (!bitmap) 432 return 0; 433 434 if (EXT2FS_IS_32_BITMAP(bitmap)) { 435 if (arg & ~0xffffffffULL) { 436 ext2fs_warn_bitmap2(bitmap, 437 EXT2FS_MARK_ERROR, 0xffffffff); 438 return 0; 439 } 440 return ext2fs_mark_generic_bitmap(bitmap, arg); 441 } 442 443 if (!EXT2FS_IS_64_BITMAP(bitmap)) 444 return 0; 445 446 arg >>= bitmap->cluster_bits; 447 448 #ifdef ENABLE_BMAP_STATS_OPS 449 if (arg == bitmap->stats.last_marked + 1) 450 bitmap->stats.mark_seq++; 451 if (arg < bitmap->stats.last_marked) 452 bitmap->stats.mark_back++; 453 bitmap->stats.last_marked = arg; 454 bitmap->stats.mark_count++; 455 #endif 456 457 if ((arg < bitmap->start) || (arg > bitmap->end)) { 458 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); 459 return 0; 460 } 461 462 return bitmap->bitmap_ops->mark_bmap(bitmap, arg); 463 } 464 465 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, 466 __u64 arg) 467 { 468 if (!bitmap) 469 return 0; 470 471 if (EXT2FS_IS_32_BITMAP(bitmap)) { 472 if (arg & ~0xffffffffULL) { 473 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, 474 0xffffffff); 475 return 0; 476 } 477 return ext2fs_unmark_generic_bitmap(bitmap, arg); 478 } 479 480 if (!EXT2FS_IS_64_BITMAP(bitmap)) 481 return 0; 482 483 arg >>= bitmap->cluster_bits; 484 485 INC_STAT(bitmap, unmark_count); 486 487 if ((arg < bitmap->start) || (arg > bitmap->end)) { 488 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); 489 return 0; 490 } 491 492 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); 493 } 494 495 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, 496 __u64 arg) 497 { 498 if (!bitmap) 499 return 0; 500 501 if (EXT2FS_IS_32_BITMAP(bitmap)) { 502 if (arg & ~0xffffffffULL) { 503 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, 504 0xffffffff); 505 return 0; 506 } 507 return ext2fs_test_generic_bitmap(bitmap, arg); 508 } 509 510 if (!EXT2FS_IS_64_BITMAP(bitmap)) 511 return 0; 512 513 arg >>= bitmap->cluster_bits; 514 515 #ifdef ENABLE_BMAP_STATS_OPS 516 bitmap->stats.test_count++; 517 if (arg == bitmap->stats.last_tested + 1) 518 bitmap->stats.test_seq++; 519 if (arg < bitmap->stats.last_tested) 520 bitmap->stats.test_back++; 521 bitmap->stats.last_tested = arg; 522 #endif 523 524 if ((arg < bitmap->start) || (arg > bitmap->end)) { 525 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); 526 return 0; 527 } 528 529 return bitmap->bitmap_ops->test_bmap(bitmap, arg); 530 } 531 532 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap, 533 __u64 start, unsigned int num, 534 void *in) 535 { 536 if (!bmap) 537 return EINVAL; 538 539 if (EXT2FS_IS_32_BITMAP(bmap)) { 540 if ((start+num-1) & ~0xffffffffULL) { 541 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR, 542 0xffffffff); 543 return EINVAL; 544 } 545 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic, 546 start, num, in); 547 } 548 549 if (!EXT2FS_IS_64_BITMAP(bmap)) 550 return EINVAL; 551 552 INC_STAT(bmap, set_range_count); 553 554 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); 555 } 556 557 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap, 558 __u64 start, unsigned int num, 559 void *out) 560 { 561 if (!bmap) 562 return EINVAL; 563 564 if (EXT2FS_IS_32_BITMAP(bmap)) { 565 if ((start+num-1) & ~0xffffffffULL) { 566 ext2fs_warn_bitmap2(bmap, 567 EXT2FS_UNMARK_ERROR, 0xffffffff); 568 return EINVAL; 569 } 570 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic, 571 start, num, out); 572 } 573 574 if (!EXT2FS_IS_64_BITMAP(bmap)) 575 return EINVAL; 576 577 INC_STAT(bmap, get_range_count); 578 579 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); 580 } 581 582 errcode_t ext2fs_compare_generic_bmap(errcode_t neq, 583 ext2fs_generic_bitmap bm1, 584 ext2fs_generic_bitmap bm2) 585 { 586 blk64_t i; 587 588 if (!bm1 || !bm2) 589 return EINVAL; 590 if (bm1->magic != bm2->magic) 591 return EINVAL; 592 593 /* Now we know both bitmaps have the same magic */ 594 if (EXT2FS_IS_32_BITMAP(bm1)) 595 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2); 596 597 if (!EXT2FS_IS_64_BITMAP(bm1)) 598 return EINVAL; 599 600 if ((bm1->start != bm2->start) || 601 (bm1->end != bm2->end)) 602 return neq; 603 604 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 605 if (ext2fs_test_generic_bmap(bm1, i) != 606 ext2fs_test_generic_bmap(bm2, i)) 607 return neq; 608 609 return 0; 610 } 611 612 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap) 613 { 614 __u64 start, num; 615 616 if (EXT2FS_IS_32_BITMAP(bmap)) { 617 ext2fs_set_generic_bitmap_padding(bmap); 618 return; 619 } 620 621 start = bmap->end + 1; 622 num = bmap->real_end - bmap->end; 623 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); 624 /* XXX ought to warn on error */ 625 } 626 627 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap, 628 blk64_t block, unsigned int num) 629 { 630 __u64 end = block + num; 631 632 if (!bmap) 633 return EINVAL; 634 635 if (num == 1) 636 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) 637 bmap, block); 638 639 if (EXT2FS_IS_32_BITMAP(bmap)) { 640 if ((block+num-1) & ~0xffffffffULL) { 641 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 642 EXT2FS_UNMARK_ERROR, 0xffffffff); 643 return EINVAL; 644 } 645 return ext2fs_test_block_bitmap_range( 646 (ext2fs_generic_bitmap) bmap, block, num); 647 } 648 649 if (!EXT2FS_IS_64_BITMAP(bmap)) 650 return EINVAL; 651 652 INC_STAT(bmap, test_ext_count); 653 654 /* convert to clusters if necessary */ 655 block >>= bmap->cluster_bits; 656 end += (1 << bmap->cluster_bits) - 1; 657 end >>= bmap->cluster_bits; 658 num = end - block; 659 660 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 661 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block, 662 bmap->description); 663 return EINVAL; 664 } 665 666 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); 667 } 668 669 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap, 670 blk64_t block, unsigned int num) 671 { 672 __u64 end = block + num; 673 674 if (!bmap) 675 return; 676 677 if (EXT2FS_IS_32_BITMAP(bmap)) { 678 if ((block+num-1) & ~0xffffffffULL) { 679 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 680 EXT2FS_UNMARK_ERROR, 0xffffffff); 681 return; 682 } 683 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 684 block, num); 685 } 686 687 if (!EXT2FS_IS_64_BITMAP(bmap)) 688 return; 689 690 INC_STAT(bmap, mark_ext_count); 691 692 /* convert to clusters if necessary */ 693 block >>= bmap->cluster_bits; 694 end += (1 << bmap->cluster_bits) - 1; 695 end >>= bmap->cluster_bits; 696 num = end - block; 697 698 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 699 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 700 bmap->description); 701 return; 702 } 703 704 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); 705 } 706 707 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap, 708 blk64_t block, unsigned int num) 709 { 710 __u64 end = block + num; 711 712 if (!bmap) 713 return; 714 715 if (EXT2FS_IS_32_BITMAP(bmap)) { 716 if ((block+num-1) & ~0xffffffffULL) { 717 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 718 EXT2FS_UNMARK_ERROR, 0xffffffff); 719 return; 720 } 721 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 722 block, num); 723 } 724 725 if (!EXT2FS_IS_64_BITMAP(bmap)) 726 return; 727 728 INC_STAT(bmap, unmark_ext_count); 729 730 /* convert to clusters if necessary */ 731 block >>= bmap->cluster_bits; 732 end += (1 << bmap->cluster_bits) - 1; 733 end >>= bmap->cluster_bits; 734 num = end - block; 735 736 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 737 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 738 bmap->description); 739 return; 740 } 741 742 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); 743 } 744 745 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func) 746 { 747 #ifndef OMIT_COM_ERR 748 if (bitmap && bitmap->description) 749 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 750 "called %s with 64-bit bitmap for %s", func, 751 bitmap->description); 752 else 753 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 754 "called %s with 64-bit bitmap", func); 755 #endif 756 } 757 758 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs, 759 ext2fs_block_bitmap *bitmap) 760 { 761 ext2fs_block_bitmap cmap, bmap; 762 errcode_t retval; 763 blk64_t i, b_end, c_end; 764 int n, ratio; 765 766 bmap = *bitmap; 767 768 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap)) 769 return 0; /* Nothing to do */ 770 771 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap", 772 &cmap); 773 if (retval) 774 return retval; 775 776 i = bmap->start; 777 b_end = bmap->end; 778 bmap->end = bmap->real_end; 779 c_end = cmap->end; 780 cmap->end = cmap->real_end; 781 n = 0; 782 ratio = 1 << fs->cluster_ratio_bits; 783 while (i < bmap->real_end) { 784 if (ext2fs_test_block_bitmap2(bmap, i)) { 785 ext2fs_mark_block_bitmap2(cmap, i); 786 i += ratio - n; 787 n = 0; 788 continue; 789 } 790 i++; n++; 791 if (n >= ratio) 792 n = 0; 793 } 794 bmap->end = b_end; 795 cmap->end = c_end; 796 ext2fs_free_block_bitmap(bmap); 797 *bitmap = cmap; 798 return 0; 799 } 800 801 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap, 802 __u64 start, __u64 end, __u64 *out) 803 { 804 __u64 cstart, cend, cout; 805 errcode_t retval; 806 807 if (!bitmap) 808 return EINVAL; 809 810 if (EXT2FS_IS_32_BITMAP(bitmap)) { 811 blk_t blk = 0; 812 813 if (((start) & ~0xffffffffULL) || 814 ((end) & ~0xffffffffULL)) { 815 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 816 return EINVAL; 817 } 818 819 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start, 820 end, &blk); 821 if (retval == 0) 822 *out = blk; 823 return retval; 824 } 825 826 if (!EXT2FS_IS_64_BITMAP(bitmap)) 827 return EINVAL; 828 829 cstart = start >> bitmap->cluster_bits; 830 cend = end >> bitmap->cluster_bits; 831 832 if (cstart < bitmap->start || cend > bitmap->end || start > end) { 833 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start); 834 return EINVAL; 835 } 836 837 if (bitmap->bitmap_ops->find_first_zero) { 838 retval = bitmap->bitmap_ops->find_first_zero(bitmap, cstart, 839 cend, &cout); 840 if (retval) 841 return retval; 842 found: 843 cout <<= bitmap->cluster_bits; 844 *out = (cout >= start) ? cout : start; 845 return 0; 846 } 847 848 for (cout = cstart; cout <= cend; cout++) 849 if (!bitmap->bitmap_ops->test_bmap(bitmap, cout)) 850 goto found; 851 852 return ENOENT; 853 } 854 855 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap, 856 __u64 start, __u64 end, __u64 *out) 857 { 858 __u64 cstart, cend, cout; 859 errcode_t retval; 860 861 if (!bitmap) 862 return EINVAL; 863 864 if (EXT2FS_IS_32_BITMAP(bitmap)) { 865 blk_t blk = 0; 866 867 if (((start) & ~0xffffffffULL) || 868 ((end) & ~0xffffffffULL)) { 869 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 870 return EINVAL; 871 } 872 873 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start, 874 end, &blk); 875 if (retval == 0) 876 *out = blk; 877 return retval; 878 } 879 880 if (!EXT2FS_IS_64_BITMAP(bitmap)) 881 return EINVAL; 882 883 cstart = start >> bitmap->cluster_bits; 884 cend = end >> bitmap->cluster_bits; 885 886 if (cstart < bitmap->start || cend > bitmap->end || start > end) { 887 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start); 888 return EINVAL; 889 } 890 891 if (bitmap->bitmap_ops->find_first_set) { 892 retval = bitmap->bitmap_ops->find_first_set(bitmap, cstart, 893 cend, &cout); 894 if (retval) 895 return retval; 896 found: 897 cout <<= bitmap->cluster_bits; 898 *out = (cout >= start) ? cout : start; 899 return 0; 900 } 901 902 for (cout = cstart; cout <= cend; cout++) 903 if (bitmap->bitmap_ops->test_bmap(bitmap, cout)) 904 goto found; 905 906 return ENOENT; 907 } 908
