[linux-2.6-block.git] / fs / hfs / bnode.c

/*
 *  linux/fs/hfs/bnode.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handle basic btree node operations
 */

#include <linux/pagemap.h>
#include <linux/swap.h>

#include "btree.h"

#define REF_PAGES	0

void hfs_bnode_read(struct hfs_bnode *node, void *buf,
		int off, int len)
{
	struct page *page;

	off += node->page_offset;
	page = node->page[0];

	memcpy(buf, kmap(page) + off, len);
	kunmap(page);
}

u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off)
{
	__be16 data;
	// optimize later...
	hfs_bnode_read(node, &data, off, 2);
	return be16_to_cpu(data);
}

u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off)
{
	u8 data;
	// optimize later...
	hfs_bnode_read(node, &data, off, 1);
	return data;
}

void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off)
{
	struct hfs_btree *tree;
	int key_len;

	tree = node->tree;
	if (node->type == HFS_NODE_LEAF ||
	    tree->attributes & HFS_TREE_VARIDXKEYS)
		key_len = hfs_bnode_read_u8(node, off) + 1;
	else
		key_len = tree->max_key_len + 1;

	hfs_bnode_read(node, key, off, key_len);
}

void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len)
{
	struct page *page;

	off += node->page_offset;
	page = node->page[0];

	memcpy(kmap(page) + off, buf, len);
	kunmap(page);
	set_page_dirty(page);
}

void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data)
{
	__be16 v = cpu_to_be16(data);
	// optimize later...
	hfs_bnode_write(node, &v, off, 2);
}

void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data)
{
	// optimize later...
	hfs_bnode_write(node, &data, off, 1);
}

void hfs_bnode_clear(struct hfs_bnode *node, int off, int len)
{
	struct page *page;

	off += node->page_offset;
	page = node->page[0];

	memset(kmap(page) + off, 0, len);
	kunmap(page);
	set_page_dirty(page);
}

void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst,
		struct hfs_bnode *src_node, int src, int len)
{
	struct hfs_btree *tree;
	struct page *src_page, *dst_page;

	dprint(DBG_BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len);
	if (!len)
		return;
	tree = src_node->tree;
	src += src_node->page_offset;
	dst += dst_node->page_offset;
	src_page = src_node->page[0];
	dst_page = dst_node->page[0];

	memcpy(kmap(dst_page) + dst, kmap(src_page) + src, len);
	kunmap(src_page);
	kunmap(dst_page);
	set_page_dirty(dst_page);
}

void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len)
{
	struct page *page;
	void *ptr;

	dprint(DBG_BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len);
	if (!len)
		return;
	src += node->page_offset;
	dst += node->page_offset;
	page = node->page[0];
	ptr = kmap(page);
	memmove(ptr + dst, ptr + src, len);
	kunmap(page);
	set_page_dirty(page);
}

void hfs_bnode_dump(struct hfs_bnode *node)
{
	struct hfs_bnode_desc desc;
	__be32 cnid;
	int i, off, key_off;

	dprint(DBG_BNODE_MOD, "bnode: %d\n", node->this);
	hfs_bnode_read(node, &desc, 0, sizeof(desc));
	dprint(DBG_BNODE_MOD, "%d, %d, %d, %d, %d\n",
		be32_to_cpu(desc.next), be32_to_cpu(desc.prev),
		desc.type, desc.height, be16_to_cpu(desc.num_recs));

	off = node->tree->node_size - 2;
	for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) {
		key_off = hfs_bnode_read_u16(node, off);
		dprint(DBG_BNODE_MOD, " %d", key_off);
		if (i && node->type == HFS_NODE_INDEX) {
			int tmp;

			if (node->tree->attributes & HFS_TREE_VARIDXKEYS)
				tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1;
			else
				tmp = node->tree->max_key_len + 1;
			dprint(DBG_BNODE_MOD, " (%d,%d", tmp, hfs_bnode_read_u8(node, key_off));
			hfs_bnode_read(node, &cnid, key_off + tmp, 4);
			dprint(DBG_BNODE_MOD, ",%d)", be32_to_cpu(cnid));
		} else if (i && node->type == HFS_NODE_LEAF) {
			int tmp;

			tmp = hfs_bnode_read_u8(node, key_off);
			dprint(DBG_BNODE_MOD, " (%d)", tmp);
		}
	}
	dprint(DBG_BNODE_MOD, "\n");
}

