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.h,v 1.14 2008/03/19 20:18:17 dillon Exp $ 35 */ 36 37 /* 38 * The hammer_cursor structure is the primary in-memory management structure 39 * for B-Tree operations. 40 * 41 * The most important issue to make note of is that a hammer_cursor is a 42 * tracking structure. Any active hammer_cursor structure will be linked into 43 * hammer_node based lists and B-Tree operations executed by unrelated 44 * treads MAY MODIFY YOUR CURSOR when you are not holding an exclusive 45 * lock on the cursor's nodes. 46 * 47 * The cursor module maintains a shared lock on cursor->node and 48 * cursor->parent. 49 */ 50 struct hammer_cursor { 51 /* 52 * Parent B-Tree node, current B-Tree node, and related element 53 * indices. 54 */ 55 hammer_transaction_t trans; 56 hammer_node_t parent; 57 int parent_index; 58 59 hammer_node_t node; 60 int index; 61 62 /* 63 * Set of a deadlock occurs. hammer_done_cursor() will block on 64 * this after releasing parent and node, before returning. 65 */ 66 hammer_node_t deadlk_node; 67 68 /* 69 * Set along with HAMMER_CURSOR_CREATE_CHECK when doing an as-of 70 * search. If ENOENT is returned and the flag is set, the caller 71 * must iterate with a new delete_tid. 72 */ 73 hammer_tid_t create_check; 74 75 /* 76 * Pointer to the current node's bounds. Typically points to the 77 * appropriate boundary elements in the parent or points to bounds 78 * stored in the cluster. The right-boundary is range-exclusive. 79 */ 80 hammer_base_elm_t left_bound; 81 hammer_base_elm_t right_bound; 82 83 /* 84 * Key or key range governing search. The cursor code may adjust 85 * key_beg/key_end if asof is non-zero. 86 */ 87 struct hammer_base_elm key_beg; 88 struct hammer_base_elm key_end; 89 hammer_tid_t asof; 90 91 /* 92 * Related data and record references. Note that the related buffers 93 * can be NULL when data and/or record is not, typically indicating 94 * information referenced via an in-memory record. 95 */ 96 struct hammer_buffer *record_buffer; /* record (+ built-in data) */ 97 struct hammer_buffer *data_buffer; /* extended data */ 98 union hammer_record_ondisk *record; 99 union hammer_data_ondisk *data; 100 101 /* 102 * Iteration and extraction control variables 103 */ 104 int flags; 105 106 /* 107 * Merged in-memory/on-disk iterations also use these fields. 108 */ 109 struct hammer_inode *ip; 110 struct hammer_record *iprec; 111 struct hammer_rec_rb_tree_scan_info scan; 112 }; 113 114 typedef struct hammer_cursor *hammer_cursor_t; 115 116 #define HAMMER_CURSOR_GET_RECORD 0x0001 117 #define HAMMER_CURSOR_GET_DATA 0x0002 118 #define HAMMER_CURSOR_UNUSED0004 0x0004 119 #define HAMMER_CURSOR_INSERT 0x0008 /* adjust for insert */ 120 #define HAMMER_CURSOR_DELETE 0x0010 /* adjust for delete */ 121 #define HAMMER_CURSOR_END_INCLUSIVE 0x0020 /* key_end is inclusive */ 122 #define HAMMER_CURSOR_END_EXCLUSIVE 0x0040 /* key_end is exclusive (def) */ 123 #define HAMMER_CURSOR_UNUSED0080 0x0080 124 125 #define HAMMER_CURSOR_ATEDISK 0x0100 126 #define HAMMER_CURSOR_ATEMEM 0x0200 127 #define HAMMER_CURSOR_DISKEOF 0x0400 128 #define HAMMER_CURSOR_MEMEOF 0x0800 129 #define HAMMER_CURSOR_DELBTREE 0x1000 /* ip_delete from b-tree */ 130 #define HAMMER_CURSOR_DATAEXTOK 0x2000 /* allow data extension */ 131 #define HAMMER_CURSOR_ASOF 0x4000 /* as-of lookup */ 132 #define HAMMER_CURSOR_CREATE_CHECK 0x8000 /* as-of lookup */ 133 134