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.2 2007/10/12 18:57:45 dillon Exp $
  35  */
  36
  37 /*
  38  * HAMMER B-Tree index
  39  *
  40  * rec_type is the record type for a leaf node or an extended record type
  41  * for internal btree nodes and cluster references.
  42  *
  43  * A B-Tree diving down into a new cluster will have two B-Tree elements
  44  * indicating the full sub-range stored in that cluster.  These elements
  45  * will match the elements stored in the cluster header.
  46  */
  47
  48 /*
  49  * Common base for all B+Tree element types (40 bytes)
  50  *
  51  * Note that obj_type is set to the object type of the record represents
  52  * an inode or a cluster range.  A cluster range is special in that the
  53  * B-Tree nodes represent a range within the B-Tree inclusive of rec_type
  54  * field, so obj_type must be used to detect the cluster range entries.
  55  */
  56 struct hammer_base_elm {
  57         int64_t obj_id;         /* 00 object record is associated with */
  58         int64_t key;            /* 08 indexing key (offset or namekey) */
  59
  60         hammer_tid_t create_tid; /* 10 transaction id for record creation */
  61         hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
  62
  63         u_int16_t rec_type;     /* 20 */
  64         u_int16_t obj_type;     /* 22 (special) */
  65         int32_t subtree_offset; /* 24 (B+Tree recursion) */
  66                                 /* 28 */
  67 };
  68
  69 /*
  70  * Leaf B-Tree element (40 + 16 = 56 bytes)
  71  */
  72 struct hammer_record_elm {
  73         struct hammer_base_elm base;
  74         int32_t rec_offset;
  75         int32_t data_offset;
  76         int32_t data_len;
  77         u_int32_t data_crc;
  78 };
  79
  80 /*
  81  * Leaf Cluster-reference B-Tree element (40 + 16 = 56 bytes)
  82  */
  83 struct hammer_cluster_elm {
  84         struct hammer_base_elm base;
  85         int32_t rec_offset;             /* cluster recursion record */
  86         u_int32_t verifier;             /* low 32 bits of target clu_id */
  87         int32_t vol_no;
  88         int32_t cluster_no;
  89 };
  90
  91 /*
  92  * Rollup btree element types - 56 byte structure
  93  */
  94 union hammer_btree_elm {
  95         struct hammer_base_elm base;
  96         struct hammer_record_elm record;
  97         struct hammer_cluster_elm cluster;
  98 };
  99
 100 /*
 101  * B-Tree node (normal or meta) - 56 + 56 * 8 = 504 bytes
 102  *
 103  * 32 B-Tree nodes fit in a 16K filesystem buffer.  Remember, the filesystem
 104  * buffer has a 128 byte header so (16384 - 128) / 32 = 508, but we want
 105  * our structures to be 8-byte aligned so we use 504.
 106  */
 107 #define HAMMER_BTREE_ELMS       8
 108
 109 struct hammer_btree_node {
 110         /*
 111          * B-Tree node header (56 bytes)
 112          */
 113         int32_t         count;  /* number of elements in B-Tree node */
 114         int32_t         parent; /* parent B-Tree node in current cluster */
 115         u_int32_t       reserved[12];
 116
 117         /*
 118          * 8 elements making up the B-Tree node 56x8 = 448 bytes
 119          */
 120         union hammer_btree_elm elms[HAMMER_BTREE_ELMS];
 121 };
 122
 123 /*
 124  * B-Tree filesystem buffer
 125  */
 126 #define HAMMER_BTREE_NODES              \
 127         ((HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head)) / \
 128         sizeof(struct hammer_btree_node))
 129
 130 struct hammer_fsbuf_btree {
 131         struct hammer_fsbuf_head        head;
 132         char                            unused[128];
 133         struct hammer_btree_node        nodes[HAMMER_BTREE_NODES];
 134 };
 135
 136