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 137