Linux-BTRFS Archive on
 help / color / Atom feed
From: Qu Wenruo <>
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: <> (raw)

This is part 1 of the incoming refactor patches for build_backref_tree()

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
  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.

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();
	if (key.objectid != bytenr ||
	    !(key.type == XXX || key.type == YYY)) 
	/* 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
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(-)


             reply index

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-02-14  6:32 Qu Wenruo [this message]
2020-02-14  6:33 ` [PATCH 1/3] btrfs: backref: Introduce the skeleton of btrfs_backref_iterator Qu Wenruo
2020-02-14  6:33 ` [PATCH 2/3] btrfs: backref: Implement btrfs_backref_iterator_next() Qu Wenruo
2020-02-14  7:25   ` Qu Wenruo
2020-02-14  6:33 ` [PATCH 3/3] btrfs: relocation: Use btrfs_backref_iterator infrastructure Qu Wenruo
2020-02-14  6:56   ` Qu Wenruo

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-BTRFS Archive on

Archives are clonable:
	git clone --mirror linux-btrfs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-btrfs linux-btrfs/ \
	public-inbox-index linux-btrfs

Example config snippet for mirrors

Newsgroup available over NNTP:

AGPL code for this site: git clone