2 * Copyright (c) 2007-2008 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * $DragonFly: src/sys/vfs/hammer/hammer_cursor.c,v 1.42 2008/08/06 15:38:58 dillon Exp $
38 * HAMMER B-Tree index - cursor support routines
42 static int hammer_load_cursor_parent(hammer_cursor_t cursor
, int try_exclusive
);
45 * Initialize a fresh cursor using the B-Tree node cache. If the cache
46 * is not available initialize a fresh cursor at the root of the filesystem.
49 hammer_init_cursor(hammer_transaction_t trans
, hammer_cursor_t cursor
,
50 hammer_node_cache_t cache
, hammer_inode_t ip
)
52 hammer_volume_t volume
;
56 bzero(cursor
, sizeof(*cursor
));
58 cursor
->trans
= trans
;
61 * If the cursor operation is on behalf of an inode, lock
64 if ((cursor
->ip
= ip
) != NULL
) {
66 if (trans
->type
== HAMMER_TRANS_FLS
)
67 hammer_lock_ex(&ip
->lock
);
69 hammer_lock_sh(&ip
->lock
);
73 * Step 1 - acquire a locked node from the cache if possible
75 if (cache
&& cache
->node
) {
76 node
= hammer_ref_node_safe(trans
, cache
, &error
);
78 hammer_lock_sh(&node
->lock
);
79 if (node
->flags
& HAMMER_NODE_DELETED
) {
80 hammer_unlock(&node
->lock
);
81 hammer_rel_node(node
);
86 ++hammer_stats_btree_root_iterations
;
89 ++hammer_stats_btree_root_iterations
;
93 * Step 2 - If we couldn't get a node from the cache, get
94 * the one from the root of the filesystem.
96 while (node
== NULL
) {
97 volume
= hammer_get_root_volume(trans
->hmp
, &error
);
100 node
= hammer_get_node(trans
, volume
->ondisk
->vol0_btree_root
,
102 hammer_rel_volume(volume
, 0);
105 hammer_lock_sh(&node
->lock
);
108 * If someone got in before we could lock the node, retry.
110 if (node
->flags
& HAMMER_NODE_DELETED
) {
111 hammer_unlock(&node
->lock
);
112 hammer_rel_node(node
);
116 if (volume
->ondisk
->vol0_btree_root
!= node
->node_offset
) {
117 hammer_unlock(&node
->lock
);
118 hammer_rel_node(node
);
125 * Step 3 - finish initializing the cursor by acquiring the parent
129 error
= hammer_load_cursor_parent(cursor
, 0);
130 KKASSERT(error
== 0);
131 /* if (error) hammer_done_cursor(cursor); */
136 * Normalize a cursor. Sometimes cursors can be left in a state
137 * where node is NULL. If the cursor is in this state, cursor up.
140 hammer_normalize_cursor(hammer_cursor_t cursor
)
142 if (cursor
->node
== NULL
) {
143 KKASSERT(cursor
->parent
!= NULL
);
144 hammer_cursor_up(cursor
);
150 * We are finished with a cursor. We NULL out various fields as sanity
151 * check, in case the structure is inappropriately used afterwords.
154 hammer_done_cursor(hammer_cursor_t cursor
)
158 KKASSERT((cursor
->flags
& HAMMER_CURSOR_TRACKED
) == 0);
159 if (cursor
->parent
) {
160 hammer_unlock(&cursor
->parent
->lock
);
161 hammer_rel_node(cursor
->parent
);
162 cursor
->parent
= NULL
;
165 hammer_unlock(&cursor
->node
->lock
);
166 hammer_rel_node(cursor
->node
);
169 if (cursor
->data_buffer
) {
170 hammer_rel_buffer(cursor
->data_buffer
, 0);
171 cursor
->data_buffer
= NULL
;
173 if ((ip
= cursor
->ip
) != NULL
) {
174 KKASSERT(ip
->cursor_ip_refs
> 0);
175 --ip
->cursor_ip_refs
;
176 hammer_unlock(&ip
->lock
);
180 hammer_rel_mem_record(cursor
->iprec
);
181 cursor
->iprec
= NULL
;
185 * If we deadlocked this node will be referenced. Do a quick
186 * lock/unlock to wait for the deadlock condition to clear.
188 if (cursor
->deadlk_node
) {
189 hammer_lock_ex_ident(&cursor
->deadlk_node
->lock
, "hmrdlk");
190 hammer_unlock(&cursor
->deadlk_node
->lock
);
191 hammer_rel_node(cursor
->deadlk_node
);
192 cursor
->deadlk_node
= NULL
;
194 if (cursor
->deadlk_rec
) {
195 hammer_wait_mem_record_ident(cursor
->deadlk_rec
, "hmmdlr");
196 hammer_rel_mem_record(cursor
->deadlk_rec
);
197 cursor
->deadlk_rec
= NULL
;
202 cursor
->left_bound
= NULL
;
203 cursor
->right_bound
= NULL
;
204 cursor
->trans
= NULL
;
208 * Upgrade cursor->node and cursor->parent to exclusive locks. This
209 * function can return EDEADLK.
211 * The lock must already be either held shared or already held exclusively
214 * If we fail to upgrade the lock and cursor->deadlk_node is NULL,
215 * we add another reference to the node that failed and set
216 * cursor->deadlk_node so hammer_done_cursor() can block on it.
219 hammer_cursor_upgrade(hammer_cursor_t cursor
)
223 error
= hammer_lock_upgrade(&cursor
->node
->lock
, 1);
224 if (error
&& cursor
->deadlk_node
== NULL
) {
225 cursor
->deadlk_node
= cursor
->node
;
226 hammer_ref_node(cursor
->deadlk_node
);
227 } else if (error
== 0 && cursor
->parent
) {
228 error
= hammer_lock_upgrade(&cursor
->parent
->lock
, 1);
229 if (error
&& cursor
->deadlk_node
== NULL
) {
230 cursor
->deadlk_node
= cursor
->parent
;
231 hammer_ref_node(cursor
->deadlk_node
);
238 hammer_cursor_upgrade_node(hammer_cursor_t cursor
)
242 error
= hammer_lock_upgrade(&cursor
->node
->lock
, 1);
243 if (error
&& cursor
->deadlk_node
== NULL
) {
244 cursor
->deadlk_node
= cursor
->node
;
245 hammer_ref_node(cursor
->deadlk_node
);
251 * Downgrade cursor->node and cursor->parent to shared locks. This
252 * function can return EDEADLK.
255 hammer_cursor_downgrade(hammer_cursor_t cursor
)
257 if (hammer_lock_excl_owned(&cursor
->node
->lock
, curthread
))
258 hammer_lock_downgrade(&cursor
->node
->lock
, 1);
259 if (cursor
->parent
&&
260 hammer_lock_excl_owned(&cursor
->parent
->lock
, curthread
)) {
261 hammer_lock_downgrade(&cursor
->parent
->lock
, 1);
266 * Upgrade and downgrade pairs of cursors. This is used by the dedup
267 * code which must deal with two cursors. A special function is needed
268 * because some of the nodes may be shared between the two cursors,
269 * resulting in share counts > 1 which will normally cause an upgrade
274 collect_node(hammer_node_t
*array
, int *counts
, int n
, hammer_node_t node
)
278 for (i
= 0; i
< n
; ++i
) {
279 if (array
[i
] == node
)
293 hammer_cursor_upgrade2(hammer_cursor_t cursor1
, hammer_cursor_t cursor2
)
295 hammer_node_t nodes
[4];
301 n
= collect_node(nodes
, counts
, 0, cursor1
->node
);
303 n
= collect_node(nodes
, counts
, n
, cursor1
->parent
);
304 n
= collect_node(nodes
, counts
, n
, cursor2
->node
);
306 n
= collect_node(nodes
, counts
, n
, cursor2
->parent
);
309 for (i
= 0; i
< n
; ++i
) {
310 error
= hammer_lock_upgrade(&nodes
[i
]->lock
, counts
[i
]);
316 hammer_lock_downgrade(&nodes
[i
]->lock
, counts
[i
]);
322 hammer_cursor_downgrade2(hammer_cursor_t cursor1
, hammer_cursor_t cursor2
)
324 hammer_node_t nodes
[4];
329 n
= collect_node(nodes
, counts
, 0, cursor1
->node
);
331 n
= collect_node(nodes
, counts
, n
, cursor1
->parent
);
332 n
= collect_node(nodes
, counts
, n
, cursor2
->node
);
334 n
= collect_node(nodes
, counts
, n
, cursor2
->parent
);
336 for (i
= 0; i
< n
; ++i
)
337 hammer_lock_downgrade(&nodes
[i
]->lock
, counts
[i
]);
341 * Seek the cursor to the specified node and index.
343 * The caller must ref the node prior to calling this routine and release
344 * it after it returns. If the seek succeeds the cursor will gain its own
348 hammer_cursor_seek(hammer_cursor_t cursor
, hammer_node_t node
, int index
)
352 hammer_cursor_downgrade(cursor
);
355 if (cursor
->node
!= node
) {
356 hammer_unlock(&cursor
->node
->lock
);
357 hammer_rel_node(cursor
->node
);
359 hammer_ref_node(node
);
360 hammer_lock_sh(&node
->lock
);
361 KKASSERT ((node
->flags
& HAMMER_NODE_DELETED
) == 0);
363 if (cursor
->parent
) {
364 hammer_unlock(&cursor
->parent
->lock
);
365 hammer_rel_node(cursor
->parent
);
366 cursor
->parent
= NULL
;
367 cursor
->parent_index
= 0;
369 error
= hammer_load_cursor_parent(cursor
, 0);
371 cursor
->index
= index
;
376 * Load the parent of cursor->node into cursor->parent.
380 hammer_load_cursor_parent(hammer_cursor_t cursor
, int try_exclusive
)
383 hammer_node_t parent
;
385 hammer_btree_elm_t elm
;
389 hmp
= cursor
->trans
->hmp
;
391 if (cursor
->node
->ondisk
->parent
) {
393 parent
= hammer_btree_get_parent(cursor
->trans
, node
,
395 &error
, try_exclusive
);
397 elm
= &parent
->ondisk
->elms
[parent_index
];
398 cursor
->parent
= parent
;
399 cursor
->parent_index
= parent_index
;
400 cursor
->left_bound
= &elm
[0].internal
.base
;
401 cursor
->right_bound
= &elm
[1].internal
.base
;
404 cursor
->parent
= NULL
;
405 cursor
->parent_index
= 0;
406 cursor
->left_bound
= &hmp
->root_btree_beg
;
407 cursor
->right_bound
= &hmp
->root_btree_end
;
414 * Cursor up to our parent node. Return ENOENT if we are at the root of
418 hammer_cursor_up(hammer_cursor_t cursor
)
422 hammer_cursor_downgrade(cursor
);
425 * If the parent is NULL we are at the root of the B-Tree and
428 if (cursor
->parent
== NULL
)
432 * Set the node to its parent.
434 hammer_unlock(&cursor
->node
->lock
);
435 hammer_rel_node(cursor
->node
);
436 cursor
->node
= cursor
->parent
;
437 cursor
->index
= cursor
->parent_index
;
438 cursor
->parent
= NULL
;
439 cursor
->parent_index
= 0;
441 error
= hammer_load_cursor_parent(cursor
, 0);
446 * Special cursor up given a locked cursor. The orignal node is not
447 * unlocked or released and the cursor is not downgraded.
449 * This function can fail with EDEADLK.
451 * This function is only run when recursively deleting parent nodes
452 * to get rid of an empty leaf.
455 hammer_cursor_up_locked(hammer_cursor_t cursor
)
462 * If the parent is NULL we are at the root of the B-Tree and
465 if (cursor
->parent
== NULL
)
469 save_index
= cursor
->index
;
472 * Set the node to its parent.
474 cursor
->node
= cursor
->parent
;
475 cursor
->index
= cursor
->parent_index
;
476 cursor
->parent
= NULL
;
477 cursor
->parent_index
= 0;
480 * load the new parent, attempt to exclusively lock it. Note that
481 * we are still holding the old parent (now cursor->node) exclusively
484 * This can return EDEADLK. Undo the operation on any error. These
485 * up sequences can occur during iterations so be sure to restore
488 error
= hammer_load_cursor_parent(cursor
, 1);
490 cursor
->parent
= cursor
->node
;
491 cursor
->parent_index
= cursor
->index
;
493 cursor
->index
= save_index
;
500 * Cursor down through the current node, which must be an internal node.
502 * This routine adjusts the cursor and sets index to 0.
505 hammer_cursor_down(hammer_cursor_t cursor
)
508 hammer_btree_elm_t elm
;
512 * The current node becomes the current parent
514 hammer_cursor_downgrade(cursor
);
516 KKASSERT(cursor
->index
>= 0 && cursor
->index
< node
->ondisk
->count
);
517 if (cursor
->parent
) {
518 hammer_unlock(&cursor
->parent
->lock
);
519 hammer_rel_node(cursor
->parent
);
521 cursor
->parent
= node
;
522 cursor
->parent_index
= cursor
->index
;
527 * Extract element to push into at (node,index), set bounds.
529 elm
= &node
->ondisk
->elms
[cursor
->parent_index
];
532 * Ok, push down into elm. If elm specifies an internal or leaf
533 * node the current node must be an internal node. If elm specifies
534 * a spike then the current node must be a leaf node.
536 switch(elm
->base
.btype
) {
537 case HAMMER_BTREE_TYPE_INTERNAL
:
538 case HAMMER_BTREE_TYPE_LEAF
:
539 KKASSERT(node
->ondisk
->type
== HAMMER_BTREE_TYPE_INTERNAL
);
540 KKASSERT(elm
->internal
.subtree_offset
!= 0);
541 cursor
->left_bound
= &elm
[0].internal
.base
;
542 cursor
->right_bound
= &elm
[1].internal
.base
;
543 node
= hammer_get_node(cursor
->trans
,
544 elm
->internal
.subtree_offset
, 0, &error
);
546 KASSERT(elm
->base
.btype
== node
->ondisk
->type
, ("BTYPE MISMATCH %c %c NODE %p\n", elm
->base
.btype
, node
->ondisk
->type
, node
));
547 if (node
->ondisk
->parent
!= cursor
->parent
->node_offset
)
548 panic("node %p %016llx vs %016llx\n", node
, (long long)node
->ondisk
->parent
, (long long)cursor
->parent
->node_offset
);
549 KKASSERT(node
->ondisk
->parent
== cursor
->parent
->node_offset
);
553 panic("hammer_cursor_down: illegal btype %02x (%c)\n",
555 (elm
->base
.btype
? elm
->base
.btype
: '?'));
559 hammer_lock_sh(&node
->lock
);
560 KKASSERT ((node
->flags
& HAMMER_NODE_DELETED
) == 0);
567 /************************************************************************
568 * DEADLOCK RECOVERY *
569 ************************************************************************
571 * These are the new deadlock recovery functions. Currently they are only
572 * used for the mirror propagation and physical node removal cases but
573 * ultimately the intention is to use them for all deadlock recovery
576 * WARNING! The contents of the cursor may be modified while unlocked.
577 * passive modifications including adjusting the node, parent,
578 * indexes, and leaf pointer.
580 * An outright removal of the element the cursor was pointing at
581 * will cause the HAMMER_CURSOR_TRACKED_RIPOUT flag to be set,
582 * which chains to causing the HAMMER_CURSOR_RETEST to be set
583 * when the cursor is locked again.
586 hammer_unlock_cursor(hammer_cursor_t cursor
)
590 KKASSERT((cursor
->flags
& HAMMER_CURSOR_TRACKED
) == 0);
591 KKASSERT(cursor
->node
);
594 * Release the cursor's locks and track B-Tree operations on node.
595 * While being tracked our cursor can be modified by other threads
596 * and the node may be replaced.
598 if (cursor
->parent
) {
599 hammer_unlock(&cursor
->parent
->lock
);
600 hammer_rel_node(cursor
->parent
);
601 cursor
->parent
= NULL
;
604 cursor
->flags
|= HAMMER_CURSOR_TRACKED
;
605 TAILQ_INSERT_TAIL(&node
->cursor_list
, cursor
, deadlk_entry
);
606 hammer_unlock(&node
->lock
);
610 * Get the cursor heated up again. The cursor's node may have
611 * changed and we might have to locate the new parent.
613 * If the exact element we were on got deleted RIPOUT will be
614 * set and we must clear ATEDISK so an iteration does not skip
615 * the element after it.
618 hammer_lock_cursor(hammer_cursor_t cursor
)
623 KKASSERT(cursor
->flags
& HAMMER_CURSOR_TRACKED
);
630 hammer_ref_node(node
);
631 hammer_lock_sh(&node
->lock
);
632 if (cursor
->node
== node
) {
633 hammer_rel_node(node
);
636 hammer_unlock(&node
->lock
);
637 hammer_rel_node(node
);
641 * Untrack the cursor, clean up, and re-establish the parent node.
643 TAILQ_REMOVE(&node
->cursor_list
, cursor
, deadlk_entry
);
644 cursor
->flags
&= ~HAMMER_CURSOR_TRACKED
;
647 * If a ripout has occured iterations must re-test the (new)
648 * current element. Clearing ATEDISK prevents the element from
649 * being skipped and RETEST causes it to be re-tested.
651 if (cursor
->flags
& HAMMER_CURSOR_TRACKED_RIPOUT
) {
652 cursor
->flags
&= ~HAMMER_CURSOR_TRACKED_RIPOUT
;
653 cursor
->flags
&= ~HAMMER_CURSOR_ATEDISK
;
654 cursor
->flags
|= HAMMER_CURSOR_RETEST
;
656 error
= hammer_load_cursor_parent(cursor
, 0);
661 * Recover from a deadlocked cursor, tracking any node removals or
662 * replacements. If the cursor's current node is removed by another
663 * thread (via btree_remove()) the cursor will be seeked upwards.
665 * The caller is working a modifying operation and must be holding the
666 * sync lock (shared). We do not release the sync lock because this
667 * would break atomicy.
670 hammer_recover_cursor(hammer_cursor_t cursor
)
674 hammer_unlock_cursor(cursor
);
675 KKASSERT(cursor
->trans
->sync_lock_refs
> 0);
678 * Wait for the deadlock to clear
680 if (cursor
->deadlk_node
) {
681 hammer_lock_ex_ident(&cursor
->deadlk_node
->lock
, "hmrdlk");
682 hammer_unlock(&cursor
->deadlk_node
->lock
);
683 hammer_rel_node(cursor
->deadlk_node
);
684 cursor
->deadlk_node
= NULL
;
686 if (cursor
->deadlk_rec
) {
687 hammer_wait_mem_record_ident(cursor
->deadlk_rec
, "hmmdlr");
688 hammer_rel_mem_record(cursor
->deadlk_rec
);
689 cursor
->deadlk_rec
= NULL
;
691 error
= hammer_lock_cursor(cursor
);
696 * Dup ocursor to ncursor. ncursor inherits ocursor's locks and ocursor
697 * is effectively unlocked and becomes tracked. If ocursor was not locked
698 * then ncursor also inherits the tracking.
700 * After the caller finishes working with ncursor it must be cleaned up
701 * with hammer_done_cursor(), and the caller must re-lock ocursor.
704 hammer_push_cursor(hammer_cursor_t ocursor
)
706 hammer_cursor_t ncursor
;
711 hmp
= ocursor
->trans
->hmp
;
712 ncursor
= kmalloc(sizeof(*ncursor
), hmp
->m_misc
, M_WAITOK
| M_ZERO
);
713 bcopy(ocursor
, ncursor
, sizeof(*ocursor
));
715 node
= ocursor
->node
;
716 hammer_ref_node(node
);
717 if ((ocursor
->flags
& HAMMER_CURSOR_TRACKED
) == 0) {
718 ocursor
->flags
|= HAMMER_CURSOR_TRACKED
;
719 TAILQ_INSERT_TAIL(&node
->cursor_list
, ocursor
, deadlk_entry
);
722 ocursor
->parent
= NULL
;
723 ocursor
->data_buffer
= NULL
;
724 ocursor
->leaf
= NULL
;
725 ocursor
->data
= NULL
;
726 if (ncursor
->flags
& HAMMER_CURSOR_TRACKED
)
727 TAILQ_INSERT_TAIL(&node
->cursor_list
, ncursor
, deadlk_entry
);
728 if ((ip
= ncursor
->ip
) != NULL
) {
729 ++ip
->cursor_ip_refs
;
732 hammer_ref(&ncursor
->iprec
->lock
);
737 * Destroy ncursor and restore ocursor
739 * This is a temporary hack for the release. We can't afford to lose
740 * the IP lock until the IP object scan code is able to deal with it,
741 * so have ocursor inherit it back.
744 hammer_pop_cursor(hammer_cursor_t ocursor
, hammer_cursor_t ncursor
)
749 hmp
= ncursor
->trans
->hmp
;
753 --ip
->cursor_ip_refs
;
754 hammer_done_cursor(ncursor
);
755 kfree(ncursor
, hmp
->m_misc
);
756 KKASSERT(ocursor
->ip
== ip
);
757 hammer_lock_cursor(ocursor
);
761 * onode is being replaced by nnode by the reblocking code.
764 hammer_cursor_replaced_node(hammer_node_t onode
, hammer_node_t nnode
)
766 hammer_cursor_t cursor
;
767 hammer_node_ondisk_t ondisk
;
768 hammer_node_ondisk_t nndisk
;
770 ondisk
= onode
->ondisk
;
771 nndisk
= nnode
->ondisk
;
773 while ((cursor
= TAILQ_FIRST(&onode
->cursor_list
)) != NULL
) {
774 TAILQ_REMOVE(&onode
->cursor_list
, cursor
, deadlk_entry
);
775 TAILQ_INSERT_TAIL(&nnode
->cursor_list
, cursor
, deadlk_entry
);
776 KKASSERT(cursor
->node
== onode
);
777 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
778 cursor
->leaf
= &nndisk
->elms
[cursor
->index
].leaf
;
779 cursor
->node
= nnode
;
780 hammer_ref_node(nnode
);
781 hammer_rel_node(onode
);
786 * We have removed <node> from the parent and collapsed the parent.
788 * Cursors in deadlock recovery are seeked upward to the parent so the
789 * btree_remove() recursion works properly even though we have marked
790 * the cursor as requiring a reseek.
792 * This is the only cursor function which sets HAMMER_CURSOR_ITERATE_CHECK,
793 * meaning the cursor is no longer definitively pointing at an element
794 * within its iteration (if the cursor is being used to iterate). The
795 * iteration code will take this into account instead of asserting if the
796 * cursor is outside the iteration range.
799 hammer_cursor_removed_node(hammer_node_t node
, hammer_node_t parent
, int index
)
801 hammer_cursor_t cursor
;
802 hammer_node_ondisk_t ondisk
;
804 KKASSERT(parent
!= NULL
);
805 ondisk
= node
->ondisk
;
807 while ((cursor
= TAILQ_FIRST(&node
->cursor_list
)) != NULL
) {
808 KKASSERT(cursor
->node
== node
);
809 KKASSERT(cursor
->index
== 0);
810 TAILQ_REMOVE(&node
->cursor_list
, cursor
, deadlk_entry
);
811 TAILQ_INSERT_TAIL(&parent
->cursor_list
, cursor
, deadlk_entry
);
812 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
814 cursor
->flags
|= HAMMER_CURSOR_TRACKED_RIPOUT
;
815 cursor
->flags
|= HAMMER_CURSOR_ITERATE_CHECK
;
816 cursor
->node
= parent
;
817 cursor
->index
= index
;
818 hammer_ref_node(parent
);
819 hammer_rel_node(node
);
824 * node was split at (onode, index) with elements >= index moved to nnode.
827 hammer_cursor_split_node(hammer_node_t onode
, hammer_node_t nnode
, int index
)
829 hammer_cursor_t cursor
;
830 hammer_node_ondisk_t ondisk
;
831 hammer_node_ondisk_t nndisk
;
833 ondisk
= onode
->ondisk
;
834 nndisk
= nnode
->ondisk
;
837 TAILQ_FOREACH(cursor
, &onode
->cursor_list
, deadlk_entry
) {
838 KKASSERT(cursor
->node
== onode
);
839 if (cursor
->index
< index
)
841 TAILQ_REMOVE(&onode
->cursor_list
, cursor
, deadlk_entry
);
842 TAILQ_INSERT_TAIL(&nnode
->cursor_list
, cursor
, deadlk_entry
);
843 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
844 cursor
->leaf
= &nndisk
->elms
[cursor
->index
- index
].leaf
;
845 cursor
->node
= nnode
;
846 cursor
->index
-= index
;
847 hammer_ref_node(nnode
);
848 hammer_rel_node(onode
);
854 * An element was moved from one node to another or within a node. The
855 * index may also represent the end of the node (index == numelements).
857 * {oparent,pindex} is the parent node's pointer to onode/oindex.
859 * This is used by the rebalancing code. This is not an insertion or
860 * deletion and any additional elements, including the degenerate case at
861 * the end of the node, will be dealt with by additional distinct calls.
864 hammer_cursor_moved_element(hammer_node_t oparent
, int pindex
,
865 hammer_node_t onode
, int oindex
,
866 hammer_node_t nnode
, int nindex
)
868 hammer_cursor_t cursor
;
869 hammer_node_ondisk_t ondisk
;
870 hammer_node_ondisk_t nndisk
;
873 * Adjust any cursors pointing at the element
875 ondisk
= onode
->ondisk
;
876 nndisk
= nnode
->ondisk
;
878 TAILQ_FOREACH(cursor
, &onode
->cursor_list
, deadlk_entry
) {
879 KKASSERT(cursor
->node
== onode
);
880 if (cursor
->index
!= oindex
)
882 TAILQ_REMOVE(&onode
->cursor_list
, cursor
, deadlk_entry
);
883 TAILQ_INSERT_TAIL(&nnode
->cursor_list
, cursor
, deadlk_entry
);
884 if (cursor
->leaf
== &ondisk
->elms
[oindex
].leaf
)
885 cursor
->leaf
= &nndisk
->elms
[nindex
].leaf
;
886 cursor
->node
= nnode
;
887 cursor
->index
= nindex
;
888 hammer_ref_node(nnode
);
889 hammer_rel_node(onode
);
894 * When moving the first element of onode to a different node any
895 * cursor which is pointing at (oparent,pindex) must be repointed
896 * to nnode and ATEDISK must be cleared.
898 * This prevents cursors from losing track due to insertions.
899 * Insertions temporarily release the cursor in order to update
900 * the mirror_tids. It primarily effects the mirror_write code.
901 * The other code paths generally only do a single insertion and
902 * then relookup or drop the cursor.
904 if (onode
== nnode
|| oindex
)
906 ondisk
= oparent
->ondisk
;
908 TAILQ_FOREACH(cursor
, &oparent
->cursor_list
, deadlk_entry
) {
909 KKASSERT(cursor
->node
== oparent
);
910 if (cursor
->index
!= pindex
)
912 kprintf("HAMMER debug: shifted cursor pointing at parent\n"
913 "parent %016jx:%d onode %016jx:%d nnode %016jx:%d\n",
914 (intmax_t)oparent
->node_offset
, pindex
,
915 (intmax_t)onode
->node_offset
, oindex
,
916 (intmax_t)nnode
->node_offset
, nindex
);
917 TAILQ_REMOVE(&oparent
->cursor_list
, cursor
, deadlk_entry
);
918 TAILQ_INSERT_TAIL(&nnode
->cursor_list
, cursor
, deadlk_entry
);
919 if (cursor
->leaf
== &ondisk
->elms
[oindex
].leaf
)
920 cursor
->leaf
= &nndisk
->elms
[nindex
].leaf
;
921 cursor
->node
= nnode
;
922 cursor
->index
= nindex
;
923 cursor
->flags
&= ~HAMMER_CURSOR_ATEDISK
;
924 hammer_ref_node(nnode
);
925 hammer_rel_node(oparent
);
931 * The B-Tree element pointing to the specified node was moved from (oparent)
932 * to (nparent, nindex). We must locate any tracked cursors pointing at
933 * node and adjust their parent accordingly.
935 * This is used by the rebalancing code when packing elements causes an
936 * element to shift from one node to another.
939 hammer_cursor_parent_changed(hammer_node_t node
, hammer_node_t oparent
,
940 hammer_node_t nparent
, int nindex
)
942 hammer_cursor_t cursor
;
945 TAILQ_FOREACH(cursor
, &node
->cursor_list
, deadlk_entry
) {
946 KKASSERT(cursor
->node
== node
);
947 if (cursor
->parent
== oparent
) {
948 cursor
->parent
= nparent
;
949 cursor
->parent_index
= nindex
;
950 hammer_ref_node(nparent
);
951 hammer_rel_node(oparent
);
958 * Deleted element at (node, index)
960 * Shift indexes >= index
963 hammer_cursor_deleted_element(hammer_node_t node
, int index
)
965 hammer_cursor_t cursor
;
966 hammer_node_ondisk_t ondisk
;
968 ondisk
= node
->ondisk
;
970 TAILQ_FOREACH(cursor
, &node
->cursor_list
, deadlk_entry
) {
971 KKASSERT(cursor
->node
== node
);
972 if (cursor
->index
== index
) {
973 cursor
->flags
|= HAMMER_CURSOR_TRACKED_RIPOUT
;
974 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
976 } else if (cursor
->index
> index
) {
977 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
978 cursor
->leaf
= &ondisk
->elms
[cursor
->index
- 1].leaf
;
985 * Inserted element at (node, index)
987 * Shift indexes >= index
990 hammer_cursor_inserted_element(hammer_node_t node
, int index
)
992 hammer_cursor_t cursor
;
993 hammer_node_ondisk_t ondisk
;
995 ondisk
= node
->ondisk
;
997 TAILQ_FOREACH(cursor
, &node
->cursor_list
, deadlk_entry
) {
998 KKASSERT(cursor
->node
== node
);
999 if (cursor
->index
>= index
) {
1000 if (cursor
->leaf
== &ondisk
->elms
[cursor
->index
].leaf
)
1001 cursor
->leaf
= &ondisk
->elms
[cursor
->index
+ 1].leaf
;
1008 * Invalidate the cached data buffer associated with a cursor.
1010 * This needs to be done when the underlying block is being freed or
1011 * the referenced buffer can prevent the related buffer cache buffer
1012 * from being properly invalidated.
1015 hammer_cursor_invalidate_cache(hammer_cursor_t cursor
)
1017 if (cursor
->data_buffer
) {
1018 hammer_rel_buffer(cursor
->data_buffer
, 0);
1019 cursor
->data_buffer
= NULL
;
1020 cursor
->data
= NULL
;