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", arg
, bitmap
->description
);
79 com_err(0, bitmap
->base_error_code
+ code
, "#%llu", arg
);
83 #ifdef ENABLE_BMAP_STATS_OPS
84 #define INC_STAT(map, name) map->stats.name
86 #define INC_STAT(map, name) ;;
90 errcode_t
ext2fs_alloc_generic_bmap(ext2_filsys fs
, errcode_t magic
,
91 int type
, __u64 start
, __u64 end
,
94 ext2fs_generic_bitmap
*ret
)
96 ext2fs_generic_bitmap_64 bitmap
;
97 struct ext2_bitmap_ops
*ops
;
102 type
= EXT2FS_BMAP64_BITARRAY
;
105 case EXT2FS_BMAP64_BITARRAY
:
106 ops
= &ext2fs_blkmap64_bitarray
;
108 case EXT2FS_BMAP64_RBTREE
:
109 ops
= &ext2fs_blkmap64_rbtree
;
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
;
116 ops
= &ext2fs_blkmap64_rbtree
;
122 retval
= ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64
),
127 #ifdef ENABLE_BMAP_STATS
128 if (gettimeofday(&bitmap
->stats
.created
,
129 (struct timezone
*) NULL
) == -1) {
130 perror("gettimeofday");
131 ext2fs_free_mem(&bitmap
);
134 bitmap
->stats
.type
= type
;
137 /* XXX factor out, repeated in copy_bmap */
138 bitmap
->magic
= magic
;
140 bitmap
->start
= start
;
142 bitmap
->real_end
= real_end
;
143 bitmap
->bitmap_ops
= ops
;
144 bitmap
->cluster_bits
= 0;
146 case EXT2_ET_MAGIC_INODE_BITMAP64
:
147 bitmap
->base_error_code
= EXT2_ET_BAD_INODE_MARK
;
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
;
154 bitmap
->base_error_code
= EXT2_ET_BAD_GENERIC_MARK
;
157 retval
= ext2fs_get_mem(strlen(descr
)+1, &bitmap
->description
);
159 ext2fs_free_mem(&bitmap
);
162 strcpy(bitmap
->description
, descr
);
164 bitmap
->description
= 0;
166 retval
= bitmap
->bitmap_ops
->new_bmap(fs
, bitmap
);
168 ext2fs_free_mem(&bitmap
->description
);
169 ext2fs_free_mem(&bitmap
);
173 *ret
= (ext2fs_generic_bitmap
) bitmap
;
177 #ifdef ENABLE_BMAP_STATS
178 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap
)
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;
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;
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;
204 if (gettimeofday(&now
, (struct timezone
*) NULL
) == -1) {
205 perror("gettimeofday");
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);
214 fprintf(stderr
, "\n[+] %s bitmap (type %d)\n", bitmap
->description
,
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 */
244 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap
)
246 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
251 if (EXT2FS_IS_32_BITMAP(bmap
)) {
252 ext2fs_free_generic_bitmap(gen_bmap
);
256 if (!EXT2FS_IS_64_BITMAP(bmap
))
259 #ifdef ENABLE_BMAP_STATS
260 if (getenv("E2FSPROGS_BITMAP_STATS")) {
261 ext2fs_print_bmap_statistics(bmap
);
262 bmap
->bitmap_ops
->print_stats(bmap
);
266 bmap
->bitmap_ops
->free_bmap(bmap
);
268 if (bmap
->description
) {
269 ext2fs_free_mem(&bmap
->description
);
270 bmap
->description
= 0;
273 ext2fs_free_mem(&bmap
);
276 errcode_t
ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src
,
277 ext2fs_generic_bitmap
*dest
)
279 ext2fs_generic_bitmap_64 src
= (ext2fs_generic_bitmap_64
) gen_src
;
280 char *descr
, *new_descr
;
281 ext2fs_generic_bitmap_64 new_bmap
;
287 if (EXT2FS_IS_32_BITMAP(src
))
288 return ext2fs_copy_generic_bitmap(gen_src
, dest
);
290 if (!EXT2FS_IS_64_BITMAP(src
))
293 /* Allocate a new bitmap struct */
294 retval
= ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64
),
300 #ifdef ENABLE_BMAP_STATS_OPS
301 src
->stats
.copy_count
++;
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
);
310 new_bmap
->stats
.type
= src
->stats
.type
;
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
;
323 descr
= src
->description
;
325 retval
= ext2fs_get_mem(strlen(descr
)+10, &new_descr
);
327 ext2fs_free_mem(&new_bmap
);
330 strcpy(new_descr
, "copy of ");
331 strcat(new_descr
, descr
);
332 new_bmap
->description
= new_descr
;
335 retval
= src
->bitmap_ops
->copy_bmap(src
, new_bmap
);
337 ext2fs_free_mem(&new_bmap
->description
);
338 ext2fs_free_mem(&new_bmap
);
342 *dest
= (ext2fs_generic_bitmap
) new_bmap
;
347 errcode_t
ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap
,
351 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
356 if (EXT2FS_IS_32_BITMAP(bmap
))
357 return ext2fs_resize_generic_bitmap(gen_bmap
->magic
, new_end
,
358 new_real_end
, gen_bmap
);
360 if (!EXT2FS_IS_64_BITMAP(bmap
))
363 INC_STAT(bmap
, resize_count
);
365 return bmap
->bitmap_ops
->resize_bmap(bmap
, new_end
, new_real_end
);
368 errcode_t
ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap
,
370 __u64 end
, __u64
*oend
)
372 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
377 if (EXT2FS_IS_32_BITMAP(bitmap
)) {
381 retval
= ext2fs_fudge_generic_bitmap_end(gen_bitmap
,
383 neq
, end
, &tmp_oend
);
389 if (!EXT2FS_IS_64_BITMAP(bitmap
))
392 if (end
> bitmap
->real_end
)
400 __u64
ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap
)
402 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
407 if (EXT2FS_IS_32_BITMAP(bitmap
))
408 return ext2fs_get_generic_bitmap_start(gen_bitmap
);
410 if (!EXT2FS_IS_64_BITMAP(bitmap
))
413 return bitmap
->start
;
416 __u64
ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap
)
418 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
423 if (EXT2FS_IS_32_BITMAP(bitmap
))
424 return ext2fs_get_generic_bitmap_end(gen_bitmap
);
426 if (!EXT2FS_IS_64_BITMAP(bitmap
))
432 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap
)
434 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
436 if (EXT2FS_IS_32_BITMAP(bitmap
))
437 ext2fs_clear_generic_bitmap(gen_bitmap
);
439 bitmap
->bitmap_ops
->clear_bmap(bitmap
);
442 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap
,
445 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
450 if (EXT2FS_IS_32_BITMAP(bitmap
)) {
451 if (arg
& ~0xffffffffULL
) {
452 ext2fs_warn_bitmap2(gen_bitmap
,
453 EXT2FS_MARK_ERROR
, 0xffffffff);
456 return ext2fs_mark_generic_bitmap(gen_bitmap
, arg
);
459 if (!EXT2FS_IS_64_BITMAP(bitmap
))
462 arg
>>= bitmap
->cluster_bits
;
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
++;
473 if ((arg
< bitmap
->start
) || (arg
> bitmap
->end
)) {
474 warn_bitmap(bitmap
, EXT2FS_MARK_ERROR
, arg
);
478 return bitmap
->bitmap_ops
->mark_bmap(bitmap
, arg
);
481 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap
,
484 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
489 if (EXT2FS_IS_32_BITMAP(bitmap
)) {
490 if (arg
& ~0xffffffffULL
) {
491 ext2fs_warn_bitmap2(gen_bitmap
, EXT2FS_UNMARK_ERROR
,
495 return ext2fs_unmark_generic_bitmap(gen_bitmap
, arg
);
498 if (!EXT2FS_IS_64_BITMAP(bitmap
))
501 arg
>>= bitmap
->cluster_bits
;
503 INC_STAT(bitmap
, unmark_count
);
505 if ((arg
< bitmap
->start
) || (arg
> bitmap
->end
)) {
506 warn_bitmap(bitmap
, EXT2FS_UNMARK_ERROR
, arg
);
510 return bitmap
->bitmap_ops
->unmark_bmap(bitmap
, arg
);
513 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap
,
516 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_TEST_ERROR
,
526 return ext2fs_test_generic_bitmap(gen_bitmap
, arg
);
529 if (!EXT2FS_IS_64_BITMAP(bitmap
))
532 arg
>>= bitmap
->cluster_bits
;
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
;
543 if ((arg
< bitmap
->start
) || (arg
> bitmap
->end
)) {
544 warn_bitmap(bitmap
, EXT2FS_TEST_ERROR
, arg
);
548 return bitmap
->bitmap_ops
->test_bmap(bitmap
, arg
);
551 errcode_t
ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap
,
552 __u64 start
, unsigned int num
,
555 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
560 if (EXT2FS_IS_32_BITMAP(bmap
)) {
561 if ((start
+num
-1) & ~0xffffffffULL
) {
562 ext2fs_warn_bitmap2(gen_bmap
, EXT2FS_UNMARK_ERROR
,
566 return ext2fs_set_generic_bitmap_range(gen_bmap
, bmap
->magic
,
570 if (!EXT2FS_IS_64_BITMAP(bmap
))
573 INC_STAT(bmap
, set_range_count
);
575 return bmap
->bitmap_ops
->set_bmap_range(bmap
, start
, num
, in
);
578 errcode_t
ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap
,
579 __u64 start
, unsigned int num
,
582 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
587 if (EXT2FS_IS_32_BITMAP(bmap
)) {
588 if ((start
+num
-1) & ~0xffffffffULL
) {
589 ext2fs_warn_bitmap2(gen_bmap
,
590 EXT2FS_UNMARK_ERROR
, 0xffffffff);
593 return ext2fs_get_generic_bitmap_range(gen_bmap
, bmap
->magic
,
597 if (!EXT2FS_IS_64_BITMAP(bmap
))
600 INC_STAT(bmap
, get_range_count
);
602 return bmap
->bitmap_ops
->get_bmap_range(bmap
, start
, num
, out
);
605 errcode_t
ext2fs_compare_generic_bmap(errcode_t neq
,
606 ext2fs_generic_bitmap gen_bm1
,
607 ext2fs_generic_bitmap gen_bm2
)
609 ext2fs_generic_bitmap_64 bm1
= (ext2fs_generic_bitmap_64
) gen_bm1
;
610 ext2fs_generic_bitmap_64 bm2
= (ext2fs_generic_bitmap_64
) gen_bm2
;
615 if (bm1
->magic
!= bm2
->magic
)
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
,
623 if (!EXT2FS_IS_64_BITMAP(bm1
))
626 if ((bm1
->start
!= bm2
->start
) ||
627 (bm1
->end
!= bm2
->end
))
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
))
638 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap
)
640 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
643 if (EXT2FS_IS_32_BITMAP(bmap
)) {
644 ext2fs_set_generic_bitmap_padding(gen_bmap
);
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 */
654 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap
,
655 blk64_t block
, unsigned int num
)
657 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
658 __u64 end
= block
+ num
;
664 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap
)
667 if (EXT2FS_IS_32_BITMAP(bmap
)) {
668 if ((block
& ~0xffffffffULL
) ||
669 ((block
+num
-1) & ~0xffffffffULL
)) {
670 ext2fs_warn_bitmap2((ext2fs_generic_bitmap
) bmap
,
671 EXT2FS_UNMARK_ERROR
, 0xffffffff);
674 return ext2fs_test_block_bitmap_range(
675 (ext2fs_generic_bitmap
) bmap
, block
, num
);
678 if (!EXT2FS_IS_64_BITMAP(bmap
))
681 INC_STAT(bmap
, test_ext_count
);
683 /* convert to clusters if necessary */
684 block
>>= bmap
->cluster_bits
;
685 end
+= (1 << bmap
->cluster_bits
) - 1;
686 end
>>= bmap
->cluster_bits
;
689 if ((block
< bmap
->start
) || (block
> bmap
->end
) ||
690 (block
+num
-1 > bmap
->end
)) {
691 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST
, block
,
696 return bmap
->bitmap_ops
->test_clear_bmap_extent(bmap
, block
, num
);
699 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap
,
700 blk64_t block
, unsigned int num
)
702 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
703 __u64 end
= block
+ num
;
708 if (EXT2FS_IS_32_BITMAP(bmap
)) {
709 if ((block
& ~0xffffffffULL
) ||
710 ((block
+num
-1) & ~0xffffffffULL
)) {
711 ext2fs_warn_bitmap2((ext2fs_generic_bitmap
) bmap
,
712 EXT2FS_UNMARK_ERROR
, 0xffffffff);
715 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap
) bmap
,
719 if (!EXT2FS_IS_64_BITMAP(bmap
))
722 INC_STAT(bmap
, mark_ext_count
);
724 /* convert to clusters if necessary */
725 block
>>= bmap
->cluster_bits
;
726 end
+= (1 << bmap
->cluster_bits
) - 1;
727 end
>>= bmap
->cluster_bits
;
730 if ((block
< bmap
->start
) || (block
> bmap
->end
) ||
731 (block
+num
-1 > bmap
->end
)) {
732 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK
, block
,
737 bmap
->bitmap_ops
->mark_bmap_extent(bmap
, block
, num
);
740 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap
,
741 blk64_t block
, unsigned int num
)
743 ext2fs_generic_bitmap_64 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
744 __u64 end
= block
+ num
;
749 if (EXT2FS_IS_32_BITMAP(bmap
)) {
750 if ((block
& ~0xffffffffULL
) ||
751 ((block
+num
-1) & ~0xffffffffULL
)) {
752 ext2fs_warn_bitmap2((ext2fs_generic_bitmap
) bmap
,
753 EXT2FS_UNMARK_ERROR
, 0xffffffff);
756 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap
) bmap
,
760 if (!EXT2FS_IS_64_BITMAP(bmap
))
763 INC_STAT(bmap
, unmark_ext_count
);
765 /* convert to clusters if necessary */
766 block
>>= bmap
->cluster_bits
;
767 end
+= (1 << bmap
->cluster_bits
) - 1;
768 end
>>= bmap
->cluster_bits
;
771 if ((block
< bmap
->start
) || (block
> bmap
->end
) ||
772 (block
+num
-1 > bmap
->end
)) {
773 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK
, block
,
778 bmap
->bitmap_ops
->unmark_bmap_extent(bmap
, block
, num
);
781 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap
, const char *func
)
783 ext2fs_generic_bitmap_64 bitmap
= (ext2fs_generic_bitmap_64
) gen_bitmap
;
786 if (bitmap
&& bitmap
->description
)
787 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP
,
788 "called %s with 64-bit bitmap for %s", func
,
789 bitmap
->description
);
791 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP
,
792 "called %s with 64-bit bitmap", func
);
796 errcode_t
ext2fs_convert_subcluster_bitmap(ext2_filsys fs
,
797 ext2fs_block_bitmap
*bitmap
)
799 ext2fs_generic_bitmap_64 bmap
, cmap
;
800 ext2fs_block_bitmap gen_bmap
= *bitmap
, gen_cmap
;
802 blk64_t i
, next
, b_end
, c_end
;
804 bmap
= (ext2fs_generic_bitmap_64
) gen_bmap
;
805 if (fs
->cluster_ratio_bits
== ext2fs_get_bitmap_granularity(gen_bmap
))
806 return 0; /* Nothing to do */
808 retval
= ext2fs_allocate_block_bitmap(fs
, "converted cluster bitmap",
813 cmap
= (ext2fs_generic_bitmap_64
) gen_cmap
;
816 bmap
->end
= bmap
->real_end
;
818 cmap
->end
= cmap
->real_end
;
819 while (i
< bmap
->real_end
) {
820 retval
= ext2fs_find_first_set_block_bitmap2(gen_bmap
,
821 i
, bmap
->real_end
, &next
);
824 ext2fs_mark_block_bitmap2(gen_cmap
, next
);
825 i
= EXT2FS_C2B(fs
, EXT2FS_B2C(fs
, next
) + 1);
829 ext2fs_free_block_bitmap(gen_bmap
);
830 *bitmap
= (ext2fs_block_bitmap
) cmap
;
834 errcode_t
ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap
,
835 __u64 start
, __u64 end
, __u64
*out
)
837 ext2fs_generic_bitmap_64 bmap64
= (ext2fs_generic_bitmap_64
) bitmap
;
838 __u64 cstart
, cend
, cout
;
844 if (EXT2FS_IS_32_BITMAP(bitmap
)) {
847 if (((start
) & ~0xffffffffULL
) ||
848 ((end
) & ~0xffffffffULL
)) {
849 ext2fs_warn_bitmap2(bitmap
, EXT2FS_TEST_ERROR
, start
);
853 retval
= ext2fs_find_first_zero_generic_bitmap(bitmap
, start
,
860 if (!EXT2FS_IS_64_BITMAP(bitmap
))
863 cstart
= start
>> bmap64
->cluster_bits
;
864 cend
= end
>> bmap64
->cluster_bits
;
866 if (cstart
< bmap64
->start
|| cend
> bmap64
->end
|| start
> end
) {
867 warn_bitmap(bmap64
, EXT2FS_TEST_ERROR
, start
);
871 if (bmap64
->bitmap_ops
->find_first_zero
) {
872 retval
= bmap64
->bitmap_ops
->find_first_zero(bmap64
, cstart
,
877 cout
<<= bmap64
->cluster_bits
;
878 *out
= (cout
>= start
) ? cout
: start
;
882 for (cout
= cstart
; cout
<= cend
; cout
++)
883 if (!bmap64
->bitmap_ops
->test_bmap(bmap64
, cout
))
889 errcode_t
ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap
,
890 __u64 start
, __u64 end
, __u64
*out
)
892 ext2fs_generic_bitmap_64 bmap64
= (ext2fs_generic_bitmap_64
) bitmap
;
893 __u64 cstart
, cend
, cout
;
899 if (EXT2FS_IS_32_BITMAP(bitmap
)) {
902 if (((start
) & ~0xffffffffULL
) ||
903 ((end
) & ~0xffffffffULL
)) {
904 ext2fs_warn_bitmap2(bitmap
, EXT2FS_TEST_ERROR
, start
);
908 retval
= ext2fs_find_first_set_generic_bitmap(bitmap
, start
,
915 if (!EXT2FS_IS_64_BITMAP(bitmap
))
918 cstart
= start
>> bmap64
->cluster_bits
;
919 cend
= end
>> bmap64
->cluster_bits
;
921 if (cstart
< bmap64
->start
|| cend
> bmap64
->end
|| start
> end
) {
922 warn_bitmap(bmap64
, EXT2FS_TEST_ERROR
, start
);
926 if (bmap64
->bitmap_ops
->find_first_set
) {
927 retval
= bmap64
->bitmap_ops
->find_first_set(bmap64
, cstart
,
932 cout
<<= bmap64
->cluster_bits
;
933 *out
= (cout
>= start
) ? cout
: start
;
937 for (cout
= cstart
; cout
<= cend
; cout
++)
938 if (bmap64
->bitmap_ops
->test_bmap(bmap64
, cout
))
944 errcode_t
ext2fs_count_used_clusters(ext2_filsys fs
, blk64_t start
,
945 blk64_t end
, blk64_t
*out
)
951 while (start
< end
) {
952 retval
= ext2fs_find_first_set_block_bitmap2(fs
->block_map
,
955 if (retval
== ENOENT
)
961 retval
= ext2fs_find_first_zero_block_bitmap2(fs
->block_map
,
964 tot_set
+= next
- start
;
966 } else if (retval
== ENOENT
) {
968 tot_set
+= end
- start
+ 1;
975 *out
= EXT2FS_NUM_B2C(fs
, tot_set
);