Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2008 Oracle. All rights reserved. |
| 3 | * |
| 4 | * This program is free software; you can redistribute it and/or |
| 5 | * modify it under the terms of the GNU General Public |
| 6 | * License v2 as published by the Free Software Foundation. |
| 7 | * |
| 8 | * This program is distributed in the hope that it will be useful, |
| 9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 11 | * General Public License for more details. |
| 12 | * |
| 13 | * You should have received a copy of the GNU General Public |
| 14 | * License along with this program; if not, write to the |
| 15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
| 16 | * Boston, MA 021110-1307, USA. |
| 17 | */ |
| 18 | |
| 19 | #include <linux/sched.h> |
| 20 | #include "ctree.h" |
| 21 | #include "ref-cache.h" |
| 22 | #include "transaction.h" |
| 23 | |
| 24 | struct btrfs_leaf_ref *btrfs_alloc_leaf_ref(int nr_extents) |
| 25 | { |
| 26 | struct btrfs_leaf_ref *ref; |
| 27 | |
| 28 | ref = kmalloc(btrfs_leaf_ref_size(nr_extents), GFP_NOFS); |
| 29 | if (ref) { |
| 30 | memset(ref, 0, sizeof(*ref)); |
| 31 | atomic_set(&ref->usage, 1); |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 32 | INIT_LIST_HEAD(&ref->list); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 33 | } |
| 34 | return ref; |
| 35 | } |
| 36 | |
| 37 | void btrfs_free_leaf_ref(struct btrfs_leaf_ref *ref) |
| 38 | { |
| 39 | if (!ref) |
| 40 | return; |
| 41 | WARN_ON(atomic_read(&ref->usage) == 0); |
| 42 | if (atomic_dec_and_test(&ref->usage)) { |
| 43 | BUG_ON(ref->in_tree); |
| 44 | kfree(ref); |
| 45 | } |
| 46 | } |
| 47 | |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 48 | static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr, |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 49 | struct rb_node *node) |
| 50 | { |
| 51 | struct rb_node ** p = &root->rb_node; |
| 52 | struct rb_node * parent = NULL; |
| 53 | struct btrfs_leaf_ref *entry; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 54 | |
| 55 | while(*p) { |
| 56 | parent = *p; |
| 57 | entry = rb_entry(parent, struct btrfs_leaf_ref, rb_node); |
| 58 | WARN_ON(!entry->in_tree); |
| 59 | |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 60 | if (bytenr < entry->bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 61 | p = &(*p)->rb_left; |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 62 | else if (bytenr > entry->bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 63 | p = &(*p)->rb_right; |
| 64 | else |
| 65 | return parent; |
| 66 | } |
| 67 | |
| 68 | entry = rb_entry(node, struct btrfs_leaf_ref, rb_node); |
| 69 | entry->in_tree = 1; |
| 70 | rb_link_node(node, parent, p); |
| 71 | rb_insert_color(node, root); |
| 72 | return NULL; |
| 73 | } |
| 74 | |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 75 | static struct rb_node *tree_search(struct rb_root *root, u64 bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 76 | { |
| 77 | struct rb_node * n = root->rb_node; |
| 78 | struct btrfs_leaf_ref *entry; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 79 | |
| 80 | while(n) { |
| 81 | entry = rb_entry(n, struct btrfs_leaf_ref, rb_node); |
| 82 | WARN_ON(!entry->in_tree); |
| 83 | |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 84 | if (bytenr < entry->bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 85 | n = n->rb_left; |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 86 | else if (bytenr > entry->bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 87 | n = n->rb_right; |
| 88 | else |
| 89 | return n; |
| 90 | } |
| 91 | return NULL; |
| 92 | } |
| 93 | |
| 94 | int btrfs_remove_leaf_refs(struct btrfs_root *root) |
| 95 | { |
| 96 | struct rb_node *rb; |
| 97 | struct btrfs_leaf_ref *ref = NULL; |
| 98 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
| 99 | |
| 100 | if (!tree) |
| 101 | return 0; |
| 102 | |
| 103 | spin_lock(&tree->lock); |
| 104 | while(!btrfs_leaf_ref_tree_empty(tree)) { |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 105 | rb = rb_first(&tree->root); |
| 106 | ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node); |
| 107 | rb_erase(&ref->rb_node, &tree->root); |
| 108 | ref->in_tree = 0; |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 109 | list_del_init(&ref->list); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 110 | |
| 111 | spin_unlock(&tree->lock); |
| 112 | |
| 113 | btrfs_free_leaf_ref(ref); |
| 114 | |
| 115 | cond_resched(); |
| 116 | spin_lock(&tree->lock); |
| 117 | } |
| 118 | spin_unlock(&tree->lock); |
| 119 | return 0; |
| 120 | } |
| 121 | |
| 122 | struct btrfs_leaf_ref *btrfs_lookup_leaf_ref(struct btrfs_root *root, |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 123 | u64 bytenr) |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 124 | { |
| 125 | struct rb_node *rb; |
| 126 | struct btrfs_leaf_ref *ref = NULL; |
| 127 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
| 128 | |
| 129 | if (!tree) |
| 130 | return NULL; |
| 131 | |
| 132 | spin_lock(&tree->lock); |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 133 | rb = tree_search(&tree->root, bytenr); |
| 134 | if (rb) |
| 135 | ref = rb_entry(rb, struct btrfs_leaf_ref, rb_node); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 136 | if (ref) |
| 137 | atomic_inc(&ref->usage); |
| 138 | spin_unlock(&tree->lock); |
| 139 | return ref; |
| 140 | } |
| 141 | |
| 142 | int btrfs_add_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) |
| 143 | { |
| 144 | int ret = 0; |
| 145 | struct rb_node *rb; |
| 146 | size_t size = btrfs_leaf_ref_size(ref->nritems); |
| 147 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 148 | |
| 149 | spin_lock(&tree->lock); |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 150 | rb = tree_insert(&tree->root, ref->bytenr, &ref->rb_node); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 151 | if (rb) { |
| 152 | ret = -EEXIST; |
| 153 | } else { |
| 154 | spin_lock(&root->fs_info->ref_cache_lock); |
| 155 | root->fs_info->total_ref_cache_size += size; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 156 | spin_unlock(&root->fs_info->ref_cache_lock); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 157 | atomic_inc(&ref->usage); |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 158 | list_add_tail(&ref->list, &tree->list); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 159 | } |
| 160 | spin_unlock(&tree->lock); |
| 161 | return ret; |
| 162 | } |
| 163 | |
| 164 | int btrfs_remove_leaf_ref(struct btrfs_root *root, struct btrfs_leaf_ref *ref) |
| 165 | { |
| 166 | size_t size = btrfs_leaf_ref_size(ref->nritems); |
| 167 | struct btrfs_leaf_ref_tree *tree = root->ref_tree; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 168 | |
| 169 | BUG_ON(!ref->in_tree); |
| 170 | spin_lock(&tree->lock); |
| 171 | |
| 172 | spin_lock(&root->fs_info->ref_cache_lock); |
| 173 | root->fs_info->total_ref_cache_size -= size; |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 174 | spin_unlock(&root->fs_info->ref_cache_lock); |
| 175 | |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 176 | rb_erase(&ref->rb_node, &tree->root); |
| 177 | ref->in_tree = 0; |
Chris Mason | 017e536 | 2008-07-28 15:32:51 -0400 | [diff] [blame^] | 178 | list_del_init(&ref->list); |
Yan Zheng | 31153d8 | 2008-07-28 15:32:19 -0400 | [diff] [blame] | 179 | |
| 180 | spin_unlock(&tree->lock); |
| 181 | |
| 182 | btrfs_free_leaf_ref(ref); |
| 183 | return 0; |
| 184 | } |
| 185 | |