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.7 2007/12/30 00:47:22 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 at the root of the specified cluster and
  75  * limit operations to within the cluster.
  76  */
  77 int
  78 hammer_init_cursor_cluster(hammer_cursor_t cursor, hammer_cluster_t cluster)
  79 {
  80         int error;
  81
  82         bzero(cursor, sizeof(*cursor));
  83         cursor->flags |= HAMMER_CURSOR_INCLUSTER;
  84         cursor->node = hammer_get_node(cluster,
  85                                        cluster->ondisk->clu_btree_root,
  86                                        &error);
  87         if (error == 0) {
  88                 hammer_lock_ex(&cursor->node->lock);
  89                 error = hammer_load_cursor_parent(cursor);
  90         }
  91         return(error);
  92 }
  93
  94 /*
  95  * Initialize a fresh cursor using the B-Tree node cached by the
  96  * in-memory inode.
  97  */
  98 int
  99 hammer_init_cursor_ip(hammer_cursor_t cursor, hammer_inode_t ip)
 100 {
 101         hammer_node_t node;
 102         int error;
 103
 104         if (ip->cache) {
 105                 bzero(cursor, sizeof(*cursor));
 106                 node = ip->cache;
 107                 error = hammer_ref_node(node);
 108                 if (error == 0) {
 109                         hammer_lock_ex(&node->lock);
 110                         cursor->node = node;
 111                         error = hammer_load_cursor_parent(cursor);
 112                 } else {
 113                         node = NULL;
 114                         cursor->node = node;
 115                 }
 116         } else {
 117                 error = hammer_init_cursor_hmp(cursor, ip->hmp);
 118         }
 119         return(error);
 120 }
 121
 122 /*
 123  * We are finished with a cursor.  We NULL out various fields as sanity
 124  * check, in case the structure is inappropriately used afterwords.
 125  */
 126 void
 127 hammer_done_cursor(hammer_cursor_t cursor)
 128 {
 129         if (cursor->parent) {
 130                 hammer_unlock(&cursor->parent->lock);
 131                 hammer_rel_node(cursor->parent);
 132                 cursor->parent = NULL;
 133         }
 134         if (cursor->node) {
 135                 hammer_unlock(&cursor->node->lock);
 136                 hammer_rel_node(cursor->node);
 137                 cursor->node = NULL;
 138         }
 139         if (cursor->data_buffer) {
 140                 hammer_rel_buffer(cursor->data_buffer, 0);
 141                 cursor->data_buffer = NULL;
 142         }
 143         if (cursor->record_buffer) {
 144                 hammer_rel_buffer(cursor->record_buffer, 0);
 145                 cursor->record_buffer = NULL;
 146         }
 147         if (cursor->ip)
 148                 hammer_mem_done(cursor);
 149
 150         cursor->data = NULL;
 151         cursor->record = NULL;
 152         cursor->left_bound = NULL;
 153         cursor->right_bound = NULL;
 154 }
 155
 156 /*
 157  * Acquire the parent B-Tree node of the specified node, returning a
 158  * referenced but unlocked node.  NULL can be returned with *errorp == 0
 159  * if node is the root node of the root cluster.
 160  */
 161 static
 162 hammer_node_t
 163 hammer_get_parent_node(hammer_node_t node, int *errorp)
 164 {
 165         hammer_cluster_t cluster;
 166         hammer_node_t parent;
 167
 168         cluster = node->cluster;
 169         if (node->ondisk->parent) {
 170                 /*
 171                  * Local parent
 172                  */
 173                 parent = hammer_get_node(cluster, node->ondisk->parent, errorp);
 174         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) {
 175                 /*
 176                  * At cluster root, locate node in parent cluster
 177                  */
 178                 hammer_cluster_ondisk_t ondisk;
 179                 hammer_cluster_t pcluster;
 180                 hammer_volume_t pvolume;
 181                 int32_t clu_no;
 182                 int32_t vol_no;
 183
 184                 ondisk = cluster->ondisk;
 185                 vol_no = ondisk->clu_btree_parent_vol_no;
 186                 clu_no = ondisk->clu_btree_parent_clu_no;
 187
 188                 /*
 189                  * Acquire the node from (volume, cluster, offset)
 190                  */
 191                 pvolume = hammer_get_volume(cluster->volume->hmp, vol_no,
 192                                             errorp);
 193                 if (*errorp)
 194                         return (NULL);
 195                 pcluster = hammer_get_cluster(pvolume, clu_no, errorp, 0);
 196                 hammer_rel_volume(pvolume, 0);
 197                 if (*errorp)
 198                         return (NULL);
 199                 parent = hammer_get_node(pcluster,
 200                                          ondisk->clu_btree_parent_offset,
 201                                          errorp);
 202                 hammer_rel_cluster(pcluster, 0);
 203         } else {
 204                 /*
 205                  * At root of root cluster, there is no parent.
 206                  */
 207                 KKASSERT(cluster->ondisk->clu_btree_parent_vol_no == -1);
 208                 parent = NULL;
 209                 *errorp = 0;
 210         }
 211         return(parent);
 212 }
 213
 214 /*
 215  * Load the parent of cursor->node into cursor->parent.  There are several
 216  * cases.  (1) The parent is in the current cluster.  (2) We are at the
 217  * root of the cluster and the parent is in another cluster.  (3) We are at
 218  * the root of the root cluster.
 219  *
 220  * If HAMMER_CURSOR_INCLUSTER is set and we are at the root of the cluster,
 221  * we do not access the parent cluster at all and make the cursor look like
 222  * its at the root.
 223  */
 224 static
 225 int
 226 hammer_load_cursor_parent(hammer_cursor_t cursor)
 227 {
 228         hammer_cluster_t cluster;
 229         int error;
 230
 231         cluster = cursor->node->cluster;
 232
 233         if (cursor->node->ondisk->parent) {
 234                 error = hammer_load_cursor_parent_local(cursor);
 235         } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0 &&
 236                    ((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0)
 237         ) {
 238                 error = hammer_load_cursor_parent_cluster(cursor);
 239         } else {
 240                 cursor->parent = NULL;
 241                 cursor->parent_index = 0;
 242                 cursor->left_bound = &cluster->ondisk->clu_btree_beg;
 243                 cursor->right_bound = &cluster->ondisk->clu_btree_end;
 244                 error = 0;
 245         }
 246         return(error);
 247 }
 248
 249 static
 250 int
 251 hammer_load_cursor_parent_local(hammer_cursor_t cursor)
 252 {
 253         hammer_node_t node;
 254         hammer_node_t parent;
 255         hammer_btree_elm_t elm;
 256         int error;
 257         int i;
 258
 259         node = cursor->node;
 260         parent = hammer_get_node(node->cluster, node->ondisk->parent, &error);
 261         if (error)
 262                 return(error);
 263         elm = NULL;
 264         for (i = 0; i < parent->ondisk->count; ++i) {
 265                 elm = &parent->ondisk->elms[i];
 266                 if (parent->ondisk->elms[i].internal.subtree_offset ==
 267                     node->node_offset) {
 268                         break;
 269                 }
 270         }
 271         if (i == parent->ondisk->count)
 272                 panic("Bad B-Tree link: parent %p node %p\n", parent, node);
 273         KKASSERT(i != parent->ondisk->count);
 274         KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0);
 275         cursor->parent = parent;
 276         cursor->parent_index = i;
 277         cursor->left_bound = &elm[0].internal.base;
 278         cursor->right_bound = &elm[1].internal.base;
 279
 280         if (hammer_lock_ex_try(&parent->lock) != 0) {
 281                 hammer_unlock(&cursor->node->lock);
 282                 hammer_lock_ex(&parent->lock);
 283                 hammer_lock_ex(&cursor->node->lock);
 284                 /* XXX check node generation count */
 285         }
 286         return(error);
 287 }
 288
 289 static
 290 int
 291 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor)
 292 {
 293         hammer_cluster_ondisk_t ondisk;
 294         hammer_cluster_t pcluster;
 295         hammer_cluster_t ccluster;
 296         hammer_volume_t volume;
 297         hammer_node_t node;
 298         hammer_node_t parent;
 299         hammer_btree_elm_t elm;
 300         int32_t clu_no;
 301         int32_t vol_no;
 302         int error;
 303         int i;
 304
 305         node = cursor->node;
 306         ccluster = node->cluster;
 307         ondisk = ccluster->ondisk;
 308         vol_no = ondisk->clu_btree_parent_vol_no;
 309         clu_no = ondisk->clu_btree_parent_clu_no;
 310
 311         /*
 312          * Acquire the node from (volume, cluster, offset)
 313          */
 314         volume = hammer_get_volume(ccluster->volume->hmp, vol_no, &error);
 315         if (error)
 316                 return (error);
 317         pcluster = hammer_get_cluster(volume, clu_no, &error, 0);
 318         hammer_rel_volume(volume, 0);
 319         if (error)
 320                 return (error);
 321         parent = hammer_get_node(pcluster, ondisk->clu_btree_parent_offset,
 322                                  &error);
 323         hammer_rel_cluster(pcluster, 0);
 324         if (error)
 325                 return (error);
 326
 327         /*
 328          * Ok, we have the node.  Locate the inter-cluster element
 329          */
 330         elm = NULL;
 331         for (i = 0; i < parent->ondisk->count; ++i) {
 332                 elm = &parent->ondisk->elms[i];
 333                 if (elm->internal.rec_offset != 0 &&
 334                     elm->internal.subtree_type == HAMMER_BTREE_TYPE_CLUSTER &&
 335                     elm->internal.subtree_clu_no == cursor->node->cluster->clu_no) {
 336                         break;
 337                 }
 338         }
 339         KKASSERT(i != parent->ondisk->count);
 340         cursor->parent = parent;
 341         cursor->parent_index = i;
 342         cursor->left_bound = &elm[0].internal.base;
 343         cursor->right_bound = &elm[1].internal.base;
 344
 345         KKASSERT(hammer_btree_cmp(cursor->left_bound,
 346                  &ccluster->ondisk->clu_btree_beg) == 0);
 347         KKASSERT(hammer_btree_cmp(cursor->right_bound,
 348                  &ccluster->ondisk->clu_btree_end) == 0);
 349
 350         if (hammer_lock_ex_try(&parent->lock) != 0) {
 351                 hammer_unlock(&cursor->node->lock);
 352                 hammer_lock_ex(&parent->lock);
 353                 hammer_lock_ex(&cursor->node->lock);
 354                 /* XXX check node generation count */
 355         }
 356         return(0);
 357 }
 358
 359 /*
 360  * Cursor up to our parent node.  Return ENOENT if we are at the root of
 361  * the root cluster.
 362  *
 363  * If doing a nonblocking cursor-up and we are unable to acquire the lock,
 364  * the cursor remains unchanged.
 365  */
 366 int
 367 hammer_cursor_up(hammer_cursor_t cursor, int nonblock)
 368 {
 369         hammer_node_t save;
 370         int error;
 371
 372         /*
 373          * If asked to do this non-blocking acquire a lock on the parent
 374          * now, before we mess with the cursor.
 375          */
 376         if (nonblock) {
 377                 save = hammer_get_parent_node(cursor->parent, &error);
 378                 if (error)
 379                         return(error);
 380                 if (save) {
 381                         if (hammer_lock_ex_try(&save->lock) != 0) {
 382                                 hammer_rel_node(save);
 383                                 return(EAGAIN);
 384                         }
 385                 }
 386         } else {
 387                 save = NULL;
 388         }
 389
 390         /*
 391          * Set the node to its parent.  If the parent is NULL we are at
 392          * the root of the root cluster and return ENOENT.
 393          */
 394         hammer_unlock(&cursor->node->lock);
 395         hammer_rel_node(cursor->node);
 396         cursor->node = cursor->parent;
 397         cursor->index = cursor->parent_index;
 398         cursor->parent = NULL;
 399         cursor->parent_index = 0;
 400
 401         if (cursor->node == NULL) {
 402                 error = ENOENT;
 403         } else if ((cursor->flags & HAMMER_CURSOR_INCLUSTER) &&
 404                    cursor->node->ondisk->parent == 0
 405         ) {
 406                 error = ENOENT;
 407         } else {
 408                 error = hammer_load_cursor_parent(cursor);
 409         }
 410         if (save) {
 411                 hammer_unlock(&save->lock);
 412                 hammer_rel_node(save);
 413         }
 414         return(error);
 415 }
 416
 417 /*
 418  * Set the cursor to the root of the current cursor's cluster.
 419  */
 420 int
 421 hammer_cursor_toroot(hammer_cursor_t cursor)
 422 {
 423         hammer_cluster_t cluster;
 424         int error;
 425
 426         /*
 427          * Already at root of cluster?
 428          */
 429         if (cursor->node->ondisk->parent == 0)
 430                 return (0);
 431
 432         /*
 433          * Parent is root of cluster?
 434          */
 435         if (cursor->parent->ondisk->parent == 0)
 436                 return (hammer_cursor_up(cursor, 0));
 437
 438         /*
 439          * Ok, reload the cursor with the root of the cluster, then
 440          * locate its parent.
 441          */
 442         cluster = cursor->node->cluster;
 443         error = hammer_ref_cluster(cluster);
 444         if (error)
 445                 return (error);
 446
 447         hammer_unlock(&cursor->parent->lock);
 448         hammer_rel_node(cursor->parent);
 449         hammer_unlock(&cursor->node->lock);
 450         hammer_rel_node(cursor->node);
 451         cursor->parent = NULL;
 452         cursor->parent_index = 0;
 453
 454         cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root,
 455                                        &error);
 456         cursor->index = 0;
 457         hammer_rel_cluster(cluster, 0);
 458         if (error == 0)
 459                 error = hammer_load_cursor_parent(cursor);
 460         return(error);
 461 }
 462
 463 /*
 464  * Cursor down through the current node, which must be an internal node.
 465  *
 466  * This routine adjusts the cursor and sets index to 0.
 467  */
 468 int
 469 hammer_cursor_down(hammer_cursor_t cursor)
 470 {
 471         hammer_node_t node;
 472         hammer_btree_elm_t elm;
 473         hammer_volume_t volume;
 474         hammer_cluster_t cluster;
 475         int32_t vol_no;
 476         int32_t clu_no;
 477         int error;
 478
 479         /*
 480          * The current node becomes the current parent
 481          */
 482         node = cursor->node;
 483         KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
 484         KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count);
 485         if (cursor->parent) {
 486                 hammer_unlock(&cursor->parent->lock);
 487                 hammer_rel_node(cursor->parent);
 488         }
 489         cursor->parent = node;
 490         cursor->parent_index = cursor->index;
 491         cursor->node = NULL;
 492         cursor->index = 0;
 493
 494         /*
 495          * Extract element to push into at (node,index), set bounds.
 496          */
 497         elm = &node->ondisk->elms[cursor->parent_index];
 498         cursor->left_bound = &elm[0].internal.base;
 499         cursor->right_bound = &elm[1].internal.base;
 500
 501         /*
 502          * Ok, push down into elm.  If rec_offset is non-zero this is
 503          * an inter-cluster push, otherwise it is a intra-cluster push.
 504          *
 505          * Cursoring down through a cluster transition when the INCLUSTER
 506          * flag is set is not legal.
 507          */
 508         if (elm->internal.rec_offset) {
 509                 KKASSERT((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0);
 510                 vol_no = elm->internal.subtree_vol_no;
 511                 clu_no = elm->internal.subtree_clu_no;
 512                 volume = hammer_get_volume(node->cluster->volume->hmp,
 513                                            vol_no, &error);
 514                 if (error)
 515                         return(error);
 516                 cluster = hammer_get_cluster(volume, clu_no, &error, 0);
 517                 hammer_rel_volume(volume, 0);
 518                 if (error)
 519                         return(error);
 520                 node = hammer_get_node(cluster,
 521                                        cluster->ondisk->clu_btree_root,
 522                                        &error);
 523                 hammer_rel_cluster(cluster, 0);
 524         } else {
 525                 KKASSERT(elm->internal.subtree_offset != 0);
 526                 node = hammer_get_node(node->cluster,
 527                                        elm->internal.subtree_offset,
 528                                        &error);
 529                 if (error == 0) {
 530                         KKASSERT(elm->internal.subtree_type == node->ondisk->type);
 531                         if(node->ondisk->parent != cursor->parent->node_offset)
 532                                 kprintf("node %p %d vs %d\n", node, node->ondisk->parent, cursor->parent->node_offset);
 533                         KKASSERT(node->ondisk->parent == cursor->parent->node_offset);
 534                 }
 535         }
 536         if (error == 0) {
 537                 hammer_lock_ex(&node->lock);
 538                 cursor->node = node;
 539                 cursor->index = 0;
 540         }
 541         return(error);
 542 }
 543