blob: 65c152a52fcf535a5b93865eea08ba2af6d2eb16 [file] [log] [blame]
Tom Rini83d290c2018-05-06 17:58:06 -04001/* SPDX-License-Identifier: GPL-2.0+ */
Marek Behúnd4a704a2017-09-03 17:00:26 +02002/*
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
Marek Behúnd4a704a2017-09-03 17:00:26 +02007 */
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
43static 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 */
75struct 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
102struct 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 */
141struct 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 */
221struct 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 */
234struct 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 */
243struct btrfs_key_ptr {
244 struct btrfs_key key;
245 __u64 blockptr;
246 __u64 generation;
247} __attribute__ ((__packed__));
248
249struct btrfs_node {
250 struct btrfs_header header;
251 struct btrfs_key_ptr ptrs[];
252} __attribute__ ((__packed__));
253
254union btrfs_tree_node {
255 struct btrfs_header header;
256 struct btrfs_leaf leaf;
257 struct btrfs_node node;
258};
259
260typedef __u8 u8;
261typedef __u16 u16;
262typedef __u32 u32;
263typedef __u64 u64;
264
265struct btrfs_path {
266 union btrfs_tree_node *nodes[BTRFS_MAX_LEVEL];
267 u32 slots[BTRFS_MAX_LEVEL];
268};
269
270struct btrfs_root {
271 u64 objectid;
272 u64 bytenr;
273 u64 root_dirid;
274};
275
276int btrfs_comp_keys(struct btrfs_key *, struct btrfs_key *);
277int btrfs_comp_keys_type(struct btrfs_key *, struct btrfs_key *);
278int btrfs_bin_search(union btrfs_tree_node *, struct btrfs_key *, int *);
279void btrfs_free_path(struct btrfs_path *);
280int btrfs_search_tree(const struct btrfs_root *, struct btrfs_key *,
281 struct btrfs_path *);
282int btrfs_prev_slot(struct btrfs_path *);
283int btrfs_next_slot(struct btrfs_path *);
284
285static 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
289static inline struct btrfs_key *
290btrfs_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;
Tom Rini6aebc0d2019-04-27 11:34:55 -0400297 key.offset = 0;
Marek Behúnd4a704a2017-09-03 17:00:26 +0200298
299 if (btrfs_search_tree(root, &key, path))
300 return NULL;
301
Tom Rini6aebc0d2019-04-27 11:34:55 -0400302 res = btrfs_path_leaf_key(path);
303 if (btrfs_comp_keys_type(&key, res)) {
304 btrfs_free_path(path);
305 return NULL;
Marek Behúnd4a704a2017-09-03 17:00:26 +0200306 }
307
Tom Rini6aebc0d2019-04-27 11:34:55 -0400308 return res;
Marek Behúnd4a704a2017-09-03 17:00:26 +0200309}
310
311static inline u32 btrfs_path_item_size(struct btrfs_path *p)
312{
313 return p->nodes[0]->leaf.items[p->slots[0]].size;
314}
315
316static 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
322static 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__ */