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