2 * Copyright (c) 2007 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.18 2008/02/10 09:51:01 dillon Exp $
38 * HAMMER B-Tree index - cursor support routines
42 static int hammer_load_cursor_parent(hammer_cursor_t cursor
);
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_hmp(hammer_cursor_t cursor
, struct hammer_node
**cache
,
52 hammer_volume_t volume
;
56 bzero(cursor
, sizeof(*cursor
));
59 * Step 1 - acquire a locked node from the cache if possible
61 if (cache
&& *cache
) {
62 node
= hammer_ref_node_safe(hmp
, cache
, &error
);
64 hammer_lock_sh(&node
->lock
);
65 if (node
->flags
& HAMMER_NODE_DELETED
) {
66 hammer_unlock(&node
->lock
);
67 hammer_rel_node(node
);
76 * Step 2 - If we couldn't get a node from the cache, get
77 * the one from the root of the filesystem.
79 while (node
== NULL
) {
80 volume
= hammer_get_root_volume(hmp
, &error
);
83 node
= hammer_get_node(hmp
, volume
->ondisk
->vol0_btree_root
,
85 hammer_rel_volume(volume
, 0);
88 hammer_lock_sh(&node
->lock
);
89 if (node
->flags
& HAMMER_NODE_DELETED
) {
90 hammer_unlock(&node
->lock
);
91 hammer_rel_node(node
);
97 * Step 3 - finish initializing the cursor by acquiring the parent
101 error
= hammer_load_cursor_parent(cursor
);
102 KKASSERT(error
== 0);
107 * We are finished with a cursor. We NULL out various fields as sanity
108 * check, in case the structure is inappropriately used afterwords.
111 hammer_done_cursor(hammer_cursor_t cursor
)
113 if (cursor
->parent
) {
114 hammer_unlock(&cursor
->parent
->lock
);
115 hammer_rel_node(cursor
->parent
);
116 cursor
->parent
= NULL
;
119 hammer_unlock(&cursor
->node
->lock
);
120 hammer_rel_node(cursor
->node
);
123 if (cursor
->data_buffer
) {
124 hammer_rel_buffer(cursor
->data_buffer
, 0);
125 cursor
->data_buffer
= NULL
;
127 if (cursor
->record_buffer
) {
128 hammer_rel_buffer(cursor
->record_buffer
, 0);
129 cursor
->record_buffer
= NULL
;
132 hammer_mem_done(cursor
);
135 * If we deadlocked this node will be referenced. Do a quick
136 * lock/unlock to wait for the deadlock condition to clear.
138 if (cursor
->deadlk_node
) {
139 hammer_lock_ex(&cursor
->deadlk_node
->lock
);
140 hammer_unlock(&cursor
->deadlk_node
->lock
);
141 hammer_rel_node(cursor
->deadlk_node
);
142 cursor
->deadlk_node
= NULL
;
146 cursor
->record
= NULL
;
147 cursor
->left_bound
= NULL
;
148 cursor
->right_bound
= NULL
;
152 * Upgrade cursor->node and cursor->parent to exclusive locks. This
153 * function can return EDEADLK.
155 * If we fail to upgrade the lock and cursor->deadlk_node is NULL,
156 * we add another reference to the node that failed and set
157 * cursor->deadlk_node so hammer_done_cursor() can block on it.
160 hammer_cursor_upgrade(hammer_cursor_t cursor
)
164 if (hammer_lock_held(&cursor
->node
->lock
) < 0) {
165 error
= hammer_lock_upgrade(&cursor
->node
->lock
);
166 if (error
&& cursor
->deadlk_node
== NULL
) {
167 cursor
->deadlk_node
= cursor
->node
;
168 hammer_ref_node(cursor
->deadlk_node
);
173 if (cursor
->parent
&& hammer_lock_held(&cursor
->parent
->lock
) < 0) {
174 error
= hammer_lock_upgrade(&cursor
->parent
->lock
);
175 if (error
&& cursor
->deadlk_node
== NULL
) {
176 cursor
->deadlk_node
= cursor
->parent
;
177 hammer_ref_node(cursor
->deadlk_node
);
186 * Downgrade cursor->node and cursor->parent to shared locks. This
187 * function can return EDEADLK.
190 hammer_cursor_downgrade(hammer_cursor_t cursor
)
192 if (hammer_lock_held(&cursor
->node
->lock
) > 0)
193 hammer_lock_downgrade(&cursor
->node
->lock
);
194 if (cursor
->parent
&& hammer_lock_held(&cursor
->parent
->lock
) > 0)
195 hammer_lock_downgrade(&cursor
->parent
->lock
);
199 * Seek the cursor to the specified node and index.
202 hammer_cursor_seek(hammer_cursor_t cursor
, hammer_node_t node
, int index
)
206 hammer_cursor_downgrade(cursor
);
209 if (cursor
->node
!= node
) {
210 hammer_unlock(&cursor
->node
->lock
);
211 hammer_rel_node(cursor
->node
);
213 cursor
->index
= index
;
214 hammer_ref_node(node
);
215 hammer_lock_sh(&node
->lock
);
217 if (cursor
->parent
) {
218 hammer_unlock(&cursor
->parent
->lock
);
219 hammer_rel_node(cursor
->parent
);
220 cursor
->parent
= NULL
;
221 cursor
->parent_index
= 0;
223 error
= hammer_load_cursor_parent(cursor
);
229 * Load the parent of cursor->node into cursor->parent.
233 hammer_load_cursor_parent(hammer_cursor_t cursor
)
236 hammer_node_t parent
;
238 hammer_btree_elm_t elm
;
242 hmp
= cursor
->node
->hmp
;
244 if (cursor
->node
->ondisk
->parent
) {
246 parent
= hammer_get_node(node
->hmp
,
247 node
->ondisk
->parent
, &error
);
251 for (i
= 0; i
< parent
->ondisk
->count
; ++i
) {
252 elm
= &parent
->ondisk
->elms
[i
];
253 if (parent
->ondisk
->elms
[i
].internal
.subtree_offset
==
258 if (i
== parent
->ondisk
->count
)
259 panic("Bad B-Tree link: parent %p node %p\n", parent
, node
);
260 KKASSERT(i
!= parent
->ondisk
->count
);
261 cursor
->parent
= parent
;
262 cursor
->parent_index
= i
;
263 cursor
->left_bound
= &elm
[0].internal
.base
;
264 cursor
->right_bound
= &elm
[1].internal
.base
;
266 hammer_lock_sh(&parent
->lock
);
269 cursor
->parent
= NULL
;
270 cursor
->parent_index
= 0;
271 cursor
->left_bound
= &hmp
->root_btree_beg
;
272 cursor
->right_bound
= &hmp
->root_btree_end
;
279 * Cursor up to our parent node. Return ENOENT if we are at the root of
282 * If doing a nonblocking cursor-up and we are unable to acquire the lock,
283 * the cursor remains unchanged.
286 hammer_cursor_up(hammer_cursor_t cursor
)
290 hammer_cursor_downgrade(cursor
);
293 * Set the node to its parent. If the parent is NULL we are at
294 * the root of the filesystem and return ENOENT.
296 hammer_unlock(&cursor
->node
->lock
);
297 hammer_rel_node(cursor
->node
);
298 cursor
->node
= cursor
->parent
;
299 cursor
->index
= cursor
->parent_index
;
300 cursor
->parent
= NULL
;
301 cursor
->parent_index
= 0;
303 if (cursor
->node
== NULL
) {
306 error
= hammer_load_cursor_parent(cursor
);
312 * Cursor down through the current node, which must be an internal node.
314 * This routine adjusts the cursor and sets index to 0.
317 hammer_cursor_down(hammer_cursor_t cursor
)
320 hammer_btree_elm_t elm
;
324 * The current node becomes the current parent
326 hammer_cursor_downgrade(cursor
);
328 KKASSERT(cursor
->index
>= 0 && cursor
->index
< node
->ondisk
->count
);
329 if (cursor
->parent
) {
330 hammer_unlock(&cursor
->parent
->lock
);
331 hammer_rel_node(cursor
->parent
);
333 cursor
->parent
= node
;
334 cursor
->parent_index
= cursor
->index
;
339 * Extract element to push into at (node,index), set bounds.
341 elm
= &node
->ondisk
->elms
[cursor
->parent_index
];
344 * Ok, push down into elm. If elm specifies an internal or leaf
345 * node the current node must be an internal node. If elm specifies
346 * a spike then the current node must be a leaf node.
348 switch(elm
->base
.btype
) {
349 case HAMMER_BTREE_TYPE_INTERNAL
:
350 case HAMMER_BTREE_TYPE_LEAF
:
351 KKASSERT(node
->ondisk
->type
== HAMMER_BTREE_TYPE_INTERNAL
);
352 KKASSERT(elm
->internal
.subtree_offset
!= 0);
353 cursor
->left_bound
= &elm
[0].internal
.base
;
354 cursor
->right_bound
= &elm
[1].internal
.base
;
355 node
= hammer_get_node(node
->hmp
, elm
->internal
.subtree_offset
,
358 KASSERT(elm
->base
.btype
== node
->ondisk
->type
, ("BTYPE MISMATCH %c %c NODE %p\n", elm
->base
.btype
, node
->ondisk
->type
, node
));
359 if (node
->ondisk
->parent
!= cursor
->parent
->node_offset
)
360 panic("node %p %016llx vs %016llx\n", node
, node
->ondisk
->parent
, cursor
->parent
->node_offset
);
361 KKASSERT(node
->ondisk
->parent
== cursor
->parent
->node_offset
);
365 panic("hammer_cursor_down: illegal btype %02x (%c)\n",
367 (elm
->base
.btype
? elm
->base
.btype
: '?'));
371 hammer_lock_sh(&node
->lock
);