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->hmp, 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);
90 * Step 2 - If we couldn't get a node from the cache, get
91 * the one from the root of the filesystem.
93 while (node == NULL) {
94 volume = hammer_get_root_volume(trans->hmp, &error);
97 node = hammer_get_node(trans, volume->ondisk->vol0_btree_root,
99 hammer_rel_volume(volume, 0);
102 hammer_lock_sh(&node->lock);
105 * If someone got in before we could lock the node, retry.
107 if (node->flags & HAMMER_NODE_DELETED) {
108 hammer_unlock(&node->lock);
109 hammer_rel_node(node);
113 if (volume->ondisk->vol0_btree_root != node->node_offset) {
114 hammer_unlock(&node->lock);
115 hammer_rel_node(node);
122 * Step 3 - finish initializing the cursor by acquiring the parent
126 error = hammer_load_cursor_parent(cursor, 0);
127 KKASSERT(error == 0);
128 /* if (error) hammer_done_cursor(cursor); */
133 * Normalize a cursor. Sometimes cursors can be left in a state
134 * where node is NULL. If the cursor is in this state, cursor up.
137 hammer_normalize_cursor(hammer_cursor_t cursor)
139 if (cursor->node == NULL) {
140 KKASSERT(cursor->parent != NULL);
141 hammer_cursor_up(cursor);
147 * We are finished with a cursor. We NULL out various fields as sanity
148 * check, in case the structure is inappropriately used afterwords.
151 hammer_done_cursor(hammer_cursor_t cursor)
155 KKASSERT((cursor->flags & HAMMER_CURSOR_TRACKED) == 0);
156 if (cursor->parent) {
157 hammer_unlock(&cursor->parent->lock);
158 hammer_rel_node(cursor->parent);
159 cursor->parent = NULL;
162 hammer_unlock(&cursor->node->lock);
163 hammer_rel_node(cursor->node);
166 if (cursor->data_buffer) {
167 hammer_rel_buffer(cursor->data_buffer, 0);
168 cursor->data_buffer = NULL;
170 if ((ip = cursor->ip) != NULL) {
171 KKASSERT(ip->cursor_ip_refs > 0);
172 --ip->cursor_ip_refs;
173 hammer_unlock(&ip->lock);
177 hammer_rel_mem_record(cursor->iprec);
178 cursor->iprec = NULL;
182 * If we deadlocked this node will be referenced. Do a quick
183 * lock/unlock to wait for the deadlock condition to clear.
185 if (cursor->deadlk_node) {
186 hammer_lock_ex_ident(&cursor->deadlk_node->lock, "hmrdlk");
187 hammer_unlock(&cursor->deadlk_node->lock);
188 hammer_rel_node(cursor->deadlk_node);
189 cursor->deadlk_node = NULL;
191 if (cursor->deadlk_rec) {
192 hammer_wait_mem_record_ident(cursor->deadlk_rec, "hmmdlr");
193 hammer_rel_mem_record(cursor->deadlk_rec);
194 cursor->deadlk_rec = NULL;
199 cursor->left_bound = NULL;
200 cursor->right_bound = NULL;
201 cursor->trans = NULL;
205 * Upgrade cursor->node and cursor->parent to exclusive locks. This
206 * function can return EDEADLK.
208 * The lock must already be either held shared or already held exclusively
211 * If we fail to upgrade the lock and cursor->deadlk_node is NULL,
212 * we add another reference to the node that failed and set
213 * cursor->deadlk_node so hammer_done_cursor() can block on it.
216 hammer_cursor_upgrade(hammer_cursor_t cursor)
220 error = hammer_lock_upgrade(&cursor->node->lock);
221 if (error && cursor->deadlk_node == NULL) {
222 cursor->deadlk_node = cursor->node;
223 hammer_ref_node(cursor->deadlk_node);
224 } else if (error == 0 && cursor->parent) {
225 error = hammer_lock_upgrade(&cursor->parent->lock);
226 if (error && cursor->deadlk_node == NULL) {
227 cursor->deadlk_node = cursor->parent;
228 hammer_ref_node(cursor->deadlk_node);
235 hammer_cursor_upgrade_node(hammer_cursor_t cursor)
239 error = hammer_lock_upgrade(&cursor->node->lock);
240 if (error && cursor->deadlk_node == NULL) {
241 cursor->deadlk_node = cursor->node;
242 hammer_ref_node(cursor->deadlk_node);
248 * Downgrade cursor->node and cursor->parent to shared locks. This
249 * function can return EDEADLK.
252 hammer_cursor_downgrade(hammer_cursor_t cursor)
254 if (hammer_lock_excl_owned(&cursor->node->lock, curthread))
255 hammer_lock_downgrade(&cursor->node->lock);
256 if (cursor->parent &&
257 hammer_lock_excl_owned(&cursor->parent->lock, curthread)) {
258 hammer_lock_downgrade(&cursor->parent->lock);
263 * Seek the cursor to the specified node and index.
265 * The caller must ref the node prior to calling this routine and release
266 * it after it returns. If the seek succeeds the cursor will gain its own
270 hammer_cursor_seek(hammer_cursor_t cursor, hammer_node_t node, int index)
274 hammer_cursor_downgrade(cursor);
277 if (cursor->node != node) {
278 hammer_unlock(&cursor->node->lock);
279 hammer_rel_node(cursor->node);
281 hammer_ref_node(node);
282 hammer_lock_sh(&node->lock);
283 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
285 if (cursor->parent) {
286 hammer_unlock(&cursor->parent->lock);
287 hammer_rel_node(cursor->parent);
288 cursor->parent = NULL;
289 cursor->parent_index = 0;
291 error = hammer_load_cursor_parent(cursor, 0);
293 cursor->index = index;
298 * Load the parent of cursor->node into cursor->parent.
302 hammer_load_cursor_parent(hammer_cursor_t cursor, int try_exclusive)
305 hammer_node_t parent;
307 hammer_btree_elm_t elm;
311 hmp = cursor->trans->hmp;
313 if (cursor->node->ondisk->parent) {
315 parent = hammer_btree_get_parent(cursor->trans, node,
317 &error, try_exclusive);
319 elm = &parent->ondisk->elms[parent_index];
320 cursor->parent = parent;
321 cursor->parent_index = parent_index;
322 cursor->left_bound = &elm[0].internal.base;
323 cursor->right_bound = &elm[1].internal.base;
326 cursor->parent = NULL;
327 cursor->parent_index = 0;
328 cursor->left_bound = &hmp->root_btree_beg;
329 cursor->right_bound = &hmp->root_btree_end;
336 * Cursor up to our parent node. Return ENOENT if we are at the root of
340 hammer_cursor_up(hammer_cursor_t cursor)
344 hammer_cursor_downgrade(cursor);
347 * If the parent is NULL we are at the root of the B-Tree and
350 if (cursor->parent == NULL)
354 * Set the node to its parent.
356 hammer_unlock(&cursor->node->lock);
357 hammer_rel_node(cursor->node);
358 cursor->node = cursor->parent;
359 cursor->index = cursor->parent_index;
360 cursor->parent = NULL;
361 cursor->parent_index = 0;
363 error = hammer_load_cursor_parent(cursor, 0);
368 * Special cursor up given a locked cursor. The orignal node is not
369 * unlocked or released and the cursor is not downgraded.
371 * This function will recover from deadlocks. EDEADLK cannot be returned.
374 hammer_cursor_up_locked(hammer_cursor_t cursor)
380 * If the parent is NULL we are at the root of the B-Tree and
383 if (cursor->parent == NULL)
389 * Set the node to its parent.
391 cursor->node = cursor->parent;
392 cursor->index = cursor->parent_index;
393 cursor->parent = NULL;
394 cursor->parent_index = 0;
397 * load the new parent, attempt to exclusively lock it. Note that
398 * we are still holding the old parent (now cursor->node) exclusively
399 * locked. This can return EDEADLK.
401 error = hammer_load_cursor_parent(cursor, 1);
403 cursor->parent = cursor->node;
404 cursor->parent_index = cursor->index;
413 * Cursor down through the current node, which must be an internal node.
415 * This routine adjusts the cursor and sets index to 0.
418 hammer_cursor_down(hammer_cursor_t cursor)
421 hammer_btree_elm_t elm;
425 * The current node becomes the current parent
427 hammer_cursor_downgrade(cursor);
429 KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
430 if (cursor->parent) {
431 hammer_unlock(&cursor->parent->lock);
432 hammer_rel_node(cursor->parent);
434 cursor->parent = node;
435 cursor->parent_index = cursor->index;
440 * Extract element to push into at (node,index), set bounds.
442 elm = &node->ondisk->elms[cursor->parent_index];
445 * Ok, push down into elm. If elm specifies an internal or leaf
446 * node the current node must be an internal node. If elm specifies
447 * a spike then the current node must be a leaf node.
449 switch(elm->base.btype) {
450 case HAMMER_BTREE_TYPE_INTERNAL:
451 case HAMMER_BTREE_TYPE_LEAF:
452 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
453 KKASSERT(elm->internal.subtree_offset != 0);
454 cursor->left_bound = &elm[0].internal.base;
455 cursor->right_bound = &elm[1].internal.base;
456 node = hammer_get_node(cursor->trans,
457 elm->internal.subtree_offset, 0, &error);
459 KASSERT(elm->base.btype == node->ondisk->type, ("BTYPE MISMATCH %c %c NODE %p\n", elm->base.btype, node->ondisk->type, node));
460 if (node->ondisk->parent != cursor->parent->node_offset)
461 panic("node %p %016llx vs %016llx\n", node, node->ondisk->parent, cursor->parent->node_offset);
462 KKASSERT(node->ondisk->parent == cursor->parent->node_offset);
466 panic("hammer_cursor_down: illegal btype %02x (%c)\n",
468 (elm->base.btype ? elm->base.btype : '?'));
472 hammer_lock_sh(&node->lock);
473 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
480 /************************************************************************
481 * DEADLOCK RECOVERY *
482 ************************************************************************
484 * These are the new deadlock recovery functions. Currently they are only
485 * used for the mirror propagation and physical node removal cases but
486 * ultimately the intention is to use them for all deadlock recovery
490 hammer_unlock_cursor(hammer_cursor_t cursor)
494 KKASSERT((cursor->flags & HAMMER_CURSOR_TRACKED) == 0);
495 KKASSERT(cursor->node);
498 * Release the cursor's locks and track B-Tree operations on node.
499 * While being tracked our cursor can be modified by other threads
500 * and the node may be replaced.
502 if (cursor->parent) {
503 hammer_unlock(&cursor->parent->lock);
504 hammer_rel_node(cursor->parent);
505 cursor->parent = NULL;
508 cursor->flags |= HAMMER_CURSOR_TRACKED;
509 TAILQ_INSERT_TAIL(&node->cursor_list, cursor, deadlk_entry);
510 hammer_unlock(&node->lock);
514 * Get the cursor heated up again. The cursor's node may have
515 * changed and we might have to locate the new parent.
517 * If the exact element we were on got deleted RIPOUT will be
518 * set and we must clear ATEDISK so an iteration does not skip
519 * the element after it.
522 hammer_lock_cursor(hammer_cursor_t cursor)
527 KKASSERT(cursor->flags & HAMMER_CURSOR_TRACKED);
534 hammer_ref_node(node);
535 hammer_lock_sh(&node->lock);
536 if (cursor->node == node) {
537 hammer_rel_node(node);
540 hammer_unlock(&node->lock);
541 hammer_rel_node(node);
545 * Untrack the cursor, clean up, and re-establish the parent node.
547 TAILQ_REMOVE(&node->cursor_list, cursor, deadlk_entry);
548 cursor->flags &= ~HAMMER_CURSOR_TRACKED;
551 * If a ripout has occured iterations must re-test the (new)
552 * current element. Clearing ATEDISK prevents the element from
553 * being skipped and RETEST causes it to be re-tested.
555 if (cursor->flags & HAMMER_CURSOR_TRACKED_RIPOUT) {
556 cursor->flags &= ~HAMMER_CURSOR_TRACKED_RIPOUT;
557 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
558 cursor->flags |= HAMMER_CURSOR_RETEST;
560 error = hammer_load_cursor_parent(cursor, 0);
565 * Recover from a deadlocked cursor, tracking any node removals or
566 * replacements. If the cursor's current node is removed by another
567 * thread (via btree_remove()) the cursor will be seeked upwards.
569 * The caller is working a modifying operation and must be holding the
570 * sync lock (shared). We do not release the sync lock because this
571 * would break atomicy.
574 hammer_recover_cursor(hammer_cursor_t cursor)
578 hammer_unlock_cursor(cursor);
579 KKASSERT(cursor->trans->sync_lock_refs > 0);
582 * Wait for the deadlock to clear
584 if (cursor->deadlk_node) {
585 hammer_lock_ex_ident(&cursor->deadlk_node->lock, "hmrdlk");
586 hammer_unlock(&cursor->deadlk_node->lock);
587 hammer_rel_node(cursor->deadlk_node);
588 cursor->deadlk_node = NULL;
590 if (cursor->deadlk_rec) {
591 hammer_wait_mem_record_ident(cursor->deadlk_rec, "hmmdlr");
592 hammer_rel_mem_record(cursor->deadlk_rec);
593 cursor->deadlk_rec = NULL;
595 error = hammer_lock_cursor(cursor);
600 * Dup ocursor to ncursor. ncursor inherits ocursor's locks and ocursor
601 * is effectively unlocked and becomes tracked. If ocursor was not locked
602 * then ncursor also inherits the tracking.
604 * After the caller finishes working with ncursor it must be cleaned up
605 * with hammer_done_cursor(), and the caller must re-lock ocursor.
608 hammer_push_cursor(hammer_cursor_t ocursor)
610 hammer_cursor_t ncursor;
615 hmp = ocursor->trans->hmp;
616 ncursor = kmalloc(sizeof(*ncursor), hmp->m_misc, M_WAITOK | M_ZERO);
617 bcopy(ocursor, ncursor, sizeof(*ocursor));
619 node = ocursor->node;
620 hammer_ref_node(node);
621 if ((ocursor->flags & HAMMER_CURSOR_TRACKED) == 0) {
622 ocursor->flags |= HAMMER_CURSOR_TRACKED;
623 TAILQ_INSERT_TAIL(&node->cursor_list, ocursor, deadlk_entry);
626 ocursor->parent = NULL;
627 ocursor->data_buffer = NULL;
628 ocursor->leaf = NULL;
629 ocursor->data = NULL;
630 if (ncursor->flags & HAMMER_CURSOR_TRACKED)
631 TAILQ_INSERT_TAIL(&node->cursor_list, ncursor, deadlk_entry);
632 if ((ip = ncursor->ip) != NULL) {
633 ++ip->cursor_ip_refs;
636 hammer_ref(&ncursor->iprec->lock);
641 * Destroy ncursor and restore ocursor
643 * This is a temporary hack for the release. We can't afford to lose
644 * the IP lock until the IP object scan code is able to deal with it,
645 * so have ocursor inherit it back.
648 hammer_pop_cursor(hammer_cursor_t ocursor, hammer_cursor_t ncursor)
653 hmp = ncursor->trans->hmp;
657 --ip->cursor_ip_refs;
658 hammer_done_cursor(ncursor);
659 kfree(ncursor, hmp->m_misc);
660 KKASSERT(ocursor->ip == ip);
661 hammer_lock_cursor(ocursor);
665 * onode is being replaced by nnode by the reblocking code.
668 hammer_cursor_replaced_node(hammer_node_t onode, hammer_node_t nnode)
670 hammer_cursor_t cursor;
672 while ((cursor = TAILQ_FIRST(&onode->cursor_list)) != NULL) {
673 TAILQ_REMOVE(&onode->cursor_list, cursor, deadlk_entry);
674 TAILQ_INSERT_TAIL(&nnode->cursor_list, cursor, deadlk_entry);
675 KKASSERT(cursor->node == onode);
676 cursor->node = nnode;
677 hammer_ref_node(nnode);
678 hammer_rel_node(onode);
683 * node is being removed, cursors in deadlock recovery are seeked upward
687 hammer_cursor_removed_node(hammer_node_t node, hammer_node_t parent, int index)
689 hammer_cursor_t cursor;
691 KKASSERT(parent != NULL);
692 while ((cursor = TAILQ_FIRST(&node->cursor_list)) != NULL) {
693 KKASSERT(cursor->node == node);
694 KKASSERT(cursor->index == 0);
695 TAILQ_REMOVE(&node->cursor_list, cursor, deadlk_entry);
696 TAILQ_INSERT_TAIL(&parent->cursor_list, cursor, deadlk_entry);
697 cursor->flags |= HAMMER_CURSOR_TRACKED_RIPOUT;
698 cursor->node = parent;
699 cursor->index = index;
700 hammer_ref_node(parent);
701 hammer_rel_node(node);
706 * node was split at (onode, index) with elements >= index moved to nnode.
709 hammer_cursor_split_node(hammer_node_t onode, hammer_node_t nnode, int index)
711 hammer_cursor_t cursor;
714 TAILQ_FOREACH(cursor, &onode->cursor_list, deadlk_entry) {
715 KKASSERT(cursor->node == onode);
716 if (cursor->index < index)
718 TAILQ_REMOVE(&onode->cursor_list, cursor, deadlk_entry);
719 TAILQ_INSERT_TAIL(&nnode->cursor_list, cursor, deadlk_entry);
720 cursor->node = nnode;
721 cursor->index -= index;
722 hammer_ref_node(nnode);
723 hammer_rel_node(onode);
729 * Deleted element at (node, index)
731 * Shift indexes >= index
734 hammer_cursor_deleted_element(hammer_node_t node, int index)
736 hammer_cursor_t cursor;
738 TAILQ_FOREACH(cursor, &node->cursor_list, deadlk_entry) {
739 KKASSERT(cursor->node == node);
740 if (cursor->index == index) {
741 cursor->flags |= HAMMER_CURSOR_TRACKED_RIPOUT;
742 } else if (cursor->index > index) {
749 * Inserted element at (node, index)
751 * Shift indexes >= index
754 hammer_cursor_inserted_element(hammer_node_t node, int index)
756 hammer_cursor_t cursor;
758 TAILQ_FOREACH(cursor, &node->cursor_list, deadlk_entry) {
759 KKASSERT(cursor->node == node);
760 if (cursor->index >= index)