From: jeffm@suse.com
To: linux-btrfs@vger.kernel.org
Cc: Jeff Mahoney <jeffm@suse.com>
Subject: [PATCH 2/7] btrfs-progs: check: switch to iterating over the backref_tree
Date: Tue, 25 Jul 2017 16:51:33 -0400 [thread overview]
Message-ID: <20170725205138.28376-2-jeffm@suse.com> (raw)
In-Reply-To: <20170725205138.28376-1-jeffm@suse.com>
From: Jeff Mahoney <jeffm@suse.com>
We now have two data structures that can be used to iterate the same data
set, and there may be quite a few of them in memory. Eliminating the
list_head member will reduce memory consumption while iterating over
the extent backrefs.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
cmds-check.c | 83 ++++++++++++++++++++++++++----------------------------------
1 file changed, 36 insertions(+), 47 deletions(-)
diff --git a/cmds-check.c b/cmds-check.c
index 6a04553..b46a686 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -86,7 +86,6 @@ enum btrfs_check_mode {
static enum btrfs_check_mode check_mode = CHECK_MODE_DEFAULT;
struct extent_backref {
- struct list_head list;
struct rb_node node;
unsigned int is_data:1;
unsigned int found_extent_tree:1;
@@ -95,11 +94,6 @@ struct extent_backref {
unsigned int broken:1;
};
-static inline struct extent_backref* to_extent_backref(struct list_head *entry)
-{
- return list_entry(entry, struct extent_backref, list);
-}
-
static inline struct extent_backref* rb_node_to_extent_backref(struct rb_node *node)
{
return rb_entry(node, struct extent_backref, node);
@@ -5452,16 +5446,14 @@ out:
static int all_backpointers_checked(struct extent_record *rec, int print_errs)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct tree_backref *tback;
struct data_backref *dback;
u64 found = 0;
int err = 0;
- while(cur != &rec->backrefs) {
- back = to_extent_backref(cur);
- cur = cur->next;
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (!back->found_extent_tree) {
err = 1;
if (!print_errs)
@@ -5564,17 +5556,16 @@ out:
return err;
}
-static int free_all_extent_backrefs(struct extent_record *rec)
+static void __free_one_backref(struct rb_node *node)
{
- struct extent_backref *back;
- struct list_head *cur;
- while (!list_empty(&rec->backrefs)) {
- cur = rec->backrefs.next;
- back = to_extent_backref(cur);
- list_del(cur);
- free(back);
- }
- return 0;
+ struct extent_backref *back = rb_node_to_extent_backref(node);
+
+ free(back);
+}
+
+static void free_all_extent_backrefs(struct extent_record *rec)
+{
+ rb_free_nodes(&rec->backref_tree, __free_one_backref);
}
static void free_extent_record_cache(struct cache_tree *extent_cache)
@@ -5613,7 +5604,7 @@ static int check_owner_ref(struct btrfs_root *root,
struct extent_record *rec,
struct extent_buffer *buf)
{
- struct extent_backref *node;
+ struct extent_backref *node, *tmp;
struct tree_backref *back;
struct btrfs_root *ref_root;
struct btrfs_key key;
@@ -5623,7 +5614,8 @@ static int check_owner_ref(struct btrfs_root *root,
int found = 0;
int ret;
- list_for_each_entry(node, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(node, tmp,
+ &rec->backref_tree, node) {
if (node->is_data)
continue;
if (!node->found_ref)
@@ -5668,14 +5660,12 @@ static int check_owner_ref(struct btrfs_root *root,
static int is_extent_tree_record(struct extent_record *rec)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *node;
+ struct extent_backref *node, *tmp;
struct tree_backref *back;
int is_extent = 0;
- while(cur != &rec->backrefs) {
- node = to_extent_backref(cur);
- cur = cur->next;
+ rbtree_postorder_for_each_entry_safe(node, tmp,
+ &rec->backref_tree, node) {
if (node->is_data)
return 0;
back = to_tree_backref(node);
@@ -6085,7 +6075,6 @@ static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
ref->root = root;
ref->node.full_backref = 0;
}
- list_add_tail(&ref->node.list, &rec->backrefs);
return ref;
}
@@ -6155,7 +6144,6 @@ static struct data_backref *alloc_data_backref(struct extent_record *rec,
ref->bytes = max_size;
ref->found_ref = 0;
ref->num_refs = 0;
- list_add_tail(&ref->node.list, &rec->backrefs);
if (max_size > rec->max_size)
rec->max_size = max_size;
return ref;
@@ -6188,12 +6176,12 @@ static void check_extent_type(struct extent_record *rec)
* Check SYSTEM extent, as it's also marked as metadata, we can only
* make sure it's a SYSTEM extent by its backref
*/
- if (!list_empty(&rec->backrefs)) {
+ if (!RB_EMPTY_ROOT(&rec->backref_tree)) {
struct extent_backref *node;
struct tree_backref *tback;
u64 bg_type;
- node = to_extent_backref(rec->backrefs.next);
+ node = rb_node_to_extent_backref(rb_first(&rec->backref_tree));
if (node->is_data) {
/* tree block shouldn't have data backref */
rec->wrong_chunk_type = 1;
@@ -8191,7 +8179,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans,
back->node.found_extent_tree = 0;
if (!back->node.found_extent_tree && back->node.found_ref) {
- list_del(&back->node.list);
+ rb_erase(&back->node.node, &rec->backref_tree);
free(back);
}
} else {
@@ -8210,7 +8198,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans,
back->node.found_extent_tree = 0;
}
if (!back->node.found_extent_tree && back->node.found_ref) {
- list_del(&back->node.list);
+ rb_erase(&back->node.node, &rec->backref_tree);
free(back);
}
}
@@ -8651,7 +8639,7 @@ out:
static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
struct extent_record *rec)
{
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct extent_entry *entry, *best = NULL;
LIST_HEAD(entries);
@@ -8667,7 +8655,8 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
if (rec->metadata)
return 0;
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data)
continue;
@@ -8793,7 +8782,8 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
* Ok great we all agreed on an extent record, let's go find the real
* references and fix up the ones that don't match.
*/
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data)
continue;
@@ -9017,7 +9007,7 @@ static int find_possible_backrefs(struct btrfs_fs_info *info,
struct extent_record *rec)
{
struct btrfs_root *root;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct cache_extent *cache;
struct btrfs_file_extent_item *fi;
@@ -9025,7 +9015,8 @@ static int find_possible_backrefs(struct btrfs_fs_info *info,
u64 bytenr, bytes;
int ret;
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
/* Don't care about full backrefs (poor unloved backrefs) */
if (back->full_backref || !back->is_data)
continue;
@@ -9113,7 +9104,7 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
{
struct btrfs_key key;
struct btrfs_root *dest_root;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct orphan_data_extent *orphan;
struct btrfs_path path;
@@ -9123,7 +9114,8 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info,
if (rec->metadata)
return 1;
btrfs_init_path(&path);
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data ||
!back->found_extent_tree)
continue;
@@ -9191,9 +9183,8 @@ static int fixup_extent_refs(struct btrfs_fs_info *info,
struct btrfs_trans_handle *trans = NULL;
int ret;
struct btrfs_path path;
- struct list_head *cur = rec->backrefs.next;
struct cache_extent *cache;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
int allocated = 0;
u64 flags = 0;
@@ -9241,10 +9232,8 @@ static int fixup_extent_refs(struct btrfs_fs_info *info,
}
/* step three, recreate all the refs we did find */
- while(cur != &rec->backrefs) {
- back = to_extent_backref(cur);
- cur = cur->next;
-
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
/*
* if we didn't find any references, don't create a
* new extent record
--
2.11.0
next prev parent reply other threads:[~2017-07-25 20:51 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-07-25 20:51 [PATCH 1/7] btrfs-progs: check: supplement extent backref list with rbtree jeffm
2017-07-25 20:51 ` jeffm [this message]
2017-07-25 20:51 ` [PATCH 3/7] btrfs-progs: extent-cache: actually cache extent buffers jeffm
2017-07-26 7:00 ` Nikolay Borisov
2017-07-26 13:21 ` Jeff Mahoney
2017-08-22 15:44 ` David Sterba
2017-07-25 20:51 ` [PATCH 4/7] btrfs-progs: backref: push state tracking into a helper structure jeffm
2017-07-25 20:51 ` [PATCH 5/7] btrfs-progs: backref: add list_first_pref helper jeffm
2017-07-26 7:08 ` Nikolay Borisov
2017-07-26 13:22 ` Jeff Mahoney
2017-07-26 13:25 ` Jeff Mahoney
2017-07-25 20:51 ` [PATCH 6/7] btrfs-progs: backref: use separate list for missing keys jeffm
2017-07-25 20:51 ` [PATCH 7/7] btrfs-progs: backref: use separate list for indirect refs jeffm
2017-09-29 17:21 ` [PATCH 1/7] btrfs-progs: check: supplement extent backref list with rbtree David Sterba
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:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170725205138.28376-2-jeffm@suse.com \
--to=jeffm@suse.com \
--cc=linux-btrfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.