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