From patchwork Tue May 8 10:11:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: robbieko X-Patchwork-Id: 10385895 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id C7D49602C2 for ; Tue, 8 May 2018 10:11:58 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B6E4228CD0 for ; Tue, 8 May 2018 10:11:58 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id AB97228CE1; Tue, 8 May 2018 10:11:58 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 438DF28CD0 for ; Tue, 8 May 2018 10:11:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754740AbeEHKL4 (ORCPT ); Tue, 8 May 2018 06:11:56 -0400 Received: from synology.com ([59.124.61.242]:43363 "EHLO synology.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754366AbeEHKLy (ORCPT ); Tue, 8 May 2018 06:11:54 -0400 Received: from localhost.localdomain (unknown [10.13.20.241]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (No client certificate requested) by synology.com (Postfix) with ESMTPSA id CC761B011607; Tue, 8 May 2018 18:11:52 +0800 (CST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=synology.com; s=123; t=1525774312; bh=V4ms9Y8d8F0NMfSBpuw3V514f6/GQxkI9qS7AdpboAU=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=ifQx6v25G12O8MblGTReUXJiOMqbtZA7+4C1AGpPdjFgJi0IDPzN5HOiUjhRydojm 1StW93adge7J7oMRMb8HKDeRxSeNS+WY1ayrDELmeBEFJmv//4GzULNpFo/OKIcD6Y c84JTekU/6pKhybkcjbG5Zuwj67Q5PJ1VEkWY43g= From: robbieko To: linux-btrfs@vger.kernel.org Cc: Robbie Ko Subject: [PATCH v2 2/2] btrfs: incremental send, improve rmdir performance for large directory Date: Tue, 8 May 2018 18:11:38 +0800 Message-Id: <1525774298-6919-3-git-send-email-robbieko@synology.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1525774298-6919-1-git-send-email-robbieko@synology.com> References: <1525774298-6919-1-git-send-email-robbieko@synology.com> X-Synology-MCP-Status: no X-Synology-Spam-Flag: no X-Synology-Spam-Status: score=0, required 5, WHITELIST_FROM_ADDRESS 0 X-Synology-Virus-Status: no Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Robbie Ko Currently when checking if we can delete a directory, we always check if all its children have been processed. Example: A directory with 2,000,000 files was deleted Result: original : 1994m57.071s patch : 1m38.554s [FIX] Instead of checking all children on all calls to can_rmdir(), we keep track of the directory index offset of the child last checked in the last call to can_rmdir(), and then use it as the starting point for future calls to can_rmdir(). Signed-off-by: Robbie Ko Reviewed-by: Filipe Manana --- V2: fix comments split optimization allocations orphan_dir_info fs/btrfs/send.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-) diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c index 2830871..a477268 100644 --- a/fs/btrfs/send.c +++ b/fs/btrfs/send.c @@ -247,6 +247,7 @@ struct orphan_dir_info { struct rb_node node; u64 ino; u64 gen; + u64 last_dir_index_offset; }; struct name_cache_entry { @@ -2872,6 +2873,7 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen, return ERR_PTR(-ENOMEM); odi->ino = dir_ino; odi->gen = 0; + odi->last_dir_index_offset = 0; rb_link_node(&odi->node, parent, p); rb_insert_color(&odi->node, &sctx->orphan_dirs); @@ -2927,6 +2929,7 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen, struct btrfs_key found_key; struct btrfs_key loc; struct btrfs_dir_item *di; + struct orphan_dir_info *odi = NULL; /* * Don't try to rmdir the top/root subvolume dir. @@ -2941,6 +2944,11 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen, key.objectid = dir; key.type = BTRFS_DIR_INDEX_KEY; key.offset = 0; + + odi = get_orphan_dir_info(sctx, dir); + if (odi) + key.offset = odi->last_dir_index_offset; + ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); if (ret < 0) goto out; @@ -2968,30 +2976,33 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen, dm = get_waiting_dir_move(sctx, loc.objectid); if (dm) { - struct orphan_dir_info *odi; - odi = add_orphan_dir_info(sctx, dir); if (IS_ERR(odi)) { ret = PTR_ERR(odi); goto out; } odi->gen = dir_gen; + odi->last_dir_index_offset = found_key.offset; dm->rmdir_ino = dir; ret = 0; goto out; } if (loc.objectid > send_progress) { - struct orphan_dir_info *odi; - - odi = get_orphan_dir_info(sctx, dir); - free_orphan_dir_info(sctx, odi); + odi = add_orphan_dir_info(sctx, dir); + if (IS_ERR(odi)) { + ret = PTR_ERR(odi); + goto out; + } + odi->gen = dir_gen; + odi->last_dir_index_offset = found_key.offset; ret = 0; goto out; } path->slots[0]++; } + free_orphan_dir_info(sctx, odi); ret = 1; @@ -3269,13 +3280,16 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm) if (rmdir_ino) { struct orphan_dir_info *odi; + u64 gen; odi = get_orphan_dir_info(sctx, rmdir_ino); if (!odi) { /* already deleted */ goto finish; } - ret = can_rmdir(sctx, rmdir_ino, odi->gen, sctx->cur_ino); + gen = odi->gen; + + ret = can_rmdir(sctx, rmdir_ino, gen, sctx->cur_ino); if (ret < 0) goto out; if (!ret) @@ -3286,13 +3300,12 @@ static int apply_dir_move(struct send_ctx *sctx, struct pending_dir_move *pm) ret = -ENOMEM; goto out; } - ret = get_cur_path(sctx, rmdir_ino, odi->gen, name); + ret = get_cur_path(sctx, rmdir_ino, gen, name); if (ret < 0) goto out; ret = send_rmdir(sctx, name); if (ret < 0) goto out; - free_orphan_dir_info(sctx, odi); } finish: