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