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         leaf = path->nodes[0];
 295         header = btrfs_item_ptr(leaf, path->slots[0],
 296                                 struct btrfs_free_space_header);
 297         num_entries = btrfs_free_space_entries(leaf, header);
 298         num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
 299         generation = btrfs_free_space_generation(leaf, header);
 300         btrfs_free_space_key(leaf, header, &disk_key);
 301         btrfs_disk_key_to_cpu(&inode_location, &disk_key);
 302         btrfs_release_path(path);
 303
 304         ret = btrfs_search_slot(NULL, root, &inode_location, path, 0, 0);
 305         if (ret) {
 306                 printf("Couldn't find free space inode %d\n", ret);
 307                 return 0;
 308         }
 309
 310         leaf = path->nodes[0];
 311         inode_item = btrfs_item_ptr(leaf, path->slots[0],
 312                                     struct btrfs_inode_item);
 313         if (btrfs_inode_generation(leaf, inode_item) != generation) {
 314                 printf("free space inode generation (%llu) did not match "
 315                        "free space cache generation (%llu)\n",
 316                        (unsigned long long)btrfs_inode_generation(leaf,
 317                                                                   inode_item),
 318                        (unsigned long long)generation);
 319                 btrfs_release_path(path);
 320                 return 0;
 321         }
 322
 323         inode_size = btrfs_inode_size(leaf, inode_item);
 324         btrfs_release_path(path);
 325         if (inode_size == 0)
 326                 return 0;
 327
 328         if (!num_entries)
 329                 return 0;
 330
 331         ret = io_ctl_init(&io_ctl, inode_size, inode_location.objectid, root);
 332         if (ret)
 333                 return ret;
 334
 335         ret = io_ctl_prepare_pages(&io_ctl, root, path,
 336                                    inode_location.objectid);
 337         if (ret)
 338                 goto out;
 339
 340         ret = io_ctl_check_crc(&io_ctl, 0);
 341         if (ret)
 342                 goto free_cache;
 343
 344         ret = io_ctl_check_generation(&io_ctl, generation);
 345         if (ret)
 346                 goto free_cache;
 347
 348         while (num_entries) {
 349                 e = calloc(1, sizeof(*e));
 350                 if (!e)
 351                         goto free_cache;
 352
 353                 ret = io_ctl_read_entry(&io_ctl, e, &type);
 354                 if (ret) {
 355                         free(e);
 356                         goto free_cache;
 357                 }
 358
 359                 if (!e->bytes) {
 360                         free(e);
 361                         goto free_cache;
 362                 }
 363
 364                 if (type == BTRFS_FREE_SPACE_EXTENT) {
 365                         ret = link_free_space(ctl, e);
 366                         if (ret) {
 367                                 printf("Duplicate entries in free space cache, dumping");
 368                                 free(e);
 369                                 goto free_cache;
 370                         }
 371                 } else {
 372                         BUG_ON(!num_bitmaps);
 373                         num_bitmaps--;
 374                         e->bitmap = kzalloc(CACHE_SECTORSIZE, GFP_NOFS);
 375                         if (!e->bitmap) {
 376                                 free(e);
 377                                 goto free_cache;
 378                         }
 379                         ret = link_free_space(ctl, e);
 380                         ctl->total_bitmaps++;
 381                         if (ret) {
 382                                 printf("Duplicate entries in free space cache, dumping");
 383                                 free(e->bitmap);
 384                                 free(e);
 385                                 goto free_cache;
 386                         }
 387                         list_add_tail(&e->list, &bitmaps);
 388                 }
 389
 390                 num_entries--;
 391         }
 392
 393         io_ctl_unmap_page(&io_ctl);
 394
 395         /*
 396          * We add the bitmaps at the end of the entries in order that
 397          * the bitmap entries are added to the cache.
 398          */
 399         list_for_each_entry_safe(e, n, &bitmaps, list) {
 400                 list_del_init(&e->list);
 401                 ret = io_ctl_read_bitmap(&io_ctl, e);
 402                 if (ret)
 403                         goto free_cache;
 404         }
 405
 406         io_ctl_drop_pages(&io_ctl);
 407         merge_space_tree(ctl);
 408         ret = 1;
 409 out:
 410         io_ctl_free(&io_ctl);
 411         return ret;
 412 free_cache:
 413         io_ctl_drop_pages(&io_ctl);
 414         __btrfs_remove_free_space_cache(ctl);
 415         goto out;
 416 }
 417
 418 int load_free_space_cache(struct btrfs_fs_info *fs_info,
 419                           struct btrfs_block_group_cache *block_group)
 420 {
 421         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 422         struct btrfs_path *path;
 423         int ret = 0;
 424
 425         path = btrfs_alloc_path();
 426         if (!path)
 427                 return 0;
 428
 429         ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
 430                                       block_group->key.objectid);
 431         btrfs_free_path(path);
 432
 433         if (ret < 0) {
 434                 ret = 0;
 435
 436                 printf("failed to load free space cache for block group %llu\n",
 437                         block_group->key.objectid);
 438         }
 439
 440         return ret;
 441 }
 442
 443 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
 444                                           u64 offset)
 445 {
 446         BUG_ON(offset < bitmap_start);
 447         offset -= bitmap_start;
 448         return (unsigned long)(offset / unit);
 449 }
 450
 451 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
 452 {
 453         return (unsigned long)(bytes / unit);
 454 }
 455
 456 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
 457                                    u64 offset)
 458 {
 459         u64 bitmap_start;
 460         u64 bytes_per_bitmap;
 461
 462         bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
 463         bitmap_start = offset - ctl->start;
 464         bitmap_start = bitmap_start / bytes_per_bitmap;
 465         bitmap_start *= bytes_per_bitmap;
 466         bitmap_start += ctl->start;
 467
 468         return bitmap_start;
 469 }
 470
 471 static int tree_insert_offset(struct rb_root *root, u64 offset,
 472                               struct rb_node *node, int bitmap)
 473 {
 474         struct rb_node **p = &root->rb_node;
 475         struct rb_node *parent = NULL;
 476         struct btrfs_free_space *info;
 477
 478         while (*p) {
 479                 parent = *p;
 480                 info = rb_entry(parent, struct btrfs_free_space, offset_index);
 481
 482                 if (offset < info->offset) {
 483                         p = &(*p)->rb_left;
 484                 } else if (offset > info->offset) {
 485                         p = &(*p)->rb_right;
 486                 } else {
 487                         /*
 488                          * we could have a bitmap entry and an extent entry
 489                          * share the same offset.  If this is the case, we want
 490                          * the extent entry to always be found first if we do a
 491                          * linear search through the tree, since we want to have
 492                          * the quickest allocation time, and allocating from an
 493                          * extent is faster than allocating from a bitmap.  So
 494                          * if we're inserting a bitmap and we find an entry at
 495                          * this offset, we want to go right, or after this entry
 496                          * logically.  If we are inserting an extent and we've
 497                          * found a bitmap, we want to go left, or before
 498                          * logically.
 499                          */
 500                         if (bitmap) {
 501                                 if (info->bitmap)
 502                                         return -EEXIST;
 503                                 p = &(*p)->rb_right;
 504                         } else {
 505                                 if (!info->bitmap)
 506                                         return -EEXIST;
 507                                 p = &(*p)->rb_left;
 508                         }
 509                 }
 510         }
 511
 512         rb_link_node(node, parent, p);
 513         rb_insert_color(node, root);
 514
 515         return 0;
 516 }
 517
 518 /*
 519  * searches the tree for the given offset.
 520  *
 521  * fuzzy - If this is set, then we are trying to make an allocation, and we just
 522  * want a section that has at least bytes size and comes at or after the given
 523  * offset.
 524  */
 525 static struct btrfs_free_space *
 526 tree_search_offset(struct btrfs_free_space_ctl *ctl,
 527                    u64 offset, int bitmap_only, int fuzzy)
 528 {
 529         struct rb_node *n = ctl->free_space_offset.rb_node;
 530         struct btrfs_free_space *entry, *prev = NULL;
 531
 532         /* find entry that is closest to the 'offset' */
 533         while (1) {
 534                 if (!n) {
 535                         entry = NULL;
 536                         break;
 537                 }
 538
 539                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 540                 prev = entry;
 541
 542                 if (offset < entry->offset)
 543                         n = n->rb_left;
 544                 else if (offset > entry->offset)
 545                         n = n->rb_right;
 546                 else
 547                         break;
 548         }
 549
 550         if (bitmap_only) {
 551                 if (!entry)
 552                         return NULL;
 553                 if (entry->bitmap)
 554                         return entry;
 555
 556                 /*
 557                  * bitmap entry and extent entry may share same offset,
 558                  * in that case, bitmap entry comes after extent entry.
 559                  */
 560                 n = rb_next(n);
 561                 if (!n)
 562                         return NULL;
 563                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 564                 if (entry->offset != offset)
 565                         return NULL;
 566
 567                 WARN_ON(!entry->bitmap);
 568                 return entry;
 569         } else if (entry) {
 570                 if (entry->bitmap) {
 571                         /*
 572                          * if previous extent entry covers the offset,
 573                          * we should return it instead of the bitmap entry
 574                          */
 575                         n = rb_prev(&entry->offset_index);
 576                         if (n) {
 577                                 prev = rb_entry(n, struct btrfs_free_space,
 578                                                 offset_index);
 579                                 if (!prev->bitmap &&
 580                                     prev->offset + prev->bytes > offset)
 581                                         entry = prev;
 582                         }
 583                 }
 584                 return entry;
 585         }
 586
 587         if (!prev)
 588                 return NULL;
 589
 590         /* find last entry before the 'offset' */
 591         entry = prev;
 592         if (entry->offset > offset) {
 593                 n = rb_prev(&entry->offset_index);
 594                 if (n) {
 595                         entry = rb_entry(n, struct btrfs_free_space,
 596                                         offset_index);
 597                         BUG_ON(entry->offset > offset);
 598                 } else {
 599                         if (fuzzy)
 600                                 return entry;
 601                         else
 602                                 return NULL;
 603                 }
 604         }
 605
 606         if (entry->bitmap) {
 607                 n = rb_prev(&entry->offset_index);
 608                 if (n) {
 609                         prev = rb_entry(n, struct btrfs_free_space,
 610                                         offset_index);
 611                         if (!prev->bitmap &&
 612                             prev->offset + prev->bytes > offset)
 613                                 return prev;
 614                 }
 615                 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
 616                         return entry;
 617         } else if (entry->offset + entry->bytes > offset)
 618                 return entry;
 619
 620         if (!fuzzy)
 621                 return NULL;
 622
 623         while (1) {
 624                 if (entry->bitmap) {
 625                         if (entry->offset + BITS_PER_BITMAP *
 626                             ctl->unit > offset)
 627                                 break;
 628                 } else {
 629                         if (entry->offset + entry->bytes > offset)
 630                                 break;
 631                 }
 632
 633                 n = rb_next(&entry->offset_index);
 634                 if (!n)
 635                         return NULL;
 636                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 637         }
 638         return entry;
 639 }
 640
 641 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 642                        struct btrfs_free_space *info)
 643 {
 644         rb_erase(&info->offset_index, &ctl->free_space_offset);
 645         ctl->free_extents--;
 646         ctl->free_space -= info->bytes;
 647 }
 648
 649 static int link_free_space(struct btrfs_free_space_ctl *ctl,
 650                            struct btrfs_free_space *info)
 651 {
 652         int ret = 0;
 653
 654         BUG_ON(!info->bitmap && !info->bytes);
 655         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
 656                                  &info->offset_index, (info->bitmap != NULL));
 657         if (ret)
 658                 return ret;
 659
 660         ctl->free_space += info->bytes;
 661         ctl->free_extents++;
 662         return ret;
 663 }
 664
 665 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
 666                          struct btrfs_free_space *bitmap_info, u64 *offset,
 667                          u64 *bytes)
 668 {
 669         unsigned long found_bits = 0;
 670         unsigned long bits, i;
 671         unsigned long next_zero;
 672
 673         i = offset_to_bit(bitmap_info->offset, ctl->unit,
 674                           max_t(u64, *offset, bitmap_info->offset));
 675         bits = bytes_to_bits(*bytes, ctl->unit);
 676
 677         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
 678                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
 679                                                BITS_PER_BITMAP, i);
 680                 if ((next_zero - i) >= bits) {
 681                         found_bits = next_zero - i;
 682                         break;
 683                 }
 684                 i = next_zero;
 685         }
 686
 687         if (found_bits) {
 688                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
 689                 *bytes = (u64)(found_bits) * ctl->unit;
 690                 return 0;
 691         }
 692
 693         return -1;
 694 }
 695
 696 struct btrfs_free_space *
 697 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
 698 {
 699         return tree_search_offset(ctl, offset, 0, 0);
 700 }
 701
 702 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
 703                                 struct btrfs_free_space *info)
 704 {
 705         struct btrfs_free_space *left_info;
 706         struct btrfs_free_space *right_info;
 707         u64 offset = info->offset;
 708         u64 bytes = info->bytes;
 709
 710         /*
 711          * first we want to see if there is free space adjacent to the range we
 712          * are adding, if there is remove that struct and add a new one to
 713          * cover the entire range
 714          */
 715         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
 716         if (right_info && rb_prev(&right_info->offset_index))
 717                 left_info = rb_entry(rb_prev(&right_info->offset_index),
 718                                      struct btrfs_free_space, offset_index);
 719         else
 720                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
 721
 722         if (right_info && !right_info->bitmap) {
 723                 unlink_free_space(ctl, right_info);
 724                 info->bytes += right_info->bytes;
 725                 free(right_info);
 726         }
 727
 728         if (left_info && !left_info->bitmap &&
 729             left_info->offset + left_info->bytes == offset) {
 730                 unlink_free_space(ctl, left_info);
 731                 info->offset = left_info->offset;
 732                 info->bytes += left_info->bytes;
 733                 free(left_info);
 734         }
 735 }
 736
 737 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
 738                            u64 bytes)
 739 {
 740         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 741         struct btrfs_free_space *info;
 742         struct rb_node *n;
 743         int count = 0;
 744
 745         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 746                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 747                 if (info->bytes >= bytes && !block_group->ro)
 748                         count++;
 749                 printk("entry offset %llu, bytes %llu, bitmap %s\n",
 750                        (unsigned long long)info->offset,
 751                        (unsigned long long)info->bytes,
 752                        (info->bitmap) ? "yes" : "no");
 753         }
 754         printk("%d blocks of free space at or bigger than bytes is \n", count);
 755 }
 756
 757 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
 758                               int sectorsize)
 759 {
 760         struct btrfs_free_space_ctl *ctl;
 761
 762         ctl = calloc(1, sizeof(*ctl));
 763         if (!ctl)
 764                 return -ENOMEM;
 765
 766         ctl->unit = sectorsize;
 767         ctl->start = block_group->key.objectid;
 768         ctl->private = block_group;
 769         block_group->free_space_ctl = ctl;
 770
 771         return 0;
 772 }
 773
 774 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
 775 {
 776         struct btrfs_free_space *info;
 777         struct rb_node *node;
 778
 779         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
 780                 info = rb_entry(node, struct btrfs_free_space, offset_index);
 781                 unlink_free_space(ctl, info);
 782                 free(info->bitmap);
 783                 free(info);
 784         }
 785 }
 786
 787 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 788 {
 789         __btrfs_remove_free_space_cache(block_group->free_space_ctl);
 790 }
 791
 792 static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
 793                                 u64 bytes)
 794 {
 795         struct btrfs_free_space *info;
 796         int ret = 0;
 797
 798         info = calloc(1, sizeof(*info));
 799         if (!info)
 800                 return -ENOMEM;
 801
 802         info->offset = offset;
 803         info->bytes = bytes;
 804
 805         try_merge_free_space(ctl, info);
 806
 807         ret = link_free_space(ctl, info);
 808         if (ret) {
 809                 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
 810                 BUG_ON(ret == -EEXIST);
 811         }
 812
 813         return ret;
 814 }
 815
 816 /*
 817  * Merges all the free space cache and kills the bitmap entries since we just
 818  * want to use the free space cache to verify it's correct, no reason to keep
 819  * the bitmaps around to confuse things.
 820  */
 821 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
 822 {
 823         struct btrfs_free_space *e, *prev = NULL;
 824         struct rb_node *n;
 825         int ret;
 826
 827 again:
 828         prev = NULL;
 829         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 830                 e = rb_entry(n, struct btrfs_free_space, offset_index);
 831                 if (e->bitmap) {
 832                         u64 offset = e->offset, bytes = ctl->unit;
 833                         u64 end;
 834
 835                         end = e->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
 836
 837                         unlink_free_space(ctl, e);
 838                         while (!(search_bitmap(ctl, e, &offset, &bytes))) {
 839                                 ret = btrfs_add_free_space(ctl, offset,
 840                                                            bytes);
 841                                 BUG_ON(ret);
 842                                 offset += bytes;
 843                                 if (offset >= end)
 844                                         break;
 845                                 bytes = ctl->unit;
 846                         }
 847                         free(e->bitmap);
 848                         free(e);
 849                         goto again;
 850                 }
 851                 if (!prev)
 852                         goto next;
 853                 if (prev->offset + prev->bytes == e->offset) {
 854                         unlink_free_space(ctl, prev);
 855                         unlink_free_space(ctl, e);
 856                         prev->bytes += e->bytes;
 857                         free(e);
 858                         link_free_space(ctl, prev);
 859                         goto again;
 860                 }
 861 next:
 862                 prev = e;
 863         }
 864 }