2 * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and
5 * Copyright (C) 2007, 2008 Theodore Ts'o.
8 * This file may be redistributed under the terms of the GNU Public
26 #include <sys/types.h>
28 #ifdef HAVE_SYS_TIME_H
37 * Design of 64-bit bitmaps
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.
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.
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
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.
71 static void warn_bitmap(ext2fs_generic_bitmap_64 bitmap,
75 if (bitmap->description)
76 com_err(0, bitmap->base_error_code+code,
77 "#%llu for %s", (unsigned long long) arg,
80 com_err(0, bitmap->base_error_code + code, "#%llu",
81 (unsigned long long) arg);
85 #ifdef ENABLE_BMAP_STATS_OPS
86 #define INC_STAT(map, name) map->stats.name
88 #define INC_STAT(map, name) ;;
92 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
93 int type, __u64 start, __u64 end,
96 ext2fs_generic_bitmap *ret)
98 ext2fs_generic_bitmap_64 bitmap;
99 struct ext2_bitmap_ops *ops;
104 type = EXT2FS_BMAP64_BITARRAY;
107 case EXT2FS_BMAP64_BITARRAY:
108 ops = &ext2fs_blkmap64_bitarray;
110 case EXT2FS_BMAP64_RBTREE:
111 ops = &ext2fs_blkmap64_rbtree;
113 case EXT2FS_BMAP64_AUTODIR:
114 retval = ext2fs_get_num_dirs(fs, &num_dirs);
115 if (retval || num_dirs > (fs->super->s_inodes_count / 320))
116 ops = &ext2fs_blkmap64_bitarray;
118 ops = &ext2fs_blkmap64_rbtree;
124 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
129 #ifdef ENABLE_BMAP_STATS
130 if (gettimeofday(&bitmap->stats.created,
131 (struct timezone *) NULL) == -1) {
132 perror("gettimeofday");
133 ext2fs_free_mem(&bitmap);
136 bitmap->stats.type = type;
139 /* XXX factor out, repeated in copy_bmap */
140 bitmap->magic = magic;
142 bitmap->start = start;
144 bitmap->real_end = real_end;
145 bitmap->bitmap_ops = ops;
146 bitmap->cluster_bits = 0;
148 case EXT2_ET_MAGIC_INODE_BITMAP64:
149 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
151 case EXT2_ET_MAGIC_BLOCK_BITMAP64:
152 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
153 bitmap->cluster_bits = fs->cluster_ratio_bits;
156 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
159 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
161 ext2fs_free_mem(&bitmap);
164 strcpy(bitmap->description, descr);
166 bitmap->description = 0;
168 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
170 ext2fs_free_mem(&bitmap->description);
171 ext2fs_free_mem(&bitmap);
175 *ret = (ext2fs_generic_bitmap) bitmap;
179 #ifdef ENABLE_BMAP_STATS
180 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap)
182 struct ext2_bmap_statistics *stats = &bitmap->stats;
183 #ifdef ENABLE_BMAP_STATS_OPS
184 float mark_seq_perc = 0.0, test_seq_perc = 0.0;
185 float mark_back_perc = 0.0, test_back_perc = 0.0;
190 #ifdef ENABLE_BMAP_STATS_OPS
191 if (stats->test_count) {
192 test_seq_perc = ((float)stats->test_seq /
193 stats->test_count) * 100;
194 test_back_perc = ((float)stats->test_back /
195 stats->test_count) * 100;
198 if (stats->mark_count) {
199 mark_seq_perc = ((float)stats->mark_seq /
200 stats->mark_count) * 100;
201 mark_back_perc = ((float)stats->mark_back /
202 stats->mark_count) * 100;
206 if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
207 perror("gettimeofday");
211 inuse = (double) now.tv_sec + \
212 (((double) now.tv_usec) * 0.000001);
213 inuse -= (double) stats->created.tv_sec + \
214 (((double) stats->created.tv_usec) * 0.000001);
216 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
218 fprintf(stderr, "=================================================\n");
219 #ifdef ENABLE_BMAP_STATS_OPS
220 fprintf(stderr, "%16llu bits long\n",
221 bitmap->real_end - bitmap->start);
222 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
223 stats->copy_count, stats->resize_count);
224 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
225 stats->mark_count, stats->unmark_count);
226 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
227 stats->test_count, stats->mark_ext_count);
228 fprintf(stderr, "%16lu unmark_bmap_extent\n"
229 "%16lu test_clear_bmap_extent\n",
230 stats->unmark_ext_count, stats->test_ext_count);
231 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
232 stats->set_range_count, stats->get_range_count);
233 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
234 stats->clear_count, stats->test_seq, test_seq_perc);
235 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
236 "%16llu bits tested backwards (%.2f%%)\n",
237 stats->mark_seq, mark_seq_perc,
238 stats->test_back, test_back_perc);
239 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
240 "%16.2f seconds in use\n",
241 stats->mark_back, mark_back_perc, inuse);
242 #endif /* ENABLE_BMAP_STATS_OPS */
246 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)
248 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
253 if (EXT2FS_IS_32_BITMAP(bmap)) {
254 ext2fs_free_generic_bitmap(gen_bmap);
258 if (!EXT2FS_IS_64_BITMAP(bmap))
261 #ifdef ENABLE_BMAP_STATS
262 if (getenv("E2FSPROGS_BITMAP_STATS")) {
263 ext2fs_print_bmap_statistics(bmap);
264 bmap->bitmap_ops->print_stats(bmap);
268 bmap->bitmap_ops->free_bmap(bmap);
270 if (bmap->description) {
271 ext2fs_free_mem(&bmap->description);
272 bmap->description = 0;
275 ext2fs_free_mem(&bmap);
278 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,
279 ext2fs_generic_bitmap *dest)
281 ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src;
282 char *descr, *new_descr;
283 ext2fs_generic_bitmap_64 new_bmap;
289 if (EXT2FS_IS_32_BITMAP(src))
290 return ext2fs_copy_generic_bitmap(gen_src, dest);
292 if (!EXT2FS_IS_64_BITMAP(src))
295 /* Allocate a new bitmap struct */
296 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
302 #ifdef ENABLE_BMAP_STATS_OPS
303 src->stats.copy_count++;
305 #ifdef ENABLE_BMAP_STATS
306 if (gettimeofday(&new_bmap->stats.created,
307 (struct timezone *) NULL) == -1) {
308 perror("gettimeofday");
309 ext2fs_free_mem(&new_bmap);
312 new_bmap->stats.type = src->stats.type;
315 /* Copy all the high-level parts over */
316 new_bmap->magic = src->magic;
317 new_bmap->fs = src->fs;
318 new_bmap->start = src->start;
319 new_bmap->end = src->end;
320 new_bmap->real_end = src->real_end;
321 new_bmap->bitmap_ops = src->bitmap_ops;
322 new_bmap->base_error_code = src->base_error_code;
323 new_bmap->cluster_bits = src->cluster_bits;
325 descr = src->description;
327 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
329 ext2fs_free_mem(&new_bmap);
332 strcpy(new_descr, "copy of ");
333 strcat(new_descr, descr);
334 new_bmap->description = new_descr;
337 retval = src->bitmap_ops->copy_bmap(src, new_bmap);
339 ext2fs_free_mem(&new_bmap->description);
340 ext2fs_free_mem(&new_bmap);
344 *dest = (ext2fs_generic_bitmap) new_bmap;
349 errcode_t ext2fs_merge_generic_bmap(ext2fs_generic_bitmap gen_src,
350 ext2fs_generic_bitmap gen_dest,
351 ext2fs_generic_bitmap gen_dup,
352 ext2fs_generic_bitmap gen_dup_allowed)
354 ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64)gen_src;
355 ext2fs_generic_bitmap_64 dest = (ext2fs_generic_bitmap_64)gen_dest;
356 ext2fs_generic_bitmap_64 dup = (ext2fs_generic_bitmap_64)gen_dup;
357 ext2fs_generic_bitmap_64 dup_allowed = (ext2fs_generic_bitmap_64)gen_dup_allowed;
362 if (!EXT2FS_IS_64_BITMAP(src) || !EXT2FS_IS_64_BITMAP(dest) ||
363 (dup && !EXT2FS_IS_64_BITMAP(dup)) ||
364 (dup_allowed && !EXT2FS_IS_64_BITMAP(dup_allowed)))
367 if (src->bitmap_ops != dest->bitmap_ops ||
368 (dup && src->bitmap_ops != dup->bitmap_ops) ||
369 (dup_allowed && src->bitmap_ops != dup_allowed->bitmap_ops))
372 if (src->bitmap_ops->merge_bmap == NULL)
375 return src->bitmap_ops->merge_bmap(src, dest, dup, dup_allowed);
378 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
382 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
387 if (EXT2FS_IS_32_BITMAP(bmap))
388 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
389 new_real_end, gen_bmap);
391 if (!EXT2FS_IS_64_BITMAP(bmap))
394 INC_STAT(bmap, resize_count);
396 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
399 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
401 __u64 end, __u64 *oend)
403 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
408 if (EXT2FS_IS_32_BITMAP(bitmap)) {
412 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
414 neq, end, &tmp_oend);
420 if (!EXT2FS_IS_64_BITMAP(bitmap))
423 if (end > bitmap->real_end)
431 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
433 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
438 if (EXT2FS_IS_32_BITMAP(bitmap))
439 return ext2fs_get_generic_bitmap_start(gen_bitmap);
441 if (!EXT2FS_IS_64_BITMAP(bitmap))
444 return bitmap->start;
447 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
449 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
454 if (EXT2FS_IS_32_BITMAP(bitmap))
455 return ext2fs_get_generic_bitmap_end(gen_bitmap);
457 if (!EXT2FS_IS_64_BITMAP(bitmap))
463 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
465 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
467 if (EXT2FS_IS_32_BITMAP(bitmap))
468 ext2fs_clear_generic_bitmap(gen_bitmap);
470 bitmap->bitmap_ops->clear_bmap(bitmap);
473 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
476 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
481 if (EXT2FS_IS_32_BITMAP(bitmap)) {
482 if (arg & ~0xffffffffULL) {
483 ext2fs_warn_bitmap2(gen_bitmap,
484 EXT2FS_MARK_ERROR, 0xffffffff);
487 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
490 if (!EXT2FS_IS_64_BITMAP(bitmap))
493 arg >>= bitmap->cluster_bits;
495 #ifdef ENABLE_BMAP_STATS_OPS
496 if (arg == bitmap->stats.last_marked + 1)
497 bitmap->stats.mark_seq++;
498 if (arg < bitmap->stats.last_marked)
499 bitmap->stats.mark_back++;
500 bitmap->stats.last_marked = arg;
501 bitmap->stats.mark_count++;
504 if ((arg < bitmap->start) || (arg > bitmap->end)) {
505 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
509 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
512 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
515 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
520 if (EXT2FS_IS_32_BITMAP(bitmap)) {
521 if (arg & ~0xffffffffULL) {
522 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
526 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
529 if (!EXT2FS_IS_64_BITMAP(bitmap))
532 arg >>= bitmap->cluster_bits;
534 INC_STAT(bitmap, unmark_count);
536 if ((arg < bitmap->start) || (arg > bitmap->end)) {
537 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
541 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
544 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
547 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
551 if (EXT2FS_IS_32_BITMAP(bitmap)) {
552 if (arg & ~0xffffffffULL) {
553 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
557 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
560 if (!EXT2FS_IS_64_BITMAP(bitmap))
563 arg >>= bitmap->cluster_bits;
565 #ifdef ENABLE_BMAP_STATS_OPS
566 bitmap->stats.test_count++;
567 if (arg == bitmap->stats.last_tested + 1)
568 bitmap->stats.test_seq++;
569 if (arg < bitmap->stats.last_tested)
570 bitmap->stats.test_back++;
571 bitmap->stats.last_tested = arg;
574 if ((arg < bitmap->start) || (arg > bitmap->end)) {
575 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
579 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
582 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
583 __u64 start, unsigned int num,
586 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
591 if (EXT2FS_IS_32_BITMAP(bmap)) {
592 if ((start+num-1) & ~0xffffffffULL) {
593 ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
597 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
601 if (!EXT2FS_IS_64_BITMAP(bmap))
604 INC_STAT(bmap, set_range_count);
606 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
609 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
610 __u64 start, unsigned int num,
613 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
618 if (EXT2FS_IS_32_BITMAP(bmap)) {
619 if ((start+num-1) & ~0xffffffffULL) {
620 ext2fs_warn_bitmap2(gen_bmap,
621 EXT2FS_UNMARK_ERROR, 0xffffffff);
624 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
628 if (!EXT2FS_IS_64_BITMAP(bmap))
631 INC_STAT(bmap, get_range_count);
633 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
636 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
637 ext2fs_generic_bitmap gen_bm1,
638 ext2fs_generic_bitmap gen_bm2)
640 ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
641 ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
646 if (bm1->magic != bm2->magic)
649 /* Now we know both bitmaps have the same magic */
650 if (EXT2FS_IS_32_BITMAP(bm1))
651 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
654 if (!EXT2FS_IS_64_BITMAP(bm1))
657 if ((bm1->start != bm2->start) ||
658 (bm1->end != bm2->end))
661 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
662 if (ext2fs_test_generic_bmap(gen_bm1, i) !=
663 ext2fs_test_generic_bmap(gen_bm2, i))
669 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
671 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
674 if (EXT2FS_IS_32_BITMAP(bmap)) {
675 ext2fs_set_generic_bitmap_padding(gen_bmap);
679 start = bmap->end + 1;
680 num = bmap->real_end - bmap->end;
681 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
682 /* XXX ought to warn on error */
685 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
686 blk64_t block, unsigned int num)
688 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
689 __u64 end = block + num;
695 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
698 if (EXT2FS_IS_32_BITMAP(bmap)) {
699 if ((block & ~0xffffffffULL) ||
700 ((block+num-1) & ~0xffffffffULL)) {
701 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
702 EXT2FS_UNMARK_ERROR, 0xffffffff);
705 return ext2fs_test_block_bitmap_range(
706 (ext2fs_generic_bitmap) bmap, block, num);
709 if (!EXT2FS_IS_64_BITMAP(bmap))
712 INC_STAT(bmap, test_ext_count);
714 /* convert to clusters if necessary */
715 block >>= bmap->cluster_bits;
716 end += (1ULL << bmap->cluster_bits) - 1;
717 end >>= bmap->cluster_bits;
720 if ((block < bmap->start) || (block > bmap->end) ||
721 (block+num-1 > bmap->end)) {
722 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
727 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
730 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
731 blk64_t block, unsigned int num)
733 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
734 __u64 end = block + num;
739 if (EXT2FS_IS_32_BITMAP(bmap)) {
740 if ((block & ~0xffffffffULL) ||
741 ((block+num-1) & ~0xffffffffULL)) {
742 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
743 EXT2FS_UNMARK_ERROR, 0xffffffff);
746 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
750 if (!EXT2FS_IS_64_BITMAP(bmap))
753 INC_STAT(bmap, mark_ext_count);
755 /* convert to clusters if necessary */
756 block >>= bmap->cluster_bits;
757 end += (1ULL << bmap->cluster_bits) - 1;
758 end >>= bmap->cluster_bits;
761 if ((block < bmap->start) || (block > bmap->end) ||
762 (block+num-1 > bmap->end)) {
763 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
768 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
771 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
772 blk64_t block, unsigned int num)
774 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
775 __u64 end = block + num;
780 if (EXT2FS_IS_32_BITMAP(bmap)) {
781 if ((block & ~0xffffffffULL) ||
782 ((block+num-1) & ~0xffffffffULL)) {
783 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
784 EXT2FS_UNMARK_ERROR, 0xffffffff);
787 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
791 if (!EXT2FS_IS_64_BITMAP(bmap))
794 INC_STAT(bmap, unmark_ext_count);
796 /* convert to clusters if necessary */
797 block >>= bmap->cluster_bits;
798 end += (1ULL << bmap->cluster_bits) - 1;
799 end >>= bmap->cluster_bits;
802 if ((block < bmap->start) || (block > bmap->end) ||
803 (block+num-1 > bmap->end)) {
804 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
809 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
812 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
814 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
817 if (bitmap && bitmap->description)
818 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
819 "called %s with 64-bit bitmap for %s", func,
820 bitmap->description);
822 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
823 "called %s with 64-bit bitmap", func);
827 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
828 ext2fs_block_bitmap *bitmap)
830 ext2fs_generic_bitmap_64 bmap, cmap;
831 ext2fs_block_bitmap gen_bmap = *bitmap, gen_cmap;
833 blk64_t i, next, b_end, c_end;
835 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
836 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
837 return 0; /* Nothing to do */
839 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
844 cmap = (ext2fs_generic_bitmap_64) gen_cmap;
847 bmap->end = bmap->real_end;
849 cmap->end = cmap->real_end;
850 while (i < bmap->real_end) {
851 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
852 i, bmap->real_end, &next);
855 ext2fs_mark_block_bitmap2(gen_cmap, next);
856 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
860 ext2fs_free_block_bitmap(gen_bmap);
861 *bitmap = (ext2fs_block_bitmap) cmap;
865 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
866 __u64 start, __u64 end, __u64 *out)
868 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
869 __u64 cstart, cend, cout;
875 if (EXT2FS_IS_32_BITMAP(bitmap)) {
878 if (((start) & ~0xffffffffULL) ||
879 ((end) & ~0xffffffffULL)) {
880 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
884 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
891 if (!EXT2FS_IS_64_BITMAP(bitmap))
894 cstart = start >> bmap64->cluster_bits;
895 cend = end >> bmap64->cluster_bits;
897 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
898 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
902 if (bmap64->bitmap_ops->find_first_zero) {
903 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
908 cout <<= bmap64->cluster_bits;
909 *out = (cout >= start) ? cout : start;
913 for (cout = cstart; cout <= cend; cout++)
914 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
920 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
921 __u64 start, __u64 end, __u64 *out)
923 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
924 __u64 cstart, cend, cout;
930 if (EXT2FS_IS_32_BITMAP(bitmap)) {
933 if (((start) & ~0xffffffffULL) ||
934 ((end) & ~0xffffffffULL)) {
935 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
939 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
946 if (!EXT2FS_IS_64_BITMAP(bitmap))
949 cstart = start >> bmap64->cluster_bits;
950 cend = end >> bmap64->cluster_bits;
952 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
953 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
957 if (bmap64->bitmap_ops->find_first_set) {
958 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
963 cout <<= bmap64->cluster_bits;
964 *out = (cout >= start) ? cout : start;
968 for (cout = cstart; cout <= cend; cout++)
969 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
975 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
976 blk64_t end, blk64_t *out)
980 errcode_t retval = 0;
982 while (start < end) {
983 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
986 if (retval == ENOENT)
992 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
995 tot_set += next - start;
997 } else if (retval == ENOENT) {
999 tot_set += end - start + 1;
1006 *out = EXT2FS_NUM_B2C(fs, tot_set);