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.8 2007/12/30 08:49:20 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