Linux Audio

Check our new training course

Loading...
v6.8
  1/* SPDX-License-Identifier: GPL-2.0 */
  2/*
  3 * Copyright (C) 2007 Oracle.  All rights reserved.
  4 */
  5
  6#ifndef BTRFS_CTREE_H
  7#define BTRFS_CTREE_H
  8
  9#include <linux/pagemap.h>
 
 
 
 
 
 
 
 
 
 10#include "locking.h"
 11#include "fs.h"
 12#include "accessors.h"
 
 13
 
 
 14struct btrfs_trans_handle;
 15struct btrfs_transaction;
 16struct btrfs_pending_snapshot;
 17struct btrfs_delayed_ref_root;
 18struct btrfs_space_info;
 19struct btrfs_block_group;
 20struct btrfs_ordered_sum;
 21struct btrfs_ref;
 22struct btrfs_bio;
 23struct btrfs_ioctl_encoded_io_args;
 24struct btrfs_device;
 25struct btrfs_fs_devices;
 26struct btrfs_balance_control;
 27struct btrfs_delayed_root;
 28struct reloc_control;
 29
 30/* Read ahead values for struct btrfs_path.reada */
 31enum {
 32	READA_NONE,
 33	READA_BACK,
 34	READA_FORWARD,
 35	/*
 36	 * Similar to READA_FORWARD but unlike it:
 37	 *
 38	 * 1) It will trigger readahead even for leaves that are not close to
 39	 *    each other on disk;
 40	 * 2) It also triggers readahead for nodes;
 41	 * 3) During a search, even when a node or leaf is already in memory, it
 42	 *    will still trigger readahead for other nodes and leaves that follow
 43	 *    it.
 44	 *
 45	 * This is meant to be used only when we know we are iterating over the
 46	 * entire tree or a very large part of it.
 47	 */
 48	READA_FORWARD_ALWAYS,
 49};
 50
 51/*
 52 * btrfs_paths remember the path taken from the root down to the leaf.
 53 * level 0 is always the leaf, and nodes[1...BTRFS_MAX_LEVEL] will point
 54 * to any other levels that are present.
 55 *
 56 * The slots array records the index of the item or block pointer
 57 * used while walking the tree.
 58 */
 59struct btrfs_path {
 60	struct extent_buffer *nodes[BTRFS_MAX_LEVEL];
 61	int slots[BTRFS_MAX_LEVEL];
 62	/* if there is real range locking, this locks field will change */
 63	u8 locks[BTRFS_MAX_LEVEL];
 64	u8 reada;
 65	/* keep some upper locks as we walk down */
 66	u8 lowest_level;
 67
 68	/*
 69	 * set by btrfs_split_item, tells search_slot to keep all locks
 70	 * and to force calls to keep space in the nodes
 71	 */
 72	unsigned int search_for_split:1;
 73	unsigned int keep_locks:1;
 74	unsigned int skip_locking:1;
 75	unsigned int search_commit_root:1;
 76	unsigned int need_commit_sem:1;
 77	unsigned int skip_release_on_error:1;
 78	/*
 79	 * Indicate that new item (btrfs_search_slot) is extending already
 80	 * existing item and ins_len contains only the data size and not item
 81	 * header (ie. sizeof(struct btrfs_item) is not included).
 82	 */
 83	unsigned int search_for_extension:1;
 84	/* Stop search if any locks need to be taken (for read) */
 85	unsigned int nowait:1;
 86};
 87
 88/*
 89 * The state of btrfs root
 90 */
 91enum {
 92	/*
 93	 * btrfs_record_root_in_trans is a multi-step process, and it can race
 94	 * with the balancing code.   But the race is very small, and only the
 95	 * first time the root is added to each transaction.  So IN_TRANS_SETUP
 96	 * is used to tell us when more checks are required
 97	 */
 98	BTRFS_ROOT_IN_TRANS_SETUP,
 99
100	/*
101	 * Set if tree blocks of this root can be shared by other roots.
102	 * Only subvolume trees and their reloc trees have this bit set.
103	 * Conflicts with TRACK_DIRTY bit.
104	 *
105	 * This affects two things:
106	 *
107	 * - How balance works
108	 *   For shareable roots, we need to use reloc tree and do path
109	 *   replacement for balance, and need various pre/post hooks for
110	 *   snapshot creation to handle them.
111	 *
112	 *   While for non-shareable trees, we just simply do a tree search
113	 *   with COW.
114	 *
115	 * - How dirty roots are tracked
116	 *   For shareable roots, btrfs_record_root_in_trans() is needed to
117	 *   track them, while non-subvolume roots have TRACK_DIRTY bit, they
118	 *   don't need to set this manually.
119	 */
120	BTRFS_ROOT_SHAREABLE,
121	BTRFS_ROOT_TRACK_DIRTY,
122	BTRFS_ROOT_IN_RADIX,
123	BTRFS_ROOT_ORPHAN_ITEM_INSERTED,
124	BTRFS_ROOT_DEFRAG_RUNNING,
125	BTRFS_ROOT_FORCE_COW,
126	BTRFS_ROOT_MULTI_LOG_TASKS,
127	BTRFS_ROOT_DIRTY,
128	BTRFS_ROOT_DELETING,
129
130	/*
131	 * Reloc tree is orphan, only kept here for qgroup delayed subtree scan
132	 *
133	 * Set for the subvolume tree owning the reloc tree.
134	 */
135	BTRFS_ROOT_DEAD_RELOC_TREE,
136	/* Mark dead root stored on device whose cleanup needs to be resumed */
137	BTRFS_ROOT_DEAD_TREE,
138	/* The root has a log tree. Used for subvolume roots and the tree root. */
139	BTRFS_ROOT_HAS_LOG_TREE,
140	/* Qgroup flushing is in progress */
141	BTRFS_ROOT_QGROUP_FLUSHING,
142	/* We started the orphan cleanup for this root. */
143	BTRFS_ROOT_ORPHAN_CLEANUP,
144	/* This root has a drop operation that was started previously. */
145	BTRFS_ROOT_UNFINISHED_DROP,
146	/* This reloc root needs to have its buffers lockdep class reset. */
147	BTRFS_ROOT_RESET_LOCKDEP_CLASS,
148};
149
150/*
151 * Record swapped tree blocks of a subvolume tree for delayed subtree trace
152 * code. For detail check comment in fs/btrfs/qgroup.c.
153 */
154struct btrfs_qgroup_swapped_blocks {
155	spinlock_t lock;
156	/* RM_EMPTY_ROOT() of above blocks[] */
157	bool swapped;
158	struct rb_root blocks[BTRFS_MAX_LEVEL];
159};
160
161/*
162 * in ram representation of the tree.  extent_root is used for all allocations
163 * and for the extent tree extent_root root.
164 */
165struct btrfs_root {
166	struct rb_node rb_node;
167
168	struct extent_buffer *node;
169
170	struct extent_buffer *commit_root;
171	struct btrfs_root *log_root;
172	struct btrfs_root *reloc_root;
173
174	unsigned long state;
175	struct btrfs_root_item root_item;
176	struct btrfs_key root_key;
177	struct btrfs_fs_info *fs_info;
178	struct extent_io_tree dirty_log_pages;
179
180	struct mutex objectid_mutex;
181
182	spinlock_t accounting_lock;
183	struct btrfs_block_rsv *block_rsv;
184
185	struct mutex log_mutex;
186	wait_queue_head_t log_writer_wait;
187	wait_queue_head_t log_commit_wait[2];
188	struct list_head log_ctxs[2];
189	/* Used only for log trees of subvolumes, not for the log root tree */
190	atomic_t log_writers;
191	atomic_t log_commit[2];
192	/* Used only for log trees of subvolumes, not for the log root tree */
193	atomic_t log_batch;
194	/*
195	 * Protected by the 'log_mutex' lock but can be read without holding
196	 * that lock to avoid unnecessary lock contention, in which case it
197	 * should be read using btrfs_get_root_log_transid() except if it's a
198	 * log tree in which case it can be directly accessed. Updates to this
199	 * field should always use btrfs_set_root_log_transid(), except for log
200	 * trees where the field can be updated directly.
201	 */
202	int log_transid;
203	/* No matter the commit succeeds or not*/
204	int log_transid_committed;
205	/*
206	 * Just be updated when the commit succeeds. Use
207	 * btrfs_get_root_last_log_commit() and btrfs_set_root_last_log_commit()
208	 * to access this field.
209	 */
210	int last_log_commit;
211	pid_t log_start_pid;
212
213	u64 last_trans;
214
215	u64 free_objectid;
216
217	struct btrfs_key defrag_progress;
218	struct btrfs_key defrag_max;
219
220	/* The dirty list is only used by non-shareable roots */
221	struct list_head dirty_list;
222
223	struct list_head root_list;
224
225	spinlock_t inode_lock;
226	/* red-black tree that keeps track of in-memory inodes */
227	struct rb_root inode_tree;
228
229	/*
230	 * Xarray that keeps track of delayed nodes of every inode, protected
231	 * by @inode_lock.
232	 */
233	struct xarray delayed_nodes;
234	/*
235	 * right now this just gets used so that a root has its own devid
236	 * for stat.  It may be used for more later
237	 */
238	dev_t anon_dev;
239
240	spinlock_t root_item_lock;
241	refcount_t refs;
242
243	struct mutex delalloc_mutex;
244	spinlock_t delalloc_lock;
245	/*
246	 * all of the inodes that have delalloc bytes.  It is possible for
247	 * this list to be empty even when there is still dirty data=ordered
248	 * extents waiting to finish IO.
249	 */
250	struct list_head delalloc_inodes;
251	struct list_head delalloc_root;
252	u64 nr_delalloc_inodes;
253
254	struct mutex ordered_extent_mutex;
255	/*
256	 * this is used by the balancing code to wait for all the pending
257	 * ordered extents
258	 */
259	spinlock_t ordered_extent_lock;
260
261	/*
262	 * all of the data=ordered extents pending writeback
263	 * these can span multiple transactions and basically include
264	 * every dirty data page that isn't from nodatacow
265	 */
266	struct list_head ordered_extents;
267	struct list_head ordered_root;
268	u64 nr_ordered_extents;
269
270	/*
271	 * Not empty if this subvolume root has gone through tree block swap
272	 * (relocation)
273	 *
274	 * Will be used by reloc_control::dirty_subvol_roots.
275	 */
276	struct list_head reloc_dirty_list;
277
278	/*
279	 * Number of currently running SEND ioctls to prevent
280	 * manipulation with the read-only status via SUBVOL_SETFLAGS
281	 */
282	int send_in_progress;
283	/*
284	 * Number of currently running deduplication operations that have a
285	 * destination inode belonging to this root. Protected by the lock
286	 * root_item_lock.
287	 */
288	int dedupe_in_progress;
289	/* For exclusion of snapshot creation and nocow writes */
290	struct btrfs_drew_lock snapshot_lock;
291
292	atomic_t snapshot_force_cow;
293
294	/* For qgroup metadata reserved space */
295	spinlock_t qgroup_meta_rsv_lock;
296	u64 qgroup_meta_rsv_pertrans;
297	u64 qgroup_meta_rsv_prealloc;
298	wait_queue_head_t qgroup_flush_wait;
299
300	/* Number of active swapfiles */
301	atomic_t nr_swapfiles;
302
303	/* Record pairs of swapped blocks for qgroup */
304	struct btrfs_qgroup_swapped_blocks swapped_blocks;
305
306	/* Used only by log trees, when logging csum items */
307	struct extent_io_tree log_csum_range;
308
309	/* Used in simple quotas, track root during relocation. */
310	u64 relocation_src_root;
311
312#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
313	u64 alloc_bytenr;
314#endif
315
316#ifdef CONFIG_BTRFS_DEBUG
317	struct list_head leak_list;
318#endif
319};
320
321static inline bool btrfs_root_readonly(const struct btrfs_root *root)
322{
323	/* Byte-swap the constant at compile time, root_item::flags is LE */
324	return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_RDONLY)) != 0;
325}
326
327static inline bool btrfs_root_dead(const struct btrfs_root *root)
328{
329	/* Byte-swap the constant at compile time, root_item::flags is LE */
330	return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_DEAD)) != 0;
331}
332
333static inline u64 btrfs_root_id(const struct btrfs_root *root)
334{
335	return root->root_key.objectid;
336}
337
338static inline int btrfs_get_root_log_transid(const struct btrfs_root *root)
339{
340	return READ_ONCE(root->log_transid);
341}
342
343static inline void btrfs_set_root_log_transid(struct btrfs_root *root, int log_transid)
344{
345	WRITE_ONCE(root->log_transid, log_transid);
346}
347
348static inline int btrfs_get_root_last_log_commit(const struct btrfs_root *root)
349{
350	return READ_ONCE(root->last_log_commit);
351}
352
353static inline void btrfs_set_root_last_log_commit(struct btrfs_root *root, int commit_id)
354{
355	WRITE_ONCE(root->last_log_commit, commit_id);
356}
357
358/*
359 * Structure that conveys information about an extent that is going to replace
360 * all the extents in a file range.
361 */
362struct btrfs_replace_extent_info {
363	u64 disk_offset;
364	u64 disk_len;
365	u64 data_offset;
366	u64 data_len;
367	u64 file_offset;
368	/* Pointer to a file extent item of type regular or prealloc. */
369	char *extent_buf;
370	/*
371	 * Set to true when attempting to replace a file range with a new extent
372	 * described by this structure, set to false when attempting to clone an
373	 * existing extent into a file range.
374	 */
375	bool is_new_extent;
376	/* Indicate if we should update the inode's mtime and ctime. */
377	bool update_times;
378	/* Meaningful only if is_new_extent is true. */
379	int qgroup_reserved;
380	/*
381	 * Meaningful only if is_new_extent is true.
382	 * Used to track how many extent items we have already inserted in a
383	 * subvolume tree that refer to the extent described by this structure,
384	 * so that we know when to create a new delayed ref or update an existing
385	 * one.
386	 */
387	int insertions;
388};
389
390/* Arguments for btrfs_drop_extents() */
391struct btrfs_drop_extents_args {
392	/* Input parameters */
393
394	/*
395	 * If NULL, btrfs_drop_extents() will allocate and free its own path.
396	 * If 'replace_extent' is true, this must not be NULL. Also the path
397	 * is always released except if 'replace_extent' is true and
398	 * btrfs_drop_extents() sets 'extent_inserted' to true, in which case
399	 * the path is kept locked.
400	 */
401	struct btrfs_path *path;
402	/* Start offset of the range to drop extents from */
403	u64 start;
404	/* End (exclusive, last byte + 1) of the range to drop extents from */
405	u64 end;
406	/* If true drop all the extent maps in the range */
407	bool drop_cache;
408	/*
409	 * If true it means we want to insert a new extent after dropping all
410	 * the extents in the range. If this is true, the 'extent_item_size'
411	 * parameter must be set as well and the 'extent_inserted' field will
412	 * be set to true by btrfs_drop_extents() if it could insert the new
413	 * extent.
414	 * Note: when this is set to true the path must not be NULL.
415	 */
416	bool replace_extent;
417	/*
418	 * Used if 'replace_extent' is true. Size of the file extent item to
419	 * insert after dropping all existing extents in the range
420	 */
421	u32 extent_item_size;
422
423	/* Output parameters */
424
425	/*
426	 * Set to the minimum between the input parameter 'end' and the end
427	 * (exclusive, last byte + 1) of the last dropped extent. This is always
428	 * set even if btrfs_drop_extents() returns an error.
429	 */
430	u64 drop_end;
431	/*
432	 * The number of allocated bytes found in the range. This can be smaller
433	 * than the range's length when there are holes in the range.
434	 */
435	u64 bytes_found;
436	/*
437	 * Only set if 'replace_extent' is true. Set to true if we were able
438	 * to insert a replacement extent after dropping all extents in the
439	 * range, otherwise set to false by btrfs_drop_extents().
440	 * Also, if btrfs_drop_extents() has set this to true it means it
441	 * returned with the path locked, otherwise if it has set this to
442	 * false it has returned with the path released.
443	 */
444	bool extent_inserted;
445};
446
447struct btrfs_file_private {
448	void *filldir_buf;
449	u64 last_index;
450	struct extent_state *llseek_cached_state;
451};
452
453static inline u32 BTRFS_LEAF_DATA_SIZE(const struct btrfs_fs_info *info)
454{
455	return info->nodesize - sizeof(struct btrfs_header);
456}
457
458static inline u32 BTRFS_MAX_ITEM_SIZE(const struct btrfs_fs_info *info)
459{
460	return BTRFS_LEAF_DATA_SIZE(info) - sizeof(struct btrfs_item);
461}
462
463static inline u32 BTRFS_NODEPTRS_PER_BLOCK(const struct btrfs_fs_info *info)
464{
465	return BTRFS_LEAF_DATA_SIZE(info) / sizeof(struct btrfs_key_ptr);
466}
467
468static inline u32 BTRFS_MAX_XATTR_SIZE(const struct btrfs_fs_info *info)
469{
470	return BTRFS_MAX_ITEM_SIZE(info) - sizeof(struct btrfs_dir_item);
471}
472
473#define BTRFS_BYTES_TO_BLKS(fs_info, bytes) \
474				((bytes) >> (fs_info)->sectorsize_bits)
475
476static inline gfp_t btrfs_alloc_write_mask(struct address_space *mapping)
477{
478	return mapping_gfp_constraint(mapping, ~__GFP_FS);
479}
480
481int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
482				   u64 start, u64 end);
483int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
484			 u64 num_bytes, u64 *actual_bytes);
485int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range);
486
487/* ctree.c */
488int __init btrfs_ctree_init(void);
489void __cold btrfs_ctree_exit(void);
490
491int btrfs_bin_search(struct extent_buffer *eb, int first_slot,
492		     const struct btrfs_key *key, int *slot);
493
494int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2);
495
496#ifdef __LITTLE_ENDIAN
497
498/*
499 * Compare two keys, on little-endian the disk order is same as CPU order and
500 * we can avoid the conversion.
501 */
502static inline int btrfs_comp_keys(const struct btrfs_disk_key *disk_key,
503				  const struct btrfs_key *k2)
504{
505	const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key;
506
507	return btrfs_comp_cpu_keys(k1, k2);
508}
509
510#else
511
512/* Compare two keys in a memcmp fashion. */
513static inline int btrfs_comp_keys(const struct btrfs_disk_key *disk,
514				  const struct btrfs_key *k2)
515{
516	struct btrfs_key k1;
517
518	btrfs_disk_key_to_cpu(&k1, disk);
519
520	return btrfs_comp_cpu_keys(&k1, k2);
521}
522
523#endif
524
525int btrfs_previous_item(struct btrfs_root *root,
526			struct btrfs_path *path, u64 min_objectid,
527			int type);
528int btrfs_previous_extent_item(struct btrfs_root *root,
529			struct btrfs_path *path, u64 min_objectid);
530void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
531			     struct btrfs_path *path,
532			     const struct btrfs_key *new_key);
533struct extent_buffer *btrfs_root_node(struct btrfs_root *root);
534int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
535			struct btrfs_key *key, int lowest_level,
536			u64 min_trans);
537int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
538			 struct btrfs_path *path,
539			 u64 min_trans);
540struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
541					   int slot);
542
543int btrfs_cow_block(struct btrfs_trans_handle *trans,
544		    struct btrfs_root *root, struct extent_buffer *buf,
545		    struct extent_buffer *parent, int parent_slot,
546		    struct extent_buffer **cow_ret,
547		    enum btrfs_lock_nesting nest);
548int btrfs_force_cow_block(struct btrfs_trans_handle *trans,
549			  struct btrfs_root *root,
550			  struct extent_buffer *buf,
551			  struct extent_buffer *parent, int parent_slot,
552			  struct extent_buffer **cow_ret,
553			  u64 search_start, u64 empty_size,
554			  enum btrfs_lock_nesting nest);
555int btrfs_copy_root(struct btrfs_trans_handle *trans,
556		      struct btrfs_root *root,
557		      struct extent_buffer *buf,
558		      struct extent_buffer **cow_ret, u64 new_root_objectid);
559bool btrfs_block_can_be_shared(struct btrfs_trans_handle *trans,
560			       struct btrfs_root *root,
561			       struct extent_buffer *buf);
562int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
563		  struct btrfs_path *path, int level, int slot);
564void btrfs_extend_item(struct btrfs_trans_handle *trans,
565		       struct btrfs_path *path, u32 data_size);
566void btrfs_truncate_item(struct btrfs_trans_handle *trans,
567			 struct btrfs_path *path, u32 new_size, int from_end);
568int btrfs_split_item(struct btrfs_trans_handle *trans,
569		     struct btrfs_root *root,
570		     struct btrfs_path *path,
571		     const struct btrfs_key *new_key,
572		     unsigned long split_offset);
573int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
574			 struct btrfs_root *root,
575			 struct btrfs_path *path,
576			 const struct btrfs_key *new_key);
577int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
578		u64 inum, u64 ioff, u8 key_type, struct btrfs_key *found_key);
579int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
580		      const struct btrfs_key *key, struct btrfs_path *p,
581		      int ins_len, int cow);
582int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
583			  struct btrfs_path *p, u64 time_seq);
584int btrfs_search_slot_for_read(struct btrfs_root *root,
585			       const struct btrfs_key *key,
586			       struct btrfs_path *p, int find_higher,
587			       int return_any);
588void btrfs_release_path(struct btrfs_path *p);
589struct btrfs_path *btrfs_alloc_path(void);
590void btrfs_free_path(struct btrfs_path *p);
591
592int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
593		   struct btrfs_path *path, int slot, int nr);
594static inline int btrfs_del_item(struct btrfs_trans_handle *trans,
595				 struct btrfs_root *root,
596				 struct btrfs_path *path)
597{
598	return btrfs_del_items(trans, root, path, path->slots[0], 1);
599}
600
601/*
602 * Describes a batch of items to insert in a btree. This is used by
603 * btrfs_insert_empty_items().
604 */
605struct btrfs_item_batch {
606	/*
607	 * Pointer to an array containing the keys of the items to insert (in
608	 * sorted order).
609	 */
610	const struct btrfs_key *keys;
611	/* Pointer to an array containing the data size for each item to insert. */
612	const u32 *data_sizes;
613	/*
614	 * The sum of data sizes for all items. The caller can compute this while
615	 * setting up the data_sizes array, so it ends up being more efficient
616	 * than having btrfs_insert_empty_items() or setup_item_for_insert()
617	 * doing it, as it would avoid an extra loop over a potentially large
618	 * array, and in the case of setup_item_for_insert(), we would be doing
619	 * it while holding a write lock on a leaf and often on upper level nodes
620	 * too, unnecessarily increasing the size of a critical section.
621	 */
622	u32 total_data_size;
623	/* Size of the keys and data_sizes arrays (number of items in the batch). */
624	int nr;
625};
626
627void btrfs_setup_item_for_insert(struct btrfs_trans_handle *trans,
628				 struct btrfs_root *root,
629				 struct btrfs_path *path,
630				 const struct btrfs_key *key,
631				 u32 data_size);
632int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
633		      const struct btrfs_key *key, void *data, u32 data_size);
634int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
635			     struct btrfs_root *root,
636			     struct btrfs_path *path,
637			     const struct btrfs_item_batch *batch);
638
639static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
640					  struct btrfs_root *root,
641					  struct btrfs_path *path,
642					  const struct btrfs_key *key,
643					  u32 data_size)
644{
645	struct btrfs_item_batch batch;
646
647	batch.keys = key;
648	batch.data_sizes = &data_size;
649	batch.total_data_size = data_size;
650	batch.nr = 1;
651
652	return btrfs_insert_empty_items(trans, root, path, &batch);
653}
654
655int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
656			u64 time_seq);
657
658int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key,
659			   struct btrfs_path *path);
660
661int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key,
662			      struct btrfs_path *path);
663
664/*
665 * Search in @root for a given @key, and store the slot found in @found_key.
666 *
667 * @root:	The root node of the tree.
668 * @key:	The key we are looking for.
669 * @found_key:	Will hold the found item.
670 * @path:	Holds the current slot/leaf.
671 * @iter_ret:	Contains the value returned from btrfs_search_slot or
672 * 		btrfs_get_next_valid_item, whichever was executed last.
673 *
674 * The @iter_ret is an output variable that will contain the return value of
675 * btrfs_search_slot, if it encountered an error, or the value returned from
676 * btrfs_get_next_valid_item otherwise. That return value can be 0, if a valid
677 * slot was found, 1 if there were no more leaves, and <0 if there was an error.
678 *
679 * It's recommended to use a separate variable for iter_ret and then use it to
680 * set the function return value so there's no confusion of the 0/1/errno
681 * values stemming from btrfs_search_slot.
682 */
683#define btrfs_for_each_slot(root, key, found_key, path, iter_ret)		\
684	for (iter_ret = btrfs_search_slot(NULL, (root), (key), (path), 0, 0);	\
685		(iter_ret) >= 0 &&						\
686		(iter_ret = btrfs_get_next_valid_item((root), (found_key), (path))) == 0; \
687		(path)->slots[0]++						\
688	)
689
690int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq);
691
692/*
693 * Search the tree again to find a leaf with greater keys.
694 *
695 * Returns 0 if it found something or 1 if there are no greater leaves.
696 * Returns < 0 on error.
697 */
698static inline int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
699{
700	return btrfs_next_old_leaf(root, path, 0);
701}
702
703static inline int btrfs_next_item(struct btrfs_root *root, struct btrfs_path *p)
704{
705	return btrfs_next_old_item(root, p, 0);
706}
707int btrfs_leaf_free_space(const struct extent_buffer *leaf);
708
709static inline int is_fstree(u64 rootid)
710{
711	if (rootid == BTRFS_FS_TREE_OBJECTID ||
712	    ((s64)rootid >= (s64)BTRFS_FIRST_FREE_OBJECTID &&
713	      !btrfs_qgroup_level(rootid)))
714		return 1;
715	return 0;
716}
717
718static inline bool btrfs_is_data_reloc_root(const struct btrfs_root *root)
719{
720	return root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID;
721}
722
723u16 btrfs_csum_type_size(u16 type);
724int btrfs_super_csum_size(const struct btrfs_super_block *s);
725const char *btrfs_super_csum_name(u16 csum_type);
726const char *btrfs_super_csum_driver(u16 csum_type);
727size_t __attribute_const__ btrfs_get_num_csums(void);
728
729/*
730 * We use page status Private2 to indicate there is an ordered extent with
731 * unfinished IO.
732 *
733 * Rename the Private2 accessors to Ordered, to improve readability.
734 */
735#define PageOrdered(page)		PagePrivate2(page)
736#define SetPageOrdered(page)		SetPagePrivate2(page)
737#define ClearPageOrdered(page)		ClearPagePrivate2(page)
738#define folio_test_ordered(folio)	folio_test_private_2(folio)
739#define folio_set_ordered(folio)	folio_set_private_2(folio)
740#define folio_clear_ordered(folio)	folio_clear_private_2(folio)
741
742#endif
v6.9.4
  1/* SPDX-License-Identifier: GPL-2.0 */
  2/*
  3 * Copyright (C) 2007 Oracle.  All rights reserved.
  4 */
  5
  6#ifndef BTRFS_CTREE_H
  7#define BTRFS_CTREE_H
  8
  9#include <linux/pagemap.h>
 10#include <linux/spinlock.h>
 11#include <linux/rbtree.h>
 12#include <linux/mutex.h>
 13#include <linux/wait.h>
 14#include <linux/list.h>
 15#include <linux/atomic.h>
 16#include <linux/xarray.h>
 17#include <linux/refcount.h>
 18#include <uapi/linux/btrfs_tree.h>
 19#include "locking.h"
 20#include "fs.h"
 21#include "accessors.h"
 22#include "extent-io-tree.h"
 23
 24struct extent_buffer;
 25struct btrfs_block_rsv;
 26struct btrfs_trans_handle;
 
 
 
 
 27struct btrfs_block_group;
 
 
 
 
 
 
 
 
 
 28
 29/* Read ahead values for struct btrfs_path.reada */
 30enum {
 31	READA_NONE,
 32	READA_BACK,
 33	READA_FORWARD,
 34	/*
 35	 * Similar to READA_FORWARD but unlike it:
 36	 *
 37	 * 1) It will trigger readahead even for leaves that are not close to
 38	 *    each other on disk;
 39	 * 2) It also triggers readahead for nodes;
 40	 * 3) During a search, even when a node or leaf is already in memory, it
 41	 *    will still trigger readahead for other nodes and leaves that follow
 42	 *    it.
 43	 *
 44	 * This is meant to be used only when we know we are iterating over the
 45	 * entire tree or a very large part of it.
 46	 */
 47	READA_FORWARD_ALWAYS,
 48};
 49
 50/*
 51 * btrfs_paths remember the path taken from the root down to the leaf.
 52 * level 0 is always the leaf, and nodes[1...BTRFS_MAX_LEVEL] will point
 53 * to any other levels that are present.
 54 *
 55 * The slots array records the index of the item or block pointer
 56 * used while walking the tree.
 57 */
 58struct btrfs_path {
 59	struct extent_buffer *nodes[BTRFS_MAX_LEVEL];
 60	int slots[BTRFS_MAX_LEVEL];
 61	/* if there is real range locking, this locks field will change */
 62	u8 locks[BTRFS_MAX_LEVEL];
 63	u8 reada;
 64	/* keep some upper locks as we walk down */
 65	u8 lowest_level;
 66
 67	/*
 68	 * set by btrfs_split_item, tells search_slot to keep all locks
 69	 * and to force calls to keep space in the nodes
 70	 */
 71	unsigned int search_for_split:1;
 72	unsigned int keep_locks:1;
 73	unsigned int skip_locking:1;
 74	unsigned int search_commit_root:1;
 75	unsigned int need_commit_sem:1;
 76	unsigned int skip_release_on_error:1;
 77	/*
 78	 * Indicate that new item (btrfs_search_slot) is extending already
 79	 * existing item and ins_len contains only the data size and not item
 80	 * header (ie. sizeof(struct btrfs_item) is not included).
 81	 */
 82	unsigned int search_for_extension:1;
 83	/* Stop search if any locks need to be taken (for read) */
 84	unsigned int nowait:1;
 85};
 86
 87/*
 88 * The state of btrfs root
 89 */
 90enum {
 91	/*
 92	 * btrfs_record_root_in_trans is a multi-step process, and it can race
 93	 * with the balancing code.   But the race is very small, and only the
 94	 * first time the root is added to each transaction.  So IN_TRANS_SETUP
 95	 * is used to tell us when more checks are required
 96	 */
 97	BTRFS_ROOT_IN_TRANS_SETUP,
 98
 99	/*
100	 * Set if tree blocks of this root can be shared by other roots.
101	 * Only subvolume trees and their reloc trees have this bit set.
102	 * Conflicts with TRACK_DIRTY bit.
103	 *
104	 * This affects two things:
105	 *
106	 * - How balance works
107	 *   For shareable roots, we need to use reloc tree and do path
108	 *   replacement for balance, and need various pre/post hooks for
109	 *   snapshot creation to handle them.
110	 *
111	 *   While for non-shareable trees, we just simply do a tree search
112	 *   with COW.
113	 *
114	 * - How dirty roots are tracked
115	 *   For shareable roots, btrfs_record_root_in_trans() is needed to
116	 *   track them, while non-subvolume roots have TRACK_DIRTY bit, they
117	 *   don't need to set this manually.
118	 */
119	BTRFS_ROOT_SHAREABLE,
120	BTRFS_ROOT_TRACK_DIRTY,
121	BTRFS_ROOT_IN_RADIX,
122	BTRFS_ROOT_ORPHAN_ITEM_INSERTED,
123	BTRFS_ROOT_DEFRAG_RUNNING,
124	BTRFS_ROOT_FORCE_COW,
125	BTRFS_ROOT_MULTI_LOG_TASKS,
126	BTRFS_ROOT_DIRTY,
127	BTRFS_ROOT_DELETING,
128
129	/*
130	 * Reloc tree is orphan, only kept here for qgroup delayed subtree scan
131	 *
132	 * Set for the subvolume tree owning the reloc tree.
133	 */
134	BTRFS_ROOT_DEAD_RELOC_TREE,
135	/* Mark dead root stored on device whose cleanup needs to be resumed */
136	BTRFS_ROOT_DEAD_TREE,
137	/* The root has a log tree. Used for subvolume roots and the tree root. */
138	BTRFS_ROOT_HAS_LOG_TREE,
139	/* Qgroup flushing is in progress */
140	BTRFS_ROOT_QGROUP_FLUSHING,
141	/* We started the orphan cleanup for this root. */
142	BTRFS_ROOT_ORPHAN_CLEANUP,
143	/* This root has a drop operation that was started previously. */
144	BTRFS_ROOT_UNFINISHED_DROP,
145	/* This reloc root needs to have its buffers lockdep class reset. */
146	BTRFS_ROOT_RESET_LOCKDEP_CLASS,
147};
148
149/*
150 * Record swapped tree blocks of a subvolume tree for delayed subtree trace
151 * code. For detail check comment in fs/btrfs/qgroup.c.
152 */
153struct btrfs_qgroup_swapped_blocks {
154	spinlock_t lock;
155	/* RM_EMPTY_ROOT() of above blocks[] */
156	bool swapped;
157	struct rb_root blocks[BTRFS_MAX_LEVEL];
158};
159
160/*
161 * in ram representation of the tree.  extent_root is used for all allocations
162 * and for the extent tree extent_root root.
163 */
164struct btrfs_root {
165	struct rb_node rb_node;
166
167	struct extent_buffer *node;
168
169	struct extent_buffer *commit_root;
170	struct btrfs_root *log_root;
171	struct btrfs_root *reloc_root;
172
173	unsigned long state;
174	struct btrfs_root_item root_item;
175	struct btrfs_key root_key;
176	struct btrfs_fs_info *fs_info;
177	struct extent_io_tree dirty_log_pages;
178
179	struct mutex objectid_mutex;
180
181	spinlock_t accounting_lock;
182	struct btrfs_block_rsv *block_rsv;
183
184	struct mutex log_mutex;
185	wait_queue_head_t log_writer_wait;
186	wait_queue_head_t log_commit_wait[2];
187	struct list_head log_ctxs[2];
188	/* Used only for log trees of subvolumes, not for the log root tree */
189	atomic_t log_writers;
190	atomic_t log_commit[2];
191	/* Used only for log trees of subvolumes, not for the log root tree */
192	atomic_t log_batch;
193	/*
194	 * Protected by the 'log_mutex' lock but can be read without holding
195	 * that lock to avoid unnecessary lock contention, in which case it
196	 * should be read using btrfs_get_root_log_transid() except if it's a
197	 * log tree in which case it can be directly accessed. Updates to this
198	 * field should always use btrfs_set_root_log_transid(), except for log
199	 * trees where the field can be updated directly.
200	 */
201	int log_transid;
202	/* No matter the commit succeeds or not*/
203	int log_transid_committed;
204	/*
205	 * Just be updated when the commit succeeds. Use
206	 * btrfs_get_root_last_log_commit() and btrfs_set_root_last_log_commit()
207	 * to access this field.
208	 */
209	int last_log_commit;
210	pid_t log_start_pid;
211
212	u64 last_trans;
213
214	u64 free_objectid;
215
216	struct btrfs_key defrag_progress;
217	struct btrfs_key defrag_max;
218
219	/* The dirty list is only used by non-shareable roots */
220	struct list_head dirty_list;
221
222	struct list_head root_list;
223
224	spinlock_t inode_lock;
225	/* red-black tree that keeps track of in-memory inodes */
226	struct rb_root inode_tree;
227
228	/*
229	 * Xarray that keeps track of delayed nodes of every inode, protected
230	 * by @inode_lock.
231	 */
232	struct xarray delayed_nodes;
233	/*
234	 * right now this just gets used so that a root has its own devid
235	 * for stat.  It may be used for more later
236	 */
237	dev_t anon_dev;
238
239	spinlock_t root_item_lock;
240	refcount_t refs;
241
242	struct mutex delalloc_mutex;
243	spinlock_t delalloc_lock;
244	/*
245	 * all of the inodes that have delalloc bytes.  It is possible for
246	 * this list to be empty even when there is still dirty data=ordered
247	 * extents waiting to finish IO.
248	 */
249	struct list_head delalloc_inodes;
250	struct list_head delalloc_root;
251	u64 nr_delalloc_inodes;
252
253	struct mutex ordered_extent_mutex;
254	/*
255	 * this is used by the balancing code to wait for all the pending
256	 * ordered extents
257	 */
258	spinlock_t ordered_extent_lock;
259
260	/*
261	 * all of the data=ordered extents pending writeback
262	 * these can span multiple transactions and basically include
263	 * every dirty data page that isn't from nodatacow
264	 */
265	struct list_head ordered_extents;
266	struct list_head ordered_root;
267	u64 nr_ordered_extents;
268
269	/*
270	 * Not empty if this subvolume root has gone through tree block swap
271	 * (relocation)
272	 *
273	 * Will be used by reloc_control::dirty_subvol_roots.
274	 */
275	struct list_head reloc_dirty_list;
276
277	/*
278	 * Number of currently running SEND ioctls to prevent
279	 * manipulation with the read-only status via SUBVOL_SETFLAGS
280	 */
281	int send_in_progress;
282	/*
283	 * Number of currently running deduplication operations that have a
284	 * destination inode belonging to this root. Protected by the lock
285	 * root_item_lock.
286	 */
287	int dedupe_in_progress;
288	/* For exclusion of snapshot creation and nocow writes */
289	struct btrfs_drew_lock snapshot_lock;
290
291	atomic_t snapshot_force_cow;
292
293	/* For qgroup metadata reserved space */
294	spinlock_t qgroup_meta_rsv_lock;
295	u64 qgroup_meta_rsv_pertrans;
296	u64 qgroup_meta_rsv_prealloc;
297	wait_queue_head_t qgroup_flush_wait;
298
299	/* Number of active swapfiles */
300	atomic_t nr_swapfiles;
301
302	/* Record pairs of swapped blocks for qgroup */
303	struct btrfs_qgroup_swapped_blocks swapped_blocks;
304
305	/* Used only by log trees, when logging csum items */
306	struct extent_io_tree log_csum_range;
307
308	/* Used in simple quotas, track root during relocation. */
309	u64 relocation_src_root;
310
311#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
312	u64 alloc_bytenr;
313#endif
314
315#ifdef CONFIG_BTRFS_DEBUG
316	struct list_head leak_list;
317#endif
318};
319
320static inline bool btrfs_root_readonly(const struct btrfs_root *root)
321{
322	/* Byte-swap the constant at compile time, root_item::flags is LE */
323	return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_RDONLY)) != 0;
324}
325
326static inline bool btrfs_root_dead(const struct btrfs_root *root)
327{
328	/* Byte-swap the constant at compile time, root_item::flags is LE */
329	return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_DEAD)) != 0;
330}
331
332static inline u64 btrfs_root_id(const struct btrfs_root *root)
333{
334	return root->root_key.objectid;
335}
336
337static inline int btrfs_get_root_log_transid(const struct btrfs_root *root)
338{
339	return READ_ONCE(root->log_transid);
340}
341
342static inline void btrfs_set_root_log_transid(struct btrfs_root *root, int log_transid)
343{
344	WRITE_ONCE(root->log_transid, log_transid);
345}
346
347static inline int btrfs_get_root_last_log_commit(const struct btrfs_root *root)
348{
349	return READ_ONCE(root->last_log_commit);
350}
351
352static inline void btrfs_set_root_last_log_commit(struct btrfs_root *root, int commit_id)
353{
354	WRITE_ONCE(root->last_log_commit, commit_id);
355}
356
357/*
358 * Structure that conveys information about an extent that is going to replace
359 * all the extents in a file range.
360 */
361struct btrfs_replace_extent_info {
362	u64 disk_offset;
363	u64 disk_len;
364	u64 data_offset;
365	u64 data_len;
366	u64 file_offset;
367	/* Pointer to a file extent item of type regular or prealloc. */
368	char *extent_buf;
369	/*
370	 * Set to true when attempting to replace a file range with a new extent
371	 * described by this structure, set to false when attempting to clone an
372	 * existing extent into a file range.
373	 */
374	bool is_new_extent;
375	/* Indicate if we should update the inode's mtime and ctime. */
376	bool update_times;
377	/* Meaningful only if is_new_extent is true. */
378	int qgroup_reserved;
379	/*
380	 * Meaningful only if is_new_extent is true.
381	 * Used to track how many extent items we have already inserted in a
382	 * subvolume tree that refer to the extent described by this structure,
383	 * so that we know when to create a new delayed ref or update an existing
384	 * one.
385	 */
386	int insertions;
387};
388
389/* Arguments for btrfs_drop_extents() */
390struct btrfs_drop_extents_args {
391	/* Input parameters */
392
393	/*
394	 * If NULL, btrfs_drop_extents() will allocate and free its own path.
395	 * If 'replace_extent' is true, this must not be NULL. Also the path
396	 * is always released except if 'replace_extent' is true and
397	 * btrfs_drop_extents() sets 'extent_inserted' to true, in which case
398	 * the path is kept locked.
399	 */
400	struct btrfs_path *path;
401	/* Start offset of the range to drop extents from */
402	u64 start;
403	/* End (exclusive, last byte + 1) of the range to drop extents from */
404	u64 end;
405	/* If true drop all the extent maps in the range */
406	bool drop_cache;
407	/*
408	 * If true it means we want to insert a new extent after dropping all
409	 * the extents in the range. If this is true, the 'extent_item_size'
410	 * parameter must be set as well and the 'extent_inserted' field will
411	 * be set to true by btrfs_drop_extents() if it could insert the new
412	 * extent.
413	 * Note: when this is set to true the path must not be NULL.
414	 */
415	bool replace_extent;
416	/*
417	 * Used if 'replace_extent' is true. Size of the file extent item to
418	 * insert after dropping all existing extents in the range
419	 */
420	u32 extent_item_size;
421
422	/* Output parameters */
423
424	/*
425	 * Set to the minimum between the input parameter 'end' and the end
426	 * (exclusive, last byte + 1) of the last dropped extent. This is always
427	 * set even if btrfs_drop_extents() returns an error.
428	 */
429	u64 drop_end;
430	/*
431	 * The number of allocated bytes found in the range. This can be smaller
432	 * than the range's length when there are holes in the range.
433	 */
434	u64 bytes_found;
435	/*
436	 * Only set if 'replace_extent' is true. Set to true if we were able
437	 * to insert a replacement extent after dropping all extents in the
438	 * range, otherwise set to false by btrfs_drop_extents().
439	 * Also, if btrfs_drop_extents() has set this to true it means it
440	 * returned with the path locked, otherwise if it has set this to
441	 * false it has returned with the path released.
442	 */
443	bool extent_inserted;
444};
445
446struct btrfs_file_private {
447	void *filldir_buf;
448	u64 last_index;
449	struct extent_state *llseek_cached_state;
450};
451
452static inline u32 BTRFS_LEAF_DATA_SIZE(const struct btrfs_fs_info *info)
453{
454	return info->nodesize - sizeof(struct btrfs_header);
455}
456
457static inline u32 BTRFS_MAX_ITEM_SIZE(const struct btrfs_fs_info *info)
458{
459	return BTRFS_LEAF_DATA_SIZE(info) - sizeof(struct btrfs_item);
460}
461
462static inline u32 BTRFS_NODEPTRS_PER_BLOCK(const struct btrfs_fs_info *info)
463{
464	return BTRFS_LEAF_DATA_SIZE(info) / sizeof(struct btrfs_key_ptr);
465}
466
467static inline u32 BTRFS_MAX_XATTR_SIZE(const struct btrfs_fs_info *info)
468{
469	return BTRFS_MAX_ITEM_SIZE(info) - sizeof(struct btrfs_dir_item);
470}
471
472#define BTRFS_BYTES_TO_BLKS(fs_info, bytes) \
473				((bytes) >> (fs_info)->sectorsize_bits)
474
475static inline gfp_t btrfs_alloc_write_mask(struct address_space *mapping)
476{
477	return mapping_gfp_constraint(mapping, ~__GFP_FS);
478}
479
480void btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info, u64 start, u64 end);
 
