2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sys/vfs/hammer/hammer_cursor.h,v 1.23 2008/07/05 18:59:27 dillon Exp $
38 * The hammer_cursor structure is the primary in-memory management structure
39 * for B-Tree operations.
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.
47 * The cursor module maintains a shared lock on cursor->node and
50 struct hammer_cursor
{
52 * Parent B-Tree node, current B-Tree node, and related element
55 hammer_transaction_t trans
;
63 * Set if a deadlock occurs. hammer_done_cursor() will block on
64 * this after releasing parent and node, before returning. See
65 * also hammer_recover_cursor().
67 TAILQ_ENTRY(hammer_cursor
) deadlk_entry
;
68 hammer_node_t deadlk_node
;
69 hammer_record_t deadlk_rec
;
72 * Set along with HAMMER_CURSOR_CREATE_CHECK when doing an as-of
73 * search. If ENOENT is returned and the flag is set, the caller
74 * must iterate with a new delete_tid.
76 hammer_tid_t create_check
;
79 * Pointer to the current node's bounds. Typically points to the
80 * appropriate boundary elements in the parent or points to bounds
81 * stored in the cluster. The right-boundary is range-exclusive.
83 hammer_base_elm_t left_bound
;
84 hammer_base_elm_t right_bound
;
87 * Key or key range governing search. The cursor code may adjust
88 * key_beg/key_end if asof is non-zero.
90 struct hammer_base_elm key_beg
;
91 struct hammer_base_elm key_end
;
93 hammer_tid_t mirror_tid
;
96 * Related data and record references. Note that the related buffers
97 * can be NULL when data and/or record is not, typically indicating
98 * information referenced via an in-memory record.
100 struct hammer_buffer
*record_buffer
; /* record (+ built-in data) */
101 struct hammer_buffer
*data_buffer
; /* extended data */
102 struct hammer_btree_leaf_elm
*leaf
;
103 union hammer_data_ondisk
*data
;
106 * Iteration and extraction control variables
111 * Merged in-memory/on-disk iterations also use these fields.
113 struct hammer_inode
*ip
;
114 struct hammer_record
*iprec
;
117 typedef struct hammer_cursor
*hammer_cursor_t
;
119 #define HAMMER_CURSOR_GET_LEAF 0x0001
120 #define HAMMER_CURSOR_GET_DATA 0x0002
121 #define HAMMER_CURSOR_BACKEND 0x0004 /* cursor run by backend */
122 #define HAMMER_CURSOR_INSERT 0x0008 /* adjust for insert */
123 #define HAMMER_CURSOR_DELETE_VISIBILITY 0x0010 /* special del-on-disk recs */
124 #define HAMMER_CURSOR_END_INCLUSIVE 0x0020 /* key_end is inclusive */
125 #define HAMMER_CURSOR_END_EXCLUSIVE 0x0040 /* key_end is exclusive (def) */
127 #define HAMMER_CURSOR_ATEDISK 0x0100
128 #define HAMMER_CURSOR_ATEMEM 0x0200
129 #define HAMMER_CURSOR_DISKEOF 0x0400
130 #define HAMMER_CURSOR_MEMEOF 0x0800
131 #define HAMMER_CURSOR_DELBTREE 0x1000 /* ip_delete from b-tree */
132 #define HAMMER_CURSOR_MIRROR_FILTERED 0x2000 /* mirror_tid filter */
133 #define HAMMER_CURSOR_ASOF 0x4000 /* as-of lookup */
134 #define HAMMER_CURSOR_CREATE_CHECK 0x8000 /* as-of lookup */
136 #define HAMMER_CURSOR_PRUNING 0x00010000
137 #define HAMMER_CURSOR_REBLOCKING 0x00020000
138 #define HAMMER_CURSOR_DEADLK_RECOVER 0x00040000
139 #define HAMMER_CURSOR_DEADLK_RIPOUT 0x00080000
142 * Flags we can clear when reusing a cursor (we can clear all of them)
144 #define HAMMER_CURSOR_INITMASK (~0)
147 * NOTE: iprec can be NULL, but the address-of does not indirect through
150 #define hammer_cursor_inmem(cursor) \
151 ((cursor)->leaf == &(cursor)->iprec->leaf)
152 #define hammer_cursor_ondisk(cursor) \
153 ((cursor)->leaf != &(cursor)->iprec->leaf)