blob: 671290663838151b12f1bd1066516d6a4efdfa47 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
14#include "hfsplus_fs.h"
15#include "hfsplus_raw.h"
16
17
18/* Get a reference to a B*Tree and do some initial checks */
19struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
20{
21 struct hfs_btree *tree;
22 struct hfs_btree_header_rec *head;
23 struct address_space *mapping;
24 struct page *page;
25 unsigned int size;
26
27 tree = kmalloc(sizeof(*tree), GFP_KERNEL);
28 if (!tree)
29 return NULL;
30 memset(tree, 0, sizeof(*tree));
31
32 init_MUTEX(&tree->tree_lock);
33 spin_lock_init(&tree->hash_lock);
34 /* Set the correct compare function */
35 tree->sb = sb;
36 tree->cnid = id;
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;
41 } else {
Roman Zippel634725a2006-01-18 17:43:05 -080042 printk(KERN_ERR "hfs: unknown B*Tree requested\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -070043 goto free_tree;
44 }
45 tree->inode = iget(sb, id);
46 if (!tree->inode)
47 goto free_tree;
48
49 mapping = tree->inode->i_mapping;
50 page = read_cache_page(mapping, 0, (filler_t *)mapping->a_ops->readpage, NULL);
51 if (IS_ERR(page))
52 goto free_tree;
53
54 /* Load the header */
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);
66
67 size = tree->node_size;
68 if (!size || size & (size - 1))
69 goto fail_page;
70 if (!tree->node_count)
71 goto fail_page;
72 tree->node_size_shift = ffs(size) - 1;
73
74 tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
75
76 kunmap(page);
77 page_cache_release(page);
78 return tree;
79
80 fail_page:
81 tree->inode->i_mapping->a_ops = &hfsplus_aops;
82 page_cache_release(page);
83 free_tree:
84 iput(tree->inode);
85 kfree(tree);
86 return NULL;
87}
88
89/* Release resources used by a btree */
90void hfs_btree_close(struct hfs_btree *tree)
91{
92 struct hfs_bnode *node;
93 int i;
94
95 if (!tree)
96 return;
97
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))
Roman Zippel634725a2006-01-18 17:43:05 -0800102 printk(KERN_CRIT "hfs: node %d:%d still has %d user(s)!\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103 node->tree->cnid, node->this, atomic_read(&node->refcnt));
104 hfs_bnode_free(node);
105 tree->node_hash_cnt--;
106 }
107 }
108 iput(tree->inode);
109 kfree(tree);
110}
111
112void hfs_btree_write(struct hfs_btree *tree)
113{
114 struct hfs_btree_header_rec *head;
115 struct hfs_bnode *node;
116 struct page *page;
117
118 node = hfs_bnode_find(tree, 0);
119 if (IS_ERR(node))
120 /* panic? */
121 return;
122 /* Load the header */
123 page = node->page[0];
124 head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc));
125
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);
134
135 kunmap(page);
136 set_page_dirty(page);
137 hfs_bnode_put(node);
138}
139
140static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
141{
142 struct hfs_btree *tree = prev->tree;
143 struct hfs_bnode *node;
144 struct hfs_bnode_desc desc;
145 __be32 cnid;
146
147 node = hfs_bnode_create(tree, idx);
148 if (IS_ERR(node))
149 return node;
150
151 tree->free_nodes--;
152 prev->next = idx;
153 cnid = cpu_to_be32(idx);
154 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
155
156 node->type = HFS_NODE_MAP;
157 node->num_recs = 1;
158 hfs_bnode_clear(node, 0, tree->node_size);
159 desc.next = 0;
160 desc.prev = 0;
161 desc.type = HFS_NODE_MAP;
162 desc.height = 0;
163 desc.num_recs = cpu_to_be16(1);
164 desc.reserved = 0;
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);
169
170 return node;
171}
172
173struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
174{
175 struct hfs_bnode *node, *next_node;
176 struct page **pagep;
177 u32 nidx, idx;
178 u16 off, len;
179 u8 *data, byte, m;
180 int i;
181
182 while (!tree->free_nodes) {
183 struct inode *inode = tree->inode;
184 u32 count;
185 int res;
186
187 res = hfsplus_file_extend(inode);
188 if (res)
189 return ERR_PTR(res);
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;
199 }
200
201 nidx = 0;
202 node = hfs_bnode_find(tree, nidx);
203 if (IS_ERR(node))
204 return node;
205 len = hfs_brec_lenoff(node, 2, &off);
206
207 off += node->page_offset;
208 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
209 data = kmap(*pagep);
210 off &= ~PAGE_CACHE_MASK;
211 idx = 0;
212
213 for (;;) {
214 while (len) {
215 byte = data[off];
216 if (byte != 0xff) {
217 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
218 if (!(byte & m)) {
219 idx += i;
220 data[off] |= m;
221 set_page_dirty(*pagep);
222 kunmap(*pagep);
223 tree->free_nodes--;
224 mark_inode_dirty(tree->inode);
225 hfs_bnode_put(node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226 return hfs_bnode_create(tree, idx);
227 }
228 }
229 }
230 if (++off >= PAGE_CACHE_SIZE) {
231 kunmap(*pagep);
232 data = kmap(*++pagep);
233 off = 0;
234 }
235 idx += 8;
236 len--;
237 }
238 kunmap(*pagep);
239 nidx = node->next;
240 if (!nidx) {
Roman Zippel634725a2006-01-18 17:43:05 -0800241 printk(KERN_DEBUG "hfs: create new bmap node...\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700242 next_node = hfs_bmap_new_bmap(node, idx);
243 } else
244 next_node = hfs_bnode_find(tree, nidx);
245 hfs_bnode_put(node);
246 if (IS_ERR(next_node))
247 return next_node;
248 node = next_node;
249
250 len = hfs_brec_lenoff(node, 0, &off);
251 off += node->page_offset;
252 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
253 data = kmap(*pagep);
254 off &= ~PAGE_CACHE_MASK;
255 }
256}
257
258void hfs_bmap_free(struct hfs_bnode *node)
259{
260 struct hfs_btree *tree;
261 struct page *page;
262 u16 off, len;
263 u32 nidx;
264 u8 *data, byte, m;
265
266 dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
267 if (!node->this)
268 BUG();
269 tree = node->tree;
270 nidx = node->this;
271 node = hfs_bnode_find(tree, 0);
272 if (IS_ERR(node))
273 return;
274 len = hfs_brec_lenoff(node, 2, &off);
275 while (nidx >= len * 8) {
276 u32 i;
277
278 nidx -= len * 8;
279 i = node->next;
280 hfs_bnode_put(node);
281 if (!i) {
282 /* panic */;
Roman Zippel634725a2006-01-18 17:43:05 -0800283 printk(KERN_CRIT "hfs: unable to free bnode %u. bmap not found!\n", node->this);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700284 return;
285 }
286 node = hfs_bnode_find(tree, i);
287 if (IS_ERR(node))
288 return;
289 if (node->type != HFS_NODE_MAP) {
290 /* panic */;
Roman Zippel634725a2006-01-18 17:43:05 -0800291 printk(KERN_CRIT "hfs: invalid bmap found! (%u,%d)\n", node->this, node->type);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 hfs_bnode_put(node);
293 return;
294 }
295 len = hfs_brec_lenoff(node, 0, &off);
296 }
297 off += node->page_offset + nidx / 8;
298 page = node->page[off >> PAGE_CACHE_SHIFT];
299 data = kmap(page);
300 off &= ~PAGE_CACHE_MASK;
301 m = 1 << (~nidx & 7);
302 byte = data[off];
303 if (!(byte & m)) {
Roman Zippel634725a2006-01-18 17:43:05 -0800304 printk(KERN_CRIT "hfs: trying to free free bnode %u(%d)\n", node->this, node->type);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700305 kunmap(page);
306 hfs_bnode_put(node);
307 return;
308 }
309 data[off] = byte & ~m;
310 set_page_dirty(page);
311 kunmap(page);
312 hfs_bnode_put(node);
313 tree->free_nodes++;
314 mark_inode_dirty(tree->inode);
315}