481int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
482			 u64 num_bytes, u64 *actual_bytes);
483int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range);
484
485/* ctree.c */
486int __init btrfs_ctree_init(void);
487void __cold btrfs_ctree_exit(void);
488
489int btrfs_bin_search(struct extent_buffer *eb, int first_slot,
490		     const struct btrfs_key *key, int *slot);
491
492int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2);
493
494#ifdef __LITTLE_ENDIAN
495
496/*
497 * Compare two keys, on little-endian the disk order is same as CPU order and
498 * we can avoid the conversion.
499 */
500static inline int btrfs_comp_keys(const struct btrfs_disk_key *disk_key,
501				  const struct btrfs_key *k2)
502{
503	const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key;
504
505	return btrfs_comp_cpu_keys(k1, k2);
506}
507
508#else
509
510/* Compare two keys in a memcmp fashion. */
511static inline int btrfs_comp_keys(const struct btrfs_disk_key *disk,
512				  const struct btrfs_key *k2)
513{
514	struct btrfs_key k1;
515
516	btrfs_disk_key_to_cpu(&k1, disk);
517
518	return btrfs_comp_cpu_keys(&k1, k2);
519}
520
521#endif
522
523int btrfs_previous_item(struct btrfs_root *root,
524			struct btrfs_path *path, u64 min_objectid,
525			int type);
526int btrfs_previous_extent_item(struct btrfs_root *root,
527			struct btrfs_path *path, u64 min_objectid);
528void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
529			     struct btrfs_path *path,
530			     const struct btrfs_key *new_key);
531struct extent_buffer *btrfs_root_node(struct btrfs_root *root);
532int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
533			struct btrfs_key *key, int lowest_level,
534			u64 min_trans);
535int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
536			 struct btrfs_path *path,
537			 u64 min_trans);
538struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
539					   int slot);
540
541int btrfs_cow_block(struct btrfs_trans_handle *trans,
542		    struct btrfs_root *root, struct extent_buffer *buf,
543		    struct extent_buffer *parent, int parent_slot,
544		    struct extent_buffer **cow_ret,
545		    enum btrfs_lock_nesting nest);
546int btrfs_force_cow_block(struct btrfs_trans_handle *trans,
547			  struct btrfs_root *root,
548			  struct extent_buffer *buf,
549			  struct extent_buffer *parent, int parent_slot,
550			  struct extent_buffer **cow_ret,
551			  u64 search_start, u64 empty_size,
552			  enum btrfs_lock_nesting nest);
553int btrfs_copy_root(struct btrfs_trans_handle *trans,
554		      struct btrfs_root *root,
555		      struct extent_buffer *buf,
556		      struct extent_buffer **cow_ret, u64 new_root_objectid);
557bool btrfs_block_can_be_shared(struct btrfs_trans_handle *trans,
558			       struct btrfs_root *root,
559			       struct extent_buffer *buf);
560int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
561		  struct btrfs_path *path, int level, int slot);
562void btrfs_extend_item(struct btrfs_trans_handle *trans,
563		       struct btrfs_path *path, u32 data_size);
564void btrfs_truncate_item(struct btrfs_trans_handle *trans,
565			 struct btrfs_path *path, u32 new_size, int from_end);
566int btrfs_split_item(struct btrfs_trans_handle *trans,
567		     struct btrfs_root *root,
568		     struct btrfs_path *path,
569		     const struct btrfs_key *new_key,
570		     unsigned long split_offset);
571int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
572			 struct btrfs_root *root,
573			 struct btrfs_path *path,
574			 const struct btrfs_key *new_key);
575int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
576		u64 inum, u64 ioff, u8 key_type, struct btrfs_key *found_key);
577int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
578		      const struct btrfs_key *key, struct btrfs_path *p,
579		      int ins_len, int cow);
580int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
581			  struct btrfs_path *p, u64 time_seq);
582int btrfs_search_slot_for_read(struct btrfs_root *root,
583			       const struct btrfs_key *key,
584			       struct btrfs_path *p, int find_higher,
585			       int return_any);
586void btrfs_release_path(struct btrfs_path *p);
587struct btrfs_path *btrfs_alloc_path(void);
588void btrfs_free_path(struct btrfs_path *p);
589
590int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
591		   struct btrfs_path *path, int slot, int nr);
592static inline int btrfs_del_item(struct btrfs_trans_handle *trans,
593				 struct btrfs_root *root,
594				 struct btrfs_path *path)
595{
596	return btrfs_del_items(trans, root, path, path->slots[0], 1);
597}
598
599/*
600 * Describes a batch of items to insert in a btree. This is used by
601 * btrfs_insert_empty_items().
602 */
603struct btrfs_item_batch {
604	/*
605	 * Pointer to an array containing the keys of the items to insert (in
606	 * sorted order).
607	 */
608	const struct btrfs_key *keys;
609	/* Pointer to an array containing the data size for each item to insert. */
610	const u32 *data_sizes;
611	/*
612	 * The sum of data sizes for all items. The caller can compute this while
613	 * setting up the data_sizes array, so it ends up being more efficient
614	 * than having btrfs_insert_empty_items() or setup_item_for_insert()
615	 * doing it, as it would avoid an extra loop over a potentially large
616	 * array, and in the case of setup_item_for_insert(), we would be doing
617	 * it while holding a write lock on a leaf and often on upper level nodes
618	 * too, unnecessarily increasing the size of a critical section.
619	 */
620	u32 total_data_size;
621	/* Size of the keys and data_sizes arrays (number of items in the batch). */
622	int nr;
623};
624
625void btrfs_setup_item_for_insert(struct btrfs_trans_handle *trans,
626				 struct btrfs_root *root,
627				 struct btrfs_path *path,
628				 const struct btrfs_key *key,
629				 u32 data_size);
630int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
631		      const struct btrfs_key *key, void *data, u32 data_size);
632int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
633			     struct btrfs_root *root,
634			     struct btrfs_path *path,
635			     const struct btrfs_item_batch *batch);
636
637static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
638					  struct btrfs_root *root,
639					  struct btrfs_path *path,
640					  const struct btrfs_key *key,
641					  u32 data_size)
642{
643	struct btrfs_item_batch batch;
644
645	batch.keys = key;
646	batch.data_sizes = &data_size;
647	batch.total_data_size = data_size;
648	batch.nr = 1;
649
650	return btrfs_insert_empty_items(trans, root, path, &batch);
651}
652
653int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
654			u64 time_seq);
655
656int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key,
657			   struct btrfs_path *path);
658
659int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key,
660			      struct btrfs_path *path);
661
662/*
663 * Search in @root for a given @key, and store the slot found in @found_key.
664 *
665 * @root:	The root node of the tree.
666 * @key:	The key we are looking for.
667 * @found_key:	Will hold the found item.
668 * @path:	Holds the current slot/leaf.
669 * @iter_ret:	Contains the value returned from btrfs_search_slot or
670 * 		btrfs_get_next_valid_item, whichever was executed last.
671 *
672 * The @iter_ret is an output variable that will contain the return value of
673 * btrfs_search_slot, if it encountered an error, or the value returned from
674 * btrfs_get_next_valid_item otherwise. That return value can be 0, if a valid
675 * slot was found, 1 if there were no more leaves, and <0 if there was an error.
676 *
677 * It's recommended to use a separate variable for iter_ret and then use it to
678 * set the function return value so there's no confusion of the 0/1/errno
679 * values stemming from btrfs_search_slot.
680 */
681#define btrfs_for_each_slot(root, key, found_key, path, iter_ret)		\
682	for (iter_ret = btrfs_search_slot(NULL, (root), (key), (path), 0, 0);	\
683		(iter_ret) >= 0 &&						\
684		(iter_ret = btrfs_get_next_valid_item((root), (found_key), (path))) == 0; \
685		(path)->slots[0]++						\
686	)
687
688int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq);
689
690/*
691 * Search the tree again to find a leaf with greater keys.
692 *
693 * Returns 0 if it found something or 1 if there are no greater leaves.
694 * Returns < 0 on error.
695 */
696static inline int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
697{
698	return btrfs_next_old_leaf(root, path, 0);
699}
700
701static inline int btrfs_next_item(struct btrfs_root *root, struct btrfs_path *p)
702{
703	return btrfs_next_old_item(root, p, 0);
704}
705int btrfs_leaf_free_space(const struct extent_buffer *leaf);
706
707static inline int is_fstree(u64 rootid)
708{
709	if (rootid == BTRFS_FS_TREE_OBJECTID ||
710	    ((s64)rootid >= (s64)BTRFS_FIRST_FREE_OBJECTID &&
711	      !btrfs_qgroup_level(rootid)))
712		return 1;
713	return 0;
714}
715
716static inline bool btrfs_is_data_reloc_root(const struct btrfs_root *root)
717{
718	return root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID;
719}
720
721u16 btrfs_csum_type_size(u16 type);
722int btrfs_super_csum_size(const struct btrfs_super_block *s);
723const char *btrfs_super_csum_name(u16 csum_type);
724const char *btrfs_super_csum_driver(u16 csum_type);
725size_t __attribute_const__ btrfs_get_num_csums(void);
726
727/*
728 * We use page status Private2 to indicate there is an ordered extent with
729 * unfinished IO.
730 *
731 * Rename the Private2 accessors to Ordered, to improve readability.
732 */
733#define PageOrdered(page)		PagePrivate2(page)
734#define SetPageOrdered(page)		SetPagePrivate2(page)
735#define ClearPageOrdered(page)		ClearPagePrivate2(page)
736#define folio_test_ordered(folio)	folio_test_private_2(folio)
737#define folio_set_ordered(folio)	folio_set_private_2(folio)
738#define folio_clear_ordered(folio)	folio_clear_private_2(folio)
739
740#endif