• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/refcount.h>
10 
11 /* these are the possible values of struct btrfs_delayed_ref_node->action */
12 #define BTRFS_ADD_DELAYED_REF    1 /* add one backref to the tree */
13 #define BTRFS_DROP_DELAYED_REF   2 /* delete one backref from the tree */
14 #define BTRFS_ADD_DELAYED_EXTENT 3 /* record a full extent allocation */
15 #define BTRFS_UPDATE_DELAYED_HEAD 4 /* not changing ref count on head ref */
16 
17 struct btrfs_delayed_ref_node {
18 	struct rb_node ref_node;
19 	/*
20 	 * If action is BTRFS_ADD_DELAYED_REF, also link this node to
21 	 * ref_head->ref_add_list, then we do not need to iterate the
22 	 * whole ref_head->ref_list to find BTRFS_ADD_DELAYED_REF nodes.
23 	 */
24 	struct list_head add_list;
25 
26 	/* the starting bytenr of the extent */
27 	u64 bytenr;
28 
29 	/* the size of the extent */
30 	u64 num_bytes;
31 
32 	/* seq number to keep track of insertion order */
33 	u64 seq;
34 
35 	/* ref count on this data structure */
36 	refcount_t refs;
37 
38 	/*
39 	 * how many refs is this entry adding or deleting.  For
40 	 * head refs, this may be a negative number because it is keeping
41 	 * track of the total mods done to the reference count.
42 	 * For individual refs, this will always be a positive number
43 	 *
44 	 * It may be more than one, since it is possible for a single
45 	 * parent to have more than one ref on an extent
46 	 */
47 	int ref_mod;
48 
49 	unsigned int action:8;
50 	unsigned int type:8;
51 	/* is this node still in the rbtree? */
52 	unsigned int is_head:1;
53 	unsigned int in_tree:1;
54 };
55 
56 struct btrfs_delayed_extent_op {
57 	struct btrfs_disk_key key;
58 	u8 level;
59 	bool update_key;
60 	bool update_flags;
61 	u64 flags_to_set;
62 };
63 
64 /*
65  * the head refs are used to hold a lock on a given extent, which allows us
66  * to make sure that only one process is running the delayed refs
67  * at a time for a single extent.  They also store the sum of all the
68  * reference count modifications we've queued up.
69  */
70 struct btrfs_delayed_ref_head {
71 	u64 bytenr;
72 	u64 num_bytes;
73 	refcount_t refs;
74 	/*
75 	 * the mutex is held while running the refs, and it is also
76 	 * held when checking the sum of reference modifications.
77 	 */
78 	struct mutex mutex;
79 
80 	spinlock_t lock;
81 	struct rb_root_cached ref_tree;
82 	/* accumulate add BTRFS_ADD_DELAYED_REF nodes to this ref_add_list. */
83 	struct list_head ref_add_list;
84 
85 	struct rb_node href_node;
86 
87 	struct btrfs_delayed_extent_op *extent_op;
88 
89 	/*
90 	 * This is used to track the final ref_mod from all the refs associated
91 	 * with this head ref, this is not adjusted as delayed refs are run,
92 	 * this is meant to track if we need to do the csum accounting or not.
93 	 */
94 	int total_ref_mod;
95 
96 	/*
97 	 * This is the current outstanding mod references for this bytenr.  This
98 	 * is used with lookup_extent_info to get an accurate reference count
99 	 * for a bytenr, so it is adjusted as delayed refs are run so that any
100 	 * on disk reference count + ref_mod is accurate.
101 	 */
102 	int ref_mod;
103 
104 	/*
105 	 * when a new extent is allocated, it is just reserved in memory
106 	 * The actual extent isn't inserted into the extent allocation tree
107 	 * until the delayed ref is processed.  must_insert_reserved is
108 	 * used to flag a delayed ref so the accounting can be updated
109 	 * when a full insert is done.
110 	 *
111 	 * It is possible the extent will be freed before it is ever
112 	 * inserted into the extent allocation tree.  In this case
113 	 * we need to update the in ram accounting to properly reflect
114 	 * the free has happened.
115 	 */
116 	unsigned int must_insert_reserved:1;
117 	unsigned int is_data:1;
118 	unsigned int is_system:1;
119 	unsigned int processing:1;
120 };
121 
122 struct btrfs_delayed_tree_ref {
123 	struct btrfs_delayed_ref_node node;
124 	u64 root;
125 	u64 parent;
126 	int level;
127 };
128 
129 struct btrfs_delayed_data_ref {
130 	struct btrfs_delayed_ref_node node;
131 	u64 root;
132 	u64 parent;
133 	u64 objectid;
134 	u64 offset;
135 };
136 
137 enum btrfs_delayed_ref_flags {
138 	/* Indicate that we are flushing delayed refs for the commit */
139 	BTRFS_DELAYED_REFS_FLUSHING,
140 };
141 
142 struct btrfs_delayed_ref_root {
143 	/* head ref rbtree */
144 	struct rb_root_cached href_root;
145 
146 	/* dirty extent records */
147 	struct rb_root dirty_extent_root;
148 
149 	/* this spin lock protects the rbtree and the entries inside */
150 	spinlock_t lock;
151 
152 	/* how many delayed ref updates we've queued, used by the
153 	 * throttling code
154 	 */
155 	atomic_t num_entries;
156 
157 	/* total number of head nodes in tree */
158 	unsigned long num_heads;
159 
160 	/* total number of head nodes ready for processing */
161 	unsigned long num_heads_ready;
162 
163 	u64 pending_csums;
164 
165 	unsigned long flags;
166 
167 	u64 run_delayed_start;
168 
169 	/*
170 	 * To make qgroup to skip given root.
171 	 * This is for snapshot, as btrfs_qgroup_inherit() will manually
172 	 * modify counters for snapshot and its source, so we should skip
173 	 * the snapshot in new_root/old_roots or it will get calculated twice
174 	 */
175 	u64 qgroup_to_skip;
176 };
177 
178 enum btrfs_ref_type {
179 	BTRFS_REF_NOT_SET,
180 	BTRFS_REF_DATA,
181 	BTRFS_REF_METADATA,
182 	BTRFS_REF_LAST,
183 };
184 
185 struct btrfs_data_ref {
186 	/* For EXTENT_DATA_REF */
187 
188 	/* Original root this data extent belongs to */
189 	u64 owning_root;
190 
191 	/* Inode which refers to this data extent */
192 	u64 ino;
193 
194 	/*
195 	 * file_offset - extent_offset
196 	 *
197 	 * file_offset is the key.offset of the EXTENT_DATA key.
198 	 * extent_offset is btrfs_file_extent_offset() of the EXTENT_DATA data.
199 	 */
200 	u64 offset;
201 };
202 
203 struct btrfs_tree_ref {
204 	/*
205 	 * Level of this tree block
206 	 *
207 	 * Shared for skinny (TREE_BLOCK_REF) and normal tree ref.
208 	 */
209 	int level;
210 
211 	/*
212 	 * Root which owns this tree block.
213 	 *
214 	 * For TREE_BLOCK_REF (skinny metadata, either inline or keyed)
215 	 */
216 	u64 owning_root;
217 
218 	/* For non-skinny metadata, no special member needed */
219 };
220 
221 struct btrfs_ref {
222 	enum btrfs_ref_type type;
223 	int action;
224 
225 	/*
226 	 * Whether this extent should go through qgroup record.
227 	 *
228 	 * Normally false, but for certain cases like delayed subtree scan,
229 	 * setting this flag can hugely reduce qgroup overhead.
230 	 */
231 	bool skip_qgroup;
232 
233 #ifdef CONFIG_BTRFS_FS_REF_VERIFY
234 	/* Through which root is this modification. */
235 	u64 real_root;
236 #endif
237 	u64 bytenr;
238 	u64 len;
239 
240 	/* Bytenr of the parent tree block */
241 	u64 parent;
242 	union {
243 		struct btrfs_data_ref data_ref;
244 		struct btrfs_tree_ref tree_ref;
245 	};
246 };
247 
248 extern struct kmem_cache *btrfs_delayed_ref_head_cachep;
249 extern struct kmem_cache *btrfs_delayed_tree_ref_cachep;
250 extern struct kmem_cache *btrfs_delayed_data_ref_cachep;
251 extern struct kmem_cache *btrfs_delayed_extent_op_cachep;
252 
253 int __init btrfs_delayed_ref_init(void);
254 void __cold btrfs_delayed_ref_exit(void);
255 
btrfs_init_generic_ref(struct btrfs_ref * generic_ref,int action,u64 bytenr,u64 len,u64 parent)256 static inline void btrfs_init_generic_ref(struct btrfs_ref *generic_ref,
257 				int action, u64 bytenr, u64 len, u64 parent)
258 {
259 	generic_ref->action = action;
260 	generic_ref->bytenr = bytenr;
261 	generic_ref->len = len;
262 	generic_ref->parent = parent;
263 }
264 
btrfs_init_tree_ref(struct btrfs_ref * generic_ref,int level,u64 root,u64 mod_root,bool skip_qgroup)265 static inline void btrfs_init_tree_ref(struct btrfs_ref *generic_ref,
266 				int level, u64 root, u64 mod_root, bool skip_qgroup)
267 {
268 #ifdef CONFIG_BTRFS_FS_REF_VERIFY
269 	/* If @real_root not set, use @root as fallback */
270 	generic_ref->real_root = mod_root ?: root;
271 #endif
272 	generic_ref->tree_ref.level = level;
273 	generic_ref->tree_ref.owning_root = root;
274 	generic_ref->type = BTRFS_REF_METADATA;
275 	if (skip_qgroup || !(is_fstree(root) &&
276 			     (!mod_root || is_fstree(mod_root))))
277 		generic_ref->skip_qgroup = true;
278 	else
279 		generic_ref->skip_qgroup = false;
280 
281 }
282 
btrfs_init_data_ref(struct btrfs_ref * generic_ref,u64 ref_root,u64 ino,u64 offset,u64 mod_root,bool skip_qgroup)283 static inline void btrfs_init_data_ref(struct btrfs_ref *generic_ref,
284 				u64 ref_root, u64 ino, u64 offset, u64 mod_root,
285 				bool skip_qgroup)
286 {
287 #ifdef CONFIG_BTRFS_FS_REF_VERIFY
288 	/* If @real_root not set, use @root as fallback */
289 	generic_ref->real_root = mod_root ?: ref_root;
290 #endif
291 	generic_ref->data_ref.owning_root = ref_root;
292 	generic_ref->data_ref.ino = ino;
293 	generic_ref->data_ref.offset = offset;
294 	generic_ref->type = BTRFS_REF_DATA;
295 	if (skip_qgroup || !(is_fstree(ref_root) &&
296 			     (!mod_root || is_fstree(mod_root))))
297 		generic_ref->skip_qgroup = true;
298 	else
299 		generic_ref->skip_qgroup = false;
300 }
301 
302 static inline struct btrfs_delayed_extent_op *
btrfs_alloc_delayed_extent_op(void)303 btrfs_alloc_delayed_extent_op(void)
304 {
305 	return kmem_cache_alloc(btrfs_delayed_extent_op_cachep, GFP_NOFS);
306 }
307 
308 static inline void
btrfs_free_delayed_extent_op(struct btrfs_delayed_extent_op * op)309 btrfs_free_delayed_extent_op(struct btrfs_delayed_extent_op *op)
310 {
311 	if (op)
312 		kmem_cache_free(btrfs_delayed_extent_op_cachep, op);
313 }
314 
btrfs_put_delayed_ref(struct btrfs_delayed_ref_node * ref)315 static inline void btrfs_put_delayed_ref(struct btrfs_delayed_ref_node *ref)
316 {
317 	WARN_ON(refcount_read(&ref->refs) == 0);
318 	if (refcount_dec_and_test(&ref->refs)) {
319 		WARN_ON(ref->in_tree);
320 		switch (ref->type) {
321 		case BTRFS_TREE_BLOCK_REF_KEY:
322 		case BTRFS_SHARED_BLOCK_REF_KEY:
323 			kmem_cache_free(btrfs_delayed_tree_ref_cachep, ref);
324 			break;
325 		case BTRFS_EXTENT_DATA_REF_KEY:
326 		case BTRFS_SHARED_DATA_REF_KEY:
327 			kmem_cache_free(btrfs_delayed_data_ref_cachep, ref);
328 			break;
329 		default:
330 			BUG();
331 		}
332 	}
333 }
334 
btrfs_ref_head_to_space_flags(struct btrfs_delayed_ref_head * head_ref)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 
btrfs_put_delayed_ref_head(struct btrfs_delayed_ref_head * head)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_trans_handle *trans,
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);
btrfs_delayed_ref_unlock(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);
382 void btrfs_update_delayed_refs_rsv(struct btrfs_trans_handle *trans);
383 int btrfs_delayed_refs_rsv_refill(struct btrfs_fs_info *fs_info,
384 				  enum btrfs_reserve_flush_enum flush);
385 void btrfs_migrate_to_delayed_refs_rsv(struct btrfs_fs_info *fs_info,
386 				       u64 num_bytes);
387 int btrfs_should_throttle_delayed_refs(struct btrfs_trans_handle *trans);
388 bool btrfs_check_space_for_delayed_refs(struct btrfs_fs_info *fs_info);
389 
390 /*
391  * helper functions to cast a node into its container
392  */
393 static inline struct btrfs_delayed_tree_ref *
btrfs_delayed_node_to_tree_ref(struct btrfs_delayed_ref_node * node)394 btrfs_delayed_node_to_tree_ref(struct btrfs_delayed_ref_node *node)
395 {
396 	return container_of(node, struct btrfs_delayed_tree_ref, node);
397 }
398 
399 static inline struct btrfs_delayed_data_ref *
btrfs_delayed_node_to_data_ref(struct btrfs_delayed_ref_node * node)400 btrfs_delayed_node_to_data_ref(struct btrfs_delayed_ref_node *node)
401 {
402 	return container_of(node, struct btrfs_delayed_data_ref, node);
403 }
404 
405 #endif
406