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