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.5 2007/11/30 00:16:56 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  * Acquire the parent B-Tree node of the specified node, returning a
 137  * referenced but unlocked node.  NULL can be returned with *errorp == 0
 138  * if node is the root node of the root cluster.
 139  */
 140 static
 141 hammer_node_t
 142 hammer_get_parent_node(hammer_node_t node, int *errorp)
 143 {
 144         hammer_cluster_t cluster;
 145         hammer_node_t parent;
 146
 147         cluster = node->cluster;
 148         if (node->ondisk->parent) {
 149                 /*
 150                  * Local parent
 151                  */
 152                 parent = hammer_get_node(cluster, node->ondisk->parent, errorp);
 153         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
 154                 /*
 155                  * At cluster root, locate node in parent cluster
 156                  */
 157                 hammer_cluster_ondisk_t ondisk;
 158                 hammer_cluster_t pcluster;
 159                 hammer_volume_t pvolume;
 160                 int32_t clu_no;
 161                 int32_t vol_no;
 162
 163                 ondisk = cluster->ondisk;
 164                 vol_no = ondisk->clu_btree_parent_vol_no;
 165                 clu_no = ondisk->clu_btree_parent_clu_no;
 166
 167                 /*
 168                  * Acquire the node from (volume, cluster, offset)
 169                  */
 170                 pvolume = hammer_get_volume(cluster->volume->hmp, vol_no,
 171                                             errorp);
 172                 if (*errorp)
 173                         return (NULL);
 174                 pcluster = hammer_get_cluster(pvolume, clu_no, errorp, 0);
 175                 hammer_rel_volume(pvolume, 0);
 176                 if (*errorp)
 177                         return (NULL);
 178                 parent = hammer_get_node(pcluster,
 179                                          ondisk->clu_btree_parent_offset,
 180                                          errorp);
 181                 hammer_rel_cluster(pcluster, 0);
 182         } else {
 183                 /*
 184                  * At root of root cluster, there is no parent.
 185                  */
 186                 parent = NULL;
 187                 *errorp = 0;
 188         }
 189         return(parent);
 190 }
 191
 192 /*
 193  * Load the parent of cursor->node into cursor->parent.  There are several
 194  * cases.  (1) The parent is in the current cluster.  (2) We are at the
 195  * root of the cluster and the parent is in another cluster.  (3) We are at
 196  * the root of the root cluster.
 197  */
 198 static
 199 int
 200 hammer_load_cursor_parent(hammer_cursor_t cursor)
 201 {
 202         hammer_cluster_t cluster;
 203         int error;
 204
 205         cluster = cursor->node->cluster;
 206
 207         if (cursor->node->ondisk->parent) {
 208                 error = hammer_load_cursor_parent_local(cursor);
 209         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
 210                 error = hammer_load_cursor_parent_cluster(cursor);
 211         } else {
 212                 cursor->parent = NULL;
 213                 cursor->parent_index = 0;
 214                 cursor->left_bound = &cluster->ondisk->clu_btree_beg;
 215                 cursor->right_bound = &cluster->ondisk->clu_btree_end;
 216                 error = 0;
 217         }
 218         return(error);
 219 }
 220
 221 static
 222 int
 223 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
 224 {
 225         hammer_node_t node;
 226         hammer_node_t parent;
 227         hammer_btree_elm_t elm;
 228         int error;
 229         int i;
 230
 231         node = cursor->node;
 232         parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
 233         if (error)
 234                 return(error);
 235         elm = NULL;
 236         for (i = 0; i < parent->ondisk->count; ++i) {
 237                 elm = &parent->ondisk->elms[i];
 238                 if (parent->ondisk->elms[i].internal.subtree_offset ==
 239                     node->node_offset) {
 240                         break;
 241                 }
 242         }
 243         KKASSERT(i != parent->ondisk->count);
 244         KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0);
 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         if (hammer_lock_ex_try(&parent->lock) != 0) {
 251                 hammer_unlock(&cursor->node->lock);
 252                 hammer_lock_ex(&parent->lock);
 253                 hammer_lock_ex(&cursor->node->lock);
 254                 /* XXX check node generation count */
 255         }
 256         return(error);
 257 }
 258
 259 static
 260 int
 261 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
 262 {
 263         hammer_cluster_ondisk_t ondisk;
 264         hammer_cluster_t cluster;
 265         hammer_volume_t volume;
 266         hammer_node_t node;
 267         hammer_node_t parent;
 268         hammer_btree_elm_t elm;
 269         int32_t clu_no;
 270         int32_t vol_no;
 271         int error;
 272         int i;
 273
 274         node = cursor->node;
 275         ondisk = node->cluster->ondisk;
 276         vol_no = ondisk->clu_btree_parent_vol_no;
 277         clu_no = ondisk->clu_btree_parent_clu_no;
 278
 279         /*
 280          * Acquire the node from (volume, cluster, offset)
 281          */
 282         volume = hammer_get_volume(node->cluster->volume->hmp, vol_no, &error);
 283         if (error)
 284                 return (error);
 285         cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 286         hammer_rel_volume(volume, 0);
 287         if (error)
 288                 return (error);
 289         parent = hammer_get_node(cluster, ondisk->clu_btree_parent_offset,
 290                                  &error);
 291         hammer_rel_cluster(cluster, 0);
 292         if (error)
 293                 return (error);
 294
 295         /*
 296          * Ok, we have the node.  Locate the inter-cluster element
 297          */
 298         elm = NULL;
 299         for (i = 0; i < parent->ondisk->count; ++i) {
 300                 elm = &parent->ondisk->elms[i];
 301                 if (elm->internal.rec_offset != 0 &&
 302                     elm->internal.subtree_cluid == clu_no) {
 303                         break;
 304                 }
 305         }
 306         KKASSERT(i != parent->ondisk->count);
 307         cursor->parent = parent;
 308         cursor->parent_index = i;
 309         cursor->left_bound = &elm[0].internal.base;
 310         cursor->right_bound = &elm[1].internal.base;
 311
 312         KKASSERT(hammer_btree_cmp(cursor->left_bound,
 313                  &parent->cluster->ondisk->clu_btree_beg) == 0);
 314         KKASSERT(hammer_btree_cmp(cursor->right_bound,
 315                  &parent->cluster->ondisk->clu_btree_end) == 0);
 316
 317         if (hammer_lock_ex_try(&parent->lock) != 0) {
 318                 hammer_unlock(&cursor->node->lock);
 319                 hammer_lock_ex(&parent->lock);
 320                 hammer_lock_ex(&cursor->node->lock);
 321                 /* XXX check node generation count */
 322         }
 323         return(0);
 324 }
 325
 326 /*
 327  * Cursor up to our parent node.  Return ENOENT if we are at the root of
 328  * the root cluster.
 329  *
 330  * If doing a nonblocking cursor-up and we are unable to acquire the lock,
 331  * the cursor remains unchanged.
 332  */
 333 int
 334 hammer_cursor_up(hammer_cursor_t cursor, int nonblock)
 335 {
 336         hammer_node_t save;
 337         int error;
 338
 339         /*
 340          * If asked to do this non-blocking acquire a lock on the parent
 341          * now, before we mess with the cursor.
 342          */
 343         if (nonblock) {
 344                 save = hammer_get_parent_node(cursor->parent, &error);
 345                 if (error)
 346                         return(error);
 347                 if (save) {
 348                         if (hammer_lock_ex_try(&save->lock) != 0) {
 349                                 hammer_rel_node(save);
 350                                 return(EAGAIN);
 351                         }
 352                 }
 353         } else {
 354                 save = NULL;
 355         }
 356
 357         /*
 358          * Set the node to its parent.  If the parent is NULL we are at
 359          * the root of the root cluster and return ENOENT.
 360          */
 361         hammer_unlock(&cursor->node->lock);
 362         hammer_rel_node(cursor->node);
 363         cursor->node = cursor->parent;
 364         cursor->index = cursor->parent_index;
 365         cursor->parent = NULL;
 366         cursor->parent_index = 0;
 367
 368         if (cursor->node == NULL) {
 369                 error = ENOENT;
 370         } else {
 371                 error = hammer_load_cursor_parent(cursor);
 372         }
 373         if (save) {
 374                 hammer_unlock(&save->lock);
 375                 hammer_rel_node(save);
 376         }
 377         return(error);
 378 }
 379
 380 /*
 381  * Set the cursor to the root of the current cursor's cluster.
 382  */
 383 int
 384 hammer_cursor_toroot(hammer_cursor_t cursor)
 385 {
 386         hammer_cluster_t cluster;
 387         int error;
 388
 389         /*
 390          * Already at root of cluster?
 391          */
 392         if (cursor->node->ondisk->parent == 0)
 393                 return (0);
 394
 395         /*
 396          * Parent is root of cluster?
 397          */
 398         if (cursor->parent->ondisk->parent == 0)
 399                 return (hammer_cursor_up(cursor, 0));
 400
 401         /*
 402          * Ok, reload the cursor with the root of the cluster, then
 403          * locate its parent.
 404          */
 405         cluster = cursor->node->cluster;
 406         error = hammer_ref_cluster(cluster);
 407         if (error)
 408                 return (error);
 409
 410         hammer_unlock(&cursor->parent->lock);
 411         hammer_rel_node(cursor->parent);
 412         hammer_unlock(&cursor->node->lock);
 413         hammer_rel_node(cursor->node);
 414         cursor->parent = NULL;
 415         cursor->parent_index = 0;
 416
 417         cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
 418                                        &error);
 419         cursor->index = 0;
 420         hammer_rel_cluster(cluster, 0);
 421         if (error == 0)
 422                 error = hammer_load_cursor_parent(cursor);
 423         return(error);
 424 }
 425
 426 /*
 427  * Cursor down through the current node, which must be an internal node.
 428  *
 429  * This routine adjusts the cursor and sets index to 0.
 430  */
 431 int
 432 hammer_cursor_down(hammer_cursor_t cursor)
 433 {
 434         hammer_node_t node;
 435         hammer_btree_elm_t elm;
 436         hammer_volume_t volume;
 437         hammer_cluster_t cluster;
 438         int32_t vol_no;
 439         int32_t clu_no;
 440         int error;
 441
 442         /*
 443          * The current node becomes the current parent
 444          */
 445         node = cursor->node;
 446         KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
 447         KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
 448         if (cursor->parent) {
 449                 hammer_unlock(&cursor->parent->lock);
 450                 hammer_rel_node(cursor->parent);
 451         }
 452         cursor->parent = node;
 453         cursor->parent_index = cursor->index;
 454         cursor->node = NULL;
 455         cursor->index = 0;
 456
 457         /*
 458          * Extract element to push into at (node,index), set bounds.
 459          */
 460         elm = &node->ondisk->elms[cursor->parent_index];
 461         cursor->left_bound = &elm[0].internal.base;
 462         cursor->right_bound = &elm[1].internal.base;
 463
 464         /*
 465          * Ok, push down into elm.  If rec_offset is non-zero this is
 466          * an inter-cluster push, otherwise it is a intra-cluster push.
 467          */
 468         if (elm->internal.rec_offset) {
 469                 vol_no = elm->internal.subtree_volno;
 470                 clu_no = elm->internal.subtree_cluid;
 471                 volume = hammer_get_volume(node->cluster->volume->hmp,
 472                                            vol_no, &error);
 473                 if (error)
 474                         return(error);
 475                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 476                 hammer_rel_volume(volume, 0);
 477                 if (error)
 478                         return(error);
 479                 node = hammer_get_node(cluster,
 480                                        cluster->ondisk->clu_btree_root,
 481                                        &error);
 482                 hammer_rel_cluster(cluster, 0);
 483         } else {
 484                 node = hammer_get_node(node->cluster,
 485                                        elm->internal.subtree_offset,
 486                                        &error);
 487         }
 488         if (error == 0) {
 489                 hammer_lock_ex(&node->lock);
 490                 cursor->node = node;
 491                 cursor->index = 0;
 492         }
 493         return(error);
 494 }
 495