new bitmaps interface in e2fsprogs

RFC PATCH In review Valerie Clement 2 participants 2 messages Jun 21, 2007

lore

Share & tools

lore

Valerie Clement

author

2007-06-21 15:55 UTC #0 lore raw

RFC PATCH 5/11 new bitmaps interface in e2fsprogs

This patch introduces new bitmap interface for ext4 filesystems which uses the new type blk64_t.

 bitmaps.c |  156 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 bitops.c  |   36 ++++++++++++++
 bitops.h  |   29 +++++++++++
 ext2fs.h  |   25 +++++++++
 4 files changed, 231 insertions(+), 15 deletions(-)

lib/ext2fs/ext2fs.h +25 -0

Index: e2fsprogs-1.39-tyt3-v7/lib/ext2fs/ext2fs.h
===================================================================
@@ -112,13 +112,30 @@ struct ext2fs_struct_generic_bitmap {
 	__u32		reserved[7];
 };
 
+struct ext4fs_struct_generic_bitmap {
+	errcode_t	magic;
+	ext2_filsys 	fs;
+	blk64_t		start, end;
+	blk64_t		real_end;
+	char	*	description;
+	char	*	bitmap;
+	errcode_t	base_error_code;
+	__u32		reserved[7];
+};
+
 #define EXT2FS_MARK_ERROR 	0
 #define EXT2FS_UNMARK_ERROR 	1
 #define EXT2FS_TEST_ERROR	2
 
+#ifdef _EXT4FS_
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_generic_bitmap;
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_inode_bitmap;
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_block_bitmap;
+#else
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_generic_bitmap;
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_inode_bitmap;
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_block_bitmap;
+#endif
 
 #define EXT2_FIRST_INODE(s)	EXT2_FIRST_INO(s)

@@ -580,11 +597,19 @@ extern errcode_t ext2fs_write_inode_bitm
 extern errcode_t ext2fs_write_block_bitmap (ext2_filsys fs);
 extern errcode_t ext2fs_read_inode_bitmap (ext2_filsys fs);
 extern errcode_t ext2fs_read_block_bitmap(ext2_filsys fs);
+#ifndef _EXT4FS_
 extern errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
 						__u32 end,
 						__u32 real_end,
 						const char *descr,
 						ext2fs_generic_bitmap *ret);
+#else
+extern errcode_t ext2fs_allocate_generic_bitmap(blk64_t start,
+						blk64_t end,
+						blk64_t real_end,
+						const char *descr,
+						ext2fs_generic_bitmap *ret);
+#endif
 extern errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
 					      const char *descr,
 					      ext2fs_block_bitmap *ret);

lib/ext2fs/bitmaps.c +142 ~~-14~~

208 lines not on this page · raw message

lib/ext2fs/bitops.c +36 -0

Index: e2fsprogs-1.39-tyt3-v7/lib/ext2fs/bitops.c
===================================================================
@@ -30,6 +30,7 @@
  * systems, as well as non-32 bit systems.
  */
 
