[linux-2.6-block.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 <linux/blkdev.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;
	if (!node)
		igrab(inode);

	write_unlock(&tree->lock);

	if (node)
		kfree(entry);
	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 void __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;
	}
	rb_erase(node, &tree->tree);
	BTRFS_I(inode)->ordered_trans = 0;
	write_unlock(&tree->lock);
	atomic_dec(&inode->i_count);
	entry = rb_entry(node, struct tree_entry, rb_node);
	kfree(entry);
	return;
}

void btrfs_del_ordered_inode(struct inode *inode, int force)
{
	struct btrfs_root *root = BTRFS_I(inode)->root;
	u64 root_objectid = root->root_key.objectid;

	if (!BTRFS_I(inode)->ordered_trans) {
		return;
	}

	if (!force && (mapping_tagged(inode->i_mapping, PAGECACHE_TAG_DIRTY) ||
	    mapping_tagged(inode->i_mapping, PAGECACHE_TAG_WRITEBACK)))
		return;

	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;
		 __btrfs_del_ordered_inode(tree, inode, root_objectid,
						inode->i_ino);
	}
	spin_unlock(&root->fs_info->new_trans_lock);
}

int btrfs_ordered_throttle(struct btrfs_root *root, struct inode *inode)
{
	struct btrfs_transaction *cur = root->fs_info->running_transaction;
	while(cur == root->fs_info->running_transaction &&
	      atomic_read(&BTRFS_I(inode)->ordered_writeback)) {
#if LINUX_VERSION_CODE > KERNEL_VERSION(2,6,18)
		congestion_wait(WRITE, HZ/20);
#else
		blk_congestion_wait(WRITE, HZ/20);
#endif
	}
	return 0;
}
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>
d6bfde87	21	#include <linux/blkdev.h>
dc17ff8f CM	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;
4d5e74bc	29	struct inode *inode;
dc17ff8f CM	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;
4d5e74bc	149	entry->inode = inode;
dc17ff8f CM	150
	151	node = tree_insert(&tree->tree, root_objectid,
	152	inode->i_ino, &entry->rb_node);
	153
	154	BTRFS_I(inode)->ordered_trans = transid;
1b1e2135 CM	155	if (!node)
1b1e2135 CM	156	igrab(inode);
dc17ff8f CM	157
dc17ff8f CM	158	write_unlock(&tree->lock);
1b1e2135	159
dc17ff8f CM	160	if (node)
	161	kfree(entry);
	162	return 0;
	163	}
	164
	165	int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
4d5e74bc CM	166	u64 root_objectid, u64 objectid,
4d5e74bc CM	167	struct inode **inode)
dc17ff8f CM	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;
4d5e74bc CM	192	*inode = entry->inode;
4d5e74bc CM	193	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	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,
4d5e74bc CM	200	u64 root_objectid, u64 objectid,
4d5e74bc CM	201	struct inode **inode)
dc17ff8f CM	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;
4d5e74bc CM	227	*inode = entry->inode;
4d5e74bc CM	228	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	229	rb_erase(node, &tree->tree);
	230	write_unlock(&tree->lock);
	231	kfree(entry);
	232	return 1;
	233	}
cee36a03	234
e1b81e67	235	static void __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
2da98f00	236	struct inode *inode,
cee36a03 CM	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);
e1b81e67	247	return;
cee36a03 CM	248	}
cee36a03 CM	249	rb_erase(node, &tree->tree);
2da98f00	250	BTRFS_I(inode)->ordered_trans = 0;
cee36a03	251	write_unlock(&tree->lock);
e1b81e67	252	atomic_dec(&inode->i_count);
cee36a03 CM	253	entry = rb_entry(node, struct tree_entry, rb_node);
cee36a03 CM	254	kfree(entry);
e1b81e67	255	return;
cee36a03 CM	256	}
cee36a03 CM	257
594a24eb	258	void btrfs_del_ordered_inode(struct inode *inode, int force)
cee36a03 CM	259	{
	260	struct btrfs_root *root = BTRFS_I(inode)->root;
	261	u64 root_objectid = root->root_key.objectid;
e1b81e67 M	262
	263	if (!BTRFS_I(inode)->ordered_trans) {
	264	return;
	265	}
	266
594a24eb CM	267	if (!force && (mapping_tagged(inode->i_mapping, PAGECACHE_TAG_DIRTY) \|\|
594a24eb CM	268	mapping_tagged(inode->i_mapping, PAGECACHE_TAG_WRITEBACK)))
e1b81e67	269	return;
cee36a03 CM	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;
e1b81e67	275	__btrfs_del_ordered_inode(tree, inode, root_objectid,
2da98f00	276	inode->i_ino);
cee36a03 CM	277	}
cee36a03 CM	278	spin_unlock(&root->fs_info->new_trans_lock);
cee36a03 CM	279	}
cee36a03 CM	280
81d7ed29 CM	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	}