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.21 2008/03/29 20:12:54 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 44 /* 45 * Initialize a fresh cursor using the B-Tree node cache. If the cache 46 * is not available initialize a fresh cursor at the root of the filesystem. 47 */ 48 int 49 hammer_init_cursor(hammer_transaction_t trans, hammer_cursor_t cursor, 50 struct hammer_node **cache) 51 { 52 hammer_volume_t volume; 53 hammer_node_t node; 54 int error; 55 56 bzero(cursor, sizeof(*cursor)); 57 58 cursor->trans = trans; 59 60 /* 61 * Step 1 - acquire a locked node from the cache if possible 62 */ 63 if (cache && *cache) { 64 node = hammer_ref_node_safe(trans->hmp, cache, &error); 65 if (error == 0) { 66 hammer_lock_sh(&node->lock); 67 if (node->flags & HAMMER_NODE_DELETED) { 68 hammer_unlock(&node->lock); 69 hammer_rel_node(node); 70 node = NULL; 71 } 72 } 73 } else { 74 node = NULL; 75 } 76 77 /* 78 * Step 2 - If we couldn't get a node from the cache, get 79 * the one from the root of the filesystem. 80 */ 81 while (node == NULL) { 82 volume = hammer_get_root_volume(trans->hmp, &error); 83 if (error) 84 break; 85 node = hammer_get_node(trans->hmp, 86 volume->ondisk->vol0_btree_root, &error); 87 hammer_rel_volume(volume, 0); 88 if (error) 89 break; 90 hammer_lock_sh(&node->lock); 91 if (node->flags & HAMMER_NODE_DELETED) { 92 hammer_unlock(&node->lock); 93 hammer_rel_node(node); 94 node = NULL; 95 } 96 } 97 98 /* 99 * Step 3 - finish initializing the cursor by acquiring the parent 100 */ 101 cursor->node = node; 102 if (error == 0) 103 error = hammer_load_cursor_parent(cursor); 104 KKASSERT(error == 0); 105 /* if (error) hammer_done_cursor(cursor); */ 106 return(error); 107 } 108 109 /* 110 * We are finished with a cursor. We NULL out various fields as sanity 111 * check, in case the structure is inappropriately used afterwords. 112 */ 113 void 114 hammer_done_cursor(hammer_cursor_t cursor) 115 { 116 if (cursor->parent) { 117 hammer_unlock(&cursor->parent->lock); 118 hammer_rel_node(cursor->parent); 119 cursor->parent = NULL; 120 } 121 if (cursor->node) { 122 hammer_unlock(&cursor->node->lock); 123 hammer_rel_node(cursor->node); 124 cursor->node = NULL; 125 } 126 if (cursor->data_buffer) { 127 hammer_rel_buffer(cursor->data_buffer, 0); 128 cursor->data_buffer = NULL; 129 } 130 if (cursor->record_buffer) { 131 hammer_rel_buffer(cursor->record_buffer, 0); 132 cursor->record_buffer = NULL; 133 } 134 if (cursor->ip) 135 hammer_mem_done(cursor); 136 137 /* 138 * If we deadlocked this node will be referenced. Do a quick 139 * lock/unlock to wait for the deadlock condition to clear. 140 */ 141 if (cursor->deadlk_node) { 142 hammer_lock_ex(&cursor->deadlk_node->lock); 143 hammer_unlock(&cursor->deadlk_node->lock); 144 hammer_rel_node(cursor->deadlk_node); 145 cursor->deadlk_node = NULL; 146 } 147 148 cursor->data = NULL; 149 cursor->record = NULL; 150 cursor->left_bound = NULL; 151 cursor->right_bound = NULL; 152 cursor->trans = NULL; 153 } 154 155 /* 156 * Upgrade cursor->node and cursor->parent to exclusive locks. This 157 * function can return EDEADLK. 158 * 159 * The lock must already be either held shared or already held exclusively 160 * by us. 161 * 162 * If we fail to upgrade the lock and cursor->deadlk_node is NULL, 163 * we add another reference to the node that failed and set 164 * cursor->deadlk_node so hammer_done_cursor() can block on it. 165 */ 166 int 167 hammer_cursor_upgrade(hammer_cursor_t cursor) 168 { 169 int error; 170 171 error = hammer_lock_upgrade(&cursor->node->lock); 172 if (error && cursor->deadlk_node == NULL) { 173 cursor->deadlk_node = cursor->node; 174 hammer_ref_node(cursor->deadlk_node); 175 } else if (error == 0 && cursor->parent) { 176 error = hammer_lock_upgrade(&cursor->parent->lock); 177 if (error && cursor->deadlk_node == NULL) { 178 cursor->deadlk_node = cursor->parent; 179 hammer_ref_node(cursor->deadlk_node); 180 } 181 } 182 return(error); 183 } 184 185 /* 186 * Downgrade cursor->node and cursor->parent to shared locks. This 187 * function can return EDEADLK. 188 */ 189 void 190 hammer_cursor_downgrade(hammer_cursor_t cursor) 191 { 192 if (hammer_lock_excl_owned(&cursor->node->lock, curthread)) 193 hammer_lock_downgrade(&cursor->node->lock); 194 if (cursor->parent && 195 hammer_lock_excl_owned(&cursor->parent->lock, curthread)) { 196 hammer_lock_downgrade(&cursor->parent->lock); 197 } 198 } 199 200 /* 201 * Seek the cursor to the specified node and index. 202 */ 203 int 204 hammer_cursor_seek(hammer_cursor_t cursor, hammer_node_t node, int index) 205 { 206 int error; 207 208 hammer_cursor_downgrade(cursor); 209 error = 0; 210 211 if (cursor->node != node) { 212 hammer_unlock(&cursor->node->lock); 213 hammer_rel_node(cursor->node); 214 cursor->node = node; 215 hammer_ref_node(node); 216 hammer_lock_sh(&node->lock); 217 218 if (cursor->parent) { 219 hammer_unlock(&cursor->parent->lock); 220 hammer_rel_node(cursor->parent); 221 cursor->parent = NULL; 222 cursor->parent_index = 0; 223 } 224 error = hammer_load_cursor_parent(cursor); 225 } 226 cursor->index = index; 227 return (error); 228 } 229 230 /* 231 * Load the parent of cursor->node into cursor->parent. 232 */ 233 static 234 int 235 hammer_load_cursor_parent(hammer_cursor_t cursor) 236 { 237 hammer_mount_t hmp; 238 hammer_node_t parent; 239 hammer_node_t node; 240 hammer_btree_elm_t elm; 241 int error; 242 int i; 243 244 hmp = cursor->trans->hmp; 245 246 if (cursor->node->ondisk->parent) { 247 node = cursor->node; 248 parent = hammer_get_node(hmp, node->ondisk->parent, &error); 249 if (error) 250 return(error); 251 hammer_lock_sh(&parent->lock); 252 elm = NULL; 253 for (i = 0; i < parent->ondisk->count; ++i) { 254 elm = &parent->ondisk->elms[i]; 255 if (parent->ondisk->elms[i].internal.subtree_offset == 256 node->node_offset) { 257 break; 258 } 259 } 260 if (i == parent->ondisk->count) { 261 hammer_unlock(&parent->lock); 262 panic("Bad B-Tree link: parent %p node %p\n", parent, node); 263 } 264 KKASSERT(i != parent->ondisk->count); 265 cursor->parent = parent; 266 cursor->parent_index = i; 267 cursor->left_bound = &elm[0].internal.base; 268 cursor->right_bound = &elm[1].internal.base; 269 return(error); 270 } else { 271 cursor->parent = NULL; 272 cursor->parent_index = 0; 273 cursor->left_bound = &hmp->root_btree_beg; 274 cursor->right_bound = &hmp->root_btree_end; 275 error = 0; 276 } 277 return(error); 278 } 279 280 /* 281 * Cursor up to our parent node. Return ENOENT if we are at the root of 282 * the filesystem. 283 * 284 * If doing a nonblocking cursor-up and we are unable to acquire the lock, 285 * the cursor remains unchanged. 286 */ 287 int 288 hammer_cursor_up(hammer_cursor_t cursor) 289 { 290 int error; 291 292 hammer_cursor_downgrade(cursor); 293 294 /* 295 * Set the node to its parent. If the parent is NULL we are at 296 * the root of the filesystem and return ENOENT. 297 */ 298 hammer_unlock(&cursor->node->lock); 299 hammer_rel_node(cursor->node); 300 cursor->node = cursor->parent; 301 cursor->index = cursor->parent_index; 302 cursor->parent = NULL; 303 cursor->parent_index = 0; 304 305 if (cursor->node == NULL) { 306 error = ENOENT; 307 } else { 308 error = hammer_load_cursor_parent(cursor); 309 } 310 return(error); 311 } 312 313 /* 314 * Cursor down through the current node, which must be an internal node. 315 * 316 * This routine adjusts the cursor and sets index to 0. 317 */ 318 int 319 hammer_cursor_down(hammer_cursor_t cursor) 320 { 321 hammer_node_t node; 322 hammer_btree_elm_t elm; 323 int error; 324 325 /* 326 * The current node becomes the current parent 327 */ 328 hammer_cursor_downgrade(cursor); 329 node = cursor->node; 330 KKASSERT(cursor->index >= 0 && cursor->index < node->ondisk->count); 331 if (cursor->parent) { 332 hammer_unlock(&cursor->parent->lock); 333 hammer_rel_node(cursor->parent); 334 } 335 cursor->parent = node; 336 cursor->parent_index = cursor->index; 337 cursor->node = NULL; 338 cursor->index = 0; 339 340 /* 341 * Extract element to push into at (node,index), set bounds. 342 */ 343 elm = &node->ondisk->elms[cursor->parent_index]; 344 345 /* 346 * Ok, push down into elm. If elm specifies an internal or leaf 347 * node the current node must be an internal node. If elm specifies 348 * a spike then the current node must be a leaf node. 349 */ 350 switch(elm->base.btype) { 351 case HAMMER_BTREE_TYPE_INTERNAL: 352 case HAMMER_BTREE_TYPE_LEAF: 353 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL); 354 KKASSERT(elm->internal.subtree_offset != 0); 355 cursor->left_bound = &elm[0].internal.base; 356 cursor->right_bound = &elm[1].internal.base; 357 node = hammer_get_node(cursor->trans->hmp, 358 elm->internal.subtree_offset, &error); 359 if (error == 0) { 360 KASSERT(elm->base.btype == node->ondisk->type, ("BTYPE MISMATCH %c %c NODE %p\n", elm->base.btype, node->ondisk->type, node)); 361 if (node->ondisk->parent != cursor->parent->node_offset) 362 panic("node %p %016llx vs %016llx\n", node, node->ondisk->parent, cursor->parent->node_offset); 363 KKASSERT(node->ondisk->parent == cursor->parent->node_offset); 364 } 365 break; 366 default: 367 panic("hammer_cursor_down: illegal btype %02x (%c)\n", 368 elm->base.btype, 369 (elm->base.btype ? elm->base.btype : '?')); 370 break; 371 } 372 if (error == 0) { 373 hammer_lock_sh(&node->lock); 374 cursor->node = node; 375 cursor->index = 0; 376 } 377 return(error); 378 } 379 380