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