From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DD7A5C35242 for ; Fri, 14 Feb 2020 06:33:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id B78DB2187F for ; Fri, 14 Feb 2020 06:33:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728718AbgBNGdK (ORCPT ); Fri, 14 Feb 2020 01:33:10 -0500 Received: from mx2.suse.de ([195.135.220.15]:49638 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725840AbgBNGdK (ORCPT ); Fri, 14 Feb 2020 01:33:10 -0500 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 5D93CAEB1 for ; Fri, 14 Feb 2020 06:33:08 +0000 (UTC) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 0/3] Btrfs: relocation: Refactor build_backref_tree() using btrfs_backref_iterator infrastructure Date: Fri, 14 Feb 2020 14:32:59 +0800 Message-Id: <20200214063302.47388-1-wqu@suse.com> X-Mailer: git-send-email 2.25.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org This is part 1 of the incoming refactor patches for build_backref_tree() [THE PLAN] The overall plan of refactoring build_backref_tree() is: - Refactor how we iterate through backref items This patchset, the smallest I guess. - Make build_backref_tree() easier to read. In short, that function is doing breadth-first-search to build a map which starts from one tree block, to all root nodes referring it. It involves backref iteration part, and a lot of backref cache only works. At least I hope to make this function less bulky and more structured. - Make build_backref_tree() independent from relocation The hardest I guess. Current it even accepts reloc_control as its first parameter. Don't have a clear plan yet, but I guess at least I should make build_backref_tree() to do some more coverage, other than taking certain relocation-dependent shortcut. [THIS PATCHSET] For the patchset itself, the main purpose is to change how we iterate through all backref items of one tree block. The old way: path->search_commit_root = 1; path->skip_locking = 1; ret = btrfs_search_slot(NULL, extent_root, path, &key, 0, 0); ptr = btrfs_item_offset_nr() end = btrfs_item_end_nr() /* Inline item loop */ while (ptr < end) { /* Handle each inline item here */ } while (1) { ret = btrfs_next_item(); btrfs_item_key_to_cpu() if (key.objectid != bytenr || !(key.type == XXX || key.type == YYY)) break; /* Handle each keyed item here */ } The new way: iterator = btrfs_backref_iterator_alloc(); for (ret = btrfs_backref_iterator_start(iterator, bytenr); ret == 0; ret = btrfs_backref_iterator_next(iterator)) { /* * Handle both keyed and inlined item here. * * We can use iterator->key to determine if it's inlined or * keyed. * Even for inlined item, it can be easily converted to keyed * item, just like we did in build_backref_tree(). */ } Currently, only build_backref_tree() can utilize this infrastructure. Backref.c has more requirement, as it needs to handle iteration for both data and metadata, both commit root and current root. And more importantly, backref.c uses depth first search, thus not a perfect match for btrfs_backref_iterator. Extra naming suggestion is welcomed. The current naming, btrfs_backref_iterator_* looks pretty long to me already. Shorter naming would be much better. Qu Wenruo (3): btrfs: backref: Introduce the skeleton of btrfs_backref_iterator btrfs: backref: Implement btrfs_backref_iterator_next() btrfs: relocation: Use btrfs_backref_iterator infrastructure fs/btrfs/backref.c | 106 +++++++++++++++++++++++ fs/btrfs/backref.h | 96 +++++++++++++++++++++ fs/btrfs/relocation.c | 193 ++++++++++++++---------------------------- 3 files changed, 264 insertions(+), 131 deletions(-) -- 2.25.0