SAFE public projects git trees. - safe/jmp/linux-2.6/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 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