HAMMER 59A/Many: Mirroring related work (and one bug fix).
[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 *
c82af904 34 * $DragonFly: src/sys/vfs/hammer/hammer_cursor.c,v 1.33 2008/06/26 04:06:22 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) {
6b4f890b 175 hammer_mem_done(cursor);
4e17f465
MD
176 KKASSERT(ip->cursor_ip_refs > 0);
177 --ip->cursor_ip_refs;
178 hammer_unlock(&ip->lock);
179 cursor->ip = NULL;
180 }
181
a89aec1b 182
6a37e7e4
MD
183 /*
184 * If we deadlocked this node will be referenced. Do a quick
185 * lock/unlock to wait for the deadlock condition to clear.
186 */
187 if (cursor->deadlk_node) {
af209b0f 188 hammer_lock_ex_ident(&cursor->deadlk_node->lock, "hmrdlk");
6a37e7e4
MD
189 hammer_unlock(&cursor->deadlk_node->lock);
190 hammer_rel_node(cursor->deadlk_node);
191 cursor->deadlk_node = NULL;
192 }
b84de5af 193 if (cursor->deadlk_rec) {
a99b9ea2 194 hammer_wait_mem_record_ident(cursor->deadlk_rec, "hmmdlr");
b84de5af
MD
195 hammer_rel_mem_record(cursor->deadlk_rec);
196 cursor->deadlk_rec = NULL;
197 }
6a37e7e4 198
40043e7f 199 cursor->data = NULL;
11ad5ade 200 cursor->leaf = NULL;
8cd0a023
MD
201 cursor->left_bound = NULL;
202 cursor->right_bound = NULL;
36f82b23 203 cursor->trans = NULL;
8cd0a023
MD
204}
205
6a37e7e4
MD
206/*
207 * Upgrade cursor->node and cursor->parent to exclusive locks. This
208 * function can return EDEADLK.
209 *
7aa3b8a6
MD
210 * The lock must already be either held shared or already held exclusively
211 * by us.
212 *
6a37e7e4
MD
213 * If we fail to upgrade the lock and cursor->deadlk_node is NULL,
214 * we add another reference to the node that failed and set
215 * cursor->deadlk_node so hammer_done_cursor() can block on it.
216 */
217int
218hammer_cursor_upgrade(hammer_cursor_t cursor)
219{
220 int error;
221
7aa3b8a6
MD
222 error = hammer_lock_upgrade(&cursor->node->lock);
223 if (error && cursor->deadlk_node == NULL) {
224 cursor->deadlk_node = cursor->node;
225 hammer_ref_node(cursor->deadlk_node);
226 } else if (error == 0 && cursor->parent) {
6a37e7e4
MD
227 error = hammer_lock_upgrade(&cursor->parent->lock);
228 if (error && cursor->deadlk_node == NULL) {
229 cursor->deadlk_node = cursor->parent;
230 hammer_ref_node(cursor->deadlk_node);
231 }
6a37e7e4
MD
232 }
233 return(error);
234}
235
7bc5b8c2
MD
236int
237hammer_cursor_upgrade_node(hammer_cursor_t cursor)
238{
239 int error;
240
241 error = hammer_lock_upgrade(&cursor->node->lock);
242 if (error && cursor->deadlk_node == NULL) {
243 cursor->deadlk_node = cursor->node;
244 hammer_ref_node(cursor->deadlk_node);
245 }
246 return(error);
247}
248
6a37e7e4
MD
249/*
250 * Downgrade cursor->node and cursor->parent to shared locks. This
251 * function can return EDEADLK.
252 */
253void
254hammer_cursor_downgrade(hammer_cursor_t cursor)
255{
7aa3b8a6 256 if (hammer_lock_excl_owned(&cursor->node->lock, curthread))
6a37e7e4 257 hammer_lock_downgrade(&cursor->node->lock);
7aa3b8a6
MD
258 if (cursor->parent &&
259 hammer_lock_excl_owned(&cursor->parent->lock, curthread)) {
6a37e7e4 260 hammer_lock_downgrade(&cursor->parent->lock);
7aa3b8a6 261 }
6a37e7e4
MD
262}
263
32c90105
MD
264/*
265 * Seek the cursor to the specified node and index.
cb51be26
MD
266 *
267 * The caller must ref the node prior to calling this routine and release
268 * it after it returns. If the seek succeeds the cursor will gain its own
269 * ref on the node.
32c90105
MD
270 */
271int
272hammer_cursor_seek(hammer_cursor_t cursor, hammer_node_t node, int index)
273{
274 int error;
275
276 hammer_cursor_downgrade(cursor);
277 error = 0;
278
279 if (cursor->node != node) {
280 hammer_unlock(&cursor->node->lock);
281 hammer_rel_node(cursor->node);
282 cursor->node = node;
32c90105
MD
283 hammer_ref_node(node);
284 hammer_lock_sh(&node->lock);
f36a9737 285 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
32c90105
MD
286
287 if (cursor->parent) {
288 hammer_unlock(&cursor->parent->lock);
289 hammer_rel_node(cursor->parent);
290 cursor->parent = NULL;
291 cursor->parent_index = 0;
292 }
f36a9737 293 error = hammer_load_cursor_parent(cursor, 0);
32c90105 294 }
a84a197d 295 cursor->index = index;
32c90105
MD
296 return (error);
297}
6a37e7e4 298
195c19a1 299/*
47197d71 300 * Load the parent of cursor->node into cursor->parent.
8cd0a023
MD
301 */
302static
303int
f36a9737 304hammer_load_cursor_parent(hammer_cursor_t cursor, int try_exclusive)
8cd0a023 305{
47197d71
MD
306 hammer_mount_t hmp;
307 hammer_node_t parent;
308 hammer_node_t node;
309 hammer_btree_elm_t elm;
8cd0a023 310 int error;
c82af904 311 int parent_index;
8cd0a023 312
36f82b23 313 hmp = cursor->trans->hmp;
8cd0a023
MD
314
315 if (cursor->node->ondisk->parent) {
47197d71 316 node = cursor->node;
c82af904
MD
317 parent = hammer_btree_get_parent(node, &parent_index,
318 &error, try_exclusive);
319 if (error == 0) {
320 elm = &parent->ondisk->elms[parent_index];
321 cursor->parent = parent;
322 cursor->parent_index = parent_index;
323 cursor->left_bound = &elm[0].internal.base;
324 cursor->right_bound = &elm[1].internal.base;
a84a197d 325 }
8cd0a023
MD
326 } else {
327 cursor->parent = NULL;
328 cursor->parent_index = 0;
47197d71
MD
329 cursor->left_bound = &hmp->root_btree_beg;
330 cursor->right_bound = &hmp->root_btree_end;
8cd0a023
MD
331 error = 0;
332 }
333 return(error);
334}
335
8cd0a023
MD
336/*
337 * Cursor up to our parent node. Return ENOENT if we are at the root of
47197d71 338 * the filesystem.
8cd0a023
MD
339 */
340int
6a37e7e4 341hammer_cursor_up(hammer_cursor_t cursor)
8cd0a023
MD
342{
343 int error;
344
6a37e7e4 345 hammer_cursor_downgrade(cursor);
195c19a1 346
8cd0a023 347 /*
4e17f465
MD
348 * If the parent is NULL we are at the root of the B-Tree and
349 * return ENOENT.
350 */
351 if (cursor->parent == NULL)
352 return (ENOENT);
353
354 /*
355 * Set the node to its parent.
8cd0a023
MD
356 */
357 hammer_unlock(&cursor->node->lock);
358 hammer_rel_node(cursor->node);
359 cursor->node = cursor->parent;
360 cursor->index = cursor->parent_index;
361 cursor->parent = NULL;
362 cursor->parent_index = 0;
363
f36a9737 364 error = hammer_load_cursor_parent(cursor, 0);
8cd0a023
MD
365 return(error);
366}
367
f36a9737
MD
368/*
369 * Special cursor up given a locked cursor. The orignal node is not
370 * unlocked and released and the cursor is not downgraded. If we are
371 * unable to acquire and lock the parent, EDEADLK is returned.
372 */
373int
374hammer_cursor_up_locked(hammer_cursor_t cursor)
375{
376 hammer_node_t save;
377 int error;
378
379 /*
380 * If the parent is NULL we are at the root of the B-Tree and
381 * return ENOENT.
382 */
383 if (cursor->parent == NULL)
384 return (ENOENT);
385
386 save = cursor->node;
387
388 /*
389 * Set the node to its parent.
390 */
391 cursor->node = cursor->parent;
392 cursor->index = cursor->parent_index;
393 cursor->parent = NULL;
394 cursor->parent_index = 0;
395
396 /*
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.
400 */
401 error = hammer_load_cursor_parent(cursor, 1);
402 if (error) {
403 cursor->parent = cursor->node;
404 cursor->parent_index = cursor->index;
405 cursor->node = save;
406 cursor->index = 0;
407 }
408 return(error);
409}
410
411
8cd0a023
MD
412/*
413 * Cursor down through the current node, which must be an internal node.
414 *
415 * This routine adjusts the cursor and sets index to 0.
416 */
417int
418hammer_cursor_down(hammer_cursor_t cursor)
419{
420 hammer_node_t node;
421 hammer_btree_elm_t elm;
8cd0a023
MD
422 int error;
423
424 /*
425 * The current node becomes the current parent
426 */
6a37e7e4 427 hammer_cursor_downgrade(cursor);
8cd0a023 428 node = cursor->node;
8cd0a023
MD
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);
433 }
434 cursor->parent = node;
435 cursor->parent_index = cursor->index;
436 cursor->node = NULL;
437 cursor->index = 0;
438
439 /*
76376933 440 * Extract element to push into at (node,index), set bounds.
8cd0a023
MD
441 */
442 elm = &node->ondisk->elms[cursor->parent_index];
443
444 /*
fe7678ee
MD
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.
8cd0a023 448 */
fe7678ee
MD
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;
36f82b23 456 node = hammer_get_node(cursor->trans->hmp,
19619882 457 elm->internal.subtree_offset, 0, &error);
fe7678ee 458 if (error == 0) {
40043e7f 459 KASSERT(elm->base.btype == node->ondisk->type, ("BTYPE MISMATCH %c %c NODE %p\n", elm->base.btype, node->ondisk->type, node));
b33e2cc0 460 if (node->ondisk->parent != cursor->parent->node_offset)
47197d71 461 panic("node %p %016llx vs %016llx\n", node, node->ondisk->parent, cursor->parent->node_offset);
fe7678ee
MD
462 KKASSERT(node->ondisk->parent == cursor->parent->node_offset);
463 }
464 break;
fe7678ee
MD
465 default:
466 panic("hammer_cursor_down: illegal btype %02x (%c)\n",
467 elm->base.btype,
468 (elm->base.btype ? elm->base.btype : '?'));
469 break;
8cd0a023
MD
470 }
471 if (error == 0) {
6a37e7e4 472 hammer_lock_sh(&node->lock);
f36a9737 473 KKASSERT ((node->flags & HAMMER_NODE_DELETED) == 0);
8cd0a023
MD
474 cursor->node = node;
475 cursor->index = 0;
476 }
477 return(error);
478}
479