#include <linux/sched.h>
#include <linux/sort.h>
-#include <linux/ftrace.h>
#include "ctree.h"
#include "delayed-ref.h"
#include "transaction.h"
* ref if it was able to find one, or NULL if nothing was in that spot
*/
static struct btrfs_delayed_ref_node *tree_search(struct rb_root *root,
- u64 bytenr, u64 parent)
+ u64 bytenr, u64 parent,
+ struct btrfs_delayed_ref_node **last)
{
struct rb_node *n = root->rb_node;
struct btrfs_delayed_ref_node *entry;
while (n) {
entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
WARN_ON(!entry->in_tree);
+ if (last)
+ *last = entry;
cmp = comp_entry(entry, bytenr, parent);
if (cmp < 0)
return NULL;
}
-/*
- * Locking on delayed refs is done by taking a lock on the head node,
- * which has the (impossible) parent id of (u64)-1. Once a lock is held
- * on the head node, you're allowed (and required) to process all the
- * delayed refs for a given byte number in the tree.
- *
- * This will walk forward in the rbtree until it finds a head node it
- * is able to lock. It might not lock the delayed ref you asked for,
- * and so it will return the one it did lock in next_ret and return 0.
- *
- * If no locks are taken, next_ret is set to null and 1 is returned. This
- * means there are no more unlocked head nodes in the rbtree.
- */
-int btrfs_lock_delayed_ref(struct btrfs_trans_handle *trans,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_ref_head **next_ret)
+int btrfs_delayed_ref_lock(struct btrfs_trans_handle *trans,
+ struct btrfs_delayed_ref_head *head)
+{
+ struct btrfs_delayed_ref_root *delayed_refs;
+
+ delayed_refs = &trans->transaction->delayed_refs;
+ assert_spin_locked(&delayed_refs->lock);
+ if (mutex_trylock(&head->mutex))
+ return 0;
+
+ atomic_inc(&head->node.refs);
+ spin_unlock(&delayed_refs->lock);
+
+ mutex_lock(&head->mutex);
+ spin_lock(&delayed_refs->lock);
+ if (!head->node.in_tree) {
+ mutex_unlock(&head->mutex);
+ btrfs_put_delayed_ref(&head->node);
+ return -EAGAIN;
+ }
+ btrfs_put_delayed_ref(&head->node);
+ return 0;
+}
+
+int btrfs_find_ref_cluster(struct btrfs_trans_handle *trans,
+ struct list_head *cluster, u64 start)
{
+ int count = 0;
+ struct btrfs_delayed_ref_root *delayed_refs;
struct rb_node *node;
+ struct btrfs_delayed_ref_node *ref;
struct btrfs_delayed_ref_head *head;
- int ret = 0;
- while (1) {
+ delayed_refs = &trans->transaction->delayed_refs;
+ if (start == 0) {
+ node = rb_first(&delayed_refs->root);
+ } else {
+ ref = NULL;
+ tree_search(&delayed_refs->root, start, (u64)-1, &ref);
+ if (ref) {
+ struct btrfs_delayed_ref_node *tmp;
+
+ node = rb_prev(&ref->rb_node);
+ while (node) {
+ tmp = rb_entry(node,
+ struct btrfs_delayed_ref_node,
+ rb_node);
+ if (tmp->bytenr < start)
+ break;
+ ref = tmp;
+ node = rb_prev(&ref->rb_node);
+ }
+ node = &ref->rb_node;
+ } else
+ node = rb_first(&delayed_refs->root);
+ }
+again:
+ while (node && count < 32) {
+ ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
if (btrfs_delayed_ref_is_head(ref)) {
head = btrfs_delayed_node_to_head(ref);
- if (mutex_trylock(&head->mutex)) {
- *next_ret = head;
- ret = 0;
+ if (list_empty(&head->cluster)) {
+ list_add_tail(&head->cluster, cluster);
+ delayed_refs->run_delayed_start =
+ head->node.bytenr;
+ count++;
+
+ WARN_ON(delayed_refs->num_heads_ready == 0);
+ delayed_refs->num_heads_ready--;
+ } else if (count) {
+ /* the goal of the clustering is to find extents
+ * that are likely to end up in the same extent
+ * leaf on disk. So, we don't want them spread
+ * all over the tree. Stop now if we've hit
+ * a head that was already in use
+ */
break;
}
}
- node = rb_next(&ref->rb_node);
- if (!node) {
- ret = 1;
- *next_ret = NULL;
- break;
- }
- ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
+ node = rb_next(node);
}
- return ret;
+ if (count) {
+ return 0;
+ } else if (start) {
+ /*
+ * we've gone to the end of the rbtree without finding any
+ * clusters. start from the beginning and try again
+ */
+ start = 0;
+ node = rb_first(&delayed_refs->root);
+ goto again;
+ }
+ return 1;
}
/*
delayed_refs = &trans->transaction->delayed_refs;
spin_lock(&delayed_refs->lock);
- ref = tree_search(&delayed_refs->root, bytenr, (u64)-1);
+ ref = tree_search(&delayed_refs->root, bytenr, (u64)-1, NULL);
if (ref) {
prev_node = rb_prev(&ref->rb_node);
if (!prev_node)
}
spin_lock(&delayed_refs->lock);
- ref = tree_search(&delayed_refs->root, bytenr, (u64)-1);
+ ref = tree_search(&delayed_refs->root, bytenr, (u64)-1, NULL);
if (ref) {
head = btrfs_delayed_node_to_head(ref);
if (mutex_trylock(&head->mutex)) {
{
struct btrfs_delayed_ref_node *existing;
struct btrfs_delayed_ref *full_ref;
- struct btrfs_delayed_ref_head *head_ref;
+ struct btrfs_delayed_ref_head *head_ref = NULL;
struct btrfs_delayed_ref_root *delayed_refs;
int count_mod = 1;
int must_insert_reserved = 0;
* the head node stores the sum of all the mods, so dropping a ref
* should drop the sum in the head node by one.
*/
- if (parent == (u64)-1 && action == BTRFS_DROP_DELAYED_REF)
- count_mod = -1;
+ if (parent == (u64)-1) {
+ if (action == BTRFS_DROP_DELAYED_REF)
+ count_mod = -1;
+ else if (action == BTRFS_UPDATE_DELAYED_HEAD)
+ count_mod = 0;
+ }
/*
* BTRFS_ADD_DELAYED_EXTENT means that we need to update
if (btrfs_delayed_ref_is_head(ref)) {
head_ref = btrfs_delayed_node_to_head(ref);
head_ref->must_insert_reserved = must_insert_reserved;
+ INIT_LIST_HEAD(&head_ref->cluster);
mutex_init(&head_ref->mutex);
} else {
full_ref = btrfs_delayed_node_to_ref(ref);
*/
kfree(ref);
} else {
+ if (btrfs_delayed_ref_is_head(ref)) {
+ delayed_refs->num_heads++;
+ delayed_refs->num_heads_ready++;
+ }
delayed_refs->num_entries++;
trans->delayed_ref_updates++;
}
return 0;
}
+/*
+ * this does a simple search for the head node for a given extent.
+ * It must be called with the delayed ref spinlock held, and it returns
+ * the head node if any where found, or NULL if not.
+ */
+struct btrfs_delayed_ref_head *
+btrfs_find_delayed_ref_head(struct btrfs_trans_handle *trans, u64 bytenr)
+{
+ struct btrfs_delayed_ref_node *ref;
+ struct btrfs_delayed_ref_root *delayed_refs;
+
+ delayed_refs = &trans->transaction->delayed_refs;
+ ref = tree_search(&delayed_refs->root, bytenr, (u64)-1, NULL);
+ if (ref)
+ return btrfs_delayed_node_to_head(ref);
+ return NULL;
+}
+
/*
* add a delayed ref to the tree. This does all of the accounting required
* to make sure the delayed ref is eventually processed before this
*/
ret = __btrfs_add_delayed_ref(trans, &head_ref->node, bytenr, num_bytes,
(u64)-1, 0, 0, 0,
- BTRFS_ADD_DELAYED_REF, 0);
+ BTRFS_UPDATE_DELAYED_HEAD, 0);
BUG_ON(ret);
ret = __btrfs_add_delayed_ref(trans, &ref->node, bytenr, num_bytes,
projects / linux-beck.git / blobdiff