blob: efb689c21a9586d5c2bfe62499b4c9ebb0ba7091 [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>
Vignesh Babu BMe1b5c1d2007-05-08 00:24:30 -070013#include <linux/log2.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070014
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 */
20struct 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;
David Howells63525392008-02-07 00:15:40 -080025 struct inode *inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -070026 struct page *page;
27 unsigned int size;
28
Panagiotis Issarisf8314dc2006-09-27 01:49:37 -070029 tree = kzalloc(sizeof(*tree), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070030 if (!tree)
31 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -070032
Thomas Gleixner467c3d92010-10-01 05:46:52 +020033 mutex_init(&tree->tree_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070034 spin_lock_init(&tree->hash_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070035 tree->sb = sb;
36 tree->cnid = id;
David Howells63525392008-02-07 00:15:40 -080037 inode = hfsplus_iget(sb, id);
38 if (IS_ERR(inode))
Linus Torvalds1da177e2005-04-16 15:20:36 -070039 goto free_tree;
David Howells63525392008-02-07 00:15:40 -080040 tree->inode = inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -070041
Jeff Mahoneyee527162010-10-14 09:53:37 -040042 if (!HFSPLUS_I(tree->inode)->first_blocks) {
43 printk(KERN_ERR
44 "hfs: invalid btree extent records (0 size).\n");
45 goto free_inode;
46 }
47
Linus Torvalds1da177e2005-04-16 15:20:36 -070048 mapping = tree->inode->i_mapping;
Pekka Enberg090d2b12006-06-23 02:05:08 -070049 page = read_mapping_page(mapping, 0, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -070050 if (IS_ERR(page))
Jeff Mahoneyee527162010-10-14 09:53:37 -040051 goto free_inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -070052
53 /* Load the header */
Anton Salikhmetov2753cc22010-12-16 18:08:38 +020054 head = (struct hfs_btree_header_rec *)(kmap(page) +
55 sizeof(struct hfs_bnode_desc));
Linus Torvalds1da177e2005-04-16 15:20:36 -070056 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
Eric Sandeen9250f922010-10-14 09:53:48 -040067 /* Verify the tree and set the correct compare function */
68 switch (id) {
69 case HFSPLUS_EXT_CNID:
70 if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {
71 printk(KERN_ERR "hfs: invalid extent max_key_len %d\n",
72 tree->max_key_len);
73 goto fail_page;
74 }
Christoph Hellwig13571a62010-10-14 09:54:23 -040075 if (tree->attributes & HFS_TREE_VARIDXKEYS) {
76 printk(KERN_ERR "hfs: invalid extent btree flag\n");
77 goto fail_page;
78 }
79
David Elliott2179d372006-01-18 17:43:08 -080080 tree->keycmp = hfsplus_ext_cmp_key;
Eric Sandeen9250f922010-10-14 09:53:48 -040081 break;
82 case HFSPLUS_CAT_CNID:
83 if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {
84 printk(KERN_ERR "hfs: invalid catalog max_key_len %d\n",
85 tree->max_key_len);
86 goto fail_page;
87 }
Christoph Hellwig13571a62010-10-14 09:54:23 -040088 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
89 printk(KERN_ERR "hfs: invalid catalog btree flag\n");
90 goto fail_page;
91 }
Eric Sandeen9250f922010-10-14 09:53:48 -040092
Christoph Hellwig84adede2010-10-01 05:45:20 +020093 if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) &&
David Elliott2179d372006-01-18 17:43:08 -080094 (head->key_type == HFSPLUS_KEY_BINARY))
95 tree->keycmp = hfsplus_cat_bin_cmp_key;
Duane Griffind45bce82007-07-15 23:41:23 -070096 else {
David Elliott2179d372006-01-18 17:43:08 -080097 tree->keycmp = hfsplus_cat_case_cmp_key;
Christoph Hellwig84adede2010-10-01 05:45:20 +020098 set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
Duane Griffind45bce82007-07-15 23:41:23 -070099 }
Eric Sandeen9250f922010-10-14 09:53:48 -0400100 break;
Vyacheslav Dubeyko324ef392013-02-27 17:03:04 -0800101 case HFSPLUS_ATTR_CNID:
102 if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
103 printk(KERN_ERR "hfs: invalid attributes max_key_len %d\n",
104 tree->max_key_len);
105 goto fail_page;
106 }
107 tree->keycmp = hfsplus_attr_bin_cmp_key;
108 break;
Eric Sandeen9250f922010-10-14 09:53:48 -0400109 default:
David Elliott2179d372006-01-18 17:43:08 -0800110 printk(KERN_ERR "hfs: unknown B*Tree requested\n");
111 goto fail_page;
112 }
113
Christoph Hellwig13571a62010-10-14 09:54:23 -0400114 if (!(tree->attributes & HFS_TREE_BIGKEYS)) {
115 printk(KERN_ERR "hfs: invalid btree flag\n");
116 goto fail_page;
117 }
118
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119 size = tree->node_size;
Vignesh Babu BMe1b5c1d2007-05-08 00:24:30 -0700120 if (!is_power_of_2(size))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 goto fail_page;
122 if (!tree->node_count)
123 goto fail_page;
Eric Sandeen9250f922010-10-14 09:53:48 -0400124
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125 tree->node_size_shift = ffs(size) - 1;
126
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200127 tree->pages_per_bnode =
128 (tree->node_size + PAGE_CACHE_SIZE - 1) >>
129 PAGE_CACHE_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130
131 kunmap(page);
132 page_cache_release(page);
133 return tree;
134
135 fail_page:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 page_cache_release(page);
Jeff Mahoneyee527162010-10-14 09:53:37 -0400137 free_inode:
Eric Sandeen9250f922010-10-14 09:53:48 -0400138 tree->inode->i_mapping->a_ops = &hfsplus_aops;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139 iput(tree->inode);
Jeff Mahoneyee527162010-10-14 09:53:37 -0400140 free_tree:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141 kfree(tree);
142 return NULL;
143}
144
145/* Release resources used by a btree */
146void hfs_btree_close(struct hfs_btree *tree)
147{
148 struct hfs_bnode *node;
149 int i;
150
151 if (!tree)
152 return;
153
154 for (i = 0; i < NODE_HASH_SIZE; i++) {
155 while ((node = tree->node_hash[i])) {
156 tree->node_hash[i] = node->next_hash;
157 if (atomic_read(&node->refcnt))
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200158 printk(KERN_CRIT "hfs: node %d:%d "
159 "still has %d user(s)!\n",
160 node->tree->cnid, node->this,
161 atomic_read(&node->refcnt));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162 hfs_bnode_free(node);
163 tree->node_hash_cnt--;
164 }
165 }
166 iput(tree->inode);
167 kfree(tree);
168}
169
Vyacheslav Dubeyko81cc7fa2012-12-20 15:05:28 -0800170int hfs_btree_write(struct hfs_btree *tree)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700171{
172 struct hfs_btree_header_rec *head;
173 struct hfs_bnode *node;
174 struct page *page;
175
176 node = hfs_bnode_find(tree, 0);
177 if (IS_ERR(node))
178 /* panic? */
Vyacheslav Dubeyko81cc7fa2012-12-20 15:05:28 -0800179 return -EIO;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180 /* Load the header */
181 page = node->page[0];
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200182 head = (struct hfs_btree_header_rec *)(kmap(page) +
183 sizeof(struct hfs_bnode_desc));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700184
185 head->root = cpu_to_be32(tree->root);
186 head->leaf_count = cpu_to_be32(tree->leaf_count);
187 head->leaf_head = cpu_to_be32(tree->leaf_head);
188 head->leaf_tail = cpu_to_be32(tree->leaf_tail);
189 head->node_count = cpu_to_be32(tree->node_count);
190 head->free_nodes = cpu_to_be32(tree->free_nodes);
191 head->attributes = cpu_to_be32(tree->attributes);
192 head->depth = cpu_to_be16(tree->depth);
193
194 kunmap(page);
195 set_page_dirty(page);
196 hfs_bnode_put(node);
Vyacheslav Dubeyko81cc7fa2012-12-20 15:05:28 -0800197 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700198}
199
200static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx)
201{
202 struct hfs_btree *tree = prev->tree;
203 struct hfs_bnode *node;
204 struct hfs_bnode_desc desc;
205 __be32 cnid;
206
207 node = hfs_bnode_create(tree, idx);
208 if (IS_ERR(node))
209 return node;
210
211 tree->free_nodes--;
212 prev->next = idx;
213 cnid = cpu_to_be32(idx);
214 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4);
215
216 node->type = HFS_NODE_MAP;
217 node->num_recs = 1;
218 hfs_bnode_clear(node, 0, tree->node_size);
219 desc.next = 0;
220 desc.prev = 0;
221 desc.type = HFS_NODE_MAP;
222 desc.height = 0;
223 desc.num_recs = cpu_to_be16(1);
224 desc.reserved = 0;
225 hfs_bnode_write(node, &desc, 0, sizeof(desc));
226 hfs_bnode_write_u16(node, 14, 0x8000);
227 hfs_bnode_write_u16(node, tree->node_size - 2, 14);
228 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
229
230 return node;
231}
232
233struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
234{
235 struct hfs_bnode *node, *next_node;
236 struct page **pagep;
237 u32 nidx, idx;
Andrew Morton487798d2008-04-30 00:54:54 -0700238 unsigned off;
239 u16 off16;
240 u16 len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241 u8 *data, byte, m;
242 int i;
243
244 while (!tree->free_nodes) {
245 struct inode *inode = tree->inode;
Christoph Hellwig6af502d2010-10-01 05:43:31 +0200246 struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700247 u32 count;
248 int res;
249
250 res = hfsplus_file_extend(inode);
251 if (res)
252 return ERR_PTR(res);
Christoph Hellwig6af502d2010-10-01 05:43:31 +0200253 hip->phys_size = inode->i_size =
254 (loff_t)hip->alloc_blocks <<
Christoph Hellwigdd73a012010-10-01 05:42:59 +0200255 HFSPLUS_SB(tree->sb)->alloc_blksz_shift;
Christoph Hellwig6af502d2010-10-01 05:43:31 +0200256 hip->fs_blocks =
257 hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258 inode_set_bytes(inode, inode->i_size);
259 count = inode->i_size >> tree->node_size_shift;
260 tree->free_nodes = count - tree->node_count;
261 tree->node_count = count;
262 }
263
264 nidx = 0;
265 node = hfs_bnode_find(tree, nidx);
266 if (IS_ERR(node))
267 return node;
Andrew Morton487798d2008-04-30 00:54:54 -0700268 len = hfs_brec_lenoff(node, 2, &off16);
269 off = off16;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270
271 off += node->page_offset;
272 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
273 data = kmap(*pagep);
274 off &= ~PAGE_CACHE_MASK;
275 idx = 0;
276
277 for (;;) {
278 while (len) {
279 byte = data[off];
280 if (byte != 0xff) {
281 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
282 if (!(byte & m)) {
283 idx += i;
284 data[off] |= m;
285 set_page_dirty(*pagep);
286 kunmap(*pagep);
287 tree->free_nodes--;
288 mark_inode_dirty(tree->inode);
289 hfs_bnode_put(node);
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200290 return hfs_bnode_create(tree,
291 idx);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 }
293 }
294 }
295 if (++off >= PAGE_CACHE_SIZE) {
296 kunmap(*pagep);
297 data = kmap(*++pagep);
298 off = 0;
299 }
300 idx += 8;
301 len--;
302 }
303 kunmap(*pagep);
304 nidx = node->next;
305 if (!nidx) {
Christoph Hellwig6d1bbfc2010-11-23 14:37:40 +0100306 dprint(DBG_BNODE_MOD, "hfs: create new bmap node.\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700307 next_node = hfs_bmap_new_bmap(node, idx);
308 } else
309 next_node = hfs_bnode_find(tree, nidx);
310 hfs_bnode_put(node);
311 if (IS_ERR(next_node))
312 return next_node;
313 node = next_node;
314
Andrew Morton487798d2008-04-30 00:54:54 -0700315 len = hfs_brec_lenoff(node, 0, &off16);
316 off = off16;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317 off += node->page_offset;
318 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
319 data = kmap(*pagep);
320 off &= ~PAGE_CACHE_MASK;
321 }
322}
323
324void hfs_bmap_free(struct hfs_bnode *node)
325{
326 struct hfs_btree *tree;
327 struct page *page;
328 u16 off, len;
329 u32 nidx;
330 u8 *data, byte, m;
331
332 dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
Eric Sesterhenn0bf3ba52006-04-01 01:14:43 +0200333 BUG_ON(!node->this);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 tree = node->tree;
335 nidx = node->this;
336 node = hfs_bnode_find(tree, 0);
337 if (IS_ERR(node))
338 return;
339 len = hfs_brec_lenoff(node, 2, &off);
340 while (nidx >= len * 8) {
341 u32 i;
342
343 nidx -= len * 8;
344 i = node->next;
345 hfs_bnode_put(node);
346 if (!i) {
347 /* panic */;
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200348 printk(KERN_CRIT "hfs: unable to free bnode %u. "
349 "bmap not found!\n",
350 node->this);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700351 return;
352 }
353 node = hfs_bnode_find(tree, i);
354 if (IS_ERR(node))
355 return;
356 if (node->type != HFS_NODE_MAP) {
357 /* panic */;
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200358 printk(KERN_CRIT "hfs: invalid bmap found! "
359 "(%u,%d)\n",
360 node->this, node->type);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361 hfs_bnode_put(node);
362 return;
363 }
364 len = hfs_brec_lenoff(node, 0, &off);
365 }
366 off += node->page_offset + nidx / 8;
367 page = node->page[off >> PAGE_CACHE_SHIFT];
368 data = kmap(page);
369 off &= ~PAGE_CACHE_MASK;
370 m = 1 << (~nidx & 7);
371 byte = data[off];
372 if (!(byte & m)) {
Anton Salikhmetov2753cc22010-12-16 18:08:38 +0200373 printk(KERN_CRIT "hfs: trying to free free bnode "
374 "%u(%d)\n",
375 node->this, node->type);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 kunmap(page);
377 hfs_bnode_put(node);
378 return;
379 }
380 data[off] = byte & ~m;
381 set_page_dirty(page);
382 kunmap(page);
383 hfs_bnode_put(node);
384 tree->free_nodes++;
385 mark_inode_dirty(tree->inode);
386}