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         u64 bg_free;
 442         s64 diff;
 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         bg_free = block_group->key.offset - used - block_group->bytes_super;
 453         diff = ctl->free_space - bg_free;
 454         if (ret == 1 && diff) {
 455                 fprintf(stderr,
 456                        "block group %llu has wrong amount of free space, free space cache has %llu block group has %llu\n",
 457                        block_group->key.objectid, ctl->free_space, bg_free);
 458                 __btrfs_remove_free_space_cache(ctl);
 459                 /*
 460                  * Due to btrfs_reserve_extent() can happen out of a
 461                  * transaction, but all btrfs_release_extent() happens inside
 462                  * a transaction, so under heavy race it's possible that free
 463                  * space cache has less free space, and both kernel just discard
 464                  * such cache. But if we find some case where free space cache
 465                  * has more free space, this means under certain case such
 466                  * cache can be loaded and cause double allocate.
 467                  *
 468                  * Detect such possibility here.
 469                  */
 470                 if (diff > 0)
 471                         error(
 472 "free space cache has more free space than block group item, this could leads to serious corruption, please contact btrfs developers");
 473                 ret = -1;
 474         }
 475
 476         if (ret < 0) {
 477                 if (diff <= 0)
 478                         ret = 0;
 479
 480                 fprintf(stderr,
 481                        "failed to load free space cache for block group %llu\n",
 482                        block_group->key.objectid);
 483         }
 484
 485         return ret;
 486 }
 487
 488 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
 489                                           u64 offset)
 490 {
 491         BUG_ON(offset < bitmap_start);
 492         offset -= bitmap_start;
 493         return (unsigned long)(offset / unit);
 494 }
 495
 496 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
 497 {
 498         return (unsigned long)(bytes / unit);
 499 }
 500
 501 static int tree_insert_offset(struct rb_root *root, u64 offset,
 502                               struct rb_node *node, int bitmap)
 503 {
 504         struct rb_node **p = &root->rb_node;
 505         struct rb_node *parent = NULL;
 506         struct btrfs_free_space *info;
 507
 508         while (*p) {
 509                 parent = *p;
 510                 info = rb_entry(parent, struct btrfs_free_space, offset_index);
 511
 512                 if (offset < info->offset) {
 513                         p = &(*p)->rb_left;
 514                 } else if (offset > info->offset) {
 515                         p = &(*p)->rb_right;
 516                 } else {
 517                         /*
 518                          * we could have a bitmap entry and an extent entry
 519                          * share the same offset.  If this is the case, we want
 520                          * the extent entry to always be found first if we do a
 521                          * linear search through the tree, since we want to have
 522                          * the quickest allocation time, and allocating from an
 523                          * extent is faster than allocating from a bitmap.  So
 524                          * if we're inserting a bitmap and we find an entry at
 525                          * this offset, we want to go right, or after this entry
 526                          * logically.  If we are inserting an extent and we've
 527                          * found a bitmap, we want to go left, or before
 528                          * logically.
 529                          */
 530                         if (bitmap) {
 531                                 if (info->bitmap)
 532                                         return -EEXIST;
 533                                 p = &(*p)->rb_right;
 534                         } else {
 535                                 if (!info->bitmap)
 536                                         return -EEXIST;
 537                                 p = &(*p)->rb_left;
 538                         }
 539                 }
 540         }
 541
 542         rb_link_node(node, parent, p);
 543         rb_insert_color(node, root);
 544
 545         return 0;
 546 }
 547
 548 /*
 549  * searches the tree for the given offset.
 550  *
 551  * fuzzy - If this is set, then we are trying to make an allocation, and we just
 552  * want a section that has at least bytes size and comes at or after the given
 553  * offset.
 554  */
 555 static struct btrfs_free_space *
 556 tree_search_offset(struct btrfs_free_space_ctl *ctl,
 557                    u64 offset, int bitmap_only, int fuzzy)
 558 {
 559         struct rb_node *n = ctl->free_space_offset.rb_node;
 560         struct btrfs_free_space *entry, *prev = NULL;
 561         u32 sectorsize = ctl->sectorsize;
 562
 563         /* find entry that is closest to the 'offset' */
 564         while (1) {
 565                 if (!n) {
 566                         entry = NULL;
 567                         break;
 568                 }
 569
 570                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 571                 prev = entry;
 572
 573                 if (offset < entry->offset)
 574                         n = n->rb_left;
 575                 else if (offset > entry->offset)
 576                         n = n->rb_right;
 577                 else
 578                         break;
 579         }
 580
 581         if (bitmap_only) {
 582                 if (!entry)
 583                         return NULL;
 584                 if (entry->bitmap)
 585                         return entry;
 586
 587                 /*
 588                  * bitmap entry and extent entry may share same offset,
 589                  * in that case, bitmap entry comes after extent entry.
 590                  */
 591                 n = rb_next(n);
 592                 if (!n)
 593                         return NULL;
 594                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 595                 if (entry->offset != offset)
 596                         return NULL;
 597
 598                 WARN_ON(!entry->bitmap);
 599                 return entry;
 600         } else if (entry) {
 601                 if (entry->bitmap) {
 602                         /*
 603                          * if previous extent entry covers the offset,
 604                          * we should return it instead of the bitmap entry
 605                          */
 606                         n = rb_prev(&entry->offset_index);
 607                         if (n) {
 608                                 prev = rb_entry(n, struct btrfs_free_space,
 609                                                 offset_index);
 610                                 if (!prev->bitmap &&
 611                                     prev->offset + prev->bytes > offset)
 612                                         entry = prev;
 613                         }
 614                 }
 615                 return entry;
 616         }
 617
 618         if (!prev)
 619                 return NULL;
 620
 621         /* find last entry before the 'offset' */
 622         entry = prev;
 623         if (entry->offset > offset) {
 624                 n = rb_prev(&entry->offset_index);
 625                 if (n) {
 626                         entry = rb_entry(n, struct btrfs_free_space,
 627                                         offset_index);
 628                         BUG_ON(entry->offset > offset);
 629                 } else {
 630                         if (fuzzy)
 631                                 return entry;
 632                         else
 633                                 return NULL;
 634                 }
 635         }
 636
 637         if (entry->bitmap) {
 638                 n = rb_prev(&entry->offset_index);
 639                 if (n) {
 640                         prev = rb_entry(n, struct btrfs_free_space,
 641                                         offset_index);
 642                         if (!prev->bitmap &&
 643                             prev->offset + prev->bytes > offset)
 644                                 return prev;
 645                 }
 646                 if (entry->offset + BITS_PER_BITMAP(sectorsize) * ctl->unit > offset)
 647                         return entry;
 648         } else if (entry->offset + entry->bytes > offset)
 649                 return entry;
 650
 651         if (!fuzzy)
 652                 return NULL;
 653
 654         while (1) {
 655                 if (entry->bitmap) {
 656                         if (entry->offset + BITS_PER_BITMAP(sectorsize) *
 657                             ctl->unit > offset)
 658                                 break;
 659                 } else {
 660                         if (entry->offset + entry->bytes > offset)
 661                                 break;
 662                 }
 663
 664                 n = rb_next(&entry->offset_index);
 665                 if (!n)
 666                         return NULL;
 667                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 668         }
 669         return entry;
 670 }
 671
 672 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 673                        struct btrfs_free_space *info)
 674 {
 675         rb_erase(&info->offset_index, &ctl->free_space_offset);
 676         ctl->free_extents--;
 677         ctl->free_space -= info->bytes;
 678 }
 679
 680 static int link_free_space(struct btrfs_free_space_ctl *ctl,
 681                            struct btrfs_free_space *info)
 682 {
 683         int ret = 0;
 684
 685         BUG_ON(!info->bitmap && !info->bytes);
 686         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
 687                                  &info->offset_index, (info->bitmap != NULL));
 688         if (ret)
 689                 return ret;
 690
 691         ctl->free_space += info->bytes;
 692         ctl->free_extents++;
 693         return ret;
 694 }
 695
 696 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
 697                          struct btrfs_free_space *bitmap_info, u64 *offset,
 698                          u64 *bytes)
 699 {
 700         unsigned long found_bits = 0;
 701         unsigned long bits, i;
 702         unsigned long next_zero;
 703         u32 sectorsize = ctl->sectorsize;
 704
 705         i = offset_to_bit(bitmap_info->offset, ctl->unit,
 706                           max_t(u64, *offset, bitmap_info->offset));
 707         bits = bytes_to_bits(*bytes, ctl->unit);
 708
 709         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP(sectorsize)) {
 710                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
 711                                                BITS_PER_BITMAP(sectorsize), i);
 712                 if ((next_zero - i) >= bits) {
 713                         found_bits = next_zero - i;
 714                         break;
 715                 }
 716                 i = next_zero;
 717         }
 718
 719         if (found_bits) {
 720                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
 721                 *bytes = (u64)(found_bits) * ctl->unit;
 722                 return 0;
 723         }
 724
 725         return -1;
 726 }
 727
 728 struct btrfs_free_space *
 729 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
 730 {
 731         return tree_search_offset(ctl, offset, 0, 0);
 732 }
 733
 734 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
 735                                 struct btrfs_free_space *info)
 736 {
 737         struct btrfs_free_space *left_info;
 738         struct btrfs_free_space *right_info;
 739         u64 offset = info->offset;
 740         u64 bytes = info->bytes;
 741
 742         /*
 743          * first we want to see if there is free space adjacent to the range we
 744          * are adding, if there is remove that struct and add a new one to
 745          * cover the entire range
 746          */
 747         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
 748         if (right_info && rb_prev(&right_info->offset_index))
 749                 left_info = rb_entry(rb_prev(&right_info->offset_index),
 750                                      struct btrfs_free_space, offset_index);
 751         else
 752                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
 753
 754         if (right_info && !right_info->bitmap) {
 755                 unlink_free_space(ctl, right_info);
 756                 info->bytes += right_info->bytes;
 757                 free(right_info);
 758         }
 759
 760         if (left_info && !left_info->bitmap &&
 761             left_info->offset + left_info->bytes == offset) {
 762                 unlink_free_space(ctl, left_info);
 763                 info->offset = left_info->offset;
 764                 info->bytes += left_info->bytes;
 765                 free(left_info);
 766         }
 767 }
 768
 769 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
 770                            u64 bytes)
 771 {
 772         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 773         struct btrfs_free_space *info;
 774         struct rb_node *n;
 775         int count = 0;
 776
 777         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 778                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 779                 if (info->bytes >= bytes && !block_group->ro)
 780                         count++;
 781                 printk("entry offset %llu, bytes %llu, bitmap %s\n",
 782                        (unsigned long long)info->offset,
 783                        (unsigned long long)info->bytes,
 784                        (info->bitmap) ? "yes" : "no");
 785         }
 786         printk("%d blocks of free space at or bigger than bytes is \n", count);
 787 }
 788
 789 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
 790                               int sectorsize)
 791 {
 792         struct btrfs_free_space_ctl *ctl;
 793
 794         ctl = calloc(1, sizeof(*ctl));
 795         if (!ctl)
 796                 return -ENOMEM;
 797
 798         ctl->sectorsize = sectorsize;
 799         ctl->unit = sectorsize;
 800         ctl->start = block_group->key.objectid;
 801         ctl->private = block_group;
 802         block_group->free_space_ctl = ctl;
 803
 804         return 0;
 805 }
 806
 807 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
 808 {
 809         struct btrfs_free_space *info;
 810         struct rb_node *node;
 811
 812         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
 813                 info = rb_entry(node, struct btrfs_free_space, offset_index);
 814                 unlink_free_space(ctl, info);
 815                 free(info->bitmap);
 816                 free(info);
 817         }
 818 }
 819
 820 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 821 {
 822         __btrfs_remove_free_space_cache(block_group->free_space_ctl);
 823 }
 824
 825 int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
 826                          u64 bytes)
 827 {
 828         struct btrfs_free_space *info;
 829         int ret = 0;
 830
 831         info = calloc(1, sizeof(*info));
 832         if (!info)
 833                 return -ENOMEM;
 834
 835         info->offset = offset;
 836         info->bytes = bytes;
 837
 838         try_merge_free_space(ctl, info);
 839
 840         ret = link_free_space(ctl, info);
 841         if (ret) {
 842                 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
 843                 BUG_ON(ret == -EEXIST);
 844         }
 845
 846         return ret;
 847 }
 848
 849 /*
 850  * Merges all the free space cache and kills the bitmap entries since we just
 851  * want to use the free space cache to verify it's correct, no reason to keep
 852  * the bitmaps around to confuse things.
 853  */
 854 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
 855 {
 856         struct btrfs_free_space *e, *prev = NULL;
 857         struct rb_node *n;
 858         int ret;
 859         u32 sectorsize = ctl->sectorsize;
 860
 861 again:
 862         prev = NULL;
 863         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 864                 e = rb_entry(n, struct btrfs_free_space, offset_index);
 865                 if (e->bitmap) {
 866                         u64 offset = e->offset, bytes = ctl->unit;
 867                         u64 end;
 868
 869                         end = e->offset + (u64)(BITS_PER_BITMAP(sectorsize) * ctl->unit);
 870
 871                         unlink_free_space(ctl, e);
 872                         while (!(search_bitmap(ctl, e, &offset, &bytes))) {
 873                                 ret = btrfs_add_free_space(ctl, offset,
 874                                                            bytes);
 875                                 BUG_ON(ret);
 876                                 offset += bytes;
 877                                 if (offset >= end)
 878                                         break;
 879                                 bytes = ctl->unit;
 880                         }
 881                         free(e->bitmap);
 882                         free(e);
 883                         goto again;
 884                 }
 885                 if (!prev)
 886                         goto next;
 887                 if (prev->offset + prev->bytes == e->offset) {
 888                         unlink_free_space(ctl, prev);
 889                         unlink_free_space(ctl, e);
 890                         prev->bytes += e->bytes;
 891                         free(e);
 892                         link_free_space(ctl, prev);
 893                         goto again;
 894                 }
 895 next:
 896                 prev = e;
 897         }
 898 }
 899
 900 int btrfs_clear_free_space_cache(struct btrfs_fs_info *fs_info,
 901                                  struct btrfs_block_group_cache *bg)
 902 {
 903         struct btrfs_trans_handle *trans;
 904         struct btrfs_root *tree_root = fs_info->tree_root;
 905         struct btrfs_path path;
 906         struct btrfs_key key;
 907         struct btrfs_disk_key location;
 908         struct btrfs_free_space_header *sc_header;
 909         struct extent_buffer *node;
 910         u64 ino;
 911         int slot;
 912         int ret;
 913
 914         trans = btrfs_start_transaction(tree_root, 1);
 915         if (IS_ERR(trans))
 916                 return PTR_ERR(trans);
 917
 918         btrfs_init_path(&path);
 919
 920         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 921         key.type = 0;
 922         key.offset = bg->key.objectid;
 923
 924         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
 925         if (ret > 0) {
 926                 ret = 0;
 927                 goto out;
 928         }
 929         if (ret < 0)
 930                 goto out;
 931
 932         node = path.nodes[0];
 933         slot = path.slots[0];
 934         sc_header = btrfs_item_ptr(node, slot, struct btrfs_free_space_header);
 935         btrfs_free_space_key(node, sc_header, &location);
 936         ino = btrfs_disk_key_objectid(&location);
 937
 938         /* Delete the free space header, as we have the ino to continue */
 939         ret = btrfs_del_item(trans, tree_root, &path);
 940         if (ret < 0) {
 941                 error("failed to remove free space header for block group %llu: %d",
 942                       bg->key.objectid, ret);
 943                 goto out;
 944         }
 945         btrfs_release_path(&path);
 946
 947         /* Iterate from the end of the free space cache inode */
 948         key.objectid = ino;
 949         key.type = BTRFS_EXTENT_DATA_KEY;
 950         key.offset = (u64)-1;
 951         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
 952         if (ret < 0) {
 953                 error("failed to locate free space cache extent for block group %llu: %d",
 954                       bg->key.objectid, ret);
 955                 goto out;
 956         }
 957         while (1) {
 958                 struct btrfs_file_extent_item *fi;
 959                 u64 disk_bytenr;
 960                 u64 disk_num_bytes;
 961
 962                 ret = btrfs_previous_item(tree_root, &path, ino,
 963                                           BTRFS_EXTENT_DATA_KEY);
 964                 if (ret > 0) {
 965                         ret = 0;
 966                         break;
 967                 }
 968                 if (ret < 0) {
 969                         error(
 970         "failed to locate free space cache extent for block group %llu: %d",
 971                                 bg->key.objectid, ret);
 972                         goto out;
 973                 }
 974                 node = path.nodes[0];
 975                 slot = path.slots[0];
 976                 btrfs_item_key_to_cpu(node, &key, slot);
 977                 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
 978                 disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
 979                 disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
 980
 981                 ret = btrfs_free_extent(trans, tree_root, disk_bytenr,
 982                                         disk_num_bytes, 0, tree_root->objectid,
 983                                         ino, key.offset);
 984                 if (ret < 0) {
 985                         error("failed to remove backref for disk bytenr %llu: %d",
 986                               disk_bytenr, ret);
 987                         goto out;
 988                 }
 989                 ret = btrfs_del_item(trans, tree_root, &path);
 990                 if (ret < 0) {
 991                         error(
 992         "failed to remove free space extent data for ino %llu offset %llu: %d",
 993                               ino, key.offset, ret);
 994                         goto out;
 995                 }
 996         }
 997         btrfs_release_path(&path);
 998
 999         /* Now delete free space cache inode item */
1000         key.objectid = ino;
1001         key.type = BTRFS_INODE_ITEM_KEY;
1002         key.offset = 0;
1003
1004         ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
1005         if (ret > 0)
1006                 warning("free space inode %llu not found, ignore", ino);
1007         if (ret < 0) {
1008                 error(
1009         "failed to locate free space cache inode %llu for block group %llu: %d",
1010                       ino, bg->key.objectid, ret);
1011                 goto out;
1012         }
1013         ret = btrfs_del_item(trans, tree_root, &path);
1014         if (ret < 0) {
1015                 error(
1016         "failed to delete free space cache inode %llu for block group %llu: %d",
1017                       ino, bg->key.objectid, ret);
1018         }
1019 out:
1020         btrfs_release_path(&path);
1021         if (!ret)
1022                 btrfs_commit_transaction(trans, tree_root);
1023         return ret;
1024 }