fs/btrfs/ctree.h

   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__ */