1
2
3
4
5
6
7
8
9
10
11#include <linux/slab.h>
12#include <linux/pagemap.h>
13#include <asm/div64.h>
14
15#include "hfsplus_fs.h"
16#include "hfsplus_raw.h"
17
18
19void hfsplus_close_btree(struct hfsplus_btree *tree)
20{
21 hfsplus_bnode *node;
22 int i;
23
24 if (!tree)
25 return;
26
27 for (i = 0; i < NODE_HASH_SIZE; i++) {
28 while ((node = tree->node_hash[i])) {
29 tree->node_hash[i] = node->next_hash;
30 if (atomic_read(&node->refcnt))
31 printk("HFS+: node %d:%d still has %d user(s)!\n",
32 node->tree->cnid, node->this, atomic_read(&node->refcnt));
33 hfsplus_bnode_free(node);
34 tree->node_hash_cnt--;
35 }
36 }
37 iput(tree->inode);
38 kfree(tree);
39}
40
41
42static void hfsplus_read_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
43{
44 unsigned int shift, size;
45
46 if (!tree || !hdr)
47 return;
48
49 tree->root = be32_to_cpu(hdr->root);
50 tree->leaf_count = be32_to_cpu(hdr->leaf_count);
51 tree->leaf_head = be32_to_cpu(hdr->leaf_head);
52 tree->leaf_tail = be32_to_cpu(hdr->leaf_tail);
53 tree->node_count = be32_to_cpu(hdr->node_count);
54 tree->free_nodes = be32_to_cpu(hdr->free_nodes);
55 tree->attributes = be32_to_cpu(hdr->attributes);
56 tree->node_size = be16_to_cpu(hdr->node_size);
57 tree->max_key_len = be16_to_cpu(hdr->max_key_len);
58 tree->depth = be16_to_cpu(hdr->depth);
59
60 size = tree->node_size;
61 if (size & (size - 1))
62 ;
63 for (shift = 0; size >>= 1; shift += 1)
64 ;
65 tree->node_size_shift = shift;
66
67 tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
68}
69
70static void hfsplus_write_treeinfo(hfsplus_btree *tree, hfsplus_btree_head *hdr)
71{
72 hdr->root = cpu_to_be32(tree->root);
73 hdr->leaf_count = cpu_to_be32(tree->leaf_count);
74 hdr->leaf_head = cpu_to_be32(tree->leaf_head);
75 hdr->leaf_tail = cpu_to_be32(tree->leaf_tail);
76 hdr->node_count = cpu_to_be32(tree->node_count);
77 hdr->free_nodes = cpu_to_be32(tree->free_nodes);
78 hdr->attributes = cpu_to_be32(tree->attributes);
79 hdr->depth = cpu_to_be16(tree->depth);
80}
81
82
83hfsplus_btree *hfsplus_open_btree(struct super_block *sb, u32 id)
84{
85 hfsplus_btree *tree;
86 hfsplus_btree_head *head;
87 struct address_space *mapping;
88 struct page *page;
89
90 tree = kmalloc(sizeof(struct hfsplus_btree), GFP_KERNEL);
91 if (!tree)
92 return NULL;
93 memset(tree, 0, sizeof(struct hfsplus_btree));
94
95 init_MUTEX(&tree->tree_lock);
96 spin_lock_init(&tree->hash_lock);
97
98 tree->sb = sb;
99 tree->cnid = id;
100 if (id == HFSPLUS_EXT_CNID) {
101 tree->keycmp = hfsplus_cmp_ext_key;
102 } else if (id == HFSPLUS_CAT_CNID) {
103 tree->keycmp = hfsplus_cmp_cat_key;
104 } else {
105 printk("HFS+-fs: unknown B*Tree requested\n");
106 goto free_tree;
107 }
108 tree->inode = iget(sb, id);
109 if (!tree->inode)
110 goto free_tree;
111
112 mapping = tree->inode->i_mapping;
113 page = grab_cache_page(mapping, 0);
114 if (!page)
115 goto free_tree;
116 if (!PageUptodate(page)) {
117 if (mapping->a_ops->readpage(NULL, page))
118 goto fail_page;
119 wait_on_page_locked(page);
120 if (!PageUptodate(page))
121 goto fail_page;
122 } else
123 unlock_page(page);
124
125
126 head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
127 hfsplus_read_treeinfo(tree, head);
128 kunmap(page);
129 page_cache_release(page);
130 return tree;
131
132 fail_page:
133 page_cache_release(page);
134 free_tree:
135 iput(tree->inode);
136 kfree(tree);
137 return NULL;
138}
139
140void hfsplus_write_btree(struct hfsplus_btree *tree)
141{
142 hfsplus_btree_head *head;
143 hfsplus_bnode *node;
144 struct page *page;
145
146 node = hfsplus_find_bnode(tree, 0);
147 if (!node)
148
149 return;
150
151 page = node->page[0];
152 head = (hfsplus_btree_head *)(kmap(page) + sizeof(hfsplus_btree_node_desc));
153 hfsplus_write_treeinfo(tree, head);
154 kunmap(page);
155 set_page_dirty(page);
156 hfsplus_put_bnode(node);
157}
158
159hfsplus_bnode *hfsplus_btree_alloc_node(hfsplus_btree *tree)
160{
161 hfsplus_bnode *node;
162 struct page **pagep;
163 u32 nidx;
164 u16 idx, off, len;
165 u8 *data, byte, m;
166 int i;
167
168 while (!tree->free_nodes) {
169 loff_t size;
170 int res;
171
172 res = hfsplus_extend_file(tree->inode);
173 if (res)
174 return ERR_PTR(res);
175 HFSPLUS_I(tree->inode).total_blocks = HFSPLUS_I(tree->inode).alloc_blocks;
176 size = HFSPLUS_I(tree->inode).total_blocks;
177 size <<= tree->sb->s_blocksize_bits;
178 tree->inode->i_size = size;
179 do_div(size, (u32)tree->node_size);
180 tree->free_nodes = (u32)size - tree->node_count;
181 tree->node_count = size;
182 }
183
184 nidx = 0;
185 node = hfsplus_find_bnode(tree, nidx);
186 len = hfsplus_brec_lenoff(node, 2, &off);
187
188 off += node->page_offset;
189 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
190 data = hfsplus_kmap(*pagep);
191 off &= ~PAGE_CACHE_MASK;
192 idx = 0;
193
194 for (;;) {
195 while (len) {
196 byte = data[off];
197 if (byte != 0xff) {
198 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
199 if (!(byte & m)) {
200 idx += i;
201 data[off] |= m;
202 set_page_dirty(*pagep);
203 hfsplus_kunmap(*pagep);
204 tree->free_nodes--;
205 mark_inode_dirty(tree->inode);
206 hfsplus_put_bnode(node);
207 return hfsplus_create_bnode(tree, idx);
208 }
209 }
210 }
211 if (++off >= PAGE_CACHE_SIZE) {
212 hfsplus_kunmap(*pagep++);
213 data = hfsplus_kmap(*pagep);
214 off = 0;
215 }
216 idx += 8;
217 len--;
218 }
219 nidx = node->next;
220 hfsplus_put_bnode(node);
221 if (!nidx) {
222 printk("need new bmap node...\n");
223 hfsplus_kunmap(*pagep);
224 return ERR_PTR(-ENOSPC);
225 }
226 node = hfsplus_find_bnode(tree, nidx);
227 len = hfsplus_brec_lenoff(node, 0, &off);
228
229 off += node->page_offset;
230 pagep = node->page + (off >> PAGE_CACHE_SHIFT);
231 data = hfsplus_kmap(*pagep);
232 off &= ~PAGE_CACHE_MASK;
233 }
234}
235
236void hfsplus_btree_remove_node(hfsplus_bnode *node)
237{
238 hfsplus_btree *tree;
239 hfsplus_bnode *tmp;
240 u32 cnid;
241
242 tree = node->tree;
243 if (node->prev) {
244 tmp = hfsplus_find_bnode(tree, node->prev);
245 tmp->next = node->next;
246 cnid = cpu_to_be32(tmp->next);
247 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, next), 4);
248 hfsplus_put_bnode(tmp);
249 } else if (node->kind == HFSPLUS_NODE_LEAF)
250 tree->leaf_head = node->next;
251
252 if (node->next) {
253 tmp = hfsplus_find_bnode(tree, node->next);
254 tmp->prev = node->prev;
255 cnid = cpu_to_be32(tmp->prev);
256 hfsplus_bnode_writebytes(tmp, &cnid, offsetof(hfsplus_btree_node_desc, prev), 4);
257 hfsplus_put_bnode(tmp);
258 } else if (node->kind == HFSPLUS_NODE_LEAF)
259 tree->leaf_tail = node->prev;
260
261
262 if (!node->prev && !node->next) {
263 printk("hfsplus_btree_del_level\n");
264 }
265 if (!node->parent) {
266 tree->root = 0;
267 tree->depth = 0;
268 }
269 set_bit(HFSPLUS_BNODE_DELETED, &node->flags);
270}
271
272void hfsplus_btree_free_node(hfsplus_bnode *node)
273{
274 hfsplus_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 = hfsplus_find_bnode(tree, 0);
284 len = hfsplus_brec_lenoff(node, 2, &off);
285 while (nidx >= len * 8) {
286 u32 i;
287
288 nidx -= len * 8;
289 i = node->next;
290 hfsplus_put_bnode(node);
291 if (!nidx)
292 ;
293 node = hfsplus_find_bnode(tree, nidx);
294 if (node->kind != HFSPLUS_NODE_MAP)
295 ;
296 len = hfsplus_brec_lenoff(node, 0, &off);
297 }
298 off += node->page_offset + nidx / 8;
299 page = node->page[off >> PAGE_CACHE_SHIFT];
300 data = hfsplus_kmap(page);
301 off &= ~PAGE_CACHE_MASK;
302 m = 1 << (~nidx & 7);
303 byte = data[off];
304 if (!(byte & m)) {
305 BUG();
306
307 hfsplus_kunmap(page);
308 hfsplus_put_bnode(node);
309 return;
310 }
311 data[off] = byte & ~m;
312 set_page_dirty(page);
313 hfsplus_kunmap(page);
314 hfsplus_put_bnode(node);
315 tree->free_nodes++;
316 mark_inode_dirty(tree->inode);
317}
318
