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