HAMMER 13/many - Stabilization commit
[dragonfly.git] / sys / vfs / hammer / hammer_cursor.c
1 /*
2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
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  * 
34  * $DragonFly: src/sys/vfs/hammer/hammer_cursor.c,v 1.9 2007/12/31 05:33:12 dillon Exp $
35  */
36
37 /*
38  * HAMMER B-Tree index - cursor support routines
39  */
40 #include "hammer.h"
41
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);
45
46 /*
47  * Initialize a fresh cursor at the root of the filesystem hierarchy.
48  *
49  * cursor->parent will be NULL on return since we are loading the root
50  * node of the root cluster.
51  */
52 int
53 hammer_init_cursor_hmp(hammer_cursor_t cursor, hammer_mount_t hmp)
54 {
55         hammer_cluster_t cluster;
56         int error;
57
58         bzero(cursor, sizeof(*cursor));
59         cluster = hammer_get_root_cluster(hmp, &error);
60         if (error == 0) {
61                 cursor->node = hammer_get_node(cluster,
62                                                cluster->ondisk->clu_btree_root,
63                                                &error);
64                 hammer_rel_cluster(cluster, 0);
65                 if (error == 0)
66                         hammer_lock_ex(&cursor->node->lock);
67         }
68         if (error == 0)
69                 error = hammer_load_cursor_parent(cursor);
70         KKASSERT(error == 0);
71         return(error);
72 }
73
74 /*
75  * Initialize a fresh cursor at the root of the specified cluster and
76  * limit operations to within the cluster.
77  */
78 int
79 hammer_init_cursor_cluster(hammer_cursor_t cursor, hammer_cluster_t cluster)
80 {
81         int error;
82
83         bzero(cursor, sizeof(*cursor));
84         cursor->flags |= HAMMER_CURSOR_INCLUSTER;
85         cursor->node = hammer_get_node(cluster,
86                                        cluster->ondisk->clu_btree_root,
87                                        &error);
88         if (error == 0) {
89                 hammer_lock_ex(&cursor->node->lock);
90                 error = hammer_load_cursor_parent(cursor);
91         }
92         KKASSERT(error == 0);
93         return(error);
94 }
95
96 /*
97  * Initialize a fresh cursor using the B-Tree node cached by the
98  * in-memory inode.
99  */
100 int
101 hammer_init_cursor_ip(hammer_cursor_t cursor, hammer_inode_t ip)
102 {
103         hammer_node_t node;
104         int error;
105
106         if (ip->cache) {
107                 bzero(cursor, sizeof(*cursor));
108                 node = ip->cache;
109                 error = hammer_ref_node(node);
110                 if (error == 0) {
111                         hammer_lock_ex(&node->lock);
112                         cursor->node = node;
113                         error = hammer_load_cursor_parent(cursor);
114                 } else {
115                         node = NULL;
116                         cursor->node = node;
117                 }
118         } else {
119                 error = hammer_init_cursor_hmp(cursor, ip->hmp);
120         }
121         KKASSERT(error == 0);
122         return(error);
123 }
124
125 /*
126  * We are finished with a cursor.  We NULL out various fields as sanity
127  * check, in case the structure is inappropriately used afterwords.
128  */
129 void
130 hammer_done_cursor(hammer_cursor_t cursor)
131 {
132         if (cursor->parent) {
133                 hammer_unlock(&cursor->parent->lock);
134                 hammer_rel_node(cursor->parent);
135                 cursor->parent = NULL;
136         }
137         if (cursor->node) {
138                 hammer_unlock(&cursor->node->lock);
139                 hammer_rel_node(cursor->node);
140                 cursor->node = NULL;
141         }
142         if (cursor->data_buffer) {
143                 hammer_rel_buffer(cursor->data_buffer, 0);
144                 cursor->data_buffer = NULL;
145         }
146         if (cursor->record_buffer) {
147                 hammer_rel_buffer(cursor->record_buffer, 0);
148                 cursor->record_buffer = NULL;
149         }
150         if (cursor->ip)
151                 hammer_mem_done(cursor);
152
153         cursor->data = NULL;
154         cursor->record = NULL;
155         cursor->left_bound = NULL;
156         cursor->right_bound = NULL;
157 }
158
159 /*
160  * Acquire the parent B-Tree node of the specified node, returning a
161  * referenced but unlocked node.  NULL can be returned with *errorp == 0
162  * if node is the root node of the root cluster.
163  */
164 static
165 hammer_node_t
166 hammer_get_parent_node(hammer_node_t node, int *errorp)
167 {
168         hammer_cluster_t cluster;
169         hammer_node_t parent;
170
171         cluster = node->cluster;
172         if (node->ondisk->parent) {
173                 /*
174                  * Local parent
175                  */
176                 parent = hammer_get_node(cluster, node->ondisk->parent, errorp);
177         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
178                 /*
179                  * At cluster root, locate node in parent cluster
180                  */
181                 hammer_cluster_ondisk_t ondisk;
182                 hammer_cluster_t pcluster;
183                 hammer_volume_t pvolume;
184                 int32_t clu_no;
185                 int32_t vol_no;
186
187                 ondisk = cluster->ondisk;
188                 vol_no = ondisk->clu_btree_parent_vol_no;
189                 clu_no = ondisk->clu_btree_parent_clu_no;
190
191                 /*
192                  * Acquire the node from (volume, cluster, offset)
193                  */
194                 pvolume = hammer_get_volume(cluster->volume->hmp, vol_no,
195                                             errorp);
196                 if (*errorp)
197                         return (NULL);
198                 pcluster = hammer_get_cluster(pvolume, clu_no, errorp, 0);
199                 hammer_rel_volume(pvolume, 0);
200                 if (*errorp)
201                         return (NULL);
202                 parent = hammer_get_node(pcluster,
203                                          ondisk->clu_btree_parent_offset,
204                                          errorp);
205                 hammer_rel_cluster(pcluster, 0);
206         } else {
207                 /*
208                  * At root of root cluster, there is no parent.
209                  */
210                 KKASSERT(cluster->ondisk->clu_btree_parent_vol_no == -1);
211                 parent = NULL;
212                 *errorp = 0;
213         }
214         return(parent);
215 }
216
217 /*
218  * Load the parent of cursor->node into cursor->parent.  There are several
219  * cases.  (1) The parent is in the current cluster.  (2) We are at the
220  * root of the cluster and the parent is in another cluster.  (3) We are at
221  * the root of the root cluster.
222  *
223  * If HAMMER_CURSOR_INCLUSTER is set and we are at the root of the cluster,
224  * we do not access the parent cluster at all and make the cursor look like
225  * its at the root.
226  */
227 static
228 int
229 hammer_load_cursor_parent(hammer_cursor_t cursor)
230 {
231         hammer_cluster_t cluster;
232         int error;
233
234         cluster = cursor->node->cluster;
235
236         if (cursor->node->ondisk->parent) {
237                 error = hammer_load_cursor_parent_local(cursor);
238         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0 &&
239                    ((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0)
240         ) {
241                 error = hammer_load_cursor_parent_cluster(cursor);
242         } else {
243                 cursor->parent = NULL;
244                 cursor->parent_index = 0;
245                 cursor->left_bound = &cluster->ondisk->clu_btree_beg;
246                 cursor->right_bound = &cluster->ondisk->clu_btree_end;
247                 error = 0;
248         }
249         return(error);
250 }
251
252 static
253 int
254 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
255 {
256         hammer_node_t node;
257         hammer_node_t parent;
258         hammer_btree_elm_t elm;
259         int error;
260         int i;
261
262         node = cursor->node;
263         parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
264         if (error)
265                 return(error);
266         elm = NULL;
267         for (i = 0; i < parent->ondisk->count; ++i) {
268                 elm = &parent->ondisk->elms[i];
269                 if (parent->ondisk->elms[i].internal.subtree_offset ==
270                     node->node_offset) {
271                         break;
272                 }
273         }
274         if (i == parent->ondisk->count)
275                 panic("Bad B-Tree link: parent %p node %p\n", parent, node);
276         KKASSERT(i != parent->ondisk->count);
277         KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0);
278         cursor->parent = parent;
279         cursor->parent_index = i;
280         cursor->left_bound = &elm[0].internal.base;
281         cursor->right_bound = &elm[1].internal.base;
282
283         if (hammer_lock_ex_try(&parent->lock) != 0) {
284                 hammer_unlock(&cursor->node->lock);
285                 hammer_lock_ex(&parent->lock);
286                 hammer_lock_ex(&cursor->node->lock);
287                 /* XXX check node generation count */
288         }
289         return(error);
290 }
291
292 static
293 int
294 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
295 {
296         hammer_cluster_ondisk_t ondisk;
297         hammer_cluster_t pcluster;
298         hammer_cluster_t ccluster;
299         hammer_volume_t volume;
300         hammer_node_t node;
301         hammer_node_t parent;
302         hammer_btree_elm_t elm;
303         int32_t clu_no;
304         int32_t vol_no;
305         int error;
306         int i;
307
308         node = cursor->node;
309         ccluster = node->cluster;
310         ondisk = ccluster->ondisk;
311         vol_no = ondisk->clu_btree_parent_vol_no;
312         clu_no = ondisk->clu_btree_parent_clu_no;
313
314         /*
315          * Acquire the node from (volume, cluster, offset)
316          */
317         volume = hammer_get_volume(ccluster->volume->hmp, vol_no, &error);
318         if (error)
319                 return (error);
320         pcluster = hammer_get_cluster(volume, clu_no, &error, 0);
321         hammer_rel_volume(volume, 0);
322         if (error)
323                 return (error);
324         parent = hammer_get_node(pcluster, ondisk->clu_btree_parent_offset,
325                                  &error);
326         hammer_rel_cluster(pcluster, 0);
327         if (error)
328                 return (error);
329
330         /* 
331          * Ok, we have the node.  Locate the inter-cluster element
332          */
333         elm = NULL;
334         for (i = 0; i < parent->ondisk->count; ++i) {
335                 elm = &parent->ondisk->elms[i];
336                 if (elm->internal.rec_offset != 0 &&
337                     elm->internal.subtree_type == HAMMER_BTREE_TYPE_CLUSTER &&
338                     elm->internal.subtree_clu_no == cursor->node->cluster->clu_no) {
339                         break;
340                 }
341         }
342         KKASSERT(i != parent->ondisk->count);
343         cursor->parent = parent;
344         cursor->parent_index = i;
345         cursor->left_bound = &elm[0].internal.base;
346         cursor->right_bound = &elm[1].internal.base;
347
348         KKASSERT(hammer_btree_cmp(cursor->left_bound,
349                  &ccluster->ondisk->clu_btree_beg) <= 0);
350         KKASSERT(hammer_btree_cmp(cursor->right_bound,
351                  &ccluster->ondisk->clu_btree_end) >= 0);
352
353         if (hammer_lock_ex_try(&parent->lock) != 0) {
354                 hammer_unlock(&cursor->node->lock);
355                 hammer_lock_ex(&parent->lock);
356                 hammer_lock_ex(&cursor->node->lock);
357                 /* XXX check node generation count */
358         }
359         return(0);
360 }
361
362 /*
363  * Cursor up to our parent node.  Return ENOENT if we are at the root of
364  * the root cluster.
365  *
366  * If doing a nonblocking cursor-up and we are unable to acquire the lock,
367  * the cursor remains unchanged.
368  */
369 int
370 hammer_cursor_up(hammer_cursor_t cursor, int nonblock)
371 {
372         hammer_node_t save;
373         int error;
374
375         /*
376          * If asked to do this non-blocking acquire a lock on the parent
377          * now, before we mess with the cursor.
378          */
379         if (nonblock) {
380                 save = hammer_get_parent_node(cursor->parent, &error);
381                 if (error)
382                         return(error);
383                 if (save) {
384                         if (hammer_lock_ex_try(&save->lock) != 0) {
385                                 hammer_rel_node(save);
386                                 return(EAGAIN);
387                         }
388                 }
389         } else {
390                 save = NULL;
391         }
392
393         /*
394          * Set the node to its parent.  If the parent is NULL we are at
395          * the root of the root cluster and return ENOENT.
396          */
397         hammer_unlock(&cursor->node->lock);
398         hammer_rel_node(cursor->node);
399         cursor->node = cursor->parent;
400         cursor->index = cursor->parent_index;
401         cursor->parent = NULL;
402         cursor->parent_index = 0;
403
404         if (cursor->node == NULL) {
405                 error = ENOENT;
406         } else if ((cursor->flags & HAMMER_CURSOR_INCLUSTER) &&
407                    cursor->node->ondisk->parent == 0
408         ) {
409                 error = ENOENT;
410         } else {
411                 error = hammer_load_cursor_parent(cursor);
412         }
413         if (save) {
414                 hammer_unlock(&save->lock);
415                 hammer_rel_node(save);
416         }
417         return(error);
418 }
419
420 /*
421  * Set the cursor to the root of the current cursor's cluster.
422  */
423 int
424 hammer_cursor_toroot(hammer_cursor_t cursor)
425 {
426         hammer_cluster_t cluster;
427         int error;
428
429         /*
430          * Already at root of cluster?
431          */
432         if (cursor->node->ondisk->parent == 0) 
433                 return (0);
434
435         /*
436          * Parent is root of cluster?
437          */
438         if (cursor->parent->ondisk->parent == 0)
439                 return (hammer_cursor_up(cursor, 0));
440
441         /*
442          * Ok, reload the cursor with the root of the cluster, then
443          * locate its parent.
444          */
445         cluster = cursor->node->cluster;
446         error = hammer_ref_cluster(cluster);
447         if (error)
448                 return (error);
449
450         hammer_unlock(&cursor->parent->lock);
451         hammer_rel_node(cursor->parent);
452         hammer_unlock(&cursor->node->lock);
453         hammer_rel_node(cursor->node);
454         cursor->parent = NULL;
455         cursor->parent_index = 0;
456
457         cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
458                                        &error);
459         cursor->index = 0;
460         hammer_lock_ex(&cursor->node->lock);
461         hammer_rel_cluster(cluster, 0);
462         if (error == 0)
463                 error = hammer_load_cursor_parent(cursor);
464         return(error);
465 }
466
467 /*
468  * Cursor down through the current node, which must be an internal node.
469  *
470  * This routine adjusts the cursor and sets index to 0.
471  */
472 int
473 hammer_cursor_down(hammer_cursor_t cursor)
474 {
475         hammer_node_t node;
476         hammer_btree_elm_t elm;
477         hammer_volume_t volume;
478         hammer_cluster_t cluster;
479         int32_t vol_no;
480         int32_t clu_no;
481         int error;
482
483         /*
484          * The current node becomes the current parent
485          */
486         node = cursor->node;
487         KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
488         KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
489         if (cursor->parent) {
490                 hammer_unlock(&cursor->parent->lock);
491                 hammer_rel_node(cursor->parent);
492         }
493         cursor->parent = node;
494         cursor->parent_index = cursor->index;
495         cursor->node = NULL;
496         cursor->index = 0;
497
498         /*
499          * Extract element to push into at (node,index), set bounds.
500          */
501         elm = &node->ondisk->elms[cursor->parent_index];
502         cursor->left_bound = &elm[0].internal.base;
503         cursor->right_bound = &elm[1].internal.base;
504
505         /*
506          * Ok, push down into elm.  If rec_offset is non-zero this is
507          * an inter-cluster push, otherwise it is a intra-cluster push.
508          *
509          * Cursoring down through a cluster transition when the INCLUSTER
510          * flag is set is not legal.
511          */
512         if (elm->internal.rec_offset) {
513                 KKASSERT((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0);
514                 vol_no = elm->internal.subtree_vol_no;
515                 clu_no = elm->internal.subtree_clu_no;
516                 volume = hammer_get_volume(node->cluster->volume->hmp,
517                                            vol_no, &error);
518                 KKASSERT(error != EINVAL);
519                 if (error)
520                         return(error);
521                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
522                 KKASSERT(error != EINVAL);
523                 hammer_rel_volume(volume, 0);
524                 if (error)
525                         return(error);
526                 node = hammer_get_node(cluster,
527                                        cluster->ondisk->clu_btree_root,
528                                        &error);
529                 hammer_rel_cluster(cluster, 0);
530         } else {
531                 KKASSERT(elm->internal.subtree_offset != 0);
532                 node = hammer_get_node(node->cluster,
533                                        elm->internal.subtree_offset,
534                                        &error);
535                 if (error == 0) {
536                         KKASSERT(elm->internal.subtree_type == node->ondisk->type);
537                         if(node->ondisk->parent != cursor->parent->node_offset)
538                                 kprintf("node %p %d vs %d\n", node, node->ondisk->parent, cursor->parent->node_offset);
539                         KKASSERT(node->ondisk->parent == cursor->parent->node_offset);
540                 }
541         }
542         if (error == 0) {
543                 hammer_lock_ex(&node->lock);
544                 cursor->node = node;
545                 cursor->index = 0;
546         }
547         return(error);
548 }
549