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.1 2007/11/19 00:53:40 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         int error;
  81
  82         if (ip->cache) {
  83                 bzero(cursor, sizeof(*cursor));
  84                 cursor->node = ip->cache;
  85                 error = hammer_ref_node(cursor->node);
  86                 if (error == 0) {
  87                         hammer_lock_ex(&cursor->node->lock);
  88                         error = hammer_load_cursor_parent(cursor);
  89                 } else {
  90                         hammer_rel_node(cursor->node);
  91                         cursor->node = NULL;
  92                 }
  93         } else {
  94                 error = hammer_init_cursor_hmp(cursor, ip->hmp);
  95         }
  96         return(error);
  97 }
  98
  99 /*
 100  * We are finished with a cursor.  We NULL out various fields as sanity
 101  * check, in case the structure is inappropriately used afterwords.
 102  */
 103 void
 104 hammer_done_cursor(hammer_cursor_t cursor)
 105 {
 106         if (cursor->parent) {
 107                 hammer_unlock(&cursor->parent->lock);
 108                 hammer_rel_node(cursor->parent);
 109                 cursor->parent = NULL;
 110         }
 111         if (cursor->node) {
 112                 hammer_unlock(&cursor->node->lock);
 113                 hammer_rel_node(cursor->node);
 114                 cursor->node = NULL;
 115         }
 116         if (cursor->data_buffer) {
 117                 hammer_rel_buffer(cursor->data_buffer, 0);
 118                 cursor->data_buffer = NULL;
 119         }
 120         if (cursor->record_buffer) {
 121                 hammer_rel_buffer(cursor->record_buffer, 0);
 122                 cursor->record_buffer = NULL;
 123         }
 124         cursor->data = NULL;
 125         cursor->record = NULL;
 126         cursor->left_bound = NULL;
 127         cursor->right_bound = NULL;
 128 }
 129
 130 /*
 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.
 135  */
 136 static
 137 int
 138 hammer_load_cursor_parent(hammer_cursor_t cursor)
 139 {
 140         hammer_cluster_t cluster;
 141         int error;
 142
 143         cluster = cursor->node->cluster;
 144
 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);
 149         } else {
 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;
 154                 error = 0;
 155         }
 156         return(error);
 157 }
 158
 159 static
 160 int
 161 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
 162 {
 163         hammer_node_t node;
 164         hammer_node_t parent;
 165         hammer_btree_elm_t elm;
 166         int error;
 167         int i;
 168
 169         node = cursor->node;
 170         parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
 171         if (error)
 172                 return(error);
 173         elm = NULL;
 174         for (i = 0; i < parent->ondisk->count; ++i) {
 175                 elm = &parent->ondisk->elms[i];
 176                 if (parent->ondisk->elms[i].internal.subtree_offset ==
 177                     node->node_offset) {
 178                         break;
 179                 }
 180         }
 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;
 187
 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 */
 193         }
 194         return(error);
 195 }
 196
 197 static
 198 int
 199 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
 200 {
 201         hammer_cluster_ondisk_t ondisk;
 202         hammer_cluster_t cluster;
 203         hammer_volume_t volume;
 204         hammer_node_t node;
 205         hammer_node_t parent;
 206         hammer_btree_elm_t elm;
 207         int32_t clu_no;
 208         int32_t vol_no;
 209         int error;
 210         int i;
 211
 212         node = cursor->node;
 213         ondisk = node->cluster->ondisk;
 214         vol_no = ondisk->clu_btree_parent_vol_no;
 215         clu_no = ondisk->clu_btree_parent_clu_no;
 216
 217         /*
 218          * Acquire the node from (volume, cluster, offset)
 219          */
 220         volume = hammer_get_volume(node->cluster->volume->hmp, vol_no, &error);
 221         if (error)
 222                 return (error);
 223         cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 224         hammer_rel_volume(volume, 0);
 225         if (error)
 226                 return (error);
 227         parent = hammer_get_node(cluster, ondisk->clu_btree_parent_offset,
 228                                  &error);
 229         hammer_rel_cluster(cluster, 0);
 230         if (error)
 231                 return (error);
 232
 233         /*
 234          * Ok, we have the node.  Locate the inter-cluster element
 235          */
 236         elm = NULL;
 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) {
 241                         break;
 242                 }
 243         }
 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;
 249
 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);
 254
 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 */
 260         }
 261         return(0);
 262 }
 263
 264
 265 /*
 266  * Cursor up to our parent node.  Return ENOENT if we are at the root of
 267  * the root cluster.
 268  */
 269 int
 270 hammer_cursor_up(hammer_cursor_t cursor)
 271 {
 272         int error;
 273
 274         /*
 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.
 277          */
 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;
 284
 285         if (cursor->node == NULL) {
 286                 error = ENOENT;
 287         } else {
 288                 error = hammer_load_cursor_parent(cursor);
 289         }
 290         return(error);
 291 }
 292
 293 /*
 294  * Set the cursor to the root of the current cursor's cluster.
 295  */
 296 int
 297 hammer_cursor_toroot(hammer_cursor_t cursor)
 298 {
 299         hammer_cluster_t cluster;
 300         int error;
 301
 302         /*
 303          * Already at root of cluster?
 304          */
 305         if (cursor->node->ondisk->parent == 0)
 306                 return (0);
 307
 308         /*
 309          * Parent is root of cluster?
 310          */
 311         if (cursor->parent->ondisk->parent == 0)
 312                 return (hammer_cursor_up(cursor));
 313
 314         /*
 315          * Ok, reload the cursor with the root of the cluster, then
 316          * locate its parent.
 317          */
 318         cluster = cursor->node->cluster;
 319         error = hammer_ref_cluster(cluster);
 320         if (error)
 321                 return (error);
 322
 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;
 329
 330         cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
 331                                        &error);
 332         cursor->index = 0;
 333         hammer_rel_cluster(cluster, 0);
 334         if (error == 0)
 335                 error = hammer_load_cursor_parent(cursor);
 336         return(error);
 337 }
 338
 339 /*
 340  * Cursor down through the current node, which must be an internal node.
 341  *
 342  * This routine adjusts the cursor and sets index to 0.
 343  */
 344 int
 345 hammer_cursor_down(hammer_cursor_t cursor)
 346 {
 347         hammer_node_t node;
 348         hammer_btree_elm_t elm;
 349         hammer_volume_t volume;
 350         hammer_cluster_t cluster;
 351         int32_t vol_no;
 352         int32_t clu_no;
 353         int error;
 354
 355         /*
 356          * The current node becomes the current parent
 357          */
 358         node = cursor->node;
 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);
 364         }
 365         cursor->parent = node;
 366         cursor->parent_index = cursor->index;
 367         cursor->node = NULL;
 368         cursor->index = 0;
 369
 370         /*
 371          * Extract element to push into at (node,index)
 372          */
 373         elm = &node->ondisk->elms[cursor->parent_index];
 374
 375         /*
 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.
 378          */
 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,
 383                                            vol_no, &error);
 384                 if (error)
 385                         return(error);
 386                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 387                 hammer_rel_volume(volume, 0);
 388                 if (error)
 389                         return(error);
 390                 node = hammer_get_node(cluster,
 391                                        cluster->ondisk->clu_btree_root,
 392                                        &error);
 393                 hammer_rel_cluster(cluster, 0);
 394         } else {
 395                 node = hammer_get_node(node->cluster,
 396                                        elm->internal.subtree_offset,
 397                                        &error);
 398         }
 399         if (error == 0) {
 400                 hammer_lock_ex(&node->lock);
 401                 cursor->node = node;
 402                 cursor->index = 0;
 403         }
 404         return(error);
 405 }
 406