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