1 /* 2 * From linux/fs/btrfs/ctree.h 3 * Copyright (C) 2007,2008 Oracle. All rights reserved. 4 * 5 * Modified in 2017 by Marek Behun, CZ.NIC, marek.behun@nic.cz 6 * 7 * SPDX-License-Identifier: GPL-2.0+ 8 */ 9 10 #ifndef __BTRFS_CTREE_H__ 11 #define __BTRFS_CTREE_H__ 12 13 #include <common.h> 14 #include <compiler.h> 15 #include "btrfs_tree.h" 16 17 #define BTRFS_MAGIC 0x4D5F53665248425FULL /* ascii _BHRfS_M, no null */ 18 19 #define BTRFS_MAX_MIRRORS 3 20 21 #define BTRFS_MAX_LEVEL 8 22 23 #define BTRFS_COMPAT_EXTENT_TREE_V0 24 25 /* 26 * the max metadata block size. This limit is somewhat artificial, 27 * but the memmove costs go through the roof for larger blocks. 28 */ 29 #define BTRFS_MAX_METADATA_BLOCKSIZE 65536 30 31 /* 32 * we can actually store much bigger names, but lets not confuse the rest 33 * of linux 34 */ 35 #define BTRFS_NAME_LEN 255 36 37 /* 38 * Theoretical limit is larger, but we keep this down to a sane 39 * value. That should limit greatly the possibility of collisions on 40 * inode ref items. 41 */ 42 #define BTRFS_LINK_MAX 65535U 43 44 static const int btrfs_csum_sizes[] = { 4 }; 45 46 /* four bytes for CRC32 */ 47 #define BTRFS_EMPTY_DIR_SIZE 0 48 49 /* ioprio of readahead is set to idle */ 50 #define BTRFS_IOPRIO_READA (IOPRIO_PRIO_VALUE(IOPRIO_CLASS_IDLE, 0)) 51 52 #define BTRFS_DIRTY_METADATA_THRESH SZ_32M 53 54 #define BTRFS_MAX_EXTENT_SIZE SZ_128M 55 56 /* 57 * File system states 58 */ 59 #define BTRFS_FS_STATE_ERROR 0 60 #define BTRFS_FS_STATE_REMOUNTING 1 61 #define BTRFS_FS_STATE_TRANS_ABORTED 2 62 #define BTRFS_FS_STATE_DEV_REPLACING 3 63 #define BTRFS_FS_STATE_DUMMY_FS_INFO 4 64 65 #define BTRFS_BACKREF_REV_MAX 256 66 #define BTRFS_BACKREF_REV_SHIFT 56 67 #define BTRFS_BACKREF_REV_MASK (((u64)BTRFS_BACKREF_REV_MAX - 1) << \ 68 BTRFS_BACKREF_REV_SHIFT) 69 70 #define BTRFS_OLD_BACKREF_REV 0 71 #define BTRFS_MIXED_BACKREF_REV 1 72 73 /* 74 * every tree block (leaf or node) starts with this header. 75 */ 76 struct btrfs_header { 77 /* these first four must match the super block */ 78 __u8 csum[BTRFS_CSUM_SIZE]; 79 __u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ 80 __u64 bytenr; /* which block this node is supposed to live in */ 81 __u64 flags; 82 83 /* allowed to be different from the super from here on down */ 84 __u8 chunk_tree_uuid[BTRFS_UUID_SIZE]; 85 __u64 generation; 86 __u64 owner; 87 __u32 nritems; 88 __u8 level; 89 } __attribute__ ((__packed__)); 90 91 /* 92 * this is a very generous portion of the super block, giving us 93 * room to translate 14 chunks with 3 stripes each. 94 */ 95 #define BTRFS_SYSTEM_CHUNK_ARRAY_SIZE 2048 96 97 /* 98 * just in case we somehow lose the roots and are not able to mount, 99 * we store an array of the roots from previous transactions 100 * in the super. 101 */ 102 #define BTRFS_NUM_BACKUP_ROOTS 4 103 struct btrfs_root_backup { 104 __u64 tree_root; 105 __u64 tree_root_gen; 106 107 __u64 chunk_root; 108 __u64 chunk_root_gen; 109 110 __u64 extent_root; 111 __u64 extent_root_gen; 112 113 __u64 fs_root; 114 __u64 fs_root_gen; 115 116 __u64 dev_root; 117 __u64 dev_root_gen; 118 119 __u64 csum_root; 120 __u64 csum_root_gen; 121 122 __u64 total_bytes; 123 __u64 bytes_used; 124 __u64 num_devices; 125 /* future */ 126 __u64 unused_64[4]; 127 128 __u8 tree_root_level; 129 __u8 chunk_root_level; 130 __u8 extent_root_level; 131 __u8 fs_root_level; 132 __u8 dev_root_level; 133 __u8 csum_root_level; 134 /* future and to align */ 135 __u8 unused_8[10]; 136 } __attribute__ ((__packed__)); 137 138 /* 139 * the super block basically lists the main trees of the FS 140 * it currently lacks any block count etc etc 141 */ 142 struct btrfs_super_block { 143 __u8 csum[BTRFS_CSUM_SIZE]; 144 /* the first 4 fields must match struct btrfs_header */ 145 __u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ 146 __u64 bytenr; /* this block number */ 147 __u64 flags; 148 149 /* allowed to be different from the btrfs_header from here own down */ 150 __u64 magic; 151 __u64 generation; 152 __u64 root; 153 __u64 chunk_root; 154 __u64 log_root; 155 156 /* this will help find the new super based on the log root */ 157 __u64 log_root_transid; 158 __u64 total_bytes; 159 __u64 bytes_used; 160 __u64 root_dir_objectid; 161 __u64 num_devices; 162 __u32 sectorsize; 163 __u32 nodesize; 164 __u32 __unused_leafsize; 165 __u32 stripesize; 166 __u32 sys_chunk_array_size; 167 __u64 chunk_root_generation; 168 __u64 compat_flags; 169 __u64 compat_ro_flags; 170 __u64 incompat_flags; 171 __u16 csum_type; 172 __u8 root_level; 173 __u8 chunk_root_level; 174 __u8 log_root_level; 175 struct btrfs_dev_item dev_item; 176 177 char label[BTRFS_LABEL_SIZE]; 178 179 __u64 cache_generation; 180 __u64 uuid_tree_generation; 181 182 /* future expansion */ 183 __u64 reserved[30]; 184 __u8 sys_chunk_array[BTRFS_SYSTEM_CHUNK_ARRAY_SIZE]; 185 struct btrfs_root_backup super_roots[BTRFS_NUM_BACKUP_ROOTS]; 186 } __attribute__ ((__packed__)); 187 188 /* 189 * Compat flags that we support. If any incompat flags are set other than the 190 * ones specified below then we will fail to mount 191 */ 192 #define BTRFS_FEATURE_COMPAT_SUPP 0ULL 193 #define BTRFS_FEATURE_COMPAT_SAFE_SET 0ULL 194 #define BTRFS_FEATURE_COMPAT_SAFE_CLEAR 0ULL 195 196 #define BTRFS_FEATURE_COMPAT_RO_SUPP \ 197 (BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE | \ 198 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE_VALID) 199 200 #define BTRFS_FEATURE_COMPAT_RO_SAFE_SET 0ULL 201 #define BTRFS_FEATURE_COMPAT_RO_SAFE_CLEAR 0ULL 202 203 #define BTRFS_FEATURE_INCOMPAT_SUPP \ 204 (BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF | \ 205 BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \ 206 BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS | \ 207 BTRFS_FEATURE_INCOMPAT_BIG_METADATA | \ 208 BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO | \ 209 BTRFS_FEATURE_INCOMPAT_RAID56 | \ 210 BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF | \ 211 BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA | \ 212 BTRFS_FEATURE_INCOMPAT_NO_HOLES) 213 214 #define BTRFS_FEATURE_INCOMPAT_SAFE_SET \ 215 (BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 216 #define BTRFS_FEATURE_INCOMPAT_SAFE_CLEAR 0ULL 217 218 /* 219 * A leaf is full of items. offset and size tell us where to find 220 * the item in the leaf (relative to the start of the data area) 221 */ 222 struct btrfs_item { 223 struct btrfs_key key; 224 __u32 offset; 225 __u32 size; 226 } __attribute__ ((__packed__)); 227 228 /* 229 * leaves have an item area and a data area: 230 * [item0, item1....itemN] [free space] [dataN...data1, data0] 231 * 232 * The data is separate from the items to get the keys closer together 233 * during searches. 234 */ 235 struct btrfs_leaf { 236 struct btrfs_header header; 237 struct btrfs_item items[]; 238 } __attribute__ ((__packed__)); 239 240 /* 241 * all non-leaf blocks are nodes, they hold only keys and pointers to 242 * other blocks 243 */ 244 struct btrfs_key_ptr { 245 struct btrfs_key key; 246 __u64 blockptr; 247 __u64 generation; 248 } __attribute__ ((__packed__)); 249 250 struct btrfs_node { 251 struct btrfs_header header; 252 struct btrfs_key_ptr ptrs[]; 253 } __attribute__ ((__packed__)); 254 255 union btrfs_tree_node { 256 struct btrfs_header header; 257 struct btrfs_leaf leaf; 258 struct btrfs_node node; 259 }; 260 261 typedef __u8 u8; 262 typedef __u16 u16; 263 typedef __u32 u32; 264 typedef __u64 u64; 265 266 struct btrfs_path { 267 union btrfs_tree_node *nodes[BTRFS_MAX_LEVEL]; 268 u32 slots[BTRFS_MAX_LEVEL]; 269 }; 270 271 struct btrfs_root { 272 u64 objectid; 273 u64 bytenr; 274 u64 root_dirid; 275 }; 276 277 int btrfs_comp_keys(struct btrfs_key *, struct btrfs_key *); 278 int btrfs_comp_keys_type(struct btrfs_key *, struct btrfs_key *); 279 int btrfs_bin_search(union btrfs_tree_node *, struct btrfs_key *, int *); 280 void btrfs_free_path(struct btrfs_path *); 281 int btrfs_search_tree(const struct btrfs_root *, struct btrfs_key *, 282 struct btrfs_path *); 283 int btrfs_prev_slot(struct btrfs_path *); 284 int btrfs_next_slot(struct btrfs_path *); 285 286 static inline struct btrfs_key *btrfs_path_leaf_key(struct btrfs_path *p) { 287 return &p->nodes[0]->leaf.items[p->slots[0]].key; 288 } 289 290 static inline struct btrfs_key * 291 btrfs_search_tree_key_type(const struct btrfs_root *root, u64 objectid, 292 u8 type, struct btrfs_path *path) 293 { 294 struct btrfs_key key, *res; 295 296 key.objectid = objectid; 297 key.type = type; 298 key.offset = 0; 299 300 if (btrfs_search_tree(root, &key, path)) 301 return NULL; 302 303 res = btrfs_path_leaf_key(path); 304 if (btrfs_comp_keys_type(&key, res)) { 305 btrfs_free_path(path); 306 return NULL; 307 } 308 309 return res; 310 } 311 312 static inline u32 btrfs_path_item_size(struct btrfs_path *p) 313 { 314 return p->nodes[0]->leaf.items[p->slots[0]].size; 315 } 316 317 static inline void *btrfs_leaf_data(struct btrfs_leaf *leaf, u32 slot) 318 { 319 return ((u8 *) leaf) + sizeof(struct btrfs_header) 320 + leaf->items[slot].offset; 321 } 322 323 static inline void *btrfs_path_leaf_data(struct btrfs_path *p) 324 { 325 return btrfs_leaf_data(&p->nodes[0]->leaf, p->slots[0]); 326 } 327 328 #define btrfs_item_ptr(l,s,t) \ 329 ((t *) btrfs_leaf_data((l),(s))) 330 331 #define btrfs_path_item_ptr(p,t) \ 332 ((t *) btrfs_path_leaf_data((p))) 333 334 #endif /* __BTRFS_CTREE_H__ */ 335