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_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
353 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
358 if (EXT2FS_IS_32_BITMAP(bmap))
359 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
360 new_real_end, gen_bmap);
362 if (!EXT2FS_IS_64_BITMAP(bmap))
365 INC_STAT(bmap, resize_count);
367 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
370 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
372 __u64 end, __u64 *oend)
374 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
379 if (EXT2FS_IS_32_BITMAP(bitmap)) {
383 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
385 neq, end, &tmp_oend);
391 if (!EXT2FS_IS_64_BITMAP(bitmap))
394 if (end > bitmap->real_end)
402 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
404 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
409 if (EXT2FS_IS_32_BITMAP(bitmap))
410 return ext2fs_get_generic_bitmap_start(gen_bitmap);
412 if (!EXT2FS_IS_64_BITMAP(bitmap))
415 return bitmap->start;
418 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
420 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
425 if (EXT2FS_IS_32_BITMAP(bitmap))
426 return ext2fs_get_generic_bitmap_end(gen_bitmap);
428 if (!EXT2FS_IS_64_BITMAP(bitmap))
434 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
436 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
438 if (EXT2FS_IS_32_BITMAP(bitmap))
439 ext2fs_clear_generic_bitmap(gen_bitmap);
441 bitmap->bitmap_ops->clear_bmap(bitmap);
444 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
447 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
452 if (EXT2FS_IS_32_BITMAP(bitmap)) {
453 if (arg & ~0xffffffffULL) {
454 ext2fs_warn_bitmap2(gen_bitmap,
455 EXT2FS_MARK_ERROR, 0xffffffff);
458 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
461 if (!EXT2FS_IS_64_BITMAP(bitmap))
464 arg >>= bitmap->cluster_bits;
466 #ifdef ENABLE_BMAP_STATS_OPS
467 if (arg == bitmap->stats.last_marked + 1)
468 bitmap->stats.mark_seq++;
469 if (arg < bitmap->stats.last_marked)
470 bitmap->stats.mark_back++;
471 bitmap->stats.last_marked = arg;
472 bitmap->stats.mark_count++;
475 if ((arg < bitmap->start) || (arg > bitmap->end)) {
476 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
480 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
483 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
486 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
491 if (EXT2FS_IS_32_BITMAP(bitmap)) {
492 if (arg & ~0xffffffffULL) {
493 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
497 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
500 if (!EXT2FS_IS_64_BITMAP(bitmap))
503 arg >>= bitmap->cluster_bits;
505 INC_STAT(bitmap, unmark_count);
507 if ((arg < bitmap->start) || (arg > bitmap->end)) {
508 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
512 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
515 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
518 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
522 if (EXT2FS_IS_32_BITMAP(bitmap)) {
523 if (arg & ~0xffffffffULL) {
524 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
528 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
531 if (!EXT2FS_IS_64_BITMAP(bitmap))
534 arg >>= bitmap->cluster_bits;
536 #ifdef ENABLE_BMAP_STATS_OPS
537 bitmap->stats.test_count++;
538 if (arg == bitmap->stats.last_tested + 1)
539 bitmap->stats.test_seq++;
540 if (arg < bitmap->stats.last_tested)
541 bitmap->stats.test_back++;
542 bitmap->stats.last_tested = arg;
545 if ((arg < bitmap->start) || (arg > bitmap->end)) {
546 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
550 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
553 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
554 __u64 start, unsigned int num,
557 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
562 if (EXT2FS_IS_32_BITMAP(bmap)) {
563 if ((start+num-1) & ~0xffffffffULL) {
564 ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
568 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
572 if (!EXT2FS_IS_64_BITMAP(bmap))
575 INC_STAT(bmap, set_range_count);
577 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
580 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
581 __u64 start, unsigned int num,
584 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
589 if (EXT2FS_IS_32_BITMAP(bmap)) {
590 if ((start+num-1) & ~0xffffffffULL) {
591 ext2fs_warn_bitmap2(gen_bmap,
592 EXT2FS_UNMARK_ERROR, 0xffffffff);
595 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
599 if (!EXT2FS_IS_64_BITMAP(bmap))
602 INC_STAT(bmap, get_range_count);
604 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
607 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
608 ext2fs_generic_bitmap gen_bm1,
609 ext2fs_generic_bitmap gen_bm2)
611 ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
612 ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
617 if (bm1->magic != bm2->magic)
620 /* Now we know both bitmaps have the same magic */
621 if (EXT2FS_IS_32_BITMAP(bm1))
622 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
625 if (!EXT2FS_IS_64_BITMAP(bm1))
628 if ((bm1->start != bm2->start) ||
629 (bm1->end != bm2->end))
632 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
633 if (ext2fs_test_generic_bmap(gen_bm1, i) !=
634 ext2fs_test_generic_bmap(gen_bm2, i))
640 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
642 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
645 if (EXT2FS_IS_32_BITMAP(bmap)) {
646 ext2fs_set_generic_bitmap_padding(gen_bmap);
650 start = bmap->end + 1;
651 num = bmap->real_end - bmap->end;
652 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
653 /* XXX ought to warn on error */
656 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
657 blk64_t block, unsigned int num)
659 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
660 __u64 end = block + num;
666 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
669 if (EXT2FS_IS_32_BITMAP(bmap)) {
670 if ((block & ~0xffffffffULL) ||
671 ((block+num-1) & ~0xffffffffULL)) {
672 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
673 EXT2FS_UNMARK_ERROR, 0xffffffff);
676 return ext2fs_test_block_bitmap_range(
677 (ext2fs_generic_bitmap) bmap, block, num);
680 if (!EXT2FS_IS_64_BITMAP(bmap))
683 INC_STAT(bmap, test_ext_count);
685 /* convert to clusters if necessary */
686 block >>= bmap->cluster_bits;
687 end += (1ULL << bmap->cluster_bits) - 1;
688 end >>= bmap->cluster_bits;
691 if ((block < bmap->start) || (block > bmap->end) ||
692 (block+num-1 > bmap->end)) {
693 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
698 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
701 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
702 blk64_t block, unsigned int num)
704 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
705 __u64 end = block + num;
710 if (EXT2FS_IS_32_BITMAP(bmap)) {
711 if ((block & ~0xffffffffULL) ||
712 ((block+num-1) & ~0xffffffffULL)) {
713 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
714 EXT2FS_UNMARK_ERROR, 0xffffffff);
717 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
721 if (!EXT2FS_IS_64_BITMAP(bmap))
724 INC_STAT(bmap, mark_ext_count);
726 /* convert to clusters if necessary */
727 block >>= bmap->cluster_bits;
728 end += (1ULL << bmap->cluster_bits) - 1;
729 end >>= bmap->cluster_bits;
732 if ((block < bmap->start) || (block > bmap->end) ||
733 (block+num-1 > bmap->end)) {
734 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
739 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
742 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
743 blk64_t block, unsigned int num)
745 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
746 __u64 end = block + num;
751 if (EXT2FS_IS_32_BITMAP(bmap)) {
752 if ((block & ~0xffffffffULL) ||
753 ((block+num-1) & ~0xffffffffULL)) {
754 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
755 EXT2FS_UNMARK_ERROR, 0xffffffff);
758 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
762 if (!EXT2FS_IS_64_BITMAP(bmap))
765 INC_STAT(bmap, unmark_ext_count);
767 /* convert to clusters if necessary */
768 block >>= bmap->cluster_bits;
769 end += (1ULL << bmap->cluster_bits) - 1;
770 end >>= bmap->cluster_bits;
773 if ((block < bmap->start) || (block > bmap->end) ||
774 (block+num-1 > bmap->end)) {
775 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
780 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
783 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
785 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
788 if (bitmap && bitmap->description)
789 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
790 "called %s with 64-bit bitmap for %s", func,
791 bitmap->description);
793 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
794 "called %s with 64-bit bitmap", func);
798 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
799 ext2fs_block_bitmap *bitmap)
801 ext2fs_generic_bitmap_64 bmap, cmap;
802 ext2fs_block_bitmap gen_bmap = *bitmap, gen_cmap;
804 blk64_t i, next, b_end, c_end;
806 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
807 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
808 return 0; /* Nothing to do */
810 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
815 cmap = (ext2fs_generic_bitmap_64) gen_cmap;
818 bmap->end = bmap->real_end;
820 cmap->end = cmap->real_end;
821 while (i < bmap->real_end) {
822 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
823 i, bmap->real_end, &next);
826 ext2fs_mark_block_bitmap2(gen_cmap, next);
827 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
831 ext2fs_free_block_bitmap(gen_bmap);
832 *bitmap = (ext2fs_block_bitmap) cmap;
836 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
837 __u64 start, __u64 end, __u64 *out)
839 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
840 __u64 cstart, cend, cout;
846 if (EXT2FS_IS_32_BITMAP(bitmap)) {
849 if (((start) & ~0xffffffffULL) ||
850 ((end) & ~0xffffffffULL)) {
851 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
855 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
862 if (!EXT2FS_IS_64_BITMAP(bitmap))
865 cstart = start >> bmap64->cluster_bits;
866 cend = end >> bmap64->cluster_bits;
868 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
869 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
873 if (bmap64->bitmap_ops->find_first_zero) {
874 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
879 cout <<= bmap64->cluster_bits;
880 *out = (cout >= start) ? cout : start;
884 for (cout = cstart; cout <= cend; cout++)
885 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
891 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
892 __u64 start, __u64 end, __u64 *out)
894 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
895 __u64 cstart, cend, cout;
901 if (EXT2FS_IS_32_BITMAP(bitmap)) {
904 if (((start) & ~0xffffffffULL) ||
905 ((end) & ~0xffffffffULL)) {
906 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
910 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
917 if (!EXT2FS_IS_64_BITMAP(bitmap))
920 cstart = start >> bmap64->cluster_bits;
921 cend = end >> bmap64->cluster_bits;
923 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
924 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
928 if (bmap64->bitmap_ops->find_first_set) {
929 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
934 cout <<= bmap64->cluster_bits;
935 *out = (cout >= start) ? cout : start;
939 for (cout = cstart; cout <= cend; cout++)
940 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
946 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
947 blk64_t end, blk64_t *out)
951 errcode_t retval = 0;
953 while (start < end) {
954 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
957 if (retval == ENOENT)
963 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
966 tot_set += next - start;
968 } else if (retval == ENOENT) {
970 tot_set += end - start + 1;
977 *out = EXT2FS_NUM_B2C(fs, tot_set);