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