fs/btrfs/extent-tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "kerncompat.h"
   4 #include "radix-tree.h"
   5 #include "ctree.h"
   6 #include "disk-io.h"
   7 #include "print-tree.h"
   8
   9 /*
  10  * pending extents are blocks that we're trying to allocate in the extent
  11  * map while trying to grow the map because of other allocations.  To avoid
  12  * recursing, they are tagged in the radix tree and cleaned up after
  13  * other allocations are done.  The pending tag is also used in the same
  14  * manner for deletes.
  15  */
  16 #define CTREE_EXTENT_PENDING 0
  17
  18 /*
  19  * find all the blocks marked as pending in the radix tree and remove
  20  * them from the extent map
  21  */
  22 static int del_pending_extents(struct ctree_root *extent_root)
  23 {
  24         int ret;
  25         struct key key;
  26         struct tree_buffer *gang[4];
  27         int i;
  28         struct ctree_path path;
  29
  30         while(1) {
  31                 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
  32                                                  (void **)gang, 0,
  33                                                  ARRAY_SIZE(gang),
  34                                                  CTREE_EXTENT_PENDING);
  35                 if (!ret)
  36                         break;
  37                 for (i = 0; i < ret; i++) {
  38                         key.objectid = gang[i]->blocknr;
  39                         key.flags = 0;
  40                         key.offset = 1;
  41                         init_path(&path);
  42                         ret = search_slot(extent_root, &key, &path, 0);
  43                         if (ret) {
  44                                 print_tree(extent_root, extent_root->node);
  45                                 printf("unable to find %Lu\n", key.objectid);
  46                                 BUG();
  47                                 // FIXME undo it and return sane
  48                                 return ret;
  49                         }
  50                         ret = del_item(extent_root, &path);
  51                         if (ret) {
  52                                 BUG();
  53                                 return ret;
  54                         }
  55                         release_path(extent_root, &path);
  56                         radix_tree_tag_clear(&extent_root->cache_radix,
  57                                                 gang[i]->blocknr,
  58                                                 CTREE_EXTENT_PENDING);
  59                         tree_block_release(extent_root, gang[i]);
  60                 }
  61         }
  62         return 0;
  63 }
  64
  65 /*
  66  * remove an extent from the root, returns 0 on success
  67  */
  68 int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
  69 {
  70         struct ctree_path path;
  71         struct key key;
  72         struct ctree_root *extent_root = root->extent_root;
  73         struct tree_buffer *t;
  74         int pending_ret;
  75         int ret;
  76         key.objectid = blocknr;
  77         key.flags = 0;
  78         key.offset = num_blocks;
  79         if (root == extent_root) {
  80                 t = read_tree_block(root, key.objectid);
  81                 radix_tree_tag_set(&root->cache_radix, key.objectid,
  82                                    CTREE_EXTENT_PENDING);
  83                 return 0;
  84         }
  85         init_path(&path);
  86         ret = search_slot(extent_root, &key, &path, 0);
  87         if (ret) {
  88                 print_tree(extent_root, extent_root->node);
  89                 printf("failed to find %Lu\n", key.objectid);
  90                 BUG();
  91         }
  92         ret = del_item(extent_root, &path);
  93         if (ret)
  94                 BUG();
  95         release_path(extent_root, &path);
  96         pending_ret = del_pending_extents(root->extent_root);
  97         return ret ? ret : pending_ret;
  98 }
  99
 100 /*
 101  * walks the btree of allocated extents and find a hole of a given size.
 102  * The key ins is changed to record the hole:
 103  * ins->objectid == block start
 104  * ins->flags = 0
 105  * ins->offset == number of blocks
 106  * Any available blocks before search_start are skipped.
 107  */
 108 int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
 109                      u64 search_start, u64 search_end, struct key *ins)
 110 {
 111         struct ctree_path path;
 112         struct key *key;
 113         int ret;
 114         u64 hole_size = 0;
 115         int slot = 0;
 116         u64 last_block;
 117         int start_found;
 118         struct leaf *l;
 119         struct ctree_root * root = orig_root->extent_root;
 120
 121 check_failed:
 122         init_path(&path);
 123         ins->objectid = search_start;
 124         ins->offset = 0;
 125         ins->flags = 0;
 126         start_found = 0;
 127         ret = search_slot(root, ins, &path, 0);
 128         while (1) {
 129                 l = &path.nodes[0]->leaf;
 130                 slot = path.slots[0];
 131                 if (slot >= l->header.nritems) {
 132                         ret = next_leaf(root, &path);
 133                         if (ret == 0)
 134                                 continue;
 135                         if (!start_found) {
 136                                 ins->objectid = search_start;
 137                                 ins->offset = num_blocks;
 138                                 start_found = 1;
 139                                 goto check_pending;
 140                         }
 141                         ins->objectid = last_block > search_start ?
 142                                         last_block : search_start;
 143                         ins->offset = num_blocks;
 144                         goto check_pending;
 145                 }
 146                 key = &l->items[slot].key;
 147                 if (key->objectid >= search_start) {
 148                         if (start_found) {
 149                                 hole_size = key->objectid - last_block;
 150                                 if (hole_size > num_blocks) {
 151                                         ins->objectid = last_block;
 152                                         ins->offset = num_blocks;
 153                                         goto check_pending;
 154                                 }
 155                         } else
 156                                 start_found = 1;
 157                         last_block = key->objectid + key->offset;
 158                 }
 159                 path.slots[0]++;
 160         }
 161         // FIXME -ENOSPC
 162 check_pending:
 163         /* we have to make sure we didn't find an extent that has already
 164          * been allocated by the map tree or the original allocation
 165          */
 166         release_path(root, &path);
 167         BUG_ON(ins->objectid < search_start);
 168         if (orig_root->extent_root == orig_root) {
 169                 BUG_ON(num_blocks != 1);
 170                 if ((root->current_insert.objectid <= ins->objectid &&
 171                     root->current_insert.objectid +
 172                     root->current_insert.offset > ins->objectid) ||
 173                    (root->current_insert.objectid > ins->objectid &&
 174                     root->current_insert.objectid <= ins->objectid +
 175                     ins->offset) ||
 176                    radix_tree_tag_get(&root->cache_radix, ins->objectid,
 177                                       CTREE_EXTENT_PENDING)) {
 178                         search_start = ins->objectid + 1;
 179                         goto check_failed;
 180                 }
 181         }
 182         if (ins->offset != 1)
 183                 BUG();
 184         return 0;
 185 }
 186
 187 /*
 188  * insert all of the pending extents reserved during the original
 189  * allocation.  (CTREE_EXTENT_PENDING).  Returns zero if it all worked out
 190  */
 191 static int insert_pending_extents(struct ctree_root *extent_root)
 192 {
 193         int ret;
 194         struct key key;
 195         struct extent_item item;
 196         struct tree_buffer *gang[4];
 197         int i;
 198
 199         // FIXME -ENOSPC
 200         item.refs = 1;
 201         item.owner = extent_root->node->node.header.parentid;
 202         while(1) {
 203                 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
 204                                                  (void **)gang, 0,
 205                                                  ARRAY_SIZE(gang),
 206                                                  CTREE_EXTENT_PENDING);
 207                 if (!ret)
 208                         break;
 209                 for (i = 0; i < ret; i++) {
 210                         key.objectid = gang[i]->blocknr;
 211                         key.flags = 0;
 212                         key.offset = 1;
 213                         ret = insert_item(extent_root, &key, &item,
 214                                           sizeof(item));
 215                         if (ret) {
 216                                 BUG();
 217                                 // FIXME undo it and return sane
 218                                 return ret;
 219                         }
 220                         radix_tree_tag_clear(&extent_root->cache_radix,
 221                                              gang[i]->blocknr,
 222                                              CTREE_EXTENT_PENDING);
 223                         tree_block_release(extent_root, gang[i]);
 224                 }
 225         }
 226         return 0;
 227 }
 228
 229 /*
 230  * finds a free extent and does all the dirty work required for allocation
 231  * returns the key for the extent through ins, and a tree buffer for
 232  * the first block of the extent through buf.
 233  *
 234  * returns 0 if everything worked, non-zero otherwise.
 235  */
 236 int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
 237                          u64 search_end, u64 owner, struct key *ins,
 238                          struct tree_buffer **buf)
 239 {
 240         int ret;
 241         int pending_ret;
 242         struct extent_item extent_item;
 243         extent_item.refs = 1;
 244         extent_item.owner = owner;
 245
 246         ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
 247         if (ret)
 248                 return ret;
 249         if (root != root->extent_root) {
 250                 memcpy(&root->extent_root->current_insert, ins, sizeof(*ins));
 251                 ret = insert_item(root->extent_root, ins, &extent_item,
 252                                   sizeof(extent_item));
 253                 memset(&root->extent_root->current_insert, 0,
 254                        sizeof(struct key));
 255                 pending_ret = insert_pending_extents(root->extent_root);
 256                 if (ret)
 257                         return ret;
 258                 if (pending_ret)
 259                         return pending_ret;
 260                 *buf = find_tree_block(root, ins->objectid);
 261                 return 0;
 262         }
 263         /* we're allocating an extent for the extent tree, don't recurse */
 264         BUG_ON(ins->offset != 1);
 265         *buf = find_tree_block(root, ins->objectid);
 266         BUG_ON(!*buf);
 267         radix_tree_tag_set(&root->cache_radix, ins->objectid,
 268                            CTREE_EXTENT_PENDING);
 269         (*buf)->count++;
 270         return 0;
 271
 272 }
 273
 274 /*
 275  * helper function to allocate a block for a given tree
 276  * returns the tree buffer or NULL.
 277  */
 278 struct tree_buffer *alloc_free_block(struct ctree_root *root)
 279 {
 280         struct key ins;
 281         int ret;
 282         struct tree_buffer *buf = NULL;
 283
 284         ret = alloc_extent(root, 1, 0, (unsigned long)-1,
 285                            root->node->node.header.parentid,
 286                            &ins, &buf);
 287
 288         if (ret) {
 289                 BUG();
 290                 return NULL;
 291         }
 292         if (root != root->extent_root)
 293                 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
 294                                           buf->blocknr, CTREE_EXTENT_PENDING));
 295         return buf;
 296 }