From f9bcce3be04b554004a82d4fe10edaf6077241be Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sat, 25 Mar 2006 13:42:45 -0500 Subject: [PATCH] Fix the i386 bitmap operations so they are 32-bit clean The x86 assembly instructures for bit test-and-set, test-and-clear, etc., interpret the bit number as a 32-bit signed number, which is problematic in order to support filesystems > 8TB. Added new inline functions (in C) to implement a ext2fs_fast_set/clear_bit() that does not return the old value of the bit, and use it for the fast block/bitmap functions. Added a regression test suite to test the low-level bit operations functions to make sure they work correctly. Note that a bitmap can address 2**32 blocks requires 2**29 bytes, or 512 megabytes. E2fsck requires 3 (and possibly 4 block bitmaps), which means that the block bitmaps can require 2GB all by themselves, and this doesn't include the 4 or 5 inode bitmaps (which assuming an 8k inode ratio, will take 256 megabytes each). This means that it's more likely that a filesystem check of a filesystem greater than 2**31 blocks will fail if the e2fsck is dynamically linked (since the shared libraries can consume a substantial portion of the 3GB address space available to x86 userspace applications). Even if e2fsck is statically linked, for a badly damaged filesystem, which may require additional block and/or inode bitmaps, I am not sure e2fsck will succeed in all cases. Signed-off-by: "Theodore Ts'o" --- lib/ext2fs/ChangeLog | 13 +++++ lib/ext2fs/Makefile.in | 5 +- lib/ext2fs/bitops.h | 54 ++++++++++++++----- lib/ext2fs/tst_bitops.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 190 insertions(+), 17 deletions(-) diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog index a93bfb9..ac3cd69 100644 --- a/lib/ext2fs/ChangeLog +++ b/lib/ext2fs/ChangeLog @@ -1,3 +1,16 @@ +2006-03-25 Theodore Ts'o + + * Makefile.in: Check the bitfield operations much more carefully, + and arrange to have tst_bitops run from "make check" + + * tst_bitops.c: Enahce tst_bitops program so that it is much more + thorough in testing bit optations. + + * bitops.h: Add new functions ext2fs_fast_set_bit() and + ext2fs_fast_clear_bit() and make the x86 functions 32-bit + clear. Change the fast inode and block mark/unmark + functions to use ext2fs_fast_set/get_bit() + 2006-03-18 Theodore Ts'o * ext2fs.h (EXT2_FLAG_EXCLUSIVE): Define new flag which requests diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in index d0412ff..b86c213 100644 --- a/lib/ext2fs/Makefile.in +++ b/lib/ext2fs/Makefile.in @@ -212,7 +212,7 @@ tst_byteswap: tst_byteswap.o bitops.o $(STATIC_LIBEXT2FS) tst_bitops: tst_bitops.o inline.o $(STATIC_LIBEXT2FS) @echo " LD $@" - @$(CC) -o tst_bitops tst_bitops.o inline.o \ + @$(CC) -o tst_bitops tst_bitops.o inline.o $(ALL_CFLAGS) \ $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) tst_getsectsize: tst_getsectsize.o getsectsize.o $(STATIC_LIBEXT2FS) @@ -224,7 +224,8 @@ mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) @echo " LD $@" @$(CC) -o mkjournal $(srcdir)/mkjournal.c -DDEBUG $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) $(ALL_CFLAGS) -check:: tst_badblocks tst_iscan @SWAPFS_CMT@ tst_byteswap +check:: tst_bitops tst_badblocks tst_iscan @SWAPFS_CMT@ tst_byteswap + LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_bitops LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_badblocks LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_iscan @SWAPFS_CMT@ LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_byteswap diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h index cb4d8a3..caaec5f 100644 --- a/lib/ext2fs/bitops.h +++ b/lib/ext2fs/bitops.h @@ -17,6 +17,8 @@ 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); extern __u16 ext2fs_swab16(__u16 val); extern __u32 ext2fs_swab32(__u32 val); @@ -129,6 +131,28 @@ extern int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, #endif #endif +/* + * Fast bit set/clear functions that doesn't need to return the + * previous bit value. + */ + +_INLINE_ void ext2fs_fast_set_bit(unsigned int nr,void * addr) +{ + unsigned char *ADDR = (unsigned char *) addr; + + ADDR += nr >> 3; + *ADDR |= (1 << (nr & 0x07)); +} + +_INLINE_ void ext2fs_fast_clear_bit(unsigned int nr, void * addr) +{ + unsigned char *ADDR = (unsigned char *) addr; + + ADDR += nr >> 3; + *ADDR &= ~(1 << (nr & 0x07)); +} + + #if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \ (defined(__i386__) || defined(__i486__) || defined(__i586__))) @@ -155,9 +179,10 @@ _INLINE_ int ext2fs_set_bit(unsigned int nr, void * addr) { int oldbit; + addr = (void *) (((unsigned char *) addr) + (nr >> 3)); __asm__ __volatile__("btsl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (EXT2FS_ADDR) - :"r" (nr)); + :"r" (nr & 7)); return oldbit; } @@ -165,9 +190,10 @@ _INLINE_ int ext2fs_clear_bit(unsigned int nr, void * addr) { int oldbit; + addr = (void *) (((unsigned char *) addr) + (nr >> 3)); __asm__ __volatile__("btrl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (EXT2FS_ADDR) - :"r" (nr)); + :"r" (nr & 7)); return oldbit; } @@ -175,9 +201,10 @@ _INLINE_ int ext2fs_test_bit(unsigned int nr, const void * addr) { int oldbit; + addr = (void *) (((unsigned char *) addr) + (nr >> 3)); __asm__ __volatile__("btl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit) - :"m" (EXT2FS_CONST_ADDR),"r" (nr)); + :"m" (EXT2FS_CONST_ADDR),"r" (nr & 7)); return oldbit; } @@ -263,7 +290,8 @@ _INLINE_ __u16 ext2fs_swab16(__u16 val) #endif /* i386 */ -#ifdef __mc68000__ +#if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \ + (defined(__mc68000__))) #define _EXT2_HAVE_ASM_BITOPS_ @@ -428,7 +456,7 @@ _INLINE_ void ext2fs_fast_mark_block_bitmap(ext2fs_block_bitmap bitmap, return; } #endif - ext2fs_set_bit(block - bitmap->start, bitmap->bitmap); + ext2fs_fast_set_bit(block - bitmap->start, bitmap->bitmap); } _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap, @@ -441,7 +469,7 @@ _INLINE_ void ext2fs_fast_unmark_block_bitmap(ext2fs_block_bitmap bitmap, return; } #endif - ext2fs_clear_bit(block - bitmap->start, bitmap->bitmap); + ext2fs_fast_clear_bit(block - bitmap->start, bitmap->bitmap); } _INLINE_ int ext2fs_fast_test_block_bitmap(ext2fs_block_bitmap bitmap, @@ -467,7 +495,7 @@ _INLINE_ void ext2fs_fast_mark_inode_bitmap(ext2fs_inode_bitmap bitmap, return; } #endif - ext2fs_set_bit(inode - bitmap->start, bitmap->bitmap); + ext2fs_fast_set_bit(inode - bitmap->start, bitmap->bitmap); } _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap, @@ -480,7 +508,7 @@ _INLINE_ void ext2fs_fast_unmark_inode_bitmap(ext2fs_inode_bitmap bitmap, return; } #endif - ext2fs_clear_bit(inode - bitmap->start, bitmap->bitmap); + ext2fs_fast_clear_bit(inode - bitmap->start, bitmap->bitmap); } _INLINE_ int ext2fs_fast_test_inode_bitmap(ext2fs_inode_bitmap bitmap, @@ -563,7 +591,7 @@ _INLINE_ void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, return; } for (i=0; i < num; i++) - ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap); + ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap); } _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, @@ -579,7 +607,7 @@ _INLINE_ void ext2fs_fast_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, } #endif for (i=0; i < num; i++) - ext2fs_set_bit(block + i - bitmap->start, bitmap->bitmap); + ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap); } _INLINE_ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, @@ -593,7 +621,8 @@ _INLINE_ void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, return; } for (i=0; i < num; i++) - ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap); + ext2fs_fast_clear_bit(block + i - bitmap->start, + bitmap->bitmap); } _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, @@ -609,7 +638,8 @@ _INLINE_ void ext2fs_fast_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, } #endif for (i=0; i < num; i++) - ext2fs_clear_bit(block + i - bitmap->start, bitmap->bitmap); + ext2fs_fast_clear_bit(block + i - bitmap->start, + bitmap->bitmap); } #undef _INLINE_ #endif diff --git a/lib/ext2fs/tst_bitops.c b/lib/ext2fs/tst_bitops.c index fb4d3ad..a0fb261 100644 --- a/lib/ext2fs/tst_bitops.c +++ b/lib/ext2fs/tst_bitops.c @@ -9,8 +9,6 @@ * %End-Header% */ -/* #define _EXT2_USE_C_VERSIONS_ */ - #include #include #if HAVE_UNISTD_H @@ -23,6 +21,8 @@ #if HAVE_ERRNO_H #include #endif +#include +#include #include "ext2_fs.h" #include "ext2fs.h" @@ -31,14 +31,143 @@ unsigned char bitarray[] = { 0x80, 0xF0, 0x40, 0x40, 0x0, 0x0, 0x0, 0x0, 0x10, 0x20, 0x00, 0x00 }; +int bits_list[] = { + 7, 12, 13, 14,15, 22, 30, 68, 77, -1, +}; + +#define BIG_TEST_BIT (((unsigned) 1 << 31) + 42) + + main(int argc, char **argv) { - int i, size; + int i, j, size; + unsigned char testarray[12]; + unsigned char *bigarray; size = sizeof(bitarray)*8; +#if 0 i = ext2fs_find_first_bit_set(bitarray, size); while (i < size) { printf("Bit set: %d\n", i); i = ext2fs_find_next_bit_set(bitarray, size, i+1); } +#endif + + /* Test test_bit */ + for (i=0,j=0; i < size; i++) { + if (ext2fs_test_bit(i, bitarray)) { + if (bits_list[j] == i) { + j++; + } else { + printf("Bit %d set, not expected\n", i); + exit(1); + } + } else { + if (bits_list[j] == i) { + printf("Expected bit %d to be clear.\n", i); + exit(1); + } + } + } + printf("ext2fs_test_bit appears to be correct\n"); + + /* Test ext2fs_set_bit */ + memset(testarray, 0, sizeof(testarray)); + for (i=0; bits_list[i] > 0; i++) { + ext2fs_set_bit(bits_list[i], testarray); + } + if (memcmp(testarray, bitarray, sizeof(testarray)) == 0) { + printf("ext2fs_set_bit test succeeded.\n"); + } else { + printf("ext2fs_set_bit test failed.\n"); + for (i=0; i < sizeof(testarray); i++) { + printf("%02x ", testarray[i]); + } + printf("\n"); + exit(1); + } + for (i=0; bits_list[i] > 0; i++) { + ext2fs_clear_bit(bits_list[i], testarray); + } + for (i=0; i < sizeof(testarray); i++) { + if (testarray[i]) { + printf("ext2fs_clear_bit failed, " + "testarray[%d] is %d\n", i, testarray[i]); + exit(1); + } + } + printf("ext2fs_clear_bit test succeed.\n"); + + + /* Do bigarray test */ + bigarray = malloc(1 << 29); + if (!bigarray) { + fprintf(stderr, "Failed to allocate scratch memory!\n"); + exit(1); + } + + bigarray[BIG_TEST_BIT >> 3] = 0; + + ext2fs_set_bit(BIG_TEST_BIT, bigarray); + printf("big bit number (%u) test: %d, expected %d\n", BIG_TEST_BIT, + bigarray[BIG_TEST_BIT >> 3], (1 << (BIG_TEST_BIT & 7))); + if (bigarray[BIG_TEST_BIT >> 3] != (1 << (BIG_TEST_BIT & 7))) + exit(1); + + ext2fs_clear_bit(BIG_TEST_BIT, bigarray); + + printf("big bit number (%u) test: %d, expected 0\n", BIG_TEST_BIT, + bigarray[BIG_TEST_BIT >> 3], 0); + if (bigarray[BIG_TEST_BIT >> 3] != 0) + exit(1); + + printf("ext2fs_set_bit big_test successful\n"); + + + /* Now test ext2fs_fast_set_bit */ + memset(testarray, 0, sizeof(testarray)); + for (i=0; bits_list[i] > 0; i++) { + ext2fs_fast_set_bit(bits_list[i], testarray); + } + if (memcmp(testarray, bitarray, sizeof(testarray)) == 0) { + printf("ext2fs_fast_set_bit test succeeded.\n"); + } else { + printf("ext2fs_fast_set_bit test failed.\n"); + for (i=0; i < sizeof(testarray); i++) { + printf("%02x ", testarray[i]); + } + printf("\n"); + exit(1); + } + for (i=0; bits_list[i] > 0; i++) { + ext2fs_clear_bit(bits_list[i], testarray); + } + for (i=0; i < sizeof(testarray); i++) { + if (testarray[i]) { + printf("ext2fs_clear_bit failed, " + "testarray[%d] is %d\n", i, testarray[i]); + exit(1); + } + } + printf("ext2fs_clear_bit test succeed.\n"); + + + bigarray[BIG_TEST_BIT >> 3] = 0; + + ext2fs_fast_set_bit(BIG_TEST_BIT, bigarray); + printf("big bit number (%u) test: %d, expected %d\n", BIG_TEST_BIT, + bigarray[BIG_TEST_BIT >> 3], (1 << (BIG_TEST_BIT & 7))); + if (bigarray[BIG_TEST_BIT >> 3] != (1 << (BIG_TEST_BIT & 7))) + exit(1); + + ext2fs_fast_clear_bit(BIG_TEST_BIT, bigarray); + + printf("big bit number (%u) test: %d, expected 0\n", BIG_TEST_BIT, + bigarray[BIG_TEST_BIT >> 3], 0); + if (bigarray[BIG_TEST_BIT >> 3] != 0) + exit(1); + + printf("ext2fs_fast_set_bit big_test successful\n"); + + exit(0); } -- 1.8.3.1