Lines Matching full:node
9 * Handle basic btree node operations
22 /* Copy a specified range of bytes from the raw data of a node */
23 void hfs_bnode_read(struct hfs_bnode *node, void *buf, u32 off, u32 len) in hfs_bnode_read() argument
28 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_read()
33 "NODE: id %u, type %#x, height %u, " in hfs_bnode_read()
35 node->this, node->type, node->height, in hfs_bnode_read()
36 node->tree->node_size, off, len); in hfs_bnode_read()
40 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_read()
42 off += node->page_offset; in hfs_bnode_read()
43 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_read()
56 u16 hfs_bnode_read_u16(struct hfs_bnode *node, u32 off) in hfs_bnode_read_u16() argument
60 hfs_bnode_read(node, &data, off, 2); in hfs_bnode_read_u16()
64 u8 hfs_bnode_read_u8(struct hfs_bnode *node, u32 off) in hfs_bnode_read_u8() argument
68 hfs_bnode_read(node, &data, off, 1); in hfs_bnode_read_u8()
72 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, u32 off) in hfs_bnode_read_key() argument
77 tree = node->tree; in hfs_bnode_read_key()
78 if (node->type == HFS_NODE_LEAF || in hfs_bnode_read_key()
80 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
81 key_len = hfs_bnode_read_u16(node, off) + 2; in hfs_bnode_read_key()
91 hfs_bnode_read(node, key, off, key_len); in hfs_bnode_read_key()
94 void hfs_bnode_write(struct hfs_bnode *node, void *buf, u32 off, u32 len) in hfs_bnode_write() argument
99 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_write()
104 "NODE: id %u, type %#x, height %u, " in hfs_bnode_write()
106 node->this, node->type, node->height, in hfs_bnode_write()
107 node->tree->node_size, off, len); in hfs_bnode_write()
111 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_write()
113 off += node->page_offset; in hfs_bnode_write()
114 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_write()
129 void hfs_bnode_write_u16(struct hfs_bnode *node, u32 off, u16 data) in hfs_bnode_write_u16() argument
133 hfs_bnode_write(node, &v, off, 2); in hfs_bnode_write_u16()
136 void hfs_bnode_clear(struct hfs_bnode *node, u32 off, u32 len) in hfs_bnode_clear() argument
141 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_clear()
146 "NODE: id %u, type %#x, height %u, " in hfs_bnode_clear()
148 node->this, node->type, node->height, in hfs_bnode_clear()
149 node->tree->node_size, off, len); in hfs_bnode_clear()
153 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_clear()
155 off += node->page_offset; in hfs_bnode_clear()
156 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_clear()
228 void hfs_bnode_move(struct hfs_bnode *node, u32 dst, u32 src, u32 len) in hfs_bnode_move() argument
238 len = check_and_correct_requested_length(node, src, len); in hfs_bnode_move()
239 len = check_and_correct_requested_length(node, dst, len); in hfs_bnode_move()
241 src += node->page_offset; in hfs_bnode_move()
242 dst += node->page_offset; in hfs_bnode_move()
245 src_page = node->page + (src >> PAGE_SHIFT); in hfs_bnode_move()
248 dst_page = node->page + (dst >> PAGE_SHIFT); in hfs_bnode_move()
296 src_page = node->page + (src >> PAGE_SHIFT); in hfs_bnode_move()
298 dst_page = node->page + (dst >> PAGE_SHIFT); in hfs_bnode_move()
348 void hfs_bnode_dump(struct hfs_bnode *node) in hfs_bnode_dump() argument
354 hfs_dbg("node %d\n", node->this); in hfs_bnode_dump()
355 hfs_bnode_read(node, &desc, 0, sizeof(desc)); in hfs_bnode_dump()
360 off = node->tree->node_size - 2; in hfs_bnode_dump()
362 key_off = hfs_bnode_read_u16(node, off); in hfs_bnode_dump()
364 if (i && node->type == HFS_NODE_INDEX) { in hfs_bnode_dump()
367 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
368 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
369 tmp = hfs_bnode_read_u16(node, key_off) + 2; in hfs_bnode_dump()
371 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
373 hfs_bnode_read(node, &cnid, key_off + tmp, 4); in hfs_bnode_dump()
375 } else if (i && node->type == HFS_NODE_LEAF) { in hfs_bnode_dump()
378 tmp = hfs_bnode_read_u16(node, key_off); in hfs_bnode_dump()
385 void hfs_bnode_unlink(struct hfs_bnode *node) in hfs_bnode_unlink() argument
391 tree = node->tree; in hfs_bnode_unlink()
392 if (node->prev) { in hfs_bnode_unlink()
393 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
396 tmp->next = node->next; in hfs_bnode_unlink()
401 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
402 tree->leaf_head = node->next; in hfs_bnode_unlink()
404 if (node->next) { in hfs_bnode_unlink()
405 tmp = hfs_bnode_find(tree, node->next); in hfs_bnode_unlink()
408 tmp->prev = node->prev; in hfs_bnode_unlink()
413 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
414 tree->leaf_tail = node->prev; in hfs_bnode_unlink()
417 if (!node->prev && !node->next) in hfs_bnode_unlink()
419 if (!node->parent) { in hfs_bnode_unlink()
423 set_bit(HFS_BNODE_DELETED, &node->flags); in hfs_bnode_unlink()
435 struct hfs_bnode *node; in hfs_bnode_findhash() local
438 pr_err("request for non-existent node %d in B*Tree\n", in hfs_bnode_findhash()
443 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; in hfs_bnode_findhash()
444 node; node = node->next_hash) in hfs_bnode_findhash()
445 if (node->this == cnid) in hfs_bnode_findhash()
446 return node; in hfs_bnode_findhash()
452 struct hfs_bnode *node, *node2; in __hfs_bnode_create() local
459 pr_err("request for non-existent node %d in B*Tree\n", in __hfs_bnode_create()
466 node = kzalloc(size, GFP_KERNEL); in __hfs_bnode_create()
467 if (!node) in __hfs_bnode_create()
469 node->tree = tree; in __hfs_bnode_create()
470 node->this = cnid; in __hfs_bnode_create()
471 set_bit(HFS_BNODE_NEW, &node->flags); in __hfs_bnode_create()
472 atomic_set(&node->refcnt, 1); in __hfs_bnode_create()
473 hfs_dbg("cnid %d, node %d, refcnt 1\n", in __hfs_bnode_create()
474 node->tree->cnid, node->this); in __hfs_bnode_create()
475 init_waitqueue_head(&node->lock_wq); in __hfs_bnode_create()
480 node->next_hash = tree->node_hash[hash]; in __hfs_bnode_create()
481 tree->node_hash[hash] = node; in __hfs_bnode_create()
486 kfree(node); in __hfs_bnode_create()
496 node->page_offset = off & ~PAGE_MASK; in __hfs_bnode_create()
501 node->page[i] = page; in __hfs_bnode_create()
504 return node; in __hfs_bnode_create()
506 set_bit(HFS_BNODE_ERROR, &node->flags); in __hfs_bnode_create()
507 return node; in __hfs_bnode_create()
510 void hfs_bnode_unhash(struct hfs_bnode *node) in hfs_bnode_unhash() argument
514 hfs_dbg("cnid %d, node %d, refcnt %d\n", in hfs_bnode_unhash()
515 node->tree->cnid, node->this, atomic_read(&node->refcnt)); in hfs_bnode_unhash()
516 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; in hfs_bnode_unhash()
517 *p && *p != node; p = &(*p)->next_hash) in hfs_bnode_unhash()
520 *p = node->next_hash; in hfs_bnode_unhash()
521 node->tree->node_hash_cnt--; in hfs_bnode_unhash()
524 /* Load a particular node out of a tree */
527 struct hfs_bnode *node; in hfs_bnode_find() local
533 node = hfs_bnode_findhash(tree, num); in hfs_bnode_find()
534 if (node) { in hfs_bnode_find()
535 hfs_bnode_get(node); in hfs_bnode_find()
537 wait_event(node->lock_wq, in hfs_bnode_find()
538 !test_bit(HFS_BNODE_NEW, &node->flags)); in hfs_bnode_find()
539 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
541 return node; in hfs_bnode_find()
544 node = __hfs_bnode_create(tree, num); in hfs_bnode_find()
545 if (!node) in hfs_bnode_find()
547 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
549 if (!test_bit(HFS_BNODE_NEW, &node->flags)) in hfs_bnode_find()
550 return node; in hfs_bnode_find()
552 desc = (struct hfs_bnode_desc *)(kmap_local_page(node->page[0]) + in hfs_bnode_find()
553 node->page_offset); in hfs_bnode_find()
554 node->prev = be32_to_cpu(desc->prev); in hfs_bnode_find()
555 node->next = be32_to_cpu(desc->next); in hfs_bnode_find()
556 node->num_recs = be16_to_cpu(desc->num_recs); in hfs_bnode_find()
557 node->type = desc->type; in hfs_bnode_find()
558 node->height = desc->height; in hfs_bnode_find()
561 switch (node->type) { in hfs_bnode_find()
564 if (node->height != 0) in hfs_bnode_find()
568 if (node->height != 1) in hfs_bnode_find()
572 if (node->height <= 1 || node->height > tree->depth) in hfs_bnode_find()
580 off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
583 for (i = 1; i <= node->num_recs; off = next_off, i++) { in hfs_bnode_find()
585 next_off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
591 if (node->type != HFS_NODE_INDEX && in hfs_bnode_find()
592 node->type != HFS_NODE_LEAF) in hfs_bnode_find()
594 key_size = hfs_bnode_read_u16(node, off) + 2; in hfs_bnode_find()
598 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
599 wake_up(&node->lock_wq); in hfs_bnode_find()
600 return node; in hfs_bnode_find()
603 set_bit(HFS_BNODE_ERROR, &node->flags); in hfs_bnode_find()
604 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
605 wake_up(&node->lock_wq); in hfs_bnode_find()
606 hfs_bnode_put(node); in hfs_bnode_find()
610 void hfs_bnode_free(struct hfs_bnode *node) in hfs_bnode_free() argument
614 for (i = 0; i < node->tree->pages_per_bnode; i++) in hfs_bnode_free()
615 if (node->page[i]) in hfs_bnode_free()
616 put_page(node->page[i]); in hfs_bnode_free()
617 kfree(node); in hfs_bnode_free()
622 struct hfs_bnode *node; in hfs_bnode_create() local
627 node = hfs_bnode_findhash(tree, num); in hfs_bnode_create()
629 if (node) { in hfs_bnode_create()
630 pr_crit("new node %u already hashed?\n", num); in hfs_bnode_create()
634 node = __hfs_bnode_create(tree, num); in hfs_bnode_create()
635 if (!node) in hfs_bnode_create()
637 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { in hfs_bnode_create()
638 hfs_bnode_put(node); in hfs_bnode_create()
642 pagep = node->page; in hfs_bnode_create()
643 memzero_page(*pagep, node->page_offset, in hfs_bnode_create()
650 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_create()
651 wake_up(&node->lock_wq); in hfs_bnode_create()
653 return node; in hfs_bnode_create()
656 void hfs_bnode_get(struct hfs_bnode *node) in hfs_bnode_get() argument
658 if (node) { in hfs_bnode_get()
659 atomic_inc(&node->refcnt); in hfs_bnode_get()
660 hfs_dbg("cnid %d, node %d, refcnt %d\n", in hfs_bnode_get()
661 node->tree->cnid, node->this, in hfs_bnode_get()
662 atomic_read(&node->refcnt)); in hfs_bnode_get()
666 /* Dispose of resources used by a node */
667 void hfs_bnode_put(struct hfs_bnode *node) in hfs_bnode_put() argument
669 if (node) { in hfs_bnode_put()
670 struct hfs_btree *tree = node->tree; in hfs_bnode_put()
673 hfs_dbg("cnid %d, node %d, refcnt %d\n", in hfs_bnode_put()
674 node->tree->cnid, node->this, in hfs_bnode_put()
675 atomic_read(&node->refcnt)); in hfs_bnode_put()
676 BUG_ON(!atomic_read(&node->refcnt)); in hfs_bnode_put()
677 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) in hfs_bnode_put()
680 if (!node->page[i]) in hfs_bnode_put()
682 mark_page_accessed(node->page[i]); in hfs_bnode_put()
685 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { in hfs_bnode_put()
686 hfs_bnode_unhash(node); in hfs_bnode_put()
689 hfs_bnode_clear(node, 0, tree->node_size); in hfs_bnode_put()
690 hfs_bmap_free(node); in hfs_bnode_put()
691 hfs_bnode_free(node); in hfs_bnode_put()