1 /* 2 * Copyright (C) 2007 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/gfp.h> 20 #include <linux/slab.h> 21 #include "ctree.h" 22 #include "transaction.h" 23 #include "btrfs_inode.h" 24 25 struct tree_entry { 26 u64 root_objectid; 27 u64 objectid; 28 struct inode *inode; 29 struct rb_node rb_node; 30 }; 31 32 /* 33 * returns > 0 if entry passed (root, objectid) is > entry, 34 * < 0 if (root, objectid) < entry and zero if they are equal 35 */ 36 static int comp_entry(struct tree_entry *entry, u64 root_objectid, 37 u64 objectid) 38 { 39 if (root_objectid < entry->root_objectid) 40 return -1; 41 if (root_objectid > entry->root_objectid) 42 return 1; 43 if (objectid < entry->objectid) 44 return -1; 45 if (objectid > entry->objectid) 46 return 1; 47 return 0; 48 } 49 50 static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid, 51 u64 objectid, struct rb_node *node) 52 { 53 struct rb_node ** p = &root->rb_node; 54 struct rb_node * parent = NULL; 55 struct tree_entry *entry; 56 int comp; 57 58 while(*p) { 59 parent = *p; 60 entry = rb_entry(parent, struct tree_entry, rb_node); 61 62 comp = comp_entry(entry, root_objectid, objectid); 63 if (comp < 0) 64 p = &(*p)->rb_left; 65 else if (comp > 0) 66 p = &(*p)->rb_right; 67 else 68 return parent; 69 } 70 71 rb_link_node(node, parent, p); 72 rb_insert_color(node, root); 73 return NULL; 74 } 75 76 static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid, 77 u64 objectid, struct rb_node **prev_ret) 78 { 79 struct rb_node * n = root->rb_node; 80 struct rb_node *prev = NULL; 81 struct tree_entry *entry; 82 struct tree_entry *prev_entry = NULL; 83 int comp; 84 85 while(n) { 86 entry = rb_entry(n, struct tree_entry, rb_node); 87 prev = n; 88 prev_entry = entry; 89 comp = comp_entry(entry, root_objectid, objectid); 90 91 if (comp < 0) 92 n = n->rb_left; 93 else if (comp > 0) 94 n = n->rb_right; 95 else 96 return n; 97 } 98 if (!prev_ret) 99 return NULL; 100 101 while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) { 102 prev = rb_next(prev); 103 prev_entry = rb_entry(prev, struct tree_entry, rb_node); 104 } 105 *prev_ret = prev; 106 return NULL; 107 } 108 109 static inline struct rb_node *tree_search(struct rb_root *root, 110 u64 root_objectid, u64 objectid) 111 { 112 struct rb_node *prev; 113 struct rb_node *ret; 114 ret = __tree_search(root, root_objectid, objectid, &prev); 115 if (!ret) 116 return prev; 117 return ret; 118 } 119 120 int btrfs_add_ordered_inode(struct inode *inode) 121 { 122 struct btrfs_root *root = BTRFS_I(inode)->root; 123 u64 root_objectid = root->root_key.objectid; 124 u64 transid = root->fs_info->running_transaction->transid; 125 struct tree_entry *entry; 126 struct rb_node *node; 127 struct btrfs_ordered_inode_tree *tree; 128 129 if (transid <= BTRFS_I(inode)->ordered_trans) 130 return 0; 131 132 tree = &root->fs_info->running_transaction->ordered_inode_tree; 133 134 read_lock(&tree->lock); 135 node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL); 136 read_unlock(&tree->lock); 137 if (node) { 138 return 0; 139 } 140 141 entry = kmalloc(sizeof(*entry), GFP_NOFS); 142 if (!entry) 143 return -ENOMEM; 144 145 write_lock(&tree->lock); 146 entry->objectid = inode->i_ino; 147 entry->root_objectid = root_objectid; 148 entry->inode = inode; 149 150 node = tree_insert(&tree->tree, root_objectid, 151 inode->i_ino, &entry->rb_node); 152 153 BTRFS_I(inode)->ordered_trans = transid; 154 155 write_unlock(&tree->lock); 156 if (node) 157 kfree(entry); 158 else 159 igrab(inode); 160 return 0; 161 } 162 163 int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, 164 u64 *root_objectid, u64 *objectid, 165 struct inode **inode) 166 { 167 struct tree_entry *entry; 168 struct rb_node *node; 169 170 write_lock(&tree->lock); 171 node = tree_search(&tree->tree, *root_objectid, *objectid); 172 if (!node) { 173 write_unlock(&tree->lock); 174 return 0; 175 } 176 entry = rb_entry(node, struct tree_entry, rb_node); 177 178 while(comp_entry(entry, *root_objectid, *objectid) >= 0) { 179 node = rb_next(node); 180 if (!node) 181 break; 182 entry = rb_entry(node, struct tree_entry, rb_node); 183 } 184 if (!node) { 185 write_unlock(&tree->lock); 186 return 0; 187 } 188 189 *root_objectid = entry->root_objectid; 190 *inode = entry->inode; 191 atomic_inc(&entry->inode->i_count); 192 *objectid = entry->objectid; 193 write_unlock(&tree->lock); 194 return 1; 195 } 196 197 int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, 198 u64 *root_objectid, u64 *objectid, 199 struct inode **inode) 200 { 201 struct tree_entry *entry; 202 struct rb_node *node; 203 204 write_lock(&tree->lock); 205 node = tree_search(&tree->tree, *root_objectid, *objectid); 206 if (!node) { 207 write_unlock(&tree->lock); 208 return 0; 209 } 210 211 entry = rb_entry(node, struct tree_entry, rb_node); 212 while(comp_entry(entry, *root_objectid, *objectid) >= 0) { 213 node = rb_next(node); 214 if (!node) 215 break; 216 entry = rb_entry(node, struct tree_entry, rb_node); 217 } 218 if (!node) { 219 write_unlock(&tree->lock); 220 return 0; 221 } 222 223 *root_objectid = entry->root_objectid; 224 *objectid = entry->objectid; 225 *inode = entry->inode; 226 atomic_inc(&entry->inode->i_count); 227 rb_erase(node, &tree->tree); 228 write_unlock(&tree->lock); 229 kfree(entry); 230 return 1; 231 } 232 233 static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree, 234 struct inode *inode, 235 u64 root_objectid, u64 objectid) 236 { 237 struct tree_entry *entry; 238 struct rb_node *node; 239 struct rb_node *prev; 240 241 write_lock(&tree->lock); 242 node = __tree_search(&tree->tree, root_objectid, objectid, &prev); 243 if (!node) { 244 write_unlock(&tree->lock); 245 return 0; 246 } 247 rb_erase(node, &tree->tree); 248 BTRFS_I(inode)->ordered_trans = 0; 249 write_unlock(&tree->lock); 250 entry = rb_entry(node, struct tree_entry, rb_node); 251 kfree(entry); 252 return 1; 253 } 254 255 int btrfs_del_ordered_inode(struct inode *inode) 256 { 257 struct btrfs_root *root = BTRFS_I(inode)->root; 258 u64 root_objectid = root->root_key.objectid; 259 int ret = 0; 260 261 spin_lock(&root->fs_info->new_trans_lock); 262 if (root->fs_info->running_transaction) { 263 struct btrfs_ordered_inode_tree *tree; 264 tree = &root->fs_info->running_transaction->ordered_inode_tree; 265 ret = __btrfs_del_ordered_inode(tree, inode, root_objectid, 266 inode->i_ino); 267 } 268 spin_unlock(&root->fs_info->new_trans_lock); 269 return ret; 270 } 271 272