u64 wanted_disk_byte;
};
+static struct __prelim_ref *list_first_pref(struct list_head *head)
+{
+ return list_first_entry(head, struct __prelim_ref, list);
+}
+
+struct pref_state {
+ struct list_head pending;
+ struct list_head pending_missing_keys;
+ struct list_head pending_indirect_refs;
+};
+
+static void init_pref_state(struct pref_state *prefstate)
+{
+ INIT_LIST_HEAD(&prefstate->pending);
+ INIT_LIST_HEAD(&prefstate->pending_missing_keys);
+ INIT_LIST_HEAD(&prefstate->pending_indirect_refs);
+}
+
/*
* the rules for all callers of this function are:
* - obtaining the parent is the goal
* block might help in merging entries to gain some speed.
*/
-static int __add_prelim_ref(struct list_head *head, u64 root_id,
+static int __add_prelim_ref(struct pref_state *prefstate, u64 root_id,
struct btrfs_key *key, int level,
u64 parent, u64 wanted_disk_byte, int count,
gfp_t gfp_mask)
{
+ struct list_head *head;
struct __prelim_ref *ref;
if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
return -ENOMEM;
ref->root_id = root_id;
- if (key)
+ if (key) {
ref->key_for_search = *key;
- else
+ head = &prefstate->pending;
+ } else if (parent) {
+ memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
+ head = &prefstate->pending;
+ } else {
memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
+ head = &prefstate->pending_missing_keys;
+ }
ref->inode_list = NULL;
ref->level = level;
ref->count = count;
ref->parent = parent;
ref->wanted_disk_byte = wanted_disk_byte;
+
list_add_tail(&ref->list, head);
return 0;
* resolve all indirect backrefs from the list
*/
static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
+ struct pref_state *prefstate,
struct btrfs_path *path, u64 time_seq,
- struct list_head *head,
const u64 *extent_item_pos, u64 total_refs)
{
+ struct list_head *head = &prefstate->pending_indirect_refs;
int err;
int ret = 0;
struct __prelim_ref *ref;
- struct __prelim_ref *ref_safe;
struct __prelim_ref *new_ref;
struct ulist *parents;
struct ulist_node *node;
if (!parents)
return -ENOMEM;
- /*
- * _safe allows us to insert directly after the current item without
- * iterating over the newly inserted items.
- * we're also allowed to re-assign ref during iteration.
- */
- list_for_each_entry_safe(ref, ref_safe, head, list) {
- if (ref->parent) /* already direct */
- continue;
- if (ref->count == 0)
- continue;
+ while (!list_empty(head)) {
+ ref = list_first_pref(head);
+ list_move(&ref->list, &prefstate->pending);
+ ASSERT(!ref->parent); /* already direct */
+ ASSERT(ref->count);
err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
parents, extent_item_pos,
total_refs);
new_ref->parent = node->val;
new_ref->inode_list = (struct extent_inode_elem *)
(uintptr_t)node->aux;
- list_add(&new_ref->list, &ref->list);
+ list_add_tail(&new_ref->list, &prefstate->pending);
}
ulist_reinit(parents);
}
* read tree blocks and add keys where required.
*/
static int __add_missing_keys(struct btrfs_fs_info *fs_info,
- struct list_head *head)
+ struct pref_state *prefstate)
{
- struct list_head *pos;
struct extent_buffer *eb;
- list_for_each(pos, head) {
+ while (!list_empty(&prefstate->pending_missing_keys)) {
struct __prelim_ref *ref;
- ref = list_entry(pos, struct __prelim_ref, list);
- if (ref->parent)
- continue;
- if (ref->key_for_search.type)
- continue;
+ ref = list_first_pref(&prefstate->pending_missing_keys);
+
+ ASSERT(ref->root_id);
+ ASSERT(!ref->parent);
+ ASSERT(!ref->key_for_search.type);
BUG_ON(!ref->wanted_disk_byte);
eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
if (!extent_buffer_uptodate(eb)) {
else
btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
free_extent_buffer(eb);
+ list_move(&ref->list, &prefstate->pending);
}
return 0;
}
* having a parent).
* mode = 2: merge identical parents
*/
-static void __merge_refs(struct list_head *head, int mode)
+static void __merge_refs(struct pref_state *prefstate, int mode)
{
+ struct list_head *head = &prefstate->pending;
struct list_head *pos1;
list_for_each(pos1, head) {
* add all inline backrefs for bytenr to the list
*/
static int __add_inline_refs(struct btrfs_fs_info *fs_info,
+ struct pref_state *prefstate,
struct btrfs_path *path, u64 bytenr,
- int *info_level, struct list_head *prefs,
- u64 *total_refs)
+ int *info_level, u64 *total_refs)
{
int ret = 0;
int slot;
struct btrfs_extent_item *ei;
u64 flags;
u64 item_size;
-
/*
* enumerate all inline refs
*/
switch (type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, 0, NULL,
+ ret = __add_prelim_ref(prefstate, 0, NULL,
*info_level + 1, offset,
bytenr, 1, GFP_NOFS);
break;
sdref = (struct btrfs_shared_data_ref *)(iref + 1);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = __add_prelim_ref(prefs, 0, NULL, 0, offset,
+ ret = __add_prelim_ref(prefstate, 0, NULL, 0, offset,
bytenr, count, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, offset, NULL,
+ ret = __add_prelim_ref(prefstate, offset, NULL,
*info_level + 1, 0,
bytenr, 1, GFP_NOFS);
break;
key.type = BTRFS_EXTENT_DATA_KEY;
key.offset = btrfs_extent_data_ref_offset(leaf, dref);
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = __add_prelim_ref(prefs, root, &key, 0, 0,
+ ret = __add_prelim_ref(prefstate, root, &key, 0, 0,
bytenr, count, GFP_NOFS);
break;
}
* add all non-inline backrefs for bytenr to the list
*/
static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
+ struct pref_state *prefstate,
struct btrfs_path *path, u64 bytenr,
- int info_level, struct list_head *prefs)
+ int info_level)
{
struct btrfs_root *extent_root = fs_info->extent_root;
int ret;
switch (key.type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, 0, NULL,
+ ret = __add_prelim_ref(prefstate, 0, NULL,
info_level + 1, key.offset,
bytenr, 1, GFP_NOFS);
break;
sdref = btrfs_item_ptr(leaf, slot,
struct btrfs_shared_data_ref);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset,
+ ret = __add_prelim_ref(prefstate, 0, NULL, 0, key.offset,
bytenr, count, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, key.offset, NULL,
+ ret = __add_prelim_ref(prefstate, key.offset, NULL,
info_level + 1, 0,
bytenr, 1, GFP_NOFS);
break;
key.type = BTRFS_EXTENT_DATA_KEY;
key.offset = btrfs_extent_data_ref_offset(leaf, dref);
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = __add_prelim_ref(prefs, root, &key, 0, 0,
+ ret = __add_prelim_ref(prefstate, root, &key, 0, 0,
bytenr, count, GFP_NOFS);
break;
}
struct btrfs_path *path;
int info_level = 0;
int ret;
- struct list_head prefs;
+ struct pref_state prefstate;
struct __prelim_ref *ref;
struct extent_inode_elem *eie = NULL;
u64 total_refs = 0;
- INIT_LIST_HEAD(&prefs);
+ init_pref_state(&prefstate);
key.objectid = bytenr;
key.offset = (u64)-1;
if (key.objectid == bytenr &&
(key.type == BTRFS_EXTENT_ITEM_KEY ||
key.type == BTRFS_METADATA_ITEM_KEY)) {
- ret = __add_inline_refs(fs_info, path, bytenr,
- &info_level, &prefs,
+ ret = __add_inline_refs(fs_info, &prefstate, path,
+ bytenr, &info_level,
&total_refs);
if (ret)
goto out;
- ret = __add_keyed_refs(fs_info, path, bytenr,
- info_level, &prefs);
+ ret = __add_keyed_refs(fs_info, &prefstate, path,
+ bytenr, info_level);
if (ret)
goto out;
}
}
btrfs_release_path(path);
- ret = __add_missing_keys(fs_info, &prefs);
+ ret = __add_missing_keys(fs_info, &prefstate);
if (ret)
goto out;
- __merge_refs(&prefs, 1);
+ __merge_refs(&prefstate, 1);
- ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
+ ret = __resolve_indirect_refs(fs_info, &prefstate, path, time_seq,
extent_item_pos, total_refs);
if (ret)
goto out;
- __merge_refs(&prefs, 2);
+ __merge_refs(&prefstate, 2);
+
+ BUG_ON(!list_empty(&prefstate.pending_missing_keys));
+ BUG_ON(!list_empty(&prefstate.pending_indirect_refs));
- while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ while (!list_empty(&prefstate.pending)) {
+ ref = list_first_pref(&prefstate.pending);
WARN_ON(ref->count < 0);
if (roots && ref->count && ref->root_id && ref->parent == 0) {
/* no parent == root of tree */
out:
btrfs_free_path(path);
- while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ while (!list_empty(&prefstate.pending)) {
+ ref = list_first_pref(&prefstate.pending);
list_del(&ref->list);
kfree(ref);
}
projects / platform / upstream / btrfs-progs.git / blobdiff