• Robbie Ko's avatar
    Btrfs: send, fix infinite loop due to directory rename dependencies · aeda9163
    Robbie Ko authored
    [ Upstream commit a4390aee72713d9e73f1132bcdeb17d72fbbf974 ]
    
    When doing an incremental send, due to the need of delaying directory move
    (rename) operations we can end up in infinite loop at
    apply_children_dir_moves().
    
    An example scenario that triggers this problem is described below, where
    directory names correspond to the numbers of their respective inodes.
    
    Parent snapshot:
    
     .
     |--- 261/
           |--- 271/
                 |--- 266/
                       |--- 259/
                       |--- 260/
                       |     |--- 267
                       |
                       |--- 264/
                       |     |--- 258/
                       |           |--- 257/
                       |
                       |--- 265/
                       |--- 268/
                       |--- 269/
                       |     |--- 262/
                       |
                       |--- 270/
                       |--- 272/
                       |     |--- 263/
                       |     |--- 275/
                       |
                       |--- 274/
                             |--- 273/
    
    Send snapshot:
    
     .
     |-- 275/
          |-- 274/
               |-- 273/
                    |-- 262/
                         |-- 269/
                              |-- 258/
                                   |-- 271/
                                        |-- 268/
                                             |-- 267/
                                                  |-- 270/
                                                       |-- 259/
                                                       |    |-- 265/
                                                       |
                                                       |-- 272/
                                                            |-- 257/
                                                                 |-- 260/
                                                                 |-- 264/
                                                                      |-- 263/
                                                                           |-- 261/
                                                                                |-- 266/
    
    When processing inode 257 we delay its move (rename) operation because its
    new parent in the send snapshot, inode 272, was not yet processed. Then
    when processing inode 272, we delay the move operation for that inode
    because inode 274 is its ancestor in the send snapshot. Finally we delay
    the move operation for inode 274 when processing it because inode 275 is
    its new parent in the send snapshot and was not yet moved.
    
    When finishing processing inode 275, we start to do the move operations
    that were previously delayed (at apply_children_dir_moves()), resulting in
    the following iterations:
    
    1) We issue the move operation for inode 274;
    
    2) Because inode 262 depended on the move operation of inode 274 (it was
       delayed because 274 is its ancestor in the send snapshot), we issue the
       move operation for inode 262;
    
    3) We issue the move operation for inode 272, because it was delayed by
       inode 274 too (ancestor of 272 in the send snapshot);
    
    4) We issue the move operation for inode 269 (it was delayed by 262);
    
    5) We issue the move operation for inode 257 (it was delayed by 272);
    
    6) We issue the move operation for inode 260 (it was delayed by 272);
    
    7) We issue the move operation for inode 258 (it was delayed by 269);
    
    8) We issue the move operation for inode 264 (it was delayed by 257);
    
    9) We issue the move operation for inode 271 (it was delayed by 258);
    
    10) We issue the move operation for inode 263 (it was delayed by 264);
    
    11) We issue the move operation for inode 268 (it was delayed by 271);
    
    12) We verify if we can issue the move operation for inode 270 (it was
        delayed by 271). We detect a path loop in the current state, because
        inode 267 needs to be moved first before we can issue the move
        operation for inode 270. So we delay again the move operation for
        inode 270, this time we will attempt to do it after inode 267 is
        moved;
    
    13) We issue the move operation for inode 261 (it was delayed by 263);
    
    14) We verify if we can issue the move operation for inode 266 (it was
        delayed by 263). We detect a path loop in the current state, because
        inode 270 needs to be moved first before we can issue the move
        operation for inode 266. So we delay again the move operation for
        inode 266, this time we will attempt to do it after inode 270 is
        moved (its move operation was delayed in step 12);
    
    15) We issue the move operation for inode 267 (it was delayed by 268);
    
    16) We verify if we can issue the move operation for inode 266 (it was
        delayed by 270). We detect a path loop in the current state, because
        inode 270 needs to be moved first before we can issue the move
        operation for inode 266. So we delay again the move operation for
        inode 266, this time we will attempt to do it after inode 270 is
        moved (its move operation was delayed in step 12). So here we added
        again the same delayed move operation that we added in step 14;
    
    17) We attempt again to see if we can issue the move operation for inode
        266, and as in step 16, we realize we can not due to a path loop in
        the current state due to a dependency on inode 270. Again we delay
        inode's 266 rename to happen after inode's 270 move operation, adding
        the same dependency to the empty stack that we did in steps 14 and 16.
        The next iteration will pick the same move dependency on the stack
        (the only entry) and realize again there is still a path loop and then
        again the same dependency to the stack, over and over, resulting in
        an infinite loop.
    
    So fix this by preventing adding the same move dependency entries to the
    stack by removing each pending move record from the red black tree of
    pending moves. This way the next call to get_pending_dir_moves() will
    not return anything for the current parent inode.
    
    A test case for fstests, with this reproducer, follows soon.
    Signed-off-by: 's avatarRobbie Ko <robbieko@synology.com>
    Reviewed-by: 's avatarFilipe Manana <fdmanana@suse.com>
    [Wrote changelog with example and more clear explanation]
    Signed-off-by: 's avatarFilipe Manana <fdmanana@suse.com>
    Signed-off-by: 's avatarDavid Sterba <dsterba@suse.com>
    Signed-off-by: 's avatarSasha Levin <sashal@kernel.org>
    aeda9163
