fs/btrfs/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         u32 refs;
 140         u64 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_node_blockptr(struct node *n, int nr)
 157 {
 158         return le64_to_cpu(n->blockptrs[nr]);
 159 }
 160
 161 static inline void btrfs_set_node_blockptr(struct node *n, int nr, u64 val)
 162 {
 163         n->blockptrs[nr] = cpu_to_le64(val);
 164 }
 165
 166 static inline u16 btrfs_item_offset(struct btrfs_item *item)
 167 {
 168         return le16_to_cpu(item->offset);
 169 }
 170
 171 static inline void btrfs_set_item_offset(struct btrfs_item *item, u16 val)
 172 {
 173         item->offset = cpu_to_le16(val);
 174 }
 175
 176 static inline u16 btrfs_item_end(struct btrfs_item *item)
 177 {
 178         return le16_to_cpu(item->offset) + le16_to_cpu(item->size);
 179 }
 180
 181 static inline u16 btrfs_item_size(struct btrfs_item *item)
 182 {
 183         return le16_to_cpu(item->size);
 184 }
 185
 186 static inline void btrfs_set_item_size(struct btrfs_item *item, u16 val)
 187 {
 188         item->size = cpu_to_le16(val);
 189 }
 190
 191 static inline void btrfs_disk_key_to_cpu(struct btrfs_key *cpu,
 192                                          struct btrfs_disk_key *disk)
 193 {
 194         cpu->offset = le64_to_cpu(disk->offset);
 195         cpu->flags = le32_to_cpu(disk->flags);
 196         cpu->objectid = le64_to_cpu(disk->objectid);
 197 }
 198
 199 static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
 200                                          struct btrfs_key *cpu)
 201 {
 202         disk->offset = cpu_to_le64(cpu->offset);
 203         disk->flags = cpu_to_le32(cpu->flags);
 204         disk->objectid = cpu_to_le64(cpu->objectid);
 205 }
 206
 207 static inline u64 btrfs_key_objectid(struct btrfs_disk_key *disk)
 208 {
 209         return le64_to_cpu(disk->objectid);
 210 }
 211
 212 static inline void btrfs_set_key_objectid(struct btrfs_disk_key *disk,
 213                                           u64 val)
 214 {
 215         disk->objectid = cpu_to_le64(val);
 216 }
 217
 218 static inline u64 btrfs_key_offset(struct btrfs_disk_key *disk)
 219 {
 220         return le64_to_cpu(disk->offset);
 221 }
 222
 223 static inline void btrfs_set_key_offset(struct btrfs_disk_key *disk,
 224                                           u64 val)
 225 {
 226         disk->offset = cpu_to_le64(val);
 227 }
 228
 229 static inline u32 btrfs_key_flags(struct btrfs_disk_key *disk)
 230 {
 231         return le32_to_cpu(disk->flags);
 232 }
 233
 234 static inline void btrfs_set_key_flags(struct btrfs_disk_key *disk,
 235                                           u32 val)
 236 {
 237         disk->flags = cpu_to_le32(val);
 238 }
 239
 240 static inline u64 btrfs_header_blocknr(struct btrfs_header *h)
 241 {
 242         return le64_to_cpu(h->blocknr);
 243 }
 244
 245 static inline void btrfs_set_header_blocknr(struct btrfs_header *h, u64 blocknr)
 246 {
 247         h->blocknr = cpu_to_le64(blocknr);
 248 }
 249
 250 static inline u64 btrfs_header_parentid(struct btrfs_header *h)
 251 {
 252         return le64_to_cpu(h->parentid);
 253 }
 254
 255 static inline void btrfs_set_header_parentid(struct btrfs_header *h,
 256                                              u64 parentid)
 257 {
 258         h->parentid = cpu_to_le64(parentid);
 259 }
 260
 261 static inline u16 btrfs_header_nritems(struct btrfs_header *h)
 262 {
 263         return le16_to_cpu(h->nritems);
 264 }
 265
 266 static inline void btrfs_set_header_nritems(struct btrfs_header *h, u16 val)
 267 {
 268         h->nritems = cpu_to_le16(val);
 269 }
 270
 271 static inline u16 btrfs_header_flags(struct btrfs_header *h)
 272 {
 273         return le16_to_cpu(h->flags);
 274 }
 275
 276 static inline void btrfs_set_header_flags(struct btrfs_header *h, u16 val)
 277 {
 278         h->flags = cpu_to_le16(val);
 279 }
 280
 281 static inline int btrfs_header_level(struct btrfs_header *h)
 282 {
 283         return btrfs_header_flags(h) & (MAX_LEVEL - 1);
 284 }
 285
 286 static inline void btrfs_set_header_level(struct btrfs_header *h, int level)
 287 {
 288         u16 flags;
 289         BUG_ON(level > MAX_LEVEL);
 290         flags = btrfs_header_flags(h) & ~(MAX_LEVEL - 1);
 291         btrfs_set_header_flags(h, flags | level);
 292 }
 293
 294 static inline int btrfs_is_leaf(struct node *n)
 295 {
 296         return (btrfs_header_level(&n->header) == 0);
 297 }
 298
 299 struct tree_buffer *alloc_free_block(struct ctree_root *root);
 300 int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf);
 301 int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks);
 302 int search_slot(struct ctree_root *root, struct btrfs_key *key,
 303                 struct ctree_path *p, int ins_len, int cow);
 304 void release_path(struct ctree_root *root, struct ctree_path *p);
 305 void init_path(struct ctree_path *p);
 306 int del_item(struct ctree_root *root, struct ctree_path *path);
 307 int insert_item(struct ctree_root *root, struct btrfs_key *key,
 308                 void *data, int data_size);
 309 int next_leaf(struct ctree_root *root, struct ctree_path *path);
 310 int leaf_free_space(struct leaf *leaf);
 311 int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap);
 312 int btrfs_finish_extent_commit(struct ctree_root *root);
 313 #endif