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.1 2007/11/19 00:53:40 dillon Exp $
38 * HAMMER B-Tree index - cursor support routines
42 static int hammer_load_cursor_parent(hammer_cursor_t cursor);
43 static int hammer_load_cursor_parent_local(hammer_cursor_t cursor);
44 static int hammer_load_cursor_parent_cluster(hammer_cursor_t cursor);
47 * Initialize a fresh cursor at the root of the filesystem hierarchy.
49 * cursor->parent will be NULL on return since we are loading the root
50 * node of the root cluster.
53 hammer_init_cursor_hmp(hammer_cursor_t cursor, hammer_mount_t hmp)
55 hammer_cluster_t cluster;
58 bzero(cursor, sizeof(*cursor));
59 cluster = hammer_get_root_cluster(hmp, &error);
61 cursor->node = hammer_get_node(cluster,
62 cluster->ondisk->clu_btree_root,
64 hammer_rel_cluster(cluster, 0);
66 hammer_lock_ex(&cursor->node->lock);
69 error = hammer_load_cursor_parent(cursor);
74 * Initialize a fresh cursor using the B-Tree node cached by the
78 hammer_init_cursor_ip(hammer_cursor_t cursor, hammer_inode_t ip)
83 bzero(cursor, sizeof(*cursor));
84 cursor->node = ip->cache;
85 error = hammer_ref_node(cursor->node);
87 hammer_lock_ex(&cursor->node->lock);
88 error = hammer_load_cursor_parent(cursor);
90 hammer_rel_node(cursor->node);
94 error = hammer_init_cursor_hmp(cursor, ip->hmp);
100 * We are finished with a cursor. We NULL out various fields as sanity
101 * check, in case the structure is inappropriately used afterwords.
104 hammer_done_cursor(hammer_cursor_t cursor)
106 if (cursor->parent) {
107 hammer_unlock(&cursor->parent->lock);
108 hammer_rel_node(cursor->parent);
109 cursor->parent = NULL;
112 hammer_unlock(&cursor->node->lock);
113 hammer_rel_node(cursor->node);
116 if (cursor->data_buffer) {
117 hammer_rel_buffer(cursor->data_buffer, 0);
118 cursor->data_buffer = NULL;
120 if (cursor->record_buffer) {
121 hammer_rel_buffer(cursor->record_buffer, 0);
122 cursor->record_buffer = NULL;
125 cursor->record = NULL;
126 cursor->left_bound = NULL;
127 cursor->right_bound = NULL;
131 * Load the parent of cursor->node into cursor->parent. There are several
132 * cases. (1) The parent is in the current cluster. (2) We are at the
133 * root of the cluster and the parent is in another cluster. (3) We are at
134 * the root of the root cluster.
138 hammer_load_cursor_parent(hammer_cursor_t cursor)
140 hammer_cluster_t cluster;
143 cluster = cursor->node->cluster;
145 if (cursor->node->ondisk->parent) {
146 error = hammer_load_cursor_parent_local(cursor);
147 } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
148 error = hammer_load_cursor_parent_cluster(cursor);
150 cursor->parent = NULL;
151 cursor->parent_index = 0;
152 cursor->left_bound = &cluster->ondisk->clu_btree_beg;
153 cursor->right_bound = &cluster->ondisk->clu_btree_end;
161 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
164 hammer_node_t parent;
165 hammer_btree_elm_t elm;
170 parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
174 for (i = 0; i < parent->ondisk->count; ++i) {
175 elm = &parent->ondisk->elms[i];
176 if (parent->ondisk->elms[i].internal.subtree_offset ==
181 KKASSERT(i != parent->ondisk->count);
182 KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0);
183 cursor->parent = parent;
184 cursor->parent_index = i;
185 cursor->left_bound = &elm[0].internal.base;
186 cursor->right_bound = &elm[1].internal.base;
188 if (hammer_lock_ex_try(&parent->lock) != 0) {
189 hammer_unlock(&cursor->node->lock);
190 hammer_lock_ex(&parent->lock);
191 hammer_lock_ex(&cursor->node->lock);
192 /* XXX check node generation count */
199 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
201 hammer_cluster_ondisk_t ondisk;
202 hammer_cluster_t cluster;
203 hammer_volume_t volume;
205 hammer_node_t parent;
206 hammer_btree_elm_t elm;
213 ondisk = node->cluster->ondisk;
214 vol_no = ondisk->clu_btree_parent_vol_no;
215 clu_no = ondisk->clu_btree_parent_clu_no;
218 * Acquire the node from (volume, cluster, offset)
220 volume = hammer_get_volume(node->cluster->volume->hmp, vol_no, &error);
223 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
224 hammer_rel_volume(volume, 0);
227 parent = hammer_get_node(cluster, ondisk->clu_btree_parent_offset,
229 hammer_rel_cluster(cluster, 0);
234 * Ok, we have the node. Locate the inter-cluster element
237 for (i = 0; i < parent->ondisk->count; ++i) {
238 elm = &parent->ondisk->elms[i];
239 if (elm->internal.rec_offset != 0 &&
240 elm->internal.subtree_cluid == clu_no) {
244 KKASSERT(i != parent->ondisk->count);
245 cursor->parent = parent;
246 cursor->parent_index = i;
247 cursor->left_bound = &elm[0].internal.base;
248 cursor->right_bound = &elm[1].internal.base;
250 KKASSERT(hammer_btree_cmp(cursor->left_bound,
251 &parent->cluster->ondisk->clu_btree_beg) == 0);
252 KKASSERT(hammer_btree_cmp(cursor->right_bound,
253 &parent->cluster->ondisk->clu_btree_end) == 0);
255 if (hammer_lock_ex_try(&parent->lock) != 0) {
256 hammer_unlock(&cursor->node->lock);
257 hammer_lock_ex(&parent->lock);
258 hammer_lock_ex(&cursor->node->lock);
259 /* XXX check node generation count */
266 * Cursor up to our parent node. Return ENOENT if we are at the root of
270 hammer_cursor_up(hammer_cursor_t cursor)
275 * Set the node to its parent. If the parent is NULL we are at
276 * the root of the root cluster and return ENOENT.
278 hammer_unlock(&cursor->node->lock);
279 hammer_rel_node(cursor->node);
280 cursor->node = cursor->parent;
281 cursor->index = cursor->parent_index;
282 cursor->parent = NULL;
283 cursor->parent_index = 0;
285 if (cursor->node == NULL) {
288 error = hammer_load_cursor_parent(cursor);
294 * Set the cursor to the root of the current cursor's cluster.
297 hammer_cursor_toroot(hammer_cursor_t cursor)
299 hammer_cluster_t cluster;
303 * Already at root of cluster?
305 if (cursor->node->ondisk->parent == 0)
309 * Parent is root of cluster?
311 if (cursor->parent->ondisk->parent == 0)
312 return (hammer_cursor_up(cursor));
315 * Ok, reload the cursor with the root of the cluster, then
318 cluster = cursor->node->cluster;
319 error = hammer_ref_cluster(cluster);
323 hammer_unlock(&cursor->parent->lock);
324 hammer_rel_node(cursor->parent);
325 hammer_unlock(&cursor->node->lock);
326 hammer_rel_node(cursor->node);
327 cursor->parent = NULL;
328 cursor->parent_index = 0;
330 cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
333 hammer_rel_cluster(cluster, 0);
335 error = hammer_load_cursor_parent(cursor);
340 * Cursor down through the current node, which must be an internal node.
342 * This routine adjusts the cursor and sets index to 0.
345 hammer_cursor_down(hammer_cursor_t cursor)
348 hammer_btree_elm_t elm;
349 hammer_volume_t volume;
350 hammer_cluster_t cluster;
356 * The current node becomes the current parent
359 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
360 KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
361 if (cursor->parent) {
362 hammer_unlock(&cursor->parent->lock);
363 hammer_rel_node(cursor->parent);
365 cursor->parent = node;
366 cursor->parent_index = cursor->index;
371 * Extract element to push into at (node,index)
373 elm = &node->ondisk->elms[cursor->parent_index];
376 * Ok, push down into elm. If rec_offset is non-zero this is
377 * an inter-cluster push, otherwise it is a intra-cluster push.
379 if (elm->internal.rec_offset) {
380 vol_no = elm->internal.subtree_volno;
381 clu_no = elm->internal.subtree_cluid;
382 volume = hammer_get_volume(node->cluster->volume->hmp,
386 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
387 hammer_rel_volume(volume, 0);
390 node = hammer_get_node(cluster,
391 cluster->ondisk->clu_btree_root,
393 hammer_rel_cluster(cluster, 0);
395 node = hammer_get_node(node->cluster,
396 elm->internal.subtree_offset,
400 hammer_lock_ex(&node->lock);