ctree.h

   1 #ifndef __CTREE__
   2 #define __CTREE__
   3
   4 #include "list.h"
   5 #include "kerncompat.h"
   6
   7 #define CTREE_BLOCKSIZE 1024
   8
   9 /*
  10  * the key defines the order in the tree, and so it also defines (optimal)
  11  * block layout.  objectid corresonds to the inode number.  The flags
  12  * tells us things about the object, and is a kind of stream selector.
  13  * so for a given inode, keys with flags of 1 might refer to the inode
  14  * data, flags of 2 may point to file data in the btree and flags == 3
  15  * may point to extents.
  16  *
  17  * offset is the starting byte offset for this key in the stream.
  18  *
  19  * btrfs_disk_key is in disk byte order.  struct btrfs_key is always
  20  * in cpu native order.  Otherwise they are identical and their sizes
  21  * should be the same (ie both packed)
  22  */
  23 struct btrfs_disk_key {
  24         __le64 objectid;
  25         __le32 flags;
  26         __le64 offset;
  27 } __attribute__ ((__packed__));
  28
  29 struct btrfs_key {
  30         u64 objectid;
  31         u32 flags;
  32         u64 offset;
  33 } __attribute__ ((__packed__));
  34
  35 /*
  36  * every tree block (leaf or node) starts with this header.
  37  */
  38 struct btrfs_header {
  39         __le64 fsid[2]; /* FS specific uuid */
  40         __le64 blocknr; /* which block this node is supposed to live in */
  41         __le64 parentid; /* objectid of the tree root */
  42         __le32 csum;
  43         __le32 ham;
  44         __le16 nritems;
  45         __le16 flags;
  46         /* generation flags to be added */
  47 } __attribute__ ((__packed__));
  48
  49 #define MAX_LEVEL 8
  50 #define NODEPTRS_PER_BLOCK ((CTREE_BLOCKSIZE - sizeof(struct btrfs_header)) / \
  51                             (sizeof(struct btrfs_disk_key) + sizeof(u64)))
  52
  53 struct tree_buffer;
  54
  55 /*
  56  * in ram representation of the tree.  extent_root is used for all allocations
  57  * and for the extent tree extent_root root.  current_insert is used
  58  * only for the extent tree.
  59  */
  60 struct ctree_root {
  61         struct tree_buffer *node;
  62         struct tree_buffer *commit_root;
  63         struct ctree_root *extent_root;
  64         struct btrfs_key current_insert;
  65         struct btrfs_key last_insert;
  66         int fp;
  67         struct radix_tree_root cache_radix;
  68         struct radix_tree_root pinned_radix;
  69         struct list_head trans;
  70         struct list_head cache;
  71         int cache_size;
  72 };
  73
  74 /*
  75  * describes a tree on disk
  76  */
  77 struct ctree_root_info {
  78         u64 fsid[2]; /* FS specific uuid */
  79         u64 blocknr; /* blocknr of this block */
  80         u64 objectid; /* inode number of this root */
  81         u64 tree_root; /* the tree root block */
  82         u32 csum;
  83         u32 ham;
  84         u64 snapuuid[2]; /* root specific uuid */
  85 } __attribute__ ((__packed__));
  86
  87 /*
  88  * the super block basically lists the main trees of the FS
  89  * it currently lacks any block count etc etc
  90  */
  91 struct ctree_super_block {
  92         struct ctree_root_info root_info;
  93         struct ctree_root_info extent_info;
  94 } __attribute__ ((__packed__));
  95
  96 /*
  97  * A leaf is full of items.  The exact type of item is defined by
  98  * the key flags parameter.  offset and size tell us where to find
  99  * the item in the leaf (relative to the start of the data area)
 100  */
 101 struct btrfs_item {
 102         struct btrfs_disk_key key;
 103         __le16 offset;
 104         __le16 size;
 105 } __attribute__ ((__packed__));
 106
 107 /*
 108  * leaves have an item area and a data area:
 109  * [item0, item1....itemN] [free space] [dataN...data1, data0]
 110  *
 111  * The data is separate from the items to get the keys closer together
 112  * during searches.
 113  */
 114 #define LEAF_DATA_SIZE (CTREE_BLOCKSIZE - sizeof(struct btrfs_header))
 115 struct leaf {
 116         struct btrfs_header header;
 117         union {
 118                 struct btrfs_item items[LEAF_DATA_SIZE/
 119                                         sizeof(struct btrfs_item)];
 120                 u8 data[CTREE_BLOCKSIZE-sizeof(struct btrfs_header)];
 121         };
 122 } __attribute__ ((__packed__));
 123
 124 /*
 125  * all non-leaf blocks are nodes, they hold only keys and pointers to
 126  * other blocks
 127  */
 128 struct node {
 129         struct btrfs_header header;
 130         struct btrfs_disk_key keys[NODEPTRS_PER_BLOCK];
 131         __le64 blockptrs[NODEPTRS_PER_BLOCK];
 132 } __attribute__ ((__packed__));
 133
 134 /*
 135  * items in the extent btree are used to record the objectid of the
 136  * owner of the block and the number of references
 137  */
 138 struct extent_item {
 139         __le32 refs;
 140         __le64 owner;
 141 } __attribute__ ((__packed__));
 142
 143 /*
 144  * ctree_paths remember the path taken from the root down to the leaf.
 145  * level 0 is always the leaf, and nodes[1...MAX_LEVEL] will point
 146  * to any other levels that are present.
 147  *
 148  * The slots array records the index of the item or block pointer
 149  * used while walking the tree.
 150  */
 151 struct ctree_path {
 152         struct tree_buffer *nodes[MAX_LEVEL];
 153         int slots[MAX_LEVEL];
 154 };
 155
 156 static inline u64 btrfs_extent_owner(struct extent_item *ei)
 157 {
 158         return le64_to_cpu(ei->owner);
 159 }
 160
 161 static inline void btrfs_set_extent_owner(struct extent_item *ei, u64 val)
 162 {
 163         ei->owner = cpu_to_le64(val);
 164 }
 165
 166 static inline u32 btrfs_extent_refs(struct extent_item *ei)
 167 {
 168         return le32_to_cpu(ei->refs);
 169 }
 170
 171 static inline void btrfs_set_extent_refs(struct extent_item *ei, u32 val)
 172 {
 173         ei->refs = cpu_to_le32(val);
 174 }
 175
 176 static inline u64 btrfs_node_blockptr(struct node *n, int nr)
 177 {
 178         return le64_to_cpu(n->blockptrs[nr]);
 179 }
 180
 181 static inline void btrfs_set_node_blockptr(struct node *n, int nr, u64 val)
 182 {
 183         n->blockptrs[nr] = cpu_to_le64(val);
 184 }
 185
 186 static inline u16 btrfs_item_offset(struct btrfs_item *item)
 187 {
 188         return le16_to_cpu(item->offset);
 189 }
 190
 191 static inline void btrfs_set_item_offset(struct btrfs_item *item, u16 val)
 192 {
 193         item->offset = cpu_to_le16(val);
 194 }
 195
 196 static inline u16 btrfs_item_end(struct btrfs_item *item)
 197 {
 198         return le16_to_cpu(item->offset) + le16_to_cpu(item->size);
 199 }
 200
 201 static inline u16 btrfs_item_size(struct btrfs_item *item)
 202 {
 203         return le16_to_cpu(item->size);
 204 }
 205
 206 static inline void btrfs_set_item_size(struct btrfs_item *item, u16 val)
 207 {
 208         item->size = cpu_to_le16(val);
 209 }
 210
 211 static inline void btrfs_disk_key_to_cpu(struct btrfs_key *cpu,
 212                                          struct btrfs_disk_key *disk)
 213 {
 214         cpu->offset = le64_to_cpu(disk->offset);
 215         cpu->flags = le32_to_cpu(disk->flags);
 216         cpu->objectid = le64_to_cpu(disk->objectid);
 217 }
 218
 219 static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
 220                                          struct btrfs_key *cpu)
 221 {
 222         disk->offset = cpu_to_le64(cpu->offset);
 223         disk->flags = cpu_to_le32(cpu->flags);
 224         disk->objectid = cpu_to_le64(cpu->objectid);
 225 }
 226
 227 static inline u64 btrfs_key_objectid(struct btrfs_disk_key *disk)
 228 {
 229         return le64_to_cpu(disk->objectid);
 230 }
 231
 232 static inline void btrfs_set_key_objectid(struct btrfs_disk_key *disk,
 233                                           u64 val)
 234 {
 235         disk->objectid = cpu_to_le64(val);
 236 }
 237
 238 static inline u64 btrfs_key_offset(struct btrfs_disk_key *disk)
 239 {
 240         return le64_to_cpu(disk->offset);
 241 }
 242
 243 static inline void btrfs_set_key_offset(struct btrfs_disk_key *disk,
 244                                           u64 val)
 245 {
 246         disk->offset = cpu_to_le64(val);
 247 }
 248
 249 static inline u32 btrfs_key_flags(struct btrfs_disk_key *disk)
 250 {
 251         return le32_to_cpu(disk->flags);
 252 }
 253
 254 static inline void btrfs_set_key_flags(struct btrfs_disk_key *disk,
 255                                           u32 val)
 256 {
 257         disk->flags = cpu_to_le32(val);
 258 }
 259
 260 static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
 261 {
 262         return le64_to_cpu(h->blocknr);
 263 }
 264
 265 static inline void btrfs_set_header_blocknr(struct btrfs_header *h, u64 blocknr)
 266 {
 267         h->blocknr = cpu_to_le64(blocknr);
 268 }
 269
 270 static inline u64 btrfs_header_parentid(struct btrfs_header *h)
 271 {
 272         return le64_to_cpu(h->parentid);
 273 }
 274
 275 static inline void btrfs_set_header_parentid(struct btrfs_header *h,
 276                                              u64 parentid)
 277 {
 278         h->parentid = cpu_to_le64(parentid);
 279 }
 280
 281 static inline u16 btrfs_header_nritems(struct btrfs_header *h)
 282 {
 283         return le16_to_cpu(h->nritems);
 284 }
 285
 286 static inline void btrfs_set_header_nritems(struct btrfs_header *h, u16 val)
 287 {
 288         h->nritems = cpu_to_le16(val);
 289 }
 290
 291 static inline u16 btrfs_header_flags(struct btrfs_header *h)
 292 {
 293         return le16_to_cpu(h->flags);
 294 }
 295
 296 static inline void btrfs_set_header_flags(struct btrfs_header *h, u16 val)
 297 {
 298         h->flags = cpu_to_le16(val);
 299 }
 300
 301 static inline int btrfs_header_level(struct btrfs_header *h)
 302 {
 303         return btrfs_header_flags(h) & (MAX_LEVEL - 1);
 304 }
 305
 306 static inline void btrfs_set_header_level(struct btrfs_header *h, int level)
 307 {
 308         u16 flags;
 309         BUG_ON(level > MAX_LEVEL);
 310         flags = btrfs_header_flags(h) & ~(MAX_LEVEL - 1);
 311         btrfs_set_header_flags(h, flags | level);
 312 }
 313
 314 static inline int btrfs_is_leaf(struct node *n)
 315 {
 316         return (btrfs_header_level(&n->header) == 0);
 317 }
 318
 319 struct tree_buffer *alloc_free_block(struct ctree_root *root);
 320 int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf);
 321 int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks);
 322 int search_slot(struct ctree_root *root, struct btrfs_key *key,
 323                 struct ctree_path *p, int ins_len, int cow);
 324 void release_path(struct ctree_root *root, struct ctree_path *p);
 325 void init_path(struct ctree_path *p);
 326 int del_item(struct ctree_root *root, struct ctree_path *path);
 327 int insert_item(struct ctree_root *root, struct btrfs_key *key,
 328                 void *data, int data_size);
 329 int next_leaf(struct ctree_root *root, struct ctree_path *path);
 330 int leaf_free_space(struct leaf *leaf);
 331 int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap);
 332 int btrfs_finish_extent_commit(struct ctree_root *root);
 333 #endif