gitweb.dragonflybsd.org Git - dragonfly.git/blame_incremental

... / ...

Commit	Line	Data
	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.23 2008/07/05 18:59:27 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 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().
	66	*/
	67	TAILQ_ENTRY(hammer_cursor) deadlk_entry;
	68	hammer_node_t deadlk_node;
	69	hammer_record_t deadlk_rec;
	70
	71	/*
	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.
	75	*/
	76	hammer_tid_t create_check;
	77
	78	/*
	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.
	82	*/
	83	hammer_base_elm_t left_bound;
	84	hammer_base_elm_t right_bound;
	85
	86	/*
	87	* Key or key range governing search. The cursor code may adjust
	88	* key_beg/key_end if asof is non-zero.
	89	*/
	90	struct hammer_base_elm key_beg;
	91	struct hammer_base_elm key_end;
	92	hammer_tid_t asof;
	93	hammer_tid_t mirror_tid;
	94
	95	/*
	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.
	99	*/
	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;
	104
	105	/*
	106	* Iteration and extraction control variables
	107	*/
	108	int flags;
	109
	110	/*
	111	* Merged in-memory/on-disk iterations also use these fields.
	112	*/
	113	struct hammer_inode *ip;
	114	struct hammer_record *iprec;
	115	};
	116
	117	typedef struct hammer_cursor *hammer_cursor_t;
	118
	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) */
	126
	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 */
	135
	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
	140
	141	/*
	142	* Flags we can clear when reusing a cursor (we can clear all of them)
	143	*/
	144	#define HAMMER_CURSOR_INITMASK (~0)
	145
	146	/*
	147	* NOTE: iprec can be NULL, but the address-of does not indirect through
	148	* it so we are ok.
	149	*/
	150	#define hammer_cursor_inmem(cursor) \
	151	((cursor)->leaf == &(cursor)->iprec->leaf)
	152	#define hammer_cursor_ondisk(cursor) \
	153	((cursor)->leaf != &(cursor)->iprec->leaf)
	154