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