2 * linux/fs/hfsplus/btree.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle opening/closing btree
11 #include <linux/slab.h>
12 #include <linux/pagemap.h>
14 #include "hfsplus_fs.h"
15 #include "hfsplus_raw.h"
18 /* Get a reference to a B*Tree and do some initial checks */
19 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
21 struct hfs_btree *tree;
22 struct hfs_btree_header_rec *head;
23 struct address_space *mapping;
27 tree = kmalloc(sizeof(*tree), GFP_KERNEL);
30 memset(tree, 0, sizeof(*tree));
32 init_MUTEX(&tree->tree_lock);
33 spin_lock_init(&tree->hash_lock);
34 /* Set the correct compare function */
37 if (id == HFSPLUS_EXT_CNID) {
38 tree->keycmp = hfsplus_ext_cmp_key;
39 } else if (id == HFSPLUS_CAT_CNID) {
40 tree->keycmp = hfsplus_cat_cmp_key;
42 printk("HFS+-fs: unknown B*Tree requested\n");
45 tree->inode = iget(sb, id);
49 mapping = tree->inode->i_mapping;
50 page = read_cache_page(mapping, 0, (filler_t *)mapping->a_ops->readpage, NULL);
55 head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
56 tree->root = be32_to_cpu(head->root);
57 tree->leaf_count = be32_to_cpu(head->leaf_count);
58 tree->leaf_head = be32_to_cpu(head->leaf_head);
59 tree->leaf_tail = be32_to_cpu(head->leaf_tail);
60 tree->node_count = be32_to_cpu(head->node_count);
61 tree->free_nodes = be32_to_cpu(head->free_nodes);
62 tree->attributes = be32_to_cpu(head->attributes);
63 tree->node_size = be16_to_cpu(head->node_size);
64 tree->max_key_len = be16_to_cpu(head->max_key_len);
65 tree->depth = be16_to_cpu(head->depth);
67 size = tree->node_size;
68 if (!size || size & (size - 1))
70 if (!tree->node_count)
72 tree->node_size_shift = ffs(size) - 1;
74 tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
77 page_cache_release(page);
81 tree->inode->i_mapping->a_ops = &hfsplus_aops;
82 page_cache_release(page);
89 /* Release resources used by a btree */
90 void hfs_btree_close(struct hfs_btree *tree)
92 struct hfs_bnode *node;
98 for (i = 0; i < NODE_HASH_SIZE; i++) {
99 while ((node = tree->node_hash[i])) {
100 tree->node_hash[i] = node->next_hash;
101 if (atomic_read(&node->refcnt))
102 printk("HFS+: node %d:%d still has %d user(s)!\n",
103 node->tree->cnid, node->this, atomic_read(&node->refcnt));
104 hfs_bnode_free(node);
105 tree->node_hash_cnt--;
112 void hfs_btree_write(struct hfs_btree *tree)
114 struct hfs_btree_header_rec *head;
115 struct hfs_bnode *node;
118 node = hfs_bnode_find(tree, 0);
122 /* Load the header */
123 page = node->page[0];
124 head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
126 head->root = cpu_to_be32(tree->root);
127 head->leaf_count = cpu_to_be32(tree->leaf_count);
128 head->leaf_head = cpu_to_be32(tree->leaf_head);
129 head->leaf_tail = cpu_to_be32(tree->leaf_tail);
130 head->node_count = cpu_to_be32(tree->node_count);
131 head->free_nodes = cpu_to_be32(tree->free_nodes);
132 head->attributes = cpu_to_be32(tree->attributes);
133 head->depth = cpu_to_be16(tree->depth);
136 set_page_dirty(page);
140 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
142 struct hfs_btree *tree = prev->tree;
143 struct hfs_bnode *node;
144 struct hfs_bnode_desc desc;
147 node = hfs_bnode_create(tree, idx);
153 cnid = cpu_to_be32(idx);
154 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
156 node->type = HFS_NODE_MAP;
158 hfs_bnode_clear(node, 0, tree->node_size);
161 desc.type = HFS_NODE_MAP;
163 desc.num_recs = cpu_to_be16(1);
165 hfs_bnode_write(node, &desc, 0, sizeof(desc));
166 hfs_bnode_write_u16(node, 14, 0x8000);
167 hfs_bnode_write_u16(node, tree->node_size - 2, 14);
168 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
173 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
175 struct hfs_bnode *node, *next_node;
182 while (!tree->free_nodes) {
183 struct inode *inode = tree->inode;
187 res = hfsplus_file_extend(inode);
190 HFSPLUS_I(inode).phys_size = inode->i_size =
191 (loff_t)HFSPLUS_I(inode).alloc_blocks <<
192 HFSPLUS_SB(tree->sb).alloc_blksz_shift;
193 HFSPLUS_I(inode).fs_blocks = HFSPLUS_I(inode).alloc_blocks <<
194 HFSPLUS_SB(tree->sb).fs_shift;
195 inode_set_bytes(inode, inode->i_size);
196 count = inode->i_size >> tree->node_size_shift;
197 tree->free_nodes = count - tree->node_count;
198 tree->node_count = count;
202 node = hfs_bnode_find(tree, nidx);
205 len = hfs_brec_lenoff(node, 2, &off);
207 off += node->page_offset;
208 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
210 off &= ~PAGE_CACHE_MASK;
217 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
221 set_page_dirty(*pagep);
224 mark_inode_dirty(tree->inode);
227 printk("unexpected idx %u (%u)\n", idx, node->this);
230 return hfs_bnode_create(tree, idx);
234 if (++off >= PAGE_CACHE_SIZE) {
236 data = kmap(*++pagep);
245 printk("create new bmap node...\n");
246 next_node = hfs_bmap_new_bmap(node, idx);
248 next_node = hfs_bnode_find(tree, nidx);
250 if (IS_ERR(next_node))
254 len = hfs_brec_lenoff(node, 0, &off);
255 off += node->page_offset;
256 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
258 off &= ~PAGE_CACHE_MASK;
262 void hfs_bmap_free(struct hfs_bnode *node)
264 struct hfs_btree *tree;
270 dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
275 node = hfs_bnode_find(tree, 0);
278 len = hfs_brec_lenoff(node, 2, &off);
279 while (nidx >= len * 8) {
287 printk("HFS: unable to free bnode %u. bmap not found!\n", node->this);
290 node = hfs_bnode_find(tree, i);
293 if (node->type != HFS_NODE_MAP) {
295 printk("HFS: invalid bmap found! (%u,%d)\n", node->this, node->type);
299 len = hfs_brec_lenoff(node, 0, &off);
301 off += node->page_offset + nidx / 8;
302 page = node->page[off >> PAGE_CACHE_SHIFT];
304 off &= ~PAGE_CACHE_MASK;
305 m = 1 << (~nidx & 7);
308 printk("HFS: trying to free free bnode %u(%d)\n", node->this, node->type);
313 data[off] = byte & ~m;
314 set_page_dirty(page);
318 mark_inode_dirty(tree->inode);