From 69365c689b7164014e539b40ef62fc8eb804a05c Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sat, 22 Aug 2009 13:27:40 -0400 Subject: [PATCH] Add support for 64-bit bitmaps Initial design was done by Theodore Ts'o; implementation was fleshed out by Valerie Aurora Henson. Also includes some fixes from Nick Dokos. Signed-off-by: "Theodore Ts'o" Signed-off-by: Valerie Aurora Henson Signed-off-by: Nick Dokos --- lib/ext2fs/Makefile.in | 4 + lib/ext2fs/bitops.h | 191 +++++++++++++++- lib/ext2fs/blkmap64_ba.c | 327 ++++++++++++++++++++++++++ lib/ext2fs/bmap64.h | 61 +++++ lib/ext2fs/ext2_err.et.in | 12 +- lib/ext2fs/ext2fs.h | 1 + lib/ext2fs/ext2fsP.h | 36 +++ lib/ext2fs/gen_bitmap.c | 6 +- lib/ext2fs/gen_bitmap64.c | 567 ++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 1195 insertions(+), 10 deletions(-) create mode 100644 lib/ext2fs/blkmap64_ba.c create mode 100644 lib/ext2fs/bmap64.h create mode 100644 lib/ext2fs/gen_bitmap64.c diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in index 354b407..d6ba05b 100644 --- a/lib/ext2fs/Makefile.in +++ b/lib/ext2fs/Makefile.in @@ -27,6 +27,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \ bb_inode.o \ bitmaps.o \ bitops.o \ + blkmap64_ba.o \ blknum.o \ block.o \ bmap.o \ @@ -46,6 +47,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \ flushb.o \ freefs.o \ gen_bitmap.o \ + gen_bitmap64.o \ get_pathname.o \ getsize.o \ getsectsize.o \ @@ -87,6 +89,7 @@ SRCS= ext2_err.c \ $(srcdir)/bb_inode.c \ $(srcdir)/bitmaps.c \ $(srcdir)/bitops.c \ + $(srcdir)/blkmap64_ba.o \ $(srcdir)/block.c \ $(srcdir)/bmap.c \ $(srcdir)/check_desc.c \ @@ -107,6 +110,7 @@ SRCS= ext2_err.c \ $(srcdir)/flushb.c \ $(srcdir)/freefs.c \ $(srcdir)/gen_bitmap.c \ + $(srcdir)/gen_bitmap64.c \ $(srcdir)/get_pathname.c \ $(srcdir)/getsize.c \ $(srcdir)/getsectsize.c \ diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h index 7c3f056..e727139 100644 --- a/lib/ext2fs/bitops.h +++ b/lib/ext2fs/bitops.h @@ -111,7 +111,7 @@ extern int ext2fs_fast_test_block_bitmap_range(ext2fs_block_bitmap bitmap, blk_t block, int num); extern void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map); -/* These routines moved to gen_bitmap.c */ +/* These routines moved to gen_bitmap.c (actually, some of the above, too) */ extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, __u32 bitno); extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, @@ -123,6 +123,72 @@ extern int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, extern __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap); extern __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap); +/* 64-bit versions */ + +extern int ext2fs_mark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); +extern int ext2fs_unmark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); +extern int ext2fs_test_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); + +extern int ext2fs_mark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); +extern int ext2fs_unmark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); +extern int ext2fs_test_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); + +extern void ext2fs_fast_mark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); +extern void ext2fs_fast_unmark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); +extern int ext2fs_fast_test_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block); + +extern void ext2fs_fast_mark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); +extern void ext2fs_fast_unmark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); +extern int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode); +extern blk64_t ext2fs_get_block_bitmap_start2(ext2fs_block_bitmap bitmap); +extern ext2_ino_t ext2fs_get_inode_bitmap_start2(ext2fs_inode_bitmap bitmap); +extern blk64_t ext2fs_get_block_bitmap_end2(ext2fs_block_bitmap bitmap); +extern ext2_ino_t ext2fs_get_inode_bitmap_end2(ext2fs_inode_bitmap bitmap); + +extern int ext2fs_fast_test_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num); +extern void ext2fs_fast_mark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num); +extern void ext2fs_fast_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num); +/* These routines moved to gen_bitmap64.c */ +extern void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap); +extern errcode_t ext2fs_compare_generic_bmap(errcode_t neq, + ext2fs_generic_bitmap bm1, + ext2fs_generic_bitmap bm2); +extern void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap); +extern int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, + blk64_t bitno); +extern int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, + blk64_t bitno); +extern int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, + blk64_t bitno); +extern int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, unsigned int num); +extern __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap); +extern __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap); +extern int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, unsigned int num); +extern void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, unsigned int num); +extern void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, unsigned int num); + /* * The inline routines themselves... * @@ -445,6 +511,129 @@ _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, { ext2fs_unmark_block_bitmap_range(bitmap, block, num); } + +/* 64-bit versions */ + +_INLINE_ int ext2fs_mark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + return ext2fs_mark_generic_bmap((ext2fs_generic_bitmap) bitmap, + block); +} + +_INLINE_ int ext2fs_unmark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + return ext2fs_unmark_generic_bmap((ext2fs_generic_bitmap) bitmap, block); +} + +_INLINE_ int ext2fs_test_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + return ext2fs_test_generic_bmap((ext2fs_generic_bitmap) bitmap, + block); +} + +_INLINE_ int ext2fs_mark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + return ext2fs_mark_generic_bmap((ext2fs_generic_bitmap) bitmap, + inode); +} + +_INLINE_ int ext2fs_unmark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + return ext2fs_unmark_generic_bmap((ext2fs_generic_bitmap) bitmap, + inode); +} + +_INLINE_ int ext2fs_test_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + return ext2fs_test_generic_bmap((ext2fs_generic_bitmap) bitmap, + inode); +} + +_INLINE_ void ext2fs_fast_mark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + ext2fs_mark_generic_bmap((ext2fs_generic_bitmap) bitmap, block); +} + +_INLINE_ void ext2fs_fast_unmark_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + ext2fs_unmark_generic_bmap((ext2fs_generic_bitmap) bitmap, block); +} + +_INLINE_ int ext2fs_fast_test_block_bitmap2(ext2fs_block_bitmap bitmap, + blk64_t block) +{ + return ext2fs_test_generic_bmap((ext2fs_generic_bitmap) bitmap, + block); +} + +_INLINE_ void ext2fs_fast_mark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + ext2fs_mark_generic_bmap((ext2fs_generic_bitmap) bitmap, inode); +} + +_INLINE_ void ext2fs_fast_unmark_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + ext2fs_unmark_generic_bmap((ext2fs_generic_bitmap) bitmap, inode); +} + +_INLINE_ int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap, + ext2_ino_t inode) +{ + return ext2fs_test_generic_bmap((ext2fs_generic_bitmap) bitmap, + inode); +} + +_INLINE_ blk64_t ext2fs_get_block_bitmap_start2(ext2fs_block_bitmap bitmap) +{ + return ext2fs_get_generic_bmap_start((ext2fs_generic_bitmap) bitmap); +} + +_INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_start2(ext2fs_inode_bitmap bitmap) +{ + return ext2fs_get_generic_bmap_start((ext2fs_generic_bitmap) bitmap); +} + +_INLINE_ blk64_t ext2fs_get_block_bitmap_end2(ext2fs_block_bitmap bitmap) +{ + return ext2fs_get_generic_bmap_end((ext2fs_generic_bitmap) bitmap); +} + +_INLINE_ ext2_ino_t ext2fs_get_inode_bitmap_end2(ext2fs_inode_bitmap bitmap) +{ + return ext2fs_get_generic_bmap_end((ext2fs_generic_bitmap) bitmap); +} + +_INLINE_ int ext2fs_fast_test_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num) +{ + return ext2fs_test_block_bitmap_range2(bitmap, block, num); +} + +_INLINE_ void ext2fs_fast_mark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num) +{ + ext2fs_mark_block_bitmap_range2(bitmap, block, num); +} + +_INLINE_ void ext2fs_fast_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap, + blk64_t block, + unsigned int num) +{ + ext2fs_unmark_block_bitmap_range2(bitmap, block, num); +} + #undef _INLINE_ #endif diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c new file mode 100644 index 0000000..395aba9 --- /dev/null +++ b/lib/ext2fs/blkmap64_ba.c @@ -0,0 +1,327 @@ +/* + * blkmap64_ba.c --- Simple bitarray implementation for bitmaps + * + * Copyright (C) 2008 Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#include +#include +#if HAVE_UNISTD_H +#include +#endif +#include +#include +#if HAVE_SYS_STAT_H +#include +#endif +#if HAVE_SYS_TYPES_H +#include +#endif + +#include "ext2_fs.h" +#include "ext2fsP.h" +#include "bmap64.h" + +/* + * Private data for bit array implementation of bitmap ops. + * Currently, this is just a pointer to our big flat hunk of memory, + * exactly equivalent to the old-skool char * bitmap member. + */ + +struct ext2fs_ba_private_struct { + char *bitarray; +}; + +typedef struct ext2fs_ba_private_struct *ext2fs_ba_private; + +static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap) +{ + ext2fs_ba_private bp; + errcode_t retval; + size_t size; + + /* + * Since we only have the one pointer, we could just shove our + * private data in the void *private field itself, but then + * we'd have to do a fair bit of rewriting if we ever added a + * field. I'm agnostic. + */ + retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp); + if (retval) + return retval; + + size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); + + retval = ext2fs_get_mem(size, &bp->bitarray); + if (retval) { + ext2fs_free_mem(&bp); + bp = 0; + return retval; + } + bitmap->private = (void *) bp; + return 0; +} + +static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), + ext2fs_generic_bitmap bitmap) +{ + ext2fs_ba_private bp; + errcode_t retval; + size_t size; + + retval = ba_alloc_private_data (bitmap); + if (retval) + return retval; + + bp = (ext2fs_ba_private) bitmap->private; + size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); + memset(bp->bitarray, 0, size); + + return 0; +} + +static void ba_free_bmap(ext2fs_generic_bitmap bitmap) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + + if (!bp) + return; + + if (bp->bitarray) { + ext2fs_free_mem (&bp->bitarray); + bp->bitarray = 0; + } + ext2fs_free_mem (&bp); + bp = 0; +} + +static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src, + ext2fs_generic_bitmap dest) +{ + ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private; + ext2fs_ba_private dest_bp; + errcode_t retval; + size_t size; + + retval = ba_alloc_private_data (dest); + if (retval) + return retval; + + dest_bp = (ext2fs_ba_private) dest->private; + + size = (size_t) (((src->real_end - src->start) / 8) + 1); + memcpy (dest_bp->bitarray, src_bp->bitarray, size); + + return 0; +} + +static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap, + __u64 new_end, __u64 new_real_end) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private; + errcode_t retval; + size_t size, new_size; + __u64 bitno; + + /* + * If we're expanding the bitmap, make sure all of the new + * parts of the bitmap are zero. + */ + if (new_end > bmap->end) { + bitno = bmap->real_end; + if (bitno > new_end) + bitno = new_end; + for (; bitno > bmap->end; bitno--) + ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray); + } + if (new_real_end == bmap->real_end) { + bmap->end = new_end; + return 0; + } + + size = ((bmap->real_end - bmap->start) / 8) + 1; + new_size = ((new_real_end - bmap->start) / 8) + 1; + + if (size != new_size) { + retval = ext2fs_resize_mem(size, new_size, &bp->bitarray); + if (retval) + return retval; + } + if (new_size > size) + memset(bp->bitarray + size, 0, new_size - size); + + bmap->end = new_end; + bmap->real_end = new_real_end; + return 0; + +} + +static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + blk64_t bitno = (blk64_t) arg; + + return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray); +} + +static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + blk64_t bitno = (blk64_t) arg; + + return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray); +} + +static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + blk64_t bitno = (blk64_t) arg; + + return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray); +} + +static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, + unsigned int num) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + blk64_t bitno = (blk64_t) arg; + unsigned int i; + + for (i = 0; i < num; i++) + ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray); +} + +static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, + unsigned int num) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + blk64_t bitno = (blk64_t) arg; + unsigned int i; + + for (i = 0; i < num; i++) + ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray); +} + +static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, + __u64 start, unsigned int len) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + __u64 start_byte, len_byte = len >> 3; + unsigned int start_bit, len_bit = len % 8; + unsigned int first_bit = 0; + unsigned int last_bit = 0; + int mark_count = 0; + int mark_bit = 0; + int i; + const char *ADDR; + + ADDR = bp->bitarray; + start -= bitmap->start; + start_byte = start >> 3; + start_bit = start % 8; + + if (start_bit != 0) { + /* + * The compared start block number or start inode number + * is not the first bit in a byte. + */ + mark_count = 8 - start_bit; + if (len < 8 - start_bit) { + mark_count = (int)len; + mark_bit = len + start_bit - 1; + } else + mark_bit = 7; + + for (i = mark_count; i > 0; i--, mark_bit--) + first_bit |= 1 << mark_bit; + + /* + * Compare blocks or inodes in the first byte. + * If there is any marked bit, this function returns 0. + */ + if (first_bit & ADDR[start_byte]) + return 0; + else if (len <= 8 - start_bit) + return 1; + + start_byte++; + len_bit = (len - mark_count) % 8; + len_byte = (len - mark_count) >> 3; + } + + /* + * The compared start block number or start inode number is + * the first bit in a byte. + */ + if (len_bit != 0) { + /* + * The compared end block number or end inode number is + * not the last bit in a byte. + */ + for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) + last_bit |= 1 << mark_bit; + + /* + * Compare blocks or inodes in the last byte. + * If there is any marked bit, this function returns 0. + */ + if (last_bit & ADDR[start_byte + len_byte]) + return 0; + else if (len_byte == 0) + return 1; + } + + /* Check whether all bytes are 0 */ + return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); +} + + +static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap, + __u64 start, size_t num, void *in) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + + memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3); + + return 0; +} + +static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap, + __u64 start, size_t num, void *out) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + + memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3); + + return 0; +} + +static void ba_clear_bmap(ext2fs_generic_bitmap bitmap) +{ + ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; + + memset(bp->bitarray, 0, + (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); +} + +struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = { + .type = EXT2FS_BMAP64_BITARRAY, + .new_bmap = ba_new_bmap, + .free_bmap = ba_free_bmap, + .copy_bmap = ba_copy_bmap, + .resize_bmap = ba_resize_bmap, + .mark_bmap = ba_mark_bmap, + .unmark_bmap = ba_unmark_bmap, + .test_bmap = ba_test_bmap, + .test_clear_bmap_extent = ba_test_clear_bmap_extent, + .mark_bmap_extent = ba_mark_bmap_extent, + .unmark_bmap_extent = ba_unmark_bmap_extent, + .set_bmap_range = ba_set_bmap_range, + .get_bmap_range = ba_get_bmap_range, + .clear_bmap = ba_clear_bmap, +}; diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h new file mode 100644 index 0000000..b0aa84c --- /dev/null +++ b/lib/ext2fs/bmap64.h @@ -0,0 +1,61 @@ +/* + * bmap64.h --- 64-bit bitmap structure + * + * Copyright (C) 2007, 2008 Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +struct ext2fs_struct_generic_bitmap { + errcode_t magic; + ext2_filsys fs; + struct ext2_bitmap_ops *bitmap_ops; + int flags; + __u64 start, end; + __u64 real_end; + char *description; + void *private; + errcode_t base_error_code; +}; + +#define EXT2FS_IS_32_BITMAP(bmap) \ + (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || \ + ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP) || \ + ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP)) + +#define EXT2FS_IS_64_BITMAP(bmap) \ + (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP64) || \ + ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP64) || \ + ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP64)) + +struct ext2_bitmap_ops { + int type; + /* Generic bmap operators */ + errcode_t (*new_bmap)(ext2_filsys fs, ext2fs_generic_bitmap bmap); + void (*free_bmap)(ext2fs_generic_bitmap bitmap); + errcode_t (*copy_bmap)(ext2fs_generic_bitmap src, + ext2fs_generic_bitmap dest); + errcode_t (*resize_bmap)(ext2fs_generic_bitmap bitmap, + __u64 new_end, + __u64 new_real_end); + /* bit set/test operators */ + int (*mark_bmap)(ext2fs_generic_bitmap bitmap, __u64 arg); + int (*unmark_bmap)(ext2fs_generic_bitmap bitmap, __u64 arg); + int (*test_bmap)(ext2fs_generic_bitmap bitmap, __u64 arg); + void (*mark_bmap_extent)(ext2fs_generic_bitmap bitmap, __u64 arg, + unsigned int num); + void (*unmark_bmap_extent)(ext2fs_generic_bitmap bitmap, __u64 arg, + unsigned int num); + int (*test_clear_bmap_extent)(ext2fs_generic_bitmap bitmap, + __u64 arg, unsigned int num); + errcode_t (*set_bmap_range)(ext2fs_generic_bitmap bitmap, + __u64 start, size_t num, void *in); + errcode_t (*get_bmap_range)(ext2fs_generic_bitmap bitmap, + __u64 start, size_t num, void *out); + void (*clear_bmap)(ext2fs_generic_bitmap bitmap); +}; + +extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray; diff --git a/lib/ext2fs/ext2_err.et.in b/lib/ext2fs/ext2_err.et.in index 406f3ae..c73527f 100644 --- a/lib/ext2fs/ext2_err.et.in +++ b/lib/ext2fs/ext2_err.et.in @@ -335,14 +335,14 @@ ec EXT2_ET_RO_BLOCK_ITERATE, ec EXT2_ET_MAGIC_EXTENT_PATH, "Wrong magic number for ext4 extent saved path" -ec EXT2_ET_MAGIC_RESERVED_10, - "Wrong magic number --- RESERVED_10" +ec EXT2_ET_MAGIC_GENERIC_BITMAP64, + "Wrong magic number for 64-bit generic bitmap" -ec EXT2_ET_MAGIC_RESERVED_11, - "Wrong magic number --- RESERVED_11" +ec EXT2_ET_MAGIC_BLOCK_BITMAP64, + "Wrong magic number for 64-bit block bitmap" -ec EXT2_ET_MAGIC_RESERVED_12, - "Wrong magic number --- RESERVED_12" +ec EXT2_ET_MAGIC_INODE_BITMAP64, + "Wrong magic number for 64-bit inode bitmap" ec EXT2_ET_MAGIC_RESERVED_13, "Wrong magic number --- RESERVED_13" diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h index 5ebeaaf..b6649ba 100644 --- a/lib/ext2fs/ext2fs.h +++ b/lib/ext2fs/ext2fs.h @@ -173,6 +173,7 @@ typedef struct ext2_file *ext2_file_t; #define EXT2_FLAG_EXCLUSIVE 0x4000 #define EXT2_FLAG_SOFTSUPP_FEATURES 0x8000 #define EXT2_FLAG_NOFREE_ON_ERROR 0x10000 +#define EXT2_FLAG_64BITS 0x20000 /* * Special flag in the ext2 inode i_flag field that means that this is diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h index c666faa..2ec091e 100644 --- a/lib/ext2fs/ext2fsP.h +++ b/lib/ext2fs/ext2fsP.h @@ -86,3 +86,39 @@ extern int ext2fs_process_dir_block(ext2_filsys fs, void *priv_data); +/* + * 64-bit bitmap support + */ + +#define EXT2FS_BMAP64_BITARRAY 1 + +extern errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic, + int type, __u64 start, __u64 end, + __u64 real_end, + const char * description, + ext2fs_generic_bitmap *bmap); + +extern void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap); + +extern errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src, + ext2fs_generic_bitmap *dest); + +extern errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, + __u64 new_end, + __u64 new_real_end); +extern errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, + errcode_t neq, + __u64 end, __u64 *oend); +extern int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg); +extern int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg); +extern int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg); +extern errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bitmap, + __u64 start, unsigned int num, + void *in); +extern errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bitmap, + __u64 start, unsigned int num, + void *out); +extern int ext2fs_mem_is_zero(const char *mem, size_t len); diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c index 1f7d2c4..ed3afef 100644 --- a/lib/ext2fs/gen_bitmap.c +++ b/lib/ext2fs/gen_bitmap.c @@ -25,7 +25,7 @@ #endif #include "ext2_fs.h" -#include "ext2fs.h" +#include "ext2fsP.h" struct ext2fs_struct_generic_bitmap { errcode_t magic; @@ -331,7 +331,7 @@ errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap, * Compare @mem to zero buffer by 256 bytes. * Return 1 if @mem is zeroed memory, otherwise return 0. */ -static int mem_is_zero(const char *mem, size_t len) +int ext2fs_mem_is_zero(const char *mem, size_t len) { static const char zero_buf[256]; @@ -419,7 +419,7 @@ static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap, } /* Check whether all bytes are 0 */ - return mem_is_zero(ADDR + start_byte, len_byte); + return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); } int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c new file mode 100644 index 0000000..fb806a2 --- /dev/null +++ b/lib/ext2fs/gen_bitmap64.c @@ -0,0 +1,567 @@ +/* + * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and + * block bitmaps. + * + * Copyright (C) 2007, 2008 Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#include +#include +#if HAVE_UNISTD_H +#include +#endif +#include +#include +#include +#if HAVE_SYS_STAT_H +#include +#endif +#if HAVE_SYS_TYPES_H +#include +#endif + +#include "ext2_fs.h" +#include "ext2fsP.h" +#include "bmap64.h" + +/* + * Design of 64-bit bitmaps + * + * In order maintain ABI compatibility with programs that don't + * understand about 64-bit blocks/inodes, + * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap() + * will create old-style bitmaps unless the application passes the + * flag EXT2_FLAG_64BITS to ext2fs_open(). If this flag is + * passed, then we know the application has been recompiled, so we can + * use the new-style bitmaps. If it is not passed, we have to return + * an error if trying to open a filesystem which needs 64-bit bitmaps. + * + * The new bitmaps use a new set of structure magic numbers, so that + * both the old-style and new-style interfaces can identify which + * version of the data structure was used. Both the old-style and + * new-style interfaces will support either type of bitmap, although + * of course 64-bit operation will only be possible when both the + * new-style interface and the new-style bitmap are used. + * + * For example, the new bitmap interfaces will check the structure + * magic numbers and so will be able to detect old-stype bitmap. If + * they see an old-style bitmap, they will pass it to the gen_bitmap.c + * functions for handling. The same will be true for the old + * interfaces as well. + * + * The new-style interfaces will have several different back-end + * implementations, so we can support different encodings that are + * appropriate for different applications. In general the default + * should be whatever makes sense, and what the application/library + * will use. However, e2fsck may need specialized implementations for + * its own uses. For example, when doing parent directory pointer + * loop detections in pass 3, the bitmap will *always* be sparse, so + * e2fsck can request an encoding which is optimized for that. + */ + +static void warn_bitmap(ext2fs_generic_bitmap bitmap, + int code, __u64 arg) +{ +#ifndef OMIT_COM_ERR + if (bitmap->description) + com_err(0, bitmap->base_error_code+code, + "#%llu for %s", arg, bitmap->description); + else + com_err(0, bitmap->base_error_code + code, "#%llu", arg); +#endif +} + + +errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic, + int type, __u64 start, __u64 end, + __u64 real_end, + const char *descr, + ext2fs_generic_bitmap *ret) +{ + ext2fs_generic_bitmap bitmap; + struct ext2_bitmap_ops *ops; + errcode_t retval; + + switch (type) { + case EXT2FS_BMAP64_BITARRAY: + ops = &ext2fs_blkmap64_bitarray; + break; + default: + return EINVAL; + } + + retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), + &bitmap); + if (retval) + return retval; + + /* XXX factor out, repeated in copy_bmap */ + bitmap->magic = magic; + bitmap->fs = fs; + bitmap->start = start; + bitmap->end = end; + bitmap->real_end = real_end; + bitmap->bitmap_ops = ops; + 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; + break; + default: + bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; + } + if (descr) { + retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); + if (retval) { + ext2fs_free_mem(&bitmap); + return retval; + } + strcpy(bitmap->description, descr); + } else + bitmap->description = 0; + + retval = bitmap->bitmap_ops->new_bmap(fs, bitmap); + if (retval) { + ext2fs_free_mem(&bitmap); + ext2fs_free_mem(&bitmap->description); + return retval; + } + + *ret = bitmap; + return 0; +} + +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); + return; + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return; + + bmap->bitmap_ops->free_bmap(bmap); + + if (bmap->description) { + ext2fs_free_mem(&bmap->description); + bmap->description = 0; + } + bmap->magic = 0; +} + +errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src, + ext2fs_generic_bitmap *dest) +{ + char *descr, *new_descr; + ext2fs_generic_bitmap new_bmap; + errcode_t retval; + + if (!src) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(src)) + return ext2fs_copy_generic_bitmap((ext2fs_generic_bitmap) src, + (ext2fs_generic_bitmap *) 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); + if (retval) + return retval; + + /* Copy all the high-level parts over */ + new_bmap->magic = src->magic; + new_bmap->fs = src->fs; + new_bmap->start = src->start; + new_bmap->end = src->end; + new_bmap->real_end = src->real_end; + new_bmap->bitmap_ops = src->bitmap_ops; + new_bmap->base_error_code = src->base_error_code; + + descr = src->description; + if (descr) { + retval = ext2fs_get_mem(strlen(descr)+1, &new_descr); + if (retval) { + ext2fs_free_mem(&new_bmap); + return retval; + } + strcpy(new_descr, descr); + new_bmap->description = new_descr; + } + + retval = src->bitmap_ops->copy_bmap(src, new_bmap); + if (retval) { + ext2fs_free_mem(&new_bmap->description); + ext2fs_free_mem(&new_bmap); + return retval; + } + + *dest = new_bmap; + + return 0; +} + +errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, + __u64 new_end, + __u64 new_real_end) +{ + 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_64_BITMAP(bmap)) + return EINVAL; + + return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); +} + +errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, + errcode_t neq, + __u64 end, __u64 *oend) +{ + if (!bitmap) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + ext2_ino_t tmp_oend; + int retval; + + retval = ext2fs_fudge_generic_bitmap_end((ext2fs_generic_bitmap) bitmap, + bitmap->magic, neq, + end, &tmp_oend); + if (oend) + *oend = tmp_oend; + return retval; + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return EINVAL; + + if (end > bitmap->real_end) + return neq; + if (oend) + *oend = bitmap->end; + bitmap->end = end; + return 0; +} + +__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap) +{ + if (!bitmap) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + return ext2fs_get_generic_bitmap_start((ext2fs_generic_bitmap) + bitmap); + + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return EINVAL; + + return bitmap->start; +} + +__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap) +{ + if (!bitmap) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + return ext2fs_get_generic_bitmap_end((ext2fs_generic_bitmap) + bitmap); + + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return EINVAL; + + return bitmap->end; +} + +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); +} + +int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg) +{ + if (!bitmap) + return 0; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + if (arg & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap, + EXT2FS_MARK_ERROR, 0xffffffff); + return 0; + } + return ext2fs_mark_generic_bitmap((ext2fs_generic_bitmap) + bitmap, arg); + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return 0; + + if ((arg < bitmap->start) || (arg > bitmap->end)) { + warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); + return 0; + } + + return bitmap->bitmap_ops->mark_bmap(bitmap, arg); +} + +int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg) +{ + if (!bitmap) + return 0; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + if (arg & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return 0; + } + return ext2fs_unmark_generic_bitmap((ext2fs_generic_bitmap) + bitmap, arg); + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return 0; + + if ((arg < bitmap->start) || (arg > bitmap->end)) { + warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); + return 0; + } + + return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); +} + +int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, + __u64 arg) +{ + if (!bitmap) + return 0; + + if (EXT2FS_IS_32_BITMAP(bitmap)) { + if (arg & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bitmap, + EXT2FS_TEST_ERROR, 0xffffffff); + return 0; + } + return ext2fs_test_generic_bitmap((ext2fs_generic_bitmap) + bitmap, arg); + } + + if (!EXT2FS_IS_64_BITMAP(bitmap)) + return 0; + + if ((arg < bitmap->start) || (arg > bitmap->end)) { + warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); + return 0; + } + + return bitmap->bitmap_ops->test_bmap(bitmap, arg); +} + +errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap, + __u64 start, unsigned int num, + void *in) +{ + if (!bmap) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(bmap)) { + if ((start+num) & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return EINVAL; + } + return ext2fs_set_generic_bitmap_range((ext2fs_generic_bitmap) bmap, + bmap->magic, start, num, + in); + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return EINVAL; + + return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); +} + +errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap, + __u64 start, unsigned int num, + void *out) +{ + if (!bmap) + return EINVAL; + + if (EXT2FS_IS_32_BITMAP(bmap)) { + if ((start+num) & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return EINVAL; + } + return ext2fs_get_generic_bitmap_range((ext2fs_generic_bitmap) bmap, + bmap->magic, start, num, + out); + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return EINVAL; + + return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); +} + +errcode_t ext2fs_compare_generic_bmap(errcode_t neq, + ext2fs_generic_bitmap bm1, + ext2fs_generic_bitmap bm2) +{ + blk64_t i; + + if (!bm1 || !bm2) + return EINVAL; + if (bm1->magic != bm2->magic) + return EINVAL; + + /* 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); + + if (!EXT2FS_IS_64_BITMAP(bm1)) + return EINVAL; + + if ((bm1->start != bm2->start) || + (bm1->end != bm2->end)) + return neq; + + for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) + if (ext2fs_test_generic_bmap(bm1, i) != + ext2fs_test_generic_bmap(bm2, i)) + return neq; + + return 0; +} + +void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap) +{ + __u64 start, num; + + if (EXT2FS_IS_32_BITMAP(bmap)) { + ext2fs_set_generic_bitmap_padding((ext2fs_generic_bitmap) bmap); + return; + } + + start = bmap->end + 1; + num = bmap->real_end - bmap->end; + bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); + /* XXX ought to warn on error */ +} + +int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap, + blk64_t block, unsigned int num) +{ + if (!bmap) + return EINVAL; + + if (num == 1) + return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) + bmap, block); + + if (EXT2FS_IS_32_BITMAP(bmap)) { + if ((block+num) & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return EINVAL; + } + return ext2fs_test_block_bitmap_range( + (ext2fs_generic_bitmap) bmap, block, num); + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return EINVAL; + + return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); +} + +void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap, + blk64_t block, unsigned int num) +{ + if (!bmap) + return; + + if (EXT2FS_IS_32_BITMAP(bmap)) { + if ((block+num) & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return; + } + ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, + block, num); + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return; + + if ((block < bmap->start) || (block+num-1 > bmap->end)) { + ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, + bmap->description); + return; + } + + bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); +} + +void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap, + blk64_t block, unsigned int num) +{ + if (!bmap) + return; + + if (EXT2FS_IS_32_BITMAP(bmap)) { + if ((block+num) & ~0xffffffffULL) { + ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, + EXT2FS_UNMARK_ERROR, 0xffffffff); + return; + } + ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, + block, num); + } + + if (!EXT2FS_IS_64_BITMAP(bmap)) + return; + + if ((block < bmap->start) || (block+num-1 > bmap->end)) { + ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, + bmap->description); + return; + } + + bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); +} -- 1.8.3.1