btree.c 9.06 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12
/*
 *  linux/fs/hfsplus/btree.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handle opening/closing btree
 */

#include <linux/slab.h>
#include <linux/pagemap.h>
Vignesh Babu BM's avatar
Vignesh Babu BM committed
13
#include <linux/log2.h>
Linus Torvalds's avatar
Linus Torvalds committed
14 15 16 17 18 19 20 21 22 23 24

#include "hfsplus_fs.h"
#include "hfsplus_raw.h"


/* Get a reference to a B*Tree and do some initial checks */
struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
{
	struct hfs_btree *tree;
	struct hfs_btree_header_rec *head;
	struct address_space *mapping;
25
	struct inode *inode;
Linus Torvalds's avatar
Linus Torvalds committed
26 27 28
	struct page *page;
	unsigned int size;

29
	tree = kzalloc(sizeof(*tree), GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
30 31 32
	if (!tree)
		return NULL;

33
	mutex_init(&tree->tree_lock);
Linus Torvalds's avatar
Linus Torvalds committed
34 35 36
	spin_lock_init(&tree->hash_lock);
	tree->sb = sb;
	tree->cnid = id;
37 38
	inode = hfsplus_iget(sb, id);
	if (IS_ERR(inode))
Linus Torvalds's avatar
Linus Torvalds committed
39
		goto free_tree;
40
	tree->inode = inode;
Linus Torvalds's avatar
Linus Torvalds committed
41

42 43 44 45 46 47
	if (!HFSPLUS_I(tree->inode)->first_blocks) {
		printk(KERN_ERR
		       "hfs: invalid btree extent records (0 size).\n");
		goto free_inode;
	}

Linus Torvalds's avatar
Linus Torvalds committed
48
	mapping = tree->inode->i_mapping;
49
	page = read_mapping_page(mapping, 0, NULL);
Linus Torvalds's avatar
Linus Torvalds committed
50
	if (IS_ERR(page))
51
		goto free_inode;
Linus Torvalds's avatar
Linus Torvalds committed
52 53

	/* Load the header */
54 55
	head = (struct hfs_btree_header_rec *)(kmap(page) +
		sizeof(struct hfs_bnode_desc));
Linus Torvalds's avatar
Linus Torvalds committed
56 57 58 59 60 61 62 63 64 65 66
	tree->root = be32_to_cpu(head->root);
	tree->leaf_count = be32_to_cpu(head->leaf_count);
	tree->leaf_head = be32_to_cpu(head->leaf_head);
	tree->leaf_tail = be32_to_cpu(head->leaf_tail);
	tree->node_count = be32_to_cpu(head->node_count);
	tree->free_nodes = be32_to_cpu(head->free_nodes);
	tree->attributes = be32_to_cpu(head->attributes);
	tree->node_size = be16_to_cpu(head->node_size);
	tree->max_key_len = be16_to_cpu(head->max_key_len);
	tree->depth = be16_to_cpu(head->depth);

67 68 69 70 71 72 73 74
	/* Verify the tree and set the correct compare function */
	switch (id) {
	case HFSPLUS_EXT_CNID:
		if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {
			printk(KERN_ERR "hfs: invalid extent max_key_len %d\n",
				tree->max_key_len);
			goto fail_page;
		}
75 76 77 78 79
		if (tree->attributes & HFS_TREE_VARIDXKEYS) {
			printk(KERN_ERR "hfs: invalid extent btree flag\n");
			goto fail_page;
		}

David Elliott's avatar
David Elliott committed
80
		tree->keycmp = hfsplus_ext_cmp_key;
81 82 83 84 85 86 87
		break;
	case HFSPLUS_CAT_CNID:
		if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {
			printk(KERN_ERR "hfs: invalid catalog max_key_len %d\n",
				tree->max_key_len);
			goto fail_page;
		}
88 89 90 91
		if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
			printk(KERN_ERR "hfs: invalid catalog btree flag\n");
			goto fail_page;
		}
92

93
		if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) &&
David Elliott's avatar
David Elliott committed
94 95
		    (head->key_type == HFSPLUS_KEY_BINARY))
			tree->keycmp = hfsplus_cat_bin_cmp_key;
96
		else {
David Elliott's avatar
David Elliott committed
97
			tree->keycmp = hfsplus_cat_case_cmp_key;
98
			set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
99
		}
100
		break;
101 102 103 104 105 106 107 108
	case HFSPLUS_ATTR_CNID:
		if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
			printk(KERN_ERR "hfs: invalid attributes max_key_len %d\n",
				tree->max_key_len);
			goto fail_page;
		}
		tree->keycmp = hfsplus_attr_bin_cmp_key;
		break;
109
	default:
David Elliott's avatar
David Elliott committed
110 111 112 113
		printk(KERN_ERR "hfs: unknown B*Tree requested\n");
		goto fail_page;
	}

114 115 116 117 118
	if (!(tree->attributes & HFS_TREE_BIGKEYS)) {
		printk(KERN_ERR "hfs: invalid btree flag\n");
		goto fail_page;
	}

