free-space-cache.c

   1 /*
   2  * Copyright (C) 2008 Red Hat.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include "kerncompat.h"
  20 #include "ctree.h"
  21 #include "free-space-cache.h"
  22 #include "transaction.h"
  23 #include "disk-io.h"
  24 #include "extent_io.h"
  25 #include "crc32c.h"
  26 #include "bitops.h"
  27 #include "internal.h"
  28 #include "utils.h"
  29
  30 /*
  31  * Kernel always uses PAGE_CACHE_SIZE for sectorsize, but we don't have
  32  * anything like that in userspace and have to get the value from the
  33  * filesystem
  34  */
  35 #define BITS_PER_BITMAP(sectorsize)             ((sectorsize) * 8)
  36 #define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
  37
  38 static int link_free_space(struct btrfs_free_space_ctl *ctl,
  39                            struct btrfs_free_space *info);
  40 static void merge_space_tree(struct btrfs_free_space_ctl *ctl);
  41
  42 struct io_ctl {
  43         void *cur, *orig;
  44         void *buffer;
  45         struct btrfs_root *root;
  46         unsigned long size;
  47         u64 total_size;
  48         int index;
  49         int num_pages;
  50         unsigned check_crcs:1;
  51 };
  52
  53 static int io_ctl_init(struct io_ctl *io_ctl, u64 size, u64 ino,
  54                        struct btrfs_root *root)
  55 {
  56         memset(io_ctl, 0, sizeof(struct io_ctl));
  57         io_ctl->num_pages = (size + root->sectorsize - 1) / root->sectorsize;
  58         io_ctl->buffer = kzalloc(size, GFP_NOFS);
  59         if (!io_ctl->buffer)
  60                 return -ENOMEM;
  61         io_ctl->total_size = size;
  62         io_ctl->root = root;
  63         if (ino != BTRFS_FREE_INO_OBJECTID)
  64                 io_ctl->check_crcs = 1;
  65         return 0;
  66 }
  67
  68 static void io_ctl_free(struct io_ctl *io_ctl)
  69 {
  70         kfree(io_ctl->buffer);
  71 }
  72
  73 static void io_ctl_unmap_page(struct io_ctl *io_ctl)
  74 {
  75         if (io_ctl->cur) {
  76                 io_ctl->cur = NULL;
  77                 io_ctl->orig = NULL;
  78         }
  79 }
  80
  81 static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
  82 {
  83         BUG_ON(io_ctl->index >= io_ctl->num_pages);
  84         io_ctl->cur = io_ctl->buffer + (io_ctl->index++ * io_ctl->root->sectorsize);
  85         io_ctl->orig = io_ctl->cur;
  86         io_ctl->size = io_ctl->root->sectorsize;
  87         if (clear)
  88                 memset(io_ctl->cur, 0, io_ctl->root->sectorsize);
  89 }
  90
  91 static void io_ctl_drop_pages(struct io_ctl *io_ctl)
  92 {
  93         io_ctl_unmap_page(io_ctl);
  94 }
  95
  96 static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct btrfs_root *root,
  97                                 struct btrfs_path *path, u64 ino)
  98 {
  99         struct extent_buffer *leaf;
 100         struct btrfs_file_extent_item *fi;
 101         struct btrfs_key key;
 102         u64 bytenr, len;
 103         u64 total_read = 0;
 104         int ret = 0;
 105
 106         key.objectid = ino;
 107         key.type = BTRFS_EXTENT_DATA_KEY;
 108         key.offset = 0;
 109
 110         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 111         if (ret) {
 112                 fprintf(stderr,
 113                        "Couldn't find file extent item for free space inode"
 114                        " %Lu\n", ino);
 115                 btrfs_release_path(path);
 116                 return -EINVAL;
 117         }
 118
 119         while (total_read < io_ctl->total_size) {
 120                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
 121                         ret = btrfs_next_leaf(root, path);
 122                         if (ret) {
 123                                 ret = -EINVAL;
 124                                 break;
 125                         }
 126                 }
 127                 leaf = path->nodes[0];
 128
 129                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 130                 if (key.objectid != ino) {
 131                         ret = -EINVAL;
 132                         break;
 133                 }
 134
 135                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
 136                         ret = -EINVAL;
 137                         break;
 138                 }
 139
 140                 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 141                                     struct btrfs_file_extent_item);
 142                 if (btrfs_file_extent_type(path->nodes[0], fi) !=
 143                     BTRFS_FILE_EXTENT_REG) {
 144                         fprintf(stderr, "Not the file extent type we wanted\n");
 145                         ret = -EINVAL;
 146                         break;
 147                 }
 148
 149                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi) +
 150                         btrfs_file_extent_offset(leaf, fi);
 151                 len = btrfs_file_extent_num_bytes(leaf, fi);
 152                 ret = read_data_from_disk(root->fs_info,
 153                                           io_ctl->buffer + key.offset, bytenr,
 154                                           len, 0);
 155                 if (ret)
 156                         break;
 157                 total_read += len;
 158                 path->slots[0]++;
 159         }
 160
 161         btrfs_release_path(path);
 162         return ret;
 163 }
 164
 165 static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
 166 {
 167         __le64 *gen;
 168
 169         /*
 170          * Skip the crc area.  If we don't check crcs then we just have a 64bit
 171          * chunk at the front of the first page.
 172          */
 173         if (io_ctl->check_crcs) {
 174                 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
 175                 io_ctl->size -= sizeof(u64) +
 176                         (sizeof(u32) * io_ctl->num_pages);
 177         } else {
 178                 io_ctl->cur += sizeof(u64);
 179                 io_ctl->size -= sizeof(u64) * 2;
 180         }
 181
 182         gen = io_ctl->cur;
 183         if (le64_to_cpu(*gen) != generation) {
 184                 printk("btrfs: space cache generation "
 185                        "(%Lu) does not match inode (%Lu)\n", *gen,
 186                        generation);
 187                 io_ctl_unmap_page(io_ctl);
 188                 return -EIO;
 189         }
 190         io_ctl->cur += sizeof(u64);
 191         return 0;
 192 }
 193
 194 static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
 195 {
 196         u32 *tmp, val;
 197         u32 crc = ~(u32)0;
 198         unsigned offset = 0;
 199
 200         if (!io_ctl->check_crcs) {
 201                 io_ctl_map_page(io_ctl, 0);
 202                 return 0;
 203         }
 204
 205         if (index == 0)
 206                 offset = sizeof(u32) * io_ctl->num_pages;
 207
 208         tmp = io_ctl->buffer;
 209         tmp += index;
 210         val = *tmp;
 211
 212         io_ctl_map_page(io_ctl, 0);
 213         crc = crc32c(crc, io_ctl->orig + offset, io_ctl->root->sectorsize - offset);
 214         btrfs_csum_final(crc, (u8 *)&crc);
 215         if (val != crc) {
 216                 printk("btrfs: csum mismatch on free space cache\n");
 217                 io_ctl_unmap_page(io_ctl);
 218                 return -EIO;
 219         }
 220
 221         return 0;
 222 }
 223
 224 static int io_ctl_read_entry(struct io_ctl *io_ctl,
 225                             struct btrfs_free_space *entry, u8 *type)
 226 {
 227         struct btrfs_free_space_entry *e;
 228         int ret;
 229
 230         if (!io_ctl->cur) {
 231                 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
 232                 if (ret)
 233                         return ret;
 234         }
 235
 236         e = io_ctl->cur;
 237         entry->offset = le64_to_cpu(e->offset);
 238         entry->bytes = le64_to_cpu(e->bytes);
 239         *type = e->type;
 240         io_ctl->cur += sizeof(struct btrfs_free_space_entry);
 241         io_ctl->size -= sizeof(struct btrfs_free_space_entry);
 242
 243         if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
 244                 return 0;
 245
 246         io_ctl_unmap_page(io_ctl);
 247
 248         return 0;
 249 }
 250
 251 static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
 252                               struct btrfs_free_space *entry)
 253 {
 254         int ret;
 255
 256         ret = io_ctl_check_crc(io_ctl, io_ctl->index);
 257         if (ret)
 258                 return ret;
 259
 260         memcpy(entry->bitmap, io_ctl->cur, io_ctl->root->sectorsize);
 261         io_ctl_unmap_page(io_ctl);
 262
 263         return 0;
 264 }
 265
 266
 267 static int __load_free_space_cache(struct btrfs_root *root,
 268                             struct btrfs_free_space_ctl *ctl,
 269                             struct btrfs_path *path, u64 offset)
 270 {
 271         struct btrfs_free_space_header *header;
 272         struct btrfs_inode_item *inode_item;
 273         struct extent_buffer *leaf;
 274         struct io_ctl io_ctl;
 275         struct btrfs_key key;
 276         struct btrfs_key inode_location;
 277         struct btrfs_disk_key disk_key;
 278         struct btrfs_free_space *e, *n;
 279         struct list_head bitmaps;
 280         u64 num_entries;
 281         u64 num_bitmaps;
 282         u64 generation;
 283         u64 inode_size;
 284         u8 type;
 285         int ret = 0;
 286
 287         INIT_LIST_HEAD(&bitmaps);
 288
 289         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 290         key.offset = offset;
 291         key.type = 0;
 292
 293         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 294         if (ret < 0) {
 295                 return 0;
 296         } else if (ret > 0) {
 297                 btrfs_release_path(path);
 298                 return 0;
 299         }
 300
 301         leaf = path->nodes[0];
 302         header = btrfs_item_ptr(leaf, path->slots[0],
 303                                 struct btrfs_free_space_header);
 304         num_entries = btrfs_free_space_entries(leaf, header);
 305         num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
 306         generation = btrfs_free_space_generation(leaf, header);
 307         btrfs_free_space_key(leaf, header, &disk_key);
 308         btrfs_disk_key_to_cpu(&inode_location, &disk_key);
 309         btrfs_release_path(path);
 310
 311         ret = btrfs_search_slot(NULL, root, &inode_location, path, 0, 0);
 312         if (ret) {
 313                 fprintf(stderr, "Couldn't find free space inode %d\n", ret);
 314                 return 0;
 315         }
 316
 317         leaf = path->nodes[0];
 318         inode_item = btrfs_item_ptr(leaf, path->slots[0],
 319                                     struct btrfs_inode_item);
 320
 321         inode_size = btrfs_inode_size(leaf, inode_item);
 322         if (!inode_size || !btrfs_inode_generation(leaf, inode_item)) {
 323                 btrfs_release_path(path);
 324                 return 0;
 325         }
 326
 327         if (btrfs_inode_generation(leaf, inode_item) != generation) {
 328                 fprintf(stderr,
 329                        "free space inode generation (%llu) did not match "
 330                        "free space cache generation (%llu)\n",
 331                        (unsigned long long)btrfs_inode_generation(leaf,
 332                                                                   inode_item),
 333                        (unsigned long long)generation);
 334                 btrfs_release_path(path);
 335                 return 0;
 336         }
 337
 338         btrfs_release_path(path);
 339
 340         if (!num_entries)
 341                 return 0;
 342
 343         ret = io_ctl_init(&io_ctl, inode_size, inode_location.objectid, root);
 344         if (ret)
 345                 return ret;
 346
 347         ret = io_ctl_prepare_pages(&io_ctl, root, path,
 348                                    inode_location.objectid);
 349         if (ret)
 350                 goto out;
 351
 352         ret = io_ctl_check_crc(&io_ctl, 0);
 353         if (ret)
 354                 goto free_cache;
 355
 356         ret = io_ctl_check_generation(&io_ctl, generation);
 357         if (ret)
 358                 goto free_cache;
 359
 360         while (num_entries) {
 361                 e = calloc(1, sizeof(*e));
 362                 if (!e)
 363                         goto free_cache;
 364
 365                 ret = io_ctl_read_entry(&io_ctl, e, &type);
 366                 if (ret) {
 367                         free(e);
 368                         goto free_cache;
 369                 }
 370
 371                 if (!e->bytes) {
 372                         free(e);
 373                         goto free_cache;
 374                 }
 375
 376                 if (type == BTRFS_FREE_SPACE_EXTENT) {
 377                         ret = link_free_space(ctl, e);
 378                         if (ret) {
 379                                 fprintf(stderr,
 380                                        "Duplicate entries in free space cache\n");
 381                                 free(e);
 382                                 goto free_cache;
 383                         }
 384                 } else {
 385                         BUG_ON(!num_bitmaps);
 386                         num_bitmaps--;
 387                         e->bitmap = kzalloc(ctl->sectorsize, GFP_NOFS);
 388                         if (!e->bitmap) {
 389                                 free(e);
 390                                 goto free_cache;
 391                         }
 392                         ret = link_free_space(ctl, e);
 393                         ctl->total_bitmaps++;
 394                         if (ret) {
 395                                 fprintf(stderr,
 396                                        "Duplicate entries in free space cache\n");
 397                                 free(e->bitmap);
 398                                 free(e);
 399                                 goto free_cache;
 400                         }
 401                         list_add_tail(&e->list, &bitmaps);
 402                 }
 403
 404                 num_entries--;
 405         }
 406
 407         io_ctl_unmap_page(&io_ctl);
 408
 409         /*
 410          * We add the bitmaps at the end of the entries in order that
 411          * the bitmap entries are added to the cache.
 412          */
 413         list_for_each_entry_safe(e, n, &bitmaps, list) {
 414                 list_del_init(&e->list);
 415                 ret = io_ctl_read_bitmap(&io_ctl, e);
 416                 if (ret)
 417                         goto free_cache;
 418         }
 419
 420         io_ctl_drop_pages(&io_ctl);
 421         merge_space_tree(ctl);
 422         ret = 1;
 423 out:
 424         io_ctl_free(&io_ctl);
 425         return ret;
 426 free_cache:
 427         io_ctl_drop_pages(&io_ctl);
 428         __btrfs_remove_free_space_cache(ctl);
 429         goto out;
 430 }
 431
 432 int load_free_space_cache(struct btrfs_fs_info *fs_info,
 433                           struct btrfs_block_group_cache *block_group)
 434 {
 435         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 436         struct btrfs_path *path;
 437         u64 used = btrfs_block_group_used(&block_group->item);
 438         int ret = 0;
 439         int matched;
 440
 441         path = btrfs_alloc_path();
 442         if (!path)
 443                 return 0;
 444
 445         ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
 446                                       block_group->key.objectid);
 447         btrfs_free_path(path);
 448
 449         matched = (ctl->free_space == (block_group->key.offset - used -
 450                                        block_group->bytes_super));
 451         if (ret == 1 && !matched) {
 452                 __btrfs_remove_free_space_cache(ctl);
 453                 fprintf(stderr,
 454                        "block group %llu has wrong amount of free space\n",
 455                        block_group->key.objectid);
 456                 ret = -1;
 457         }
 458
 459         if (ret < 0) {
 460                 ret = 0;
 461
 462                 fprintf(stderr,
 463                        "failed to load free space cache for block group %llu\n",
 464                        block_group->key.objectid);
 465         }
 466
 467         return ret;
 468 }
 469
 470 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
 471                                           u64 offset)
 472 {
 473         BUG_ON(offset < bitmap_start);
 474         offset -= bitmap_start;
 475         return (unsigned long)(offset / unit);
 476 }
 477
 478 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
 479 {
 480         return (unsigned long)(bytes / unit);
 481 }
 482
 483 static int tree_insert_offset(struct rb_root *root, u64 offset,
 484                               struct rb_node *node, int bitmap)
 485 {
 486         struct rb_node **p = &root->rb_node;
 487         struct rb_node *parent = NULL;
 488         struct btrfs_free_space *info;
 489
 490         while (*p) {
 491                 parent = *p;
 492                 info = rb_entry(parent, struct btrfs_free_space, offset_index);
 493
 494                 if (offset < info->offset) {
 495                         p = &(*p)->rb_left;
 496                 } else if (offset > info->offset) {
 497                         p = &(*p)->rb_right;
 498                 } else {
 499                         /*
 500                          * we could have a bitmap entry and an extent entry
 501                          * share the same offset.  If this is the case, we want
 502                          * the extent entry to always be found first if we do a
 503                          * linear search through the tree, since we want to have
 504                          * the quickest allocation time, and allocating from an
 505                          * extent is faster than allocating from a bitmap.  So
 506                          * if we're inserting a bitmap and we find an entry at
 507                          * this offset, we want to go right, or after this entry
 508                          * logically.  If we are inserting an extent and we've
 509                          * found a bitmap, we want to go left, or before
 510                          * logically.
 511                          */
 512                         if (bitmap) {
 513                                 if (info->bitmap)
 514                                         return -EEXIST;
 515                                 p = &(*p)->rb_right;
 516                         } else {
 517                                 if (!info->bitmap)
 518                                         return -EEXIST;
 519                                 p = &(*p)->rb_left;
 520                         }
 521                 }
 522         }
 523
 524         rb_link_node(node, parent, p);
 525         rb_insert_color(node, root);
 526
 527         return 0;
 528 }
 529
 530 /*
 531  * searches the tree for the given offset.
 532  *
 533  * fuzzy - If this is set, then we are trying to make an allocation, and we just
 534  * want a section that has at least bytes size and comes at or after the given
 535  * offset.
 536  */
 537 static struct btrfs_free_space *
 538 tree_search_offset(struct btrfs_free_space_ctl *ctl,
 539                    u64 offset, int bitmap_only, int fuzzy)
 540 {
 541         struct rb_node *n = ctl->free_space_offset.rb_node;
 542         struct btrfs_free_space *entry, *prev = NULL;
 543         u32 sectorsize = ctl->sectorsize;
 544
 545         /* find entry that is closest to the 'offset' */
 546         while (1) {
 547                 if (!n) {
 548                         entry = NULL;
 549                         break;
 550                 }
 551
 552                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 553                 prev = entry;
 554
 555                 if (offset < entry->offset)
 556                         n = n->rb_left;
 557                 else if (offset > entry->offset)
 558                         n = n->rb_right;
 559                 else
 560                         break;
 561         }
 562
 563         if (bitmap_only) {
 564                 if (!entry)
 565                         return NULL;
 566                 if (entry->bitmap)
 567                         return entry;
 568
 569                 /*
 570                  * bitmap entry and extent entry may share same offset,
 571                  * in that case, bitmap entry comes after extent entry.
 572                  */
 573                 n = rb_next(n);
 574                 if (!n)
 575                         return NULL;
 576                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 577                 if (entry->offset != offset)
 578                         return NULL;
 579
 580                 WARN_ON(!entry->bitmap);
 581                 return entry;
 582         } else if (entry) {
 583                 if (entry->bitmap) {
 584                         /*
 585                          * if previous extent entry covers the offset,
 586                          * we should return it instead of the bitmap entry
 587                          */
 588                         n = rb_prev(&entry->offset_index);
 589                         if (n) {
 590                                 prev = rb_entry(n, struct btrfs_free_space,
 591                                                 offset_index);
 592                                 if (!prev->bitmap &&
 593                                     prev->offset + prev->bytes > offset)
 594                                         entry = prev;
 595                         }
 596                 }
 597                 return entry;
 598         }
 599
 600         if (!prev)
 601                 return NULL;
 602
 603         /* find last entry before the 'offset' */
 604         entry = prev;
 605         if (entry->offset > offset) {
 606                 n = rb_prev(&entry->offset_index);
 607                 if (n) {
 608                         entry = rb_entry(n, struct btrfs_free_space,
 609                                         offset_index);
 610                         BUG_ON(entry->offset > offset);
 611                 } else {
 612                         if (fuzzy)
 613                                 return entry;
 614                         else
 615                                 return NULL;
 616                 }
 617         }
 618
 619         if (entry->bitmap) {
 620                 n = rb_prev(&entry->offset_index);
 621                 if (n) {
 622                         prev = rb_entry(n, struct btrfs_free_space,
 623                                         offset_index);
 624                         if (!prev->bitmap &&
 625                             prev->offset + prev->bytes > offset)
 626                                 return prev;
 627                 }
 628                 if (entry->offset + BITS_PER_BITMAP(sectorsize) * ctl->unit > offset)
 629                         return entry;
 630         } else if (entry->offset + entry->bytes > offset)
 631                 return entry;
 632
 633         if (!fuzzy)
 634                 return NULL;
 635
 636         while (1) {
 637                 if (entry->bitmap) {
 638                         if (entry->offset + BITS_PER_BITMAP(sectorsize) *
 639                             ctl->unit > offset)
 640                                 break;
 641                 } else {
 642                         if (entry->offset + entry->bytes > offset)
 643                                 break;
 644                 }
 645
 646                 n = rb_next(&entry->offset_index);
 647                 if (!n)
 648                         return NULL;
 649                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 650         }
 651         return entry;
 652 }
 653
 654 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 655                        struct btrfs_free_space *info)
 656 {
 657         rb_erase(&info->offset_index, &ctl->free_space_offset);
 658         ctl->free_extents--;
 659         ctl->free_space -= info->bytes;
 660 }
 661
 662 static int link_free_space(struct btrfs_free_space_ctl *ctl,
 663                            struct btrfs_free_space *info)
 664 {
 665         int ret = 0;
 666
 667         BUG_ON(!info->bitmap && !info->bytes);
 668         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
 669                                  &info->offset_index, (info->bitmap != NULL));
 670         if (ret)
 671                 return ret;
 672
 673         ctl->free_space += info->bytes;
 674         ctl->free_extents++;
 675         return ret;
 676 }
 677
 678 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
 679                          struct btrfs_free_space *bitmap_info, u64 *offset,
 680                          u64 *bytes)
 681 {
 682         unsigned long found_bits = 0;
 683         unsigned long bits, i;
 684         unsigned long next_zero;
 685         u32 sectorsize = ctl->sectorsize;
 686
 687         i = offset_to_bit(bitmap_info->offset, ctl->unit,
 688                           max_t(u64, *offset, bitmap_info->offset));
 689         bits = bytes_to_bits(*bytes, ctl->unit);
 690
 691         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP(sectorsize)) {
 692                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
 693                                                BITS_PER_BITMAP(sectorsize), i);
 694                 if ((next_zero - i) >= bits) {
 695                         found_bits = next_zero - i;
 696                         break;
 697                 }
 698                 i = next_zero;
 699         }
 700
 701         if (found_bits) {
 702                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
 703                 *bytes = (u64)(found_bits) * ctl->unit;
 704                 return 0;
 705         }
 706
 707         return -1;
 708 }
 709
 710 struct btrfs_free_space *
 711 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
 712 {
 713         return tree_search_offset(ctl, offset, 0, 0);
 714 }
 715
 716 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
 717                                 struct btrfs_free_space *info)
 718 {
 719         struct btrfs_free_space *left_info;
 720         struct btrfs_free_space *right_info;
 721         u64 offset = info->offset;
 722         u64 bytes = info->bytes;
 723
 724         /*
 725          * first we want to see if there is free space adjacent to the range we
 726          * are adding, if there is remove that struct and add a new one to
 727          * cover the entire range
 728          */
 729         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
 730         if (right_info && rb_prev(&right_info->offset_index))
 731                 left_info = rb_entry(rb_prev(&right_info->offset_index),
 732                                      struct btrfs_free_space, offset_index);
 733         else
 734                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
 735
 736         if (right_info && !right_info->bitmap) {
 737                 unlink_free_space(ctl, right_info);
 738                 info->bytes += right_info->bytes;
 739                 free(right_info);
 740         }
 741
 742         if (left_info && !left_info->bitmap &&
 743             left_info->offset + left_info->bytes == offset) {
 744                 unlink_free_space(ctl, left_info);
 745                 info->offset = left_info->offset;
 746                 info->bytes += left_info->bytes;
 747                 free(left_info);
 748         }
 749 }
 750
 751 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
 752                            u64 bytes)
 753 {
 754         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 755         struct btrfs_free_space *info;
 756         struct rb_node *n;
 757         int count = 0;
 758
 759         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 760                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 761                 if (info->bytes >= bytes && !block_group->ro)
 762                         count++;
 763                 printk("entry offset %llu, bytes %llu, bitmap %s\n",
 764                        (unsigned long long)info->offset,
 765                        (unsigned long long)info->bytes,
 766                        (info->bitmap) ? "yes" : "no");
 767         }
 768         printk("%d blocks of free space at or bigger than bytes is \n", count);
 769 }
 770
 771 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
 772                               int sectorsize)
 773 {
 774         struct btrfs_free_space_ctl *ctl;
 775
 776         ctl = calloc(1, sizeof(*ctl));
 777         if (!ctl)
 778                 return -ENOMEM;
 779
 780         ctl->sectorsize = sectorsize;
 781         ctl->unit = sectorsize;
 782         ctl->start = block_group->key.objectid;
 783         ctl->private = block_group;
 784         block_group->free_space_ctl = ctl;
 785
 786         return 0;
 787 }
 788
 789 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
 790 {
 791         struct btrfs_free_space *info;
 792         struct rb_node *node;
 793
 794         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
 795                 info = rb_entry(node, struct btrfs_free_space, offset_index);
 796                 unlink_free_space(ctl, info);
 797                 free(info->bitmap);
 798                 free(info);
 799         }
 800 }
 801
 802 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 803 {
 804         __btrfs_remove_free_space_cache(block_group->free_space_ctl);
 805 }
 806
 807 int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
 808                          u64 bytes)
 809 {
 810         struct btrfs_free_space *info;
 811         int ret = 0;
 812
 813         info = calloc(1, sizeof(*info));
 814         if (!info)
 815                 return -ENOMEM;
 816
 817         info->offset = offset;
 818         info->bytes = bytes;
 819
 820         try_merge_free_space(ctl, info);
 821
 822         ret = link_free_space(ctl, info);
 823         if (ret) {
 824                 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
 825                 BUG_ON(ret == -EEXIST);
 826         }
 827
 828         return ret;
 829 }
 830
 831 /*
 832  * Merges all the free space cache and kills the bitmap entries since we just
 833  * want to use the free space cache to verify it's correct, no reason to keep
 834  * the bitmaps around to confuse things.
 835  */
 836 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
 837 {
 838         struct btrfs_free_space *e, *prev = NULL;
 839         struct rb_node *n;
 840         int ret;
 841         u32 sectorsize = ctl->sectorsize;
 842
 843 again:
 844         prev = NULL;
 845         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 846                 e = rb_entry(n, struct btrfs_free_space, offset_index);
 847                 if (e->bitmap) {
 848                         u64 offset = e->offset, bytes = ctl->unit;
 849                         u64 end;
 850
 851                         end = e->offset + (u64)(BITS_PER_BITMAP(sectorsize) * ctl->unit);
 852
 853                         unlink_free_space(ctl, e);
 854                         while (!(search_bitmap(ctl, e, &offset, &bytes))) {
 855                                 ret = btrfs_add_free_space(ctl, offset,
 856                                                            bytes);
 857                                 BUG_ON(ret);
 858                                 offset += bytes;
 859                                 if (offset >= end)
 860                                         break;
 861                                 bytes = ctl->unit;
 862                         }
 863                         free(e->bitmap);
 864                         free(e);
 865                         goto again;
 866                 }
 867                 if (!prev)
 868                         goto next;
 869                 if (prev->offset + prev->bytes == e->offset) {
 870                         unlink_free_space(ctl, prev);
 871                         unlink_free_space(ctl, e);
 872                         prev->bytes += e->bytes;
 873                         free(e);
 874                         link_free_space(ctl, prev);
 875                         goto again;
 876                 }
 877 next:
 878                 prev = e;
 879         }
 880 }
 881
 882 int btrfs_clear_free_space_cache(struct btrfs_fs_info *fs_info,
 883                                  struct btrfs_block_group_cache *bg)
 884 {
 885         struct btrfs_trans_handle *trans;
 886         struct btrfs_root *tree_root = fs_info->tree_root;
 887         struct btrfs_path path;
 888         struct btrfs_key key;
 889         struct btrfs_disk_key location;
 890         struct btrfs_free_space_header *sc_header;
 891         struct extent_buffer *node;
 892         u64 ino;
 893         int slot;
 894         int ret;
 895
 896         trans = btrfs_start_transaction(tree_root, 1);
 897         if (IS_ERR(trans))
 898                 return PTR_ERR(trans);
 899
 900         btrfs_init_path(&path);
 901
 902         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 903         key.type = 0;
 904         key.offset = bg->key.objectid;
 905
 906         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
 907         if (ret > 0) {
 908                 ret = 0;
 909                 goto out;
 910         }
 911         if (ret < 0)
 912                 goto out;
 913
 914         node = path.nodes[0];
 915         slot = path.slots[0];
 916         sc_header = btrfs_item_ptr(node, slot, struct btrfs_free_space_header);
 917         btrfs_free_space_key(node, sc_header, &location);
 918         ino = location.objectid;
 919
 920         /* Delete the free space header, as we have the ino to continue */
 921         ret = btrfs_del_item(trans, tree_root, &path);
 922         if (ret < 0) {
 923                 error("failed to remove free space header for block group %llu: %d",
 924                       bg->key.objectid, ret);
 925                 goto out;
 926         }
 927         btrfs_release_path(&path);
 928
 929         /* Iterate from the end of the free space cache inode */
 930         key.objectid = ino;
 931         key.type = BTRFS_EXTENT_DATA_KEY;
 932         key.offset = (u64)-1;
 933         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
 934         if (ret < 0) {
 935                 error("failed to locate free space cache extent for block group %llu: %d",
 936                       bg->key.objectid, ret);
 937                 goto out;
 938         }
 939         while (1) {
 940                 struct btrfs_file_extent_item *fi;
 941                 u64 disk_bytenr;
 942                 u64 disk_num_bytes;
 943
 944                 ret = btrfs_previous_item(tree_root, &path, ino,
 945                                           BTRFS_EXTENT_DATA_KEY);
 946                 if (ret > 0) {
 947                         ret = 0;
 948                         break;
 949                 }
 950                 if (ret < 0) {
 951                         error(
 952         "failed to locate free space cache extent for block group %llu: %d",
 953                                 bg->key.objectid, ret);
 954                         goto out;
 955                 }
 956                 node = path.nodes[0];
 957                 slot = path.slots[0];
 958                 btrfs_item_key_to_cpu(node, &key, slot);
 959                 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
 960                 disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
 961                 disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
 962
 963                 ret = btrfs_free_extent(trans, tree_root, disk_bytenr,
 964                                         disk_num_bytes, 0, tree_root->objectid,
 965                                         ino, key.offset);
 966                 if (ret < 0) {
 967                         error("failed to remove backref for disk bytenr %llu: %d",
 968                               disk_bytenr, ret);
 969                         goto out;
 970                 }
 971                 ret = btrfs_del_item(trans, tree_root, &path);
 972                 if (ret < 0) {
 973                         error(
 974         "failed to remove free space extent data for ino %llu offset %llu: %d",
 975                               ino, key.offset, ret);
 976                         goto out;
 977                 }
 978         }
 979         btrfs_release_path(&path);
 980
 981         /* Now delete free space cache inode item */
 982         key.objectid = ino;
 983         key.type = BTRFS_INODE_ITEM_KEY;
 984         key.offset = 0;
 985
 986         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
 987         if (ret > 0)
 988                 warning("free space inode %llu not found, ignore", ino);
 989         if (ret < 0) {
 990                 error(
 991         "failed to locate free space cache inode %llu for block group %llu: %d",
 992                       ino, bg->key.objectid, ret);
 993                 goto out;
 994         }
 995         ret = btrfs_del_item(trans, tree_root, &path);
 996         if (ret < 0) {
 997                 error(
 998         "failed to delete free space cache inode %llu for block group %llu: %d",
 999                       ino, bg->key.objectid, ret);
1000         }
1001 out:
1002         btrfs_release_path(&path);
1003         if (!ret)
1004                 btrfs_commit_transaction(trans, tree_root);
1005         return ret;
1006 }