1 // SPDX-License-Identifier: GPL-2.0
3 * linux/fs/hfsplus/bnode.c
6 * Brad Boyer (flar@allandria.com)
7 * (C) 2003 Ardis Technologies <roman@ardistech.com>
9 * Handle basic btree node operations
12 #include <linux/string.h>
13 #include <linux/slab.h>
14 #include <linux/pagemap.h>
16 #include <linux/swap.h>
18 #include "hfsplus_fs.h"
19 #include "hfsplus_raw.h"
21 /* Copy a specified range of bytes from the raw data of a node */
22 void hfs_bnode_read(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
27 off
+= node
->page_offset
;
28 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
31 l
= min_t(int, len
, PAGE_SIZE
- off
);
32 memcpy(buf
, kmap(*pagep
) + off
, l
);
35 while ((len
-= l
) != 0) {
37 l
= min_t(int, len
, PAGE_SIZE
);
38 memcpy(buf
, kmap(*++pagep
), l
);
43 u16
hfs_bnode_read_u16(struct hfs_bnode
*node
, int off
)
46 /* TODO: optimize later... */
47 hfs_bnode_read(node
, &data
, off
, 2);
48 return be16_to_cpu(data
);
51 u8
hfs_bnode_read_u8(struct hfs_bnode
*node
, int off
)
54 /* TODO: optimize later... */
55 hfs_bnode_read(node
, &data
, off
, 1);
59 void hfs_bnode_read_key(struct hfs_bnode
*node
, void *key
, int off
)
61 struct hfs_btree
*tree
;
65 if (node
->type
== HFS_NODE_LEAF
||
66 tree
->attributes
& HFS_TREE_VARIDXKEYS
||
67 node
->tree
->cnid
== HFSPLUS_ATTR_CNID
)
68 key_len
= hfs_bnode_read_u16(node
, off
) + 2;
70 key_len
= tree
->max_key_len
+ 2;
72 hfs_bnode_read(node
, key
, off
, key_len
);
75 void hfs_bnode_write(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
80 off
+= node
->page_offset
;
81 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
84 l
= min_t(int, len
, PAGE_SIZE
- off
);
85 memcpy(kmap(*pagep
) + off
, buf
, l
);
86 set_page_dirty(*pagep
);
89 while ((len
-= l
) != 0) {
91 l
= min_t(int, len
, PAGE_SIZE
);
92 memcpy(kmap(*++pagep
), buf
, l
);
93 set_page_dirty(*pagep
);
98 void hfs_bnode_write_u16(struct hfs_bnode
*node
, int off
, u16 data
)
100 __be16 v
= cpu_to_be16(data
);
101 /* TODO: optimize later... */
102 hfs_bnode_write(node
, &v
, off
, 2);
105 void hfs_bnode_clear(struct hfs_bnode
*node
, int off
, int len
)
110 off
+= node
->page_offset
;
111 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
114 l
= min_t(int, len
, PAGE_SIZE
- off
);
115 memset(kmap(*pagep
) + off
, 0, l
);
116 set_page_dirty(*pagep
);
119 while ((len
-= l
) != 0) {
120 l
= min_t(int, len
, PAGE_SIZE
);
121 memset(kmap(*++pagep
), 0, l
);
122 set_page_dirty(*pagep
);
127 void hfs_bnode_copy(struct hfs_bnode
*dst_node
, int dst
,
128 struct hfs_bnode
*src_node
, int src
, int len
)
130 struct hfs_btree
*tree
;
131 struct page
**src_page
, **dst_page
;
134 hfs_dbg(BNODE_MOD
, "copybytes: %u,%u,%u\n", dst
, src
, len
);
137 tree
= src_node
->tree
;
138 src
+= src_node
->page_offset
;
139 dst
+= dst_node
->page_offset
;
140 src_page
= src_node
->page
+ (src
>> PAGE_SHIFT
);
142 dst_page
= dst_node
->page
+ (dst
>> PAGE_SHIFT
);
146 l
= min_t(int, len
, PAGE_SIZE
- src
);
147 memcpy(kmap(*dst_page
) + src
, kmap(*src_page
) + src
, l
);
149 set_page_dirty(*dst_page
);
152 while ((len
-= l
) != 0) {
153 l
= min_t(int, len
, PAGE_SIZE
);
154 memcpy(kmap(*++dst_page
), kmap(*++src_page
), l
);
156 set_page_dirty(*dst_page
);
160 void *src_ptr
, *dst_ptr
;
163 src_ptr
= kmap(*src_page
) + src
;
164 dst_ptr
= kmap(*dst_page
) + dst
;
165 if (PAGE_SIZE
- src
< PAGE_SIZE
- dst
) {
175 memcpy(dst_ptr
, src_ptr
, l
);
177 set_page_dirty(*dst_page
);
183 } while ((len
-= l
));
187 void hfs_bnode_move(struct hfs_bnode
*node
, int dst
, int src
, int len
)
189 struct page
**src_page
, **dst_page
;
192 hfs_dbg(BNODE_MOD
, "movebytes: %u,%u,%u\n", dst
, src
, len
);
195 src
+= node
->page_offset
;
196 dst
+= node
->page_offset
;
199 src_page
= node
->page
+ (src
>> PAGE_SHIFT
);
200 src
= (src
& ~PAGE_MASK
) + 1;
202 dst_page
= node
->page
+ (dst
>> PAGE_SHIFT
);
203 dst
= (dst
& ~PAGE_MASK
) + 1;
207 memmove(kmap(*dst_page
), kmap(*src_page
), src
);
209 set_page_dirty(*dst_page
);
217 memmove(kmap(*dst_page
) + src
,
218 kmap(*src_page
) + src
, len
);
220 set_page_dirty(*dst_page
);
223 void *src_ptr
, *dst_ptr
;
226 src_ptr
= kmap(*src_page
) + src
;
227 dst_ptr
= kmap(*dst_page
) + dst
;
238 memmove(dst_ptr
- l
, src_ptr
- l
, l
);
240 set_page_dirty(*dst_page
);
242 if (dst
== PAGE_SIZE
)
246 } while ((len
-= l
));
249 src_page
= node
->page
+ (src
>> PAGE_SHIFT
);
251 dst_page
= node
->page
+ (dst
>> PAGE_SHIFT
);
255 l
= min_t(int, len
, PAGE_SIZE
- src
);
256 memmove(kmap(*dst_page
) + src
,
257 kmap(*src_page
) + src
, l
);
259 set_page_dirty(*dst_page
);
262 while ((len
-= l
) != 0) {
263 l
= min_t(int, len
, PAGE_SIZE
);
264 memmove(kmap(*++dst_page
),
265 kmap(*++src_page
), l
);
267 set_page_dirty(*dst_page
);
271 void *src_ptr
, *dst_ptr
;
274 src_ptr
= kmap(*src_page
) + src
;
275 dst_ptr
= kmap(*dst_page
) + dst
;
276 if (PAGE_SIZE
- src
<
287 memmove(dst_ptr
, src_ptr
, l
);
289 set_page_dirty(*dst_page
);
295 } while ((len
-= l
));
300 void hfs_bnode_dump(struct hfs_bnode
*node
)
302 struct hfs_bnode_desc desc
;
306 hfs_dbg(BNODE_MOD
, "bnode: %d\n", node
->this);
307 hfs_bnode_read(node
, &desc
, 0, sizeof(desc
));
308 hfs_dbg(BNODE_MOD
, "%d, %d, %d, %d, %d\n",
309 be32_to_cpu(desc
.next
), be32_to_cpu(desc
.prev
),
310 desc
.type
, desc
.height
, be16_to_cpu(desc
.num_recs
));
312 off
= node
->tree
->node_size
- 2;
313 for (i
= be16_to_cpu(desc
.num_recs
); i
>= 0; off
-= 2, i
--) {
314 key_off
= hfs_bnode_read_u16(node
, off
);
315 hfs_dbg(BNODE_MOD
, " %d", key_off
);
316 if (i
&& node
->type
== HFS_NODE_INDEX
) {
319 if (node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
||
320 node
->tree
->cnid
== HFSPLUS_ATTR_CNID
)
321 tmp
= hfs_bnode_read_u16(node
, key_off
) + 2;
323 tmp
= node
->tree
->max_key_len
+ 2;
324 hfs_dbg_cont(BNODE_MOD
, " (%d", tmp
);
325 hfs_bnode_read(node
, &cnid
, key_off
+ tmp
, 4);
326 hfs_dbg_cont(BNODE_MOD
, ",%d)", be32_to_cpu(cnid
));
327 } else if (i
&& node
->type
== HFS_NODE_LEAF
) {
330 tmp
= hfs_bnode_read_u16(node
, key_off
);
331 hfs_dbg_cont(BNODE_MOD
, " (%d)", tmp
);
334 hfs_dbg_cont(BNODE_MOD
, "\n");
337 void hfs_bnode_unlink(struct hfs_bnode
*node
)
339 struct hfs_btree
*tree
;
340 struct hfs_bnode
*tmp
;
345 tmp
= hfs_bnode_find(tree
, node
->prev
);
348 tmp
->next
= node
->next
;
349 cnid
= cpu_to_be32(tmp
->next
);
350 hfs_bnode_write(tmp
, &cnid
,
351 offsetof(struct hfs_bnode_desc
, next
), 4);
353 } else if (node
->type
== HFS_NODE_LEAF
)
354 tree
->leaf_head
= node
->next
;
357 tmp
= hfs_bnode_find(tree
, node
->next
);
360 tmp
->prev
= node
->prev
;
361 cnid
= cpu_to_be32(tmp
->prev
);
362 hfs_bnode_write(tmp
, &cnid
,
363 offsetof(struct hfs_bnode_desc
, prev
), 4);
365 } else if (node
->type
== HFS_NODE_LEAF
)
366 tree
->leaf_tail
= node
->prev
;
369 if (!node
->prev
&& !node
->next
)
370 hfs_dbg(BNODE_MOD
, "hfs_btree_del_level\n");
375 set_bit(HFS_BNODE_DELETED
, &node
->flags
);
378 static inline int hfs_bnode_hash(u32 num
)
380 num
= (num
>> 16) + num
;
382 return num
& (NODE_HASH_SIZE
- 1);
385 struct hfs_bnode
*hfs_bnode_findhash(struct hfs_btree
*tree
, u32 cnid
)
387 struct hfs_bnode
*node
;
389 if (cnid
>= tree
->node_count
) {
390 pr_err("request for non-existent node %d in B*Tree\n",
395 for (node
= tree
->node_hash
[hfs_bnode_hash(cnid
)];
396 node
; node
= node
->next_hash
)
397 if (node
->this == cnid
)
402 static struct hfs_bnode
*__hfs_bnode_create(struct hfs_btree
*tree
, u32 cnid
)
404 struct super_block
*sb
;
405 struct hfs_bnode
*node
, *node2
;
406 struct address_space
*mapping
;
408 int size
, block
, i
, hash
;
411 if (cnid
>= tree
->node_count
) {
412 pr_err("request for non-existent node %d in B*Tree\n",
417 sb
= tree
->inode
->i_sb
;
418 size
= sizeof(struct hfs_bnode
) + tree
->pages_per_bnode
*
419 sizeof(struct page
*);
420 node
= kzalloc(size
, GFP_KERNEL
);
425 set_bit(HFS_BNODE_NEW
, &node
->flags
);
426 atomic_set(&node
->refcnt
, 1);
427 hfs_dbg(BNODE_REFS
, "new_node(%d:%d): 1\n",
428 node
->tree
->cnid
, node
->this);
429 init_waitqueue_head(&node
->lock_wq
);
430 spin_lock(&tree
->hash_lock
);
431 node2
= hfs_bnode_findhash(tree
, cnid
);
433 hash
= hfs_bnode_hash(cnid
);
434 node
->next_hash
= tree
->node_hash
[hash
];
435 tree
->node_hash
[hash
] = node
;
436 tree
->node_hash_cnt
++;
438 spin_unlock(&tree
->hash_lock
);
440 wait_event(node2
->lock_wq
,
441 !test_bit(HFS_BNODE_NEW
, &node2
->flags
));
444 spin_unlock(&tree
->hash_lock
);
446 mapping
= tree
->inode
->i_mapping
;
447 off
= (loff_t
)cnid
<< tree
->node_size_shift
;
448 block
= off
>> PAGE_SHIFT
;
449 node
->page_offset
= off
& ~PAGE_MASK
;
450 for (i
= 0; i
< tree
->pages_per_bnode
; block
++, i
++) {
451 page
= read_mapping_page(mapping
, block
, NULL
);
454 if (PageError(page
)) {
458 node
->page
[i
] = page
;
463 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
467 void hfs_bnode_unhash(struct hfs_bnode
*node
)
469 struct hfs_bnode
**p
;
471 hfs_dbg(BNODE_REFS
, "remove_node(%d:%d): %d\n",
472 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
473 for (p
= &node
->tree
->node_hash
[hfs_bnode_hash(node
->this)];
474 *p
&& *p
!= node
; p
= &(*p
)->next_hash
)
477 *p
= node
->next_hash
;
478 node
->tree
->node_hash_cnt
--;
481 /* Load a particular node out of a tree */
482 struct hfs_bnode
*hfs_bnode_find(struct hfs_btree
*tree
, u32 num
)
484 struct hfs_bnode
*node
;
485 struct hfs_bnode_desc
*desc
;
486 int i
, rec_off
, off
, next_off
;
487 int entry_size
, key_size
;
489 spin_lock(&tree
->hash_lock
);
490 node
= hfs_bnode_findhash(tree
, num
);
493 spin_unlock(&tree
->hash_lock
);
494 wait_event(node
->lock_wq
,
495 !test_bit(HFS_BNODE_NEW
, &node
->flags
));
496 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
500 spin_unlock(&tree
->hash_lock
);
501 node
= __hfs_bnode_create(tree
, num
);
503 return ERR_PTR(-ENOMEM
);
504 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
506 if (!test_bit(HFS_BNODE_NEW
, &node
->flags
))
509 desc
= (struct hfs_bnode_desc
*)(kmap(node
->page
[0]) +
511 node
->prev
= be32_to_cpu(desc
->prev
);
512 node
->next
= be32_to_cpu(desc
->next
);
513 node
->num_recs
= be16_to_cpu(desc
->num_recs
);
514 node
->type
= desc
->type
;
515 node
->height
= desc
->height
;
516 kunmap(node
->page
[0]);
518 switch (node
->type
) {
519 case HFS_NODE_HEADER
:
521 if (node
->height
!= 0)
525 if (node
->height
!= 1)
529 if (node
->height
<= 1 || node
->height
> tree
->depth
)
536 rec_off
= tree
->node_size
- 2;
537 off
= hfs_bnode_read_u16(node
, rec_off
);
538 if (off
!= sizeof(struct hfs_bnode_desc
))
540 for (i
= 1; i
<= node
->num_recs
; off
= next_off
, i
++) {
542 next_off
= hfs_bnode_read_u16(node
, rec_off
);
543 if (next_off
<= off
||
544 next_off
> tree
->node_size
||
547 entry_size
= next_off
- off
;
548 if (node
->type
!= HFS_NODE_INDEX
&&
549 node
->type
!= HFS_NODE_LEAF
)
551 key_size
= hfs_bnode_read_u16(node
, off
) + 2;
552 if (key_size
>= entry_size
|| key_size
& 1)
555 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
556 wake_up(&node
->lock_wq
);
560 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
561 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
562 wake_up(&node
->lock_wq
);
564 return ERR_PTR(-EIO
);
567 void hfs_bnode_free(struct hfs_bnode
*node
)
571 for (i
= 0; i
< node
->tree
->pages_per_bnode
; i
++)
573 put_page(node
->page
[i
]);
577 struct hfs_bnode
*hfs_bnode_create(struct hfs_btree
*tree
, u32 num
)
579 struct hfs_bnode
*node
;
583 spin_lock(&tree
->hash_lock
);
584 node
= hfs_bnode_findhash(tree
, num
);
585 spin_unlock(&tree
->hash_lock
);
587 pr_crit("new node %u already hashed?\n", num
);
591 node
= __hfs_bnode_create(tree
, num
);
593 return ERR_PTR(-ENOMEM
);
594 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
)) {
596 return ERR_PTR(-EIO
);
600 memset(kmap(*pagep
) + node
->page_offset
, 0,
601 min_t(int, PAGE_SIZE
, tree
->node_size
));
602 set_page_dirty(*pagep
);
604 for (i
= 1; i
< tree
->pages_per_bnode
; i
++) {
605 memset(kmap(*++pagep
), 0, PAGE_SIZE
);
606 set_page_dirty(*pagep
);
609 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
610 wake_up(&node
->lock_wq
);
615 void hfs_bnode_get(struct hfs_bnode
*node
)
618 atomic_inc(&node
->refcnt
);
619 hfs_dbg(BNODE_REFS
, "get_node(%d:%d): %d\n",
620 node
->tree
->cnid
, node
->this,
621 atomic_read(&node
->refcnt
));
625 /* Dispose of resources used by a node */
626 void hfs_bnode_put(struct hfs_bnode
*node
)
629 struct hfs_btree
*tree
= node
->tree
;
632 hfs_dbg(BNODE_REFS
, "put_node(%d:%d): %d\n",
633 node
->tree
->cnid
, node
->this,
634 atomic_read(&node
->refcnt
));
635 BUG_ON(!atomic_read(&node
->refcnt
));
636 if (!atomic_dec_and_lock(&node
->refcnt
, &tree
->hash_lock
))
638 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
641 mark_page_accessed(node
->page
[i
]);
644 if (test_bit(HFS_BNODE_DELETED
, &node
->flags
)) {
645 hfs_bnode_unhash(node
);
646 spin_unlock(&tree
->hash_lock
);
647 if (hfs_bnode_need_zeroout(tree
))
648 hfs_bnode_clear(node
, 0, tree
->node_size
);
650 hfs_bnode_free(node
);
653 spin_unlock(&tree
->hash_lock
);
658 * Unused nodes have to be zeroed if this is the catalog tree and
659 * a corresponding flag in the volume header is set.
661 bool hfs_bnode_need_zeroout(struct hfs_btree
*tree
)
663 struct super_block
*sb
= tree
->inode
->i_sb
;
664 struct hfsplus_sb_info
*sbi
= HFSPLUS_SB(sb
);
665 const u32 volume_attr
= be32_to_cpu(sbi
->s_vhdr
->attributes
);
667 return tree
->cnid
== HFSPLUS_CAT_CNID
&&
668 volume_attr
& HFSPLUS_VOL_UNUSED_NODE_FIX
;