void hfs_bnode_unlink(struct hfs_bnode *node)
{
	struct hfs_btree *tree;
	struct hfs_bnode *tmp;
	__be32 cnid;

	tree = node->tree;
	if (node->prev) {
		tmp = hfs_bnode_find(tree, node->prev);
		if (IS_ERR(tmp))
			return;
		tmp->next = node->next;
		cnid = cpu_to_be32(tmp->next);
		hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
		hfs_bnode_put(tmp);
	} else if (node->type == HFS_NODE_LEAF)
		tree->leaf_head = node->next;

	if (node->next) {
		tmp = hfs_bnode_find(tree, node->next);
		if (IS_ERR(tmp))
			return;
		tmp->prev = node->prev;
		cnid = cpu_to_be32(tmp->prev);
		hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4);
		hfs_bnode_put(tmp);
	} else if (node->type == HFS_NODE_LEAF)
		tree->leaf_tail = node->prev;

	// move down?
	if (!node->prev && !node->next) {
		printk("hfs_btree_del_level\n");
	}
	if (!node->parent) {
		tree->root = 0;
		tree->depth = 0;
	}
	set_bit(HFS_BNODE_DELETED, &node->flags);
}

static inline int hfs_bnode_hash(u32 num)
{
	num = (num >> 16) + num;
	num += num >> 8;
	return num & (NODE_HASH_SIZE - 1);
}

struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid)
{
	struct hfs_bnode *node;

	if (cnid >= tree->node_count) {
		printk("HFS: request for non-existent node %d in B*Tree\n", cnid);
		return NULL;
	}

	for (node = tree->node_hash[hfs_bnode_hash(cnid)];
	     node; node = node->next_hash) {
		if (node->this == cnid) {
			return node;
		}
	}
	return NULL;
}

static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid)
{
	struct super_block *sb;
	struct hfs_bnode *node, *node2;
	struct address_space *mapping;
	struct page *page;
	int size, block, i, hash;
	loff_t off;

	if (cnid >= tree->node_count) {
		printk("HFS: request for non-existent node %d in B*Tree\n", cnid);
		return NULL;
	}

	sb = tree->inode->i_sb;
	size = sizeof(struct hfs_bnode) + tree->pages_per_bnode *
		sizeof(struct page *);
	node = kmalloc(size, GFP_KERNEL);
	if (!node)
		return NULL;
	memset(node, 0, size);
	node->tree = tree;
	node->this = cnid;
	set_bit(HFS_BNODE_NEW, &node->flags);
	atomic_set(&node->refcnt, 1);
	dprint(DBG_BNODE_REFS, "new_node(%d:%d): 1\n",
	       node->tree->cnid, node->this);
	init_waitqueue_head(&node->lock_wq);
	spin_lock(&tree->hash_lock);
	node2 = hfs_bnode_findhash(tree, cnid);
	if (!node2) {
		hash = hfs_bnode_hash(cnid);
		node->next_hash = tree->node_hash[hash];
		tree->node_hash[hash] = node;
		tree->node_hash_cnt++;
	} else {
		spin_unlock(&tree->hash_lock);
		kfree(node);
		wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags));
		return node2;
	}
	spin_unlock(&tree->hash_lock);

	mapping = tree->inode->i_mapping;
	off = (loff_t)cnid * tree->node_size;
	block = off >> PAGE_CACHE_SHIFT;
	node->page_offset = off & ~PAGE_CACHE_MASK;
	for (i = 0; i < tree->pages_per_bnode; i++) {
		page = read_cache_page(mapping, block++, (filler_t *)mapping->a_ops->readpage, NULL);
		if (IS_ERR(page))
			goto fail;
		if (PageError(page)) {
			page_cache_release(page);
			goto fail;
		}
#if !REF_PAGES
		page_cache_release(page);
#endif
		node->page[i] = page;
	}

	return node;
