fs/btrfs/delayed-inode.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2011 Fujitsu.  All rights reserved.
   4  * Written by Miao Xie <miaox@cn.fujitsu.com>
   5  */
   6
   7 #include <linux/slab.h>
   8 #include <linux/iversion.h>
   9 #include "ctree.h"
  10 #include "fs.h"
  11 #include "messages.h"
  12 #include "misc.h"
  13 #include "delayed-inode.h"
  14 #include "disk-io.h"
  15 #include "transaction.h"
  16 #include "qgroup.h"
  17 #include "locking.h"
  18 #include "inode-item.h"
  19 #include "space-info.h"
  20 #include "accessors.h"
  21 #include "file-item.h"
  22
  23 #define BTRFS_DELAYED_WRITEBACK         512
  24 #define BTRFS_DELAYED_BACKGROUND        128
  25 #define BTRFS_DELAYED_BATCH             16
  26
  27 static struct kmem_cache *delayed_node_cache;
  28
  29 int __init btrfs_delayed_inode_init(void)
  30 {
  31         delayed_node_cache = kmem_cache_create("btrfs_delayed_node",
  32                                         sizeof(struct btrfs_delayed_node),
  33                                         0,
  34                                         SLAB_MEM_SPREAD,
  35                                         NULL);
  36         if (!delayed_node_cache)
  37                 return -ENOMEM;
  38         return 0;
  39 }
  40
  41 void __cold btrfs_delayed_inode_exit(void)
  42 {
  43         kmem_cache_destroy(delayed_node_cache);
  44 }
  45
  46 static inline void btrfs_init_delayed_node(
  47                                 struct btrfs_delayed_node *delayed_node,
  48                                 struct btrfs_root *root, u64 inode_id)
  49 {
  50         delayed_node->root = root;
  51         delayed_node->inode_id = inode_id;
  52         refcount_set(&delayed_node->refs, 0);
  53         delayed_node->ins_root = RB_ROOT_CACHED;
  54         delayed_node->del_root = RB_ROOT_CACHED;
  55         mutex_init(&delayed_node->mutex);
  56         INIT_LIST_HEAD(&delayed_node->n_list);
  57         INIT_LIST_HEAD(&delayed_node->p_list);
  58 }
  59
  60 static struct btrfs_delayed_node *btrfs_get_delayed_node(
  61                 struct btrfs_inode *btrfs_inode)
  62 {
  63         struct btrfs_root *root = btrfs_inode->root;
  64         u64 ino = btrfs_ino(btrfs_inode);
  65         struct btrfs_delayed_node *node;
  66
  67         node = READ_ONCE(btrfs_inode->delayed_node);
  68         if (node) {
  69                 refcount_inc(&node->refs);
  70                 return node;
  71         }
  72
  73         spin_lock(&root->inode_lock);
  74         node = radix_tree_lookup(&root->delayed_nodes_tree, ino);
  75
  76         if (node) {
  77                 if (btrfs_inode->delayed_node) {
  78                         refcount_inc(&node->refs);      /* can be accessed */
  79                         BUG_ON(btrfs_inode->delayed_node != node);
  80                         spin_unlock(&root->inode_lock);
  81                         return node;
  82                 }
  83
  84                 /*
  85                  * It's possible that we're racing into the middle of removing
  86                  * this node from the radix tree.  In this case, the refcount
  87                  * was zero and it should never go back to one.  Just return
  88                  * NULL like it was never in the radix at all; our release
  89                  * function is in the process of removing it.
  90                  *
  91                  * Some implementations of refcount_inc refuse to bump the
  92                  * refcount once it has hit zero.  If we don't do this dance
  93                  * here, refcount_inc() may decide to just WARN_ONCE() instead
  94                  * of actually bumping the refcount.
  95                  *
  96                  * If this node is properly in the radix, we want to bump the
  97                  * refcount twice, once for the inode and once for this get
  98                  * operation.
  99                  */
 100                 if (refcount_inc_not_zero(&node->refs)) {
 101                         refcount_inc(&node->refs);
 102                         btrfs_inode->delayed_node = node;
 103                 } else {
 104                         node = NULL;
 105                 }
 106
 107                 spin_unlock(&root->inode_lock);
 108                 return node;
 109         }
 110         spin_unlock(&root->inode_lock);
 111
 112         return NULL;
 113 }
 114
 115 /* Will return either the node or PTR_ERR(-ENOMEM) */
 116 static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(
 117                 struct btrfs_inode *btrfs_inode)
 118 {
 119         struct btrfs_delayed_node *node;
 120         struct btrfs_root *root = btrfs_inode->root;
 121         u64 ino = btrfs_ino(btrfs_inode);
 122         int ret;
 123
 124 again:
 125         node = btrfs_get_delayed_node(btrfs_inode);
 126         if (node)
 127                 return node;
 128
 129         node = kmem_cache_zalloc(delayed_node_cache, GFP_NOFS);
 130         if (!node)
 131                 return ERR_PTR(-ENOMEM);
 132         btrfs_init_delayed_node(node, root, ino);
 133
 134         /* cached in the btrfs inode and can be accessed */
 135         refcount_set(&node->refs, 2);
 136
 137         ret = radix_tree_preload(GFP_NOFS);
 138         if (ret) {
 139                 kmem_cache_free(delayed_node_cache, node);
 140                 return ERR_PTR(ret);
 141         }
 142
 143         spin_lock(&root->inode_lock);
 144         ret = radix_tree_insert(&root->delayed_nodes_tree, ino, node);
 145         if (ret == -EEXIST) {
 146                 spin_unlock(&root->inode_lock);
 147                 kmem_cache_free(delayed_node_cache, node);
 148                 radix_tree_preload_end();
 149                 goto again;
 150         }
 151         btrfs_inode->delayed_node = node;
 152         spin_unlock(&root->inode_lock);
 153         radix_tree_preload_end();
 154
 155         return node;
 156 }
 157
 158 /*
 159  * Call it when holding delayed_node->mutex
 160  *
 161  * If mod = 1, add this node into the prepared list.
 162  */
 163 static void btrfs_queue_delayed_node(struct btrfs_delayed_root *root,
 164                                      struct btrfs_delayed_node *node,
 165                                      int mod)
 166 {
 167         spin_lock(&root->lock);
 168         if (test_bit(BTRFS_DELAYED_NODE_IN_LIST, &node->flags)) {
 169                 if (!list_empty(&node->p_list))
 170                         list_move_tail(&node->p_list, &root->prepare_list);
 171                 else if (mod)
 172                         list_add_tail(&node->p_list, &root->prepare_list);
 173         } else {
 174                 list_add_tail(&node->n_list, &root->node_list);
 175                 list_add_tail(&node->p_list, &root->prepare_list);
 176                 refcount_inc(&node->refs);      /* inserted into list */
 177                 root->nodes++;
 178                 set_bit(BTRFS_DELAYED_NODE_IN_LIST, &node->flags);
 179         }
 180         spin_unlock(&root->lock);
 181 }
 182
 183 /* Call it when holding delayed_node->mutex */
 184 static void btrfs_dequeue_delayed_node(struct btrfs_delayed_root *root,
 185                                        struct btrfs_delayed_node *node)
 186 {
 187         spin_lock(&root->lock);
 188         if (test_bit(BTRFS_DELAYED_NODE_IN_LIST, &node->flags)) {
 189                 root->nodes--;
 190                 refcount_dec(&node->refs);      /* not in the list */
 191                 list_del_init(&node->n_list);
 192                 if (!list_empty(&node->p_list))
 193                         list_del_init(&node->p_list);
 194                 clear_bit(BTRFS_DELAYED_NODE_IN_LIST, &node->flags);
 195         }
 196         spin_unlock(&root->lock);
 197 }
 198
 199 static struct btrfs_delayed_node *btrfs_first_delayed_node(
 200                         struct btrfs_delayed_root *delayed_root)
 201 {
 202         struct list_head *p;
 203         struct btrfs_delayed_node *node = NULL;
 204
 205         spin_lock(&delayed_root->lock);
 206         if (list_empty(&delayed_root->node_list))
 207                 goto out;
 208
 209         p = delayed_root->node_list.next;
 210         node = list_entry(p, struct btrfs_delayed_node, n_list);
 211         refcount_inc(&node->refs);
 212 out:
 213         spin_unlock(&delayed_root->lock);
 214
 215         return node;
 216 }
 217
 218 static struct btrfs_delayed_node *btrfs_next_delayed_node(
 219                                                 struct btrfs_delayed_node *node)
 220 {
 221         struct btrfs_delayed_root *delayed_root;
 222         struct list_head *p;
 223         struct btrfs_delayed_node *next = NULL;
 224
 225         delayed_root = node->root->fs_info->delayed_root;
 226         spin_lock(&delayed_root->lock);
 227         if (!test_bit(BTRFS_DELAYED_NODE_IN_LIST, &node->flags)) {
 228                 /* not in the list */
 229                 if (list_empty(&delayed_root->node_list))
 230                         goto out;
 231                 p = delayed_root->node_list.next;
 232         } else if (list_is_last(&node->n_list, &delayed_root->node_list))
 233                 goto out;
 234         else
 235                 p = node->n_list.next;
 236
 237         next = list_entry(p, struct btrfs_delayed_node, n_list);
 238         refcount_inc(&next->refs);
 239 out:
 240         spin_unlock(&delayed_root->lock);
 241
 242         return next;
 243 }
 244
 245 static void __btrfs_release_delayed_node(
 246                                 struct btrfs_delayed_node *delayed_node,
 247                                 int mod)
 248 {
 249         struct btrfs_delayed_root *delayed_root;
 250
 251         if (!delayed_node)
 252                 return;
 253
 254         delayed_root = delayed_node->root->fs_info->delayed_root;
 255
 256         mutex_lock(&delayed_node->mutex);
 257         if (delayed_node->count)
 258                 btrfs_queue_delayed_node(delayed_root, delayed_node, mod);
 259         else
 260                 btrfs_dequeue_delayed_node(delayed_root, delayed_node);
 261         mutex_unlock(&delayed_node->mutex);
 262
 263         if (refcount_dec_and_test(&delayed_node->refs)) {
 264                 struct btrfs_root *root = delayed_node->root;
 265
 266                 spin_lock(&root->inode_lock);
 267                 /*
 268                  * Once our refcount goes to zero, nobody is allowed to bump it
 269                  * back up.  We can delete it now.
 270                  */
 271                 ASSERT(refcount_read(&delayed_node->refs) == 0);
 272                 radix_tree_delete(&root->delayed_nodes_tree,
 273                                   delayed_node->inode_id);
 274                 spin_unlock(&root->inode_lock);
 275                 kmem_cache_free(delayed_node_cache, delayed_node);
 276         }
 277 }
 278
 279 static inline void btrfs_release_delayed_node(struct btrfs_delayed_node *node)
 280 {
 281         __btrfs_release_delayed_node(node, 0);
 282 }
 283
 284 static struct btrfs_delayed_node *btrfs_first_prepared_delayed_node(
 285                                         struct btrfs_delayed_root *delayed_root)
 286 {
 287         struct list_head *p;
 288         struct btrfs_delayed_node *node = NULL;
 289
 290         spin_lock(&delayed_root->lock);
 291         if (list_empty(&delayed_root->prepare_list))
 292                 goto out;
 293
 294         p = delayed_root->prepare_list.next;
 295         list_del_init(p);
 296         node = list_entry(p, struct btrfs_delayed_node, p_list);
 297         refcount_inc(&node->refs);
 298 out:
 299         spin_unlock(&delayed_root->lock);
 300
 301         return node;
 302 }
 303
 304 static inline void btrfs_release_prepared_delayed_node(
 305                                         struct btrfs_delayed_node *node)
 306 {
 307         __btrfs_release_delayed_node(node, 1);
 308 }
 309
 310 static struct btrfs_delayed_item *btrfs_alloc_delayed_item(u16 data_len,
 311                                            struct btrfs_delayed_node *node,
 312                                            enum btrfs_delayed_item_type type)
 313 {
 314         struct btrfs_delayed_item *item;
 315
 316         item = kmalloc(struct_size(item, data, data_len), GFP_NOFS);
 317         if (item) {
 318                 item->data_len = data_len;
 319                 item->type = type;
 320                 item->bytes_reserved = 0;
 321                 item->delayed_node = node;
 322                 RB_CLEAR_NODE(&item->rb_node);
 323                 INIT_LIST_HEAD(&item->log_list);
 324                 item->logged = false;
 325                 refcount_set(&item->refs, 1);
 326         }
 327         return item;
 328 }
 329
 330 /*
 331  * Look up the delayed item by key.
 332  *
 333  * @delayed_node: pointer to the delayed node
 334  * @index:        the dir index value to lookup (offset of a dir index key)
 335  *
 336  * Note: if we don't find the right item, we will return the prev item and
 337  * the next item.
 338  */
 339 static struct btrfs_delayed_item *__btrfs_lookup_delayed_item(
 340                                 struct rb_root *root,
 341                                 u64 index)
 342 {
 343         struct rb_node *node = root->rb_node;
 344         struct btrfs_delayed_item *delayed_item = NULL;
 345
 346         while (node) {
 347                 delayed_item = rb_entry(node, struct btrfs_delayed_item,
 348                                         rb_node);
 349                 if (delayed_item->index < index)
 350                         node = node->rb_right;
 351                 else if (delayed_item->index > index)
 352                         node = node->rb_left;
 353                 else
 354                         return delayed_item;
 355         }
 356
 357         return NULL;
 358 }
 359
 360 static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node,
 361                                     struct btrfs_delayed_item *ins)
 362 {
 363         struct rb_node **p, *node;
 364         struct rb_node *parent_node = NULL;
 365         struct rb_root_cached *root;
 366         struct btrfs_delayed_item *item;
 367         bool leftmost = true;
 368
 369         if (ins->type == BTRFS_DELAYED_INSERTION_ITEM)
 370                 root = &delayed_node->ins_root;
 371         else
 372                 root = &delayed_node->del_root;
 373
 374         p = &root->rb_root.rb_node;
 375         node = &ins->rb_node;
 376
 377         while (*p) {
 378                 parent_node = *p;
 379                 item = rb_entry(parent_node, struct btrfs_delayed_item,
 380                                  rb_node);
 381
 382                 if (item->index < ins->index) {
 383                         p = &(*p)->rb_right;
 384                         leftmost = false;
 385                 } else if (item->index > ins->index) {
 386                         p = &(*p)->rb_left;
 387                 } else {
 388                         return -EEXIST;
 389                 }
 390         }
 391
 392         rb_link_node(node, parent_node, p);
 393         rb_insert_color_cached(node, root, leftmost);
 394
 395         if (ins->type == BTRFS_DELAYED_INSERTION_ITEM &&
 396             ins->index >= delayed_node->index_cnt)
 397                 delayed_node->index_cnt = ins->index + 1;
 398
 399         delayed_node->count++;
 400         atomic_inc(&delayed_node->root->fs_info->delayed_root->items);
 401         return 0;
 402 }
 403
 404 static void finish_one_item(struct btrfs_delayed_root *delayed_root)
 405 {
 406         int seq = atomic_inc_return(&delayed_root->items_seq);
 407
 408         /* atomic_dec_return implies a barrier */
 409         if ((atomic_dec_return(&delayed_root->items) <
 410             BTRFS_DELAYED_BACKGROUND || seq % BTRFS_DELAYED_BATCH == 0))
 411                 cond_wake_up_nomb(&delayed_root->wait);
 412 }
 413
 414 static void __btrfs_remove_delayed_item(struct btrfs_delayed_item *delayed_item)
 415 {
 416         struct btrfs_delayed_node *delayed_node = delayed_item->delayed_node;
 417         struct rb_root_cached *root;
 418         struct btrfs_delayed_root *delayed_root;
 419
 420         /* Not inserted, ignore it. */
 421         if (RB_EMPTY_NODE(&delayed_item->rb_node))
 422                 return;
 423
 424         /* If it's in a rbtree, then we need to have delayed node locked. */
 425         lockdep_assert_held(&delayed_node->mutex);
 426
 427         delayed_root = delayed_node->root->fs_info->delayed_root;
 428
 429         BUG_ON(!delayed_root);
 430
 431         if (delayed_item->type == BTRFS_DELAYED_INSERTION_ITEM)
 432                 root = &delayed_node->ins_root;
 433         else
 434                 root = &delayed_node->del_root;
 435
 436         rb_erase_cached(&delayed_item->rb_node, root);
 437         RB_CLEAR_NODE(&delayed_item->rb_node);
 438         delayed_node->count--;
 439
 440         finish_one_item(delayed_root);
 441 }
 442
 443 static void btrfs_release_delayed_item(struct btrfs_delayed_item *item)
 444 {
 445         if (item) {
 446                 __btrfs_remove_delayed_item(item);
 447                 if (refcount_dec_and_test(&item->refs))
 448                         kfree(item);
 449         }
 450 }
 451
 452 static struct btrfs_delayed_item *__btrfs_first_delayed_insertion_item(
 453                                         struct btrfs_delayed_node *delayed_node)
 454 {
 455         struct rb_node *p;
 456         struct btrfs_delayed_item *item = NULL;
 457
 458         p = rb_first_cached(&delayed_node->ins_root);
 459         if (p)
 460                 item = rb_entry(p, struct btrfs_delayed_item, rb_node);
 461
 462         return item;
 463 }
 464
 465 static struct btrfs_delayed_item *__btrfs_first_delayed_deletion_item(
 466                                         struct btrfs_delayed_node *delayed_node)
 467 {
 468         struct rb_node *p;
 469         struct btrfs_delayed_item *item = NULL;
 470
 471         p = rb_first_cached(&delayed_node->del_root);
 472         if (p)
 473                 item = rb_entry(p, struct btrfs_delayed_item, rb_node);
 474
 475         return item;
 476 }
 477
 478 static struct btrfs_delayed_item *__btrfs_next_delayed_item(
 479                                                 struct btrfs_delayed_item *item)
 480 {
 481         struct rb_node *p;
 482         struct btrfs_delayed_item *next = NULL;
 483
 484         p = rb_next(&item->rb_node);
 485         if (p)
 486                 next = rb_entry(p, struct btrfs_delayed_item, rb_node);
 487
 488         return next;
 489 }
 490
 491 static int btrfs_delayed_item_reserve_metadata(struct btrfs_trans_handle *trans,
 492                                                struct btrfs_delayed_item *item)
 493 {
 494         struct btrfs_block_rsv *src_rsv;
 495         struct btrfs_block_rsv *dst_rsv;
 496         struct btrfs_fs_info *fs_info = trans->fs_info;
 497         u64 num_bytes;
 498         int ret;
 499
 500         if (!trans->bytes_reserved)
 501                 return 0;
 502
 503         src_rsv = trans->block_rsv;
 504         dst_rsv = &fs_info->delayed_block_rsv;
 505
 506         num_bytes = btrfs_calc_insert_metadata_size(fs_info, 1);
 507
 508         /*
 509          * Here we migrate space rsv from transaction rsv, since have already
 510          * reserved space when starting a transaction.  So no need to reserve
 511          * qgroup space here.
 512          */
 513         ret = btrfs_block_rsv_migrate(src_rsv, dst_rsv, num_bytes, true);
 514         if (!ret) {
 515                 trace_btrfs_space_reservation(fs_info, "delayed_item",
 516                                               item->delayed_node->inode_id,
 517                                               num_bytes, 1);
 518                 /*
 519                  * For insertions we track reserved metadata space by accounting
 520                  * for the number of leaves that will be used, based on the delayed
 521                  * node's curr_index_batch_size and index_item_leaves fields.
 522                  */
 523                 if (item->type == BTRFS_DELAYED_DELETION_ITEM)
 524                         item->bytes_reserved = num_bytes;
 525         }
 526
 527         return ret;
 528 }
 529
 530 static void btrfs_delayed_item_release_metadata(struct btrfs_root *root,
 531                                                 struct btrfs_delayed_item *item)
 532 {
 533         struct btrfs_block_rsv *rsv;
 534         struct btrfs_fs_info *fs_info = root->fs_info;
 535
 536         if (!item->bytes_reserved)
 537                 return;
 538
 539         rsv = &fs_info->delayed_block_rsv;
 540         /*
 541          * Check btrfs_delayed_item_reserve_metadata() to see why we don't need
 542          * to release/reserve qgroup space.
 543          */
 544         trace_btrfs_space_reservation(fs_info, "delayed_item",
 545                                       item->delayed_node->inode_id,
 546                                       item->bytes_reserved, 0);
 547         btrfs_block_rsv_release(fs_info, rsv, item->bytes_reserved, NULL);
 548 }
 549
 550 static void btrfs_delayed_item_release_leaves(struct btrfs_delayed_node *node,
 551                                               unsigned int num_leaves)
 552 {
 553         struct btrfs_fs_info *fs_info = node->root->fs_info;
 554         const u64 bytes = btrfs_calc_insert_metadata_size(fs_info, num_leaves);
 555
 556         /* There are no space reservations during log replay, bail out. */
 557         if (test_bit(BTRFS_FS_LOG_RECOVERING, &fs_info->flags))
 558                 return;
 559
 560         trace_btrfs_space_reservation(fs_info, "delayed_item", node->inode_id,
 561                                       bytes, 0);
 562         btrfs_block_rsv_release(fs_info, &fs_info->delayed_block_rsv, bytes, NULL);
 563 }
 564
 565 static int btrfs_delayed_inode_reserve_metadata(
 566                                         struct btrfs_trans_handle *trans,
 567                                         struct btrfs_root *root,
 568                                         struct btrfs_delayed_node *node)
 569 {
 570         struct btrfs_fs_info *fs_info = root->fs_info;
 571         struct btrfs_block_rsv *src_rsv;
 572         struct btrfs_block_rsv *dst_rsv;
 573         u64 num_bytes;
 574         int ret;
 575
 576         src_rsv = trans->block_rsv;
 577         dst_rsv = &fs_info->delayed_block_rsv;
 578
 579         num_bytes = btrfs_calc_metadata_size(fs_info, 1);
 580
 581         /*
 582          * btrfs_dirty_inode will update the inode under btrfs_join_transaction
 583          * which doesn't reserve space for speed.  This is a problem since we
 584          * still need to reserve space for this update, so try to reserve the
 585          * space.
 586          *
 587          * Now if src_rsv == delalloc_block_rsv we'll let it just steal since
 588          * we always reserve enough to update the inode item.
 589          */
 590         if (!src_rsv || (!trans->bytes_reserved &&
 591                          src_rsv->type != BTRFS_BLOCK_RSV_DELALLOC)) {
 592                 ret = btrfs_qgroup_reserve_meta(root, num_bytes,
 593                                           BTRFS_QGROUP_RSV_META_PREALLOC, true);
 594                 if (ret < 0)
 595                         return ret;
 596                 ret = btrfs_block_rsv_add(fs_info, dst_rsv, num_bytes,
 597                                           BTRFS_RESERVE_NO_FLUSH);
 598                 /* NO_FLUSH could only fail with -ENOSPC */
 599                 ASSERT(ret == 0 || ret == -ENOSPC);
 600                 if (ret)
 601                         btrfs_qgroup_free_meta_prealloc(root, num_bytes);
 602         } else {
 603                 ret = btrfs_block_rsv_migrate(src_rsv, dst_rsv, num_bytes, true);
 604         }
 605
 606         if (!ret) {
 607                 trace_btrfs_space_reservation(fs_info, "delayed_inode",
 608                                               node->inode_id, num_bytes, 1);
 609                 node->bytes_reserved = num_bytes;
 610         }
 611
 612         return ret;
 613 }
 614
 615 static void btrfs_delayed_inode_release_metadata(struct btrfs_fs_info *fs_info,
 616                                                 struct btrfs_delayed_node *node,
 617                                                 bool qgroup_free)
 618 {
 619         struct btrfs_block_rsv *rsv;
 620
 621         if (!node->bytes_reserved)
 622                 return;
 623
 624         rsv = &fs_info->delayed_block_rsv;
 625         trace_btrfs_space_reservation(fs_info, "delayed_inode",
 626                                       node->inode_id, node->bytes_reserved, 0);
 627         btrfs_block_rsv_release(fs_info, rsv, node->bytes_reserved, NULL);
 628         if (qgroup_free)
 629                 btrfs_qgroup_free_meta_prealloc(node->root,
 630                                 node->bytes_reserved);
 631         else
 632                 btrfs_qgroup_convert_reserved_meta(node->root,
 633                                 node->bytes_reserved);
 634         node->bytes_reserved = 0;
 635 }
 636
 637 /*
 638  * Insert a single delayed item or a batch of delayed items, as many as possible
 639  * that fit in a leaf. The delayed items (dir index keys) are sorted by their key
 640  * in the rbtree, and if there's a gap between two consecutive dir index items,
 641  * then it means at some point we had delayed dir indexes to add but they got
 642  * removed (by btrfs_delete_delayed_dir_index()) before we attempted to flush them
 643  * into the subvolume tree. Dir index keys also have their offsets coming from a
 644  * monotonically increasing counter, so we can't get new keys with an offset that
 645  * fits within a gap between delayed dir index items.
 646  */
 647 static int btrfs_insert_delayed_item(struct btrfs_trans_handle *trans,
 648                                      struct btrfs_root *root,
 649                                      struct btrfs_path *path,
 650                                      struct btrfs_delayed_item *first_item)
 651 {
 652         struct btrfs_fs_info *fs_info = root->fs_info;
 653         struct btrfs_delayed_node *node = first_item->delayed_node;
 654         LIST_HEAD(item_list);
 655         struct btrfs_delayed_item *curr;
 656         struct btrfs_delayed_item *next;
 657         const int max_size = BTRFS_LEAF_DATA_SIZE(fs_info);
 658         struct btrfs_item_batch batch;
 659         struct btrfs_key first_key;
 660         const u32 first_data_size = first_item->data_len;
 661         int total_size;
 662         char *ins_data = NULL;
 663         int ret;
 664         bool continuous_keys_only = false;
 665
 666         lockdep_assert_held(&node->mutex);
 667
 668         /*
 669          * During normal operation the delayed index offset is continuously
 670          * increasing, so we can batch insert all items as there will not be any
 671          * overlapping keys in the tree.
 672          *
 673          * The exception to this is log replay, where we may have interleaved
 674          * offsets in the tree, so our batch needs to be continuous keys only in
 675          * order to ensure we do not end up with out of order items in our leaf.
 676          */
 677         if (test_bit(BTRFS_FS_LOG_RECOVERING, &fs_info->flags))
 678                 continuous_keys_only = true;
 679
 680         /*
 681          * For delayed items to insert, we track reserved metadata bytes based
 682          * on the number of leaves that we will use.
 683          * See btrfs_insert_delayed_dir_index() and
 684          * btrfs_delayed_item_reserve_metadata()).
 685          */
 686         ASSERT(first_item->bytes_reserved == 0);
 687
 688         list_add_tail(&first_item->tree_list, &item_list);
 689         batch.total_data_size = first_data_size;
 690         batch.nr = 1;
 691         total_size = first_data_size + sizeof(struct btrfs_item);
 692         curr = first_item;
 693
 694         while (true) {
 695                 int next_size;
 696
 697                 next = __btrfs_next_delayed_item(curr);
 698                 if (!next)
 699                         break;
 700
 701                 /*
 702                  * We cannot allow gaps in the key space if we're doing log
 703                  * replay.
 704                  */
 705                 if (continuous_keys_only && (next->index != curr->index + 1))
 706                         break;
 707
 708                 ASSERT(next->bytes_reserved == 0);
 709
 710                 next_size = next->data_len + sizeof(struct btrfs_item);
 711                 if (total_size + next_size > max_size)
 712                         break;
 713
 714                 list_add_tail(&next->tree_list, &item_list);
 715                 batch.nr++;
 716                 total_size += next_size;
 717                 batch.total_data_size += next->data_len;
 718                 curr = next;
 719         }
 720
 721         if (batch.nr == 1) {
 722                 first_key.objectid = node->inode_id;
 723                 first_key.type = BTRFS_DIR_INDEX_KEY;
 724                 first_key.offset = first_item->index;
 725                 batch.keys = &first_key;
 726                 batch.data_sizes = &first_data_size;
 727         } else {
 728                 struct btrfs_key *ins_keys;
 729                 u32 *ins_sizes;
 730                 int i = 0;
 731
 732                 ins_data = kmalloc(batch.nr * sizeof(u32) +
 733                                    batch.nr * sizeof(struct btrfs_key), GFP_NOFS);
 734                 if (!ins_data) {
 735                         ret = -ENOMEM;
 736                         goto out;
 737                 }
 738                 ins_sizes = (u32 *)ins_data;
 739                 ins_keys = (struct btrfs_key *)(ins_data + batch.nr * sizeof(u32));
 740                 batch.keys = ins_keys;
 741                 batch.data_sizes = ins_sizes;
 742                 list_for_each_entry(curr, &item_list, tree_list) {
 743                         ins_keys[i].objectid = node->inode_id;
 744                         ins_keys[i].type = BTRFS_DIR_INDEX_KEY;
 745                         ins_keys[i].offset = curr->index;
 746                         ins_sizes[i] = curr->data_len;
 747                         i++;
 748                 }
 749         }
 750
 751         ret = btrfs_insert_empty_items(trans, root, path, &batch);
 752         if (ret)
 753                 goto out;
 754
 755         list_for_each_entry(curr, &item_list, tree_list) {
 756                 char *data_ptr;
 757
 758                 data_ptr = btrfs_item_ptr(path->nodes[0], path->slots[0], char);
 759                 write_extent_buffer(path->nodes[0], &curr->data,
 760                                     (unsigned long)data_ptr, curr->data_len);
 761                 path->slots[0]++;
 762         }
 763
 764         /*
 765          * Now release our path before releasing the delayed items and their
 766          * metadata reservations, so that we don't block other tasks for more
 767          * time than needed.
 768          */
 769         btrfs_release_path(path);
 770
 771         ASSERT(node->index_item_leaves > 0);
 772
 773         /*
 774          * For normal operations we will batch an entire leaf's worth of delayed
 775          * items, so if there are more items to process we can decrement
 776          * index_item_leaves by 1 as we inserted 1 leaf's worth of items.
 777          *
 778          * However for log replay we may not have inserted an entire leaf's
 779          * worth of items, we may have not had continuous items, so decrementing
 780          * here would mess up the index_item_leaves accounting.  For this case
 781          * only clean up the accounting when there are no items left.
 782          */
 783         if (next && !continuous_keys_only) {
 784                 /*
 785                  * We inserted one batch of items into a leaf a there are more
 786                  * items to flush in a future batch, now release one unit of
 787                  * metadata space from the delayed block reserve, corresponding
 788                  * the leaf we just flushed to.
 789                  */
 790                 btrfs_delayed_item_release_leaves(node, 1);
 791                 node->index_item_leaves--;
 792         } else if (!next) {
 793                 /*
 794                  * There are no more items to insert. We can have a number of
 795                  * reserved leaves > 1 here - this happens when many dir index
 796                  * items are added and then removed before they are flushed (file
 797                  * names with a very short life, never span a transaction). So
 798                  * release all remaining leaves.
 799                  */
 800                 btrfs_delayed_item_release_leaves(node, node->index_item_leaves);
 801                 node->index_item_leaves = 0;
 802         }
 803
 804         list_for_each_entry_safe(curr, next, &item_list, tree_list) {
 805                 list_del(&curr->tree_list);
 806                 btrfs_release_delayed_item(curr);
 807         }
 808 out:
 809         kfree(ins_data);
 810         return ret;
 811 }
 812
 813 static int btrfs_insert_delayed_items(struct btrfs_trans_handle *trans,
 814                                       struct btrfs_path *path,
 815                                       struct btrfs_root *root,
 816                                       struct btrfs_delayed_node *node)
 817 {
 818         int ret = 0;
 819
 820         while (ret == 0) {
 821                 struct btrfs_delayed_item *curr;
 822
 823                 mutex_lock(&node->mutex);
 824                 curr = __btrfs_first_delayed_insertion_item(node);
 825                 if (!curr) {
 826                         mutex_unlock(&node->mutex);
 827                         break;
 828                 }
 829                 ret = btrfs_insert_delayed_item(trans, root, path, curr);
 830                 mutex_unlock(&node->mutex);
 831         }
 832
 833         return ret;
 834 }
 835
 836 static int btrfs_batch_delete_items(struct btrfs_trans_handle *trans,
 837                                     struct btrfs_root *root,
 838                                     struct btrfs_path *path,
 839                                     struct btrfs_delayed_item *item)
 840 {
 841         const u64 ino = item->delayed_node->inode_id;
 842         struct btrfs_fs_info *fs_info = root->fs_info;
 843         struct btrfs_delayed_item *curr, *next;
 844         struct extent_buffer *leaf = path->nodes[0];
 845         LIST_HEAD(batch_list);
 846         int nitems, slot, last_slot;
 847         int ret;
 848         u64 total_reserved_size = item->bytes_reserved;
 849
 850         ASSERT(leaf != NULL);
 851
 852         slot = path->slots[0];
 853         last_slot = btrfs_header_nritems(leaf) - 1;
 854         /*
 855          * Our caller always gives us a path pointing to an existing item, so
 856          * this can not happen.
 857          */
 858         ASSERT(slot <= last_slot);
 859         if (WARN_ON(slot > last_slot))
 860                 return -ENOENT;
 861
 862         nitems = 1;
 863         curr = item;
 864         list_add_tail(&curr->tree_list, &batch_list);
 865
 866         /*
 867          * Keep checking if the next delayed item matches the next item in the
 868          * leaf - if so, we can add it to the batch of items to delete from the
 869          * leaf.
 870          */
 871         while (slot < last_slot) {
 872                 struct btrfs_key key;
 873
 874                 next = __btrfs_next_delayed_item(curr);
 875                 if (!next)
 876                         break;
 877
 878                 slot++;
 879                 btrfs_item_key_to_cpu(leaf, &key, slot);
 880                 if (key.objectid != ino ||
 881                     key.type != BTRFS_DIR_INDEX_KEY ||
 882                     key.offset != next->index)
 883                         break;
 884                 nitems++;
 885                 curr = next;
 886                 list_add_tail(&curr->tree_list, &batch_list);
 887                 total_reserved_size += curr->bytes_reserved;
 888         }
 889
 890         ret = btrfs_del_items(trans, root, path, path->slots[0], nitems);
 891         if (ret)
 892                 return ret;
 893
 894         /* In case of BTRFS_FS_LOG_RECOVERING items won't have reserved space */
 895         if (total_reserved_size > 0) {
 896                 /*
 897                  * Check btrfs_delayed_item_reserve_metadata() to see why we
 898                  * don't need to release/reserve qgroup space.
 899                  */
 900                 trace_btrfs_space_reservation(fs_info, "delayed_item", ino,
 901                                               total_reserved_size, 0);
 902                 btrfs_block_rsv_release(fs_info, &fs_info->delayed_block_rsv,
 903                                         total_reserved_size, NULL);
 904         }
 905
 906         list_for_each_entry_safe(curr, next, &batch_list, tree_list) {
 907                 list_del(&curr->tree_list);
 908                 btrfs_release_delayed_item(curr);
 909         }
 910
 911         return 0;
 912 }
 913
 914 static int btrfs_delete_delayed_items(struct btrfs_trans_handle *trans,
 915                                       struct btrfs_path *path,
 916                                       struct btrfs_root *root,
 917                                       struct btrfs_delayed_node *node)
 918 {
 919         struct btrfs_key key;
 920         int ret = 0;
 921
 922         key.objectid = node->inode_id;
 923         key.type = BTRFS_DIR_INDEX_KEY;
 924
 925         while (ret == 0) {
 926                 struct btrfs_delayed_item *item;
 927
 928                 mutex_lock(&node->mutex);
 929                 item = __btrfs_first_delayed_deletion_item(node);
 930                 if (!item) {
 931                         mutex_unlock(&node->mutex);
 932                         break;
 933                 }
 934
 935                 key.offset = item->index;
 936                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 937                 if (ret > 0) {
 938                         /*
 939                          * There's no matching item in the leaf. This means we
 940                          * have already deleted this item in a past run of the
 941                          * delayed items. We ignore errors when running delayed
 942                          * items from an async context, through a work queue job
 943                          * running btrfs_async_run_delayed_root(), and don't
 944                          * release delayed items that failed to complete. This
 945                          * is because we will retry later, and at transaction
 946                          * commit time we always run delayed items and will
 947                          * then deal with errors if they fail to run again.
 948                          *
 949                          * So just release delayed items for which we can't find
 950                          * an item in the tree, and move to the next item.
 951                          */
 952                         btrfs_release_path(path);
 953                         btrfs_release_delayed_item(item);
 954                         ret = 0;
 955                 } else if (ret == 0) {
 956                         ret = btrfs_batch_delete_items(trans, root, path, item);
 957                         btrfs_release_path(path);
 958                 }
 959
 960                 /*
 961                  * We unlock and relock on each iteration, this is to prevent
 962                  * blocking other tasks for too long while we are being run from
 963                  * the async context (work queue job). Those tasks are typically
 964                  * running system calls like creat/mkdir/rename/unlink/etc which
 965                  * need to add delayed items to this delayed node.
 966                  */
 967                 mutex_unlock(&node->mutex);
 968         }
 969
 970         return ret;
 971 }
 972
 973 static void btrfs_release_delayed_inode(struct btrfs_delayed_node *delayed_node)
 974 {
 975         struct btrfs_delayed_root *delayed_root;
 976
 977         if (delayed_node &&
 978             test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags)) {
 979                 BUG_ON(!delayed_node->root);
 980                 clear_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags);
 981                 delayed_node->count--;
 982
 983                 delayed_root = delayed_node->root->fs_info->delayed_root;
 984                 finish_one_item(delayed_root);
 985         }
 986 }
 987
 988 static void btrfs_release_delayed_iref(struct btrfs_delayed_node *delayed_node)
 989 {
 990
 991         if (test_and_clear_bit(BTRFS_DELAYED_NODE_DEL_IREF, &delayed_node->flags)) {
 992                 struct btrfs_delayed_root *delayed_root;
 993
 994                 ASSERT(delayed_node->root);
 995                 delayed_node->count--;
 996
 997                 delayed_root = delayed_node->root->fs_info->delayed_root;
 998                 finish_one_item(delayed_root);
 999         }
1000 }
1001
1002 static int __btrfs_update_delayed_inode(struct btrfs_trans_handle *trans,
1003                                         struct btrfs_root *root,
1004                                         struct btrfs_path *path,
1005                                         struct btrfs_delayed_node *node)
1006 {
1007         struct btrfs_fs_info *fs_info = root->fs_info;
1008         struct btrfs_key key;
1009         struct btrfs_inode_item *inode_item;
1010         struct extent_buffer *leaf;
1011         int mod;
1012         int ret;
1013
1014         key.objectid = node->inode_id;
1015         key.type = BTRFS_INODE_ITEM_KEY;
1016         key.offset = 0;
1017
1018         if (test_bit(BTRFS_DELAYED_NODE_DEL_IREF, &node->flags))
1019                 mod = -1;
1020         else
1021                 mod = 1;
1022
1023         ret = btrfs_lookup_inode(trans, root, path, &key, mod);
1024         if (ret > 0)
1025                 ret = -ENOENT;
1026         if (ret < 0)
1027                 goto out;
1028
1029         leaf = path->nodes[0];
1030         inode_item = btrfs_item_ptr(leaf, path->slots[0],
1031                                     struct btrfs_inode_item);
1032         write_extent_buffer(leaf, &node->inode_item, (unsigned long)inode_item,
1033                             sizeof(struct btrfs_inode_item));
1034         btrfs_mark_buffer_dirty(trans, leaf);
1035
1036         if (!test_bit(BTRFS_DELAYED_NODE_DEL_IREF, &node->flags))
1037                 goto out;
1038
1039         path->slots[0]++;
1040         if (path->slots[0] >= btrfs_header_nritems(leaf))
1041                 goto search;
1042 again:
1043         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1044         if (key.objectid != node->inode_id)
1045                 goto out;
1046
1047         if (key.type != BTRFS_INODE_REF_KEY &&
1048             key.type != BTRFS_INODE_EXTREF_KEY)
1049                 goto out;
1050
1051         /*
1052          * Delayed iref deletion is for the inode who has only one link,
1053          * so there is only one iref. The case that several irefs are
1054          * in the same item doesn't exist.
1055          */
1056         ret = btrfs_del_item(trans, root, path);
1057 out:
1058         btrfs_release_delayed_iref(node);
1059         btrfs_release_path(path);
1060 err_out:
1061         btrfs_delayed_inode_release_metadata(fs_info, node, (ret < 0));
1062         btrfs_release_delayed_inode(node);
1063
1064         /*
1065          * If we fail to update the delayed inode we need to abort the
1066          * transaction, because we could leave the inode with the improper
1067          * counts behind.
1068          */
1069         if (ret && ret != -ENOENT)
1070                 btrfs_abort_transaction(trans, ret);
1071
1072         return ret;
1073
1074 search:
1075         btrfs_release_path(path);
1076
1077         key.type = BTRFS_INODE_EXTREF_KEY;
1078         key.offset = -1;
1079
1080         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1081         if (ret < 0)
1082                 goto err_out;
1083         ASSERT(ret);
1084
1085         ret = 0;
1086         leaf = path->nodes[0];
1087         path->slots[0]--;
1088         goto again;
1089 }
1090
1091 static inline int btrfs_update_delayed_inode(struct btrfs_trans_handle *trans,
1092                                              struct btrfs_root *root,
1093                                              struct btrfs_path *path,
1094                                              struct btrfs_delayed_node *node)
1095 {
1096         int ret;
1097
1098         mutex_lock(&node->mutex);
1099         if (!test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &node->flags)) {
1100                 mutex_unlock(&node->mutex);
1101                 return 0;
1102         }
1103
1104         ret = __btrfs_update_delayed_inode(trans, root, path, node);
1105         mutex_unlock(&node->mutex);
1106         return ret;
1107 }
1108
1109 static inline int
1110 __btrfs_commit_inode_delayed_items(struct btrfs_trans_handle *trans,
1111                                    struct btrfs_path *path,
1112                                    struct btrfs_delayed_node *node)
1113 {
1114         int ret;
1115
1116         ret = btrfs_insert_delayed_items(trans, path, node->root, node);
1117         if (ret)
1118                 return ret;
1119
1120         ret = btrfs_delete_delayed_items(trans, path, node->root, node);
1121         if (ret)
1122                 return ret;
1123
1124         ret = btrfs_update_delayed_inode(trans, node->root, path, node);
1125         return ret;
1126 }
1127
1128 /*
1129  * Called when committing the transaction.
1130  * Returns 0 on success.
1131  * Returns < 0 on error and returns with an aborted transaction with any
1132  * outstanding delayed items cleaned up.
1133  */
1134 static int __btrfs_run_delayed_items(struct btrfs_trans_handle *trans, int nr)
1135 {
1136         struct btrfs_fs_info *fs_info = trans->fs_info;
1137         struct btrfs_delayed_root *delayed_root;
1138         struct btrfs_delayed_node *curr_node, *prev_node;
1139         struct btrfs_path *path;
1140         struct btrfs_block_rsv *block_rsv;
1141         int ret = 0;
1142         bool count = (nr > 0);
1143
1144         if (TRANS_ABORTED(trans))
1145                 return -EIO;
1146
1147         path = btrfs_alloc_path();
1148         if (!path)
1149                 return -ENOMEM;
1150
1151         block_rsv = trans->block_rsv;
1152         trans->block_rsv = &fs_info->delayed_block_rsv;
1153
1154         delayed_root = fs_info->delayed_root;
1155
1156         curr_node = btrfs_first_delayed_node(delayed_root);
1157         while (curr_node && (!count || nr--)) {
1158                 ret = __btrfs_commit_inode_delayed_items(trans, path,
1159                                                          curr_node);
1160                 if (ret) {
1161                         btrfs_abort_transaction(trans, ret);
1162                         break;
1163                 }
1164
1165                 prev_node = curr_node;
1166                 curr_node = btrfs_next_delayed_node(curr_node);
1167                 /*
1168                  * See the comment below about releasing path before releasing
1169                  * node. If the commit of delayed items was successful the path
1170                  * should always be released, but in case of an error, it may
1171                  * point to locked extent buffers (a leaf at the very least).
1172                  */
1173                 ASSERT(path->nodes[0] == NULL);
1174                 btrfs_release_delayed_node(prev_node);
1175         }
1176
1177         /*
1178          * Release the path to avoid a potential deadlock and lockdep splat when
1179          * releasing the delayed node, as that requires taking the delayed node's
1180          * mutex. If another task starts running delayed items before we take
1181          * the mutex, it will first lock the mutex and then it may try to lock
1182          * the same btree path (leaf).
1183          */
1184         btrfs_free_path(path);
1185
1186         if (curr_node)
1187                 btrfs_release_delayed_node(curr_node);
1188         trans->block_rsv = block_rsv;
1189
1190         return ret;
1191 }
1192
1193 int btrfs_run_delayed_items(struct btrfs_trans_handle *trans)
1194 {
1195         return __btrfs_run_delayed_items(trans, -1);
1196 }
1197
1198 int btrfs_run_delayed_items_nr(struct btrfs_trans_handle *trans, int nr)
1199 {
1200         return __btrfs_run_delayed_items(trans, nr);
1201 }
1202
1203 int btrfs_commit_inode_delayed_items(struct btrfs_trans_handle *trans,
1204                                      struct btrfs_inode *inode)
1205 {
1206         struct btrfs_delayed_node *delayed_node = btrfs_get_delayed_node(inode);
1207         struct btrfs_path *path;
1208         struct btrfs_block_rsv *block_rsv;
1209         int ret;
1210
1211         if (!delayed_node)
1212                 return 0;
1213
1214         mutex_lock(&delayed_node->mutex);
1215         if (!delayed_node->count) {
1216                 mutex_unlock(&delayed_node->mutex);
1217                 btrfs_release_delayed_node(delayed_node);
1218                 return 0;
1219         }
1220         mutex_unlock(&delayed_node->mutex);
1221
1222         path = btrfs_alloc_path();
1223         if (!path) {
1224                 btrfs_release_delayed_node(delayed_node);
1225                 return -ENOMEM;
1226         }
1227
1228         block_rsv = trans->block_rsv;
1229         trans->block_rsv = &delayed_node->root->fs_info->delayed_block_rsv;
1230
1231         ret = __btrfs_commit_inode_delayed_items(trans, path, delayed_node);
1232
1233         btrfs_release_delayed_node(delayed_node);
1234         btrfs_free_path(path);
1235         trans->block_rsv = block_rsv;
1236
1237         return ret;
1238 }
1239
1240 int btrfs_commit_inode_delayed_inode(struct btrfs_inode *inode)
1241 {
1242         struct btrfs_fs_info *fs_info = inode->root->fs_info;
1243         struct btrfs_trans_handle *trans;
1244         struct btrfs_delayed_node *delayed_node = btrfs_get_delayed_node(inode);
1245         struct btrfs_path *path;
1246         struct btrfs_block_rsv *block_rsv;
1247         int ret;
1248
1249         if (!delayed_node)
1250                 return 0;
1251
1252         mutex_lock(&delayed_node->mutex);
1253         if (!test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags)) {
1254                 mutex_unlock(&delayed_node->mutex);
1255                 btrfs_release_delayed_node(delayed_node);
1256                 return 0;
1257         }
1258         mutex_unlock(&delayed_node->mutex);
1259
1260         trans = btrfs_join_transaction(delayed_node->root);
1261         if (IS_ERR(trans)) {
1262                 ret = PTR_ERR(trans);
1263                 goto out;
1264         }
1265
1266         path = btrfs_alloc_path();
1267         if (!path) {
1268                 ret = -ENOMEM;
1269                 goto trans_out;
1270         }
1271
1272         block_rsv = trans->block_rsv;
1273         trans->block_rsv = &fs_info->delayed_block_rsv;
1274
1275         mutex_lock(&delayed_node->mutex);
1276         if (test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags))
1277                 ret = __btrfs_update_delayed_inode(trans, delayed_node->root,
1278                                                    path, delayed_node);
1279         else
1280                 ret = 0;
1281         mutex_unlock(&delayed_node->mutex);
1282
1283         btrfs_free_path(path);
1284         trans->block_rsv = block_rsv;
1285 trans_out:
1286         btrfs_end_transaction(trans);
1287         btrfs_btree_balance_dirty(fs_info);
1288 out:
1289         btrfs_release_delayed_node(delayed_node);
1290
1291         return ret;
1292 }
1293
1294 void btrfs_remove_delayed_node(struct btrfs_inode *inode)
1295 {
1296         struct btrfs_delayed_node *delayed_node;
1297
1298         delayed_node = READ_ONCE(inode->delayed_node);
1299         if (!delayed_node)
1300                 return;
1301
1302         inode->delayed_node = NULL;
1303         btrfs_release_delayed_node(delayed_node);
1304 }
1305
1306 struct btrfs_async_delayed_work {
1307         struct btrfs_delayed_root *delayed_root;
1308         int nr;
1309         struct btrfs_work work;
1310 };
1311
1312 static void btrfs_async_run_delayed_root(struct btrfs_work *work)
1313 {
1314         struct btrfs_async_delayed_work *async_work;
1315         struct btrfs_delayed_root *delayed_root;
1316         struct btrfs_trans_handle *trans;
1317         struct btrfs_path *path;
1318         struct btrfs_delayed_node *delayed_node = NULL;
1319         struct btrfs_root *root;
1320         struct btrfs_block_rsv *block_rsv;
1321         int total_done = 0;
1322
1323         async_work = container_of(work, struct btrfs_async_delayed_work, work);
1324         delayed_root = async_work->delayed_root;
1325
1326         path = btrfs_alloc_path();
1327         if (!path)
1328                 goto out;
1329
1330         do {
1331                 if (atomic_read(&delayed_root->items) <
1332                     BTRFS_DELAYED_BACKGROUND / 2)
1333                         break;
1334
1335                 delayed_node = btrfs_first_prepared_delayed_node(delayed_root);
1336                 if (!delayed_node)
1337                         break;
1338
1339                 root = delayed_node->root;
1340
1341                 trans = btrfs_join_transaction(root);
1342                 if (IS_ERR(trans)) {
1343                         btrfs_release_path(path);
1344                         btrfs_release_prepared_delayed_node(delayed_node);
1345                         total_done++;
1346                         continue;
1347                 }
1348
1349                 block_rsv = trans->block_rsv;
1350                 trans->block_rsv = &root->fs_info->delayed_block_rsv;
1351
1352                 __btrfs_commit_inode_delayed_items(trans, path, delayed_node);
1353
1354                 trans->block_rsv = block_rsv;
1355                 btrfs_end_transaction(trans);
1356                 btrfs_btree_balance_dirty_nodelay(root->fs_info);
1357
1358                 btrfs_release_path(path);
1359                 btrfs_release_prepared_delayed_node(delayed_node);
1360                 total_done++;
1361
1362         } while ((async_work->nr == 0 && total_done < BTRFS_DELAYED_WRITEBACK)
1363                  || total_done < async_work->nr);
1364
1365         btrfs_free_path(path);
1366 out:
1367         wake_up(&delayed_root->wait);
1368         kfree(async_work);
1369 }
1370
1371
1372 static int btrfs_wq_run_delayed_node(struct btrfs_delayed_root *delayed_root,
1373                                      struct btrfs_fs_info *fs_info, int nr)
1374 {
1375         struct btrfs_async_delayed_work *async_work;
1376
1377         async_work = kmalloc(sizeof(*async_work), GFP_NOFS);
1378         if (!async_work)
1379                 return -ENOMEM;
1380
1381         async_work->delayed_root = delayed_root;
1382         btrfs_init_work(&async_work->work, btrfs_async_run_delayed_root, NULL);
1383         async_work->nr = nr;
1384
1385         btrfs_queue_work(fs_info->delayed_workers, &async_work->work);
1386         return 0;
1387 }
1388
1389 void btrfs_assert_delayed_root_empty(struct btrfs_fs_info *fs_info)
1390 {
1391         WARN_ON(btrfs_first_delayed_node(fs_info->delayed_root));
1392 }
1393
1394 static int could_end_wait(struct btrfs_delayed_root *delayed_root, int seq)
1395 {
1396         int val = atomic_read(&delayed_root->items_seq);
1397
1398         if (val < seq || val >= seq + BTRFS_DELAYED_BATCH)
1399                 return 1;
1400
1401         if (atomic_read(&delayed_root->items) < BTRFS_DELAYED_BACKGROUND)
1402                 return 1;
1403
1404         return 0;
1405 }
1406
1407 void btrfs_balance_delayed_items(struct btrfs_fs_info *fs_info)
1408 {
1409         struct btrfs_delayed_root *delayed_root = fs_info->delayed_root;
1410
1411         if ((atomic_read(&delayed_root->items) < BTRFS_DELAYED_BACKGROUND) ||
1412                 btrfs_workqueue_normal_congested(fs_info->delayed_workers))
1413                 return;
1414
1415         if (atomic_read(&delayed_root->items) >= BTRFS_DELAYED_WRITEBACK) {
1416                 int seq;
1417                 int ret;
1418
1419                 seq = atomic_read(&delayed_root->items_seq);
1420
1421                 ret = btrfs_wq_run_delayed_node(delayed_root, fs_info, 0);
1422                 if (ret)
1423                         return;
1424
1425                 wait_event_interruptible(delayed_root->wait,
1426                                          could_end_wait(delayed_root, seq));
1427                 return;
1428         }
1429
1430         btrfs_wq_run_delayed_node(delayed_root, fs_info, BTRFS_DELAYED_BATCH);
1431 }
1432
1433 static void btrfs_release_dir_index_item_space(struct btrfs_trans_handle *trans)
1434 {
1435         struct btrfs_fs_info *fs_info = trans->fs_info;
1436         const u64 bytes = btrfs_calc_insert_metadata_size(fs_info, 1);
1437
1438         if (test_bit(BTRFS_FS_LOG_RECOVERING, &fs_info->flags))
1439                 return;
1440
1441         /*
1442          * Adding the new dir index item does not require touching another
1443          * leaf, so we can release 1 unit of metadata that was previously
1444          * reserved when starting the transaction. This applies only to
1445          * the case where we had a transaction start and excludes the
1446          * transaction join case (when replaying log trees).
1447          */
1448         trace_btrfs_space_reservation(fs_info, "transaction",
1449                                       trans->transid, bytes, 0);
1450         btrfs_block_rsv_release(fs_info, trans->block_rsv, bytes, NULL);
1451         ASSERT(trans->bytes_reserved >= bytes);
1452         trans->bytes_reserved -= bytes;
1453 }
1454
1455 /* Will return 0, -ENOMEM or -EEXIST (index number collision, unexpected). */
1456 int btrfs_insert_delayed_dir_index(struct btrfs_trans_handle *trans,
1457                                    const char *name, int name_len,
1458                                    struct btrfs_inode *dir,
1459                                    struct btrfs_disk_key *disk_key, u8 flags,
1460                                    u64 index)
1461 {
1462         struct btrfs_fs_info *fs_info = trans->fs_info;
1463         const unsigned int leaf_data_size = BTRFS_LEAF_DATA_SIZE(fs_info);
1464         struct btrfs_delayed_node *delayed_node;
1465         struct btrfs_delayed_item *delayed_item;
1466         struct btrfs_dir_item *dir_item;
1467         bool reserve_leaf_space;
1468         u32 data_len;
1469         int ret;
1470
1471         delayed_node = btrfs_get_or_create_delayed_node(dir);
1472         if (IS_ERR(delayed_node))
1473                 return PTR_ERR(delayed_node);
1474
1475         delayed_item = btrfs_alloc_delayed_item(sizeof(*dir_item) + name_len,
1476                                                 delayed_node,
1477                                                 BTRFS_DELAYED_INSERTION_ITEM);
1478         if (!delayed_item) {
1479                 ret = -ENOMEM;
1480                 goto release_node;
1481         }
1482
1483         delayed_item->index = index;
1484
1485         dir_item = (struct btrfs_dir_item *)delayed_item->data;
1486         dir_item->location = *disk_key;
1487         btrfs_set_stack_dir_transid(dir_item, trans->transid);
1488         btrfs_set_stack_dir_data_len(dir_item, 0);
1489         btrfs_set_stack_dir_name_len(dir_item, name_len);
1490         btrfs_set_stack_dir_flags(dir_item, flags);
1491         memcpy((char *)(dir_item + 1), name, name_len);
1492
1493         data_len = delayed_item->data_len + sizeof(struct btrfs_item);
1494
1495         mutex_lock(&delayed_node->mutex);
1496
1497         /*
1498          * First attempt to insert the delayed item. This is to make the error
1499          * handling path simpler in case we fail (-EEXIST). There's no risk of
1500          * any other task coming in and running the delayed item before we do
1501          * the metadata space reservation below, because we are holding the
1502          * delayed node's mutex and that mutex must also be locked before the
1503          * node's delayed items can be run.
1504          */
1505         ret = __btrfs_add_delayed_item(delayed_node, delayed_item);
1506         if (unlikely(ret)) {
1507                 btrfs_err(trans->fs_info,
1508 "error adding delayed dir index item, name: %.*s, index: %llu, root: %llu, dir: %llu, dir->index_cnt: %llu, delayed_node->index_cnt: %llu, error: %d",
1509                           name_len, name, index, btrfs_root_id(delayed_node->root),
1510                           delayed_node->inode_id, dir->index_cnt,
1511                           delayed_node->index_cnt, ret);
1512                 btrfs_release_delayed_item(delayed_item);
1513                 btrfs_release_dir_index_item_space(trans);
1514                 mutex_unlock(&delayed_node->mutex);
1515                 goto release_node;
1516         }
1517
1518         if (delayed_node->index_item_leaves == 0 ||
1519             delayed_node->curr_index_batch_size + data_len > leaf_data_size) {
1520                 delayed_node->curr_index_batch_size = data_len;
1521                 reserve_leaf_space = true;
1522         } else {
1523                 delayed_node->curr_index_batch_size += data_len;
1524                 reserve_leaf_space = false;
1525         }
1526
1527         if (reserve_leaf_space) {
1528                 ret = btrfs_delayed_item_reserve_metadata(trans, delayed_item);
1529                 /*
1530                  * Space was reserved for a dir index item insertion when we
1531                  * started the transaction, so getting a failure here should be
1532                  * impossible.
1533                  */
1534                 if (WARN_ON(ret)) {
1535                         btrfs_release_delayed_item(delayed_item);
1536                         mutex_unlock(&delayed_node->mutex);
1537                         goto release_node;
1538                 }
1539
1540                 delayed_node->index_item_leaves++;
1541         } else {
1542                 btrfs_release_dir_index_item_space(trans);
1543         }
1544         mutex_unlock(&delayed_node->mutex);
1545
1546 release_node:
1547         btrfs_release_delayed_node(delayed_node);
1548         return ret;
1549 }
1550
1551 static int btrfs_delete_delayed_insertion_item(struct btrfs_fs_info *fs_info,
1552                                                struct btrfs_delayed_node *node,
1553                                                u64 index)
1554 {
1555         struct btrfs_delayed_item *item;
1556
1557         mutex_lock(&node->mutex);
1558         item = __btrfs_lookup_delayed_item(&node->ins_root.rb_root, index);
1559         if (!item) {
1560                 mutex_unlock(&node->mutex);
1561                 return 1;
1562         }
1563
1564         /*
1565          * For delayed items to insert, we track reserved metadata bytes based
1566          * on the number of leaves that we will use.
1567          * See btrfs_insert_delayed_dir_index() and
1568          * btrfs_delayed_item_reserve_metadata()).
1569          */
1570         ASSERT(item->bytes_reserved == 0);
1571         ASSERT(node->index_item_leaves > 0);
1572
1573         /*
1574          * If there's only one leaf reserved, we can decrement this item from the
1575          * current batch, otherwise we can not because we don't know which leaf
1576          * it belongs to. With the current limit on delayed items, we rarely
1577          * accumulate enough dir index items to fill more than one leaf (even
1578          * when using a leaf size of 4K).
1579          */
1580         if (node->index_item_leaves == 1) {
1581                 const u32 data_len = item->data_len + sizeof(struct btrfs_item);
1582
1583                 ASSERT(node->curr_index_batch_size >= data_len);
1584                 node->curr_index_batch_size -= data_len;
1585         }
1586
1587         btrfs_release_delayed_item(item);
1588
1589         /* If we now have no more dir index items, we can release all leaves. */
1590         if (RB_EMPTY_ROOT(&node->ins_root.rb_root)) {
1591                 btrfs_delayed_item_release_leaves(node, node->index_item_leaves);
1592                 node->index_item_leaves = 0;
1593         }
1594
1595         mutex_unlock(&node->mutex);
1596         return 0;
1597 }
1598
1599 int btrfs_delete_delayed_dir_index(struct btrfs_trans_handle *trans,
1600                                    struct btrfs_inode *dir, u64 index)
1601 {
1602         struct btrfs_delayed_node *node;
1603         struct btrfs_delayed_item *item;
1604         int ret;
1605
1606         node = btrfs_get_or_create_delayed_node(dir);
1607         if (IS_ERR(node))
1608                 return PTR_ERR(node);
1609
1610         ret = btrfs_delete_delayed_insertion_item(trans->fs_info, node, index);
1611         if (!ret)
1612                 goto end;
1613
1614         item = btrfs_alloc_delayed_item(0, node, BTRFS_DELAYED_DELETION_ITEM);
1615         if (!item) {
1616                 ret = -ENOMEM;
1617                 goto end;
1618         }
1619
1620         item->index = index;
1621
1622         ret = btrfs_delayed_item_reserve_metadata(trans, item);
1623         /*
1624          * we have reserved enough space when we start a new transaction,
1625          * so reserving metadata failure is impossible.
1626          */
1627         if (ret < 0) {
1628                 btrfs_err(trans->fs_info,
1629 "metadata reservation failed for delayed dir item deltiona, should have been reserved");
1630                 btrfs_release_delayed_item(item);
1631                 goto end;
1632         }
1633
1634         mutex_lock(&node->mutex);
1635         ret = __btrfs_add_delayed_item(node, item);
1636         if (unlikely(ret)) {
1637                 btrfs_err(trans->fs_info,
1638                           "err add delayed dir index item(index: %llu) into the deletion tree of the delayed node(root id: %llu, inode id: %llu, errno: %d)",
1639                           index, node->root->root_key.objectid,
1640                           node->inode_id, ret);
1641                 btrfs_delayed_item_release_metadata(dir->root, item);
1642                 btrfs_release_delayed_item(item);
1643         }
1644         mutex_unlock(&node->mutex);
1645 end:
1646         btrfs_release_delayed_node(node);
1647         return ret;
1648 }
1649
1650 int btrfs_inode_delayed_dir_index_count(struct btrfs_inode *inode)
1651 {
1652         struct btrfs_delayed_node *delayed_node = btrfs_get_delayed_node(inode);
1653
1654         if (!delayed_node)
1655                 return -ENOENT;
1656
1657         /*
1658          * Since we have held i_mutex of this directory, it is impossible that
1659          * a new directory index is added into the delayed node and index_cnt
1660          * is updated now. So we needn't lock the delayed node.
1661          */
1662         if (!delayed_node->index_cnt) {
1663                 btrfs_release_delayed_node(delayed_node);
1664                 return -EINVAL;
1665         }
1666
1667         inode->index_cnt = delayed_node->index_cnt;
1668         btrfs_release_delayed_node(delayed_node);
1669         return 0;
1670 }
1671
1672 bool btrfs_readdir_get_delayed_items(struct inode *inode,
1673                                      u64 last_index,
1674                                      struct list_head *ins_list,
1675                                      struct list_head *del_list)
1676 {
1677         struct btrfs_delayed_node *delayed_node;
1678         struct btrfs_delayed_item *item;
1679
1680         delayed_node = btrfs_get_delayed_node(BTRFS_I(inode));
1681         if (!delayed_node)
1682                 return false;
1683
1684         /*
1685          * We can only do one readdir with delayed items at a time because of
1686          * item->readdir_list.
1687          */
1688         btrfs_inode_unlock(BTRFS_I(inode), BTRFS_ILOCK_SHARED);
1689         btrfs_inode_lock(BTRFS_I(inode), 0);
1690
1691         mutex_lock(&delayed_node->mutex);
1692         item = __btrfs_first_delayed_insertion_item(delayed_node);
1693         while (item && item->index <= last_index) {
1694                 refcount_inc(&item->refs);
1695                 list_add_tail(&item->readdir_list, ins_list);
1696                 item = __btrfs_next_delayed_item(item);
1697         }
1698
1699         item = __btrfs_first_delayed_deletion_item(delayed_node);
1700         while (item && item->index <= last_index) {
1701                 refcount_inc(&item->refs);
1702                 list_add_tail(&item->readdir_list, del_list);
1703                 item = __btrfs_next_delayed_item(item);
1704         }
1705         mutex_unlock(&delayed_node->mutex);
1706         /*
1707          * This delayed node is still cached in the btrfs inode, so refs
1708          * must be > 1 now, and we needn't check it is going to be freed
1709          * or not.
1710          *
1711          * Besides that, this function is used to read dir, we do not
1712          * insert/delete delayed items in this period. So we also needn't
1713          * requeue or dequeue this delayed node.
1714          */
1715         refcount_dec(&delayed_node->refs);
1716
1717         return true;
1718 }
1719
1720 void btrfs_readdir_put_delayed_items(struct inode *inode,
1721                                      struct list_head *ins_list,
1722                                      struct list_head *del_list)
1723 {
1724         struct btrfs_delayed_item *curr, *next;
1725
1726         list_for_each_entry_safe(curr, next, ins_list, readdir_list) {
1727                 list_del(&curr->readdir_list);
1728                 if (refcount_dec_and_test(&curr->refs))
1729                         kfree(curr);
1730         }
1731
1732         list_for_each_entry_safe(curr, next, del_list, readdir_list) {
1733                 list_del(&curr->readdir_list);
1734                 if (refcount_dec_and_test(&curr->refs))
1735                         kfree(curr);
1736         }
1737
1738         /*
1739          * The VFS is going to do up_read(), so we need to downgrade back to a
1740          * read lock.
1741          */
1742         downgrade_write(&inode->i_rwsem);
1743 }
1744
1745 int btrfs_should_delete_dir_index(struct list_head *del_list,
1746                                   u64 index)
1747 {
1748         struct btrfs_delayed_item *curr;
1749         int ret = 0;
1750
1751         list_for_each_entry(curr, del_list, readdir_list) {
1752                 if (curr->index > index)
1753                         break;
1754                 if (curr->index == index) {
1755                         ret = 1;
1756                         break;
1757                 }
1758         }
1759         return ret;
1760 }
1761
1762 /*
1763  * Read dir info stored in the delayed tree.
1764  */
1765 int btrfs_readdir_delayed_dir_index(struct dir_context *ctx,
1766                                     struct list_head *ins_list)
1767 {
1768         struct btrfs_dir_item *di;
1769         struct btrfs_delayed_item *curr, *next;
1770         struct btrfs_key location;
1771         char *name;
1772         int name_len;
1773         int over = 0;
1774         unsigned char d_type;
1775
1776         /*
1777          * Changing the data of the delayed item is impossible. So
1778          * we needn't lock them. And we have held i_mutex of the
1779          * directory, nobody can delete any directory indexes now.
1780          */
1781         list_for_each_entry_safe(curr, next, ins_list, readdir_list) {
1782                 list_del(&curr->readdir_list);
1783
1784                 if (curr->index < ctx->pos) {
1785                         if (refcount_dec_and_test(&curr->refs))
1786                                 kfree(curr);
1787                         continue;
1788                 }
1789
1790                 ctx->pos = curr->index;
1791
1792                 di = (struct btrfs_dir_item *)curr->data;
1793                 name = (char *)(di + 1);
1794                 name_len = btrfs_stack_dir_name_len(di);
1795
1796                 d_type = fs_ftype_to_dtype(btrfs_dir_flags_to_ftype(di->type));
1797                 btrfs_disk_key_to_cpu(&location, &di->location);
1798
1799                 over = !dir_emit(ctx, name, name_len,
1800                                location.objectid, d_type);
1801
1802                 if (refcount_dec_and_test(&curr->refs))
1803                         kfree(curr);
1804
1805                 if (over)
1806                         return 1;
1807                 ctx->pos++;
1808         }
1809         return 0;
1810 }
1811
1812 static void fill_stack_inode_item(struct btrfs_trans_handle *trans,
1813                                   struct btrfs_inode_item *inode_item,
1814                                   struct inode *inode)
1815 {
1816         u64 flags;
1817
1818         btrfs_set_stack_inode_uid(inode_item, i_uid_read(inode));
1819         btrfs_set_stack_inode_gid(inode_item, i_gid_read(inode));
1820         btrfs_set_stack_inode_size(inode_item, BTRFS_I(inode)->disk_i_size);
1821         btrfs_set_stack_inode_mode(inode_item, inode->i_mode);
1822         btrfs_set_stack_inode_nlink(inode_item, inode->i_nlink);
1823         btrfs_set_stack_inode_nbytes(inode_item, inode_get_bytes(inode));
1824         btrfs_set_stack_inode_generation(inode_item,
1825                                          BTRFS_I(inode)->generation);
1826         btrfs_set_stack_inode_sequence(inode_item,
1827                                        inode_peek_iversion(inode));
1828         btrfs_set_stack_inode_transid(inode_item, trans->transid);
1829         btrfs_set_stack_inode_rdev(inode_item, inode->i_rdev);
1830         flags = btrfs_inode_combine_flags(BTRFS_I(inode)->flags,
1831                                           BTRFS_I(inode)->ro_flags);
1832         btrfs_set_stack_inode_flags(inode_item, flags);
1833         btrfs_set_stack_inode_block_group(inode_item, 0);
1834
1835         btrfs_set_stack_timespec_sec(&inode_item->atime,
1836                                      inode_get_atime_sec(inode));
1837         btrfs_set_stack_timespec_nsec(&inode_item->atime,
1838                                       inode_get_atime_nsec(inode));
1839
1840         btrfs_set_stack_timespec_sec(&inode_item->mtime,
1841                                      inode_get_mtime_sec(inode));
1842         btrfs_set_stack_timespec_nsec(&inode_item->mtime,
1843                                       inode_get_mtime_nsec(inode));
1844
1845         btrfs_set_stack_timespec_sec(&inode_item->ctime,
1846                                      inode_get_ctime_sec(inode));
1847         btrfs_set_stack_timespec_nsec(&inode_item->ctime,
1848                                       inode_get_ctime_nsec(inode));
1849
1850         btrfs_set_stack_timespec_sec(&inode_item->otime, BTRFS_I(inode)->i_otime_sec);
1851         btrfs_set_stack_timespec_nsec(&inode_item->otime, BTRFS_I(inode)->i_otime_nsec);
1852 }
1853
1854 int btrfs_fill_inode(struct inode *inode, u32 *rdev)
1855 {
1856         struct btrfs_fs_info *fs_info = BTRFS_I(inode)->root->fs_info;
1857         struct btrfs_delayed_node *delayed_node;
1858         struct btrfs_inode_item *inode_item;
1859
1860         delayed_node = btrfs_get_delayed_node(BTRFS_I(inode));
1861         if (!delayed_node)
1862                 return -ENOENT;
1863
1864         mutex_lock(&delayed_node->mutex);
1865         if (!test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags)) {
1866                 mutex_unlock(&delayed_node->mutex);
1867                 btrfs_release_delayed_node(delayed_node);
1868                 return -ENOENT;
1869         }
1870
1871         inode_item = &delayed_node->inode_item;
1872
1873         i_uid_write(inode, btrfs_stack_inode_uid(inode_item));
1874         i_gid_write(inode, btrfs_stack_inode_gid(inode_item));
1875         btrfs_i_size_write(BTRFS_I(inode), btrfs_stack_inode_size(inode_item));
1876         btrfs_inode_set_file_extent_range(BTRFS_I(inode), 0,
1877                         round_up(i_size_read(inode), fs_info->sectorsize));
1878         inode->i_mode = btrfs_stack_inode_mode(inode_item);
1879         set_nlink(inode, btrfs_stack_inode_nlink(inode_item));
1880         inode_set_bytes(inode, btrfs_stack_inode_nbytes(inode_item));
1881         BTRFS_I(inode)->generation = btrfs_stack_inode_generation(inode_item);
1882         BTRFS_I(inode)->last_trans = btrfs_stack_inode_transid(inode_item);
1883
1884         inode_set_iversion_queried(inode,
1885                                    btrfs_stack_inode_sequence(inode_item));
1886         inode->i_rdev = 0;
1887         *rdev = btrfs_stack_inode_rdev(inode_item);
1888         btrfs_inode_split_flags(btrfs_stack_inode_flags(inode_item),
1889                                 &BTRFS_I(inode)->flags, &BTRFS_I(inode)->ro_flags);
1890
1891         inode_set_atime(inode, btrfs_stack_timespec_sec(&inode_item->atime),
1892                         btrfs_stack_timespec_nsec(&inode_item->atime));
1893
1894         inode_set_mtime(inode, btrfs_stack_timespec_sec(&inode_item->mtime),
1895                         btrfs_stack_timespec_nsec(&inode_item->mtime));
1896
1897         inode_set_ctime(inode, btrfs_stack_timespec_sec(&inode_item->ctime),
1898                         btrfs_stack_timespec_nsec(&inode_item->ctime));
1899
1900         BTRFS_I(inode)->i_otime_sec = btrfs_stack_timespec_sec(&inode_item->otime);
1901         BTRFS_I(inode)->i_otime_nsec = btrfs_stack_timespec_nsec(&inode_item->otime);
1902
1903         inode->i_generation = BTRFS_I(inode)->generation;
1904         BTRFS_I(inode)->index_cnt = (u64)-1;
1905
1906         mutex_unlock(&delayed_node->mutex);
1907         btrfs_release_delayed_node(delayed_node);
1908         return 0;
1909 }
1910
1911 int btrfs_delayed_update_inode(struct btrfs_trans_handle *trans,
1912                                struct btrfs_inode *inode)
1913 {
1914         struct btrfs_root *root = inode->root;
1915         struct btrfs_delayed_node *delayed_node;
1916         int ret = 0;
1917
1918         delayed_node = btrfs_get_or_create_delayed_node(inode);
1919         if (IS_ERR(delayed_node))
1920                 return PTR_ERR(delayed_node);
1921
1922         mutex_lock(&delayed_node->mutex);
1923         if (test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags)) {
1924                 fill_stack_inode_item(trans, &delayed_node->inode_item,
1925                                       &inode->vfs_inode);
1926                 goto release_node;
1927         }
1928
1929         ret = btrfs_delayed_inode_reserve_metadata(trans, root, delayed_node);
1930         if (ret)
1931                 goto release_node;
1932
1933         fill_stack_inode_item(trans, &delayed_node->inode_item, &inode->vfs_inode);
1934         set_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags);
1935         delayed_node->count++;
1936         atomic_inc(&root->fs_info->delayed_root->items);
1937 release_node:
1938         mutex_unlock(&delayed_node->mutex);
1939         btrfs_release_delayed_node(delayed_node);
1940         return ret;
1941 }
1942
1943 int btrfs_delayed_delete_inode_ref(struct btrfs_inode *inode)
1944 {
1945         struct btrfs_fs_info *fs_info = inode->root->fs_info;
1946         struct btrfs_delayed_node *delayed_node;
1947
1948         /*
1949          * we don't do delayed inode updates during log recovery because it
1950          * leads to enospc problems.  This means we also can't do
1951          * delayed inode refs
1952          */
1953         if (test_bit(BTRFS_FS_LOG_RECOVERING, &fs_info->flags))
1954                 return -EAGAIN;
1955
1956         delayed_node = btrfs_get_or_create_delayed_node(inode);
1957         if (IS_ERR(delayed_node))
1958                 return PTR_ERR(delayed_node);
1959
1960         /*
1961          * We don't reserve space for inode ref deletion is because:
1962          * - We ONLY do async inode ref deletion for the inode who has only
1963          *   one link(i_nlink == 1), it means there is only one inode ref.
1964          *   And in most case, the inode ref and the inode item are in the
1965          *   same leaf, and we will deal with them at the same time.
1966          *   Since we are sure we will reserve the space for the inode item,
1967          *   it is unnecessary to reserve space for inode ref deletion.
1968          * - If the inode ref and the inode item are not in the same leaf,
1969          *   We also needn't worry about enospc problem, because we reserve
1970          *   much more space for the inode update than it needs.
1971          * - At the worst, we can steal some space from the global reservation.
1972          *   It is very rare.
1973          */
1974         mutex_lock(&delayed_node->mutex);
1975         if (test_bit(BTRFS_DELAYED_NODE_DEL_IREF, &delayed_node->flags))
1976                 goto release_node;
1977
1978         set_bit(BTRFS_DELAYED_NODE_DEL_IREF, &delayed_node->flags);
1979         delayed_node->count++;
1980         atomic_inc(&fs_info->delayed_root->items);
1981 release_node:
1982         mutex_unlock(&delayed_node->mutex);
1983         btrfs_release_delayed_node(delayed_node);
1984         return 0;
1985 }
1986
1987 static void __btrfs_kill_delayed_node(struct btrfs_delayed_node *delayed_node)
1988 {
1989         struct btrfs_root *root = delayed_node->root;
1990         struct btrfs_fs_info *fs_info = root->fs_info;
1991         struct btrfs_delayed_item *curr_item, *prev_item;
1992
1993         mutex_lock(&delayed_node->mutex);
1994         curr_item = __btrfs_first_delayed_insertion_item(delayed_node);
1995         while (curr_item) {
1996                 prev_item = curr_item;
1997                 curr_item = __btrfs_next_delayed_item(prev_item);
1998                 btrfs_release_delayed_item(prev_item);
1999         }
2000
2001         if (delayed_node->index_item_leaves > 0) {
2002                 btrfs_delayed_item_release_leaves(delayed_node,
2003                                           delayed_node->index_item_leaves);
2004                 delayed_node->index_item_leaves = 0;
2005         }
2006
2007         curr_item = __btrfs_first_delayed_deletion_item(delayed_node);
2008         while (curr_item) {
2009                 btrfs_delayed_item_release_metadata(root, curr_item);
2010                 prev_item = curr_item;
2011                 curr_item = __btrfs_next_delayed_item(prev_item);
2012                 btrfs_release_delayed_item(prev_item);
2013         }
2014
2015         btrfs_release_delayed_iref(delayed_node);
2016
2017         if (test_bit(BTRFS_DELAYED_NODE_INODE_DIRTY, &delayed_node->flags)) {
2018                 btrfs_delayed_inode_release_metadata(fs_info, delayed_node, false);
2019                 btrfs_release_delayed_inode(delayed_node);
2020         }
2021         mutex_unlock(&delayed_node->mutex);
2022 }
2023
2024 void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode)
2025 {
2026         struct btrfs_delayed_node *delayed_node;
2027
2028         delayed_node = btrfs_get_delayed_node(inode);
2029         if (!delayed_node)
2030                 return;
2031
2032         __btrfs_kill_delayed_node(delayed_node);
2033         btrfs_release_delayed_node(delayed_node);
2034 }
2035
2036 void btrfs_kill_all_delayed_nodes(struct btrfs_root *root)
2037 {
2038         u64 inode_id = 0;
2039         struct btrfs_delayed_node *delayed_nodes[8];
2040         int i, n;
2041
2042         while (1) {
2043                 spin_lock(&root->inode_lock);
2044                 n = radix_tree_gang_lookup(&root->delayed_nodes_tree,
2045                                            (void **)delayed_nodes, inode_id,
2046                                            ARRAY_SIZE(delayed_nodes));
2047                 if (!n) {
2048                         spin_unlock(&root->inode_lock);
2049                         break;
2050                 }
2051
2052                 inode_id = delayed_nodes[n - 1]->inode_id + 1;
2053                 for (i = 0; i < n; i++) {
2054                         /*
2055                          * Don't increase refs in case the node is dead and
2056                          * about to be removed from the tree in the loop below
2057                          */
2058                         if (!refcount_inc_not_zero(&delayed_nodes[i]->refs))
2059                                 delayed_nodes[i] = NULL;
2060                 }
2061                 spin_unlock(&root->inode_lock);
2062
2063                 for (i = 0; i < n; i++) {
2064                         if (!delayed_nodes[i])
2065                                 continue;
2066                         __btrfs_kill_delayed_node(delayed_nodes[i]);
2067                         btrfs_release_delayed_node(delayed_nodes[i]);
2068                 }
2069         }
2070 }
2071
2072 void btrfs_destroy_delayed_inodes(struct btrfs_fs_info *fs_info)
2073 {
2074         struct btrfs_delayed_node *curr_node, *prev_node;
2075
2076         curr_node = btrfs_first_delayed_node(fs_info->delayed_root);
2077         while (curr_node) {
2078                 __btrfs_kill_delayed_node(curr_node);
2079
2080                 prev_node = curr_node;
2081                 curr_node = btrfs_next_delayed_node(curr_node);
2082                 btrfs_release_delayed_node(prev_node);
2083         }
2084 }
2085
2086 void btrfs_log_get_delayed_items(struct btrfs_inode *inode,
2087                                  struct list_head *ins_list,
2088                                  struct list_head *del_list)
2089 {
2090         struct btrfs_delayed_node *node;
2091         struct btrfs_delayed_item *item;
2092
2093         node = btrfs_get_delayed_node(inode);
2094         if (!node)
2095                 return;
2096
2097         mutex_lock(&node->mutex);
2098         item = __btrfs_first_delayed_insertion_item(node);
2099         while (item) {
2100                 /*
2101                  * It's possible that the item is already in a log list. This
2102                  * can happen in case two tasks are trying to log the same
2103                  * directory. For example if we have tasks A and task B:
2104                  *
2105                  * Task A collected the delayed items into a log list while
2106                  * under the inode's log_mutex (at btrfs_log_inode()), but it
2107                  * only releases the items after logging the inodes they point
2108                  * to (if they are new inodes), which happens after unlocking
2109                  * the log mutex;
2110                  *
2111                  * Task B enters btrfs_log_inode() and acquires the log_mutex
2112                  * of the same directory inode, before task B releases the
2113                  * delayed items. This can happen for example when logging some
2114                  * inode we need to trigger logging of its parent directory, so
2115                  * logging two files that have the same parent directory can
2116                  * lead to this.
2117                  *
2118                  * If this happens, just ignore delayed items already in a log
2119                  * list. All the tasks logging the directory are under a log
2120                  * transaction and whichever finishes first can not sync the log
2121                  * before the other completes and leaves the log transaction.
2122                  */
2123                 if (!item->logged && list_empty(&item->log_list)) {
2124                         refcount_inc(&item->refs);
2125                         list_add_tail(&item->log_list, ins_list);
2126                 }
2127                 item = __btrfs_next_delayed_item(item);
2128         }
2129
2130         item = __btrfs_first_delayed_deletion_item(node);
2131         while (item) {
2132                 /* It may be non-empty, for the same reason mentioned above. */
2133                 if (!item->logged && list_empty(&item->log_list)) {
2134                         refcount_inc(&item->refs);
2135                         list_add_tail(&item->log_list, del_list);
2136                 }
2137                 item = __btrfs_next_delayed_item(item);
2138         }
2139         mutex_unlock(&node->mutex);
2140
2141         /*
2142          * We are called during inode logging, which means the inode is in use
2143          * and can not be evicted before we finish logging the inode. So we never
2144          * have the last reference on the delayed inode.
2145          * Also, we don't use btrfs_release_delayed_node() because that would
2146          * requeue the delayed inode (change its order in the list of prepared
2147          * nodes) and we don't want to do such change because we don't create or
2148          * delete delayed items.
2149          */
2150         ASSERT(refcount_read(&node->refs) > 1);
2151         refcount_dec(&node->refs);
2152 }
2153
2154 void btrfs_log_put_delayed_items(struct btrfs_inode *inode,
2155                                  struct list_head *ins_list,
2156                                  struct list_head *del_list)
2157 {
2158         struct btrfs_delayed_node *node;
2159         struct btrfs_delayed_item *item;
2160         struct btrfs_delayed_item *next;
2161
2162         node = btrfs_get_delayed_node(inode);
2163         if (!node)
2164                 return;
2165
2166         mutex_lock(&node->mutex);
2167
2168         list_for_each_entry_safe(item, next, ins_list, log_list) {
2169                 item->logged = true;
2170                 list_del_init(&item->log_list);
2171                 if (refcount_dec_and_test(&item->refs))
2172                         kfree(item);
2173         }
2174
2175         list_for_each_entry_safe(item, next, del_list, log_list) {
2176                 item->logged = true;
2177                 list_del_init(&item->log_list);
2178                 if (refcount_dec_and_test(&item->refs))
2179                         kfree(item);
2180         }
2181
2182         mutex_unlock(&node->mutex);
2183
2184         /*
2185          * We are called during inode logging, which means the inode is in use
2186          * and can not be evicted before we finish logging the inode. So we never
2187          * have the last reference on the delayed inode.
2188          * Also, we don't use btrfs_release_delayed_node() because that would
2189          * requeue the delayed inode (change its order in the list of prepared
2190          * nodes) and we don't want to do such change because we don't create or
2191          * delete delayed items.
2192          */
2193         ASSERT(refcount_read(&node->refs) > 1);
2194         refcount_dec(&node->refs);
2195 }