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