[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;

	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 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;
	155
	156	write_unlock(&tree->lock);
	157	if (node)
	158	kfree(entry);
2da98f00 CM	159	else
2da98f00 CM	160	igrab(inode);
dc17ff8f CM	161	return 0;
	162	}
	163
	164	int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
4d5e74bc CM	165	u64 root_objectid, u64 objectid,
4d5e74bc CM	166	struct inode **inode)
dc17ff8f CM	167	{
	168	struct tree_entry *entry;
	169	struct rb_node *node;
	170
	171	write_lock(&tree->lock);
	172	node = tree_search(&tree->tree, root_objectid, objectid);
	173	if (!node) {
	174	write_unlock(&tree->lock);
	175	return 0;
	176	}
	177	entry = rb_entry(node, struct tree_entry, rb_node);
	178
	179	while(comp_entry(entry, root_objectid, objectid) >= 0) {
	180	node = rb_next(node);
	181	if (!node)
	182	break;
	183	entry = rb_entry(node, struct tree_entry, rb_node);
	184	}
	185	if (!node) {
	186	write_unlock(&tree->lock);
	187	return 0;
	188	}
	189
	190	*root_objectid = entry->root_objectid;
4d5e74bc CM	191	*inode = entry->inode;
4d5e74bc CM	192	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	193	*objectid = entry->objectid;
	194	write_unlock(&tree->lock);
	195	return 1;
	196	}
	197
	198	int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
4d5e74bc CM	199	u64 root_objectid, u64 objectid,
4d5e74bc CM	200	struct inode **inode)
dc17ff8f CM	201	{
	202	struct tree_entry *entry;
	203	struct rb_node *node;
	204
	205	write_lock(&tree->lock);
	206	node = tree_search(&tree->tree, root_objectid, objectid);
	207	if (!node) {
	208	write_unlock(&tree->lock);
	209	return 0;
	210	}
	211
	212	entry = rb_entry(node, struct tree_entry, rb_node);
	213	while(comp_entry(entry, root_objectid, objectid) >= 0) {
	214	node = rb_next(node);
	215	if (!node)
	216	break;
	217	entry = rb_entry(node, struct tree_entry, rb_node);
	218	}
	219	if (!node) {
	220	write_unlock(&tree->lock);
	221	return 0;
	222	}
	223
	224	*root_objectid = entry->root_objectid;
	225	*objectid = entry->objectid;
4d5e74bc CM	226	*inode = entry->inode;
4d5e74bc CM	227	atomic_inc(&entry->inode->i_count);
dc17ff8f CM	228	rb_erase(node, &tree->tree);
	229	write_unlock(&tree->lock);
	230	kfree(entry);
	231	return 1;
	232	}
cee36a03	233
e1b81e67	234	static void __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
2da98f00	235	struct inode *inode,
cee36a03 CM	236	u64 root_objectid, u64 objectid)
	237	{
	238	struct tree_entry *entry;
	239	struct rb_node *node;
	240	struct rb_node *prev;
	241
	242	write_lock(&tree->lock);
	243	node = __tree_search(&tree->tree, root_objectid, objectid, &prev);
	244	if (!node) {
	245	write_unlock(&tree->lock);
e1b81e67	246	return;
cee36a03 CM	247	}
cee36a03 CM	248	rb_erase(node, &tree->tree);
2da98f00	249	BTRFS_I(inode)->ordered_trans = 0;
cee36a03	250	write_unlock(&tree->lock);
e1b81e67	251	atomic_dec(&inode->i_count);
cee36a03 CM	252	entry = rb_entry(node, struct tree_entry, rb_node);
cee36a03 CM	253	kfree(entry);
e1b81e67	254	return;
cee36a03 CM	255	}
cee36a03 CM	256
594a24eb	257	void btrfs_del_ordered_inode(struct inode *inode, int force)
cee36a03 CM	258	{
	259	struct btrfs_root *root = BTRFS_I(inode)->root;
	260	u64 root_objectid = root->root_key.objectid;
e1b81e67 M	261
	262	if (!BTRFS_I(inode)->ordered_trans) {
	263	return;
	264	}
	265
594a24eb CM	266	if (!force && (mapping_tagged(inode->i_mapping, PAGECACHE_TAG_DIRTY) \|\|
594a24eb CM	267	mapping_tagged(inode->i_mapping, PAGECACHE_TAG_WRITEBACK)))
e1b81e67	268	return;
cee36a03 CM	269
	270	spin_lock(&root->fs_info->new_trans_lock);
	271	if (root->fs_info->running_transaction) {
	272	struct btrfs_ordered_inode_tree *tree;
	273	tree = &root->fs_info->running_transaction->ordered_inode_tree;
e1b81e67	274	__btrfs_del_ordered_inode(tree, inode, root_objectid,
2da98f00	275	inode->i_ino);
cee36a03 CM	276	}
cee36a03 CM	277	spin_unlock(&root->fs_info->new_trans_lock);
cee36a03 CM	278	}
cee36a03 CM	279
81d7ed29 CM	280	int btrfs_ordered_throttle(struct btrfs_root root, struct inode inode)
	281	{
	282	struct btrfs_transaction *cur = root->fs_info->running_transaction;
	283	while(cur == root->fs_info->running_transaction &&
	284	atomic_read(&BTRFS_I(inode)->ordered_writeback)) {
	285	#if LINUX_VERSION_CODE > KERNEL_VERSION(2,6,18)
	286	congestion_wait(WRITE, HZ/20);
	287	#else
	288	blk_congestion_wait(WRITE, HZ/20);
	289	#endif
	290	}
	291	return 0;
	292	}