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.9 2008/01/17 05:06:09 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  *
  61  * The big benefit to using a B-Tree with built-in bounds information is
  62  * that it makes it possible to cache pointers into the middle of the tree
  63  * and not have to start searches, insertions, OR deletions at the root node.
  64  * The boundary elements allow searches to progress in a definitive direction
  65  * from any point in the tree without revisting nodes.  It is also possible
  66  * to terminate searches early and make minor adjustments to the boundaries
  67  * (within the confines of the parent's boundaries) on the fly.  This greatly
  68  * improves the efficiency of many operations, most especially record appends.
  69  *
  70  * HAMMER B-Trees are per-cluster.  The global multi-cluster B-Tree is
  71  * constructed by allowing internal nodes to link to the roots of other
  72  * clusters.  Fields in the cluster header then reference back to its
  73  * parent and use the cluster generation number to detect stale linkages.
  74  *
  75  * The B-Tree balancing code can operate within a cluster or across the
  76  * filesystem's ENTIRE B-Tree super-structure.  A cluster's B-Tree root
  77  * can be a leaf node in the worse case.  A cluster is guarenteed to have
  78  * sufficient free space to hold a single completely full leaf in the
  79  * degenerate case.
  80  *
  81  * All of the structures below are on-disk structures.
  82  */
  83
  84 /*
  85  * Common base for all B-Tree element types (40 bytes)
  86  *
  87  * obj_type is set to the object type the record represents if an inode,
  88  * directory entry, or an inter-cluster reference.  A cluster range is
  89  * special in that the B-Tree nodes represent a range within the B-Tree
  90  * inclusive of rec_type field, so obj_type must be used to detect the
  91  * cluster range entries.
  92  *
  93  * btype is only used by the elements making up an internal or leaf B-Tree
  94  * node and applies to the node rather then to the key.  This means that
  95  * btype must be assigned/reassigned after any update to the base_elm making
  96  * up a B-Tree element.
  97  */
  98 struct hammer_base_elm {
  99         int64_t obj_id;         /* 00 object record is associated with */
 100         int64_t key;            /* 08 indexing key (offset or namekey) */
 101
 102         hammer_tid_t create_tid; /* 10 transaction id for record creation */
 103         hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
 104
 105         u_int16_t rec_type;     /* 20 _RECTYPE_ */
 106         u_int8_t obj_type;      /* 22 _OBJTYPE_ (restricted) */
 107         u_int8_t btype;         /* 23 B-Tree element type */
 108         int32_t reserved07;     /* 24 (future) */
 109                                 /* 28 */
 110 };
 111
 112 typedef struct hammer_base_elm *hammer_base_elm_t;
 113
 114 /*
 115  * Internal element (40 + 16 = 56 bytes).
 116  *
 117  * An internal element contains the left-hand boundary, right-hand boundary,
 118  * and a recursion to another B-Tree node.
 119  */
 120 struct hammer_btree_internal_elm {
 121         struct hammer_base_elm base;
 122         int32_t unused00;
 123         int32_t subtree_offset; /* cluster relative offset */
 124         int32_t unused02;
 125         int32_t unused03;
 126 };
 127
 128 /*
 129  * Leaf B-Tree element (40 + 16 = 56 bytes).
 130  *
 131  * A leaf element.  Note that the data_offset, data_len, and data_crc
 132  * fields only apply to HAMMER_BTREE_TYPE_RECORD subtree_type's.  These
 133  * fields are overloaded for spike elements.
 134  */
 135 struct hammer_btree_leaf_elm {
 136         struct hammer_base_elm base;
 137         int32_t rec_offset;
 138         int32_t data_offset;
 139         int32_t data_len;
 140         u_int32_t data_crc;
 141 };
 142
 143 #define spike_clu_no    data_offset
 144 #define spike_vol_no    data_len
 145 #define spike_unused01  data_crc
 146
 147 /*
 148  * Rollup btree leaf element types - 56 byte structure
 149  */
 150 union hammer_btree_elm {
 151         struct hammer_base_elm base;
 152         struct hammer_btree_leaf_elm leaf;
 153         struct hammer_btree_internal_elm internal;
 154 };
 155
 156 typedef union hammer_btree_elm *hammer_btree_elm_t;
 157
 158 /*
 159  * B-Tree node (normal or meta) - 24 + 56 * 14 = 808 bytes (8-byte aligned)
 160  *
 161  * 20 B-Tree nodes fit in a 16K filesystem buffer, leaving us room for
 162  * the 128 byte filesystem buffer header and another 96 bytes of filler.
 163  *
 164  * Each node contains 14 elements.  The last element for an internal node
 165  * is the right-boundary so internal nodes have one fewer logical elements
 166  * then leaf nodes.
 167  *
 168  * 'count' always refers to the number of elements and is non-inclusive of
 169  * the right-hand boundary for an internal node.
 170  *
 171  * NOTE: The node head for an internal does not contain the subtype
 172  * (The B-Tree node type for the nodes referenced by its elements).
 173  * Instead, each element specifies the subtype (elm->base.subtype).
 174  * This allows us to maintain an unbalanced B-Tree and to easily identify
 175  * special inter-cluster link elements.
 176  */
 177 #define HAMMER_BTREE_LEAF_ELMS  14
 178 #define HAMMER_BTREE_INT_ELMS   (HAMMER_BTREE_LEAF_ELMS - 1)
 179 #define HAMMER_BTREE_NODES      20
 180
 181 /*
 182  * It is safe to combine two adjacent nodes if the total number of elements
 183  * is less then or equal to the *_FILL constant.
 184  */
 185 #define HAMMER_BTREE_LEAF_FILL  (HAMMER_BTREE_LEAF_ELMS - 3)
 186 #define HAMMER_BTREE_INT_FILL   (HAMMER_BTREE_INT_ELMS - 3)
 187
 188 #define HAMMER_BTREE_TYPE_INTERNAL      ((u_int8_t)'I')
 189 #define HAMMER_BTREE_TYPE_LEAF          ((u_int8_t)'L')
 190 #define HAMMER_BTREE_TYPE_RECORD        ((u_int8_t)'R')
 191 #define HAMMER_BTREE_TYPE_SPIKE_BEG     ((u_int8_t)'C')
 192 #define HAMMER_BTREE_TYPE_SPIKE_END     ((u_int8_t)'E')
 193
 194 struct hammer_node_ondisk {
 195         /*
 196          * B-Tree node header (24 bytes)
 197          */
 198         int32_t         count;
 199         int32_t         parent;         /* 0 if at root of cluster */
 200         u_int8_t        type;
 201         u_int8_t        reserved01;
 202         u_int16_t       reserved02;
 203         int32_t         reserved03;     /* future heuristic */
 204         int32_t         reserved04;     /* future link_left */
 205         int32_t         reserved05;     /* future link_right */
 206
 207         /*
 208          * Element array.  Internal nodes have one less logical element
 209          * (meaning: the same number of physical elements) in order to
 210          * accomodate the right-hand boundary.  The left-hand boundary
 211          * is integrated into the first element.  Leaf nodes have no
 212          * boundary elements.
 213          */
 214         union hammer_btree_elm elms[HAMMER_BTREE_LEAF_ELMS];
 215 };
 216
 217 typedef struct hammer_node_ondisk *hammer_node_ondisk_t;
 218
 219 /*
 220  * B-Tree filesystem buffer (16K exactly)
 221  */
 222 struct hammer_fsbuf_btree {
 223         struct hammer_fsbuf_head        head;           /* 128 */
 224         char                            filler[96];
 225         struct hammer_node_ondisk       nodes[HAMMER_BTREE_NODES];
 226 };
 227
 228 #if HAMMER_BTREE_NODES * (HAMMER_BTREE_LEAF_ELMS * 56 + 24) + 128 + 96 != 16384
 229 #error "Sanity check hammer_fsbuf_btree"
 230 #endif