HAMMER 7/many - deletions, overwrites, B-Tree work.
[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.4 2007/11/26 21:38:37 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         return(error);
71 }
72
73 /*
74  * Initialize a fresh cursor using the B-Tree node cached by the
75  * in-memory inode.
76  */
77 int
78 hammer_init_cursor_ip(hammer_cursor_t cursor, hammer_inode_t ip)
79 {
80         hammer_node_t node;
81         int error;
82
83         if (ip->cache) {
84                 bzero(cursor, sizeof(*cursor));
85                 node = ip->cache;
86                 error = hammer_ref_node(node);
87                 if (error == 0) {
88                         hammer_lock_ex(&node->lock);
89                         cursor->node = node;
90                         error = hammer_load_cursor_parent(cursor);
91                 } else {
92                         node = NULL;
93                         cursor->node = node;
94                 }
95         } else {
96                 error = hammer_init_cursor_hmp(cursor, ip->hmp);
97         }
98         return(error);
99 }
100
101 /*
102  * We are finished with a cursor.  We NULL out various fields as sanity
103  * check, in case the structure is inappropriately used afterwords.
104  */
105 void
106 hammer_done_cursor(hammer_cursor_t cursor)
107 {
108         if (cursor->parent) {
109                 hammer_unlock(&cursor->parent->lock);
110                 hammer_rel_node(cursor->parent);
111                 cursor->parent = NULL;
112         }
113         if (cursor->node) {
114                 hammer_unlock(&cursor->node->lock);
115                 hammer_rel_node(cursor->node);
116                 cursor->node = NULL;
117         }
118         if (cursor->data_buffer) {
119                 hammer_rel_buffer(cursor->data_buffer, 0);
120                 cursor->data_buffer = NULL;
121         }
122         if (cursor->record_buffer) {
123                 hammer_rel_buffer(cursor->record_buffer, 0);
124                 cursor->record_buffer = NULL;
125         }
126         if (cursor->ip)
127                 hammer_mem_done(cursor);
128
129         cursor->data = NULL;
130         cursor->record = NULL;
131         cursor->left_bound = NULL;
132         cursor->right_bound = NULL;
133 }
134
135 /*
136  * Load the parent of cursor->node into cursor->parent.  There are several
137  * cases.  (1) The parent is in the current cluster.  (2) We are at the
138  * root of the cluster and the parent is in another cluster.  (3) We are at
139  * the root of the root cluster.
140  */
141 static
142 int
143 hammer_load_cursor_parent(hammer_cursor_t cursor)
144 {
145         hammer_cluster_t cluster;
146         int error;
147
148         cluster = cursor->node->cluster;
149
150         if (cursor->node->ondisk->parent) {
151                 error = hammer_load_cursor_parent_local(cursor);
152         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
153                 error = hammer_load_cursor_parent_cluster(cursor);
154         } else {
155                 cursor->parent = NULL;
156                 cursor->parent_index = 0;
157                 cursor->left_bound = &cluster->ondisk->clu_btree_beg;
158                 cursor->right_bound = &cluster->ondisk->clu_btree_end;
159                 error = 0;
160         }
161         return(error);
162 }
163
164 static
165 int
166 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
167 {
168         hammer_node_t node;
169         hammer_node_t parent;
170         hammer_btree_elm_t elm;
171         int error;
172         int i;
173
174         node = cursor->node;
175         parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
176         if (error)
177                 return(error);
178         elm = NULL;
179         for (i = 0; i < parent->ondisk->count; ++i) {
180                 elm = &parent->ondisk->elms[i];
181                 if (parent->ondisk->elms[i].internal.subtree_offset ==
182                     node->node_offset) {
183                         break;
184                 }
185         }
186         KKASSERT(i != parent->ondisk->count);
187         KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0);
188         cursor->parent = parent;
189         cursor->parent_index = i;
190         cursor->left_bound = &elm[0].internal.base;
191         cursor->right_bound = &elm[1].internal.base;
192
193         if (hammer_lock_ex_try(&parent->lock) != 0) {
194                 hammer_unlock(&cursor->node->lock);
195                 hammer_lock_ex(&parent->lock);
196                 hammer_lock_ex(&cursor->node->lock);
197                 /* XXX check node generation count */
198         }
199         return(error);
200 }
201
202 static
203 int
204 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
205 {
206         hammer_cluster_ondisk_t ondisk;
207         hammer_cluster_t cluster;
208         hammer_volume_t volume;
209         hammer_node_t node;
210         hammer_node_t parent;
211         hammer_btree_elm_t elm;
212         int32_t clu_no;
213         int32_t vol_no;
214         int error;
215         int i;
216
217         node = cursor->node;
218         ondisk = node->cluster->ondisk;
219         vol_no = ondisk->clu_btree_parent_vol_no;
220         clu_no = ondisk->clu_btree_parent_clu_no;
221
222         /*
223          * Acquire the node from (volume, cluster, offset)
224          */
225         volume = hammer_get_volume(node->cluster->volume->hmp, vol_no, &error);
226         if (error)
227                 return (error);
228         cluster = hammer_get_cluster(volume, clu_no, &error, 0);
229         hammer_rel_volume(volume, 0);
230         if (error)
231                 return (error);
232         parent = hammer_get_node(cluster, ondisk->clu_btree_parent_offset,
233                                  &error);
234         hammer_rel_cluster(cluster, 0);
235         if (error)
236                 return (error);
237
238         /* 
239          * Ok, we have the node.  Locate the inter-cluster element
240          */
241         elm = NULL;
242         for (i = 0; i < parent->ondisk->count; ++i) {
243                 elm = &parent->ondisk->elms[i];
244                 if (elm->internal.rec_offset != 0 &&
245                     elm->internal.subtree_cluid == clu_no) {
246                         break;
247                 }
248         }
249         KKASSERT(i != parent->ondisk->count);
250         cursor->parent = parent;
251         cursor->parent_index = i;
252         cursor->left_bound = &elm[0].internal.base;
253         cursor->right_bound = &elm[1].internal.base;
254
255         KKASSERT(hammer_btree_cmp(cursor->left_bound,
256                  &parent->cluster->ondisk->clu_btree_beg) == 0);
257         KKASSERT(hammer_btree_cmp(cursor->right_bound,
258                  &parent->cluster->ondisk->clu_btree_end) == 0);
259
260         if (hammer_lock_ex_try(&parent->lock) != 0) {
261                 hammer_unlock(&cursor->node->lock);
262                 hammer_lock_ex(&parent->lock);
263                 hammer_lock_ex(&cursor->node->lock);
264                 /* XXX check node generation count */
265         }
266         return(0);
267 }
268
269
270 /*
271  * Cursor up to our parent node.  Return ENOENT if we are at the root of
272  * the root cluster.
273  */
274 int
275 hammer_cursor_up(hammer_cursor_t cursor)
276 {
277         int error;
278
279         /*
280          * Set the node to its parent.  If the parent is NULL we are at
281          * the root of the root cluster and return ENOENT.
282          */
283         hammer_unlock(&cursor->node->lock);
284         hammer_rel_node(cursor->node);
285         cursor->node = cursor->parent;
286         cursor->index = cursor->parent_index;
287         cursor->parent = NULL;
288         cursor->parent_index = 0;
289
290         if (cursor->node == NULL) {
291                 error = ENOENT;
292         } else {
293                 error = hammer_load_cursor_parent(cursor);
294         }
295         return(error);
296 }
297
298 /*
299  * Set the cursor to the root of the current cursor's cluster.
300  */
301 int
302 hammer_cursor_toroot(hammer_cursor_t cursor)
303 {
304         hammer_cluster_t cluster;
305         int error;
306
307         /*
308          * Already at root of cluster?
309          */
310         if (cursor->node->ondisk->parent == 0) 
311                 return (0);
312
313         /*
314          * Parent is root of cluster?
315          */
316         if (cursor->parent->ondisk->parent == 0)
317                 return (hammer_cursor_up(cursor));
318
319         /*
320          * Ok, reload the cursor with the root of the cluster, then
321          * locate its parent.
322          */
323         cluster = cursor->node->cluster;
324         error = hammer_ref_cluster(cluster);
325         if (error)
326                 return (error);
327
328         hammer_unlock(&cursor->parent->lock);
329         hammer_rel_node(cursor->parent);
330         hammer_unlock(&cursor->node->lock);
331         hammer_rel_node(cursor->node);
332         cursor->parent = NULL;
333         cursor->parent_index = 0;
334
335         cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
336                                        &error);
337         cursor->index = 0;
338         hammer_rel_cluster(cluster, 0);
339         if (error == 0)
340                 error = hammer_load_cursor_parent(cursor);
341         return(error);
342 }
343
344 /*
345  * Cursor down through the current node, which must be an internal node.
346  *
347  * This routine adjusts the cursor and sets index to 0.
348  */
349 int
350 hammer_cursor_down(hammer_cursor_t cursor)
351 {
352         hammer_node_t node;
353         hammer_btree_elm_t elm;
354         hammer_volume_t volume;
355         hammer_cluster_t cluster;
356         int32_t vol_no;
357         int32_t clu_no;
358         int error;
359
360         /*
361          * The current node becomes the current parent
362          */
363         node = cursor->node;
364         KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
365         KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
366         if (cursor->parent) {
367                 hammer_unlock(&cursor->parent->lock);
368                 hammer_rel_node(cursor->parent);
369         }
370         cursor->parent = node;
371         cursor->parent_index = cursor->index;
372         cursor->node = NULL;
373         cursor->index = 0;
374
375         /*
376          * Extract element to push into at (node,index), set bounds.
377          */
378         elm = &node->ondisk->elms[cursor->parent_index];
379         cursor->left_bound = &elm[0].internal.base;
380         cursor->right_bound = &elm[1].internal.base;
381
382         /*
383          * Ok, push down into elm.  If rec_offset is non-zero this is
384          * an inter-cluster push, otherwise it is a intra-cluster push.
385          */
386         if (elm->internal.rec_offset) {
387                 vol_no = elm->internal.subtree_volno;
388                 clu_no = elm->internal.subtree_cluid;
389                 volume = hammer_get_volume(node->cluster->volume->hmp,
390                                            vol_no, &error);
391                 if (error)
392                         return(error);
393                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
394                 hammer_rel_volume(volume, 0);
395                 if (error)
396                         return(error);
397                 node = hammer_get_node(cluster,
398                                        cluster->ondisk->clu_btree_root,
399                                        &error);
400                 hammer_rel_cluster(cluster, 0);
401         } else {
402                 node = hammer_get_node(node->cluster,
403                                        elm->internal.subtree_offset,
404                                        &error);
405         }
406         if (error == 0) {
407                 hammer_lock_ex(&node->lock);
408                 cursor->node = node;
409                 cursor->index = 0;
410         }
411         return(error);
412 }
413