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 btrfs_root *orig_root, u64 num_blocks,
  10                             u64 search_start, u64 search_end,
  11                             struct btrfs_key *ins);
  12 static int finish_current_insert(struct btrfs_root *extent_root);
  13 static int run_pending(struct btrfs_root *extent_root);
  14
  15 /*
  16  * pending extents are blocks that we're trying to allocate in the extent
  17  * map while trying to grow the map because of other allocations.  To avoid
  18  * recursing, they are tagged in the radix tree and cleaned up after
  19  * other allocations are done.  The pending tag is also used in the same
  20  * manner for deletes.
  21  */
  22 #define CTREE_EXTENT_PENDING_DEL 0
  23
  24 static int inc_block_ref(struct btrfs_root *root, u64 blocknr)
  25 {
  26         struct btrfs_path path;
  27         int ret;
  28         struct btrfs_key key;
  29         struct btrfs_leaf *l;
  30         struct btrfs_extent_item *item;
  31         struct btrfs_key ins;
  32         u32 refs;
  33
  34         find_free_extent(root->extent_root, 0, 0, (u64)-1, &ins);
  35         btrfs_init_path(&path);
  36         key.objectid = blocknr;
  37         key.flags = 0;
  38         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  39         key.offset = 1;
  40         ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 1);
  41         if (ret != 0)
  42                 BUG();
  43         BUG_ON(ret != 0);
  44         l = &path.nodes[0]->leaf;
  45         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  46         refs = btrfs_extent_refs(item);
  47         btrfs_set_extent_refs(item, refs + 1);
  48
  49         BUG_ON(list_empty(&path.nodes[0]->dirty));
  50         btrfs_release_path(root->extent_root, &path);
  51         finish_current_insert(root->extent_root);
  52         run_pending(root->extent_root);
  53         return 0;
  54 }
  55
  56 static int lookup_block_ref(struct btrfs_root *root, u64 blocknr, u32 *refs)
  57 {
  58         struct btrfs_path path;
  59         int ret;
  60         struct btrfs_key key;
  61         struct btrfs_leaf *l;
  62         struct btrfs_extent_item *item;
  63         btrfs_init_path(&path);
  64         key.objectid = blocknr;
  65         key.offset = 1;
  66         key.flags = 0;
  67         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  68         ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 0);
  69         if (ret != 0)
  70                 BUG();
  71         l = &path.nodes[0]->leaf;
  72         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  73         *refs = btrfs_extent_refs(item);
  74         btrfs_release_path(root->extent_root, &path);
  75         return 0;
  76 }
  77
  78 int btrfs_inc_ref(struct btrfs_root *root, struct btrfs_buffer *buf)
  79 {
  80         u64 blocknr;
  81         int i;
  82
  83         if (!root->ref_cows)
  84                 return 0;
  85         if (btrfs_is_leaf(&buf->node))
  86                 return 0;
  87
  88         for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
  89                 blocknr = btrfs_node_blockptr(&buf->node, i);
  90                 inc_block_ref(root, blocknr);
  91         }
  92         return 0;
  93 }
  94
  95 int btrfs_finish_extent_commit(struct btrfs_root *root)
  96 {
  97         unsigned long gang[8];
  98         u64 first = 0;
  99         int ret;
 100         int i;
 101
 102         while(1) {
 103                 ret = radix_tree_gang_lookup(&root->pinned_radix,
 104                                                  (void **)gang, 0,
 105                                                  ARRAY_SIZE(gang));
 106                 if (!ret)
 107                         break;
 108                 if (!first)
 109                         first = gang[0];
 110                 for (i = 0; i < ret; i++) {
 111                         radix_tree_delete(&root->pinned_radix, gang[i]);
 112                 }
 113         }
 114         root->last_insert.objectid = first;
 115         root->last_insert.offset = 0;
 116         return 0;
 117 }
 118
 119 static int finish_current_insert(struct btrfs_root *extent_root)
 120 {
 121         struct btrfs_key ins;
 122         struct btrfs_extent_item extent_item;
 123         int i;
 124         int ret;
 125
 126         btrfs_set_extent_refs(&extent_item, 1);
 127         btrfs_set_extent_owner(&extent_item,
 128                 btrfs_header_parentid(&extent_root->node->node.header));
 129         ins.offset = 1;
 130         ins.flags = 0;
 131         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 132
 133         for (i = 0; i < extent_root->current_insert.flags; i++) {
 134                 ins.objectid = extent_root->current_insert.objectid + i;
 135                 ret = btrfs_insert_item(extent_root, &ins, &extent_item,
 136                                   sizeof(extent_item));
 137                 BUG_ON(ret);
 138         }
 139         extent_root->current_insert.offset = 0;
 140         return 0;
 141 }
 142
 143 /*
 144  * remove an extent from the root, returns 0 on success
 145  */
 146 static int __free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks,
 147                          int pin)
 148 {
 149         struct btrfs_path path;
 150         struct btrfs_key key;
 151         struct btrfs_root *extent_root = root->extent_root;
 152         int ret;
 153         struct btrfs_extent_item *ei;
 154         struct btrfs_key ins;
 155         u32 refs;
 156
 157         BUG_ON(pin && num_blocks != 1);
 158         key.objectid = blocknr;
 159         key.flags = 0;
 160         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 161         key.offset = num_blocks;
 162
 163         find_free_extent(root, 0, 0, (u64)-1, &ins);
 164         btrfs_init_path(&path);
 165         ret = btrfs_search_slot(extent_root, &key, &path, -1, 1);
 166         if (ret) {
 167                 printf("failed to find %Lu\n", key.objectid);
 168                 btrfs_print_tree(extent_root, extent_root->node);
 169                 printf("failed to find %Lu\n", key.objectid);
 170                 BUG();
 171         }
 172         ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 173                             struct btrfs_extent_item);
 174         BUG_ON(ei->refs == 0);
 175         refs = btrfs_extent_refs(ei) - 1;
 176         btrfs_set_extent_refs(ei, refs);
 177         if (refs == 0) {
 178                 if (pin) {
 179                         int err;
 180                         radix_tree_preload(GFP_KERNEL);
 181                         err = radix_tree_insert(&extent_root->pinned_radix,
 182                                           blocknr, (void *)blocknr);
 183                         BUG_ON(err);
 184                         radix_tree_preload_end();
 185                 }
 186                 ret = btrfs_del_item(extent_root, &path);
 187                 if (!pin && extent_root->last_insert.objectid > blocknr)
 188                         extent_root->last_insert.objectid = blocknr;
 189                 if (ret)
 190                         BUG();
 191         }
 192         btrfs_release_path(extent_root, &path);
 193         finish_current_insert(extent_root);
 194         return ret;
 195 }
 196
 197 /*
 198  * find all the blocks marked as pending in the radix tree and remove
 199  * them from the extent map
 200  */
 201 static int del_pending_extents(struct btrfs_root *extent_root)
 202 {
 203         int ret;
 204         struct btrfs_buffer *gang[4];
 205         int i;
 206
 207         while(1) {
 208                 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
 209                                                  (void **)gang, 0,
 210                                                  ARRAY_SIZE(gang),
 211                                                  CTREE_EXTENT_PENDING_DEL);
 212                 if (!ret)
 213                         break;
 214                 for (i = 0; i < ret; i++) {
 215                         ret = __free_extent(extent_root,
 216                                             gang[i]->blocknr, 1, 1);
 217                         radix_tree_tag_clear(&extent_root->cache_radix,
 218                                                 gang[i]->blocknr,
 219                                                 CTREE_EXTENT_PENDING_DEL);
 220                         btrfs_block_release(extent_root, gang[i]);
 221                 }
 222         }
 223         return 0;
 224 }
 225
 226 static int run_pending(struct btrfs_root *extent_root)
 227 {
 228         while(radix_tree_tagged(&extent_root->cache_radix,
 229                                 CTREE_EXTENT_PENDING_DEL))
 230                 del_pending_extents(extent_root);
 231         return 0;
 232 }
 233
 234
 235 /*
 236  * remove an extent from the root, returns 0 on success
 237  */
 238 int btrfs_free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks,
 239                       int pin)
 240 {
 241         struct btrfs_root *extent_root = root->extent_root;
 242         struct btrfs_buffer *t;
 243         int pending_ret;
 244         int ret;
 245
 246         if (root == extent_root) {
 247                 t = find_tree_block(root, blocknr);
 248                 radix_tree_tag_set(&root->cache_radix, blocknr,
 249                                    CTREE_EXTENT_PENDING_DEL);
 250                 return 0;
 251         }
 252         ret = __free_extent(root, blocknr, num_blocks, pin);
 253         pending_ret = run_pending(root->extent_root);
 254         return ret ? ret : pending_ret;
 255 }
 256
 257 /*
 258  * walks the btree of allocated extents and find a hole of a given size.
 259  * The key ins is changed to record the hole:
 260  * ins->objectid == block start
 261  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 262  * ins->offset == number of blocks
 263  * Any available blocks before search_start are skipped.
 264  */
 265 static int find_free_extent(struct btrfs_root *orig_root, u64 num_blocks,
 266                             u64 search_start, u64 search_end,
 267                             struct btrfs_key *ins)
 268 {
 269         struct btrfs_path path;
 270         struct btrfs_key key;
 271         int ret;
 272         u64 hole_size = 0;
 273         int slot = 0;
 274         u64 last_block;
 275         u64 test_block;
 276         int start_found;
 277         struct btrfs_leaf *l;
 278         struct btrfs_root * root = orig_root->extent_root;
 279         int total_needed = num_blocks;
 280
 281         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 282         if (root->last_insert.objectid > search_start)
 283                 search_start = root->last_insert.objectid;
 284
 285         ins->flags = 0;
 286         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 287
 288 check_failed:
 289         btrfs_init_path(&path);
 290         ins->objectid = search_start;
 291         ins->offset = 0;
 292         start_found = 0;
 293         ret = btrfs_search_slot(root, ins, &path, 0, 0);
 294         if (ret < 0)
 295                 goto error;
 296
 297         if (path.slots[0] > 0)
 298                 path.slots[0]--;
 299
 300         while (1) {
 301                 l = &path.nodes[0]->leaf;
 302                 slot = path.slots[0];
 303                 if (slot >= btrfs_header_nritems(&l->header)) {
 304                         ret = btrfs_next_leaf(root, &path);
 305                         if (ret == 0)
 306                                 continue;
 307                         if (ret < 0)
 308                                 goto error;
 309                         if (!start_found) {
 310                                 ins->objectid = search_start;
 311                                 ins->offset = (u64)-1;
 312                                 start_found = 1;
 313                                 goto check_pending;
 314                         }
 315                         ins->objectid = last_block > search_start ?
 316                                         last_block : search_start;
 317                         ins->offset = (u64)-1;
 318                         goto check_pending;
 319                 }
 320                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 321                 if (key.objectid >= search_start) {
 322                         if (start_found) {
 323                                 if (last_block < search_start)
 324                                         last_block = search_start;
 325                                 hole_size = key.objectid - last_block;
 326                                 if (hole_size > total_needed) {
 327                                         ins->objectid = last_block;
 328                                         ins->offset = hole_size;
 329                                         goto check_pending;
 330                                 }
 331                         }
 332                 }
 333                 start_found = 1;
 334                 last_block = key.objectid + key.offset;
 335                 path.slots[0]++;
 336         }
 337         // FIXME -ENOSPC
 338 check_pending:
 339         /* we have to make sure we didn't find an extent that has already
 340          * been allocated by the map tree or the original allocation
 341          */
 342         btrfs_release_path(root, &path);
 343         BUG_ON(ins->objectid < search_start);
 344         for (test_block = ins->objectid;
 345              test_block < ins->objectid + total_needed; test_block++) {
 346                 if (radix_tree_lookup(&root->pinned_radix, test_block)) {
 347                         search_start = test_block + 1;
 348                         goto check_failed;
 349                 }
 350         }
 351         BUG_ON(root->current_insert.offset);
 352         root->current_insert.offset = total_needed - num_blocks;
 353         root->current_insert.objectid = ins->objectid + num_blocks;
 354         root->current_insert.flags = 0;
 355         root->last_insert.objectid = ins->objectid;
 356         ins->offset = num_blocks;
 357         return 0;
 358 error:
 359         btrfs_release_path(root, &path);
 360         return ret;
 361 }
 362
 363 /*
 364  * finds a free extent and does all the dirty work required for allocation
 365  * returns the key for the extent through ins, and a tree buffer for
 366  * the first block of the extent through buf.
 367  *
 368  * returns 0 if everything worked, non-zero otherwise.
 369  */
 370 static int alloc_extent(struct btrfs_root *root, u64 num_blocks,
 371                         u64 search_start, u64 search_end, u64 owner,
 372                         struct btrfs_key *ins)
 373 {
 374         int ret;
 375         int pending_ret;
 376         struct btrfs_root *extent_root = root->extent_root;
 377         struct btrfs_extent_item extent_item;
 378
 379         btrfs_set_extent_refs(&extent_item, 1);
 380         btrfs_set_extent_owner(&extent_item, owner);
 381
 382         if (root == extent_root) {
 383                 BUG_ON(extent_root->current_insert.offset == 0);
 384                 BUG_ON(num_blocks != 1);
 385                 BUG_ON(extent_root->current_insert.flags ==
 386                        extent_root->current_insert.offset);
 387                 ins->offset = 1;
 388                 ins->objectid = extent_root->current_insert.objectid +
 389                                 extent_root->current_insert.flags++;
 390                 return 0;
 391         }
 392         ret = find_free_extent(root, num_blocks, search_start,
 393                                search_end, ins);
 394         if (ret)
 395                 return ret;
 396
 397         ret = btrfs_insert_item(extent_root, ins, &extent_item,
 398                           sizeof(extent_item));
 399
 400         finish_current_insert(extent_root);
 401         pending_ret = run_pending(extent_root);
 402         if (ret)
 403                 return ret;
 404         if (pending_ret)
 405                 return pending_ret;
 406         return 0;
 407 }
 408
 409 /*
 410  * helper function to allocate a block for a given tree
 411  * returns the tree buffer or NULL.
 412  */
 413 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_root *root)
 414 {
 415         struct btrfs_key ins;
 416         int ret;
 417         struct btrfs_buffer *buf;
 418
 419         ret = alloc_extent(root, 1, 0, (unsigned long)-1,
 420                            btrfs_header_parentid(&root->node->node.header),
 421                            &ins);
 422         if (ret) {
 423                 BUG();
 424                 return NULL;
 425         }
 426         buf = find_tree_block(root, ins.objectid);
 427         dirty_tree_block(root, buf);
 428         return buf;
 429 }
 430
 431 /*
 432  * helper function for drop_snapshot, this walks down the tree dropping ref
 433  * counts as it goes.
 434  */
 435 static int walk_down_tree(struct btrfs_root *root,
 436                           struct btrfs_path *path, int *level)
 437 {
 438         struct btrfs_buffer *next;
 439         struct btrfs_buffer *cur;
 440         u64 blocknr;
 441         int ret;
 442         u32 refs;
 443
 444         ret = lookup_block_ref(root, path->nodes[*level]->blocknr, &refs);
 445         BUG_ON(ret);
 446         if (refs > 1)
 447                 goto out;
 448         /*
 449          * walk down to the last node level and free all the leaves
 450          */
 451         while(*level > 0) {
 452                 cur = path->nodes[*level];
 453                 if (path->slots[*level] >=
 454                     btrfs_header_nritems(&cur->node.header))
 455                         break;
 456                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 457                 ret = lookup_block_ref(root, blocknr, &refs);
 458                 if (refs != 1 || *level == 1) {
 459                         path->slots[*level]++;
 460                         ret = btrfs_free_extent(root, blocknr, 1, 1);
 461                         BUG_ON(ret);
 462                         continue;
 463                 }
 464                 BUG_ON(ret);
 465                 next = read_tree_block(root, blocknr);
 466                 if (path->nodes[*level-1])
 467                         btrfs_block_release(root, path->nodes[*level-1]);
 468                 path->nodes[*level-1] = next;
 469                 *level = btrfs_header_level(&next->node.header);
 470                 path->slots[*level] = 0;
 471         }
 472 out:
 473         ret = btrfs_free_extent(root, path->nodes[*level]->blocknr, 1, 1);
 474         btrfs_block_release(root, path->nodes[*level]);
 475         path->nodes[*level] = NULL;
 476         *level += 1;
 477         BUG_ON(ret);
 478         return 0;
 479 }
 480
 481 /*
 482  * helper for dropping snapshots.  This walks back up the tree in the path
 483  * to find the first node higher up where we haven't yet gone through
 484  * all the slots
 485  */
 486 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 487                         int *level)
 488 {
 489         int i;
 490         int slot;
 491         int ret;
 492         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 493                 slot = path->slots[i];
 494                 if (slot <
 495                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 496                         path->slots[i]++;
 497                         *level = i;
 498                         return 0;
 499                 } else {
 500                         ret = btrfs_free_extent(root,
 501                                           path->nodes[*level]->blocknr, 1, 1);
 502                         btrfs_block_release(root, path->nodes[*level]);
 503                         path->nodes[*level] = NULL;
 504                         *level = i + 1;
 505                         BUG_ON(ret);
 506                 }
 507         }
 508         return 1;
 509 }
 510
 511 /*
 512  * drop the reference count on the tree rooted at 'snap'.  This traverses
 513  * the tree freeing any blocks that have a ref count of zero after being
 514  * decremented.
 515  */
 516 int btrfs_drop_snapshot(struct btrfs_root *root, struct btrfs_buffer *snap)
 517 {
 518         int ret = 0;
 519         int wret;
 520         int level;
 521         struct btrfs_path path;
 522         int i;
 523         int orig_level;
 524
 525         btrfs_init_path(&path);
 526
 527         level = btrfs_header_level(&snap->node.header);
 528         orig_level = level;
 529         path.nodes[level] = snap;
 530         path.slots[level] = 0;
 531         while(1) {
 532                 wret = walk_down_tree(root, &path, &level);
 533                 if (wret > 0)
 534                         break;
 535                 if (wret < 0)
 536                         ret = wret;
 537
 538                 wret = walk_up_tree(root, &path, &level);
 539                 if (wret > 0)
 540                         break;
 541                 if (wret < 0)
 542                         ret = wret;
 543         }
 544         for (i = 0; i <= orig_level; i++) {
 545                 if (path.nodes[i]) {
 546                         btrfs_block_release(root, path.nodes[i]);
 547                 }
 548         }
 549         return ret;
 550 }