/* * Copyright (c) 2007 The DragonFly Project. All rights reserved. * * This code is derived from software contributed to The DragonFly Project * by Matthew Dillon <dillon@backplane.com> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * 3. Neither the name of The DragonFly Project nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific, prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $DragonFly: src/sys/vfs/hammer/hammer_btree.h,v 1.24 2008/06/26 04:06:22 dillon Exp $ */ #ifndef VFS_HAMMER_BTREE_H_ #define VFS_HAMMER_BTREE_H_ /* * HAMMER B-Tree index * * HAMMER implements a modified B+Tree. B+Trees store records only * at their leaves and HAMMER's modification is to adjust the internal * elements so there is a boundary element on each side instead of sub-tree * pointers. * * We just call our modified B+Tree a 'B-Tree' in HAMMER documentation to * reduce confusion. * * A B-Tree internal node looks like this: * * B N N N N N N B <-- boundary and internal elements * S S S S S S S <-- subtree pointers * * A B-Tree leaf node looks like this: * * L L L L L L L L <-- leaf elemenets * (there is also a previous and next-leaf pointer) * * The recursion radix of an internal node is reduced by 1 relative to * a normal B-Tree in order to accomodate the right-hand boundary. * The left-hand boundary (B in the left) is integrated into the first * element so it doesn't require 2 elements to accomodate boundaries. * * The big benefit to using a B-Tree with built-in bounds information is * that it makes it possible to cache pointers into the middle of the tree * and not have to start searches, insertions, OR deletions at the root node. * The boundary elements allow searches to progress in a definitive direction * from any point in the tree without revisting nodes. It is also possible * to terminate searches early and make minor adjustments to the boundaries * (within the confines of the parent's boundaries) on the fly. This greatly * improves the efficiency of many operations. * * All of the structures below are on-disk structures. */ /* * Common base for all B-Tree element types (40 bytes) * * btype field represents a type of B-Tree ondisk structure that this * B-Tree element points to, but not a type of B-Tree node that this * B-Tree element is a part of. btype could be HAMMER_BTREE_TYPE_RECORD * as well as HAMMER_BTREE_TYPE_INTERNAL and HAMMER_BTREE_TYPE_LEAF, * while B-Tree node type is never HAMMER_BTREE_TYPE_RECORD. * * The following fields are keys used by hammer_btree_cmp() to compare * B-Tree elements listed from higher to lower priority on comparison. * B-Tree elements are first grouped by localization value, and then * obj_id within a subtree of the same localization value, and so on. * * 1. localization * 2. obj_id * 3. rec_type * 4. key * 5. create_tid */ typedef struct hammer_base_elm { int64_t obj_id; /* 00 object record is associated with */ int64_t key; /* 08 indexing key (offset or namekey) */ hammer_tid_t create_tid; /* 10 transaction id for record creation */ hammer_tid_t delete_tid; /* 18 transaction id for record update/del */ uint16_t rec_type; /* 20 HAMMER_RECTYPE_ */ uint8_t obj_type; /* 22 HAMMER_OBJTYPE_ */ uint8_t btype; /* 23 B-Tree element type */ uint32_t localization; /* 24 B-Tree localization parameter */ /* 28 */ } *hammer_base_elm_t; /* * Localization has sorting priority over the obj_id,rec_type,key,tid * and is used to localize inodes for very fast directory scans. * * Localization can also be used to create pseudo-filesystems within * a HAMMER filesystem. Pseudo-filesystems would be suitable * replication targets. * * Upper 16 bits of the localization field in struct hammer_base_elm * represents pseudo-filesystem id ranging from default 0 to 65535, * and lower 16 bits represents its localization type in bitfield * where 0x1 means the element is for inode and 0x2 means the element * is for anything other than inode. Note that 0x3 (0x1|0x2) is not * a valid type, while 0 and 0xFFFF are valid types for some cases. * * The root inode (not the PFS root inode but the real root) uses * HAMMER_DEF_LOCALIZATION for its incore ip->obj_localization. * HAMMER_DEF_LOCALIZATION implies PFS#0 and no localization type. */ #define HAMMER_LOCALIZE_INODE 0x00000001 #define HAMMER_LOCALIZE_MISC 0x00000002 /* not inode */ #define HAMMER_LOCALIZE_MASK 0x0000FFFF #define HAMMER_LOCALIZE_PSEUDOFS_MASK 0xFFFF0000 #define HAMMER_MIN_LOCALIZATION 0x00000000U #define HAMMER_MAX_LOCALIZATION 0x0000FFFFU #define HAMMER_DEF_LOCALIZATION 0x00000000U #define HAMMER_MIN_ONDISK_LOCALIZATION \ HAMMER_MIN_LOCALIZATION #define HAMMER_MAX_ONDISK_LOCALIZATION \ (HAMMER_MAX_LOCALIZATION | HAMMER_LOCALIZE_PSEUDOFS_MASK) #define lo_to_pfs(lo) \ ((int)(((lo) & HAMMER_LOCALIZE_PSEUDOFS_MASK) >> 16)) #define pfs_to_lo(pfs) \ ((((uint32_t)(pfs)) << 16) & HAMMER_LOCALIZE_PSEUDOFS_MASK) /* * Internal element (40 + 24 = 64 bytes). * * An internal element contains a recursion to another B-Tree node. */ typedef struct hammer_btree_internal_elm { struct hammer_base_elm base; hammer_tid_t mirror_tid; /* mirroring support */ hammer_off_t subtree_offset; int32_t reserved01; int32_t reserved02; } *hammer_btree_internal_elm_t; /* * Leaf B-Tree element (40 + 24 = 64 bytes). * * NOTE: create_ts/delete_ts are not used by any core algorithms, they are * used only by userland to present nominal real-time date strings * to the user. */ typedef struct hammer_btree_leaf_elm { struct hammer_base_elm base; uint32_t create_ts; uint32_t delete_ts; hammer_off_t data_offset; int32_t data_len; hammer_crc_t data_crc; } *hammer_btree_leaf_elm_t; /* * Rollup btree leaf element types - 64 byte structure */ typedef union hammer_btree_elm { struct hammer_base_elm base; struct hammer_btree_leaf_elm leaf; struct hammer_btree_internal_elm internal; } *hammer_btree_elm_t; /* * B-Tree node (64x64 = 4K structure) * * Each node contains 63 elements. The last element for an internal node * is the right-boundary so internal nodes have one fewer logical elements * then leaf nodes. * * 'count' always refers to the number of elements and is non-inclusive of * the right-hand boundary for an internal node. For a leaf node, 'count' * refers to the number of elements and there is no idea of boundaries. * * The use of a fairly large radix is designed to reduce the number of * discrete disk accesses required to locate something. Keep in mind * that nodes are allocated out of 16K hammer buffers so supported values * are (256-1), (128-1), (64-1), (32-1), or (16-1). HAMMER uses 63-way * so the node size is (64x(1+(64-1))) = 4KB. * * NOTE: FUTURE EXPANSION: The reserved fields in hammer_node_ondisk are * reserved for left/right leaf linkage fields, flags, and other future * features. */ #define HAMMER_BTREE_TYPE_INTERNAL ((uint8_t)'I') #define HAMMER_BTREE_TYPE_LEAF ((uint8_t)'L') #define HAMMER_BTREE_TYPE_RECORD ((uint8_t)'R') #define HAMMER_BTREE_TYPE_DELETED ((uint8_t)'D') #define HAMMER_BTREE_TYPE_NONE ((uint8_t)0) #define HAMMER_BTREE_LEAF_ELMS 63 #define HAMMER_BTREE_INT_ELMS (HAMMER_BTREE_LEAF_ELMS - 1) typedef struct hammer_node_ondisk { /* * B-Tree node header (64 bytes) */ hammer_crc_t crc; /* MUST BE FIRST FIELD OF STRUCTURE */ uint32_t reserved01; hammer_off_t parent; /* 0 if at root of B-Tree */ int32_t count; /* maximum 62 for INTERNAL, 63 for LEAF */ uint8_t type; /* B-Tree node type (INTERNAL or LEAF) */ uint8_t reserved02; uint16_t reserved03; hammer_off_t reserved04; hammer_off_t reserved05; hammer_off_t reserved06; hammer_off_t reserved07; hammer_tid_t mirror_tid; /* mirroring support (aggregator) */ /* * B-Tree node element array (64x63 bytes) * * Internal nodes have one less logical element * (meaning: the same number of physical elements) in order to * accomodate the right-hand boundary. The left-hand boundary * is integrated into the first element. Leaf nodes have no * boundary elements. */ union hammer_btree_elm elms[HAMMER_BTREE_LEAF_ELMS]; } *hammer_node_ondisk_t; #define HAMMER_BTREE_CRCSIZE \ (sizeof(struct hammer_node_ondisk) - sizeof(hammer_crc_t)) /* * Return 1 if elm is a node element of an internal node, * otherwise return 0. */ static __inline int hammer_is_internal_node_elm(hammer_btree_elm_t elm) { switch (elm->base.btype) { case HAMMER_BTREE_TYPE_INTERNAL: case HAMMER_BTREE_TYPE_LEAF: return(1); } return(0); } /* * Return 1 if elm is a node element of a leaf node, * otherwise return 0. */ static __inline int hammer_is_leaf_node_elm(hammer_btree_elm_t elm) { switch (elm->base.btype) { case HAMMER_BTREE_TYPE_RECORD: return(1); } return(0); } static __inline int hammer_node_max_elements(uint8_t type) { switch (type) { case HAMMER_BTREE_TYPE_LEAF: return(HAMMER_BTREE_LEAF_ELMS); case HAMMER_BTREE_TYPE_INTERNAL: return(HAMMER_BTREE_INT_ELMS); } return(-1); /* invalid type */ } static __inline char hammer_elm_btype(hammer_btree_elm_t elm) { switch(elm->base.btype) { case HAMMER_BTREE_TYPE_INTERNAL: case HAMMER_BTREE_TYPE_LEAF: case HAMMER_BTREE_TYPE_RECORD: case HAMMER_BTREE_TYPE_DELETED: return(elm->base.btype); /* ascii */ case HAMMER_BTREE_TYPE_NONE: return('*'); default: return('?'); } } #endif /* !VFS_HAMMER_BTREE_H_ */
