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