From patchwork Tue Mar 18 17:55:09 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 3854971 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork2.web.kernel.org (Postfix) with ESMTP id D1814BF540 for ; Wed, 19 Mar 2014 17:52:16 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id CDD07200DE for ; Wed, 19 Mar 2014 17:52:15 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id CED912012E for ; Wed, 19 Mar 2014 17:52:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757086AbaCRRzV (ORCPT ); Tue, 18 Mar 2014 13:55:21 -0400 Received: from mail-wi0-f176.google.com ([209.85.212.176]:49180 "EHLO mail-wi0-f176.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755175AbaCRRzT (ORCPT ); Tue, 18 Mar 2014 13:55:19 -0400 Received: by mail-wi0-f176.google.com with SMTP id hr14so4059714wib.3 for ; Tue, 18 Mar 2014 10:55:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=jmIrAgw1xP2B71evLvUBEQPZ+KqDlW4Gou+jcaY4sP4=; b=cnD+ArHBJIaoNUo0hh9U48p4vmM+oqMAlkBZs6psRDXDP9Au3UgkgYWtxTKmNNwiVL cVoV7IYndsODAe3xGvi6jB2+Gw55MP3t/B0hK1ieT0CFT/BabEJ/LZVeVgctqz0HmDXB X9Sx/ab4fE/A9SYGybya4ZCyn/xlJFyi5/RerJDyCHZj3iYh96sm3d9FO96wLqAZMHDy bDlyAn2UAQlGBDOg15UOi1NVwnnUyCQBYIJs519tUjEXATMQMQAEhjhDALG4fPZqj6+M JF72S//i4RsaXyMBU4lPk1E7rAIu1DFvWVNbpKXIymKA7GKNUxkEHM057vegTKf5u3Uc sc4w== X-Received: by 10.180.19.130 with SMTP id f2mr15694603wie.6.1395165318138; Tue, 18 Mar 2014 10:55:18 -0700 (PDT) Received: from debian-vm3.lan (bl10-140-160.dsl.telepac.pt. [85.243.140.160]) by mx.google.com with ESMTPSA id c7sm4880168wjf.19.2014.03.18.10.55.16 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 18 Mar 2014 10:55:17 -0700 (PDT) From: Filipe David Borba Manana To: linux-btrfs@vger.kernel.org Cc: Filipe David Borba Manana Subject: [PATCH v3] Btrfs: part 2, fix incremental send's decision to delay a dir move/rename Date: Tue, 18 Mar 2014 17:55:09 +0000 Message-Id: <1395165310-24621-1-git-send-email-fdmanana@gmail.com> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <1395022528-27225-1-git-send-email-fdmanana@gmail.com> References: <1395022528-27225-1-git-send-email-fdmanana@gmail.com> Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, T_DKIM_INVALID, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP For an incremental send, fix the process of determining whether the directory inode we're currently processing needs to have its move/rename operation delayed. We were ignoring the fact that if the inode's new immediate ancestor has a higher inode number than ours but wasn't renamed/moved, we might still need to delay our move/rename, because some other ancestor directory higher in the hierarchy might have an inode number higher than ours *and* was renamed/moved too - in this case we have to wait for rename/move of that ancestor to happen before our current directory's rename/move operation. Simple steps to reproduce this issue: $ mkfs.btrfs -f /dev/sdd $ mount /dev/sdd /mnt $ mkdir -p /mnt/a/x1/x2 $ mkdir /mnt/a/Z $ mkdir -p /mnt/a/x1/x2/x3/x4/x5 $ btrfs subvolume snapshot -r /mnt /mnt/snap1 $ btrfs send /mnt/snap1 -f /tmp/base.send $ mv /mnt/a/x1/x2/x3 /mnt/a/Z/X33 $ mv /mnt/a/x1/x2 /mnt/a/Z/X33/x4/x5/X22 $ btrfs subvolume snapshot -r /mnt /mnt/snap2 $ btrfs send -p /mnt/snap1 /mnt/snap2 -f /tmp/incremental.send The incremental send caused the kernel code to enter an infinite loop when building the path string for directory Z after its references are processed. A more complex scenario: $ mkfs.btrfs -f /dev/sdd $ mount /dev/sdd /mnt $ mkdir -p /mnt/a/b/c/d $ mkdir /mnt/a/b/c/d/e $ mkdir /mnt/a/b/c/d/f $ mv /mnt/a/b/c/d/e /mnt/a/b/c/d/f/E2 $ mkdir /mmt/a/b/c/g $ mv /mnt/a/b/c/d /mnt/a/b/D2 $ btrfs subvolume snapshot -r /mnt /mnt/snap1 $ btrfs send /mnt/snap1 -f /tmp/base.send $ mkdir /mnt/a/o $ mv /mnt/a/b/c/g /mnt/a/b/D2/f/G2 $ mv /mnt/a/b/D2 /mnt/a/b/dd $ mv /mnt/a/b/c /mnt/a/C2 $ mv /mnt/a/b/dd/f /mnt/a/o/FF $ mv /mnt/a/b /mnt/a/o/FF/E2/BB $ btrfs subvolume snapshot -r /mnt /mnt/snap2 $ btrfs send -p /mnt/snap1 /mnt/snap2 -f /tmp/incremental.send A test case for xfstests follows. Signed-off-by: Filipe David Borba Manana --- V2: Added missing error handling and fixed typo in commit message. V3: Updated the algorithm to deal with more complex cases, hopefully all cases are nailed down now. fs/btrfs/send.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 53 insertions(+), 3 deletions(-) diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c index d869079..5d757ee 100644 --- a/fs/btrfs/send.c +++ b/fs/btrfs/send.c @@ -2916,7 +2916,7 @@ static void free_waiting_dir_move(struct send_ctx *sctx, kfree(dm); } -static int add_pending_dir_move(struct send_ctx *sctx, u64 parent_ino) +static int add_pending_dir_move(struct send_ctx *sctx, u64 ino, u64 parent_ino) { struct rb_node **p = &sctx->pending_dir_moves.rb_node; struct rb_node *parent = NULL; @@ -2929,7 +2929,7 @@ static int add_pending_dir_move(struct send_ctx *sctx, u64 parent_ino) if (!pm) return -ENOMEM; pm->parent_ino = parent_ino; - pm->ino = sctx->cur_ino; + pm->ino = ino; pm->gen = sctx->cur_inode_gen; INIT_LIST_HEAD(&pm->list); INIT_LIST_HEAD(&pm->update_refs); @@ -3183,6 +3183,7 @@ static int wait_for_parent_move(struct send_ctx *sctx, struct fs_path *path_before = NULL; struct fs_path *path_after = NULL; int len1, len2; + int register_upper_dirs; if (is_waiting_for_move(sctx, ino)) return 1; @@ -3242,6 +3243,54 @@ static int wait_for_parent_move(struct send_ctx *sctx, } ret = 0; + /* + * Ok, our new most direct ancestor has a higher inode number but + * wasn't moved/renamed. So maybe some of the new ancestors higher in + * the hierarchy have an higher inode number too *and* were renamed + * or moved - in this case we need to wait for the ancestor's rename + * or move operation before we can do the move/rename for the current + * inode. + */ + register_upper_dirs = 0; +again: + while ((ret == 0 || register_upper_dirs) && + parent_ino_after > sctx->cur_ino) { + ino = parent_ino_after; + fs_path_reset(path_before); + fs_path_reset(path_after); + + ret = get_first_ref(sctx->send_root, ino, &parent_ino_after, + NULL, path_after); + if (ret < 0) + goto out; + ret = get_first_ref(sctx->parent_root, ino, &parent_ino_before, + NULL, path_before); + if (ret == -ENOENT) { + ret = 0; + break; + } else if (ret < 0) { + goto out; + } + + len1 = fs_path_len(path_before); + len2 = fs_path_len(path_after); + if (parent_ino_before != parent_ino_after || len1 != len2 || + memcmp(path_before->start, path_after->start, len1)) { + ret = 1; + if (register_upper_dirs) { + break; + } else { + register_upper_dirs = 1; + parent_ino_after = parent_ref->dir; + goto again; + } + } else if (register_upper_dirs) { + ret = add_pending_dir_move(sctx, ino, parent_ino_after); + if (ret < 0 && ret != -EEXIST) + goto out; + } + } + out: fs_path_free(path_before); fs_path_free(path_after); @@ -3407,7 +3456,8 @@ verbose_printk("btrfs: process_recorded_refs %llu\n", sctx->cur_ino); goto out; if (ret) { ret = add_pending_dir_move(sctx, - cur->dir); + sctx->cur_ino, + cur->dir); *pending_move = 1; } else { ret = send_rename(sctx, valid_path,