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.1 2007/10/10 19:37:25 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 struct hammer_base_elm {
  52         int64_t obj_id;         /* 00 object record is associated with */
  53         int64_t key;            /* 08 indexing key (offset or namekey) */
  54
  55         hammer_tid_t create_tid; /* 10 transaction id for record creation */
  56         hammer_tid_t delete_tid; /* 18 transaction id for record update/del */
  57
  58         u_int16_t rec_type;     /* 20 */
  59         u_int16_t obj_type;     /* 22 (only if rec_type is an inode) */
  60         u_int32_t reserved01;   /* 24 */
  61                                 /* 28 */
  62 };
  63
  64 /*
  65  * Internal B-Tree element (40 + 16 = 56 bytes)
  66  */
  67 struct hammer_internal_elm {
  68         struct hammer_base_elm base;
  69         int32_t subtree_offset;
  70         u_int32_t reserved01;
  71         u_int32_t reserved02;
  72         u_int32_t reserved03;
  73
  74 };
  75
  76 /*
  77  * Leaf B-Tree element (40 + 16 = 56 bytes)
  78  */
  79 struct hammer_leaf_elm {
  80         struct hammer_base_elm base;
  81         int32_t rec_offset;
  82         int32_t data_offset;
  83         int32_t data_len;
  84         u_int32_t data_crc;
  85 };
  86
  87 /*
  88  * Leaf Cluster-reference B-Tree element (40 + 16 = 56 bytes)
  89  */
  90 struct hammer_cluster_elm {
  91         struct hammer_base_elm base;
  92         u_int64_t clu_id;               /* cluster id (sanity check) */
  93         u_int32_t vol_no;
  94         u_int32_t cluster_no;
  95 };
  96
  97 /*
  98  * Rollup btree element types - 56 byte structure
  99  */
 100 union hammer_btree_elm {
 101         struct hammer_base_elm base;
 102         struct hammer_internal_elm internal;
 103         struct hammer_leaf_elm leaf;
 104         struct hammer_cluster_elm cluster;
 105 };
 106
 107 /*
 108  * B-Tree node (normal or meta) - 56 + 56 * 8 = 504 bytes
 109  *
 110  * 32 B-Tree nodes fit in a 16K filesystem buffer.  Remember, the filesystem
 111  * buffer has a 128 byte header so (16384 - 128) / 32 = 508, but we want
 112  * our structures to be 8-byte aligned so we use 504.
 113  */
 114 #define HAMMER_BTREE_ELMS       8
 115
 116 struct hammer_btree_node {
 117         /*
 118          * B-Tree node header (56 bytes)
 119          */
 120         int32_t         count;  /* number of elements in B-Tree node */
 121         u_int32_t       parent; /* parent B-Tree node in current cluster */
 122         u_int32_t       reserved[12];
 123
 124         /*
 125          * 8 elements making up the B-Tree node 56x8 = 448 bytes
 126          */
 127         union hammer_btree_elm elms[HAMMER_BTREE_ELMS];
 128 };
 129
 130 /*
 131  * B-Tree filesystem buffer
 132  */
 133 #define HAMMER_BTREE_NODES              \
 134         ((HAMMER_BUFSIZE - sizeof(struct hammer_fsbuf_head)) / \
 135         sizeof(struct hammer_btree_node))
 136
 137 struct hammer_fsbuf_btree {
 138         struct hammer_fsbuf_head        head;
 139         char                            unused[128];
 140         struct hammer_btree_node        nodes[HAMMER_BTREE_NODES];
 141 };
 142
 143