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.3 2007/11/20 22:55: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         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)
 377          */
 378         elm = &node->ondisk->elms[cursor->parent_index];
 379
 380         /*
 381          * Ok, push down into elm.  If rec_offset is non-zero this is
 382          * an inter-cluster push, otherwise it is a intra-cluster push.
 383          */
 384         if (elm->internal.rec_offset) {
 385                 vol_no = elm->internal.subtree_volno;
 386                 clu_no = elm->internal.subtree_cluid;
 387                 volume = hammer_get_volume(node->cluster->volume->hmp,
 388                                            vol_no, &error);
 389                 if (error)
 390                         return(error);
 391                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 392                 hammer_rel_volume(volume, 0);
 393                 if (error)
 394                         return(error);
 395                 node = hammer_get_node(cluster,
 396                                        cluster->ondisk->clu_btree_root,
 397                                        &error);
 398                 hammer_rel_cluster(cluster, 0);
 399         } else {
 400                 node = hammer_get_node(node->cluster,
 401                                        elm->internal.subtree_offset,
 402                                        &error);
 403         }
 404         if (error == 0) {
 405                 hammer_lock_ex(&node->lock);
 406                 cursor->node = node;
 407                 cursor->index = 0;
 408         }
 409         return(error);
 410 }
 411