fail:
	set_bit(HFS_BNODE_ERROR, &node->flags);
	return node;
}

void hfs_bnode_unhash(struct hfs_bnode *node)
{
	struct hfs_bnode **p;

	dprint(DBG_BNODE_REFS, "remove_node(%d:%d): %d\n",
		node->tree->cnid, node->this, atomic_read(&node->refcnt));
	for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)];
	     *p && *p != node; p = &(*p)->next_hash)
		;
	if (!*p)
		BUG();
	*p = node->next_hash;
	node->tree->node_hash_cnt--;
}

/* Load a particular node out of a tree */
struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)
{
	struct hfs_bnode *node;
	struct hfs_bnode_desc *desc;
	int i, rec_off, off, next_off;
	int entry_size, key_size;

	spin_lock(&tree->hash_lock);
	node = hfs_bnode_findhash(tree, num);
	if (node) {
		hfs_bnode_get(node);
		spin_unlock(&tree->hash_lock);
		wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags));
		if (test_bit(HFS_BNODE_ERROR, &node->flags))
			goto node_error;
		return node;
	}
	spin_unlock(&tree->hash_lock);
	node = __hfs_bnode_create(tree, num);
	if (!node)
		return ERR_PTR(-ENOMEM);
	if (test_bit(HFS_BNODE_ERROR, &node->flags))
		goto node_error;
	if (!test_bit(HFS_BNODE_NEW, &node->flags))
		return node;

	desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset);
	node->prev = be32_to_cpu(desc->prev);
	node->next = be32_to_cpu(desc->next);
	node->num_recs = be16_to_cpu(desc->num_recs);
	node->type = desc->type;
	node->height = desc->height;
	kunmap(node->page[0]);

	switch (node->type) {
	case HFS_NODE_HEADER:
	case HFS_NODE_MAP:
		if (node->height != 0)
			goto node_error;
		break;
	case HFS_NODE_LEAF:
		if (node->height != 1)
			goto node_error;
		break;
	case HFS_NODE_INDEX:
		if (node->height <= 1 || node->height > tree->depth)
			goto node_error;
		break;
	default:
		goto node_error;
	}

	rec_off = tree->node_size - 2;
	off = hfs_bnode_read_u16(node, rec_off);
	if (off != sizeof(struct hfs_bnode_desc))
		goto node_error;
	for (i = 1; i <= node->num_recs; off = next_off, i++) {
		rec_off -= 2;
		next_off = hfs_bnode_read_u16(node, rec_off);
		if (next_off <= off ||
		    next_off > tree->node_size ||
		    next_off & 1)
			goto node_error;
		entry_size = next_off - off;
		if (node->type != HFS_NODE_INDEX &&
		    node->type != HFS_NODE_LEAF)
			continue;
		key_size = hfs_bnode_read_u8(node, off) + 1;
		if (key_size >= entry_size /*|| key_size & 1*/)
			goto node_error;
	}
	clear_bit(HFS_BNODE_NEW, &node->flags);
	wake_up(&node->lock_wq);
	return node;

node_error:
	set_bit(HFS_BNODE_ERROR, &node->flags);
	clear_bit(HFS_BNODE_NEW, &node->flags);
	wake_up(&node->lock_wq);
	hfs_bnode_put(node);
	return ERR_PTR(-EIO);
}

void hfs_bnode_free(struct hfs_bnode *node)
{
	//int i;

	//for (i = 0; i < node->tree->pages_per_bnode; i++)
	//	if (node->page[i])
	//		page_cache_release(node->page[i]);
	kfree(node);
}

struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num)
{
	struct hfs_bnode *node;
	struct page **pagep;
	int i;

	spin_lock(&tree->hash_lock);
	node = hfs_bnode_findhash(tree, num);
	spin_unlock(&tree->hash_lock);
	if (node)
		BUG();
	node = __hfs_bnode_create(tree, num);
	if (!node)
		return ERR_PTR(-ENOMEM);
	if (test_bit(HFS_BNODE_ERROR, &node->flags)) {
		hfs_bnode_put(node);
		return ERR_PTR(-EIO);
	}

	pagep = node->page;
	memset(kmap(*pagep) + node->page_offset, 0,
	       min((int)PAGE_CACHE_SIZE, (int)tree->node_size));
	set_page_dirty(*pagep);
	kunmap(*pagep);
	for (i = 1; i < tree->pages_per_bnode; i++) {
		memset(kmap(*++pagep), 0, PAGE_CACHE_SIZE);
		set_page_dirty(*pagep);
		kunmap(*pagep);
	}
	clear_bit(HFS_BNODE_NEW, &node->flags);
	wake_up(&node->lock_wq);

	return node;
}

void hfs_bnode_get(struct hfs_bnode *node)
{
	if (node) {
		atomic_inc(&node->refcnt);
#if REF_PAGES
		{
		int i;
		for (i = 0; i < node->tree->pages_per_bnode; i++)
			get_page(node->page[i]);
		}
#endif
		dprint(DBG_BNODE_REFS, "get_node(%d:%d): %d\n",
		       node->tree->cnid, node->this, atomic_read(&node->refcnt));
	}
}

