4da07e41bb60d344a8bd01e3fec35689beb87a18
[dragonfly.git] / 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