From patchwork Tue May 8 02:50:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: robbieko X-Patchwork-Id: 10385199 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 1BA3260236 for ; Tue, 8 May 2018 02:50:57 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0B5CD289C5 for ; Tue, 8 May 2018 02:50:57 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0012028BB3; Tue, 8 May 2018 02:50:56 +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 154E0289C5 for ; Tue, 8 May 2018 02:50:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753648AbeEHCux (ORCPT ); Mon, 7 May 2018 22:50:53 -0400 Received: from synology.com ([59.124.61.242]:42954 "EHLO synology.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753499AbeEHCuw (ORCPT ); Mon, 7 May 2018 22:50:52 -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 CF4531E3905B8; Tue, 8 May 2018 10:50:50 +0800 (CST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=synology.com; s=123; t=1525747850; bh=ZRYGAnMyD7qQXsb135GqmMwcS1N9clWpYx9DVEEn9ds=; h=From:To:Cc:Subject:Date; b=dgpuEPMhtUZCoOMQffz+9Y7+pcibF+w1MaNJtD8Tkd7LsGOARnXeRwZnZ1LzTLXgo skGIMUjtPyyEEtoPjrlbD9wHgdt1eHHkY3YL91rWSpk0iYzLNZM5X+nwDltsKpUZ3Z mChznFx71c3MZ1/BZBJbjjol0lAO8pMANNHsuS/c= From: robbieko To: linux-btrfs@vger.kernel.org Cc: Robbie Ko Subject: [PATCH] btrfs: send, improve rmdir performance for large directory Date: Tue, 8 May 2018 10:50:43 +0800 Message-Id: <1525747843-31894-1-git-send-email-robbieko@synology.com> X-Mailer: git-send-email 1.9.1 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 At present, we check if the directory can be deleted. We need to check whether all the files under this directory have been processed every time we finished processing an entry under that directory. Example: 2,000,000 files in 1 directory. Parent snapshot: |---- dir/ (ino 257, dir) |---- f1 (ino 258, file1) |---- f2 (ino 259, file2) |---- ... |---- f2000000 Send snapshot: (Empty) Result: original : 1994m57.071s patch : 1m38.554s [FIX] We add a offset hint for dir index when check can_rmdir. This hint records the offset to which the last can_rmdir was processed. Signed-off-by: Robbie Ko --- fs/btrfs/send.c | 45 +++++++++++++++++++++++++++++---------------- 1 file changed, 29 insertions(+), 16 deletions(-) diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c index 484e2af..43b0364 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 offset_hint; }; struct name_cache_entry { @@ -2855,12 +2856,6 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen, struct rb_node *parent = NULL; struct orphan_dir_info *entry, *odi; - odi = kmalloc(sizeof(*odi), GFP_KERNEL); - if (!odi) - return ERR_PTR(-ENOMEM); - odi->ino = dir_ino; - odi->gen = 0; - while (*p) { parent = *p; entry = rb_entry(parent, struct orphan_dir_info, node); @@ -2869,11 +2864,17 @@ static int orphanize_inode(struct send_ctx *sctx, u64 ino, u64 gen, } else if (dir_ino > entry->ino) { p = &(*p)->rb_right; } else { - kfree(odi); return entry; } } + odi = kmalloc(sizeof(*odi), GFP_KERNEL); + if (!odi) + return ERR_PTR(-ENOMEM); + odi->ino = dir_ino; + odi->gen = 0; + odi->offset_hint = 0; + rb_link_node(&odi->node, parent, p); rb_insert_color(&odi->node, &sctx->orphan_dirs); return odi; @@ -2928,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. @@ -2942,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->offset_hint; + ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); if (ret < 0) goto out; @@ -2969,24 +2976,26 @@ 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->offset_hint = 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->offset_hint = found_key.offset; ret = 0; goto out; } @@ -2994,6 +3003,8 @@ static int can_rmdir(struct send_ctx *sctx, u64 dir, u64 dir_gen, path->slots[0]++; } + if (odi) + free_orphan_dir_info(sctx, odi); ret = 1; out: @@ -3270,13 +3281,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) @@ -3287,13 +3301,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: