fs/btrfs/inode-map.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  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 <linux/delay.h>
  20 #include <linux/kthread.h>
  21 #include <linux/pagemap.h>
  22
  23 #include "ctree.h"
  24 #include "disk-io.h"
  25 #include "free-space-cache.h"
  26 #include "inode-map.h"
  27 #include "transaction.h"
  28
  29 static void fail_caching_thread(struct btrfs_root *root)
  30 {
  31         struct btrfs_fs_info *fs_info = root->fs_info;
  32
  33         btrfs_warn(fs_info, "failed to start inode caching task");
  34         btrfs_clear_pending_and_info(fs_info, INODE_MAP_CACHE,
  35                                      "disabling inode map caching");
  36         spin_lock(&root->ino_cache_lock);
  37         root->ino_cache_state = BTRFS_CACHE_ERROR;
  38         spin_unlock(&root->ino_cache_lock);
  39         wake_up(&root->ino_cache_wait);
  40 }
  41
  42 static int caching_kthread(void *data)
  43 {
  44         struct btrfs_root *root = data;
  45         struct btrfs_fs_info *fs_info = root->fs_info;
  46         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
  47         struct btrfs_key key;
  48         struct btrfs_path *path;
  49         struct extent_buffer *leaf;
  50         u64 last = (u64)-1;
  51         int slot;
  52         int ret;
  53
  54         if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
  55                 return 0;
  56
  57         path = btrfs_alloc_path();
  58         if (!path) {
  59                 fail_caching_thread(root);
  60                 return -ENOMEM;
  61         }
  62
  63         /* Since the commit root is read-only, we can safely skip locking. */
  64         path->skip_locking = 1;
  65         path->search_commit_root = 1;
  66         path->reada = READA_FORWARD;
  67
  68         key.objectid = BTRFS_FIRST_FREE_OBJECTID;
  69         key.offset = 0;
  70         key.type = BTRFS_INODE_ITEM_KEY;
  71 again:
  72         /* need to make sure the commit_root doesn't disappear */
  73         down_read(&fs_info->commit_root_sem);
  74
  75         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  76         if (ret < 0)
  77                 goto out;
  78
  79         while (1) {
  80                 if (btrfs_fs_closing(fs_info))
  81                         goto out;
  82
  83                 leaf = path->nodes[0];
  84                 slot = path->slots[0];
  85                 if (slot >= btrfs_header_nritems(leaf)) {
  86                         ret = btrfs_next_leaf(root, path);
  87                         if (ret < 0)
  88                                 goto out;
  89                         else if (ret > 0)
  90                                 break;
  91
  92                         if (need_resched() ||
  93                             btrfs_transaction_in_commit(fs_info)) {
  94                                 leaf = path->nodes[0];
  95
  96                                 if (WARN_ON(btrfs_header_nritems(leaf) == 0))
  97                                         break;
  98
  99                                 /*
 100                                  * Save the key so we can advances forward
 101                                  * in the next search.
 102                                  */
 103                                 btrfs_item_key_to_cpu(leaf, &key, 0);
 104                                 btrfs_release_path(path);
 105                                 root->ino_cache_progress = last;
 106                                 up_read(&fs_info->commit_root_sem);
 107                                 schedule_timeout(1);
 108                                 goto again;
 109                         } else
 110                                 continue;
 111                 }
 112
 113                 btrfs_item_key_to_cpu(leaf, &key, slot);
 114
 115                 if (key.type != BTRFS_INODE_ITEM_KEY)
 116                         goto next;
 117
 118                 if (key.objectid >= root->highest_objectid)
 119                         break;
 120
 121                 if (last != (u64)-1 && last + 1 != key.objectid) {
 122                         __btrfs_add_free_space(fs_info, ctl, last + 1,
 123                                                key.objectid - last - 1);
 124                         wake_up(&root->ino_cache_wait);
 125                 }
 126
 127                 last = key.objectid;
 128 next:
 129                 path->slots[0]++;
 130         }
 131
 132         if (last < root->highest_objectid - 1) {
 133                 __btrfs_add_free_space(fs_info, ctl, last + 1,
 134                                        root->highest_objectid - last - 1);
 135         }
 136
 137         spin_lock(&root->ino_cache_lock);
 138         root->ino_cache_state = BTRFS_CACHE_FINISHED;
 139         spin_unlock(&root->ino_cache_lock);
 140
 141         root->ino_cache_progress = (u64)-1;
 142         btrfs_unpin_free_ino(root);
 143 out:
 144         wake_up(&root->ino_cache_wait);
 145         up_read(&fs_info->commit_root_sem);
 146
 147         btrfs_free_path(path);
 148
 149         return ret;
 150 }
 151
 152 static void start_caching(struct btrfs_root *root)
 153 {
 154         struct btrfs_fs_info *fs_info = root->fs_info;
 155         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
 156         struct task_struct *tsk;
 157         int ret;
 158         u64 objectid;
 159
 160         if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
 161                 return;
 162
 163         spin_lock(&root->ino_cache_lock);
 164         if (root->ino_cache_state != BTRFS_CACHE_NO) {
 165                 spin_unlock(&root->ino_cache_lock);
 166                 return;
 167         }
 168
 169         root->ino_cache_state = BTRFS_CACHE_STARTED;
 170         spin_unlock(&root->ino_cache_lock);
 171
 172         ret = load_free_ino_cache(fs_info, root);
 173         if (ret == 1) {
 174                 spin_lock(&root->ino_cache_lock);
 175                 root->ino_cache_state = BTRFS_CACHE_FINISHED;
 176                 spin_unlock(&root->ino_cache_lock);
 177                 wake_up(&root->ino_cache_wait);
 178                 return;
 179         }
 180
 181         /*
 182          * It can be quite time-consuming to fill the cache by searching
 183          * through the extent tree, and this can keep ino allocation path
 184          * waiting. Therefore at start we quickly find out the highest
 185          * inode number and we know we can use inode numbers which fall in
 186          * [highest_ino + 1, BTRFS_LAST_FREE_OBJECTID].
 187          */
 188         ret = btrfs_find_free_objectid(root, &objectid);
 189         if (!ret && objectid <= BTRFS_LAST_FREE_OBJECTID) {
 190                 __btrfs_add_free_space(fs_info, ctl, objectid,
 191                                        BTRFS_LAST_FREE_OBJECTID - objectid + 1);
 192         }
 193
 194         tsk = kthread_run(caching_kthread, root, "btrfs-ino-cache-%llu",
 195                           root->root_key.objectid);
 196         if (IS_ERR(tsk))
 197                 fail_caching_thread(root);
 198 }
 199
 200 int btrfs_find_free_ino(struct btrfs_root *root, u64 *objectid)
 201 {
 202         if (!btrfs_test_opt(root->fs_info, INODE_MAP_CACHE))
 203                 return btrfs_find_free_objectid(root, objectid);
 204
 205 again:
 206         *objectid = btrfs_find_ino_for_alloc(root);
 207
 208         if (*objectid != 0)
 209                 return 0;
 210
 211         start_caching(root);
 212
 213         wait_event(root->ino_cache_wait,
 214                    root->ino_cache_state == BTRFS_CACHE_FINISHED ||
 215                    root->ino_cache_state == BTRFS_CACHE_ERROR ||
 216                    root->free_ino_ctl->free_space > 0);
 217
 218         if (root->ino_cache_state == BTRFS_CACHE_FINISHED &&
 219             root->free_ino_ctl->free_space == 0)
 220                 return -ENOSPC;
 221         else if (root->ino_cache_state == BTRFS_CACHE_ERROR)
 222                 return btrfs_find_free_objectid(root, objectid);
 223         else
 224                 goto again;
 225 }
 226
 227 void btrfs_return_ino(struct btrfs_root *root, u64 objectid)
 228 {
 229         struct btrfs_fs_info *fs_info = root->fs_info;
 230         struct btrfs_free_space_ctl *pinned = root->free_ino_pinned;
 231
 232         if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
 233                 return;
 234 again:
 235         if (root->ino_cache_state == BTRFS_CACHE_FINISHED) {
 236                 __btrfs_add_free_space(fs_info, pinned, objectid, 1);
 237         } else {
 238                 down_write(&fs_info->commit_root_sem);
 239                 spin_lock(&root->ino_cache_lock);
 240                 if (root->ino_cache_state == BTRFS_CACHE_FINISHED) {
 241                         spin_unlock(&root->ino_cache_lock);
 242                         up_write(&fs_info->commit_root_sem);
 243                         goto again;
 244                 }
 245                 spin_unlock(&root->ino_cache_lock);
 246
 247                 start_caching(root);
 248
 249                 __btrfs_add_free_space(fs_info, pinned, objectid, 1);
 250
 251                 up_write(&fs_info->commit_root_sem);
 252         }
 253 }
 254
 255 /*
 256  * When a transaction is committed, we'll move those inode numbers which are
 257  * smaller than root->ino_cache_progress from pinned tree to free_ino tree, and
 258  * others will just be dropped, because the commit root we were searching has
 259  * changed.
 260  *
 261  * Must be called with root->fs_info->commit_root_sem held
 262  */
 263 void btrfs_unpin_free_ino(struct btrfs_root *root)
 264 {
 265         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
 266         struct rb_root *rbroot = &root->free_ino_pinned->free_space_offset;
 267         spinlock_t *rbroot_lock = &root->free_ino_pinned->tree_lock;
 268         struct btrfs_free_space *info;
 269         struct rb_node *n;
 270         u64 count;
 271
 272         if (!btrfs_test_opt(root->fs_info, INODE_MAP_CACHE))
 273                 return;
 274
 275         while (1) {
 276                 bool add_to_ctl = true;
 277
 278                 spin_lock(rbroot_lock);
 279                 n = rb_first(rbroot);
 280                 if (!n) {
 281                         spin_unlock(rbroot_lock);
 282                         break;
 283                 }
 284
 285                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 286                 BUG_ON(info->bitmap); /* Logic error */
 287
 288                 if (info->offset > root->ino_cache_progress)
 289                         add_to_ctl = false;
 290                 else if (info->offset + info->bytes > root->ino_cache_progress)
 291                         count = root->ino_cache_progress - info->offset + 1;
 292                 else
 293                         count = info->bytes;
 294
 295                 rb_erase(&info->offset_index, rbroot);
 296                 spin_unlock(rbroot_lock);
 297                 if (add_to_ctl)
 298                         __btrfs_add_free_space(root->fs_info, ctl,
 299                                                info->offset, count);
 300                 kmem_cache_free(btrfs_free_space_cachep, info);
 301         }
 302 }
 303
 304 #define INIT_THRESHOLD  ((SZ_32K / 2) / sizeof(struct btrfs_free_space))
 305 #define INODES_PER_BITMAP (PAGE_SIZE * 8)
 306
 307 /*
 308  * The goal is to keep the memory used by the free_ino tree won't
 309  * exceed the memory if we use bitmaps only.
 310  */
 311 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
 312 {
 313         struct btrfs_free_space *info;
 314         struct rb_node *n;
 315         int max_ino;
 316         int max_bitmaps;
 317
 318         n = rb_last(&ctl->free_space_offset);
 319         if (!n) {
 320                 ctl->extents_thresh = INIT_THRESHOLD;
 321                 return;
 322         }
 323         info = rb_entry(n, struct btrfs_free_space, offset_index);
 324
 325         /*
 326          * Find the maximum inode number in the filesystem. Note we
 327          * ignore the fact that this can be a bitmap, because we are
 328          * not doing precise calculation.
 329          */
 330         max_ino = info->bytes - 1;
 331
 332         max_bitmaps = ALIGN(max_ino, INODES_PER_BITMAP) / INODES_PER_BITMAP;
 333         if (max_bitmaps <= ctl->total_bitmaps) {
 334                 ctl->extents_thresh = 0;
 335                 return;
 336         }
 337
 338         ctl->extents_thresh = (max_bitmaps - ctl->total_bitmaps) *
 339                                 PAGE_SIZE / sizeof(*info);
 340 }
 341
 342 /*
 343  * We don't fall back to bitmap, if we are below the extents threshold
 344  * or this chunk of inode numbers is a big one.
 345  */
 346 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
 347                        struct btrfs_free_space *info)
 348 {
 349         if (ctl->free_extents < ctl->extents_thresh ||
 350             info->bytes > INODES_PER_BITMAP / 10)
 351                 return false;
 352
 353         return true;
 354 }
 355
 356 static const struct btrfs_free_space_op free_ino_op = {
 357         .recalc_thresholds      = recalculate_thresholds,
 358         .use_bitmap             = use_bitmap,
 359 };
 360
 361 static void pinned_recalc_thresholds(struct btrfs_free_space_ctl *ctl)
 362 {
 363 }
 364
 365 static bool pinned_use_bitmap(struct btrfs_free_space_ctl *ctl,
 366                               struct btrfs_free_space *info)
 367 {
 368         /*
 369          * We always use extents for two reasons:
 370          *
 371          * - The pinned tree is only used during the process of caching
 372          *   work.
 373          * - Make code simpler. See btrfs_unpin_free_ino().
 374          */
 375         return false;
 376 }
 377
 378 static const struct btrfs_free_space_op pinned_free_ino_op = {
 379         .recalc_thresholds      = pinned_recalc_thresholds,
 380         .use_bitmap             = pinned_use_bitmap,
 381 };
 382
 383 void btrfs_init_free_ino_ctl(struct btrfs_root *root)
 384 {
 385         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
 386         struct btrfs_free_space_ctl *pinned = root->free_ino_pinned;
 387
 388         spin_lock_init(&ctl->tree_lock);
 389         ctl->unit = 1;
 390         ctl->start = 0;
 391         ctl->private = NULL;
 392         ctl->op = &free_ino_op;
 393         INIT_LIST_HEAD(&ctl->trimming_ranges);
 394         mutex_init(&ctl->cache_writeout_mutex);
 395
 396         /*
 397          * Initially we allow to use 16K of ram to cache chunks of
 398          * inode numbers before we resort to bitmaps. This is somewhat
 399          * arbitrary, but it will be adjusted in runtime.
 400          */
 401         ctl->extents_thresh = INIT_THRESHOLD;
 402
 403         spin_lock_init(&pinned->tree_lock);
 404         pinned->unit = 1;
 405         pinned->start = 0;
 406         pinned->private = NULL;
 407         pinned->extents_thresh = 0;
 408         pinned->op = &pinned_free_ino_op;
 409 }
 410
 411 int btrfs_save_ino_cache(struct btrfs_root *root,
 412                          struct btrfs_trans_handle *trans)
 413 {
 414         struct btrfs_fs_info *fs_info = root->fs_info;
 415         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
 416         struct btrfs_path *path;
 417         struct inode *inode;
 418         struct btrfs_block_rsv *rsv;
 419         struct extent_changeset *data_reserved = NULL;
 420         u64 num_bytes;
 421         u64 alloc_hint = 0;
 422         int ret;
 423         int prealloc;
 424         bool retry = false;
 425
 426         /* only fs tree and subvol/snap needs ino cache */
 427         if (root->root_key.objectid != BTRFS_FS_TREE_OBJECTID &&
 428             (root->root_key.objectid < BTRFS_FIRST_FREE_OBJECTID ||
 429              root->root_key.objectid > BTRFS_LAST_FREE_OBJECTID))
 430                 return 0;
 431
 432         /* Don't save inode cache if we are deleting this root */
 433         if (btrfs_root_refs(&root->root_item) == 0)
 434                 return 0;
 435
 436         if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
 437                 return 0;
 438
 439         path = btrfs_alloc_path();
 440         if (!path)
 441                 return -ENOMEM;
 442
 443         rsv = trans->block_rsv;
 444         trans->block_rsv = &fs_info->trans_block_rsv;
 445
 446         num_bytes = trans->bytes_reserved;
 447         /*
 448          * 1 item for inode item insertion if need
 449          * 4 items for inode item update (in the worst case)
 450          * 1 items for slack space if we need do truncation
 451          * 1 item for free space object
 452          * 3 items for pre-allocation
 453          */
 454         trans->bytes_reserved = btrfs_calc_trans_metadata_size(fs_info, 10);
 455         ret = btrfs_block_rsv_add(root, trans->block_rsv,
 456                                   trans->bytes_reserved,
 457                                   BTRFS_RESERVE_NO_FLUSH);
 458         if (ret)
 459                 goto out;
 460         trace_btrfs_space_reservation(fs_info, "ino_cache", trans->transid,
 461                                       trans->bytes_reserved, 1);
 462 again:
 463         inode = lookup_free_ino_inode(root, path);
 464         if (IS_ERR(inode) && (PTR_ERR(inode) != -ENOENT || retry)) {
 465                 ret = PTR_ERR(inode);
 466                 goto out_release;
 467         }
 468
 469         if (IS_ERR(inode)) {
 470                 BUG_ON(retry); /* Logic error */
 471                 retry = true;
 472
 473                 ret = create_free_ino_inode(root, trans, path);
 474                 if (ret)
 475                         goto out_release;
 476                 goto again;
 477         }
 478
 479         BTRFS_I(inode)->generation = 0;
 480         ret = btrfs_update_inode(trans, root, inode);
 481         if (ret) {
 482                 btrfs_abort_transaction(trans, ret);
 483                 goto out_put;
 484         }
 485
 486         if (i_size_read(inode) > 0) {
 487                 ret = btrfs_truncate_free_space_cache(trans, NULL, inode);
 488                 if (ret) {
 489                         if (ret != -ENOSPC)
 490                                 btrfs_abort_transaction(trans, ret);
 491                         goto out_put;
 492                 }
 493         }
 494
 495         spin_lock(&root->ino_cache_lock);
 496         if (root->ino_cache_state != BTRFS_CACHE_FINISHED) {
 497                 ret = -1;
 498                 spin_unlock(&root->ino_cache_lock);
 499                 goto out_put;
 500         }
 501         spin_unlock(&root->ino_cache_lock);
 502
 503         spin_lock(&ctl->tree_lock);
 504         prealloc = sizeof(struct btrfs_free_space) * ctl->free_extents;
 505         prealloc = ALIGN(prealloc, PAGE_SIZE);
 506         prealloc += ctl->total_bitmaps * PAGE_SIZE;
 507         spin_unlock(&ctl->tree_lock);
 508
 509         /* Just to make sure we have enough space */
 510         prealloc += 8 * PAGE_SIZE;
 511
 512         ret = btrfs_delalloc_reserve_space(inode, &data_reserved, 0, prealloc);
 513         if (ret)
 514                 goto out_put;
 515
 516         ret = btrfs_prealloc_file_range_trans(inode, trans, 0, 0, prealloc,
 517                                               prealloc, prealloc, &alloc_hint);
 518         if (ret) {
 519                 btrfs_delalloc_release_metadata(BTRFS_I(inode), prealloc);
 520                 goto out_put;
 521         }
 522
 523         ret = btrfs_write_out_ino_cache(root, trans, path, inode);
 524 out_put:
 525         iput(inode);
 526 out_release:
 527         trace_btrfs_space_reservation(fs_info, "ino_cache", trans->transid,
 528                                       trans->bytes_reserved, 0);
 529         btrfs_block_rsv_release(fs_info, trans->block_rsv,
 530                                 trans->bytes_reserved);
 531 out:
 532         trans->block_rsv = rsv;
 533         trans->bytes_reserved = num_bytes;
 534
 535         btrfs_free_path(path);
 536         extent_changeset_free(data_reserved);
 537         return ret;
 538 }
 539
 540 int btrfs_find_highest_objectid(struct btrfs_root *root, u64 *objectid)
 541 {
 542         struct btrfs_path *path;
 543         int ret;
 544         struct extent_buffer *l;
 545         struct btrfs_key search_key;
 546         struct btrfs_key found_key;
 547         int slot;
 548
 549         path = btrfs_alloc_path();
 550         if (!path)
 551                 return -ENOMEM;
 552
 553         search_key.objectid = BTRFS_LAST_FREE_OBJECTID;
 554         search_key.type = -1;
 555         search_key.offset = (u64)-1;
 556         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
 557         if (ret < 0)
 558                 goto error;
 559         BUG_ON(ret == 0); /* Corruption */
 560         if (path->slots[0] > 0) {
 561                 slot = path->slots[0] - 1;
 562                 l = path->nodes[0];
 563                 btrfs_item_key_to_cpu(l, &found_key, slot);
 564                 *objectid = max_t(u64, found_key.objectid,
 565                                   BTRFS_FIRST_FREE_OBJECTID - 1);
 566         } else {
 567                 *objectid = BTRFS_FIRST_FREE_OBJECTID - 1;
 568         }
 569         ret = 0;
 570 error:
 571         btrfs_free_path(path);
 572         return ret;
 573 }
 574
 575 int btrfs_find_free_objectid(struct btrfs_root *root, u64 *objectid)
 576 {
 577         int ret;
 578         mutex_lock(&root->objectid_mutex);
 579
 580         if (unlikely(root->highest_objectid >= BTRFS_LAST_FREE_OBJECTID)) {
 581                 btrfs_warn(root->fs_info,
 582                            "the objectid of root %llu reaches its highest value",
 583                            root->root_key.objectid);
 584                 ret = -ENOSPC;
 585                 goto out;
 586         }
 587
 588         *objectid = ++root->highest_objectid;
 589         ret = 0;
 590 out:
 591         mutex_unlock(&root->objectid_mutex);
 592         return ret;
 593 }