[people/ms/linux.git] / fs / hfs / bnode.c

// SPDX-License-Identifier: GPL-2.0
/*
 *  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/slab.h>
#include <linux/swap.h>

#include "btree.h"

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

	off += node->page_offset;
	pagenum = off >> PAGE_SHIFT;
	off &= ~PAGE_MASK; /* compute page offset for the first page */

	for (bytes_read = 0; bytes_read < len; bytes_read += bytes_to_read) {
		if (pagenum >= node->tree->pages_per_bnode)
			break;
		page = node->page[pagenum];
		bytes_to_read = min_t(int, len - bytes_read, PAGE_SIZE - off);

		vaddr = kmap_atomic(page);
		memcpy(buf + bytes_read, vaddr + off, bytes_to_read);
		kunmap_atomic(vaddr);

		pagenum++;
		off = 0; /* page offset only applies to the first 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 page *src_page, *dst_page;

	hfs_dbg(BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len);
	if (!len)
		return;
	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;

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

	hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this);
	hfs_bnode_read(node, &desc, 0, sizeof(desc));
	hfs_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);
		hfs_dbg_cont(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;
			hfs_dbg_cont(BNODE_MOD, " (%d,%d",
				     tmp, hfs_bnode_read_u8(node, key_off));
			hfs_bnode_read(node, &cnid, key_off + tmp, 4);
			hfs_dbg_cont(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);
			hfs_dbg_cont(BNODE_MOD, " (%d)", tmp);
		}
	}
	hfs_dbg_cont(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(KERN_DEBUG "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) {
		pr_err("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 hfs_bnode *node, *node2;
	struct address_space *mapping;
	struct page *page;
	int size, block, i, hash;
	loff_t off;

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

	size = sizeof(struct hfs_bnode) + tree->pages_per_bnode *
		sizeof(struct page *);
	node = kzalloc(size, GFP_KERNEL);
	if (!node)
		return NULL;
	node->tree = tree;
	node->this = cnid;
	set_bit(HFS_BNODE_NEW, &node->flags);
	atomic_set(&node->refcnt, 1);
	hfs_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_SHIFT;
	node->page_offset = off & ~PAGE_MASK;
	for (i = 0; i < tree->pages_per_bnode; i++) {
		page = read_mapping_page(mapping, block++, NULL);
		if (IS_ERR(page))
			goto fail;
		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;

	hfs_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)
		;
	BUG_ON(!*p);
	*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])
			put_page(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) {
		pr_crit("new node %u already hashed?\n", num);
		WARN_ON(1);
		return node;
	}
	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_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_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);
		hfs_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;

		hfs_dbg(BNODE_REFS, "put_node(%d:%d): %d\n",
			node->tree->cnid, node->this,
			atomic_read(&node->refcnt));
		BUG_ON(!atomic_read(&node->refcnt));
		if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock))
			return;
		for (i = 0; i < tree->pages_per_bnode; i++) {
			if (!node->page[i])
				continue;
			mark_page_accessed(node->page[i]);
		}

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