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