xref: /openbmc/linux/fs/hfsplus/btree.c (revision f42b3800)
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 <linux/log2.h>
14 
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
17 
18 
19 /* Get a reference to a B*Tree and do some initial checks */
20 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
21 {
22 	struct hfs_btree *tree;
23 	struct hfs_btree_header_rec *head;
24 	struct address_space *mapping;
25 	struct inode *inode;
26 	struct page *page;
27 	unsigned int size;
28 
29 	tree = kzalloc(sizeof(*tree), GFP_KERNEL);
30 	if (!tree)
31 		return NULL;
32 
33 	init_MUTEX(&tree->tree_lock);
34 	spin_lock_init(&tree->hash_lock);
35 	tree->sb = sb;
36 	tree->cnid = id;
37 	inode = hfsplus_iget(sb, id);
38 	if (IS_ERR(inode))
39 		goto free_tree;
40 	tree->inode = inode;
41 
42 	mapping = tree->inode->i_mapping;
43 	page = read_mapping_page(mapping, 0, NULL);
44 	if (IS_ERR(page))
45 		goto free_tree;
46 
47 	/* Load the header */
48 	head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
49 	tree->root = be32_to_cpu(head->root);
50 	tree->leaf_count = be32_to_cpu(head->leaf_count);
51 	tree->leaf_head = be32_to_cpu(head->leaf_head);
52 	tree->leaf_tail = be32_to_cpu(head->leaf_tail);
53 	tree->node_count = be32_to_cpu(head->node_count);
54 	tree->free_nodes = be32_to_cpu(head->free_nodes);
55 	tree->attributes = be32_to_cpu(head->attributes);
56 	tree->node_size = be16_to_cpu(head->node_size);
57 	tree->max_key_len = be16_to_cpu(head->max_key_len);
58 	tree->depth = be16_to_cpu(head->depth);
59 
60 	/* Set the correct compare function */
61 	if (id == HFSPLUS_EXT_CNID) {
62 		tree->keycmp = hfsplus_ext_cmp_key;
63 	} else if (id == HFSPLUS_CAT_CNID) {
64 		if ((HFSPLUS_SB(sb).flags & HFSPLUS_SB_HFSX) &&
65 		    (head->key_type == HFSPLUS_KEY_BINARY))
66 			tree->keycmp = hfsplus_cat_bin_cmp_key;
67 		else {
68 			tree->keycmp = hfsplus_cat_case_cmp_key;
69 			HFSPLUS_SB(sb).flags |= HFSPLUS_SB_CASEFOLD;
70 		}
71 	} else {
72 		printk(KERN_ERR "hfs: unknown B*Tree requested\n");
73 		goto fail_page;
74 	}
75 
76 	size = tree->node_size;
77 	if (!is_power_of_2(size))
78 		goto fail_page;
79 	if (!tree->node_count)
80 		goto fail_page;
81 	tree->node_size_shift = ffs(size) - 1;
82 
83 	tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
84 
85 	kunmap(page);
86 	page_cache_release(page);
87 	return tree;
88 
89  fail_page:
90 	tree->inode->i_mapping->a_ops = &hfsplus_aops;
91 	page_cache_release(page);
92  free_tree:
93 	iput(tree->inode);
94 	kfree(tree);
95 	return NULL;
96 }
97 
98 /* Release resources used by a btree */
99 void hfs_btree_close(struct hfs_btree *tree)
100 {
101 	struct hfs_bnode *node;
102 	int i;
103 
104 	if (!tree)
105 		return;
106 
107 	for (i = 0; i < NODE_HASH_SIZE; i++) {
108 		while ((node = tree->node_hash[i])) {
109 			tree->node_hash[i] = node->next_hash;
110 			if (atomic_read(&node->refcnt))
111 				printk(KERN_CRIT "hfs: node %d:%d still has %d user(s)!\n",
112 					node->tree->cnid, node->this, atomic_read(&node->refcnt));
113 			hfs_bnode_free(node);
114 			tree->node_hash_cnt--;
115 		}
116 	}
117 	iput(tree->inode);
118 	kfree(tree);
119 }
120 
121 void hfs_btree_write(struct hfs_btree *tree)
122 {
123 	struct hfs_btree_header_rec *head;
124 	struct hfs_bnode *node;
125 	struct page *page;
126 
127 	node = hfs_bnode_find(tree, 0);
128 	if (IS_ERR(node))
129 		/* panic? */
130 		return;
131 	/* Load the header */
132 	page = node->page[0];
133 	head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
134 
135 	head->root = cpu_to_be32(tree->root);
136 	head->leaf_count = cpu_to_be32(tree->leaf_count);
137 	head->leaf_head = cpu_to_be32(tree->leaf_head);
138 	head->leaf_tail = cpu_to_be32(tree->leaf_tail);
139 	head->node_count = cpu_to_be32(tree->node_count);
140 	head->free_nodes = cpu_to_be32(tree->free_nodes);
141 	head->attributes = cpu_to_be32(tree->attributes);
142 	head->depth = cpu_to_be16(tree->depth);
143 
144 	kunmap(page);
145 	set_page_dirty(page);
146 	hfs_bnode_put(node);
147 }
148 
149 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
150 {
151 	struct hfs_btree *tree = prev->tree;
152 	struct hfs_bnode *node;
153 	struct hfs_bnode_desc desc;
154 	__be32 cnid;
155 
156 	node = hfs_bnode_create(tree, idx);
157 	if (IS_ERR(node))
158 		return node;
159 
160 	tree->free_nodes--;
161 	prev->next = idx;
162 	cnid = cpu_to_be32(idx);
163 	hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
164 
165 	node->type = HFS_NODE_MAP;
166 	node->num_recs = 1;
167 	hfs_bnode_clear(node, 0, tree->node_size);
168 	desc.next = 0;
169 	desc.prev = 0;
170 	desc.type = HFS_NODE_MAP;
171 	desc.height = 0;
172 	desc.num_recs = cpu_to_be16(1);
173 	desc.reserved = 0;
174 	hfs_bnode_write(node, &desc, 0, sizeof(desc));
175 	hfs_bnode_write_u16(node, 14, 0x8000);
176 	hfs_bnode_write_u16(node, tree->node_size - 2, 14);
177 	hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
178 
179 	return node;
180 }
181 
182 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
183 {
184 	struct hfs_bnode *node, *next_node;
185 	struct page **pagep;
186 	u32 nidx, idx;
187 	u16 off, len;
188 	u8 *data, byte, m;
189 	int i;
190 
191 	while (!tree->free_nodes) {
192 		struct inode *inode = tree->inode;
193 		u32 count;
194 		int res;
195 
196 		res = hfsplus_file_extend(inode);
197 		if (res)
198 			return ERR_PTR(res);
199 		HFSPLUS_I(inode).phys_size = inode->i_size =
200 				(loff_t)HFSPLUS_I(inode).alloc_blocks <<
201 				HFSPLUS_SB(tree->sb).alloc_blksz_shift;
202 		HFSPLUS_I(inode).fs_blocks = HFSPLUS_I(inode).alloc_blocks <<
203 					     HFSPLUS_SB(tree->sb).fs_shift;
204 		inode_set_bytes(inode, inode->i_size);
205 		count = inode->i_size >> tree->node_size_shift;
206 		tree->free_nodes = count - tree->node_count;
207 		tree->node_count = count;
208 	}
209 
210 	nidx = 0;
211 	node = hfs_bnode_find(tree, nidx);
212 	if (IS_ERR(node))
213 		return node;
214 	len = hfs_brec_lenoff(node, 2, &off);
215 
216 	off += node->page_offset;
217 	pagep = node->page + (off >> PAGE_CACHE_SHIFT);
218 	data = kmap(*pagep);
219 	off &= ~PAGE_CACHE_MASK;
220 	idx = 0;
221 
222 	for (;;) {
223 		while (len) {
224 			byte = data[off];
225 			if (byte != 0xff) {
226 				for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
227 					if (!(byte & m)) {
228 						idx += i;
229 						data[off] |= m;
230 						set_page_dirty(*pagep);
231 						kunmap(*pagep);
232 						tree->free_nodes--;
233 						mark_inode_dirty(tree->inode);
234 						hfs_bnode_put(node);
235 						return hfs_bnode_create(tree, idx);
236 					}
237 				}
238 			}
239 			if (++off >= PAGE_CACHE_SIZE) {
240 				kunmap(*pagep);
241 				data = kmap(*++pagep);
242 				off = 0;
243 			}
244 			idx += 8;
245 			len--;
246 		}
247 		kunmap(*pagep);
248 		nidx = node->next;
249 		if (!nidx) {
250 			printk(KERN_DEBUG "hfs: create new bmap node...\n");
251 			next_node = hfs_bmap_new_bmap(node, idx);
252 		} else
253 			next_node = hfs_bnode_find(tree, nidx);
254 		hfs_bnode_put(node);
255 		if (IS_ERR(next_node))
256 			return next_node;
257 		node = next_node;
258 
259 		len = hfs_brec_lenoff(node, 0, &off);
260 		off += node->page_offset;
261 		pagep = node->page + (off >> PAGE_CACHE_SHIFT);
262 		data = kmap(*pagep);
263 		off &= ~PAGE_CACHE_MASK;
264 	}
265 }
266 
267 void hfs_bmap_free(struct hfs_bnode *node)
268 {
269 	struct hfs_btree *tree;
270 	struct page *page;
271 	u16 off, len;
272 	u32 nidx;
273 	u8 *data, byte, m;
274 
275 	dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
276 	BUG_ON(!node->this);
277 	tree = node->tree;
278 	nidx = node->this;
279 	node = hfs_bnode_find(tree, 0);
280 	if (IS_ERR(node))
281 		return;
282 	len = hfs_brec_lenoff(node, 2, &off);
283 	while (nidx >= len * 8) {
284 		u32 i;
285 
286 		nidx -= len * 8;
287 		i = node->next;
288 		hfs_bnode_put(node);
289 		if (!i) {
290 			/* panic */;
291 			printk(KERN_CRIT "hfs: unable to free bnode %u. bmap not found!\n", node->this);
292 			return;
293 		}
294 		node = hfs_bnode_find(tree, i);
295 		if (IS_ERR(node))
296 			return;
297 		if (node->type != HFS_NODE_MAP) {
298 			/* panic */;
299 			printk(KERN_CRIT "hfs: invalid bmap found! (%u,%d)\n", node->this, node->type);
300 			hfs_bnode_put(node);
301 			return;
302 		}
303 		len = hfs_brec_lenoff(node, 0, &off);
304 	}
305 	off += node->page_offset + nidx / 8;
306 	page = node->page[off >> PAGE_CACHE_SHIFT];
307 	data = kmap(page);
308 	off &= ~PAGE_CACHE_MASK;
309 	m = 1 << (~nidx & 7);
310 	byte = data[off];
311 	if (!(byte & m)) {
312 		printk(KERN_CRIT "hfs: trying to free free bnode %u(%d)\n", node->this, node->type);
313 		kunmap(page);
314 		hfs_bnode_put(node);
315 		return;
316 	}
317 	data[off] = byte & ~m;
318 	set_page_dirty(page);
319 	kunmap(page);
320 	hfs_bnode_put(node);
321 	tree->free_nodes++;
322 	mark_inode_dirty(tree->inode);
323 }
324