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.26 2008/08/06 15:38:58 dillon Exp $ 35 */ 36 37 #ifndef VFS_HAMMER_CURSOR_H_ 38 #define VFS_HAMMER_CURSOR_H_ 39 40 struct hammer_cmirror; 41 42 /* 43 * The hammer_cursor structure is the primary in-memory management structure 44 * for B-Tree operations. 45 * 46 * The most important issue to make note of is that a hammer_cursor is a 47 * tracking structure. Any active hammer_cursor structure will be linked into 48 * hammer_node based lists and B-Tree operations executed by unrelated 49 * treads MAY MODIFY YOUR CURSOR when you are not holding an exclusive 50 * lock on the cursor's nodes. 51 * 52 * The cursor module maintains a shared lock on cursor->node and 53 * cursor->parent. 54 */ 55 struct hammer_cursor { 56 /* 57 * Parent B-Tree node, current B-Tree node, and related element 58 * indices. 59 */ 60 hammer_transaction_t trans; 61 hammer_node_t parent; 62 int parent_index; 63 64 hammer_node_t node; 65 int index; 66 67 /* 68 * Set if a deadlock occurs. hammer_done_cursor() will block on 69 * this after releasing parent and node, before returning. See 70 * also hammer_recover_cursor(). 71 */ 72 TAILQ_ENTRY(hammer_cursor) deadlk_entry; 73 hammer_node_t deadlk_node; 74 hammer_record_t deadlk_rec; 75 76 /* 77 * Set along with HAMMER_CURSOR_CREATE_CHECK when doing an as-of 78 * search. If ENOENT is returned and the flag is set, the caller 79 * must iterate with a new delete_tid. 80 */ 81 hammer_tid_t create_check; 82 83 /* 84 * Pointer to the current node's bounds. Typically points to the 85 * appropriate boundary elements in the parent. 86 * The right-boundary is range-exclusive. 87 */ 88 hammer_base_elm_t left_bound; 89 hammer_base_elm_t right_bound; 90 91 /* 92 * Key or key range governing search. The cursor code may adjust 93 * key_beg/key_end if asof is non-zero. 94 */ 95 struct hammer_base_elm key_beg; 96 struct hammer_base_elm key_end; 97 hammer_tid_t asof; 98 struct hammer_cmirror *cmirror; 99 100 /* 101 * Related data and record references. Note that the related buffers 102 * can be NULL when data and/or record is not, typically indicating 103 * information referenced via an in-memory record. 104 */ 105 struct hammer_buffer *data_buffer; /* extended data */ 106 struct hammer_btree_leaf_elm *leaf; 107 union hammer_data_ondisk *data; 108 109 /* 110 * Iteration and extraction control variables 111 */ 112 int flags; 113 int rec_generation; 114 115 /* 116 * Merged in-memory/on-disk iterations also use these fields. 117 */ 118 struct hammer_inode *ip; 119 struct hammer_record *iprec; 120 }; 121 122 typedef struct hammer_cursor *hammer_cursor_t; 123 124 #define HAMMER_CURSOR_GET_LEAF 0x0001 125 #define HAMMER_CURSOR_GET_DATA 0x0002 126 #define HAMMER_CURSOR_BACKEND 0x0004 /* cursor run by backend */ 127 #define HAMMER_CURSOR_INSERT 0x0008 /* adjust for insert */ 128 #define HAMMER_CURSOR_DELETE_VISIBILITY 0x0010 /* special del-on-disk recs */ 129 #define HAMMER_CURSOR_END_INCLUSIVE 0x0020 /* key_end is inclusive */ 130 #define HAMMER_CURSOR_END_EXCLUSIVE 0x0040 /* key_end is exclusive (def) */ 131 132 #define HAMMER_CURSOR_ATEDISK 0x0100 133 #define HAMMER_CURSOR_ATEMEM 0x0200 134 #define HAMMER_CURSOR_DISKEOF 0x0400 135 #define HAMMER_CURSOR_MEMEOF 0x0800 136 #define HAMMER_CURSOR_RETEST 0x1000 /* retest current element */ 137 #define HAMMER_CURSOR_MIRROR_FILTERED 0x2000 /* mirror_tid filter */ 138 #define HAMMER_CURSOR_ASOF 0x4000 /* as-of lookup */ 139 #define HAMMER_CURSOR_CREATE_CHECK 0x8000 /* as-of lookup */ 140 141 #define HAMMER_CURSOR_PRUNING 0x00010000 142 #define HAMMER_CURSOR_REBLOCKING 0x00020000 143 #define HAMMER_CURSOR_TRACKED 0x00040000 144 #define HAMMER_CURSOR_TRACKED_RIPOUT 0x00080000 145 #define HAMMER_CURSOR_LASTWASMEM 0x00100000 /* hammer_ip_next logic */ 146 #define HAMMER_CURSOR_ITERATE_CHECK 0x00200000 147 #define HAMMER_CURSOR_NOSWAPCACHE 0x00400000 /* applies to LARGE_DATA */ 148 149 /* 150 * Flags we can clear when reusing a cursor (we can clear all of them) 151 */ 152 #define HAMMER_CURSOR_INITMASK (~0) 153 154 /* 155 * Mirror scan extension structure. Caller sets mirror_tid to restrict 156 * the scan. If the iteration is able to skip one or more internal nodes 157 * it returns an internal node with skip_beg/end set to the skipped range. 158 * 159 * If the first element of an internal node is skipped skip_beg will use 160 * the left_bound inherited from the parent, and the same for the last 161 * element. This is because gaps can develop in the bounds. 162 */ 163 struct hammer_cmirror { 164 hammer_tid_t mirror_tid; 165 struct hammer_base_elm skip_beg; 166 struct hammer_base_elm skip_end; 167 }; 168 169 /* 170 * NOTE: iprec can be NULL, but the address-of does not indirect through 171 * it so we are ok. 172 */ 173 #define hammer_cursor_inmem(cursor) \ 174 ((cursor)->leaf == &(cursor)->iprec->leaf) 175 #define hammer_cursor_ondisk(cursor) \ 176 ((cursor)->leaf != &(cursor)->iprec->leaf) 177 178 #endif /* !VFS_HAMMER_CURSOR_H_ */ 179