ctree.h 8.1 KB

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