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