+#ifndef _EXT4FS_
 int ext2fs_set_bit(unsigned int nr,void * addr)
 {
 	int		mask, retval;

@@ -63,6 +64,41 @@ int ext2fs_test_bit(unsigned int nr, con
 	mask = 1 << (nr & 0x07);
 	return (mask & *ADDR);
 }
+#else
+int ext2fs_set_bit(blk64_t nr,void * addr)
+{
+	int		mask, retval;
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	retval = mask & *ADDR;
+	*ADDR |= mask;
+	return retval;
+}
+
+int ext2fs_clear_bit(blk64_t nr, void * addr)
+{
+	int		mask, retval;
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	retval = mask & *ADDR;
+	*ADDR &= ~mask;
+	return retval;
+}
+
+int ext2fs_test_bit(blk64_t nr, const void * addr)
+{
+	int			mask;
+	const unsigned char	*ADDR = (const unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	return (mask & *ADDR);
+}
+#endif
 
 #endif	/* !_EXT2_HAVE_ASM_BITOPS_ */

lib/ext2fs/bitops.h +28 -1

Index: e2fsprogs-1.39-tyt3-v7/lib/ext2fs/bitops.h
===================================================================
@@ -14,11 +14,19 @@
  */
 
 
+#ifndef _EXT4FS_
 extern int ext2fs_set_bit(unsigned int nr,void * addr);
 extern int ext2fs_clear_bit(unsigned int nr, void * addr);
 extern int ext2fs_test_bit(unsigned int nr, const void * addr);
 extern void ext2fs_fast_set_bit(unsigned int nr,void * addr);
 extern void ext2fs_fast_clear_bit(unsigned int nr, void * addr);
+#else
+extern int ext2fs_set_bit(blk64_t nr,void * addr);
+extern int ext2fs_clear_bit(blk64_t nr, void * addr);
+extern int ext2fs_test_bit(blk64_t nr, const void * addr);
+extern void ext2fs_fast_set_bit(blk64_t nr,void * addr);
+extern void ext2fs_fast_clear_bit(blk64_t nr, void * addr);
+#endif
 extern __u16 ext2fs_swab16(__u16 val);
 extern __u32 ext2fs_swab32(__u32 val);
 extern __u64 ext2fs_swab64(__u64 val);

@@ -141,6 +149,7 @@ extern int ext2fs_unmark_generic_bitmap(
  * previous bit value.
  */
 
+#ifndef _EXT4FS_
 _INLINE_ void ext2fs_fast_set_bit(unsigned int nr,void * addr)
 {
 	unsigned char	*ADDR = (unsigned char *) addr;

@@ -156,10 +165,28 @@ _INLINE_ void ext2fs_fast_clear_bit(unsi
 	ADDR += nr >> 3;
 	*ADDR &= ~(1 << (nr & 0x07));
 }
+#else
+_INLINE_ void ext2fs_fast_set_bit(blk64_t nr,void * addr)
+{
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	*ADDR |= (1 << (nr & 0x07));
+}
+
+_INLINE_ void ext2fs_fast_clear_bit(blk64_t nr, void * addr)
+{
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	*ADDR &= ~(1 << (nr & 0x07));
+}
+#endif
 
 
 #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \
-     (defined(__i386__) || defined(__i486__) || defined(__i586__)))
+     (defined(__i386__) || defined(__i486__) || defined(__i586__)) && \
+     !(defined(_EXT2_64BIT_BLK_T) && (SIZEOF_LONG == 4)))
 
 #define _EXT2_HAVE_ASM_BITOPS_
 #define _EXT2_HAVE_ASM_SWAB_

Note - most of these comments relate to making these changes compatible with existing e2fsprogs. I don't object to such patches for the short term to make 64-bit usable e2fsprogs, but I don't think they should go into the upstream e2fsprogs. I wonder if having _EXT4FS_ should force the .so version to be 2.0 or something, to make it clear if any applications are linking against it.

Quoted 14 lines · Valerie Clement

lib/ext2fs/ext2fs.h +11 -0

+struct ext4fs_struct_generic_bitmap {
+	errcode_t	magic;
+	ext2_filsys 	fs;
+	blk64_t		start, end;
+	blk64_t		real_end;
+	char	*	description;
+	char	*	bitmap;
+	errcode_t	base_error_code;
+	__u32		reserved[7];
+};
+
 #define EXT2FS_MARK_ERROR 	0
 #define EXT2FS_UNMARK_ERROR 	1
 #define EXT2FS_TEST_ERROR	2

lib/ext2fs/ext2fs.h struct ext2fs_struct_generic_bitmap { · line 138

Quoted 10 lines

lib/ext2fs/ext2fs.h +6 -0

 
+#ifdef _EXT4FS_
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_generic_bitmap;
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_inode_bitmap;
+typedef struct ext4fs_struct_generic_bitmap *ext2fs_block_bitmap;
+#else
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_generic_bitmap;
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_inode_bitmap;
 typedef struct ext2fs_struct_generic_bitmap *ext2fs_block_bitmap;
+#endif

Ideally, it would be good if we could hide the internals of the bitmap types, layouts, etc from the caller. Allocating several 2^48 bits bitmaps for a large filesystem is just not practical, so we may as well start taking steps toward fixing that.

Instead, we should keep a backward-compatible 32-bit interface to the bitmaps (using the same ext2fs_struct_generic_bitmap), and then use the magic to distinguish between 32-bit and 64-bit bitmaps. This implies that "#ifdef _EXT4FS_" would not be needed, and everything can be decided at runtime based on the size of the bitmap. Callers using the 32-bit interface could obviously only specify 2^32-bit bitmaps.

It might be initially OK to just keep the "array of bits" interface for simplicity but at some point in the (likely near) future we will want to move to an "extent" structure as Ted proposed, having an {offset, count} list of bits in a tree to manage bitmaps that are nearly full and nearly empty efficiently. It might make sense to have real bitmaps for fragmented parts of the tree where {offset, count} would be less efficient.

lib/ext2fs/ext2fs.h extern errcode_t ext2fs_write_inode_bitm · line 608

Quoted 13 lines

lib/ext2fs/ext2fs.h +7 -0

@@ -580,11 +597,19 @@ extern errcode_t ext2fs_write_inode_bitm
+#ifndef _EXT4FS_
 extern errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
 						__u32 end,
 						__u32 real_end,
 						const char *descr,
 						ext2fs_generic_bitmap *ret);
+#else
+extern errcode_t ext2fs_allocate_generic_bitmap(blk64_t start,
+						blk64_t end,
+						blk64_t real_end,
+						const char *descr,
+						ext2fs_generic_bitmap *ret);

This should become ext2fs_allocate_generic_bitmap_64(), and ext2fs_allocate_generic_bitmap().

lib/ext2fs/bitmaps.c errcode_t ext2fs_allocate_generic_bitmap · line 90

Quoted 4 lines

lib/ext2fs/bitmaps.c +4 -0

+void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map)
+{
+	/* Protect loop from wrap-around if map->real_end is maxed */
+	for (i=map->end+1, j = i - map->start;

Please, spaces around '=' and '+'.

Quoted 25 lines

lib/ext2fs/bitops.c +25 -0

+#else
+int ext2fs_set_bit(blk64_t nr,void * addr)
+{
+	int		mask, retval;
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	retval = mask & *ADDR;
+	*ADDR |= mask;
+	return retval;
+}
+
+int ext2fs_clear_bit(blk64_t nr, void * addr)
+{
+	int		mask, retval;
+	unsigned char	*ADDR = (unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	retval = mask & *ADDR;
+	*ADDR &= ~mask;
+	return retval;
+}
+

lib/ext2fs/bitops.c int ext2fs_test_bit(unsigned int nr, con · line 101

Quoted 10 lines

lib/ext2fs/bitops.c +10 -0

+int ext2fs_test_bit(blk64_t nr, const void * addr)
+{
+	int			mask;
+	const unsigned char	*ADDR = (const unsigned char *) addr;
+
+	ADDR += nr >> 3;
+	mask = 1 << (nr & 0x07);
+	return (mask & *ADDR);
+}
+#endif

These functions are almost all used only internally, so it should be acceptable to add ext2fs_test_bit_64(), use that everywhere in e2fsprogs and leave only the old functions for compatibility.

This percolates up to ext2fs_{mark,unmark,test}_{block,inode}_bitmap(), via ext2fs_{mark,unmark,test}_generic_bitmap(). Since these interface with an ext2fs_{block,inode}_bitmap (that presumably has a magic to determine whether it is 32 bits or 64 bits counts, it should be possible to leave them as simple compatibility wrappers for applications linking against e2fsprogs (using ext2fs_*bitmap_64() internallY), and change the e2fsprogs to use ext2fs_*bitmap_64() internally (though there are a large number of callsites).

The other issue is that applications which are using the old API but are actually using these functions against a 64-bit filesystem should fail gracefully. For many apps this might never be a problem, since they only deal with high-level library/filesystem operations.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.