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

source code of linux/fs/hfs/btree.c