]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - fs/hfs/bnode.c
1 // SPDX-License-Identifier: GPL-2.0
6 * Brad Boyer (flar@allandria.com)
7 * (C) 2003 Ardis Technologies <roman@ardistech.com>
9 * Handle basic btree node operations
12 #include <linux/pagemap.h>
13 #include <linux/slab.h>
14 #include <linux/swap.h>
18 void hfs_bnode_read(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
26 off
+= node
->page_offset
;
27 pagenum
= off
>> PAGE_SHIFT
;
28 off
&= ~PAGE_MASK
; /* compute page offset for the first page */
30 for (bytes_read
= 0; bytes_read
< len
; bytes_read
+= bytes_to_read
) {
31 if (pagenum
>= node
->tree
->pages_per_bnode
)
33 page
= node
->page
[pagenum
];
34 bytes_to_read
= min_t(int, len
- bytes_read
, PAGE_SIZE
- off
);
36 vaddr
= kmap_atomic(page
);
37 memcpy(buf
+ bytes_read
, vaddr
+ off
, bytes_to_read
);
41 off
= 0; /* page offset only applies to the first page */
45 u16
hfs_bnode_read_u16(struct hfs_bnode
*node
, int off
)
49 hfs_bnode_read(node
, &data
, off
, 2);
50 return be16_to_cpu(data
);
53 u8
hfs_bnode_read_u8(struct hfs_bnode
*node
, int off
)
57 hfs_bnode_read(node
, &data
, off
, 1);
61 void hfs_bnode_read_key(struct hfs_bnode
*node
, void *key
, int off
)
63 struct hfs_btree
*tree
;
67 if (node
->type
== HFS_NODE_LEAF
||
68 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
69 key_len
= hfs_bnode_read_u8(node
, off
) + 1;
71 key_len
= tree
->max_key_len
+ 1;
73 hfs_bnode_read(node
, key
, off
, key_len
);
76 void hfs_bnode_write(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
80 off
+= node
->page_offset
;
83 memcpy(kmap(page
) + off
, buf
, len
);
88 void hfs_bnode_write_u16(struct hfs_bnode
*node
, int off
, u16 data
)
90 __be16 v
= cpu_to_be16(data
);
92 hfs_bnode_write(node
, &v
, off
, 2);
95 void hfs_bnode_write_u8(struct hfs_bnode
*node
, int off
, u8 data
)
98 hfs_bnode_write(node
, &data
, off
, 1);
101 void hfs_bnode_clear(struct hfs_bnode
*node
, int off
, int len
)
105 off
+= node
->page_offset
;
106 page
= node
->page
[0];
108 memset(kmap(page
) + off
, 0, len
);
110 set_page_dirty(page
);
113 void hfs_bnode_copy(struct hfs_bnode
*dst_node
, int dst
,
114 struct hfs_bnode
*src_node
, int src
, int len
)
116 struct page
*src_page
, *dst_page
;
118 hfs_dbg(BNODE_MOD
, "copybytes: %u,%u,%u\n", dst
, src
, len
);
121 src
+= src_node
->page_offset
;
122 dst
+= dst_node
->page_offset
;
123 src_page
= src_node
->page
[0];
124 dst_page
= dst_node
->page
[0];
126 memcpy(kmap(dst_page
) + dst
, kmap(src_page
) + src
, len
);
129 set_page_dirty(dst_page
);
132 void hfs_bnode_move(struct hfs_bnode
*node
, int dst
, int src
, int len
)
137 hfs_dbg(BNODE_MOD
, "movebytes: %u,%u,%u\n", dst
, src
, len
);
140 src
+= node
->page_offset
;
141 dst
+= node
->page_offset
;
142 page
= node
->page
[0];
144 memmove(ptr
+ dst
, ptr
+ src
, len
);
146 set_page_dirty(page
);
149 void hfs_bnode_dump(struct hfs_bnode
*node
)
151 struct hfs_bnode_desc desc
;
155 hfs_dbg(BNODE_MOD
, "bnode: %d\n", node
->this);
156 hfs_bnode_read(node
, &desc
, 0, sizeof(desc
));
157 hfs_dbg(BNODE_MOD
, "%d, %d, %d, %d, %d\n",
158 be32_to_cpu(desc
.next
), be32_to_cpu(desc
.prev
),
159 desc
.type
, desc
.height
, be16_to_cpu(desc
.num_recs
));
161 off
= node
->tree
->node_size
- 2;
162 for (i
= be16_to_cpu(desc
.num_recs
); i
>= 0; off
-= 2, i
--) {
163 key_off
= hfs_bnode_read_u16(node
, off
);
164 hfs_dbg_cont(BNODE_MOD
, " %d", key_off
);
165 if (i
&& node
->type
== HFS_NODE_INDEX
) {
168 if (node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)
169 tmp
= (hfs_bnode_read_u8(node
, key_off
) | 1) + 1;
171 tmp
= node
->tree
->max_key_len
+ 1;
172 hfs_dbg_cont(BNODE_MOD
, " (%d,%d",
173 tmp
, hfs_bnode_read_u8(node
, key_off
));
174 hfs_bnode_read(node
, &cnid
, key_off
+ tmp
, 4);
175 hfs_dbg_cont(BNODE_MOD
, ",%d)", be32_to_cpu(cnid
));
176 } else if (i
&& node
->type
== HFS_NODE_LEAF
) {
179 tmp
= hfs_bnode_read_u8(node
, key_off
);
180 hfs_dbg_cont(BNODE_MOD
, " (%d)", tmp
);
183 hfs_dbg_cont(BNODE_MOD
, "\n");
186 void hfs_bnode_unlink(struct hfs_bnode
*node
)
188 struct hfs_btree
*tree
;
189 struct hfs_bnode
*tmp
;
194 tmp
= hfs_bnode_find(tree
, node
->prev
);
197 tmp
->next
= node
->next
;
198 cnid
= cpu_to_be32(tmp
->next
);
199 hfs_bnode_write(tmp
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
201 } else if (node
->type
== HFS_NODE_LEAF
)
202 tree
->leaf_head
= node
->next
;
205 tmp
= hfs_bnode_find(tree
, node
->next
);
208 tmp
->prev
= node
->prev
;
209 cnid
= cpu_to_be32(tmp
->prev
);
210 hfs_bnode_write(tmp
, &cnid
, offsetof(struct hfs_bnode_desc
, prev
), 4);
212 } else if (node
->type
== HFS_NODE_LEAF
)
213 tree
->leaf_tail
= node
->prev
;
216 if (!node
->prev
&& !node
->next
) {
217 printk(KERN_DEBUG
"hfs_btree_del_level\n");
223 set_bit(HFS_BNODE_DELETED
, &node
->flags
);
226 static inline int hfs_bnode_hash(u32 num
)
228 num
= (num
>> 16) + num
;
230 return num
& (NODE_HASH_SIZE
- 1);
233 struct hfs_bnode
*hfs_bnode_findhash(struct hfs_btree
*tree
, u32 cnid
)
235 struct hfs_bnode
*node
;
237 if (cnid
>= tree
->node_count
) {
238 pr_err("request for non-existent node %d in B*Tree\n", cnid
);
242 for (node
= tree
->node_hash
[hfs_bnode_hash(cnid
)];
243 node
; node
= node
->next_hash
) {
244 if (node
->this == cnid
) {
251 static struct hfs_bnode
*__hfs_bnode_create(struct hfs_btree
*tree
, u32 cnid
)
253 struct hfs_bnode
*node
, *node2
;
254 struct address_space
*mapping
;
256 int size
, block
, i
, hash
;
259 if (cnid
>= tree
->node_count
) {
260 pr_err("request for non-existent node %d in B*Tree\n", cnid
);
264 size
= sizeof(struct hfs_bnode
) + tree
->pages_per_bnode
*
265 sizeof(struct page
*);
266 node
= kzalloc(size
, GFP_KERNEL
);
271 set_bit(HFS_BNODE_NEW
, &node
->flags
);
272 atomic_set(&node
->refcnt
, 1);
273 hfs_dbg(BNODE_REFS
, "new_node(%d:%d): 1\n",
274 node
->tree
->cnid
, node
->this);
275 init_waitqueue_head(&node
->lock_wq
);
276 spin_lock(&tree
->hash_lock
);
277 node2
= hfs_bnode_findhash(tree
, cnid
);
279 hash
= hfs_bnode_hash(cnid
);
280 node
->next_hash
= tree
->node_hash
[hash
];
281 tree
->node_hash
[hash
] = node
;
282 tree
->node_hash_cnt
++;
284 spin_unlock(&tree
->hash_lock
);
286 wait_event(node2
->lock_wq
, !test_bit(HFS_BNODE_NEW
, &node2
->flags
));
289 spin_unlock(&tree
->hash_lock
);
291 mapping
= tree
->inode
->i_mapping
;
292 off
= (loff_t
)cnid
* tree
->node_size
;
293 block
= off
>> PAGE_SHIFT
;
294 node
->page_offset
= off
& ~PAGE_MASK
;
295 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
296 page
= read_mapping_page(mapping
, block
++, NULL
);
299 if (PageError(page
)) {
303 node
->page
[i
] = page
;
308 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
312 void hfs_bnode_unhash(struct hfs_bnode
*node
)
314 struct hfs_bnode
**p
;
316 hfs_dbg(BNODE_REFS
, "remove_node(%d:%d): %d\n",
317 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
318 for (p
= &node
->tree
->node_hash
[hfs_bnode_hash(node
->this)];
319 *p
&& *p
!= node
; p
= &(*p
)->next_hash
)
322 *p
= node
->next_hash
;
323 node
->tree
->node_hash_cnt
--;
326 /* Load a particular node out of a tree */
327 struct hfs_bnode
*hfs_bnode_find(struct hfs_btree
*tree
, u32 num
)
329 struct hfs_bnode
*node
;
330 struct hfs_bnode_desc
*desc
;
331 int i
, rec_off
, off
, next_off
;
332 int entry_size
, key_size
;
334 spin_lock(&tree
->hash_lock
);
335 node
= hfs_bnode_findhash(tree
, num
);
338 spin_unlock(&tree
->hash_lock
);
339 wait_event(node
->lock_wq
, !test_bit(HFS_BNODE_NEW
, &node
->flags
));
340 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
344 spin_unlock(&tree
->hash_lock
);
345 node
= __hfs_bnode_create(tree
, num
);
347 return ERR_PTR(-ENOMEM
);
348 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
350 if (!test_bit(HFS_BNODE_NEW
, &node
->flags
))
353 desc
= (struct hfs_bnode_desc
*)(kmap(node
->page
[0]) + node
->page_offset
);
354 node
->prev
= be32_to_cpu(desc
->prev
);
355 node
->next
= be32_to_cpu(desc
->next
);
356 node
->num_recs
= be16_to_cpu(desc
->num_recs
);
357 node
->type
= desc
->type
;
358 node
->height
= desc
->height
;
359 kunmap(node
->page
[0]);
361 switch (node
->type
) {
362 case HFS_NODE_HEADER
:
364 if (node
->height
!= 0)
368 if (node
->height
!= 1)
372 if (node
->height
<= 1 || node
->height
> tree
->depth
)
379 rec_off
= tree
->node_size
- 2;
380 off
= hfs_bnode_read_u16(node
, rec_off
);
381 if (off
!= sizeof(struct hfs_bnode_desc
))
383 for (i
= 1; i
<= node
->num_recs
; off
= next_off
, i
++) {
385 next_off
= hfs_bnode_read_u16(node
, rec_off
);
386 if (next_off
<= off
||
387 next_off
> tree
->node_size
||
390 entry_size
= next_off
- off
;
391 if (node
->type
!= HFS_NODE_INDEX
&&
392 node
->type
!= HFS_NODE_LEAF
)
394 key_size
= hfs_bnode_read_u8(node
, off
) + 1;
395 if (key_size
>= entry_size
/*|| key_size & 1*/)
398 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
399 wake_up(&node
->lock_wq
);
403 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
404 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
405 wake_up(&node
->lock_wq
);
407 return ERR_PTR(-EIO
);
410 void hfs_bnode_free(struct hfs_bnode
*node
)
414 for (i
= 0; i
< node
->tree
->pages_per_bnode
; i
++)
416 put_page(node
->page
[i
]);
420 struct hfs_bnode
*hfs_bnode_create(struct hfs_btree
*tree
, u32 num
)
422 struct hfs_bnode
*node
;
426 spin_lock(&tree
->hash_lock
);
427 node
= hfs_bnode_findhash(tree
, num
);
428 spin_unlock(&tree
->hash_lock
);
430 pr_crit("new node %u already hashed?\n", num
);
434 node
= __hfs_bnode_create(tree
, num
);
436 return ERR_PTR(-ENOMEM
);
437 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
)) {
439 return ERR_PTR(-EIO
);
443 memset(kmap(*pagep
) + node
->page_offset
, 0,
444 min((int)PAGE_SIZE
, (int)tree
->node_size
));
445 set_page_dirty(*pagep
);
447 for (i
= 1; i
< tree
->pages_per_bnode
; i
++) {
448 memset(kmap(*++pagep
), 0, PAGE_SIZE
);
449 set_page_dirty(*pagep
);
452 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
453 wake_up(&node
->lock_wq
);
458 void hfs_bnode_get(struct hfs_bnode
*node
)
461 atomic_inc(&node
->refcnt
);
462 hfs_dbg(BNODE_REFS
, "get_node(%d:%d): %d\n",
463 node
->tree
->cnid
, node
->this,
464 atomic_read(&node
->refcnt
));
468 /* Dispose of resources used by a node */
469 void hfs_bnode_put(struct hfs_bnode
*node
)
472 struct hfs_btree
*tree
= node
->tree
;
475 hfs_dbg(BNODE_REFS
, "put_node(%d:%d): %d\n",
476 node
->tree
->cnid
, node
->this,
477 atomic_read(&node
->refcnt
));
478 BUG_ON(!atomic_read(&node
->refcnt
));
479 if (!atomic_dec_and_lock(&node
->refcnt
, &tree
->hash_lock
))
481 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
484 mark_page_accessed(node
->page
[i
]);
487 if (test_bit(HFS_BNODE_DELETED
, &node
->flags
)) {
488 hfs_bnode_unhash(node
);
489 spin_unlock(&tree
->hash_lock
);
491 hfs_bnode_free(node
);
494 spin_unlock(&tree
->hash_lock
);