5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle basic btree node operations
11 #include <linux/pagemap.h>
12 #include <linux/swap.h>
18 void hfs_bnode_read(struct hfs_bnode
*node
, void *buf
,
23 off
+= node
->page_offset
;
26 memcpy(buf
, kmap(page
) + off
, len
);
30 u16
hfs_bnode_read_u16(struct hfs_bnode
*node
, int off
)
34 hfs_bnode_read(node
, &data
, off
, 2);
35 return be16_to_cpu(data
);
38 u8
hfs_bnode_read_u8(struct hfs_bnode
*node
, int off
)
42 hfs_bnode_read(node
, &data
, off
, 1);
46 void hfs_bnode_read_key(struct hfs_bnode
*node
, void *key
, int off
)
48 struct hfs_btree
*tree
;
52 if (node
->type
== HFS_NODE_LEAF
||
53 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
54 key_len
= hfs_bnode_read_u8(node
, off
) + 1;
56 key_len
= tree
->max_key_len
+ 1;
58 hfs_bnode_read(node
, key
, off
, key_len
);
61 void hfs_bnode_write(struct hfs_bnode
*node
, void *buf
, int off
, int len
)
65 off
+= node
->page_offset
;
68 memcpy(kmap(page
) + off
, buf
, len
);
73 void hfs_bnode_write_u16(struct hfs_bnode
*node
, int off
, u16 data
)
75 __be16 v
= cpu_to_be16(data
);
77 hfs_bnode_write(node
, &v
, off
, 2);
80 void hfs_bnode_write_u8(struct hfs_bnode
*node
, int off
, u8 data
)
83 hfs_bnode_write(node
, &data
, off
, 1);
86 void hfs_bnode_clear(struct hfs_bnode
*node
, int off
, int len
)
90 off
+= node
->page_offset
;
93 memset(kmap(page
) + off
, 0, len
);
98 void hfs_bnode_copy(struct hfs_bnode
*dst_node
, int dst
,
99 struct hfs_bnode
*src_node
, int src
, int len
)
101 struct hfs_btree
*tree
;
102 struct page
*src_page
, *dst_page
;
104 dprint(DBG_BNODE_MOD
, "copybytes: %u,%u,%u\n", dst
, src
, len
);
107 tree
= src_node
->tree
;
108 src
+= src_node
->page_offset
;
109 dst
+= dst_node
->page_offset
;
110 src_page
= src_node
->page
[0];
111 dst_page
= dst_node
->page
[0];
113 memcpy(kmap(dst_page
) + dst
, kmap(src_page
) + src
, len
);
116 set_page_dirty(dst_page
);
119 void hfs_bnode_move(struct hfs_bnode
*node
, int dst
, int src
, int len
)
124 dprint(DBG_BNODE_MOD
, "movebytes: %u,%u,%u\n", dst
, src
, len
);
127 src
+= node
->page_offset
;
128 dst
+= node
->page_offset
;
129 page
= node
->page
[0];
131 memmove(ptr
+ dst
, ptr
+ src
, len
);
133 set_page_dirty(page
);
136 void hfs_bnode_dump(struct hfs_bnode
*node
)
138 struct hfs_bnode_desc desc
;
142 dprint(DBG_BNODE_MOD
, "bnode: %d\n", node
->this);
143 hfs_bnode_read(node
, &desc
, 0, sizeof(desc
));
144 dprint(DBG_BNODE_MOD
, "%d, %d, %d, %d, %d\n",
145 be32_to_cpu(desc
.next
), be32_to_cpu(desc
.prev
),
146 desc
.type
, desc
.height
, be16_to_cpu(desc
.num_recs
));
148 off
= node
->tree
->node_size
- 2;
149 for (i
= be16_to_cpu(desc
.num_recs
); i
>= 0; off
-= 2, i
--) {
150 key_off
= hfs_bnode_read_u16(node
, off
);
151 dprint(DBG_BNODE_MOD
, " %d", key_off
);
152 if (i
&& node
->type
== HFS_NODE_INDEX
) {
155 if (node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)
156 tmp
= (hfs_bnode_read_u8(node
, key_off
) | 1) + 1;
158 tmp
= node
->tree
->max_key_len
+ 1;
159 dprint(DBG_BNODE_MOD
, " (%d,%d", tmp
, hfs_bnode_read_u8(node
, key_off
));
160 hfs_bnode_read(node
, &cnid
, key_off
+ tmp
, 4);
161 dprint(DBG_BNODE_MOD
, ",%d)", be32_to_cpu(cnid
));
162 } else if (i
&& node
->type
== HFS_NODE_LEAF
) {
165 tmp
= hfs_bnode_read_u8(node
, key_off
);
166 dprint(DBG_BNODE_MOD
, " (%d)", tmp
);
169 dprint(DBG_BNODE_MOD
, "\n");
172 void hfs_bnode_unlink(struct hfs_bnode
*node
)
174 struct hfs_btree
*tree
;
175 struct hfs_bnode
*tmp
;
180 tmp
= hfs_bnode_find(tree
, node
->prev
);
183 tmp
->next
= node
->next
;
184 cnid
= cpu_to_be32(tmp
->next
);
185 hfs_bnode_write(tmp
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
187 } else if (node
->type
== HFS_NODE_LEAF
)
188 tree
->leaf_head
= node
->next
;
191 tmp
= hfs_bnode_find(tree
, node
->next
);
194 tmp
->prev
= node
->prev
;
195 cnid
= cpu_to_be32(tmp
->prev
);
196 hfs_bnode_write(tmp
, &cnid
, offsetof(struct hfs_bnode_desc
, prev
), 4);
198 } else if (node
->type
== HFS_NODE_LEAF
)
199 tree
->leaf_tail
= node
->prev
;
202 if (!node
->prev
&& !node
->next
) {
203 printk("hfs_btree_del_level\n");
209 set_bit(HFS_BNODE_DELETED
, &node
->flags
);
212 static inline int hfs_bnode_hash(u32 num
)
214 num
= (num
>> 16) + num
;
216 return num
& (NODE_HASH_SIZE
- 1);
219 struct hfs_bnode
*hfs_bnode_findhash(struct hfs_btree
*tree
, u32 cnid
)
221 struct hfs_bnode
*node
;
223 if (cnid
>= tree
->node_count
) {
224 printk("HFS: request for non-existent node %d in B*Tree\n", cnid
);
228 for (node
= tree
->node_hash
[hfs_bnode_hash(cnid
)];
229 node
; node
= node
->next_hash
) {
230 if (node
->this == cnid
) {
237 static struct hfs_bnode
*__hfs_bnode_create(struct hfs_btree
*tree
, u32 cnid
)
239 struct super_block
*sb
;
240 struct hfs_bnode
*node
, *node2
;
241 struct address_space
*mapping
;
243 int size
, block
, i
, hash
;
246 if (cnid
>= tree
->node_count
) {
247 printk("HFS: request for non-existent node %d in B*Tree\n", cnid
);
251 sb
= tree
->inode
->i_sb
;
252 size
= sizeof(struct hfs_bnode
) + tree
->pages_per_bnode
*
253 sizeof(struct page
*);
254 node
= kmalloc(size
, GFP_KERNEL
);
257 memset(node
, 0, size
);
260 set_bit(HFS_BNODE_NEW
, &node
->flags
);
261 atomic_set(&node
->refcnt
, 1);
262 dprint(DBG_BNODE_REFS
, "new_node(%d:%d): 1\n",
263 node
->tree
->cnid
, node
->this);
264 init_waitqueue_head(&node
->lock_wq
);
265 spin_lock(&tree
->hash_lock
);
266 node2
= hfs_bnode_findhash(tree
, cnid
);
268 hash
= hfs_bnode_hash(cnid
);
269 node
->next_hash
= tree
->node_hash
[hash
];
270 tree
->node_hash
[hash
] = node
;
271 tree
->node_hash_cnt
++;
273 spin_unlock(&tree
->hash_lock
);
275 wait_event(node2
->lock_wq
, !test_bit(HFS_BNODE_NEW
, &node2
->flags
));
278 spin_unlock(&tree
->hash_lock
);
280 mapping
= tree
->inode
->i_mapping
;
281 off
= (loff_t
)cnid
* tree
->node_size
;
282 block
= off
>> PAGE_CACHE_SHIFT
;
283 node
->page_offset
= off
& ~PAGE_CACHE_MASK
;
284 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
285 page
= read_cache_page(mapping
, block
++, (filler_t
*)mapping
->a_ops
->readpage
, NULL
);
288 if (PageError(page
)) {
289 page_cache_release(page
);
293 page_cache_release(page
);
295 node
->page
[i
] = page
;
300 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
304 void hfs_bnode_unhash(struct hfs_bnode
*node
)
306 struct hfs_bnode
**p
;
308 dprint(DBG_BNODE_REFS
, "remove_node(%d:%d): %d\n",
309 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
310 for (p
= &node
->tree
->node_hash
[hfs_bnode_hash(node
->this)];
311 *p
&& *p
!= node
; p
= &(*p
)->next_hash
)
315 *p
= node
->next_hash
;
316 node
->tree
->node_hash_cnt
--;
319 /* Load a particular node out of a tree */
320 struct hfs_bnode
*hfs_bnode_find(struct hfs_btree
*tree
, u32 num
)
322 struct hfs_bnode
*node
;
323 struct hfs_bnode_desc
*desc
;
324 int i
, rec_off
, off
, next_off
;
325 int entry_size
, key_size
;
327 spin_lock(&tree
->hash_lock
);
328 node
= hfs_bnode_findhash(tree
, num
);
331 spin_unlock(&tree
->hash_lock
);
332 wait_event(node
->lock_wq
, !test_bit(HFS_BNODE_NEW
, &node
->flags
));
333 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
337 spin_unlock(&tree
->hash_lock
);
338 node
= __hfs_bnode_create(tree
, num
);
340 return ERR_PTR(-ENOMEM
);
341 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
))
343 if (!test_bit(HFS_BNODE_NEW
, &node
->flags
))
346 desc
= (struct hfs_bnode_desc
*)(kmap(node
->page
[0]) + node
->page_offset
);
347 node
->prev
= be32_to_cpu(desc
->prev
);
348 node
->next
= be32_to_cpu(desc
->next
);
349 node
->num_recs
= be16_to_cpu(desc
->num_recs
);
350 node
->type
= desc
->type
;
351 node
->height
= desc
->height
;
352 kunmap(node
->page
[0]);
354 switch (node
->type
) {
355 case HFS_NODE_HEADER
:
357 if (node
->height
!= 0)
361 if (node
->height
!= 1)
365 if (node
->height
<= 1 || node
->height
> tree
->depth
)
372 rec_off
= tree
->node_size
- 2;
373 off
= hfs_bnode_read_u16(node
, rec_off
);
374 if (off
!= sizeof(struct hfs_bnode_desc
))
376 for (i
= 1; i
<= node
->num_recs
; off
= next_off
, i
++) {
378 next_off
= hfs_bnode_read_u16(node
, rec_off
);
379 if (next_off
<= off
||
380 next_off
> tree
->node_size
||
383 entry_size
= next_off
- off
;
384 if (node
->type
!= HFS_NODE_INDEX
&&
385 node
->type
!= HFS_NODE_LEAF
)
387 key_size
= hfs_bnode_read_u8(node
, off
) + 1;
388 if (key_size
>= entry_size
/*|| key_size & 1*/)
391 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
392 wake_up(&node
->lock_wq
);
396 set_bit(HFS_BNODE_ERROR
, &node
->flags
);
397 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
398 wake_up(&node
->lock_wq
);
400 return ERR_PTR(-EIO
);
403 void hfs_bnode_free(struct hfs_bnode
*node
)
407 //for (i = 0; i < node->tree->pages_per_bnode; i++)
408 // if (node->page[i])
409 // page_cache_release(node->page[i]);
413 struct hfs_bnode
*hfs_bnode_create(struct hfs_btree
*tree
, u32 num
)
415 struct hfs_bnode
*node
;
419 spin_lock(&tree
->hash_lock
);
420 node
= hfs_bnode_findhash(tree
, num
);
421 spin_unlock(&tree
->hash_lock
);
424 node
= __hfs_bnode_create(tree
, num
);
426 return ERR_PTR(-ENOMEM
);
427 if (test_bit(HFS_BNODE_ERROR
, &node
->flags
)) {
429 return ERR_PTR(-EIO
);
433 memset(kmap(*pagep
) + node
->page_offset
, 0,
434 min((int)PAGE_CACHE_SIZE
, (int)tree
->node_size
));
435 set_page_dirty(*pagep
);
437 for (i
= 1; i
< tree
->pages_per_bnode
; i
++) {
438 memset(kmap(*++pagep
), 0, PAGE_CACHE_SIZE
);
439 set_page_dirty(*pagep
);
442 clear_bit(HFS_BNODE_NEW
, &node
->flags
);
443 wake_up(&node
->lock_wq
);
448 void hfs_bnode_get(struct hfs_bnode
*node
)
451 atomic_inc(&node
->refcnt
);
455 for (i
= 0; i
< node
->tree
->pages_per_bnode
; i
++)
456 get_page(node
->page
[i
]);
459 dprint(DBG_BNODE_REFS
, "get_node(%d:%d): %d\n",
460 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
464 /* Dispose of resources used by a node */
465 void hfs_bnode_put(struct hfs_bnode
*node
)
468 struct hfs_btree
*tree
= node
->tree
;
471 dprint(DBG_BNODE_REFS
, "put_node(%d:%d): %d\n",
472 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
473 if (!atomic_read(&node
->refcnt
))
475 if (!atomic_dec_and_lock(&node
->refcnt
, &tree
->hash_lock
)) {
477 for (i
= 0; i
< tree
->pages_per_bnode
; i
++)
478 put_page(node
->page
[i
]);
482 for (i
= 0; i
< tree
->pages_per_bnode
; i
++) {
483 mark_page_accessed(node
->page
[i
]);
485 put_page(node
->page
[i
]);
489 if (test_bit(HFS_BNODE_DELETED
, &node
->flags
)) {
490 hfs_bnode_unhash(node
);
491 spin_unlock(&tree
->hash_lock
);
493 hfs_bnode_free(node
);
496 spin_unlock(&tree
->hash_lock
);