Linus Torvalds's avatar
Linus Torvalds committed
119
	size = tree->node_size;
Vignesh Babu BM's avatar
Vignesh Babu BM committed
120
	if (!is_power_of_2(size))
Linus Torvalds's avatar
Linus Torvalds committed
121 122 123
		goto fail_page;
	if (!tree->node_count)
		goto fail_page;
124

Linus Torvalds's avatar
Linus Torvalds committed
125 126
	tree->node_size_shift = ffs(size) - 1;

127 128 129
	tree->pages_per_bnode =
		(tree->node_size + PAGE_CACHE_SIZE - 1) >>
		PAGE_CACHE_SHIFT;
Linus Torvalds's avatar
Linus Torvalds committed
130 131 132 133 134 135 136

	kunmap(page);
	page_cache_release(page);
	return tree;

 fail_page:
	page_cache_release(page);
137
 free_inode:
138
	tree->inode->i_mapping->a_ops = &hfsplus_aops;
Linus Torvalds's avatar
Linus Torvalds committed
139
	iput(tree->inode);
140
 free_tree:
Linus Torvalds's avatar
Linus Torvalds committed
141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
	kfree(tree);
	return NULL;
}

/* Release resources used by a btree */
void hfs_btree_close(struct hfs_btree *tree)
{
	struct hfs_bnode *node;
	int i;

	if (!tree)
		return;

	for (i = 0; i < NODE_HASH_SIZE; i++) {
		while ((node = tree->node_hash[i])) {
			tree->node_hash[i] = node->next_hash;
			if (atomic_read(&node->refcnt))
158 159 160 161
				printk(KERN_CRIT "hfs: node %d:%d "
						"still has %d user(s)!\n",
					node->tree->cnid, node->this,
					atomic_read(&node->refcnt));
Linus Torvalds's avatar
Linus Torvalds committed
162 163 164 165 166 167 168 169
			hfs_bnode_free(node);
			tree->node_hash_cnt--;
		}
	}
	iput(tree->inode);
	kfree(tree);
}

170
int hfs_btree_write(struct hfs_btree *tree)
Linus Torvalds's avatar
Linus Torvalds committed
171 172 173 174 175 176 177 178
{
	struct hfs_btree_header_rec *head;
	struct hfs_bnode *node;
	struct page *page;

	node = hfs_bnode_find(tree, 0);
	if (IS_ERR(node))
		/* panic? */
179
		return -EIO;
Linus Torvalds's avatar
Linus Torvalds committed
180 181
	/* Load the header */
	page = node->page[0];
182 183
	head = (struct hfs_btree_header_rec *)(kmap(page) +
		sizeof(struct hfs_bnode_desc));
Linus Torvalds's avatar
Linus Torvalds committed
184 185 186 187 188 189 190 191 192 193 194 195 196

	head->root = cpu_to_be32(tree->root);
	head->leaf_count = cpu_to_be32(tree->leaf_count);
	head->leaf_head = cpu_to_be32(tree->leaf_head);
	head->leaf_tail = cpu_to_be32(tree->leaf_tail);
	head->node_count = cpu_to_be32(tree->node_count);
	head->free_nodes = cpu_to_be32(tree->free_nodes);
	head->attributes = cpu_to_be32(tree->attributes);
	head->depth = cpu_to_be16(tree->depth);

	kunmap(page);
	set_page_dirty(page);
	hfs_bnode_put(node);
197
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
}

static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
{
	struct hfs_btree *tree = prev->tree;
	struct hfs_bnode *node;
	struct hfs_bnode_desc desc;
	__be32 cnid;

	node = hfs_bnode_create(tree, idx);
	if (IS_ERR(node))
		return node;

	tree->free_nodes--;
	prev->next = idx;
	cnid = cpu_to_be32(idx);
	hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);

	node->type = HFS_NODE_MAP;
	node->num_recs = 1;
	hfs_bnode_clear(node, 0, tree->node_size);
	desc.next = 0;
	desc.prev = 0;
	desc.type = HFS_NODE_MAP;
	desc.height = 0;
	desc.num_recs = cpu_to_be16(1);
	desc.reserved = 0;
	hfs_bnode_write(node, &desc, 0, sizeof(desc));
	hfs_bnode_write_u16(node, 14, 0x8000);
	hfs_bnode_write_u16(node, tree->node_size - 2, 14);
	hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);

	return node;
}

struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
{
	struct hfs_bnode *node, *next_node;
	struct page **pagep;
	u32 nidx, idx;
238 239 240
	unsigned off;
	u16 off16;
	u16 len;
Linus Torvalds's avatar
Linus Torvalds committed
241 242 243 244 245
	u8 *data, byte, m;
	int i;

	while (!tree->free_nodes) {
		struct inode *inode = tree->inode;
246
		struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
Linus Torvalds's avatar
Linus Torvalds committed
247 248 249 250 251 252
		u32 count;
		int res;

		res = hfsplus_file_extend(inode);
		if (res)
			return ERR_PTR(res);
253 254
		hip->phys_size = inode->i_size =
			(loff_t)hip->alloc_blocks <<
255
				HFSPLUS_SB(tree->sb)->alloc_blksz_shift;
256 257
		hip->fs_blocks =
			hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;
Linus Torvalds's avatar
Linus Torvalds committed
258 259 260 261 262 263 264 265 266 267
		inode_set_bytes(inode, inode->i_size);
		count = inode->i_size >> tree->node_size_shift;
		tree->free_nodes = count - tree->node_count;
		tree->node_count = count;
	}

	nidx = 0;
	node = hfs_bnode_find(tree, nidx);
	if (IS_ERR(node))
		return node;
268 269
	len = hfs_brec_lenoff(node, 2, &off16);
	off = off16;
Linus Torvalds's avatar
Linus Torvalds committed
270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289

	off += node->page_offset;
	pagep = node->page + (off >> PAGE_CACHE_SHIFT);
	data = kmap(*pagep);
	off &= ~PAGE_CACHE_MASK;
	idx = 0;

	for (;;) {
		while (len) {
			byte = data[off];
			if (byte != 0xff) {
				for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
					if (!(byte & m)) {
						idx += i;
						data[off] |= m;
						set_page_dirty(*pagep);
						kunmap(*pagep);
						tree->free_nodes--;
						mark_inode_dirty(tree->inode);
						hfs_bnode_put(node);
290 291
						return hfs_bnode_create(tree,
							idx);
Linus Torvalds's avatar
Linus Torvalds committed
292 293 294 295 296 297 298 299 300 301 302 303 304 305
					}
				}
			}
			if (++off >= PAGE_CACHE_SIZE) {
				kunmap(*pagep);
				data = kmap(*++pagep);
				off = 0;
			}
			idx += 8;
			len--;
		}
		kunmap(*pagep);
		nidx = node->next;
		if (!nidx) {
306
			hfs_dbg(BNODE_MOD, "create new bmap node\n");
Linus Torvalds's avatar
Linus Torvalds committed
307 308 309 310 311 312 313 314
			next_node = hfs_bmap_new_bmap(node, idx);
		} else
			next_node = hfs_bnode_find(tree, nidx);
		hfs_bnode_put(node);
		if (IS_ERR(next_node))
			return next_node;
		node = next_node;

315 316
		len = hfs_brec_lenoff(node, 0, &off16);
		off = off16;
Linus Torvalds's avatar
Linus Torvalds committed
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
		off += node->page_offset;
		pagep = node->page + (off >> PAGE_CACHE_SHIFT);
		data = kmap(*pagep);
		off &= ~PAGE_CACHE_MASK;
	}
}

void hfs_bmap_free(struct hfs_bnode *node)
{
	struct hfs_btree *tree;
	struct page *page;
	u16 off, len;
	u32 nidx;
	u8 *data, byte, m;

332
	hfs_dbg(BNODE_MOD, "btree_free_node: %u\n", node->this);
333
	BUG_ON(!node->this);
Linus Torvalds's avatar
Linus Torvalds committed
334 335 336 337 338 339 340 341 342 343 344 345 346 347
	tree = node->tree;
	nidx = node->this;
	node = hfs_bnode_find(tree, 0);
	if (IS_ERR(node))
		return;
	len = hfs_brec_lenoff(node, 2, &off);
	while (nidx >= len * 8) {
		u32 i;

		nidx -= len * 8;
		i = node->next;
		hfs_bnode_put(node);
		if (!i) {
			/* panic */;
348 349 350
			printk(KERN_CRIT "hfs: unable to free bnode %u. "
					"bmap not found!\n",
				node->this);
Linus Torvalds's avatar
Linus Torvalds committed
351 352 353 354 355 356 357
			return;
		}
		node = hfs_bnode_find(tree, i);
		if (IS_ERR(node))
			return;
		if (node->type != HFS_NODE_MAP) {
			/* panic */;
358 359 360
			printk(KERN_CRIT "hfs: invalid bmap found! "
					"(%u,%d)\n",
				node->this, node->type);
Linus Torvalds's avatar
Linus Torvalds committed
361 362 363 364 365 366 367 368 369 370 371 372
			hfs_bnode_put(node);
			return;
		}
		len = hfs_brec_lenoff(node, 0, &off);
	}
	off += node->page_offset + nidx / 8;
	page = node->page[off >> PAGE_CACHE_SHIFT];
	data = kmap(page);
	off &= ~PAGE_CACHE_MASK;
	m = 1 << (~nidx & 7);
	byte = data[off];
	if (!(byte & m)) {
373 374 375
		printk(KERN_CRIT "hfs: trying to free free bnode "
				"%u(%d)\n",
			node->this, node->type);
Linus Torvalds's avatar
Linus Torvalds committed
376 377 378 379 380 381 382 383 384 385 386
		kunmap(page);
		hfs_bnode_put(node);
		return;
	}
	data[off] = byte & ~m;
	set_page_dirty(page);
	kunmap(page);
	hfs_bnode_put(node);
	tree->free_nodes++;
	mark_inode_dirty(tree->inode);
}