]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - fs/hfsplus/bnode.c
2 * linux/fs/hfsplus/bnode.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle basic btree node operations
11 #include <linux/string.h>
12 #include <linux/slab.h>
13 #include <linux/pagemap.h>
15 #include <linux/swap.h>
17 #include "hfsplus_fs.h"
18 #include "hfsplus_raw.h"
20 /* Copy a specified range of bytes from the raw data of a node */
21 void hfs_bnode_read(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
26 off
+= node
->page_offset
;
27 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
28 off
&= ~PAGE_CACHE_MASK
;
30 l
= min(len
, (int)PAGE_CACHE_SIZE
- off
);
31 memcpy(buf
, kmap(*pagep
) + off
, l
);
34 while ((len
-= l
) != 0) {
36 l
= min(len
, (int)PAGE_CACHE_SIZE
);
37 memcpy(buf
, kmap(*++pagep
), l
);
42 u16
hfs_bnode_read_u16(struct hfs_bnode
*node
, int off
)
46 hfs_bnode_read(node
, &data
, off
, 2);
47 return be16_to_cpu(data
);
50 u8
hfs_bnode_read_u8(struct hfs_bnode
*node
, int off
)
54 hfs_bnode_read(node
, &data
, off
, 1);
58 void hfs_bnode_read_key(struct hfs_bnode
*node
, void *key
, int off
)
60 struct hfs_btree
*tree
;
64 if (node
->type
== HFS_NODE_LEAF
||
65 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
66 key_len
= hfs_bnode_read_u16(node
, off
) + 2;
68 key_len
= tree
->max_key_len
+ 2;
70 hfs_bnode_read(node
, key
, off
, key_len
);
73 void hfs_bnode_write(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
78 off
+= node
->page_offset
;
79 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
80 off
&= ~PAGE_CACHE_MASK
;
82 l
= min(len
, (int)PAGE_CACHE_SIZE
- off
);
83 memcpy(kmap(*pagep
) + off
, buf
, l
);
84 set_page_dirty(*pagep
);
87 while ((len
-= l
) != 0) {
89 l
= min(len
, (int)PAGE_CACHE_SIZE
);
90 memcpy(kmap(*++pagep
), buf
, l
);
91 set_page_dirty(*pagep
);
96 void hfs_bnode_write_u16(struct hfs_bnode
*node
, int off
, u16 data
)
98 __be16 v
= cpu_to_be16(data
);
100 hfs_bnode_write(node
, &v
, off
, 2);
103 void hfs_bnode_clear(struct hfs_bnode
*node
, int off
, int len
)
108 off
+= node
->page_offset
;
109 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
110 off
&= ~PAGE_CACHE_MASK
;
112 l
= min(len
, (int)PAGE_CACHE_SIZE
- off
);
113 memset(kmap(*pagep
) + off
, 0, l
);
114 set_page_dirty(*pagep
);
117 while ((len
-= l
) != 0) {
118 l
= min(len
, (int)PAGE_CACHE_SIZE
);
119 memset(kmap(*++pagep
), 0, l
);
120 set_page_dirty(*pagep
);
125 void hfs_bnode_copy(struct hfs_bnode
*dst_node
, int dst
,
126 struct hfs_bnode
*src_node
, int src
, int len
)
128 struct hfs_btree
*tree
;
129 struct page
**src_page
, **dst_page
;
132 dprint(DBG_BNODE_MOD
, "copybytes: %u,%u,%u\n", dst
, src
, len
);
135 tree
= src_node
->tree
;
136 src
+= src_node
->page_offset
;
137 dst
+= dst_node
->page_offset
;
138 src_page
= src_node
->page
+ (src
>> PAGE_CACHE_SHIFT
);
139 src
&= ~PAGE_CACHE_MASK
;
140 dst_page
= dst_node
->page
+ (dst
>> PAGE_CACHE_SHIFT
);
141 dst
&= ~PAGE_CACHE_MASK
;
144 l
= min(len
, (int)PAGE_CACHE_SIZE
- src
);
145 memcpy(kmap(*dst_page
) + src
, kmap(*src_page
) + src
, l
);
147 set_page_dirty(*dst_page
);
150 while ((len
-= l
) != 0) {
151 l
= min(len
, (int)PAGE_CACHE_SIZE
);
152 memcpy(kmap(*++dst_page
), kmap(*++src_page
), l
);
154 set_page_dirty(*dst_page
);
158 void *src_ptr
, *dst_ptr
;
161 src_ptr
= kmap(*src_page
) + src
;
162 dst_ptr
= kmap(*dst_page
) + dst
;
163 if (PAGE_CACHE_SIZE
- src
< PAGE_CACHE_SIZE
- dst
) {
164 l
= PAGE_CACHE_SIZE
- src
;
168 l
= PAGE_CACHE_SIZE
- dst
;
173 memcpy(dst_ptr
, src_ptr
, l
);
175 set_page_dirty(*dst_page
);
181 } while ((len
-= l
));
185 void hfs_bnode_move(struct hfs_bnode
*node
, int dst
, int src
, int len
)
187 struct page
**src_page
, **dst_page
;
190 dprint(DBG_BNODE_MOD
, "movebytes: %u,%u,%u\n", dst
, src
, len
);
193 src
+= node
->page_offset
;
194 dst
+= node
->page_offset
;
197 src_page
= node
->page
+ (src
>> PAGE_CACHE_SHIFT
);
198 src
= (src
& ~PAGE_CACHE_MASK
) + 1;
200 dst_page
= node
->page
+ (dst
>> PAGE_CACHE_SHIFT
);
201 dst
= (dst
& ~PAGE_CACHE_MASK
) + 1;
205 memmove(kmap(*dst_page
), kmap(*src_page
), src
);
207 set_page_dirty(*dst_page
);
210 src
= PAGE_CACHE_SIZE
;
215 memmove(kmap(*dst_page
) + src
,
216 kmap(*src_page
) + src
, len
);
218 set_page_dirty(*dst_page
);
221 void *src_ptr
, *dst_ptr
;
224 src_ptr
= kmap(*src_page
) + src
;
225 dst_ptr
= kmap(*dst_page
) + dst
;
228 src
= PAGE_CACHE_SIZE
;
233 dst
= PAGE_CACHE_SIZE
;
236 memmove(dst_ptr
- l
, src_ptr
- l
, l
);
238 set_page_dirty(*dst_page
);
240 if (dst
== PAGE_CACHE_SIZE
)
244 } while ((len
-= l
));
247 src_page
= node
->page
+ (src
>> PAGE_CACHE_SHIFT
);
248 src
&= ~PAGE_CACHE_MASK
;
249 dst_page
= node
->page
+ (dst
>> PAGE_CACHE_SHIFT
);
250 dst
&= ~PAGE_CACHE_MASK
;
253 l
= min(len
, (int)PAGE_CACHE_SIZE
- src
);
254 memmove(kmap(*dst_page
) + src
,
255 kmap(*src_page
) + src
, l
);
257 set_page_dirty(*dst_page
);
260 while ((len
-= l
) != 0) {
261 l
= min(len
, (int)PAGE_CACHE_SIZE
);
262 memmove(kmap(*++dst_page
),
263 kmap(*++src_page
), l
);
265 set_page_dirty(*dst_page
);
269 void *src_ptr
, *dst_ptr
;
272 src_ptr
= kmap(*src_page
) + src
;
273 dst_ptr
= kmap(*dst_page
) + dst
;
274 if (PAGE_CACHE_SIZE
- src
<
275 PAGE_CACHE_SIZE
- dst
) {
276 l
= PAGE_CACHE_SIZE
- src
;
280 l
= PAGE_CACHE_SIZE
- dst
;
285 memmove(dst_ptr
, src_ptr
, l
);
287 set_page_dirty(*dst_page
);
293 } while ((len
-= l
));
298 void hfs_bnode_dump(struct hfs_bnode
*node
)
300 struct hfs_bnode_desc desc
;
304 dprint(DBG_BNODE_MOD
, "bnode: %d\n", node
->this);
305 hfs_bnode_read(node
, &desc
, 0, sizeof(desc
));
306 dprint(DBG_BNODE_MOD
, "%d, %d, %d, %d, %d\n",
307 be32_to_cpu(desc
.next
), be32_to_cpu(desc
.prev
),
308 desc
.type
, desc
.height
, be16_to_cpu(desc
.num_recs
));
310 off
= node
->tree
->node_size
- 2;
311 for (i
= be16_to_cpu(desc
.num_recs
); i
>= 0; off
-= 2, i
--) {
312 key_off
= hfs_bnode_read_u16(node
, off
);
313 dprint(DBG_BNODE_MOD
, " %d", key_off
);
314 if (i
&& node
->type
== HFS_NODE_INDEX
) {
317 if (node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)
318 tmp
= hfs_bnode_read_u16(node
, key_off
) + 2;
320 tmp
= node
->tree
->max_key_len
+ 2;
321 dprint(DBG_BNODE_MOD
, " (%d", tmp
);
322 hfs_bnode_read(node
, &cnid
, key_off
+ tmp
, 4);
323 dprint(DBG_BNODE_MOD
, ",%d)", be32_to_cpu(cnid
));
324 } else if (i
&& node
->type
== HFS_NODE_LEAF
) {
327 tmp
= hfs_bnode_read_u16(node
, key_off
);
328 dprint(DBG_BNODE_MOD
, " (%d)", tmp
);
331 dprint(DBG_BNODE_MOD
, "\n");
334 void hfs_bnode_unlink(struct hfs_bnode
*node
)
336 struct hfs_btree
*tree
;
337 struct hfs_bnode
*tmp
;
342 tmp
= hfs_bnode_find(tree
, node
->prev
);
345 tmp
->next
= node
->next
;
346 cnid
= cpu_to_be32(tmp
->next
);
347 hfs_bnode_write(tmp
, &cnid
,
348 offsetof(struct hfs_bnode_desc
, next
), 4);
350 } else if (node
->type
== HFS_NODE_LEAF
)
351 tree
->leaf_head
= node
->next
;
354 tmp
= hfs_bnode_find(tree
, node
->next
);
357 tmp
->prev
= node
->prev
;
358 cnid
= cpu_to_be32(tmp
->prev
);
359 hfs_bnode_write(tmp
, &cnid
,
360 offsetof(struct hfs_bnode_desc
, prev
), 4);
362 } else if (node
->type
== HFS_NODE_LEAF
)
363 tree
->leaf_tail
= node
->prev
;
366 if (!node
->prev
&& !node
->next
) {
367 dprint(DBG_BNODE_MOD
, "hfs_btree_del_level\n");
373 set_bit(HFS_BNODE_DELETED
, &node
->flags
);
376 static inline int hfs_bnode_hash(u32 num
)
378 num
= (num
>> 16) + num
;
380 return num
& (NODE_HASH_SIZE
- 1);
383 struct hfs_bnode
*hfs_bnode_findhash(struct hfs_btree
*tree
, u32 cnid
)
385 struct hfs_bnode
*node
;
387 if (cnid
>= tree
->node_count
) {
388 printk(KERN_ERR
"hfs: request for non-existent node "
394 for (node
= tree
->node_hash
[hfs_bnode_hash(cnid
)];
395 node
; node
= node
->next_hash
) {
396 if (node
->this == cnid
) {
403 static struct hfs_bnode
*__hfs_bnode_create(struct hfs_btree
*tree
, u32 cnid
)
405 struct super_block
*sb
;
406 struct hfs_bnode
*node
, *node2
;
407 struct address_space
*mapping
;
409 int size
, block
, i
, hash
;
412 if (cnid
>= tree
->node_count
) {
413 printk(KERN_ERR
"hfs: request for non-existent node "
419 sb
= tree
->inode
->i_sb
;
420 size
= sizeof(struct hfs_bnode
) + tree
->pages_per_bnode
*
421 sizeof(struct page
*);
422 node
= kzalloc(size
, GFP_KERNEL
);
427 set_bit(HFS_BNODE_NEW
, &node
->flags
);
428 atomic_set(&node
->refcnt
, 1);
429 dprint(DBG_BNODE_REFS
, "new_node(%d:%d): 1\n",
430 node
->tree
->cnid
, node
->this);
431 init_waitqueue_head(&node
->lock_wq
);
432 spin_lock(&tree
->hash_lock
);
433 node2
= hfs_bnode_findhash(tree
, cnid
);
435 hash
= hfs_bnode_hash(cnid
);
436 node
->next_hash
= tree
->node_hash
[hash
];
437 tree
->node_hash
[hash
] = node
;
438 tree
->node_hash_cnt
++;
440 spin_unlock(&tree
->hash_lock
);
442 wait_event(node2
->lock_wq
,
443 !test_bit(HFS_BNODE_NEW
, &node2
->flags
));
446 spin_unlock(&tree
->hash_lock
);
448 mapping
= tree
->inode
->i_mapping
;
449 off
= (loff_t
)cnid
<< tree
->node_size_shift
;
450 block
= off
>> PAGE_CACHE_SHIFT
;
451 node
->page_offset
= off
& ~PAGE_CACHE_MASK
;
452 for (i
= 0; i
< tree
->pages_per_bnode
; block
++, i
++) {
453 page
= read_mapping_page(mapping
, block
, NULL
);
456 if (PageError(page
)) {
457 page_cache_release(page
);
460 page_cache_release(page
);
461 node
->page
[i
] = page
;
466 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
470 void hfs_bnode_unhash(struct hfs_bnode
*node
)
472 struct hfs_bnode
**p
;
474 dprint(DBG_BNODE_REFS
, "remove_node(%d:%d): %d\n",
475 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
476 for (p
= &node
->tree
->node_hash
[hfs_bnode_hash(node
->this)];
477 *p
&& *p
!= node
; p
= &(*p
)->next_hash
)
480 *p
= node
->next_hash
;
481 node
->tree
->node_hash_cnt
--;
484 /* Load a particular node out of a tree */
485 struct hfs_bnode
*hfs_bnode_find(struct hfs_btree
*tree
, u32 num
)
487 struct hfs_bnode
*node
;
488 struct hfs_bnode_desc
*desc
;
489 int i
, rec_off
, off
, next_off
;
490 int entry_size
, key_size
;
492 spin_lock(&tree
->hash_lock
);
493 node
= hfs_bnode_findhash(tree
, num
);
496 spin_unlock(&tree
->hash_lock
);
497 wait_event(node
->lock_wq
,
498 !test_bit(HFS_BNODE_NEW
, &node
->flags
));
499 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
503 spin_unlock(&tree
->hash_lock
);
504 node
= __hfs_bnode_create(tree
, num
);
506 return ERR_PTR(-ENOMEM
);
507 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
509 if (!test_bit(HFS_BNODE_NEW
, &node
->flags
))
512 desc
= (struct hfs_bnode_desc
*)(kmap(node
->page
[0]) +
514 node
->prev
= be32_to_cpu(desc
->prev
);
515 node
->next
= be32_to_cpu(desc
->next
);
516 node
->num_recs
= be16_to_cpu(desc
->num_recs
);
517 node
->type
= desc
->type
;
518 node
->height
= desc
->height
;
519 kunmap(node
->page
[0]);
521 switch (node
->type
) {
522 case HFS_NODE_HEADER
:
524 if (node
->height
!= 0)
528 if (node
->height
!= 1)
532 if (node
->height
<= 1 || node
->height
> tree
->depth
)
539 rec_off
= tree
->node_size
- 2;
540 off
= hfs_bnode_read_u16(node
, rec_off
);
541 if (off
!= sizeof(struct hfs_bnode_desc
))
543 for (i
= 1; i
<= node
->num_recs
; off
= next_off
, i
++) {
545 next_off
= hfs_bnode_read_u16(node
, rec_off
);
546 if (next_off
<= off
||
547 next_off
> tree
->node_size
||
550 entry_size
= next_off
- off
;
551 if (node
->type
!= HFS_NODE_INDEX
&&
552 node
->type
!= HFS_NODE_LEAF
)
554 key_size
= hfs_bnode_read_u16(node
, off
) + 2;
555 if (key_size
>= entry_size
|| key_size
& 1)
558 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
559 wake_up(&node
->lock_wq
);
563 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
564 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
565 wake_up(&node
->lock_wq
);
567 return ERR_PTR(-EIO
);
570 void hfs_bnode_free(struct hfs_bnode
*node
)
574 //for (i = 0; i < node->tree->pages_per_bnode; i++)
575 // if (node->page[i])
576 // page_cache_release(node->page[i]);
580 struct hfs_bnode
*hfs_bnode_create(struct hfs_btree
*tree
, u32 num
)
582 struct hfs_bnode
*node
;
586 spin_lock(&tree
->hash_lock
);
587 node
= hfs_bnode_findhash(tree
, num
);
588 spin_unlock(&tree
->hash_lock
);
590 printk(KERN_CRIT
"new node %u already hashed?\n", num
);
594 node
= __hfs_bnode_create(tree
, num
);
596 return ERR_PTR(-ENOMEM
);
597 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
)) {
599 return ERR_PTR(-EIO
);
603 memset(kmap(*pagep
) + node
->page_offset
, 0,
604 min((int)PAGE_CACHE_SIZE
, (int)tree
->node_size
));
605 set_page_dirty(*pagep
);
607 for (i
= 1; i
< tree
->pages_per_bnode
; i
++) {
608 memset(kmap(*++pagep
), 0, PAGE_CACHE_SIZE
);
609 set_page_dirty(*pagep
);
612 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
613 wake_up(&node
->lock_wq
);
618 void hfs_bnode_get(struct hfs_bnode
*node
)
621 atomic_inc(&node
->refcnt
);
622 dprint(DBG_BNODE_REFS
, "get_node(%d:%d): %d\n",
623 node
->tree
->cnid
, node
->this,
624 atomic_read(&node
->refcnt
));
628 /* Dispose of resources used by a node */
629 void hfs_bnode_put(struct hfs_bnode
*node
)
632 struct hfs_btree
*tree
= node
->tree
;
635 dprint(DBG_BNODE_REFS
, "put_node(%d:%d): %d\n",
636 node
->tree
->cnid
, node
->this,
637 atomic_read(&node
->refcnt
));
638 BUG_ON(!atomic_read(&node
->refcnt
));
639 if (!atomic_dec_and_lock(&node
->refcnt
, &tree
->hash_lock
))
641 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
644 mark_page_accessed(node
->page
[i
]);
647 if (test_bit(HFS_BNODE_DELETED
, &node
->flags
)) {
648 hfs_bnode_unhash(node
);
649 spin_unlock(&tree
->hash_lock
);
651 hfs_bnode_free(node
);
654 spin_unlock(&tree
->hash_lock
);