HAMMER 60C/many: Mirroring
[dragonfly.git] / sys / vfs / hammer / hammer_cursor.c
CommitLineData
8cd0a023 1/*
b84de5af 2 * Copyright (c) 2007-2008 The DragonFly Project. All rights reserved.
8cd0a023
MD
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
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
16 * distribution.
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.
20 *
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
32 * SUCH DAMAGE.
33 *
602c6cb8 34 * $DragonFly: src/sys/vfs/hammer/hammer_cursor.c,v 1.36 2008/07/04 07:25:36 dillon Exp $
8cd0a023
MD
35 */
36
37/*
38 * HAMMER B-Tree index - cursor support routines
39 */
40#include "hammer.h"
41
f36a9737 42static int hammer_load_cursor_parent(hammer_cursor_t cursor, int try_exclusive);
8cd0a023
MD
43
44/*
61aeeb33 45 * Initialize a fresh cursor using the B-Tree node cache. If the cache
47197d71 46 * is not available initialize a fresh cursor at the root of the filesystem.
8cd0a023
MD
47 */
48int
36f82b23 49hammer_init_cursor(hammer_transaction_t trans, hammer_cursor_t cursor,
bcac4bbb 50 hammer_node_cache_t cache, hammer_inode_t ip)
8cd0a023 51{
47197d71 52 hammer_volume_t volume;
61aeeb33 53 hammer_node_t node;
8cd0a023
MD
54 int error;
55
56 bzero(cursor, sizeof(*cursor));
61aeeb33 57
36f82b23
MD
58 cursor->trans = trans;
59
4e17f465
MD
60 /*
61 * If the cursor operation is on behalf of an inode, lock
62 * the inode.
63 */
64 if ((cursor->ip = ip) != NULL) {
65 ++ip->cursor_ip_refs;
66 if (trans->type == HAMMER_TRANS_FLS)
67 hammer_lock_ex(&ip->lock);
68 else
69 hammer_lock_sh(&ip->lock);
70 }
71
61aeeb33
MD
72 /*
73 * Step 1 - acquire a locked node from the cache if possible
74 */
bcac4bbb 75 if (cache && cache->node) {
36f82b23 76 node = hammer_ref_node_safe(trans->hmp, cache, &error);
61aeeb33 77 if (error == 0) {
4a2796f3 78 hammer_lock_sh_lowpri(&node->lock);
61aeeb33
MD
79 if (node->flags & HAMMER_NODE_DELETED) {
80 hammer_unlock(&node->lock);
81 hammer_rel_node(node);
82 node = NULL;
83 }
61aeeb33
MD
84 }
85 } else {
86 node = NULL;
87 }
88
89 /*
90 * Step 2 - If we couldn't get a node from the cache, get
47197d71 91 * the one from the root of the filesystem.
61aeeb33
MD
92 */
93 while (node == NULL) {
36f82b23 94 volume = hammer_get_root_volume(trans->hmp, &error);
61aeeb33
MD
95 if (error)
96 break;
36f82b23 97 node = hammer_get_node(trans->hmp,
19619882
MD
98 volume->ondisk->vol0_btree_root,
99 0, &error);
47197d71 100 hammer_rel_volume(volume, 0);
61aeeb33
MD
101 if (error)
102 break;
4a2796f3 103 hammer_lock_sh_lowpri(&node->lock);
11ad5ade
MD
104
105 /*
106 * If someone got in before we could lock the node, retry.
107 */
61aeeb33
MD
108 if (node->flags & HAMMER_NODE_DELETED) {
109 hammer_unlock(&node->lock);
110 hammer_rel_node(node);
111 node = NULL;
11ad5ade
MD
112 continue;
113 }
114 if (volume->ondisk->vol0_btree_root != node->node_offset) {
115 hammer_unlock(&node->lock);
116 hammer_rel_node(node);
117 node = NULL;
118 continue;
61aeeb33 119 }
8cd0a023 120 }
61aeeb33
MD
121
122 /*
123 * Step 3 - finish initializing the cursor by acquiring the parent
124 */
125 cursor->node = node;
8cd0a023 126 if (error == 0)
f36a9737 127 error = hammer_load_cursor_parent(cursor, 0);
0b075555 128 KKASSERT(error == 0);
a84a197d 129 /* if (error) hammer_done_cursor(cursor); */
8cd0a023
MD
130 return(error);
131}
132
4e17f465
MD
133/*
134 * Normalize a cursor. Sometimes cursors can be left in a state
135 * where node is NULL. If the cursor is in this state, cursor up.
136 */
137void
138hammer_normalize_cursor(hammer_cursor_t cursor)
139{
140 if (cursor->node == NULL) {
141 KKASSERT(cursor->parent != NULL);
142 hammer_cursor_up(cursor);
143 }
144}
145
146
8cd0a023
MD
147/*
148 * We are finished with a cursor. We NULL out various fields as sanity
149 * check, in case the structure is inappropriately used afterwords.
150 */
151void
152hammer_done_cursor(hammer_cursor_t cursor)
153{
4e17f465
MD
154 hammer_inode_t ip;
155
8cd0a023
MD
156 if (cursor->parent) {
157 hammer_unlock(&cursor->parent->lock);
158 hammer_rel_node(cursor->parent);
159 cursor->parent = NULL;
160 }
161 if (cursor->node) {
162 hammer_unlock(&cursor->node->lock);
163 hammer_rel_node(cursor->node);
164 cursor->node = NULL;
165 }
166 if (cursor->data_buffer) {
167 hammer_rel_buffer(cursor->data_buffer, 0);
168 cursor->data_buffer = NULL;
169 }
170 if (cursor->record_buffer) {
171 hammer_rel_buffer(cursor->record_buffer, 0);
172 cursor->record_buffer = NULL;
173 }
4e17f465 174 if ((ip = cursor->ip) != NULL) {
602c6cb8
MD
175 if (cursor->iprec) {
176 hammer_rel_mem_record(cursor->iprec);
177 cursor->iprec = NULL;
178 }
4e17f465
MD
179 KKASSERT(ip->cursor_ip_refs > 0);
180 --ip->cursor_ip_refs;
181 hammer_unlock(&ip->lock);
182 cursor->ip = NULL;
183 }
184
a89aec1b 185
6a37e7e4
MD
186 /*
187 * If we deadlocked this node will be referenced. Do a quick
188 * lock/unlock to wait for the deadlock condition to clear.
189 */
190 if (cursor->deadlk_node) {
af209b0f 191 hammer_lock_ex_ident(&cursor->deadlk_node->lock, "hmrdlk");
6a37e7e4
MD
192 hammer_unlock(&cursor->deadlk_node->lock);
193 hammer_rel_node(cursor->deadlk_node);
194 cursor->deadlk_node = NULL;
195 }
b84de5af 196 if (cursor->deadlk_rec) {
a99b9ea2 197 hammer_wait_mem_record_ident(cursor->deadlk_rec, "hmmdlr");
b84de5af
MD
198 hammer_rel_mem_record(cursor->deadlk_rec);
199 cursor->deadlk_rec = NULL;
200 }
6a37e7e4 201
40043e7f 202 cursor->data = NULL;
11ad5ade 203 cursor->leaf = NULL;
8cd0a023
MD
204 cursor->left_bound = NULL;
205 cursor->right_bound = NULL;
36f82b23 206 cursor->trans = NULL;
8cd0a023
MD
207}
208
6a37e7e4
MD
209/*
210 * Upgrade cursor->node and cursor->parent to exclusive locks. This
211 * function can return EDEADLK.
212 *
7aa3b8a6
MD
213 * The lock must already be either held shared or already held exclusively
214 * by us.
215 *
6a37e7e4
MD
216 * If we fail to upgrade the lock and cursor->deadlk_node is NULL,
217 * we add another reference to the node that failed and set
218 * cursor->deadlk_node so hammer_done_cursor() can block on it.
219 */
220int
221hammer_cursor_upgrade(hammer_cursor_t cursor)
222{
223 int error;
224
7aa3b8a6
MD
225 error = hammer_lock_upgrade(&cursor->node->lock);
226 if (error && cursor->deadlk_node == NULL) {
227 cursor->deadlk_node = cursor->node;
228 hammer_ref_node(cursor->deadlk_node);
229 } else if (error == 0 && cursor->parent) {
6a37e7e4
MD
230 error = hammer_lock_upgrade(&cursor->parent->lock);
231 if (error && cursor->deadlk_node == NULL) {
232 cursor->deadlk_node = cursor->parent;
233 hammer_ref_node(cursor->deadlk_node);
234 }
6a37e7e4
MD
235 }
236 return(error);
237}
238
7bc5b8c2
MD
239int
240hammer_cursor_upgrade_node(hammer_cursor_t cursor)
241{
242 int error;
243
244 error = hammer_lock_upgrade(&cursor->node->lock);
245 if (error && cursor->deadlk_node == NULL) {
246 cursor->deadlk_node = cursor->node;
247 hammer_ref_node(cursor->deadlk_node);
248 }
249 return(error);
250}
251
6a37e7e4
MD
252/*
253 * Downgrade cursor->node and cursor->parent to shared locks. This
254 * function can return EDEADLK.
255 */
256void
257hammer_cursor_downgrade(hammer_cursor_t cursor)
258{
7aa3b8a6 259 if (hammer_lock_excl_owned(&cursor->node->lock, curthread))
6a37e7e4 260 hammer_lock_downgrade(&cursor->node->lock);
7aa3b8a6
MD
261 if (cursor->parent &&
262 hammer_lock_excl_owned(&cursor->parent->lock, curthread)) {
6a37e7e4 263 hammer_lock_downgrade(&cursor->parent->lock);
7aa3b8a6 264 }
6a37e7e4
MD
265}
266
32c90105
MD
267/*
268 * Seek the cursor to the specified node and index.
cb51be26
MD
269 *
270 * The caller must ref the node prior to calling this routine and release
271 * it after it returns. If the seek succeeds the cursor will gain its own
272 * ref on the node.
32c90105
MD
273 */
274int
275hammer_cursor_seek(hammer_cursor_t cursor, hammer_node_t node, int index)
276{
277 int error;
278
279 hammer_cursor_downgrade(cursor);
280 error = 0;
281
282 if (cursor->node != node) {
283 hammer_unlock(&cursor->node->lock);
284 hammer_rel_node(cursor->node);
285 cursor->node = node;
32c90105
MD
286 hammer_ref_node(node);
287 hammer_lock_sh(&node->lock);
f36a9737 288 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
32c90105
MD
289
290 if (cursor->parent) {
291 hammer_unlock(&cursor->parent->lock);
292 hammer_rel_node(cursor->parent);
293 cursor->parent = NULL;
294 cursor->parent_index = 0;
295 }
f36a9737 296 error = hammer_load_cursor_parent(cursor, 0);
32c90105 297 }
a84a197d 298 cursor->index = index;
32c90105
MD
299 return (error);
300}
6a37e7e4 301
195c19a1 302/*
47197d71 303 * Load the parent of cursor->node into cursor->parent.
8cd0a023
MD
304 */
305static
306int
f36a9737 307hammer_load_cursor_parent(hammer_cursor_t cursor, int try_exclusive)
8cd0a023 308{
47197d71
MD
309 hammer_mount_t hmp;
310 hammer_node_t parent;
311 hammer_node_t node;
312 hammer_btree_elm_t elm;
8cd0a023 313 int error;
c82af904 314 int parent_index;
8cd0a023 315
36f82b23 316 hmp = cursor->trans->hmp;
8cd0a023
MD
317
318 if (cursor->node->ondisk->parent) {
47197d71 319 node = cursor->node;
c82af904
MD
320 parent = hammer_btree_get_parent(node, &parent_index,
321 &error, try_exclusive);
322 if (error == 0) {
323 elm = &parent->ondisk->elms[parent_index];
324 cursor->parent = parent;
325 cursor->parent_index = parent_index;
326 cursor->left_bound = &elm[0].internal.base;
327 cursor->right_bound = &elm[1].internal.base;
a84a197d 328 }
8cd0a023
MD
329 } else {
330 cursor->parent = NULL;
331 cursor->parent_index = 0;
47197d71
MD
332 cursor->left_bound = &hmp->root_btree_beg;
333 cursor->right_bound = &hmp->root_btree_end;
8cd0a023
MD
334 error = 0;
335 }
336 return(error);
337}
338
8cd0a023
MD
339/*
340 * Cursor up to our parent node. Return ENOENT if we are at the root of
47197d71 341 * the filesystem.
8cd0a023
MD
342 */
343int
6a37e7e4 344hammer_cursor_up(hammer_cursor_t cursor)
8cd0a023
MD
345{
346 int error;
347
6a37e7e4 348 hammer_cursor_downgrade(cursor);
195c19a1 349
8cd0a023 350 /*
4e17f465
MD
351 * If the parent is NULL we are at the root of the B-Tree and
352 * return ENOENT.
353 */
354 if (cursor->parent == NULL)
355 return (ENOENT);
356
357 /*
358 * Set the node to its parent.
8cd0a023
MD
359 */
360 hammer_unlock(&cursor->node->lock);
361 hammer_rel_node(cursor->node);
362 cursor->node = cursor->parent;
363 cursor->index = cursor->parent_index;
364 cursor->parent = NULL;
365 cursor->parent_index = 0;
366
f36a9737 367 error = hammer_load_cursor_parent(cursor, 0);
8cd0a023
MD
368 return(error);
369}
370
f36a9737
MD
371/*
372 * Special cursor up given a locked cursor. The orignal node is not
373 * unlocked and released and the cursor is not downgraded. If we are
374 * unable to acquire and lock the parent, EDEADLK is returned.
375 */
376int
377hammer_cursor_up_locked(hammer_cursor_t cursor)
378{
379 hammer_node_t save;
380 int error;
381
382 /*
383 * If the parent is NULL we are at the root of the B-Tree and
384 * return ENOENT.
385 */
386 if (cursor->parent == NULL)
387 return (ENOENT);
388
389 save = cursor->node;
390
391 /*
392 * Set the node to its parent.
393 */
394 cursor->node = cursor->parent;
395 cursor->index = cursor->parent_index;
396 cursor->parent = NULL;
397 cursor->parent_index = 0;
398
399 /*
400 * load the new parent, attempt to exclusively lock it. Note that
401 * we are still holding the old parent (now cursor->node) exclusively
402 * locked. This can return EDEADLK.
403 */
404 error = hammer_load_cursor_parent(cursor, 1);
405 if (error) {
406 cursor->parent = cursor->node;
407 cursor->parent_index = cursor->index;
408 cursor->node = save;
409 cursor->index = 0;
410 }
411 return(error);
412}
413
414
8cd0a023
MD
415/*
416 * Cursor down through the current node, which must be an internal node.
417 *
418 * This routine adjusts the cursor and sets index to 0.
419 */
420int
421hammer_cursor_down(hammer_cursor_t cursor)
422{
423 hammer_node_t node;
424 hammer_btree_elm_t elm;
8cd0a023
MD
425 int error;
426
427 /*
428 * The current node becomes the current parent
429 */
6a37e7e4 430 hammer_cursor_downgrade(cursor);
8cd0a023 431 node = cursor->node;
8cd0a023
MD
432 KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
433 if (cursor->parent) {
434 hammer_unlock(&cursor->parent->lock);
435 hammer_rel_node(cursor->parent);
436 }
437 cursor->parent = node;
438 cursor->parent_index = cursor->index;
439 cursor->node = NULL;
440 cursor->index = 0;
441
442 /*
76376933 443 * Extract element to push into at (node,index), set bounds.
8cd0a023
MD
444 */
445 elm = &node->ondisk->elms[cursor->parent_index];
446
447 /*
fe7678ee
MD
448 * Ok, push down into elm. If elm specifies an internal or leaf
449 * node the current node must be an internal node. If elm specifies
450 * a spike then the current node must be a leaf node.
8cd0a023 451 */
fe7678ee
MD
452 switch(elm->base.btype) {
453 case HAMMER_BTREE_TYPE_INTERNAL:
454 case HAMMER_BTREE_TYPE_LEAF:
455 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
456 KKASSERT(elm->internal.subtree_offset != 0);
457 cursor->left_bound = &elm[0].internal.base;
458 cursor->right_bound = &elm[1].internal.base;
36f82b23 459 node = hammer_get_node(cursor->trans->hmp,
19619882 460 elm->internal.subtree_offset, 0, &error);
fe7678ee 461 if (error == 0) {
40043e7f 462 KASSERT(elm->base.btype == node->ondisk->type, ("BTYPE MISMATCH %c %c NODE %p\n", elm->base.btype, node->ondisk->type, node));
b33e2cc0 463 if (node->ondisk->parent != cursor->parent->node_offset)
47197d71 464 panic("node %p %016llx vs %016llx\n", node, node->ondisk->parent, cursor->parent->node_offset);
fe7678ee
MD
465 KKASSERT(node->ondisk->parent == cursor->parent->node_offset);
466 }
467 break;
fe7678ee
MD
468 default:
469 panic("hammer_cursor_down: illegal btype %02x (%c)\n",
470 elm->base.btype,
471 (elm->base.btype ? elm->base.btype : '?'));
472 break;
8cd0a023
MD
473 }
474 if (error == 0) {
6a37e7e4 475 hammer_lock_sh(&node->lock);
f36a9737 476 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
8cd0a023
MD
477 cursor->node = node;
478 cursor->index = 0;
479 }
480 return(error);
481}
482