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.1 2007/11/19 00:53: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 int error; 81 82 if (ip->cache) { 83 bzero(cursor, sizeof(*cursor)); 84 cursor->node = ip->cache; 85 error = hammer_ref_node(cursor->node); 86 if (error == 0) { 87 hammer_lock_ex(&cursor->node->lock); 88 error = hammer_load_cursor_parent(cursor); 89 } else { 90 hammer_rel_node(cursor->node); 91 cursor->node = NULL; 92 } 93 } else { 94 error = hammer_init_cursor_hmp(cursor, ip->hmp); 95 } 96 return(error); 97 } 98 99 /* 100 * We are finished with a cursor. We NULL out various fields as sanity 101 * check, in case the structure is inappropriately used afterwords. 102 */ 103 void 104 hammer_done_cursor(hammer_cursor_t cursor) 105 { 106 if (cursor->parent) { 107 hammer_unlock(&cursor->parent->lock); 108 hammer_rel_node(cursor->parent); 109 cursor->parent = NULL; 110 } 111 if (cursor->node) { 112 hammer_unlock(&cursor->node->lock); 113 hammer_rel_node(cursor->node); 114 cursor->node = NULL; 115 } 116 if (cursor->data_buffer) { 117 hammer_rel_buffer(cursor->data_buffer, 0); 118 cursor->data_buffer = NULL; 119 } 120 if (cursor->record_buffer) { 121 hammer_rel_buffer(cursor->record_buffer, 0); 122 cursor->record_buffer = NULL; 123 } 124 cursor->data = NULL; 125 cursor->record = NULL; 126 cursor->left_bound = NULL; 127 cursor->right_bound = NULL; 128 } 129 130 /* 131 * Load the parent of cursor->node into cursor->parent. There are several 132 * cases. (1) The parent is in the current cluster. (2) We are at the 133 * root of the cluster and the parent is in another cluster. (3) We are at 134 * the root of the root cluster. 135 */ 136 static 137 int 138 hammer_load_cursor_parent(hammer_cursor_t cursor) 139 { 140 hammer_cluster_t cluster; 141 int error; 142 143 cluster = cursor->node->cluster; 144 145 if (cursor->node->ondisk->parent) { 146 error = hammer_load_cursor_parent_local(cursor); 147 } else if (cluster->ondisk->clu_btree_parent_vol_no >= 0) { 148 error = hammer_load_cursor_parent_cluster(cursor); 149 } else { 150 cursor->parent = NULL; 151 cursor->parent_index = 0; 152 cursor->left_bound = &cluster->ondisk->clu_btree_beg; 153 cursor->right_bound = &cluster->ondisk->clu_btree_end; 154 error = 0; 155 } 156 return(error); 157 } 158 159 static 160 int 161 hammer_load_cursor_parent_local(hammer_cursor_t cursor) 162 { 163 hammer_node_t node; 164 hammer_node_t parent; 165 hammer_btree_elm_t elm; 166 int error; 167 int i; 168 169 node = cursor->node; 170 parent = hammer_get_node(node->cluster, node->ondisk->parent, &error); 171 if (error) 172 return(error); 173 elm = NULL; 174 for (i = 0; i < parent->ondisk->count; ++i) { 175 elm = &parent->ondisk->elms[i]; 176 if (parent->ondisk->elms[i].internal.subtree_offset == 177 node->node_offset) { 178 break; 179 } 180 } 181 KKASSERT(i != parent->ondisk->count); 182 KKASSERT(parent->ondisk->elms[i].internal.rec_offset == 0); 183 cursor->parent = parent; 184 cursor->parent_index = i; 185 cursor->left_bound = &elm[0].internal.base; 186 cursor->right_bound = &elm[1].internal.base; 187 188 if (hammer_lock_ex_try(&parent->lock) != 0) { 189 hammer_unlock(&cursor->node->lock); 190 hammer_lock_ex(&parent->lock); 191 hammer_lock_ex(&cursor->node->lock); 192 /* XXX check node generation count */ 193 } 194 return(error); 195 } 196 197 static 198 int 199 hammer_load_cursor_parent_cluster(hammer_cursor_t cursor) 200 { 201 hammer_cluster_ondisk_t ondisk; 202 hammer_cluster_t cluster; 203 hammer_volume_t volume; 204 hammer_node_t node; 205 hammer_node_t parent; 206 hammer_btree_elm_t elm; 207 int32_t clu_no; 208 int32_t vol_no; 209 int error; 210 int i; 211 212 node = cursor->node; 213 ondisk = node->cluster->ondisk; 214 vol_no = ondisk->clu_btree_parent_vol_no; 215 clu_no = ondisk->clu_btree_parent_clu_no; 216 217 /* 218 * Acquire the node from (volume, cluster, offset) 219 */ 220 volume = hammer_get_volume(node->cluster->volume->hmp, vol_no, &error); 221 if (error) 222 return (error); 223 cluster = hammer_get_cluster(volume, clu_no, &error, 0); 224 hammer_rel_volume(volume, 0); 225 if (error) 226 return (error); 227 parent = hammer_get_node(cluster, ondisk->clu_btree_parent_offset, 228 &error); 229 hammer_rel_cluster(cluster, 0); 230 if (error) 231 return (error); 232 233 /* 234 * Ok, we have the node. Locate the inter-cluster element 235 */ 236 elm = NULL; 237 for (i = 0; i < parent->ondisk->count; ++i) { 238 elm = &parent->ondisk->elms[i]; 239 if (elm->internal.rec_offset != 0 && 240 elm->internal.subtree_cluid == clu_no) { 241 break; 242 } 243 } 244 KKASSERT(i != parent->ondisk->count); 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 KKASSERT(hammer_btree_cmp(cursor->left_bound, 251 &parent->cluster->ondisk->clu_btree_beg) == 0); 252 KKASSERT(hammer_btree_cmp(cursor->right_bound, 253 &parent->cluster->ondisk->clu_btree_end) == 0); 254 255 if (hammer_lock_ex_try(&parent->lock) != 0) { 256 hammer_unlock(&cursor->node->lock); 257 hammer_lock_ex(&parent->lock); 258 hammer_lock_ex(&cursor->node->lock); 259 /* XXX check node generation count */ 260 } 261 return(0); 262 } 263 264 265 /* 266 * Cursor up to our parent node. Return ENOENT if we are at the root of 267 * the root cluster. 268 */ 269 int 270 hammer_cursor_up(hammer_cursor_t cursor) 271 { 272 int error; 273 274 /* 275 * Set the node to its parent. If the parent is NULL we are at 276 * the root of the root cluster and return ENOENT. 277 */ 278 hammer_unlock(&cursor->node->lock); 279 hammer_rel_node(cursor->node); 280 cursor->node = cursor->parent; 281 cursor->index = cursor->parent_index; 282 cursor->parent = NULL; 283 cursor->parent_index = 0; 284 285 if (cursor->node == NULL) { 286 error = ENOENT; 287 } else { 288 error = hammer_load_cursor_parent(cursor); 289 } 290 return(error); 291 } 292 293 /* 294 * Set the cursor to the root of the current cursor's cluster. 295 */ 296 int 297 hammer_cursor_toroot(hammer_cursor_t cursor) 298 { 299 hammer_cluster_t cluster; 300 int error; 301 302 /* 303 * Already at root of cluster? 304 */ 305 if (cursor->node->ondisk->parent == 0) 306 return (0); 307 308 /* 309 * Parent is root of cluster? 310 */ 311 if (cursor->parent->ondisk->parent == 0) 312 return (hammer_cursor_up(cursor)); 313 314 /* 315 * Ok, reload the cursor with the root of the cluster, then 316 * locate its parent. 317 */ 318 cluster = cursor->node->cluster; 319 error = hammer_ref_cluster(cluster); 320 if (error) 321 return (error); 322 323 hammer_unlock(&cursor->parent->lock); 324 hammer_rel_node(cursor->parent); 325 hammer_unlock(&cursor->node->lock); 326 hammer_rel_node(cursor->node); 327 cursor->parent = NULL; 328 cursor->parent_index = 0; 329 330 cursor->node = hammer_get_node(cluster, cluster->ondisk->clu_btree_root, 331 &error); 332 cursor->index = 0; 333 hammer_rel_cluster(cluster, 0); 334 if (error == 0) 335 error = hammer_load_cursor_parent(cursor); 336 return(error); 337 } 338 339 /* 340 * Cursor down through the current node, which must be an internal node. 341 * 342 * This routine adjusts the cursor and sets index to 0. 343 */ 344 int 345 hammer_cursor_down(hammer_cursor_t cursor) 346 { 347 hammer_node_t node; 348 hammer_btree_elm_t elm; 349 hammer_volume_t volume; 350 hammer_cluster_t cluster; 351 int32_t vol_no; 352 int32_t clu_no; 353 int error; 354 355 /* 356 * The current node becomes the current parent 357 */ 358 node = cursor->node; 359 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL); 360 KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count); 361 if (cursor->parent) { 362 hammer_unlock(&cursor->parent->lock); 363 hammer_rel_node(cursor->parent); 364 } 365 cursor->parent = node; 366 cursor->parent_index = cursor->index; 367 cursor->node = NULL; 368 cursor->index = 0; 369 370 /* 371 * Extract element to push into at (node,index) 372 */ 373 elm = &node->ondisk->elms[cursor->parent_index]; 374 375 /* 376 * Ok, push down into elm. If rec_offset is non-zero this is 377 * an inter-cluster push, otherwise it is a intra-cluster push. 378 */ 379 if (elm->internal.rec_offset) { 380 vol_no = elm->internal.subtree_volno; 381 clu_no = elm->internal.subtree_cluid; 382 volume = hammer_get_volume(node->cluster->volume->hmp, 383 vol_no, &error); 384 if (error) 385 return(error); 386 cluster = hammer_get_cluster(volume, clu_no, &error, 0); 387 hammer_rel_volume(volume, 0); 388 if (error) 389 return(error); 390 node = hammer_get_node(cluster, 391 cluster->ondisk->clu_btree_root, 392 &error); 393 hammer_rel_cluster(cluster, 0); 394 } else { 395 node = hammer_get_node(node->cluster, 396 elm->internal.subtree_offset, 397 &error); 398 } 399 if (error == 0) { 400 hammer_lock_ex(&node->lock); 401 cursor->node = node; 402 cursor->index = 0; 403 } 404 return(error); 405 } 406 407