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 static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
  10                             u64 search_start, u64 search_end, struct key *ins);
  11 static int finish_current_insert(struct ctree_root *extent_root);
  12 static int run_pending(struct ctree_root *extent_root);
  13
  14 /*
  15  * pending extents are blocks that we're trying to allocate in the extent
  16  * map while trying to grow the map because of other allocations.  To avoid
  17  * recursing, they are tagged in the radix tree and cleaned up after
  18  * other allocations are done.  The pending tag is also used in the same
  19  * manner for deletes.
  20  */
  21 #define CTREE_EXTENT_PENDING_DEL 0
  22
  23 static int inc_block_ref(struct ctree_root *root, u64 blocknr)
  24 {
  25         struct ctree_path path;
  26         int ret;
  27         struct key key;
  28         struct leaf *l;
  29         struct extent_item *item;
  30         struct key ins;
  31
  32         find_free_extent(root->extent_root, 0, 0, (u64)-1, &ins);
  33         init_path(&path);
  34         key.objectid = blocknr;
  35         key.flags = 0;
  36         key.offset = 1;
  37         ret = search_slot(root->extent_root, &key, &path, 0, 1);
  38         if (ret != 0)
  39                 BUG();
  40         BUG_ON(ret != 0);
  41         l = &path.nodes[0]->leaf;
  42         item = (struct extent_item *)(l->data +
  43                                       l->items[path.slots[0]].offset);
  44         item->refs++;
  45
  46         BUG_ON(list_empty(&path.nodes[0]->dirty));
  47         release_path(root->extent_root, &path);
  48         finish_current_insert(root->extent_root);
  49         run_pending(root->extent_root);
  50         return 0;
  51 }
  52
  53 static int lookup_block_ref(struct ctree_root *root, u64 blocknr, int *refs)
  54 {
  55         struct ctree_path path;
  56         int ret;
  57         struct key key;
  58         struct leaf *l;
  59         struct extent_item *item;
  60         init_path(&path);
  61         key.objectid = blocknr;
  62         key.flags = 0;
  63         key.offset = 1;
  64         ret = search_slot(root->extent_root, &key, &path, 0, 0);
  65         if (ret != 0)
  66                 BUG();
  67         l = &path.nodes[0]->leaf;
  68         item = (struct extent_item *)(l->data +
  69                                       l->items[path.slots[0]].offset);
  70         *refs = item->refs;
  71         release_path(root->extent_root, &path);
  72         return 0;
  73 }
  74
  75 int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf)
  76 {
  77         u64 blocknr;
  78         int i;
  79
  80         if (root == root->extent_root)
  81                 return 0;
  82         if (is_leaf(buf->node.header.flags))
  83                 return 0;
  84
  85         for (i = 0; i < buf->node.header.nritems; i++) {
  86                 blocknr = buf->node.blockptrs[i];
  87                 inc_block_ref(root, blocknr);
  88         }
  89         return 0;
  90 }
  91
  92 int btrfs_finish_extent_commit(struct ctree_root *root)
  93 {
  94         struct ctree_root *extent_root = root->extent_root;
  95         unsigned long gang[8];
  96         int ret;
  97         int i;
  98
  99         while(1) {
 100                 ret = radix_tree_gang_lookup(&extent_root->pinned_radix,
 101                                                  (void **)gang, 0,
 102                                                  ARRAY_SIZE(gang));
 103                 if (!ret)
 104                         break;
 105                 for (i = 0; i < ret; i++)
 106                         radix_tree_delete(&extent_root->pinned_radix, gang[i]);
 107         }
 108         return 0;
 109 }
 110
 111 static int finish_current_insert(struct ctree_root *extent_root)
 112 {
 113         struct key ins;
 114         struct extent_item extent_item;
 115         int i;
 116         int ret;
 117
 118         extent_item.refs = 1;
 119         extent_item.owner = extent_root->node->node.header.parentid;
 120         ins.offset = 1;
 121         ins.flags = 0;
 122
 123         for (i = 0; i < extent_root->current_insert.flags; i++) {
 124                 ins.objectid = extent_root->current_insert.objectid + i;
 125                 ret = insert_item(extent_root, &ins, &extent_item,
 126                                   sizeof(extent_item));
 127                 BUG_ON(ret);
 128         }
 129         extent_root->current_insert.offset = 0;
 130         return 0;
 131 }
 132
 133 /*
 134  * remove an extent from the root, returns 0 on success
 135  */
 136 int __free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
 137 {
 138         struct ctree_path path;
 139         struct key key;
 140         struct ctree_root *extent_root = root->extent_root;
 141         int ret;
 142         struct item *item;
 143         struct extent_item *ei;
 144         struct key ins;
 145
 146         key.objectid = blocknr;
 147         key.flags = 0;
 148         key.offset = num_blocks;
 149
 150         find_free_extent(root, 0, 0, (u64)-1, &ins);
 151         init_path(&path);
 152         ret = search_slot(extent_root, &key, &path, -1, 1);
 153         if (ret) {
 154                 printf("failed to find %Lu\n", key.objectid);
 155                 print_tree(extent_root, extent_root->node);
 156                 printf("failed to find %Lu\n", key.objectid);
 157                 BUG();
 158         }
 159         item = path.nodes[0]->leaf.items + path.slots[0];
 160         ei = (struct extent_item *)(path.nodes[0]->leaf.data + item->offset);
 161         BUG_ON(ei->refs == 0);
 162         ei->refs--;
 163         if (ei->refs == 0) {
 164                 if (root == extent_root) {
 165                         int err;
 166                         radix_tree_preload(GFP_KERNEL);
 167                         err = radix_tree_insert(&extent_root->pinned_radix,
 168                                           blocknr, (void *)blocknr);
 169                         BUG_ON(err);
 170                         radix_tree_preload_end();
 171                 }
 172                 ret = del_item(extent_root, &path);
 173                 if (ret)
 174                         BUG();
 175         }
 176         release_path(extent_root, &path);
 177         finish_current_insert(extent_root);
 178         return ret;
 179 }
 180
 181 /*
 182  * find all the blocks marked as pending in the radix tree and remove
 183  * them from the extent map
 184  */
 185 static int del_pending_extents(struct ctree_root *extent_root)
 186 {
 187         int ret;
 188         struct tree_buffer *gang[4];
 189         int i;
 190
 191         while(1) {
 192                 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
 193                                                  (void **)gang, 0,
 194                                                  ARRAY_SIZE(gang),
 195                                                  CTREE_EXTENT_PENDING_DEL);
 196                 if (!ret)
 197                         break;
 198                 for (i = 0; i < ret; i++) {
 199                         ret = __free_extent(extent_root, gang[i]->blocknr, 1);
 200                         radix_tree_tag_clear(&extent_root->cache_radix,
 201                                                 gang[i]->blocknr,
 202                                                 CTREE_EXTENT_PENDING_DEL);
 203                         tree_block_release(extent_root, gang[i]);
 204                 }
 205         }
 206         return 0;
 207 }
 208
 209 static int run_pending(struct ctree_root *extent_root)
 210 {
 211         while(radix_tree_tagged(&extent_root->cache_radix,
 212                                 CTREE_EXTENT_PENDING_DEL))
 213                 del_pending_extents(extent_root);
 214         return 0;
 215 }
 216
 217
 218 /*
 219  * remove an extent from the root, returns 0 on success
 220  */
 221 int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
 222 {
 223         struct key key;
 224         struct ctree_root *extent_root = root->extent_root;
 225         struct tree_buffer *t;
 226         int pending_ret;
 227         int ret;
 228
 229         if (root == extent_root) {
 230                 t = find_tree_block(root, blocknr);
 231                 radix_tree_tag_set(&root->cache_radix, blocknr,
 232                                    CTREE_EXTENT_PENDING_DEL);
 233                 return 0;
 234         }
 235         key.objectid = blocknr;
 236         key.flags = 0;
 237         key.offset = num_blocks;
 238         ret = __free_extent(root, blocknr, num_blocks);
 239         pending_ret = run_pending(root->extent_root);
 240         return ret ? ret : pending_ret;
 241 }
 242
 243 /*
 244  * walks the btree of allocated extents and find a hole of a given size.
 245  * The key ins is changed to record the hole:
 246  * ins->objectid == block start
 247  * ins->flags = 0
 248  * ins->offset == number of blocks
 249  * Any available blocks before search_start are skipped.
 250  */
 251 static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
 252                             u64 search_start, u64 search_end, struct key *ins)
 253 {
 254         struct ctree_path path;
 255         struct key *key;
 256         int ret;
 257         u64 hole_size = 0;
 258         int slot = 0;
 259         u64 last_block;
 260         u64 test_block;
 261         int start_found;
 262         struct leaf *l;
 263         struct ctree_root * root = orig_root->extent_root;
 264         int total_needed = num_blocks + MAX_LEVEL * 3;
 265
 266 check_failed:
 267         init_path(&path);
 268         ins->objectid = search_start;
 269         ins->offset = 0;
 270         ins->flags = 0;
 271         start_found = 0;
 272         ret = search_slot(root, ins, &path, 0, 0);
 273         if (ret < 0)
 274                 goto error;
 275
 276         while (1) {
 277                 l = &path.nodes[0]->leaf;
 278                 slot = path.slots[0];
 279                 if (slot >= l->header.nritems) {
 280                         ret = next_leaf(root, &path);
 281                         if (ret == 0)
 282                                 continue;
 283                         if (ret < 0)
 284                                 goto error;
 285                         if (!start_found) {
 286                                 ins->objectid = search_start;
 287                                 ins->offset = (u64)-1;
 288                                 start_found = 1;
 289                                 goto check_pending;
 290                         }
 291                         ins->objectid = last_block > search_start ?
 292                                         last_block : search_start;
 293                         ins->offset = (u64)-1;
 294                         goto check_pending;
 295                 }
 296                 if (slot == 0) {
 297                         int last_slot = l->header.nritems - 1;
 298                         u64 span = l->items[last_slot].key.objectid;
 299                         span -= l->items[slot].key.objectid;
 300                         if (span + total_needed > last_slot - slot) {
 301                                 path.slots[0] = last_slot + 1;
 302                                 key = &l->items[last_slot].key;
 303                                 last_block = key->objectid + key->offset;
 304                                 start_found = 1;
 305                                 continue;
 306                         }
 307                 }
 308                 key = &l->items[slot].key;
 309                 if (key->objectid >= search_start) {
 310                         if (start_found) {
 311                                 hole_size = key->objectid - last_block;
 312                                 if (hole_size > total_needed) {
 313                                         ins->objectid = last_block;
 314                                         ins->offset = hole_size;
 315                                         goto check_pending;
 316                                 }
 317                         } else
 318                                 start_found = 1;
 319                         last_block = key->objectid + key->offset;
 320                 }
 321                 path.slots[0]++;
 322         }
 323         // FIXME -ENOSPC
 324 check_pending:
 325         /* we have to make sure we didn't find an extent that has already
 326          * been allocated by the map tree or the original allocation
 327          */
 328         release_path(root, &path);
 329         BUG_ON(ins->objectid < search_start);
 330         for (test_block = ins->objectid;
 331              test_block < ins->objectid + total_needed; test_block++) {
 332                 if (radix_tree_lookup(&root->pinned_radix, test_block)) {
 333                         search_start = test_block + 1;
 334                         goto check_failed;
 335                 }
 336         }
 337         BUG_ON(root->current_insert.offset);
 338         root->current_insert.offset = total_needed;
 339         root->current_insert.objectid = ins->objectid + num_blocks;
 340         root->current_insert.flags = 0;
 341         ins->offset = num_blocks;
 342         return 0;
 343 error:
 344         release_path(root, &path);
 345         return ret;
 346 }
 347
 348 /*
 349  * finds a free extent and does all the dirty work required for allocation
 350  * returns the key for the extent through ins, and a tree buffer for
 351  * the first block of the extent through buf.
 352  *
 353  * returns 0 if everything worked, non-zero otherwise.
 354  */
 355 int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
 356                          u64 search_end, u64 owner, struct key *ins)
 357 {
 358         int ret;
 359         int pending_ret;
 360         struct ctree_root *extent_root = root->extent_root;
 361         struct extent_item extent_item;
 362
 363         extent_item.refs = 1;
 364         extent_item.owner = owner;
 365
 366         if (root == extent_root) {
 367                 BUG_ON(extent_root->current_insert.offset == 0);
 368                 BUG_ON(num_blocks != 1);
 369                 BUG_ON(extent_root->current_insert.flags ==
 370                        extent_root->current_insert.offset);
 371                 ins->offset = 1;
 372                 ins->objectid = extent_root->current_insert.objectid +
 373                                 extent_root->current_insert.flags++;
 374                 return 0;
 375         }
 376         ret = find_free_extent(root, num_blocks, search_start,
 377                                search_end, ins);
 378         if (ret)
 379                 return ret;
 380
 381         ret = insert_item(extent_root, ins, &extent_item,
 382                           sizeof(extent_item));
 383
 384         finish_current_insert(extent_root);
 385         pending_ret = run_pending(extent_root);
 386         if (ret)
 387                 return ret;
 388         if (pending_ret)
 389                 return pending_ret;
 390         return 0;
 391 }
 392
 393 /*
 394  * helper function to allocate a block for a given tree
 395  * returns the tree buffer or NULL.
 396  */
 397 struct tree_buffer *alloc_free_block(struct ctree_root *root)
 398 {
 399         struct key ins;
 400         int ret;
 401         struct tree_buffer *buf;
 402
 403         ret = alloc_extent(root, 1, 0, (unsigned long)-1,
 404                            root->node->node.header.parentid,
 405                            &ins);
 406         if (ret) {
 407                 BUG();
 408                 return NULL;
 409         }
 410         buf = find_tree_block(root, ins.objectid);
 411         dirty_tree_block(root, buf);
 412         return buf;
 413 }
 414
 415 int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap)
 416 {
 417         int ret;
 418         int level;
 419         int refs;
 420         u64 blocknr = snap->blocknr;
 421
 422         level = node_level(snap->node.header.flags);
 423         ret = lookup_block_ref(root, snap->blocknr, &refs);
 424         BUG_ON(ret);
 425         if (refs == 1 && level != 0) {
 426                 struct node *n = &snap->node;
 427                 struct tree_buffer *b;
 428                 int i;
 429                 for (i = 0; i < n->header.nritems; i++) {
 430                         b = read_tree_block(root, n->blockptrs[i]);
 431                         /* FIXME, don't recurse here */
 432                         ret = btrfs_drop_snapshot(root, b);
 433                         BUG_ON(ret);
 434                         tree_block_release(root, b);
 435                 }
 436         }
 437         ret = free_extent(root, blocknr, 1);
 438         BUG_ON(ret);
 439         return 0;
 440 }
 441