* %End-Header%
*/
+#include "config.h"
#include <stdio.h>
#include <string.h>
#if HAVE_UNISTD_H
#if HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif
+#ifdef HAVE_SYS_TIME_H
+#include <sys/time.h>
+#endif
#include "ext2_fs.h"
#include "ext2fsP.h"
#endif
}
+#ifdef BMAP_STATS_OPS
+#define INC_STAT(map, name) map->stats.name
+#else
+#define INC_STAT(map, name) ;;
+#endif
+
errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
int type, __u64 start, __u64 end,
{
ext2fs_generic_bitmap bitmap;
struct ext2_bitmap_ops *ops;
+ ext2_ino_t num_dirs;
errcode_t retval;
+ if (!type)
+ type = EXT2FS_BMAP64_BITARRAY;
+
switch (type) {
case EXT2FS_BMAP64_BITARRAY:
ops = &ext2fs_blkmap64_bitarray;
break;
+ case EXT2FS_BMAP64_RBTREE:
+ ops = &ext2fs_blkmap64_rbtree;
+ break;
+ case EXT2FS_BMAP64_AUTODIR:
+ retval = ext2fs_get_num_dirs(fs, &num_dirs);
+ if (retval || num_dirs > (fs->super->s_inodes_count / 320))
+ ops = &ext2fs_blkmap64_bitarray;
+ else
+ ops = &ext2fs_blkmap64_rbtree;
+ break;
default:
return EINVAL;
}
- retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
- &bitmap);
+ retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
+ &bitmap);
if (retval)
return retval;
+#ifdef BMAP_STATS
+ if (gettimeofday(&bitmap->stats.created,
+ (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return 1;
+ }
+ bitmap->stats.type = type;
+#endif
+
/* XXX factor out, repeated in copy_bmap */
bitmap->magic = magic;
bitmap->fs = fs;
bitmap->end = end;
bitmap->real_end = real_end;
bitmap->bitmap_ops = ops;
+ bitmap->cluster_bits = 0;
switch (magic) {
case EXT2_ET_MAGIC_INODE_BITMAP64:
bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
break;
case EXT2_ET_MAGIC_BLOCK_BITMAP64:
bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
+ bitmap->cluster_bits = fs->cluster_ratio_bits;
break;
default:
bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
if (retval) {
- ext2fs_free_mem(&bitmap);
ext2fs_free_mem(&bitmap->description);
+ ext2fs_free_mem(&bitmap);
return retval;
}
return 0;
}
+#ifdef BMAP_STATS
+void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2_bmap_statistics *stats = &bitmap->stats;
+ float mark_seq_perc = 0.0, test_seq_perc = 0.0;
+ float mark_back_perc = 0.0, test_back_perc = 0.0;
+ double inuse;
+ struct timeval now;
+
+#ifdef BMAP_STATS_OPS
+ if (stats->test_count) {
+ test_seq_perc = ((float)stats->test_seq /
+ stats->test_count) * 100;
+ test_back_perc = ((float)stats->test_back /
+ stats->test_count) * 100;
+ }
+
+ if (stats->mark_count) {
+ mark_seq_perc = ((float)stats->mark_seq /
+ stats->mark_count) * 100;
+ mark_back_perc = ((float)stats->mark_back /
+ stats->mark_count) * 100;
+ }
+#endif
+
+ if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return;
+ }
+
+ inuse = (double) now.tv_sec + \
+ (((double) now.tv_usec) * 0.000001);
+ inuse -= (double) stats->created.tv_sec + \
+ (((double) stats->created.tv_usec) * 0.000001);
+
+ fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
+ stats->type);
+ fprintf(stderr, "=================================================\n");
+#ifdef BMAP_STATS_OPS
+ fprintf(stderr, "%16llu bits long\n",
+ bitmap->real_end - bitmap->start);
+ fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
+ stats->copy_count, stats->resize_count);
+ fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
+ stats->mark_count, stats->unmark_count);
+ fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
+ stats->test_count, stats->mark_ext_count);
+ fprintf(stderr, "%16lu unmark_bmap_extent\n"
+ "%16lu test_clear_bmap_extent\n",
+ stats->unmark_ext_count, stats->test_ext_count);
+ fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
+ stats->set_range_count, stats->get_range_count);
+ fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
+ stats->clear_count, stats->test_seq, test_seq_perc);
+ fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
+ "%16llu bits tested backwards (%.2f%%)\n",
+ stats->mark_seq, mark_seq_perc,
+ stats->test_back, test_back_perc);
+ fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
+ "%16.2f seconds in use\n",
+ stats->mark_back, mark_back_perc, inuse);
+#endif /* BMAP_STATS_OPS */
+}
+#endif
+
void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
{
if (!bmap)
return;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- ext2fs_free_generic_bitmap((ext2fs_generic_bitmap) bmap);
+ ext2fs_free_generic_bitmap(bmap);
return;
}
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+#ifdef BMAP_STATS
+ if (getenv("E2FSPROGS_BITMAP_STATS")) {
+ ext2fs_print_bmap_statistics(bmap);
+ bmap->bitmap_ops->print_stats(bmap);
+ }
+#endif
+
bmap->bitmap_ops->free_bmap(bmap);
if (bmap->description) {
bmap->description = 0;
}
bmap->magic = 0;
+ ext2fs_free_mem(&bmap);
}
errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
return EINVAL;
if (EXT2FS_IS_32_BITMAP(src))
- return ext2fs_copy_generic_bitmap((ext2fs_generic_bitmap) src,
- (ext2fs_generic_bitmap *) dest);
+ return ext2fs_copy_generic_bitmap(src, dest);
if (!EXT2FS_IS_64_BITMAP(src))
return EINVAL;
/* Allocate a new bitmap struct */
- retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
- &new_bmap);
+ retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
+ &new_bmap);
if (retval)
return retval;
+
+#ifdef BMAP_STATS_OPS
+ src->stats.copy_count++;
+#endif
+#ifdef BMAP_STATS
+ if (gettimeofday(&new_bmap->stats.created,
+ (struct timezone *) NULL) == -1) {
+ perror("gettimeofday");
+ return 1;
+ }
+ new_bmap->stats.type = src->stats.type;
+#endif
+
/* Copy all the high-level parts over */
new_bmap->magic = src->magic;
new_bmap->fs = src->fs;
new_bmap->real_end = src->real_end;
new_bmap->bitmap_ops = src->bitmap_ops;
new_bmap->base_error_code = src->base_error_code;
+ new_bmap->cluster_bits = src->cluster_bits;
descr = src->description;
if (descr) {
- retval = ext2fs_get_mem(strlen(descr)+1, &new_descr);
+ retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
if (retval) {
ext2fs_free_mem(&new_bmap);
return retval;
}
- strcpy(new_descr, descr);
+ sprintf(new_descr, "copy of %s", descr);
new_bmap->description = new_descr;
}
if (!bmap)
return EINVAL;
- if (EXT2FS_IS_32_BITMAP(bmap)) {
- return ext2fs_resize_generic_bitmap(bmap->magic,
- new_end, new_real_end,
- (ext2fs_generic_bitmap) bmap);
- }
+ if (EXT2FS_IS_32_BITMAP(bmap))
+ return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
+ new_real_end, bmap);
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, resize_count);
+
return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
}
ext2_ino_t tmp_oend;
int retval;
- retval = ext2fs_fudge_generic_bitmap_end((ext2fs_generic_bitmap) bitmap,
- bitmap->magic, neq,
- end, &tmp_oend);
+ retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
+ neq, end, &tmp_oend);
if (oend)
*oend = tmp_oend;
return retval;
if (!bitmap)
return EINVAL;
- if (EXT2FS_IS_32_BITMAP(bitmap)) {
- return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap)
- bitmap);
-
- }
+ if (EXT2FS_IS_32_BITMAP(bitmap))
+ return ext2fs_get_generic_bitmap_start(bitmap);
if (!EXT2FS_IS_64_BITMAP(bitmap))
return EINVAL;
if (!bitmap)
return EINVAL;
- if (EXT2FS_IS_32_BITMAP(bitmap)) {
- return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap)
- bitmap);
-
- }
+ if (EXT2FS_IS_32_BITMAP(bitmap))
+ return ext2fs_get_generic_bitmap_end(bitmap);
if (!EXT2FS_IS_64_BITMAP(bitmap))
return EINVAL;
void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
{
- if (EXT2FS_IS_32_BITMAP(bitmap)) {
- ext2fs_clear_generic_bitmap((ext2fs_generic_bitmap) bitmap);
- return;
- }
-
- bitmap->bitmap_ops->clear_bmap (bitmap);
+ if (EXT2FS_IS_32_BITMAP(bitmap))
+ ext2fs_clear_generic_bitmap(bitmap);
+ else
+ bitmap->bitmap_ops->clear_bmap (bitmap);
}
int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
if (EXT2FS_IS_32_BITMAP(bitmap)) {
if (arg & ~0xffffffffULL) {
- ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap,
+ ext2fs_warn_bitmap2(bitmap,
EXT2FS_MARK_ERROR, 0xffffffff);
return 0;
}
- return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap)
- bitmap, arg);
+ return ext2fs_mark_generic_bitmap(bitmap, arg);
}
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+ arg >>= bitmap->cluster_bits;
+
+#ifdef BMAP_STATS_OPS
+ if (arg == bitmap->stats.last_marked + 1)
+ bitmap->stats.mark_seq++;
+ if (arg < bitmap->stats.last_marked)
+ bitmap->stats.mark_back++;
+ bitmap->stats.last_marked = arg;
+ bitmap->stats.mark_count++;
+#endif
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
return 0;
if (EXT2FS_IS_32_BITMAP(bitmap)) {
if (arg & ~0xffffffffULL) {
- ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap,
- EXT2FS_UNMARK_ERROR, 0xffffffff);
+ ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
+ 0xffffffff);
return 0;
}
- return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap)
- bitmap, arg);
+ return ext2fs_unmark_generic_bitmap(bitmap, arg);
}
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+ arg >>= bitmap->cluster_bits;
+
+ INC_STAT(bitmap, unmark_count);
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
return 0;
if (EXT2FS_IS_32_BITMAP(bitmap)) {
if (arg & ~0xffffffffULL) {
- ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap,
- EXT2FS_TEST_ERROR, 0xffffffff);
+ ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
+ 0xffffffff);
return 0;
}
- return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap)
- bitmap, arg);
+ return ext2fs_test_generic_bitmap(bitmap, arg);
}
if (!EXT2FS_IS_64_BITMAP(bitmap))
return 0;
+ arg >>= bitmap->cluster_bits;
+
+#ifdef BMAP_STATS_OPS
+ bitmap->stats.test_count++;
+ if (arg == bitmap->stats.last_tested + 1)
+ bitmap->stats.test_seq++;
+ if (arg < bitmap->stats.last_tested)
+ bitmap->stats.test_back++;
+ bitmap->stats.last_tested = arg;
+#endif
+
if ((arg < bitmap->start) || (arg > bitmap->end)) {
warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
return 0;
return EINVAL;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- if ((start+num) & ~0xffffffffULL) {
- ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
- EXT2FS_UNMARK_ERROR, 0xffffffff);
+ if ((start+num-1) & ~0xffffffffULL) {
+ ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
+ 0xffffffff);
return EINVAL;
}
- return ext2fs_set_generic_bitmap_range((ext2fs_generic_bitmap) bmap,
- bmap->magic, start, num,
- in);
+ return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
+ start, num, in);
}
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, set_range_count);
+
return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
}
return EINVAL;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- if ((start+num) & ~0xffffffffULL) {
- ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
+ if ((start+num-1) & ~0xffffffffULL) {
+ ext2fs_warn_bitmap2(bmap,
EXT2FS_UNMARK_ERROR, 0xffffffff);
return EINVAL;
}
- return ext2fs_get_generic_bitmap_range((ext2fs_generic_bitmap) bmap,
- bmap->magic, start, num,
- out);
+ return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
+ start, num, out);
}
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, get_range_count);
+
return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
}
/* Now we know both bitmaps have the same magic */
if (EXT2FS_IS_32_BITMAP(bm1))
- return ext2fs_compare_generic_bitmap(bm1->magic, neq,
- (ext2fs_generic_bitmap) bm1,
- (ext2fs_generic_bitmap) bm2);
+ return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
if (!EXT2FS_IS_64_BITMAP(bm1))
return EINVAL;
__u64 start, num;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- ext2fs_set_generic_bitmap_padding((ext2fs_generic_bitmap) bmap);
+ ext2fs_set_generic_bitmap_padding(bmap);
return;
}
bmap, block);
if (EXT2FS_IS_32_BITMAP(bmap)) {
- if ((block+num) & ~0xffffffffULL) {
+ if ((block+num-1) & ~0xffffffffULL) {
ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
EXT2FS_UNMARK_ERROR, 0xffffffff);
return EINVAL;
if (!EXT2FS_IS_64_BITMAP(bmap))
return EINVAL;
+ INC_STAT(bmap, test_ext_count);
+
return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
}
return;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- if ((block+num) & ~0xffffffffULL) {
+ if ((block+num-1) & ~0xffffffffULL) {
ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
EXT2FS_UNMARK_ERROR, 0xffffffff);
return;
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+ INC_STAT(bmap, mark_ext_count);
+
if ((block < bmap->start) || (block+num-1 > bmap->end)) {
ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
bmap->description);
return;
if (EXT2FS_IS_32_BITMAP(bmap)) {
- if ((block+num) & ~0xffffffffULL) {
+ if ((block+num-1) & ~0xffffffffULL) {
ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
EXT2FS_UNMARK_ERROR, 0xffffffff);
return;
if (!EXT2FS_IS_64_BITMAP(bmap))
return;
+ INC_STAT(bmap, unmark_ext_count);
+
if ((block < bmap->start) || (block+num-1 > bmap->end)) {
ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
bmap->description);
bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
}
-int ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
+void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
{
#ifndef OMIT_COM_ERR
if (bitmap && bitmap->description)
"called %s with 64-bit bitmap", func);
#endif
}
+
+errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
+ ext2fs_block_bitmap *bitmap)
+{
+ ext2fs_block_bitmap cmap, bmap;
+ errcode_t retval;
+ blk64_t i, b_end, c_end;
+ int n, ratio;
+
+ bmap = *bitmap;
+
+ if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
+ return 0; /* Nothing to do */
+
+ retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
+ &cmap);
+ if (retval)
+ return retval;
+
+ i = bmap->start;
+ b_end = bmap->end;
+ bmap->end = bmap->real_end;
+ c_end = cmap->end;
+ cmap->end = cmap->real_end;
+ n = 0;
+ ratio = 1 << fs->cluster_ratio_bits;
+ while (i < bmap->real_end) {
+ if (ext2fs_test_block_bitmap2(bmap, i)) {
+ ext2fs_mark_block_bitmap2(cmap, i);
+ i += ratio - n;
+ n = 0;
+ continue;
+ }
+ i++; n++;
+ if (n >= ratio)
+ n = 0;
+ }
+ bmap->end = b_end;
+ cmap->end = c_end;
+ ext2fs_free_block_bitmap(bmap);
+ *bitmap = cmap;
+ return 0;
+}