1 /*
2  *  linux/fs/hfsplus/btree.c
3  *
4  * Copyright (C) 2001
5  * Brad Boyer (flar@allandria.com)
6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
7  *
8  * Handle opening/closing btree
9  */
10 
11 #include <linux/slab.h>
12 #include <linux/pagemap.h>
13 #include <asm/div64.h>
14 
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
17 
18 /* Release resources used by a btree */
hfsplus_close_btree(struct hfsplus_btree * tree)19 void hfsplus_close_btree(struct hfsplus_btree *tree)
20 {
21 	hfsplus_bnode *node;
22 	int i;
23 
24 	if (!tree)
25 		return;
26 
27 	for (i = 0; i < NODE_HASH_SIZE; i++) {
28 		while ((node = tree->node_hash[i])) {
29 			tree->node_hash[i] = node->next_hash;
30 			if (atomic_read(&node->refcnt))
31 				printk("HFS+: node %d:%d still has %d user(s)!\n",
32 					node->tree->cnid, node->this, atomic_read(&node->refcnt));
33 			hfsplus_bnode_free(node);
34 			tree->node_hash_cnt--;
35 		}
36 	}
37 	iput(tree->inode);
38 	kfree(tree);
39 }
40 
41 /* Fill in extra data in tree structure from header node */
hfsplus_read_treeinfo(hfsplus_btree * tree,hfsplus_btree_head * hdr)42 static void hfsplus_read_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
43 {
44 	unsigned int shift, size;
45 
46 	if (!tree || !hdr)
47 		return;
48 
49 	tree->root = be32_to_cpu(hdr->root);
50 	tree->leaf_count = be32_to_cpu(hdr->leaf_count);
51 	tree->leaf_head = be32_to_cpu(hdr->leaf_head);
52 	tree->leaf_tail = be32_to_cpu(hdr->leaf_tail);
53 	tree->node_count = be32_to_cpu(hdr->node_count);
54 	tree->free_nodes = be32_to_cpu(hdr->free_nodes);
55 	tree->attributes = be32_to_cpu(hdr->attributes);
56 	tree->node_size = be16_to_cpu(hdr->node_size);
57 	tree->max_key_len = be16_to_cpu(hdr->max_key_len);
58 	tree->depth = be16_to_cpu(hdr->depth);
59 
60 	size = tree->node_size;
61 	if (size & (size - 1))
62 		/* panic */;
63 	for (shift = 0; size >>= 1; shift += 1)
64 		;
65 	tree->node_size_shift = shift;
66 
67 	tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
68 }
69 
hfsplus_write_treeinfo(hfsplus_btree * tree,hfsplus_btree_head * hdr)70 static void hfsplus_write_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
71 {
72 	hdr->root = cpu_to_be32(tree->root);
73 	hdr->leaf_count = cpu_to_be32(tree->leaf_count);
74 	hdr->leaf_head = cpu_to_be32(tree->leaf_head);
75 	hdr->leaf_tail = cpu_to_be32(tree->leaf_tail);
76 	hdr->node_count = cpu_to_be32(tree->node_count);
77 	hdr->free_nodes = cpu_to_be32(tree->free_nodes);
78 	hdr->attributes = cpu_to_be32(tree->attributes);
79 	hdr->depth = cpu_to_be16(tree->depth);
80 }
81 
82 /* Get a reference to a B*Tree and do some initial checks */
hfsplus_open_btree(struct super_block * sb,u32 id)83 hfsplus_btree *hfsplus_open_btree(struct super_block *sb, u32 id)
84 {
85 	hfsplus_btree *tree;
86 	hfsplus_btree_head *head;
87 	struct address_space *mapping;
88 	struct page *page;
89 
90 	tree = kmalloc(sizeof(struct hfsplus_btree), GFP_KERNEL);
91 	if (!tree)
92 		return NULL;
93 	memset(tree, 0, sizeof(struct hfsplus_btree));
94 
95 	init_MUTEX(&tree->tree_lock);
96 	spin_lock_init(&tree->hash_lock);
97 	/* Set the correct compare function */
98 	tree->sb = sb;
99 	tree->cnid = id;
100 	if (id == HFSPLUS_EXT_CNID) {
101 		tree->keycmp = hfsplus_cmp_ext_key;
102 	} else if (id == HFSPLUS_CAT_CNID) {
103 		tree->keycmp = hfsplus_cmp_cat_key;
104 	} else {
105 		printk("HFS+-fs: unknown B*Tree requested\n");
106 		goto free_tree;
107 	}
108 	tree->inode = iget(sb, id);
109 	if (!tree->inode)
110 		goto free_tree;
111 
112 	mapping = tree->inode->i_mapping;
113 	page = grab_cache_page(mapping, 0);
114 	if (!page)
115 		goto free_tree;
116 	if (!PageUptodate(page)) {
117 		if (mapping->a_ops->readpage(NULL, page))
118 			goto fail_page;
119 		wait_on_page_locked(page);
120 		if (!PageUptodate(page))
121 			goto fail_page;
122 	} else
123 		unlock_page(page);
124 
125 	/* Load the header */
126 	head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
127 	hfsplus_read_treeinfo(tree, head);
128 	kunmap(page);
129 	page_cache_release(page);
130 	return tree;
131 
132  fail_page:
133 	page_cache_release(page);
134  free_tree:
135 	iput(tree->inode);
136 	kfree(tree);
137 	return NULL;
138 }
139 
hfsplus_write_btree(struct hfsplus_btree * tree)140 void hfsplus_write_btree(struct hfsplus_btree *tree)
141 {
142 	hfsplus_btree_head *head;
143 	hfsplus_bnode *node;
144 	struct page *page;
145 
146 	node = hfsplus_find_bnode(tree, 0);
147 	if (!node)
148 		/* panic? */
149 		return;
150 	/* Load the header */
151 	page = node->page[0];
152 	head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
153 	hfsplus_write_treeinfo(tree, head);
154 	kunmap(page);
155 	set_page_dirty(page);
156 	hfsplus_put_bnode(node);
157 }
158 
hfsplus_btree_alloc_node(hfsplus_btree * tree)159 hfsplus_bnode *hfsplus_btree_alloc_node(hfsplus_btree *tree)
160 {
161 	hfsplus_bnode *node;
162 	struct page **pagep;
163 	u32 nidx;
164 	u16 idx, off, len;
165 	u8 *data, byte, m;
166 	int i;
167 
168 	while (!tree->free_nodes) {
169 		loff_t size;
170 		int res;
171 
172 		res = hfsplus_extend_file(tree->inode);
173 		if (res)
174 			return ERR_PTR(res);
175 		HFSPLUS_I(tree->inode).total_blocks = HFSPLUS_I(tree->inode).alloc_blocks;
176 		size = HFSPLUS_I(tree->inode).total_blocks;
177 		size <<= tree->sb->s_blocksize_bits;
178 		tree->inode->i_size = size;
179 		do_div(size, (u32)tree->node_size);
180 		tree->free_nodes = (u32)size - tree->node_count;
181 		tree->node_count = size;
182 	}
183 
184 	nidx = 0;
185 	node = hfsplus_find_bnode(tree, nidx);
186 	len = hfsplus_brec_lenoff(node, 2, &off);
187 
188 	off += node->page_offset;
189 	pagep = node->page + (off >> PAGE_CACHE_SHIFT);
190 	data = hfsplus_kmap(*pagep);
191 	off &= ~PAGE_CACHE_MASK;
192 	idx = 0;
193 
194 	for (;;) {
195 		while (len) {
196 			byte = data[off];
197 			if (byte != 0xff) {
198 				for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
199 					if (!(byte & m)) {
200 						idx += i;
201 						data[off] |= m;
202 						set_page_dirty(*pagep);
203 						hfsplus_kunmap(*pagep);
204 						tree->free_nodes--;
205 						mark_inode_dirty(tree->inode);
206 						hfsplus_put_bnode(node);
207 						return hfsplus_create_bnode(tree, idx);
208 					}
209 				}
210 			}
211 			if (++off >= PAGE_CACHE_SIZE) {
212 				hfsplus_kunmap(*pagep++);
213 				data = hfsplus_kmap(*pagep);
214 				off = 0;
215 			}
216 			idx += 8;
217 			len--;
218 		}
219 		nidx = node->next;
220 		hfsplus_put_bnode(node);
221 		if (!nidx) {
222 			printk("need new bmap node...\n");
223 			hfsplus_kunmap(*pagep);
224 			return ERR_PTR(-ENOSPC);
225 		}
226 		node = hfsplus_find_bnode(tree, nidx);
227 		len = hfsplus_brec_lenoff(node, 0, &off);
228 
229 		off += node->page_offset;
230 		pagep = node->page + (off >> PAGE_CACHE_SHIFT);
231 		data = hfsplus_kmap(*pagep);
232 		off &= ~PAGE_CACHE_MASK;
233 	}
234 }
235 
hfsplus_btree_remove_node(hfsplus_bnode * node)236 void hfsplus_btree_remove_node(hfsplus_bnode *node)
237 {
238 	hfsplus_btree *tree;
239 	hfsplus_bnode *tmp;
240 	u32 cnid;
241 
242 	tree = node->tree;
243 	if (node->prev) {
244 		tmp = hfsplus_find_bnode(tree, node->prev);
245 		tmp->next = node->next;
246 		cnid = cpu_to_be32(tmp->next);
247 		hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, next), 4);
248 		hfsplus_put_bnode(tmp);
249 	} else if (node->kind == HFSPLUS_NODE_LEAF)
250 		tree->leaf_head = node->next;
251 
252 	if (node->next) {
253 		tmp = hfsplus_find_bnode(tree, node->next);
254 		tmp->prev = node->prev;
255 		cnid = cpu_to_be32(tmp->prev);
256 		hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, prev), 4);
257 		hfsplus_put_bnode(tmp);
258 	} else if (node->kind == HFSPLUS_NODE_LEAF)
259 		tree->leaf_tail = node->prev;
260 
261 	// move down?
262 	if (!node->prev && !node->next) {
263 		printk("hfsplus_btree_del_level\n");
264 	}
265 	if (!node->parent) {
266 		tree->root = 0;
267 		tree->depth = 0;
268 	}
269 	set_bit(HFSPLUS_BNODE_DELETED, &node->flags);
270 }
271 
hfsplus_btree_free_node(hfsplus_bnode * node)272 void hfsplus_btree_free_node(hfsplus_bnode *node)
273 {
274 	hfsplus_btree *tree;
275 	struct page *page;
276 	u16 off, len;
277 	u32 nidx;
278 	u8 *data, byte, m;
279 
280 	dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
281 	tree = node->tree;
282 	nidx = node->this;
283 	node = hfsplus_find_bnode(tree, 0);
284 	len = hfsplus_brec_lenoff(node, 2, &off);
285 	while (nidx >= len * 8) {
286 		u32 i;
287 
288 		nidx -= len * 8;
289 		i = node->next;
290 		hfsplus_put_bnode(node);
291 		if (!nidx)
292 			/* panic */;
293 		node = hfsplus_find_bnode(tree, nidx);
294 		if (node->kind != HFSPLUS_NODE_MAP)
295 			/* panic */;
296 		len = hfsplus_brec_lenoff(node, 0, &off);
297 	}
298 	off += node->page_offset + nidx / 8;
299 	page = node->page[off >> PAGE_CACHE_SHIFT];
300 	data = hfsplus_kmap(page);
301 	off &= ~PAGE_CACHE_MASK;
302 	m = 1 << (~nidx & 7);
303 	byte = data[off];
304 	if (!(byte & m)) {
305 		BUG();
306 		/* panic */
307 		hfsplus_kunmap(page);
308 		hfsplus_put_bnode(node);
309 		return;
310 	}
311 	data[off] = byte & ~m;
312 	set_page_dirty(page);
313 	hfsplus_kunmap(page);
314 	hfsplus_put_bnode(node);
315 	tree->free_nodes++;
316 	mark_inode_dirty(tree->inode);
317 }
318