fs/btrfs/delayed-ref.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /*
   3  * Copyright (C) 2008 Oracle.  All rights reserved.
   4  */
   5
   6 #ifndef BTRFS_DELAYED_REF_H
   7 #define BTRFS_DELAYED_REF_H
   8
   9 #include <linux/types.h>
  10 #include <linux/refcount.h>
  11 #include <linux/list.h>
  12 #include <linux/rbtree.h>
  13 #include <linux/mutex.h>
  14 #include <linux/spinlock.h>
  15 #include <linux/slab.h>
  16 #include <uapi/linux/btrfs_tree.h>
  17
  18 struct btrfs_trans_handle;
  19 struct btrfs_fs_info;
  20
  21 /* these are the possible values of struct btrfs_delayed_ref_node->action */
  22 enum btrfs_delayed_ref_action {
  23         /* Add one backref to the tree */
  24         BTRFS_ADD_DELAYED_REF = 1,
  25         /* Delete one backref from the tree */
  26         BTRFS_DROP_DELAYED_REF,
  27         /* Record a full extent allocation */
  28         BTRFS_ADD_DELAYED_EXTENT,
  29         /* Not changing ref count on head ref */
  30         BTRFS_UPDATE_DELAYED_HEAD,
  31 } __packed;
  32
  33 struct btrfs_data_ref {
  34         /* For EXTENT_DATA_REF */
  35
  36         /* Inode which refers to this data extent */
  37         u64 objectid;
  38
  39         /*
  40          * file_offset - extent_offset
  41          *
  42          * file_offset is the key.offset of the EXTENT_DATA key.
  43          * extent_offset is btrfs_file_extent_offset() of the EXTENT_DATA data.
  44          */
  45         u64 offset;
  46 };
  47
  48 struct btrfs_tree_ref {
  49         /*
  50          * Level of this tree block.
  51          *
  52          * Shared for skinny (TREE_BLOCK_REF) and normal tree ref.
  53          */
  54         int level;
  55
  56         /* For non-skinny metadata, no special member needed */
  57 };
  58
  59 struct btrfs_delayed_ref_node {
  60         struct rb_node ref_node;
  61         /*
  62          * If action is BTRFS_ADD_DELAYED_REF, also link this node to
  63          * ref_head->ref_add_list, then we do not need to iterate the
  64          * whole ref_head->ref_list to find BTRFS_ADD_DELAYED_REF nodes.
  65          */
  66         struct list_head add_list;
  67
  68         /* the starting bytenr of the extent */
  69         u64 bytenr;
  70
  71         /* the size of the extent */
  72         u64 num_bytes;
  73
  74         /* seq number to keep track of insertion order */
  75         u64 seq;
  76
  77         /* The ref_root for this ref */
  78         u64 ref_root;
  79
  80         /*
  81          * The parent for this ref, if this isn't set the ref_root is the
  82          * reference owner.
  83          */
  84         u64 parent;
  85
  86         /* ref count on this data structure */
  87         refcount_t refs;
  88
  89         /*
  90          * how many refs is this entry adding or deleting.  For
  91          * head refs, this may be a negative number because it is keeping
  92          * track of the total mods done to the reference count.
  93          * For individual refs, this will always be a positive number
  94          *
  95          * It may be more than one, since it is possible for a single
  96          * parent to have more than one ref on an extent
  97          */
  98         int ref_mod;
  99
 100         unsigned int action:8;
 101         unsigned int type:8;
 102
 103         union {
 104                 struct btrfs_tree_ref tree_ref;
 105                 struct btrfs_data_ref data_ref;
 106         };
 107 };
 108
 109 struct btrfs_delayed_extent_op {
 110         struct btrfs_disk_key key;
 111         u8 level;
 112         bool update_key;
 113         bool update_flags;
 114         u64 flags_to_set;
 115 };
 116
 117 /*
 118  * the head refs are used to hold a lock on a given extent, which allows us
 119  * to make sure that only one process is running the delayed refs
 120  * at a time for a single extent.  They also store the sum of all the
 121  * reference count modifications we've queued up.
 122  */
 123 struct btrfs_delayed_ref_head {
 124         u64 bytenr;
 125         u64 num_bytes;
 126         /*
 127          * For insertion into struct btrfs_delayed_ref_root::href_root.
 128          * Keep it in the same cache line as 'bytenr' for more efficient
 129          * searches in the rbtree.
 130          */
 131         struct rb_node href_node;
 132         /*
 133          * the mutex is held while running the refs, and it is also
 134          * held when checking the sum of reference modifications.
 135          */
 136         struct mutex mutex;
 137
 138         refcount_t refs;
 139
 140         /* Protects 'ref_tree' and 'ref_add_list'. */
 141         spinlock_t lock;
 142         struct rb_root_cached ref_tree;
 143         /* accumulate add BTRFS_ADD_DELAYED_REF nodes to this ref_add_list. */
 144         struct list_head ref_add_list;
 145
 146         struct btrfs_delayed_extent_op *extent_op;
 147
 148         /*
 149          * This is used to track the final ref_mod from all the refs associated
 150          * with this head ref, this is not adjusted as delayed refs are run,
 151          * this is meant to track if we need to do the csum accounting or not.
 152          */
 153         int total_ref_mod;
 154
 155         /*
 156          * This is the current outstanding mod references for this bytenr.  This
 157          * is used with lookup_extent_info to get an accurate reference count
 158          * for a bytenr, so it is adjusted as delayed refs are run so that any
 159          * on disk reference count + ref_mod is accurate.
 160          */
 161         int ref_mod;
 162
 163         /*
 164          * The root that triggered the allocation when must_insert_reserved is
 165          * set to true.
 166          */
 167         u64 owning_root;
 168
 169         /*
 170          * Track reserved bytes when setting must_insert_reserved.  On success
 171          * or cleanup, we will need to free the reservation.
 172          */
 173         u64 reserved_bytes;
 174
 175         /*
 176          * when a new extent is allocated, it is just reserved in memory
 177          * The actual extent isn't inserted into the extent allocation tree
 178          * until the delayed ref is processed.  must_insert_reserved is
 179          * used to flag a delayed ref so the accounting can be updated
 180          * when a full insert is done.
 181          *
 182          * It is possible the extent will be freed before it is ever
 183          * inserted into the extent allocation tree.  In this case
 184          * we need to update the in ram accounting to properly reflect
 185          * the free has happened.
 186          */
 187         bool must_insert_reserved;
 188
 189         bool is_data;
 190         bool is_system;
 191         bool processing;
 192 };
 193
 194 enum btrfs_delayed_ref_flags {
 195         /* Indicate that we are flushing delayed refs for the commit */
 196         BTRFS_DELAYED_REFS_FLUSHING,
 197 };
 198
 199 struct btrfs_delayed_ref_root {
 200         /* head ref rbtree */
 201         struct rb_root_cached href_root;
 202
 203         /* dirty extent records */
 204         struct rb_root dirty_extent_root;
 205
 206         /* this spin lock protects the rbtree and the entries inside */
 207         spinlock_t lock;
 208
 209         /* how many delayed ref updates we've queued, used by the
 210          * throttling code
 211          */
 212         atomic_t num_entries;
 213
 214         /* total number of head nodes in tree */
 215         unsigned long num_heads;
 216
 217         /* total number of head nodes ready for processing */
 218         unsigned long num_heads_ready;
 219
 220         u64 pending_csums;
 221
 222         unsigned long flags;
 223
 224         u64 run_delayed_start;
 225
 226         /*
 227          * To make qgroup to skip given root.
 228          * This is for snapshot, as btrfs_qgroup_inherit() will manually
 229          * modify counters for snapshot and its source, so we should skip
 230          * the snapshot in new_root/old_roots or it will get calculated twice
 231          */
 232         u64 qgroup_to_skip;
 233 };
 234
 235 enum btrfs_ref_type {
 236         BTRFS_REF_NOT_SET,
 237         BTRFS_REF_DATA,
 238         BTRFS_REF_METADATA,
 239         BTRFS_REF_LAST,
 240 } __packed;
 241
 242 struct btrfs_ref {
 243         enum btrfs_ref_type type;
 244         enum btrfs_delayed_ref_action action;
 245
 246         /*
 247          * Whether this extent should go through qgroup record.
 248          *
 249          * Normally false, but for certain cases like delayed subtree scan,
 250          * setting this flag can hugely reduce qgroup overhead.
 251          */
 252         bool skip_qgroup;
 253
 254 #ifdef CONFIG_BTRFS_FS_REF_VERIFY
 255         /* Through which root is this modification. */
 256         u64 real_root;
 257 #endif
 258         u64 bytenr;
 259         u64 num_bytes;
 260         u64 owning_root;
 261
 262         /*
 263          * The root that owns the reference for this reference, this will be set
 264          * or ->parent will be set, depending on what type of reference this is.
 265          */
 266         u64 ref_root;
 267
 268         /* Bytenr of the parent tree block */
 269         u64 parent;
 270         union {
 271                 struct btrfs_data_ref data_ref;
 272                 struct btrfs_tree_ref tree_ref;
 273         };
 274 };
 275
 276 extern struct kmem_cache *btrfs_delayed_ref_head_cachep;
 277 extern struct kmem_cache *btrfs_delayed_ref_node_cachep;
 278 extern struct kmem_cache *btrfs_delayed_extent_op_cachep;
 279
 280 int __init btrfs_delayed_ref_init(void);
 281 void __cold btrfs_delayed_ref_exit(void);
 282
 283 static inline u64 btrfs_calc_delayed_ref_bytes(const struct btrfs_fs_info *fs_info,
 284                                                int num_delayed_refs)
 285 {
 286         u64 num_bytes;
 287
 288         num_bytes = btrfs_calc_insert_metadata_size(fs_info, num_delayed_refs);
 289
 290         /*
 291          * We have to check the mount option here because we could be enabling
 292          * the free space tree for the first time and don't have the compat_ro
 293          * option set yet.
 294          *
 295          * We need extra reservations if we have the free space tree because
 296          * we'll have to modify that tree as well.
 297          */
 298         if (btrfs_test_opt(fs_info, FREE_SPACE_TREE))
 299                 num_bytes *= 2;
 300
 301         return num_bytes;
 302 }
 303
 304 static inline u64 btrfs_calc_delayed_ref_csum_bytes(const struct btrfs_fs_info *fs_info,
 305                                                     int num_csum_items)
 306 {
 307         /*
 308          * Deleting csum items does not result in new nodes/leaves and does not
 309          * require changing the free space tree, only the csum tree, so this is
 310          * all we need.
 311          */
 312         return btrfs_calc_metadata_size(fs_info, num_csum_items);
 313 }
 314
 315 void btrfs_init_tree_ref(struct btrfs_ref *generic_ref, int level, u64 mod_root,
 316                          bool skip_qgroup);
 317 void btrfs_init_data_ref(struct btrfs_ref *generic_ref, u64 ino, u64 offset,
 318                          u64 mod_root, bool skip_qgroup);
 319
 320 static inline struct btrfs_delayed_extent_op *
 321 btrfs_alloc_delayed_extent_op(void)
 322 {
 323         return kmem_cache_alloc(btrfs_delayed_extent_op_cachep, GFP_NOFS);
 324 }
 325
 326 static inline void
 327 btrfs_free_delayed_extent_op(struct btrfs_delayed_extent_op *op)
 328 {
 329         if (op)
 330                 kmem_cache_free(btrfs_delayed_extent_op_cachep, op);
 331 }
 332
 333 void btrfs_put_delayed_ref(struct btrfs_delayed_ref_node *ref);
 334
 335 static inline u64 btrfs_ref_head_to_space_flags(
 336                                 struct btrfs_delayed_ref_head *head_ref)
 337 {
 338         if (head_ref->is_data)
 339                 return BTRFS_BLOCK_GROUP_DATA;
 340         else if (head_ref->is_system)
 341                 return BTRFS_BLOCK_GROUP_SYSTEM;
 342         return BTRFS_BLOCK_GROUP_METADATA;
 343 }
 344
 345 static inline void btrfs_put_delayed_ref_head(struct btrfs_delayed_ref_head *head)
 346 {
 347         if (refcount_dec_and_test(&head->refs))
 348                 kmem_cache_free(btrfs_delayed_ref_head_cachep, head);
 349 }
 350
 351 int btrfs_add_delayed_tree_ref(struct btrfs_trans_handle *trans,
 352                                struct btrfs_ref *generic_ref,
 353                                struct btrfs_delayed_extent_op *extent_op);
 354 int btrfs_add_delayed_data_ref(struct btrfs_trans_handle *trans,
 355                                struct btrfs_ref *generic_ref,
 356                                u64 reserved);
 357 int btrfs_add_delayed_extent_op(struct btrfs_trans_handle *trans,
 358                                 u64 bytenr, u64 num_bytes,
 359                                 struct btrfs_delayed_extent_op *extent_op);
 360 void btrfs_merge_delayed_refs(struct btrfs_fs_info *fs_info,
 361                               struct btrfs_delayed_ref_root *delayed_refs,
 362                               struct btrfs_delayed_ref_head *head);
 363
 364 struct btrfs_delayed_ref_head *
 365 btrfs_find_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 366                             u64 bytenr);
 367 int btrfs_delayed_ref_lock(struct btrfs_delayed_ref_root *delayed_refs,
 368                            struct btrfs_delayed_ref_head *head);
 369 static inline void btrfs_delayed_ref_unlock(struct btrfs_delayed_ref_head *head)
 370 {
 371         mutex_unlock(&head->mutex);
 372 }
 373 void btrfs_delete_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 374                            struct btrfs_delayed_ref_head *head);
 375
 376 struct btrfs_delayed_ref_head *btrfs_select_ref_head(
 377                 struct btrfs_delayed_ref_root *delayed_refs);
 378
 379 int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info, u64 seq);
 380
 381 void btrfs_delayed_refs_rsv_release(struct btrfs_fs_info *fs_info, int nr_refs, int nr_csums);
 382 void btrfs_update_delayed_refs_rsv(struct btrfs_trans_handle *trans);
 383 void btrfs_inc_delayed_refs_rsv_bg_inserts(struct btrfs_fs_info *fs_info);
 384 void btrfs_dec_delayed_refs_rsv_bg_inserts(struct btrfs_fs_info *fs_info);
 385 void btrfs_inc_delayed_refs_rsv_bg_updates(struct btrfs_fs_info *fs_info);
 386 void btrfs_dec_delayed_refs_rsv_bg_updates(struct btrfs_fs_info *fs_info);
 387 int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,
 388                                   enum btrfs_reserve_flush_enum flush);
 389 void btrfs_migrate_to_delayed_refs_rsv(struct btrfs_fs_info *fs_info,
 390                                        u64 num_bytes);
 391 bool btrfs_check_space_for_delayed_refs(struct btrfs_fs_info *fs_info);
 392
 393 static inline u64 btrfs_delayed_ref_owner(struct btrfs_delayed_ref_node *node)
 394 {
 395         if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
 396             node->type == BTRFS_SHARED_DATA_REF_KEY)
 397                 return node->data_ref.objectid;
 398         return node->tree_ref.level;
 399 }
 400
 401 static inline u64 btrfs_delayed_ref_offset(struct btrfs_delayed_ref_node *node)
 402 {
 403         if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
 404             node->type == BTRFS_SHARED_DATA_REF_KEY)
 405                 return node->data_ref.offset;
 406         return 0;
 407 }
 408
 409 static inline u8 btrfs_ref_type(struct btrfs_ref *ref)
 410 {
 411         ASSERT(ref->type == BTRFS_REF_DATA || ref->type == BTRFS_REF_METADATA);
 412
 413         if (ref->type == BTRFS_REF_DATA) {
 414                 if (ref->parent)
 415                         return BTRFS_SHARED_DATA_REF_KEY;
 416                 else
 417                         return BTRFS_EXTENT_DATA_REF_KEY;
 418         } else {
 419                 if (ref->parent)
 420                         return BTRFS_SHARED_BLOCK_REF_KEY;
 421                 else
 422                         return BTRFS_TREE_BLOCK_REF_KEY;
 423         }
 424
 425         return 0;
 426 }
 427
 428 #endif