Merge branch 'linus' into cont_syslog

[safe/jmp/linux-2.6] / fs / btrfs / ref-cache.c

diff --git a/fs/btrfs/ref-cache.c b/fs/btrfs/ref-cache.c
index 272b989..a97314c 100644 (file)
--- a/fs/btrfs/ref-cache.c
+++ b/fs/btrfs/ref-cache.c
@@ -17,10 +17,22 @@
  */
 
 #include <linux/sched.h>
+#include <linux/slab.h>
+#include <linux/sort.h>
 #include "ctree.h"
 #include "ref-cache.h"
 #include "transaction.h"
 
+/*
+ * leaf refs are used to cache the information about which extents
+ * a given leaf has references on.  This allows us to process that leaf
+ * in btrfs_drop_snapshot without needing to read it back from disk.
+ */
+
+/*
+ * kmalloc a leaf reference struct and update the counters for the
+ * total ref cache size
+ */
 struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root,
                                            int nr_extents)
 {
@@ -40,6 +52,10 @@ struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(struct btrfs_root *root,
        return ref;
 }
 
+/*
+ * free a leaf reference struct and update the counters for the
+ * total ref cache size
+ */
 void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
 {
        if (!ref)
@@ -60,14 +76,13 @@ void btrfs_free_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
 static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
                                   struct rb_node *node)
 {
-       struct rb_node ** p = &root->rb_node;
-       struct rb_node * parent = NULL;
+       struct rb_node **p = &root->rb_node;
+       struct rb_node *parent = NULL;
        struct btrfs_leaf_ref *entry;
 
-       while(*p) {
+       while (*p) {
                parent = *p;
                entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node);
-               WARN_ON(!entry->in_tree);
 
                if (bytenr < entry->bytenr)
                        p = &(*p)->rb_left;
@@ -78,7 +93,6 @@ static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
        }
 
        entry = rb_entry(node, struct btrfs_leaf_ref, rb_node);
-       entry->in_tree = 1;
        rb_link_node(node, parent, p);
        rb_insert_color(node, root);
        return NULL;
@@ -86,10 +100,10 @@ static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
 
 static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
 {
-       struct rb_node * n = root->rb_node;
+       struct rb_node *n = root->rb_node;
        struct btrfs_leaf_ref *entry;
 
-       while(n) {
+       while (n) {
                entry = rb_entry(n, struct btrfs_leaf_ref, rb_node);
                WARN_ON(!entry->in_tree);
 
@@ -103,23 +117,29 @@ static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
        return NULL;
 }
 
-int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen)
+int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen,
+                          int shared)
 {
        struct btrfs_leaf_ref *ref = NULL;
        struct btrfs_leaf_ref_tree *tree = root->ref_tree;
 
+       if (shared)
+               tree = &root->fs_info->shared_ref_tree;
        if (!tree)
                return 0;
 
        spin_lock(&tree->lock);
-       while(!list_empty(&tree->list)) {
+       while (!list_empty(&tree->list)) {
                ref = list_entry(tree->list.next, struct btrfs_leaf_ref, list);
-               BUG_ON(!ref->in_tree);
+               BUG_ON(ref->tree != tree);
                if (ref->root_gen > max_root_gen)
                        break;
+               if (!xchg(&ref->in_tree, 0)) {
+                       cond_resched_lock(&tree->lock);
+                       continue;
+               }
 
                rb_erase(&ref->rb_node, &tree->root);
-               ref->in_tree = 0;
                list_del_init(&ref->list);
 
                spin_unlock(&tree->lock);
@@ -131,53 +151,78 @@ int btrfs_remove_leaf_refs(struct btrfs_root *root, u64 max_root_gen)
        return 0;
 }
 
+/*
+ * find the leaf ref for a given extent.  This returns the ref struct with
+ * a usage reference incremented
+ */
 struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root,
                                             u64 bytenr)
 {
        struct rb_node *rb;
        struct btrfs_leaf_ref *ref = NULL;
        struct btrfs_leaf_ref_tree *tree = root->ref_tree;
-
-       if (!tree)
-               return NULL;
-
-       spin_lock(&tree->lock);
-       rb = tree_search(&tree->root, bytenr);
-       if (rb)
-               ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
-       if (ref)
-               atomic_inc(&ref->usage);
-       spin_unlock(&tree->lock);
-       return ref;
+again:
+       if (tree) {
+               spin_lock(&tree->lock);
+               rb = tree_search(&tree->root, bytenr);
+               if (rb)
+                       ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node);
+               if (ref)
+                       atomic_inc(&ref->usage);
+               spin_unlock(&tree->lock);
+               if (ref)
+                       return ref;
+       }
+       if (tree != &root->fs_info->shared_ref_tree) {
+               tree = &root->fs_info->shared_ref_tree;
+               goto again;
+       }
+       return NULL;
 }
 
-int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
+/*
+ * add a fully filled in leaf ref struct
+ * remove all the refs older than a given root generation
+ */
+int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref,
+                      int shared)
 {
        int ret = 0;
        struct rb_node *rb;
        struct btrfs_leaf_ref_tree *tree = root->ref_tree;
 
+       if (shared)
+               tree = &root->fs_info->shared_ref_tree;
+
        spin_lock(&tree->lock);
        rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node);
        if (rb) {
                ret = -EEXIST;
        } else {
                atomic_inc(&ref->usage);
+               ref->tree = tree;
+               ref->in_tree = 1;
                list_add_tail(&ref->list, &tree->list);
        }
        spin_unlock(&tree->lock);
        return ret;
 }
 
+/*
+ * remove a single leaf ref from the tree.  This drops the ref held by the tree
+ * only
+ */
 int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref)
 {
-       struct btrfs_leaf_ref_tree *tree = root->ref_tree;
+       struct btrfs_leaf_ref_tree *tree;
+
+       if (!xchg(&ref->in_tree, 0))
+               return 0;
 
-       BUG_ON(!ref->in_tree);
+       tree = ref->tree;
        spin_lock(&tree->lock);
 
        rb_erase(&ref->rb_node, &tree->root);
-       ref->in_tree = 0;
        list_del_init(&ref->list);
 
        spin_unlock(&tree->lock);