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