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 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 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),
127 #ifdef ENABLE_BMAP_STATS
128 if (gettimeofday(&bitmap->stats.created,
129 (struct timezone *) NULL) == -1) {
130 perror("gettimeofday");
133 bitmap->stats.type = type;
136 /* XXX factor out, repeated in copy_bmap */
137 bitmap->magic = magic;
139 bitmap->start = start;
141 bitmap->real_end = real_end;
142 bitmap->bitmap_ops = ops;
143 bitmap->cluster_bits = 0;
145 case EXT2_ET_MAGIC_INODE_BITMAP64:
146 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
148 case EXT2_ET_MAGIC_BLOCK_BITMAP64:
149 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
150 bitmap->cluster_bits = fs->cluster_ratio_bits;
153 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
156 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
158 ext2fs_free_mem(&bitmap);
161 strcpy(bitmap->description, descr);
163 bitmap->description = 0;
165 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
167 ext2fs_free_mem(&bitmap->description);
168 ext2fs_free_mem(&bitmap);
176 #ifdef ENABLE_BMAP_STATS
177 void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)
179 struct ext2_bmap_statistics *stats = &bitmap->stats;
180 #ifdef ENABLE_BMAP_STATS_OPS
181 float mark_seq_perc = 0.0, test_seq_perc = 0.0;
182 float mark_back_perc = 0.0, test_back_perc = 0.0;
187 #ifdef ENABLE_BMAP_STATS_OPS
188 if (stats->test_count) {
189 test_seq_perc = ((float)stats->test_seq /
190 stats->test_count) * 100;
191 test_back_perc = ((float)stats->test_back /
192 stats->test_count) * 100;
195 if (stats->mark_count) {
196 mark_seq_perc = ((float)stats->mark_seq /
197 stats->mark_count) * 100;
198 mark_back_perc = ((float)stats->mark_back /
199 stats->mark_count) * 100;
203 if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
204 perror("gettimeofday");
208 inuse = (double) now.tv_sec + \
209 (((double) now.tv_usec) * 0.000001);
210 inuse -= (double) stats->created.tv_sec + \
211 (((double) stats->created.tv_usec) * 0.000001);
213 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
215 fprintf(stderr, "=================================================\n");
216 #ifdef ENABLE_BMAP_STATS_OPS
217 fprintf(stderr, "%16llu bits long\n",
218 bitmap->real_end - bitmap->start);
219 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
220 stats->copy_count, stats->resize_count);
221 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
222 stats->mark_count, stats->unmark_count);
223 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
224 stats->test_count, stats->mark_ext_count);
225 fprintf(stderr, "%16lu unmark_bmap_extent\n"
226 "%16lu test_clear_bmap_extent\n",
227 stats->unmark_ext_count, stats->test_ext_count);
228 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
229 stats->set_range_count, stats->get_range_count);
230 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
231 stats->clear_count, stats->test_seq, test_seq_perc);
232 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
233 "%16llu bits tested backwards (%.2f%%)\n",
234 stats->mark_seq, mark_seq_perc,
235 stats->test_back, test_back_perc);
236 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
237 "%16.2f seconds in use\n",
238 stats->mark_back, mark_back_perc, inuse);
239 #endif /* ENABLE_BMAP_STATS_OPS */
243 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
248 if (EXT2FS_IS_32_BITMAP(bmap)) {
249 ext2fs_free_generic_bitmap(bmap);
253 if (!EXT2FS_IS_64_BITMAP(bmap))
256 #ifdef ENABLE_BMAP_STATS
257 if (getenv("E2FSPROGS_BITMAP_STATS")) {
258 ext2fs_print_bmap_statistics(bmap);
259 bmap->bitmap_ops->print_stats(bmap);
263 bmap->bitmap_ops->free_bmap(bmap);
265 if (bmap->description) {
266 ext2fs_free_mem(&bmap->description);
267 bmap->description = 0;
270 ext2fs_free_mem(&bmap);
273 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
274 ext2fs_generic_bitmap *dest)
276 char *descr, *new_descr;
277 ext2fs_generic_bitmap new_bmap;
283 if (EXT2FS_IS_32_BITMAP(src))
284 return ext2fs_copy_generic_bitmap(src, dest);
286 if (!EXT2FS_IS_64_BITMAP(src))
289 /* Allocate a new bitmap struct */
290 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
296 #ifdef ENABLE_BMAP_STATS_OPS
297 src->stats.copy_count++;
299 #ifdef ENABLE_BMAP_STATS
300 if (gettimeofday(&new_bmap->stats.created,
301 (struct timezone *) NULL) == -1) {
302 perror("gettimeofday");
305 new_bmap->stats.type = src->stats.type;
308 /* Copy all the high-level parts over */
309 new_bmap->magic = src->magic;
310 new_bmap->fs = src->fs;
311 new_bmap->start = src->start;
312 new_bmap->end = src->end;
313 new_bmap->real_end = src->real_end;
314 new_bmap->bitmap_ops = src->bitmap_ops;
315 new_bmap->base_error_code = src->base_error_code;
316 new_bmap->cluster_bits = src->cluster_bits;
318 descr = src->description;
320 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
322 ext2fs_free_mem(&new_bmap);
325 sprintf(new_descr, "copy of %s", descr);
326 new_bmap->description = new_descr;
329 retval = src->bitmap_ops->copy_bmap(src, new_bmap);
331 ext2fs_free_mem(&new_bmap->description);
332 ext2fs_free_mem(&new_bmap);
341 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
348 if (EXT2FS_IS_32_BITMAP(bmap))
349 return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
352 if (!EXT2FS_IS_64_BITMAP(bmap))
355 INC_STAT(bmap, resize_count);
357 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
360 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
362 __u64 end, __u64 *oend)
367 if (EXT2FS_IS_32_BITMAP(bitmap)) {
371 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
372 neq, end, &tmp_oend);
378 if (!EXT2FS_IS_64_BITMAP(bitmap))
381 if (end > bitmap->real_end)
389 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)
394 if (EXT2FS_IS_32_BITMAP(bitmap))
395 return ext2fs_get_generic_bitmap_start(bitmap);
397 if (!EXT2FS_IS_64_BITMAP(bitmap))
400 return bitmap->start;
403 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)
408 if (EXT2FS_IS_32_BITMAP(bitmap))
409 return ext2fs_get_generic_bitmap_end(bitmap);
411 if (!EXT2FS_IS_64_BITMAP(bitmap))
417 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
419 if (EXT2FS_IS_32_BITMAP(bitmap))
420 ext2fs_clear_generic_bitmap(bitmap);
422 bitmap->bitmap_ops->clear_bmap (bitmap);
425 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
431 if (EXT2FS_IS_32_BITMAP(bitmap)) {
432 if (arg & ~0xffffffffULL) {
433 ext2fs_warn_bitmap2(bitmap,
434 EXT2FS_MARK_ERROR, 0xffffffff);
437 return ext2fs_mark_generic_bitmap(bitmap, arg);
440 if (!EXT2FS_IS_64_BITMAP(bitmap))
443 arg >>= bitmap->cluster_bits;
445 #ifdef ENABLE_BMAP_STATS_OPS
446 if (arg == bitmap->stats.last_marked + 1)
447 bitmap->stats.mark_seq++;
448 if (arg < bitmap->stats.last_marked)
449 bitmap->stats.mark_back++;
450 bitmap->stats.last_marked = arg;
451 bitmap->stats.mark_count++;
454 if ((arg < bitmap->start) || (arg > bitmap->end)) {
455 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
459 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
462 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
468 if (EXT2FS_IS_32_BITMAP(bitmap)) {
469 if (arg & ~0xffffffffULL) {
470 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
474 return ext2fs_unmark_generic_bitmap(bitmap, arg);
477 if (!EXT2FS_IS_64_BITMAP(bitmap))
480 arg >>= bitmap->cluster_bits;
482 INC_STAT(bitmap, unmark_count);
484 if ((arg < bitmap->start) || (arg > bitmap->end)) {
485 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
489 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
492 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
498 if (EXT2FS_IS_32_BITMAP(bitmap)) {
499 if (arg & ~0xffffffffULL) {
500 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
504 return ext2fs_test_generic_bitmap(bitmap, arg);
507 if (!EXT2FS_IS_64_BITMAP(bitmap))
510 arg >>= bitmap->cluster_bits;
512 #ifdef ENABLE_BMAP_STATS_OPS
513 bitmap->stats.test_count++;
514 if (arg == bitmap->stats.last_tested + 1)
515 bitmap->stats.test_seq++;
516 if (arg < bitmap->stats.last_tested)
517 bitmap->stats.test_back++;
518 bitmap->stats.last_tested = arg;
521 if ((arg < bitmap->start) || (arg > bitmap->end)) {
522 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
526 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
529 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
530 __u64 start, unsigned int num,
536 if (EXT2FS_IS_32_BITMAP(bmap)) {
537 if ((start+num-1) & ~0xffffffffULL) {
538 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
542 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
546 if (!EXT2FS_IS_64_BITMAP(bmap))
549 INC_STAT(bmap, set_range_count);
551 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
554 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
555 __u64 start, unsigned int num,
561 if (EXT2FS_IS_32_BITMAP(bmap)) {
562 if ((start+num-1) & ~0xffffffffULL) {
563 ext2fs_warn_bitmap2(bmap,
564 EXT2FS_UNMARK_ERROR, 0xffffffff);
567 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
571 if (!EXT2FS_IS_64_BITMAP(bmap))
574 INC_STAT(bmap, get_range_count);
576 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
579 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
580 ext2fs_generic_bitmap bm1,
581 ext2fs_generic_bitmap bm2)
587 if (bm1->magic != bm2->magic)
590 /* Now we know both bitmaps have the same magic */
591 if (EXT2FS_IS_32_BITMAP(bm1))
592 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
594 if (!EXT2FS_IS_64_BITMAP(bm1))
597 if ((bm1->start != bm2->start) ||
598 (bm1->end != bm2->end))
601 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
602 if (ext2fs_test_generic_bmap(bm1, i) !=
603 ext2fs_test_generic_bmap(bm2, i))
609 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)
613 if (EXT2FS_IS_32_BITMAP(bmap)) {
614 ext2fs_set_generic_bitmap_padding(bmap);
618 start = bmap->end + 1;
619 num = bmap->real_end - bmap->end;
620 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
621 /* XXX ought to warn on error */
624 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
625 blk64_t block, unsigned int num)
631 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
634 if (EXT2FS_IS_32_BITMAP(bmap)) {
635 if ((block+num-1) & ~0xffffffffULL) {
636 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
637 EXT2FS_UNMARK_ERROR, 0xffffffff);
640 return ext2fs_test_block_bitmap_range(
641 (ext2fs_generic_bitmap) bmap, block, num);
644 if (!EXT2FS_IS_64_BITMAP(bmap))
647 INC_STAT(bmap, test_ext_count);
649 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
652 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
653 blk64_t block, unsigned int num)
658 if (EXT2FS_IS_32_BITMAP(bmap)) {
659 if ((block+num-1) & ~0xffffffffULL) {
660 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
661 EXT2FS_UNMARK_ERROR, 0xffffffff);
664 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
668 if (!EXT2FS_IS_64_BITMAP(bmap))
671 INC_STAT(bmap, mark_ext_count);
673 if ((block < bmap->start) || (block+num-1 > bmap->end)) {
674 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
679 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
682 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
683 blk64_t block, unsigned int num)
688 if (EXT2FS_IS_32_BITMAP(bmap)) {
689 if ((block+num-1) & ~0xffffffffULL) {
690 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
691 EXT2FS_UNMARK_ERROR, 0xffffffff);
694 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
698 if (!EXT2FS_IS_64_BITMAP(bmap))
701 INC_STAT(bmap, unmark_ext_count);
703 if ((block < bmap->start) || (block+num-1 > bmap->end)) {
704 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
709 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
712 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
715 if (bitmap && bitmap->description)
716 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
717 "called %s with 64-bit bitmap for %s", func,
718 bitmap->description);
720 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
721 "called %s with 64-bit bitmap", func);
725 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
726 ext2fs_block_bitmap *bitmap)
728 ext2fs_block_bitmap cmap, bmap;
730 blk64_t i, b_end, c_end;
735 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
736 return 0; /* Nothing to do */
738 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
745 bmap->end = bmap->real_end;
747 cmap->end = cmap->real_end;
749 ratio = 1 << fs->cluster_ratio_bits;
750 while (i < bmap->real_end) {
751 if (ext2fs_test_block_bitmap2(bmap, i)) {
752 ext2fs_mark_block_bitmap2(cmap, i);
763 ext2fs_free_block_bitmap(bmap);
768 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
769 __u64 start, __u64 end, __u64 *out)
776 if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
777 return bitmap->bitmap_ops->find_first_zero(bitmap, start,
780 if (EXT2FS_IS_32_BITMAP(bitmap)) {
784 if (((start) & ~0xffffffffULL) ||
785 ((end) & ~0xffffffffULL)) {
786 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
790 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
797 if (!EXT2FS_IS_64_BITMAP(bitmap))
800 start >>= bitmap->cluster_bits;
801 end >>= bitmap->cluster_bits;
803 if (start < bitmap->start || end > bitmap->end || start > end) {
804 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
808 while (start <= end) {
809 b = bitmap->bitmap_ops->test_bmap(bitmap, start);
811 *out = start << bitmap->cluster_bits;