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         u64 used = btrfs_block_group_used(&block_group->item);
 432         int ret = 0;
 433         int matched;
 434
 435         path = btrfs_alloc_path();
 436         if (!path)
 437                 return 0;
 438
 439         ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
 440                                       block_group->key.objectid);
 441         btrfs_free_path(path);
 442
 443         matched = (ctl->free_space == (block_group->key.offset - used -
 444                                        block_group->bytes_super));
 445         if (ret == 1 && !matched) {
 446                 __btrfs_remove_free_space_cache(ctl);
 447                 printf("block group %llu has wrong amount of free space",
 448                        block_group->key.objectid);
 449                 ret = -1;
 450         }
 451
 452         if (ret < 0) {
 453                 ret = 0;
 454
 455                 printf("failed to load free space cache for block group %llu\n",
 456                         block_group->key.objectid);
 457         }
 458
 459         return ret;
 460 }
 461
 462 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
 463                                           u64 offset)
 464 {
 465         BUG_ON(offset < bitmap_start);
 466         offset -= bitmap_start;
 467         return (unsigned long)(offset / unit);
 468 }
 469
 470 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
 471 {
 472         return (unsigned long)(bytes / unit);
 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         u32 sectorsize = ctl->sectorsize;
 536
 537         /* find entry that is closest to the 'offset' */
 538         while (1) {
 539                 if (!n) {
 540                         entry = NULL;
 541                         break;
 542                 }
 543
 544                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 545                 prev = entry;
 546
 547                 if (offset < entry->offset)
 548                         n = n->rb_left;
 549                 else if (offset > entry->offset)
 550                         n = n->rb_right;
 551                 else
 552                         break;
 553         }
 554
 555         if (bitmap_only) {
 556                 if (!entry)
 557                         return NULL;
 558                 if (entry->bitmap)
 559                         return entry;
 560
 561                 /*
 562                  * bitmap entry and extent entry may share same offset,
 563                  * in that case, bitmap entry comes after extent entry.
 564                  */
 565                 n = rb_next(n);
 566                 if (!n)
 567                         return NULL;
 568                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 569                 if (entry->offset != offset)
 570                         return NULL;
 571
 572                 WARN_ON(!entry->bitmap);
 573                 return entry;
 574         } else if (entry) {
 575                 if (entry->bitmap) {
 576                         /*
 577                          * if previous extent entry covers the offset,
 578                          * we should return it instead of the bitmap entry
 579                          */
 580                         n = rb_prev(&entry->offset_index);
 581                         if (n) {
 582                                 prev = rb_entry(n, struct btrfs_free_space,
 583                                                 offset_index);
 584                                 if (!prev->bitmap &&
 585                                     prev->offset + prev->bytes > offset)
 586                                         entry = prev;
 587                         }
 588                 }
 589                 return entry;
 590         }
 591
 592         if (!prev)
 593                 return NULL;
 594
 595         /* find last entry before the 'offset' */
 596         entry = prev;
 597         if (entry->offset > offset) {
 598                 n = rb_prev(&entry->offset_index);
 599                 if (n) {
 600                         entry = rb_entry(n, struct btrfs_free_space,
 601                                         offset_index);
 602                         BUG_ON(entry->offset > offset);
 603                 } else {
 604                         if (fuzzy)
 605                                 return entry;
 606                         else
 607                                 return NULL;
 608                 }
 609         }
 610
 611         if (entry->bitmap) {
 612                 n = rb_prev(&entry->offset_index);
 613                 if (n) {
 614                         prev = rb_entry(n, struct btrfs_free_space,
 615                                         offset_index);
 616                         if (!prev->bitmap &&
 617                             prev->offset + prev->bytes > offset)
 618                                 return prev;
 619                 }
 620                 if (entry->offset + BITS_PER_BITMAP(sectorsize) * ctl->unit > offset)
 621                         return entry;
 622         } else if (entry->offset + entry->bytes > offset)
 623                 return entry;
 624
 625         if (!fuzzy)
 626                 return NULL;
 627
 628         while (1) {
 629                 if (entry->bitmap) {
 630                         if (entry->offset + BITS_PER_BITMAP(sectorsize) *
 631                             ctl->unit > offset)
 632                                 break;
 633                 } else {
 634                         if (entry->offset + entry->bytes > offset)
 635                                 break;
 636                 }
 637
 638                 n = rb_next(&entry->offset_index);
 639                 if (!n)
 640                         return NULL;
 641                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
 642         }
 643         return entry;
 644 }
 645
 646 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
 647                        struct btrfs_free_space *info)
 648 {
 649         rb_erase(&info->offset_index, &ctl->free_space_offset);
 650         ctl->free_extents--;
 651         ctl->free_space -= info->bytes;
 652 }
 653
 654 static int link_free_space(struct btrfs_free_space_ctl *ctl,
 655                            struct btrfs_free_space *info)
 656 {
 657         int ret = 0;
 658
 659         BUG_ON(!info->bitmap && !info->bytes);
 660         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
 661                                  &info->offset_index, (info->bitmap != NULL));
 662         if (ret)
 663                 return ret;
 664
 665         ctl->free_space += info->bytes;
 666         ctl->free_extents++;
 667         return ret;
 668 }
 669
 670 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
 671                          struct btrfs_free_space *bitmap_info, u64 *offset,
 672                          u64 *bytes)
 673 {
 674         unsigned long found_bits = 0;
 675         unsigned long bits, i;
 676         unsigned long next_zero;
 677         u32 sectorsize = ctl->sectorsize;
 678
 679         i = offset_to_bit(bitmap_info->offset, ctl->unit,
 680                           max_t(u64, *offset, bitmap_info->offset));
 681         bits = bytes_to_bits(*bytes, ctl->unit);
 682
 683         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP(sectorsize)) {
 684                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
 685                                                BITS_PER_BITMAP(sectorsize), i);
 686                 if ((next_zero - i) >= bits) {
 687                         found_bits = next_zero - i;
 688                         break;
 689                 }
 690                 i = next_zero;
 691         }
 692
 693         if (found_bits) {
 694                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
 695                 *bytes = (u64)(found_bits) * ctl->unit;
 696                 return 0;
 697         }
 698
 699         return -1;
 700 }
 701
 702 struct btrfs_free_space *
 703 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
 704 {
 705         return tree_search_offset(ctl, offset, 0, 0);
 706 }
 707
 708 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
 709                                 struct btrfs_free_space *info)
 710 {
 711         struct btrfs_free_space *left_info;
 712         struct btrfs_free_space *right_info;
 713         u64 offset = info->offset;
 714         u64 bytes = info->bytes;
 715
 716         /*
 717          * first we want to see if there is free space adjacent to the range we
 718          * are adding, if there is remove that struct and add a new one to
 719          * cover the entire range
 720          */
 721         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
 722         if (right_info && rb_prev(&right_info->offset_index))
 723                 left_info = rb_entry(rb_prev(&right_info->offset_index),
 724                                      struct btrfs_free_space, offset_index);
 725         else
 726                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
 727
 728         if (right_info && !right_info->bitmap) {
 729                 unlink_free_space(ctl, right_info);
 730                 info->bytes += right_info->bytes;
 731                 free(right_info);
 732         }
 733
 734         if (left_info && !left_info->bitmap &&
 735             left_info->offset + left_info->bytes == offset) {
 736                 unlink_free_space(ctl, left_info);
 737                 info->offset = left_info->offset;
 738                 info->bytes += left_info->bytes;
 739                 free(left_info);
 740         }
 741 }
 742
 743 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
 744                            u64 bytes)
 745 {
 746         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 747         struct btrfs_free_space *info;
 748         struct rb_node *n;
 749         int count = 0;
 750
 751         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 752                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 753                 if (info->bytes >= bytes && !block_group->ro)
 754                         count++;
 755                 printk("entry offset %llu, bytes %llu, bitmap %s\n",
 756                        (unsigned long long)info->offset,
 757                        (unsigned long long)info->bytes,
 758                        (info->bitmap) ? "yes" : "no");
 759         }
 760         printk("%d blocks of free space at or bigger than bytes is \n", count);
 761 }
 762
 763 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
 764                               int sectorsize)
 765 {
 766         struct btrfs_free_space_ctl *ctl;
 767
 768         ctl = calloc(1, sizeof(*ctl));
 769         if (!ctl)
 770                 return -ENOMEM;
 771
 772         ctl->sectorsize = sectorsize;
 773         ctl->unit = sectorsize;
 774         ctl->start = block_group->key.objectid;
 775         ctl->private = block_group;
 776         block_group->free_space_ctl = ctl;
 777
 778         return 0;
 779 }
 780
 781 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
 782 {
 783         struct btrfs_free_space *info;
 784         struct rb_node *node;
 785
 786         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
 787                 info = rb_entry(node, struct btrfs_free_space, offset_index);
 788                 unlink_free_space(ctl, info);
 789                 free(info->bitmap);
 790                 free(info);
 791         }
 792 }
 793
 794 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 795 {
 796         __btrfs_remove_free_space_cache(block_group->free_space_ctl);
 797 }
 798
 799 static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
 800                                 u64 bytes)
 801 {
 802         struct btrfs_free_space *info;
 803         int ret = 0;
 804
 805         info = calloc(1, sizeof(*info));
 806         if (!info)
 807                 return -ENOMEM;
 808
 809         info->offset = offset;
 810         info->bytes = bytes;
 811
 812         try_merge_free_space(ctl, info);
 813
 814         ret = link_free_space(ctl, info);
 815         if (ret) {
 816                 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
 817                 BUG_ON(ret == -EEXIST);
 818         }
 819
 820         return ret;
 821 }
 822
 823 /*
 824  * Merges all the free space cache and kills the bitmap entries since we just
 825  * want to use the free space cache to verify it's correct, no reason to keep
 826  * the bitmaps around to confuse things.
 827  */
 828 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
 829 {
 830         struct btrfs_free_space *e, *prev = NULL;
 831         struct rb_node *n;
 832         int ret;
 833         u32 sectorsize = ctl->sectorsize;
 834
 835 again:
 836         prev = NULL;
 837         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
 838                 e = rb_entry(n, struct btrfs_free_space, offset_index);
 839                 if (e->bitmap) {
 840                         u64 offset = e->offset, bytes = ctl->unit;
 841                         u64 end;
 842
 843                         end = e->offset + (u64)(BITS_PER_BITMAP(sectorsize) * ctl->unit);
 844
 845                         unlink_free_space(ctl, e);
 846                         while (!(search_bitmap(ctl, e, &offset, &bytes))) {
 847                                 ret = btrfs_add_free_space(ctl, offset,
 848                                                            bytes);
 849                                 BUG_ON(ret);
 850                                 offset += bytes;
 851                                 if (offset >= end)
 852                                         break;
 853                                 bytes = ctl->unit;
 854                         }
 855                         free(e->bitmap);
 856                         free(e);
 857                         goto again;
 858                 }
 859                 if (!prev)
 860                         goto next;
 861                 if (prev->offset + prev->bytes == e->offset) {
 862                         unlink_free_space(ctl, prev);
 863                         unlink_free_space(ctl, e);
 864                         prev->bytes += e->bytes;
 865                         free(e);
 866                         link_free_space(ctl, prev);
 867                         goto again;
 868                 }
 869 next:
 870                 prev = e;
 871         }
 872 }