Name
Last commit
Last update
..
tests Loading commit data...
Kconfig Loading commit data...
Makefile Loading commit data...
acl.c Loading commit data...
async-thread.c Loading commit data...
async-thread.h Loading commit data...
backref.c Loading commit data...
backref.h Loading commit data...
btrfs_inode.h Loading commit data...
check-integrity.c Loading commit data...
check-integrity.h Loading commit data...
compression.c Loading commit data...
compression.h Loading commit data...
ctree.c Loading commit data...
ctree.h Loading commit data...
dedupe.h Loading commit data...
delayed-inode.c Loading commit data...
delayed-inode.h Loading commit data...
delayed-ref.c Loading commit data...
delayed-ref.h Loading commit data...
dev-replace.c Loading commit data...
dev-replace.h Loading commit data...
dir-item.c Loading commit data...
disk-io.c Loading commit data...
disk-io.h Loading commit data...
export.c Loading commit data...
export.h Loading commit data...
extent-tree.c Loading commit data...
extent_io.c Loading commit data...
extent_io.h Loading commit data...
extent_map.c Loading commit data...
extent_map.h Loading commit data...
file-item.c Loading commit data...
file.c Loading commit data...
free-space-cache.c Loading commit data...
free-space-cache.h Loading commit data...
free-space-tree.c Loading commit data...
free-space-tree.h Loading commit data...
hash.c Loading commit data...
hash.h Loading commit data...
inode-item.c Loading commit data...
inode-map.c Loading commit data...
inode-map.h Loading commit data...
inode.c Loading commit data...
ioctl.c Loading commit data...
locking.c Loading commit data...
locking.h Loading commit data...
lzo.c Loading commit data...
math.h Loading commit data...
ordered-data.c Loading commit data...
ordered-data.h Loading commit data...
orphan.c Loading commit data...
print-tree.c Loading commit data...
print-tree.h Loading commit data...
props.c Loading commit data...
props.h Loading commit data...
qgroup.c Loading commit data...
qgroup.h Loading commit data...
raid56.c Loading commit data...
raid56.h Loading commit data...
rcu-string.h Loading commit data...
reada.c Loading commit data...
relocation.c Loading commit data...
root-tree.c Loading commit data...
scrub.c Loading commit data...
send.c Loading commit data...
send.h Loading commit data...
struct-funcs.c Loading commit data...
super.c Loading commit data...
sysfs.c Loading commit data...
sysfs.h Loading commit data...
transaction.c Loading commit data...
transaction.h Loading commit data...
tree-checker.c Loading commit data...
tree-checker.h Loading commit data...
tree-defrag.c Loading commit data...
tree-log.c Loading commit data...
tree-log.h Loading commit data...
ulist.c Loading commit data...
ulist.h Loading commit data...
uuid-tree.c Loading commit data...
volumes.c Loading commit data...
volumes.h Loading commit data...
xattr.c Loading commit data...
xattr.h Loading commit data...
zlib.c Loading commit data...