fs/btrfs/tree-log.c

13 #include "tree-log.h"
24 #include "extent-tree.h"
25 #include "root-tree.h"
30 #include "tree-checker.h"
84  * directory tree.  The inode link count fixup code takes care of the
89  * stages for the tree walking.  The first
119  * tree logging is a special write ahead log used to make sure that
120  * fsyncs and O_SYNCs can happen without doing full tree commits.
122  * Full tree commits are expensive because they require commonly
124  * extent tree an 4x-6x higher write load than ext3.
126  * Instead of doing a tree commit on every fsync, we use the
129  * a special tree (one per subvolume root), that tree is written to disk
132  * After a crash, items are copied out of the log-tree back into the
133  * subvolume tree.  Any file data extents found are recorded in the extent
134  * allocation tree, and the log-tree freed.
136  * The log tree is read three times, once to pin down all the extents it is
137  * using in ram and once, once to create all the inodes logged in the tree
142  * start a sub transaction and setup the log tree
143  * this increments the log tree writer count to make the people
144  * syncing the tree wait for us to finish
157 	 * First check if the log root tree was already created. If not, create
269  * indicate we're done making changes to the log tree
282  * processing the log tree.  The stage field tells us which part
283  * of the log tree processing we are currently doing.  The others
288 	 * at transaction commit time while freeing a log tree
314 	 * tree.  Note the extent_buffer might not be up to date when it is
360  * Item overwrite used by replay and tree logging.  eb, slot and key all refer
363  * root is the tree we are copying into, and path is a scratch
367  * If the key is already in the destination tree the existing item is
389 	 * fs/subvolume tree. In case we ever need to support a log root, then
391 	 * the leaf before writing into the log tree. See the comments at
399 	/* Look for the key in the destination tree. */
436 		 * us from cowing blocks in the destination tree and doing
492 	/* try to insert the key into the destination tree */
514 	 * was logged as zero.  This is done when the tree logging code
519 	 * state of the tree found in the subvolume, and i_size is modified
538 			 * tree, otherwise we would be throwing valid data away.
613  * extents in the log tree have not been allocated out of the extent
614  * tree yet.  So, this completes the allocation, taking a reference
616  * if it isn't in the extent allocation tree yet.
739 		 * but modifying extent tree all by ourselves.
741 		 * as the owner of the file extent changed from log tree
742 		 * (doesn't affect qgroup) to fs/file tree(affects qgroup)
757 			 * allocation tree?  If so, just add a reference
779 				 * allocation tree
814 			 * below, we can get 2 csum items in the csum tree that
827 			 * that starts at disk byte 12845056, and the log tree
834 			 * csum tree gets the following csum item:
842 			 * csum items in our csum tree that overlap each other:
911 	 * fs/subvolume tree. So after an unlink we must run delayed items, so
1009  * helper function to check a log tree for a named back reference in
1257  * Take an inode reference item from the log tree and iterate all names from the
1258  * inode reference item in the subvolume tree with the same key (if it exists).
1259  * For any name that is not in the inode reference item from the log tree, do a
1342  * replay one inode back reference item found in the log tree.
1343  * eb, slot and key refer to the buffer and key found in the log tree.
1464 	 * Before we overwrite the inode reference item in the subvolume tree
1465 	 * with the item from the log tree, we must unlink all names from the
1466 	 * parent directory that are in the subvolume's tree inode reference
1467 	 * item, otherwise we end up with an inconsistent subvolume tree where
1811  * fix up tree.
2065 	/* check the next slot in the tree to see if it is a valid item */
2231 				/* Doesn't exist in log tree, so delete it. */
2374  * the process_func used to replay items from the log tree.  This
2542  * Correctly adjust the reserved bytes occupied by a log tree extent buffer
2702  * drop the reference count on the tree rooted at 'snap'.  This traverses
2703  * the tree freeing any blocks that have a ref count of zero after being
2761  * in the tree of log roots
2894  * Sends a given tree log down to the disk and updates the super blocks to
2937 	/* wait for previous tree log sync to complete */
2974 	 *  commit, writes a dirty extent in this tree-log commit. This
3010 	 * IO has been started, blocks of the log tree have WRITTEN flag set
3083 	 * now that we've moved on to the tree of log tree roots,
3224 			 * We weren't able to traverse the entire log tree, the
3226 			 * extent buffer of the tree, due to a previous writeback
3233 			 * Some extent buffers of the log tree may still be dirty
3235 			 * have updates to a log tree without syncing a log tree,
3260  * free all the extents used by the tree log.  This should be called
3312 	 * If no log tree was created for this root in this transaction, then
3316 	 * a log tree gets created after this.
3324 	 * We have a log tree and the inode's logged_trans is 0. We can't tell
3381 	 * the current transacion's ID, to avoid future tree searches as long as
3389 	 * not skip checking if dir index keys found in modified subvolume tree
3391 	 * to insert duplicate dir index keys in the log tree. This must be done
3549 	 * directory and have concurrent insertions in the subvolume's tree for
3710 	 * clone before modifying the log tree. See the comment at copy_items()
3805  * directory.  This also creates the range items in the log tree required
3992  * is to avoid lookups in the log tree every time we try to insert a dir index
4058  * key in the range logged that is not present in the log tree, then it means
4142 		 * found the last guy with the objectid in this tree.
4220 	 * inode item in subvolume tree as needed (see overwrite_item()).
4242 	 * it exists in the log tree. For performance reasons, in this case use
4309 	 * This would leave csum items in the log tree that cover the same range
4310 	 * and break the searches for checksums in the log tree, resulting in
4311 	 * some checksums missing in the fs/subvolume tree. So just delete (or
4346 	 * tree, to insert items from the subvolume tree or insert csum items,
4347 	 * while holding a read lock on a leaf from the subvolume tree, which
4348 	 * creates a nasty lock dependency when COWing log tree nodes/leaves:
4350 	 * 1) Modifying the log tree triggers an extent buffer allocation while
4351 	 *    holding a write lock on a parent extent buffer from the log tree.
4357 	 * 2) Allocating a metadata extent for a log tree can trigger the async
4362 	 *    buffers of a subvolume tree - all this while holding a write lock
4363 	 *    on the parent extent buffer in the log tree.
4440 		 * checksums are already accessible from the committed csum tree,
4726 	 * but also adds significant contention in a log tree, since log trees
4765  * subvolume's root instead of iterating the inode's extent map tree because
4768  * are not in the extent map tree's list of modified extents.
4866 			 * and leading to duplicate keys in the log tree.
4905 	struct extent_map_tree *tree = &inode->extent_tree;
4909 	write_lock(&tree->lock);
4911 	list_for_each_entry_safe(em, n, &tree->modified_extents, list) {
4920 			list_del_init(&tree->modified_extents);
4957 		write_unlock(&tree->lock);
4960 		write_lock(&tree->lock);
4965 	write_unlock(&tree->lock);
5040  * in the log tree and exists in the fs/subvol tree, we delete it. This is
5425  *    BTRFS_DIR_INDEX_KEY) are added to fs/subvol tree and the logged inode item
5987 		 * not holding locks on any tree.
6062 	/* We are adding dir index items to the log tree. */
6067 	 * to the log tree. However just after we collected them, they may have
6069 	 * could have copied them from the subvolume tree to the log tree.
6291 	 * We are deleting dir index items from the log tree or adding range
6309  * items instead of the subvolume tree.
6375 /* log a single inode in the tree log.
6376  * At least one parent directory for this inode must exist in the tree
6380  * to the log tree.  An extra reference is taken on any extents in this
6382  * blocks that have been removed from the tree.
6579 	 * before iterating the subvolume tree, so that we don't miss any new
6581 	 * iterating the subvolume tree.
6961 	 * need to iterate the fs/subvolume tree.
7013 		 * tree, so it releases the path as needed to avoid deadlocks.
7364  * Must be called before the unlink operations (updates to the subvolume tree,
7391 	 * tree with btrfs_del_dir_entries_in_log() or with
7421  * that after replaying the log tree of the parent directory's root we will not
7422  * see the snapshot anymore and at log replay time we will not see any log tree
7424  * it after replaying the log tree of the parent directory (which would replay
7428  * parent root and tree of tree roots trees, etc) are done.