Pileus Git - ~andy/linux/blob - fs/btrfs/ordered-data.c

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