/* * Copyright (C) 2007 Oracle. All rights reserved. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public * License v2 as published by the Free Software Foundation. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this program; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 021110-1307, USA. */ #include <linux/gfp.h> #include <linux/slab.h> #include "ctree.h" #include "transaction.h" #include "btrfs_inode.h" struct tree_entry { u64 root_objectid; u64 objectid; struct inode *inode; struct rb_node rb_node; }; /* * returns > 0 if entry passed (root, objectid) is > entry, * < 0 if (root, objectid) < entry and zero if they are equal */ static int comp_entry(struct tree_entry *entry, u64 root_objectid, u64 objectid) { if (root_objectid < entry->root_objectid) return -1; if (root_objectid > entry->root_objectid) return 1; if (objectid < entry->objectid) return -1; if (objectid > entry->objectid) return 1; return 0; } static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid, u64 objectid, struct rb_node *node) { struct rb_node ** p = &root->rb_node; struct rb_node * parent = NULL; struct tree_entry *entry; int comp; while(*p) { parent = *p; entry = rb_entry(parent, struct tree_entry, rb_node); comp = comp_entry(entry, root_objectid, objectid); if (comp < 0) p = &(*p)->rb_left; else if (comp > 0) p = &(*p)->rb_right; else return parent; } rb_link_node(node, parent, p); rb_insert_color(node, root); return NULL; } static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid, u64 objectid, struct rb_node **prev_ret) { struct rb_node * n = root->rb_node; struct rb_node *prev = NULL; struct tree_entry *entry; struct tree_entry *prev_entry = NULL; int comp; while(n) { entry = rb_entry(n, struct tree_entry, rb_node); prev = n; prev_entry = entry; comp = comp_entry(entry, root_objectid, objectid); if (comp < 0) n = n->rb_left; else if (comp > 0) n = n->rb_right; else return n; } if (!prev_ret) return NULL; while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) { prev = rb_next(prev); prev_entry = rb_entry(prev, struct tree_entry, rb_node); } *prev_ret = prev; return NULL; } static inline struct rb_node *tree_search(struct rb_root *root, u64 root_objectid, u64 objectid) { struct rb_node *prev; struct rb_node *ret; ret = __tree_search(root, root_objectid, objectid, &prev); if (!ret) return prev; return ret; } int btrfs_add_ordered_inode(struct inode *inode) { struct btrfs_root *root = BTRFS_I(inode)->root; u64 root_objectid = root->root_key.objectid; u64 transid = root->fs_info->running_transaction->transid; struct tree_entry *entry; struct rb_node *node; struct btrfs_ordered_inode_tree *tree; if (transid <= BTRFS_I(inode)->ordered_trans) return 0; tree = &root->fs_info->running_transaction->ordered_inode_tree; read_lock(&tree->lock); node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL); read_unlock(&tree->lock); if (node) { return 0; } entry = kmalloc(sizeof(*entry), GFP_NOFS); if (!entry) return -ENOMEM; write_lock(&tree->lock); entry->objectid = inode->i_ino; entry->root_objectid = root_objectid; entry->inode = inode; node = tree_insert(&tree->tree, root_objectid, inode->i_ino, &entry->rb_node); BTRFS_I(inode)->ordered_trans = transid; write_unlock(&tree->lock); if (node) kfree(entry); else igrab(inode); return 0; } int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, u64 *root_objectid, u64 *objectid, struct inode **inode) { struct tree_entry *entry; struct rb_node *node; write_lock(&tree->lock); node = tree_search(&tree->tree, *root_objectid, *objectid); if (!node) { write_unlock(&tree->lock); return 0; } entry = rb_entry(node, struct tree_entry, rb_node); while(comp_entry(entry, *root_objectid, *objectid) >= 0) { node = rb_next(node); if (!node) break; entry = rb_entry(node, struct tree_entry, rb_node); } if (!node) { write_unlock(&tree->lock); return 0; } *root_objectid = entry->root_objectid; *inode = entry->inode; atomic_inc(&entry->inode->i_count); *objectid = entry->objectid; write_unlock(&tree->lock); return 1; } int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree, u64 *root_objectid, u64 *objectid, struct inode **inode) { struct tree_entry *entry; struct rb_node *node; write_lock(&tree->lock); node = tree_search(&tree->tree, *root_objectid, *objectid); if (!node) { write_unlock(&tree->lock); return 0; } entry = rb_entry(node, struct tree_entry, rb_node); while(comp_entry(entry, *root_objectid, *objectid) >= 0) { node = rb_next(node); if (!node) break; entry = rb_entry(node, struct tree_entry, rb_node); } if (!node) { write_unlock(&tree->lock); return 0; } *root_objectid = entry->root_objectid; *objectid = entry->objectid; *inode = entry->inode; atomic_inc(&entry->inode->i_count); rb_erase(node, &tree->tree); write_unlock(&tree->lock); kfree(entry); return 1; } static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree, struct inode *inode, u64 root_objectid, u64 objectid) { struct tree_entry *entry; struct rb_node *node; struct rb_node *prev; write_lock(&tree->lock); node = __tree_search(&tree->tree, root_objectid, objectid, &prev); if (!node) { write_unlock(&tree->lock); return 0; } rb_erase(node, &tree->tree); BTRFS_I(inode)->ordered_trans = 0; write_unlock(&tree->lock); entry = rb_entry(node, struct tree_entry, rb_node); kfree(entry); return 1; } int btrfs_del_ordered_inode(struct inode *inode) { struct btrfs_root *root = BTRFS_I(inode)->root; u64 root_objectid = root->root_key.objectid; int ret = 0; spin_lock(&root->fs_info->new_trans_lock); if (root->fs_info->running_transaction) { struct btrfs_ordered_inode_tree *tree; tree = &root->fs_info->running_transaction->ordered_inode_tree; ret = __btrfs_del_ordered_inode(tree, inode, root_objectid, inode->i_ino); } spin_unlock(&root->fs_info->new_trans_lock); return ret; }