/* Dispose of resources used by a node */
void hfs_bnode_put(struct hfs_bnode *node)
{
	if (node) {
		struct hfs_btree *tree = node->tree;
		int i;

		dprint(DBG_BNODE_REFS, "put_node(%d:%d): %d\n",
		       node->tree->cnid, node->this, atomic_read(&node->refcnt));
		if (!atomic_read(&node->refcnt))
			BUG();
		if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) {
#if REF_PAGES
			for (i = 0; i < tree->pages_per_bnode; i++)
				put_page(node->page[i]);
#endif
			return;
		}
		for (i = 0; i < tree->pages_per_bnode; i++) {
			if (!node->page[i])
				continue;
			mark_page_accessed(node->page[i]);
#if REF_PAGES
			put_page(node->page[i]);
#endif
		}

		if (test_bit(HFS_BNODE_DELETED, &node->flags)) {
			hfs_bnode_unhash(node);
			spin_unlock(&tree->hash_lock);
			hfs_bmap_free(node);
			hfs_bnode_free(node);
			return;
		}
		spin_unlock(&tree->hash_lock);
	}
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hfs/bnode.c
	3	*
	4	* Copyright (C) 2001
	5	* Brad Boyer (flar@allandria.com)
	6	* (C) 2003 Ardis Technologies <roman@ardistech.com>
	7	*
	8	* Handle basic btree node operations
	9	*/
	10
	11	#include <linux/pagemap.h>
	12	#include <linux/swap.h>
	13
	14	#include "btree.h"
	15
	16	#define REF_PAGES 0
	17
	18	void hfs_bnode_read(struct hfs_bnode node, void buf,
	19	int off, int len)
	20	{
	21	struct page *page;
	22
	23	off += node->page_offset;
	24	page = node->page[0];
	25
	26	memcpy(buf, kmap(page) + off, len);
	27	kunmap(page);
	28	}
	29
	30	u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off)
	31	{
	32	__be16 data;
	33	// optimize later...
	34	hfs_bnode_read(node, &data, off, 2);
	35	return be16_to_cpu(data);
	36	}
	37
	38	u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off)
	39	{
	40	u8 data;
	41	// optimize later...
	42	hfs_bnode_read(node, &data, off, 1);
	43	return data;
	44	}
	45
	46	void hfs_bnode_read_key(struct hfs_bnode node, void key, int off)
	47	{
	48	struct hfs_btree *tree;
	49	int key_len;
	50
	51	tree = node->tree;
	52	if (node->type == HFS_NODE_LEAF \|\|
	53	tree->attributes & HFS_TREE_VARIDXKEYS)
	54	key_len = hfs_bnode_read_u8(node, off) + 1;
	55	else
	56	key_len = tree->max_key_len + 1;
	57
	58	hfs_bnode_read(node, key, off, key_len);
	59	}
	60
	61	void hfs_bnode_write(struct hfs_bnode node, void buf, int off, int len)
	62	{
	63	struct page *page;
	64
65	off += node->page_offset;
66	page = node->page[0];
67
68	memcpy(kmap(page) + off, buf, len);
69	kunmap(page);
70	set_page_dirty(page);
71	}
72
73	void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data)
74	{
75	__be16 v = cpu_to_be16(data);
76	// optimize later...
77	hfs_bnode_write(node, &v, off, 2);
78	}
79
80	void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data)
81	{
82	// optimize later...
83	hfs_bnode_write(node, &data, off, 1);
84	}
85
86	void hfs_bnode_clear(struct hfs_bnode *node, int off, int len)
87	{
88	struct page *page;
89
90	off += node->page_offset;
91	page = node->page[0];
92
93	memset(kmap(page) + off, 0, len);
94	kunmap(page);
95	set_page_dirty(page);
96	}
97
98	void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst,
99	struct hfs_bnode *src_node, int src, int len)
100	{
101	struct hfs_btree *tree;
102	struct page src_page, dst_page;
103
104	dprint(DBG_BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len);
105	if (!len)
106	return;
107	tree = src_node->tree;
108	src += src_node->page_offset;
109	dst += dst_node->page_offset;
110	src_page = src_node->page[0];
111	dst_page = dst_node->page[0];
112
113	memcpy(kmap(dst_page) + dst, kmap(src_page) + src, len);
114	kunmap(src_page);
115	kunmap(dst_page);
116	set_page_dirty(dst_page);
117	}
118
119	void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len)
120	{
121	struct page *page;
122	void *ptr;
123
124	dprint(DBG_BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len);
125	if (!len)
126	return;
127	src += node->page_offset;
128	dst += node->page_offset;
129	page = node->page[0];
130	ptr = kmap(page);
131	memmove(ptr + dst, ptr + src, len);
132	kunmap(page);
133	set_page_dirty(page);
134	}
135
136	void hfs_bnode_dump(struct hfs_bnode *node)
137	{
138	struct hfs_bnode_desc desc;
139	__be32 cnid;
140	int i, off, key_off;
141
142	dprint(DBG_BNODE_MOD, "bnode: %d\n", node->this);
143	hfs_bnode_read(node, &desc, 0, sizeof(desc));
144	dprint(DBG_BNODE_MOD, "%d, %d, %d, %d, %d\n",
145	be32_to_cpu(desc.next), be32_to_cpu(desc.prev),
146	desc.type, desc.height, be16_to_cpu(desc.num_recs));
147
148	off = node->tree->node_size - 2;
149	for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) {
150	key_off = hfs_bnode_read_u16(node, off);
151	dprint(DBG_BNODE_MOD, " %d", key_off);
152	if (i && node->type == HFS_NODE_INDEX) {
153	int tmp;
154
155	if (node->tree->attributes & HFS_TREE_VARIDXKEYS)
156	tmp = (hfs_bnode_read_u8(node, key_off) \| 1) + 1;
157	else
158	tmp = node->tree->max_key_len + 1;
159	dprint(DBG_BNODE_MOD, " (%d,%d", tmp, hfs_bnode_read_u8(node, key_off));
160	hfs_bnode_read(node, &cnid, key_off + tmp, 4);
161	dprint(DBG_BNODE_MOD, ",%d)", be32_to_cpu(cnid));
162	} else if (i && node->type == HFS_NODE_LEAF) {
163	int tmp;
164
165	tmp = hfs_bnode_read_u8(node, key_off);
166	dprint(DBG_BNODE_MOD, " (%d)", tmp);
167	}
168	}
169	dprint(DBG_BNODE_MOD, "\n");
170	}
171
172	void hfs_bnode_unlink(struct hfs_bnode *node)
173	{
174	struct hfs_btree *tree;
175	struct hfs_bnode *tmp;
176	__be32 cnid;
177
178	tree = node->tree;
179	if (node->prev) {
180	tmp = hfs_bnode_find(tree, node->prev);
181	if (IS_ERR(tmp))
182	return;
183	tmp->next = node->next;
184	cnid = cpu_to_be32(tmp->next);
185	hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
186	hfs_bnode_put(tmp);
187	} else if (node->type == HFS_NODE_LEAF)
188	tree->leaf_head = node->next;
189
190	if (node->next) {
191	tmp = hfs_bnode_find(tree, node->next);
192	if (IS_ERR(tmp))
193	return;
194	tmp->prev = node->prev;
195	cnid = cpu_to_be32(tmp->prev);
196	hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4);
197	hfs_bnode_put(tmp);
198	} else if (node->type == HFS_NODE_LEAF)
199	tree->leaf_tail = node->prev;
200
201	// move down?
202	if (!node->prev && !node->next) {
203	printk("hfs_btree_del_level\n");
204	}
205	if (!node->parent) {
206	tree->root = 0;
207	tree->depth = 0;
208	}
209	set_bit(HFS_BNODE_DELETED, &node->flags);
210	}
211
212	static inline int hfs_bnode_hash(u32 num)
213	{
214	num = (num >> 16) + num;
215	num += num >> 8;
216	return num & (NODE_HASH_SIZE - 1);
217	}
218
219	struct hfs_bnode hfs_bnode_findhash(struct hfs_btree tree, u32 cnid)
220	{
221	struct hfs_bnode *node;
222
223	if (cnid >= tree->node_count) {
224	printk("HFS: request for non-existent node %d in B*Tree\n", cnid);
225	return NULL;
226	}
227
228	for (node = tree->node_hash[hfs_bnode_hash(cnid)];
229	node; node = node->next_hash) {
230	if (node->this == cnid) {
231	return node;
232	}
233	}
234	return NULL;
235	}
236
237	static struct hfs_bnode __hfs_bnode_create(struct hfs_btree tree, u32 cnid)
238	{
239	struct super_block *sb;
240	struct hfs_bnode node, node2;
241	struct address_space *mapping;
242	struct page *page;
243	int size, block, i, hash;
244	loff_t off;
245
246	if (cnid >= tree->node_count) {
247	printk("HFS: request for non-existent node %d in B*Tree\n", cnid);
248	return NULL;
249	}
250
251	sb = tree->inode->i_sb;
252	size = sizeof(struct hfs_bnode) + tree->pages_per_bnode *
253	sizeof(struct page *);
254	node = kmalloc(size, GFP_KERNEL);
255	if (!node)
256	return NULL;
257	memset(node, 0, size);
258	node->tree = tree;
259	node->this = cnid;
260	set_bit(HFS_BNODE_NEW, &node->flags);
261	atomic_set(&node->refcnt, 1);
262	dprint(DBG_BNODE_REFS, "new_node(%d:%d): 1\n",
263	node->tree->cnid, node->this);
264	init_waitqueue_head(&node->lock_wq);
265	spin_lock(&tree->hash_lock);
266	node2 = hfs_bnode_findhash(tree, cnid);
267	if (!node2) {
268	hash = hfs_bnode_hash(cnid);
269	node->next_hash = tree->node_hash[hash];
270	tree->node_hash[hash] = node;
271	tree->node_hash_cnt++;
272	} else {
273	spin_unlock(&tree->hash_lock);
274	kfree(node);
275	wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags));
276	return node2;
277	}
278	spin_unlock(&tree->hash_lock);
279
280	mapping = tree->inode->i_mapping;
281	off = (loff_t)cnid * tree->node_size;
282	block = off >> PAGE_CACHE_SHIFT;
283	node->page_offset = off & ~PAGE_CACHE_MASK;
284	for (i = 0; i < tree->pages_per_bnode; i++) {
285	page = read_cache_page(mapping, block++, (filler_t *)mapping->a_ops->readpage, NULL);
286	if (IS_ERR(page))
287	goto fail;
288	if (PageError(page)) {
289	page_cache_release(page);
290	goto fail;
291	}
292	#if !REF_PAGES
293	page_cache_release(page);
294	#endif
295	node->page[i] = page;
296	}
297
298	return node;
299	fail:
300	set_bit(HFS_BNODE_ERROR, &node->flags);
301	return node;
302	}
303
304	void hfs_bnode_unhash(struct hfs_bnode *node)
305	{
306	struct hfs_bnode **p;
307
308	dprint(DBG_BNODE_REFS, "remove_node(%d:%d): %d\n",
309	node->tree->cnid, node->this, atomic_read(&node->refcnt));
310	for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)];
311	p && p != node; p = &(*p)->next_hash)
312	;
313	if (!*p)
314	BUG();
315	*p = node->next_hash;
316	node->tree->node_hash_cnt--;
317	}
318
319	/* Load a particular node out of a tree */
320	struct hfs_bnode hfs_bnode_find(struct hfs_btree tree, u32 num)
321	{
322	struct hfs_bnode *node;
323	struct hfs_bnode_desc *desc;
324	int i, rec_off, off, next_off;
325	int entry_size, key_size;
326
327	spin_lock(&tree->hash_lock);
328	node = hfs_bnode_findhash(tree, num);
329	if (node) {
330	hfs_bnode_get(node);
331	spin_unlock(&tree->hash_lock);
332	wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags));
333	if (test_bit(HFS_BNODE_ERROR, &node->flags))
334	goto node_error;
335	return node;
336	}
337	spin_unlock(&tree->hash_lock);
338	node = __hfs_bnode_create(tree, num);
339	if (!node)
340	return ERR_PTR(-ENOMEM);
341	if (test_bit(HFS_BNODE_ERROR, &node->flags))
342	goto node_error;
343	if (!test_bit(HFS_BNODE_NEW, &node->flags))
344	return node;
345
346	desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset);
347	node->prev = be32_to_cpu(desc->prev);
348	node->next = be32_to_cpu(desc->next);
349	node->num_recs = be16_to_cpu(desc->num_recs);
350	node->type = desc->type;
351	node->height = desc->height;
352	kunmap(node->page[0]);
353
354	switch (node->type) {
355	case HFS_NODE_HEADER:
356	case HFS_NODE_MAP:
357	if (node->height != 0)
358	goto node_error;
359	break;
360	case HFS_NODE_LEAF:
361	if (node->height != 1)
362	goto node_error;
363	break;
364	case HFS_NODE_INDEX:
365	if (node->height <= 1 \|\| node->height > tree->depth)
366	goto node_error;
367	break;
368	default:
369	goto node_error;
370	}
371
372	rec_off = tree->node_size - 2;
373	off = hfs_bnode_read_u16(node, rec_off);
374	if (off != sizeof(struct hfs_bnode_desc))
375	goto node_error;
376	for (i = 1; i <= node->num_recs; off = next_off, i++) {
377	rec_off -= 2;
378	next_off = hfs_bnode_read_u16(node, rec_off);
379	if (next_off <= off \|\|
380	next_off > tree->node_size \|\|
381	next_off & 1)
382	goto node_error;
383	entry_size = next_off - off;
384	if (node->type != HFS_NODE_INDEX &&
385	node->type != HFS_NODE_LEAF)
386	continue;
387	key_size = hfs_bnode_read_u8(node, off) + 1;
388	if (key_size >= entry_size /\|\| key_size & 1/)
389	goto node_error;
390	}
391	clear_bit(HFS_BNODE_NEW, &node->flags);
392	wake_up(&node->lock_wq);
393	return node;
394
395	node_error:
396	set_bit(HFS_BNODE_ERROR, &node->flags);
397	clear_bit(HFS_BNODE_NEW, &node->flags);
398	wake_up(&node->lock_wq);
399	hfs_bnode_put(node);
400	return ERR_PTR(-EIO);
401	}
402
403	void hfs_bnode_free(struct hfs_bnode *node)
404	{
405	//int i;
406
407	//for (i = 0; i < node->tree->pages_per_bnode; i++)
408	// if (node->page[i])
409	// page_cache_release(node->page[i]);
410	kfree(node);
411	}
412
413	struct hfs_bnode hfs_bnode_create(struct hfs_btree tree, u32 num)
414	{
415	struct hfs_bnode *node;
416	struct page **pagep;
417	int i;
418
419	spin_lock(&tree->hash_lock);
420	node = hfs_bnode_findhash(tree, num);
421	spin_unlock(&tree->hash_lock);
422	if (node)
423	BUG();
424	node = __hfs_bnode_create(tree, num);
425	if (!node)
426	return ERR_PTR(-ENOMEM);
427	if (test_bit(HFS_BNODE_ERROR, &node->flags)) {
428	hfs_bnode_put(node);
429	return ERR_PTR(-EIO);
430	}
431
432	pagep = node->page;
433	memset(kmap(*pagep) + node->page_offset, 0,
434	min((int)PAGE_CACHE_SIZE, (int)tree->node_size));
435	set_page_dirty(*pagep);
436	kunmap(*pagep);
437	for (i = 1; i < tree->pages_per_bnode; i++) {
438	memset(kmap(*++pagep), 0, PAGE_CACHE_SIZE);
439	set_page_dirty(*pagep);
440	kunmap(*pagep);
441	}
442	clear_bit(HFS_BNODE_NEW, &node->flags);
443	wake_up(&node->lock_wq);
444
445	return node;
446	}
447
448	void hfs_bnode_get(struct hfs_bnode *node)
449	{
450	if (node) {
451	atomic_inc(&node->refcnt);
452	#if REF_PAGES
453	{
454	int i;
455	for (i = 0; i < node->tree->pages_per_bnode; i++)
456	get_page(node->page[i]);
457	}
458	#endif
459	dprint(DBG_BNODE_REFS, "get_node(%d:%d): %d\n",
460	node->tree->cnid, node->this, atomic_read(&node->refcnt));
461	}
462	}
463
464	/* Dispose of resources used by a node */
465	void hfs_bnode_put(struct hfs_bnode *node)
466	{
467	if (node) {
468	struct hfs_btree *tree = node->tree;
469	int i;
470
471	dprint(DBG_BNODE_REFS, "put_node(%d:%d): %d\n",
472	node->tree->cnid, node->this, atomic_read(&node->refcnt));
473	if (!atomic_read(&node->refcnt))
474	BUG();
475	if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) {
476	#if REF_PAGES
477	for (i = 0; i < tree->pages_per_bnode; i++)
478	put_page(node->page[i]);
479	#endif
480	return;
481	}
482	for (i = 0; i < tree->pages_per_bnode; i++) {
74f9c9c2 RZ	483	if (!node->page[i])
74f9c9c2 RZ	484	continue;
1da177e4 LT	485	mark_page_accessed(node->page[i]);
	486	#if REF_PAGES
	487	put_page(node->page[i]);
	488	#endif
	489	}
	490
	491	if (test_bit(HFS_BNODE_DELETED, &node->flags)) {
	492	hfs_bnode_unhash(node);
	493	spin_unlock(&tree->hash_lock);
	494	hfs_bmap_free(node);
	495	hfs_bnode_free(node);
	496	return;
	497	}
	498	spin_unlock(&tree->hash_lock);
	499	}
	500	}