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