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