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