[net-next-2.6.git] / fs / btrfs / ordered-data.c

/*
 * 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;
}
Commit	Line	Data
dc17ff8f CM	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;
4d5e74bc	28	struct inode *inode;
dc17ff8f CM	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;
4d5e74bc	148	entry->inode = inode;
dc17ff8f CM	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);
2da98f00 CM	158	else
2da98f00 CM	159	igrab(inode);
dc17ff8f CM	160	return 0;
	161	}
	162
	163	int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
4d5e74bc CM	164	u64 root_objectid, u64 objectid,
4d5e74bc CM	165	struct inode **inode)
dc17ff8f CM	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;
4d5e74bc CM	190	*inode = entry->inode;
4d5e74bc CM	191	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	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,
4d5e74bc CM	198	u64 root_objectid, u64 objectid,
4d5e74bc CM	199	struct inode **inode)
dc17ff8f CM	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;
4d5e74bc CM	225	*inode = entry->inode;
4d5e74bc CM	226	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	227	rb_erase(node, &tree->tree);
	228	write_unlock(&tree->lock);
	229	kfree(entry);
	230	return 1;
	231	}
cee36a03 CM	232
cee36a03 CM	233	static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
2da98f00	234	struct inode *inode,
cee36a03 CM	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);
2da98f00	248	BTRFS_I(inode)->ordered_trans = 0;
cee36a03 CM	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;
2da98f00	259	int ret = 0;
cee36a03 CM	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;
2da98f00 CM	265	ret = __btrfs_del_ordered_inode(tree, inode, root_objectid,
2da98f00 CM	266	inode->i_ino);
cee36a03 CM	267	}
cee36a03 CM	268	spin_unlock(&root->fs_info->new_trans_lock);
2da98f00	269	return ret;
cee36a03 CM	270	}
cee36a03 CM	271