sys/vfs/hammer/hammer_btree.h

   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_btree.h,v 1.24 2008/06/26 04:06:22 dillon Exp $
  35  */
  36
  37 /*
  38  * HAMMER B-Tree index
  39  *
  40  * HAMMER implements a modified B+Tree.   B+Trees store records only
  41  * at their leaves and HAMMER's modification is to adjust the internal
  42  * elements so there is a boundary element on each side instead of sub-tree
  43  * pointers.
  44  *
  45  * We just call our modified B+Tree a 'B-Tree' in HAMMER documentation to
  46  * reduce confusion.
  47  *
  48  * A B-Tree internal node looks like this:
  49  *
  50  *      B N N N N N N B   <-- boundary and internal elements
  51  *       S S S S S S S    <-- subtree pointers
  52  *
  53  * A B-Tree leaf node looks like this:
  54  *
  55  *      L L L L L L L L   <-- leaf elemenets
  56  *                            (there is also a previous and next-leaf pointer)
  57  *
  58  * The recursion radix of an internal node is reduced by 1 relative to
  59  * a normal B-Tree in order to accomodate the right-hand boundary.
  60  * The left-hand boundary (B in the left) is integrated into the first
  61  * element so it doesn't require 2 elements to accomodate boundaries.
  62  *
  63  * The big benefit to using a B-Tree with built-in bounds information is
  64  * that it makes it possible to cache pointers into the middle of the tree
  65  * and not have to start searches, insertions, OR deletions at the root node.
  66  * The boundary elements allow searches to progress in a definitive direction
  67  * from any point in the tree without revisting nodes.  It is also possible
  68  * to terminate searches early and make minor adjustments to the boundaries
  69  * (within the confines of the parent's boundaries) on the fly.  This greatly
  70  * improves the efficiency of many operations.
  71  *
  72  * HAMMER B-Trees are per-cluster.  The global multi-cluster B-Tree is
  73  * constructed by allowing internal nodes to link to the roots of other
  74  * clusters.  Fields in the cluster header then reference back to its
  75  * parent and use the cluster generation number to detect stale linkages.
  76  *
  77  * The B-Tree balancing code can operate within a cluster or across the
  78  * filesystem's ENTIRE B-Tree super-structure.  A cluster's B-Tree root
  79  * can be a leaf node in the worse case.  A cluster is guarenteed to have
  80  * sufficient free space to hold a single completely full leaf in the
  81  * degenerate case.
  82  *
  83  * All of the structures below are on-disk structures.
  84  */
  85
  86 /*
  87  * Common base for all B-Tree element types (40 bytes)
  88  *
  89  * obj_type is set to the object type the record represents if an inode,
  90  * directory entry, or an inter-cluster reference.  A cluster range is
  91  * special in that the B-Tree nodes represent a range within the B-Tree
  92  * inclusive of rec_type field, so obj_type must be used to detect the
  93  * cluster range entries.
  94  *
  95  * btype is only used by the elements making up an internal or leaf B-Tree
  96  * node and applies to the node rather then to the key.  This means that
  97  * btype must be assigned/reassigned after any update to the base_elm making
  98  * up a B-Tree element.
  99  */
 100 struct hammer_base_elm {
 101         int64_t obj_id;         /* 00 object record is associated with */
 102         int64_t key;            /* 08 indexing key (offset or namekey) */
 103
 104         hammer_tid_t create_tid; /* 10 transaction id for record creation */
 105         hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
 106
 107         u_int16_t rec_type;     /* 20 _RECTYPE_ */
 108         u_int8_t obj_type;      /* 22 _OBJTYPE_ (restricted) */
 109         u_int8_t btype;         /* 23 B-Tree element type */
 110         u_int32_t localization; /* 24 B-Tree localization parameter */
 111                                 /* 28 */
 112 };
 113
 114 typedef struct hammer_base_elm *hammer_base_elm_t;
 115
 116 /*
 117  * Localization has sorting priority over the obj_id,rec_type,key and
 118  * is used to localize inodes for very fast directory scans.
 119  *
 120  * Localization can also be used to create pseudo-filesystems within
 121  * a HAMMER filesystem.  Pseudo-filesystems would be suitable
 122  * replication targets.
 123  *
 124  * The root inode (not the PFS root inode but the real root) uses
 125  * HAMMER_DEF_LOCALIZATION for its ip->obj_localization.
 126  */
 127 #define HAMMER_LOCALIZE_RESERVED00      0x00000000
 128 #define HAMMER_LOCALIZE_INODE           0x00000001
 129 #define HAMMER_LOCALIZE_MISC            0x00000002
 130 #define HAMMER_LOCALIZE_RESERVED03      0x00000003
 131 #define HAMMER_LOCALIZE_MASK            0x0000FFFF
 132 #define HAMMER_LOCALIZE_PSEUDOFS_MASK   0xFFFF0000
 133 #define HAMMER_LOCALIZE_PSEUDOFS_INC    0x00010000
 134
 135 #define HAMMER_MIN_LOCALIZATION         0x00000000U
 136 #define HAMMER_MAX_LOCALIZATION         0x0000FFFFU
 137 #define HAMMER_DEF_LOCALIZATION         0x00000000U
 138
 139 /*
 140  * Internal element (40 + 24 = 64 bytes).
 141  *
 142  * An internal element contains a recursion to another B-Tree node.
 143  */
 144 struct hammer_btree_internal_elm {
 145         struct hammer_base_elm base;
 146         hammer_tid_t    mirror_tid;             /* mirroring support */
 147         hammer_off_t    subtree_offset;
 148         int32_t         unused02;
 149         int32_t         unused03;
 150 };
 151
 152 typedef struct hammer_btree_internal_elm *hammer_btree_internal_elm_t;
 153
 154 /*
 155  * Leaf B-Tree element (40 + 24 = 64 bytes).
 156  *
 157  * NOTE: create_ts/delete_ts are not used by any core algorithms, they are
 158  *       used only by userland to present nominal real-time date strings
 159  *       to the user.
 160  */
 161 struct hammer_btree_leaf_elm {
 162         struct hammer_base_elm base;
 163         u_int32_t       create_ts;
 164         u_int32_t       delete_ts;
 165         hammer_off_t    data_offset;
 166         int32_t         data_len;
 167         hammer_crc_t    data_crc;
 168 };
 169
 170 typedef struct hammer_btree_leaf_elm *hammer_btree_leaf_elm_t;
 171
 172 /*
 173  * Rollup btree leaf element types - 64 byte structure
 174  */
 175 union hammer_btree_elm {
 176         struct hammer_base_elm          base;
 177         struct hammer_btree_leaf_elm    leaf;
 178         struct hammer_btree_internal_elm internal;
 179 };
 180
 181 typedef union hammer_btree_elm *hammer_btree_elm_t;
 182
 183 /*
 184  * B-Tree node (64x64 = 4K structure)
 185  *
 186  * Each node contains 63 elements.  The last element for an internal node
 187  * is the right-boundary so internal nodes have one fewer logical elements
 188  * then leaf nodes.
 189  *
 190  * 'count' always refers to the number of elements and is non-inclusive of
 191  * the right-hand boundary for an internal node. For a leaf node, 'count'
 192  * refers to the number of elements and there is no idea of boundaries.
 193  *
 194  * The use of a fairly large radix is designed to reduce the number of
 195  * discrete disk accesses required to locate something.  Keep in mind
 196  * that nodes are allocated out of 16K hammer buffers so supported values
 197  * are (256-1), (128-1), (64-1), (32-1), or (16-1). HAMMER uses 63-way
 198  * so the node size is (64x(1+(64-1))) = 4KB.
 199  *
 200  * NOTE: FUTURE EXPANSION: The reserved fields in hammer_node_ondisk are
 201  * reserved for left/right leaf linkage fields, flags, and other future
 202  * features.
 203  */
 204 #define HAMMER_BTREE_LEAF_ELMS  63
 205 #define HAMMER_BTREE_INT_ELMS   (HAMMER_BTREE_LEAF_ELMS - 1)
 206
 207 #define HAMMER_BTREE_TYPE_INTERNAL      ((u_int8_t)'I')
 208 #define HAMMER_BTREE_TYPE_LEAF          ((u_int8_t)'L')
 209 #define HAMMER_BTREE_TYPE_RECORD        ((u_int8_t)'R')
 210 #define HAMMER_BTREE_TYPE_DELETED       ((u_int8_t)'D')
 211
 212 static __inline
 213 int
 214 hammer_node_max_elements(u_int8_t type)
 215 {
 216         switch (type) {
 217         case HAMMER_BTREE_TYPE_LEAF:
 218                 return(HAMMER_BTREE_LEAF_ELMS);
 219         case HAMMER_BTREE_TYPE_INTERNAL:
 220                 return(HAMMER_BTREE_INT_ELMS);
 221         }
 222         return(-1);  /* invalid type */
 223 }
 224
 225 struct hammer_node_ondisk {
 226         /*
 227          * B-Tree node header (64 bytes)
 228          */
 229         hammer_crc_t    crc;            /* MUST BE FIRST FIELD OF STRUCTURE */
 230         u_int32_t       signature;
 231         hammer_off_t    parent;         /* 0 if at root of cluster */
 232         int32_t         count;
 233         u_int8_t        type;
 234         u_int8_t        reserved01;
 235         u_int16_t       reserved02;
 236         hammer_off_t    reserved03;     /* future link_left */
 237         hammer_off_t    reserved04;     /* future link_right */
 238         hammer_off_t    reserved05;
 239         hammer_off_t    reserved06;
 240         hammer_tid_t    mirror_tid;     /* mirroring support (aggregator) */
 241
 242         /*
 243          * Element array.  Internal nodes have one less logical element
 244          * (meaning: the same number of physical elements) in order to
 245          * accomodate the right-hand boundary.  The left-hand boundary
 246          * is integrated into the first element.  Leaf nodes have no
 247          * boundary elements.
 248          */
 249         union hammer_btree_elm elms[HAMMER_BTREE_LEAF_ELMS];
 250 };
 251
 252 #define HAMMER_BTREE_SIGNATURE_GOOD             0xB3A49586
 253 #define HAMMER_BTREE_SIGNATURE_DESTROYED        0x4A3B2C1D
 254 #define HAMMER_BTREE_CRCSIZE    \
 255         (sizeof(struct hammer_node_ondisk) - sizeof(hammer_crc_t))
 256
 257 typedef struct hammer_node_ondisk *hammer_node_ondisk_t;