libext2fs: teach ext2fs_extent_set_bmap() to update extents more optimally
When programs like resize2fs or e2fsck relocates all of the blocks in
an extent one at a time, the ext2fs_extent_set_bmap() works by
initially adding a new extent and then moving mapping from the old
extent to the new extent. For example:
t=1 EXTENTS: (0-2) 1152-1154
t=2 EXTENTS: (0) 1136, (1-2) 1153-1154
t=3 EXTENTS: (0-1) 1136-1137, (2) 1154
Unfortunately, previously, when the last block is updated, the
resulting extent tree will have two extents instead of one, like this:
t=4 EXTENTS: (0-1) 1136-1137, (2) 1138
With this commit, the resulting extent tree will be more optimally
represented with a single extent:
t=4 EXTENTS: (0-2) 1136-1138
The optimization in this commit solves the prolem reproted at:
https://github.com/tytso/e2fsprogs/issues/146
In that case, the file had a very large, complex (fragmented) extent
tree, and resize2fs needed to relcate all of its blocks as part of a
off-line shrink, the lack of the optimization led to an extent block
overflowing, resulting in the old extent (the one which originally
mapped logical block
2507128 to physical block
389065080) and the new
extent landing in two different leaf blocks:
2/ 2 1/ 1
2507128 -
2507128 640097 - 640097 1
2/ 2 1/135
2507128 -
2507128 389065080 -
389065080 1
This resulted a corrupted extent tree block and data loss.
Signed-off-by: Theodore Ts'o <tytso@mit.edu>