libext2fs: Fix rbtree backend for extent lengths greater than 2^32
PATCH 1/1 libext2fs: Fix rbtree backend for extent lengths greater than 2^32
Well, this took way too long to find, in retrospect.
In short, for a completely full filesystem with more than 2^32 blocks, the rbtree bitmap backend can assemble an extent of used blocks which is longer than 2^32. If it does, it will overflow ->count, and corrupt the rbtree for the bitmaps.
Discovered by completely filling a 32T filesystem using fallocate, and then observing debugfs, dumpe2fs, and e2fsck all behaving badly.
(Note that filling with only 31 x 1T files did not show the problem, because freespace was fragmented enough that there was no sufficiently long range of used blocks.)
---
An alternative solution might be to limit the rb_extent to 32-bit counts, and not merging beyond that. For fragmented freespace, as normal, perhaps that would be a better memory savings? But this fixes the immediate problem and seems worth merging to avoid bad situations such as e2fsck corrupting a perfectly good 32T filesystem...
lib/ext2fs/blkmap64_rb.c +1 -1
@@ -33,7 +33,7 @@struct bmap_rb_extent {struct rb_node node;__u64 start; -__u32 count; +__u64 count; };struct ext2fs_rb_private {
Quoted 13 lines · Eric Sandeen
In short, for a completely full filesystem with more than 2^32 blocks, the rbtree bitmap backend can assemble an extent of used blocks which is longer than 2^32. If it does, it will overflow ->count, and corrupt the rbtree for the bitmaps.
Discovered by completely filling a 32T filesystem using fallocate, and then observing debugfs, dumpe2fs, and e2fsck all behaving badly.
(Note that filling with only 31 x 1T files did not show the problem, because freespace was fragmented enough that there was no sufficiently long range of used blocks.)
Signed-off-by Eric Sandeen <[email protected]>
Quoted 8 lines
---
An alternative solution might be to limit the
rb_extentto 32-bit counts, and not merging beyond that. For fragmented freespace, as normal, perhaps that would be a better memory savings? But this fixes the immediate problem and seems worth merging to avoid bad situations such as e2fsck corrupting a perfectly good 32T filesystem...
That was my initial thought as well, but the bmap_rb_extent struct already has several 64-bit values in it on a 64-bit arch, so there would not be any space savings. On a 32-bit arch, in theory we could save 8 bytes by locating a 32-bit count adjacent to rb_node instead of after __u64 start, but then 32-bit systems can't handle block devices over 16TB anyway, so the point is moot...
Quoted 15 lines
lib/ext2fs/blkmap64_rb.c +1
-2@@ -33,7 +33,7 @@struct bmap_rb_extent {struct rb_node node;__u64 start; -__u32 count; +__u64 count; };struct ext2fs_rb_private { --
Quoted 3 lines
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Cheers, Andreas
Ted Ts'o
AppliedQuoted 7 lines · Eric Sandeen
Well, this took way too long to find, in retrospect.
In short, for a completely full filesystem with more than 2^32 blocks, the rbtree bitmap backend can assemble an extent of used blocks which is longer than 2^32. If it does, it will overflow ->count, and corrupt the rbtree for the bitmaps.
Quoted 8 lines
Discovered by completely filling a 32T filesystem using fallocate, and then observing debugfs, dumpe2fs, and e2fsck all behaving badly.
(Note that filling with only 31 x 1T files did not show the problem, because freespace was fragmented enough that there was no sufficiently long range of used blocks.)
Signed-off-by Eric Sandeen <[email protected]>
Thanks, applied.
- Ted