1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * linux/fs/hfs/btree.c |
4 | * |
5 | * Copyright (C) 2001 |
6 | * Brad Boyer (flar@allandria.com) |
7 | * (C) 2003 Ardis Technologies <roman@ardistech.com> |
8 | * |
9 | * Handle opening/closing btree |
10 | */ |
11 | |
12 | #include <linux/pagemap.h> |
13 | #include <linux/slab.h> |
14 | #include <linux/log2.h> |
15 | |
16 | #include "btree.h" |
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, btree_keycmp keycmp) |
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 = kzalloc(size: sizeof(*tree), GFP_KERNEL); |
28 | if (!tree) |
29 | return NULL; |
30 | |
31 | mutex_init(&tree->tree_lock); |
32 | spin_lock_init(&tree->hash_lock); |
33 | /* Set the correct compare function */ |
34 | tree->sb = sb; |
35 | tree->cnid = id; |
36 | tree->keycmp = keycmp; |
37 | |
38 | tree->inode = iget_locked(sb, id); |
39 | if (!tree->inode) |
40 | goto free_tree; |
41 | BUG_ON(!(tree->inode->i_state & I_NEW)); |
42 | { |
43 | struct hfs_mdb *mdb = HFS_SB(sb)->mdb; |
44 | HFS_I(tree->inode)->flags = 0; |
45 | mutex_init(&HFS_I(tree->inode)->extents_lock); |
46 | switch (id) { |
47 | case HFS_EXT_CNID: |
48 | hfs_inode_read_fork(inode: tree->inode, ext: mdb->drXTExtRec, log_size: mdb->drXTFlSize, |
49 | phys_size: mdb->drXTFlSize, be32_to_cpu(mdb->drXTClpSiz)); |
50 | if (HFS_I(tree->inode)->alloc_blocks > |
51 | HFS_I(tree->inode)->first_blocks) { |
52 | pr_err("invalid btree extent records\n" ); |
53 | unlock_new_inode(tree->inode); |
54 | goto free_inode; |
55 | } |
56 | |
57 | tree->inode->i_mapping->a_ops = &hfs_btree_aops; |
58 | break; |
59 | case HFS_CAT_CNID: |
60 | hfs_inode_read_fork(inode: tree->inode, ext: mdb->drCTExtRec, log_size: mdb->drCTFlSize, |
61 | phys_size: mdb->drCTFlSize, be32_to_cpu(mdb->drCTClpSiz)); |
62 | |
63 | if (!HFS_I(tree->inode)->first_blocks) { |
64 | pr_err("invalid btree extent records (0 size)\n" ); |
65 | unlock_new_inode(tree->inode); |
66 | goto free_inode; |
67 | } |
68 | |
69 | tree->inode->i_mapping->a_ops = &hfs_btree_aops; |
70 | break; |
71 | default: |
72 | BUG(); |
73 | } |
74 | } |
75 | unlock_new_inode(tree->inode); |
76 | |
77 | mapping = tree->inode->i_mapping; |
78 | page = read_mapping_page(mapping, index: 0, NULL); |
79 | if (IS_ERR(ptr: page)) |
80 | goto free_inode; |
81 | |
82 | /* Load the header */ |
83 | head = (struct hfs_btree_header_rec *)(kmap_local_page(page) + |
84 | sizeof(struct hfs_bnode_desc)); |
85 | tree->root = be32_to_cpu(head->root); |
86 | tree->leaf_count = be32_to_cpu(head->leaf_count); |
87 | tree->leaf_head = be32_to_cpu(head->leaf_head); |
88 | tree->leaf_tail = be32_to_cpu(head->leaf_tail); |
89 | tree->node_count = be32_to_cpu(head->node_count); |
90 | tree->free_nodes = be32_to_cpu(head->free_nodes); |
91 | tree->attributes = be32_to_cpu(head->attributes); |
92 | tree->node_size = be16_to_cpu(head->node_size); |
93 | tree->max_key_len = be16_to_cpu(head->max_key_len); |
94 | tree->depth = be16_to_cpu(head->depth); |
95 | |
96 | size = tree->node_size; |
97 | if (!is_power_of_2(n: size)) |
98 | goto fail_page; |
99 | if (!tree->node_count) |
100 | goto fail_page; |
101 | switch (id) { |
102 | case HFS_EXT_CNID: |
103 | if (tree->max_key_len != HFS_MAX_EXT_KEYLEN) { |
104 | pr_err("invalid extent max_key_len %d\n" , |
105 | tree->max_key_len); |
106 | goto fail_page; |
107 | } |
108 | break; |
109 | case HFS_CAT_CNID: |
110 | if (tree->max_key_len != HFS_MAX_CAT_KEYLEN) { |
111 | pr_err("invalid catalog max_key_len %d\n" , |
112 | tree->max_key_len); |
113 | goto fail_page; |
114 | } |
115 | break; |
116 | default: |
117 | BUG(); |
118 | } |
119 | |
120 | tree->node_size_shift = ffs(size) - 1; |
121 | tree->pages_per_bnode = (tree->node_size + PAGE_SIZE - 1) >> PAGE_SHIFT; |
122 | |
123 | kunmap_local(head); |
124 | put_page(page); |
125 | return tree; |
126 | |
127 | fail_page: |
128 | kunmap_local(head); |
129 | put_page(page); |
130 | free_inode: |
131 | tree->inode->i_mapping->a_ops = &hfs_aops; |
132 | iput(tree->inode); |
133 | free_tree: |
134 | kfree(objp: tree); |
135 | return NULL; |
136 | } |
137 | |
138 | /* Release resources used by a btree */ |
139 | void hfs_btree_close(struct hfs_btree *tree) |
140 | { |
141 | struct hfs_bnode *node; |
142 | int i; |
143 | |
144 | if (!tree) |
145 | return; |
146 | |
147 | for (i = 0; i < NODE_HASH_SIZE; i++) { |
148 | while ((node = tree->node_hash[i])) { |
149 | tree->node_hash[i] = node->next_hash; |
150 | if (atomic_read(v: &node->refcnt)) |
151 | pr_err("node %d:%d still has %d user(s)!\n" , |
152 | node->tree->cnid, node->this, |
153 | atomic_read(&node->refcnt)); |
154 | hfs_bnode_free(node); |
155 | tree->node_hash_cnt--; |
156 | } |
157 | } |
158 | iput(tree->inode); |
159 | kfree(objp: tree); |
160 | } |
161 | |
162 | void hfs_btree_write(struct hfs_btree *tree) |
163 | { |
164 | struct hfs_btree_header_rec *head; |
165 | struct hfs_bnode *node; |
166 | struct page *page; |
167 | |
168 | node = hfs_bnode_find(tree, 0); |
169 | if (IS_ERR(ptr: node)) |
170 | /* panic? */ |
171 | return; |
172 | /* Load the header */ |
173 | page = node->page[0]; |
174 | head = (struct hfs_btree_header_rec *)(kmap_local_page(page) + |
175 | sizeof(struct hfs_bnode_desc)); |
176 | |
177 | head->root = cpu_to_be32(tree->root); |
178 | head->leaf_count = cpu_to_be32(tree->leaf_count); |
179 | head->leaf_head = cpu_to_be32(tree->leaf_head); |
180 | head->leaf_tail = cpu_to_be32(tree->leaf_tail); |
181 | head->node_count = cpu_to_be32(tree->node_count); |
182 | head->free_nodes = cpu_to_be32(tree->free_nodes); |
183 | head->attributes = cpu_to_be32(tree->attributes); |
184 | head->depth = cpu_to_be16(tree->depth); |
185 | |
186 | kunmap_local(head); |
187 | set_page_dirty(page); |
188 | hfs_bnode_put(node); |
189 | } |
190 | |
191 | static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx) |
192 | { |
193 | struct hfs_btree *tree = prev->tree; |
194 | struct hfs_bnode *node; |
195 | struct hfs_bnode_desc desc; |
196 | __be32 cnid; |
197 | |
198 | node = hfs_bnode_create(tree, idx); |
199 | if (IS_ERR(ptr: node)) |
200 | return node; |
201 | |
202 | if (!tree->free_nodes) |
203 | panic(fmt: "FIXME!!!" ); |
204 | tree->free_nodes--; |
205 | prev->next = idx; |
206 | cnid = cpu_to_be32(idx); |
207 | hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4); |
208 | |
209 | node->type = HFS_NODE_MAP; |
210 | node->num_recs = 1; |
211 | hfs_bnode_clear(node, 0, tree->node_size); |
212 | desc.next = 0; |
213 | desc.prev = 0; |
214 | desc.type = HFS_NODE_MAP; |
215 | desc.height = 0; |
216 | desc.num_recs = cpu_to_be16(1); |
217 | desc.reserved = 0; |
218 | hfs_bnode_write(node, &desc, 0, sizeof(desc)); |
219 | hfs_bnode_write_u16(node, 14, 0x8000); |
220 | hfs_bnode_write_u16(node, tree->node_size - 2, 14); |
221 | hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); |
222 | |
223 | return node; |
224 | } |
225 | |
226 | /* Make sure @tree has enough space for the @rsvd_nodes */ |
227 | int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes) |
228 | { |
229 | struct inode *inode = tree->inode; |
230 | u32 count; |
231 | int res; |
232 | |
233 | while (tree->free_nodes < rsvd_nodes) { |
234 | res = hfs_extend_file(inode); |
235 | if (res) |
236 | return res; |
237 | HFS_I(inode)->phys_size = inode->i_size = |
238 | (loff_t)HFS_I(inode)->alloc_blocks * |
239 | HFS_SB(tree->sb)->alloc_blksz; |
240 | HFS_I(inode)->fs_blocks = inode->i_size >> |
241 | tree->sb->s_blocksize_bits; |
242 | inode_set_bytes(inode, bytes: inode->i_size); |
243 | count = inode->i_size >> tree->node_size_shift; |
244 | tree->free_nodes += count - tree->node_count; |
245 | tree->node_count = count; |
246 | } |
247 | return 0; |
248 | } |
249 | |
250 | struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) |
251 | { |
252 | struct hfs_bnode *node, *next_node; |
253 | struct page **pagep; |
254 | u32 nidx, idx; |
255 | unsigned off; |
256 | u16 off16; |
257 | u16 len; |
258 | u8 *data, byte, m; |
259 | int i, res; |
260 | |
261 | res = hfs_bmap_reserve(tree, rsvd_nodes: 1); |
262 | if (res) |
263 | return ERR_PTR(error: res); |
264 | |
265 | nidx = 0; |
266 | node = hfs_bnode_find(tree, nidx); |
267 | if (IS_ERR(ptr: node)) |
268 | return node; |
269 | len = hfs_brec_lenoff(node, 2, &off16); |
270 | off = off16; |
271 | |
272 | off += node->page_offset; |
273 | pagep = node->page + (off >> PAGE_SHIFT); |
274 | data = kmap_local_page(page: *pagep); |
275 | off &= ~PAGE_MASK; |
276 | idx = 0; |
277 | |
278 | for (;;) { |
279 | while (len) { |
280 | byte = data[off]; |
281 | if (byte != 0xff) { |
282 | for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { |
283 | if (!(byte & m)) { |
284 | idx += i; |
285 | data[off] |= m; |
286 | set_page_dirty(*pagep); |
287 | kunmap_local(data); |
288 | tree->free_nodes--; |
289 | mark_inode_dirty(inode: tree->inode); |
290 | hfs_bnode_put(node); |
291 | return hfs_bnode_create(tree, idx); |
292 | } |
293 | } |
294 | } |
295 | if (++off >= PAGE_SIZE) { |
296 | kunmap_local(data); |
297 | data = kmap_local_page(page: *++pagep); |
298 | off = 0; |
299 | } |
300 | idx += 8; |
301 | len--; |
302 | } |
303 | kunmap_local(data); |
304 | nidx = node->next; |
305 | if (!nidx) { |
306 | printk(KERN_DEBUG "create new bmap node...\n" ); |
307 | next_node = hfs_bmap_new_bmap(prev: node, idx); |
308 | } else |
309 | next_node = hfs_bnode_find(tree, nidx); |
310 | hfs_bnode_put(node); |
311 | if (IS_ERR(ptr: next_node)) |
312 | return next_node; |
313 | node = next_node; |
314 | |
315 | len = hfs_brec_lenoff(node, 0, &off16); |
316 | off = off16; |
317 | off += node->page_offset; |
318 | pagep = node->page + (off >> PAGE_SHIFT); |
319 | data = kmap_local_page(page: *pagep); |
320 | off &= ~PAGE_MASK; |
321 | } |
322 | } |
323 | |
324 | void 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 | hfs_dbg(BNODE_MOD, "btree_free_node: %u\n" , node->this); |
333 | tree = node->tree; |
334 | nidx = node->this; |
335 | node = hfs_bnode_find(tree, 0); |
336 | if (IS_ERR(ptr: node)) |
337 | return; |
338 | len = hfs_brec_lenoff(node, 2, &off); |
339 | while (nidx >= len * 8) { |
340 | u32 i; |
341 | |
342 | nidx -= len * 8; |
343 | i = node->next; |
344 | if (!i) { |
345 | /* panic */; |
346 | pr_crit("unable to free bnode %u. bmap not found!\n" , |
347 | node->this); |
348 | hfs_bnode_put(node); |
349 | return; |
350 | } |
351 | hfs_bnode_put(node); |
352 | node = hfs_bnode_find(tree, i); |
353 | if (IS_ERR(ptr: node)) |
354 | return; |
355 | if (node->type != HFS_NODE_MAP) { |
356 | /* panic */; |
357 | pr_crit("invalid bmap found! (%u,%d)\n" , |
358 | node->this, node->type); |
359 | hfs_bnode_put(node); |
360 | return; |
361 | } |
362 | len = hfs_brec_lenoff(node, 0, &off); |
363 | } |
364 | off += node->page_offset + nidx / 8; |
365 | page = node->page[off >> PAGE_SHIFT]; |
366 | data = kmap_local_page(page); |
367 | off &= ~PAGE_MASK; |
368 | m = 1 << (~nidx & 7); |
369 | byte = data[off]; |
370 | if (!(byte & m)) { |
371 | pr_crit("trying to free free bnode %u(%d)\n" , |
372 | node->this, node->type); |
373 | kunmap_local(data); |
374 | hfs_bnode_put(node); |
375 | return; |
376 | } |
377 | data[off] = byte & ~m; |
378 | set_page_dirty(page); |
379 | kunmap_local(data); |
380 | hfs_bnode_put(node); |
381 | tree->free_nodes++; |
382 | mark_inode_dirty(inode: tree->inode); |
383 | } |
384 | |