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_btree.h,v 1.24 2008/06/26 04:06:22 dillon Exp $
37 #ifndef VFS_HAMMER_BTREE_H_
38 #define VFS_HAMMER_BTREE_H_
43 * HAMMER implements a modified B+Tree. B+Trees store records only
44 * at their leaves and HAMMER's modification is to adjust the internal
45 * elements so there is a boundary element on each side instead of sub-tree
48 * We just call our modified B+Tree a 'B-Tree' in HAMMER documentation to
51 * A B-Tree internal node looks like this:
53 * B N N N N N N B <-- boundary and internal elements
54 * S S S S S S S <-- subtree pointers
56 * A B-Tree leaf node looks like this:
58 * L L L L L L L L <-- leaf elemenets
59 * (there is also a previous and next-leaf pointer)
61 * The recursion radix of an internal node is reduced by 1 relative to
62 * a normal B-Tree in order to accomodate the right-hand boundary.
63 * The left-hand boundary (B in the left) is integrated into the first
64 * element so it doesn't require 2 elements to accomodate boundaries.
66 * The big benefit to using a B-Tree with built-in bounds information is
67 * that it makes it possible to cache pointers into the middle of the tree
68 * and not have to start searches, insertions, OR deletions at the root node.
69 * The boundary elements allow searches to progress in a definitive direction
70 * from any point in the tree without revisting nodes. It is also possible
71 * to terminate searches early and make minor adjustments to the boundaries
72 * (within the confines of the parent's boundaries) on the fly. This greatly
73 * improves the efficiency of many operations.
75 * All of the structures below are on-disk structures.
79 * Common base for all B-Tree element types (40 bytes)
81 * The following fields are keys used by hammer_btree_cmp()
82 * to compare B-Tree elements listed from higher priority
83 * to lower priority on comparison.
91 struct hammer_base_elm {
92 int64_t obj_id; /* 00 object record is associated with */
93 int64_t key; /* 08 indexing key (offset or namekey) */
95 hammer_tid_t create_tid; /* 10 transaction id for record creation */
96 hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
98 u_int16_t rec_type; /* 20 _RECTYPE_ */
99 u_int8_t obj_type; /* 22 _OBJTYPE_ (restricted) */
100 u_int8_t btype; /* 23 B-Tree element type */
101 u_int32_t localization; /* 24 B-Tree localization parameter */
105 typedef struct hammer_base_elm *hammer_base_elm_t;
108 * Localization has sorting priority over the obj_id,rec_type,key,tid
109 * and is used to localize inodes for very fast directory scans.
111 * Localization can also be used to create pseudo-filesystems within
112 * a HAMMER filesystem. Pseudo-filesystems would be suitable
113 * replication targets. Upper 16 bits of the localization field in
114 * struct hammer_base_elm represents pseudo-filesystem id, and lower
115 * 16 bits of this field represents its type (inode or misc).
117 * The root inode (not the PFS root inode but the real root) uses
118 * HAMMER_DEF_LOCALIZATION for its incore ip->obj_localization.
119 * HAMMER_DEF_LOCALIZATION implies PFS 0 and no localization type.
121 #define HAMMER_LOCALIZE_RESERVED00 0x00000000
122 #define HAMMER_LOCALIZE_INODE 0x00000001
123 #define HAMMER_LOCALIZE_MISC 0x00000002
124 #define HAMMER_LOCALIZE_RESERVED03 0x00000003
125 #define HAMMER_LOCALIZE_MASK 0x0000FFFF
126 #define HAMMER_LOCALIZE_PSEUDOFS_MASK 0xFFFF0000
128 #define HAMMER_MIN_LOCALIZATION 0x00000000U
129 #define HAMMER_MAX_LOCALIZATION 0x0000FFFFU
130 #define HAMMER_DEF_LOCALIZATION 0x00000000U
133 * Internal element (40 + 24 = 64 bytes).
135 * An internal element contains a recursion to another B-Tree node.
137 struct hammer_btree_internal_elm {
138 struct hammer_base_elm base;
139 hammer_tid_t mirror_tid; /* mirroring support */
140 hammer_off_t subtree_offset;
145 typedef struct hammer_btree_internal_elm *hammer_btree_internal_elm_t;
148 * Leaf B-Tree element (40 + 24 = 64 bytes).
150 * NOTE: create_ts/delete_ts are not used by any core algorithms, they are
151 * used only by userland to present nominal real-time date strings
154 struct hammer_btree_leaf_elm {
155 struct hammer_base_elm base;
158 hammer_off_t data_offset;
160 hammer_crc_t data_crc;
163 typedef struct hammer_btree_leaf_elm *hammer_btree_leaf_elm_t;
166 * Rollup btree leaf element types - 64 byte structure
168 union hammer_btree_elm {
169 struct hammer_base_elm base;
170 struct hammer_btree_leaf_elm leaf;
171 struct hammer_btree_internal_elm internal;
174 typedef union hammer_btree_elm *hammer_btree_elm_t;
177 * B-Tree node (64x64 = 4K structure)
179 * Each node contains 63 elements. The last element for an internal node
180 * is the right-boundary so internal nodes have one fewer logical elements
183 * 'count' always refers to the number of elements and is non-inclusive of
184 * the right-hand boundary for an internal node. For a leaf node, 'count'
185 * refers to the number of elements and there is no idea of boundaries.
187 * The use of a fairly large radix is designed to reduce the number of
188 * discrete disk accesses required to locate something. Keep in mind
189 * that nodes are allocated out of 16K hammer buffers so supported values
190 * are (256-1), (128-1), (64-1), (32-1), or (16-1). HAMMER uses 63-way
191 * so the node size is (64x(1+(64-1))) = 4KB.
193 * NOTE: FUTURE EXPANSION: The reserved fields in hammer_node_ondisk are
194 * reserved for left/right leaf linkage fields, flags, and other future
197 #define HAMMER_BTREE_LEAF_ELMS 63
198 #define HAMMER_BTREE_INT_ELMS (HAMMER_BTREE_LEAF_ELMS - 1)
200 #define HAMMER_BTREE_TYPE_INTERNAL ((u_int8_t)'I')
201 #define HAMMER_BTREE_TYPE_LEAF ((u_int8_t)'L')
202 #define HAMMER_BTREE_TYPE_RECORD ((u_int8_t)'R')
203 #define HAMMER_BTREE_TYPE_DELETED ((u_int8_t)'D')
204 #define HAMMER_BTREE_TYPE_NONE ((u_int8_t)0)
207 * Return 1 if elm is a node element of an internal node,
208 * otherwise return 0.
212 hammer_is_internal_node_elm(hammer_btree_elm_t elm)
214 switch (elm->base.btype) {
215 case HAMMER_BTREE_TYPE_INTERNAL:
216 case HAMMER_BTREE_TYPE_LEAF:
223 * Return 1 if elm is a node element of a leaf node,
224 * otherwise return 0.
228 hammer_is_leaf_node_elm(hammer_btree_elm_t elm)
230 switch (elm->base.btype) {
231 case HAMMER_BTREE_TYPE_RECORD:
239 hammer_node_max_elements(u_int8_t type)
242 case HAMMER_BTREE_TYPE_LEAF:
243 return(HAMMER_BTREE_LEAF_ELMS);
244 case HAMMER_BTREE_TYPE_INTERNAL:
245 return(HAMMER_BTREE_INT_ELMS);
247 return(-1); /* invalid type */
252 hammer_elm_btype(hammer_btree_elm_t elm)
254 switch(elm->base.btype) {
255 case HAMMER_BTREE_TYPE_INTERNAL:
256 case HAMMER_BTREE_TYPE_LEAF:
257 case HAMMER_BTREE_TYPE_RECORD:
258 case HAMMER_BTREE_TYPE_DELETED:
259 return(elm->base.btype); /* ascii */
260 case HAMMER_BTREE_TYPE_NONE:
267 struct hammer_node_ondisk {
269 * B-Tree node header (64 bytes)
271 hammer_crc_t crc; /* MUST BE FIRST FIELD OF STRUCTURE */
272 u_int32_t signature; /* 0 or 0xB3A49586 but not used for anything */
273 hammer_off_t parent; /* 0 if at root of B-Tree */
277 u_int16_t reserved02;
278 hammer_off_t reserved03; /* future link_left */
279 hammer_off_t reserved04; /* future link_right */
280 hammer_off_t reserved05;
281 hammer_off_t reserved06;
282 hammer_tid_t mirror_tid; /* mirroring support (aggregator) */
285 * Element array. Internal nodes have one less logical element
286 * (meaning: the same number of physical elements) in order to
287 * accomodate the right-hand boundary. The left-hand boundary
288 * is integrated into the first element. Leaf nodes have no
291 union hammer_btree_elm elms[HAMMER_BTREE_LEAF_ELMS];
294 #define HAMMER_BTREE_SIGNATURE_GOOD 0xB3A49586
295 #define HAMMER_BTREE_SIGNATURE_DESTROYED 0x4A3B2C1D /* not used */
296 #define HAMMER_BTREE_CRCSIZE \
297 (sizeof(struct hammer_node_ondisk) - sizeof(hammer_crc_t))
299 typedef struct hammer_node_ondisk *hammer_node_ondisk_t;
301 #endif /* !VFS_HAMMER_BTREE_H_ */