aboutsummaryrefslogtreecommitdiffstats
path: root/fs/hfsplus/btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/hfsplus/btree.c')
-rw-r--r--fs/hfsplus/btree.c319
1 files changed, 319 insertions, 0 deletions
diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
new file mode 100644
index 000000000000..44326aa2bd34
--- /dev/null
+++ b/fs/hfsplus/btree.c
@@ -0,0 +1,319 @@
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 */
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 {
42 printk("HFS+-fs: unknown B*Tree requested\n");
43 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))
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--;
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);
226 if (!idx) {
227 printk("unexpected idx %u (%u)\n", idx, node->this);
228 BUG();
229 }
230 return hfs_bnode_create(tree, idx);
231 }
232 }
233 }
234 if (++off >= PAGE_CACHE_SIZE) {
235 kunmap(*pagep);
236 data = kmap(*++pagep);
237 off = 0;
238 }
239 idx += 8;
240 len--;
241 }
242 kunmap(*pagep);
243 nidx = node->next;
244 if (!nidx) {
245 printk("create new bmap node...\n");
246 next_node = hfs_bmap_new_bmap(node, idx);
247 } else
248 next_node = hfs_bnode_find(tree, nidx);
249 hfs_bnode_put(node);
250 if (IS_ERR(next_node))
251 return next_node;
252 node = next_node;
253
254 len = hfs_brec_lenoff(node, 0, &off);
255 off += node->page_offset;
256 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
257 data = kmap(*pagep);
258 off &= ~PAGE_CACHE_MASK;
259 }
260}
261
262void hfs_bmap_free(struct hfs_bnode *node)
263{
264 struct hfs_btree *tree;
265 struct page *page;
266 u16 off, len;
267 u32 nidx;
268 u8 *data, byte, m;
269
270 dprint(DBG_BNODE_MOD, "btree_free_node: %u\n", node->this);
271 if (!node->this)
272 BUG();
273 tree = node->tree;
274 nidx = node->this;
275 node = hfs_bnode_find(tree, 0);
276 if (IS_ERR(node))
277 return;
278 len = hfs_brec_lenoff(node, 2, &off);
279 while (nidx >= len * 8) {
280 u32 i;
281
282 nidx -= len * 8;
283 i = node->next;
284 hfs_bnode_put(node);
285 if (!i) {
286 /* panic */;
287 printk("HFS: unable to free bnode %u. bmap not found!\n", node->this);
288 return;
289 }
290 node = hfs_bnode_find(tree, i);
291 if (IS_ERR(node))
292 return;
293 if (node->type != HFS_NODE_MAP) {
294 /* panic */;
295 printk("HFS: invalid bmap found! (%u,%d)\n", node->this, node->type);
296 hfs_bnode_put(node);
297 return;
298 }
299 len = hfs_brec_lenoff(node, 0, &off);
300 }
301 off += node->page_offset + nidx / 8;
302 page = node->page[off >> PAGE_CACHE_SHIFT];
303 data = kmap(page);
304 off &= ~PAGE_CACHE_MASK;
305 m = 1 << (~nidx & 7);
306 byte = data[off];
307 if (!(byte & m)) {
308 printk("HFS: trying to free free bnode %u(%d)\n", node->this, node->type);
309 kunmap(page);
310 hfs_bnode_put(node);
311 return;
312 }
313 data[off] = byte & ~m;
314 set_page_dirty(page);
315 kunmap(page);
316 hfs_bnode_put(node);
317 tree->free_nodes++;
318 mark_inode_dirty(tree->inode);
319}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-27 11:12:26 -0500