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