Lines Matching defs:tree
13 #include "tree-log.h"
16 #include "print-tree.h"
76 * directory tree. The inode link count fixup code takes care of the
81 * stages for the tree walking. The first
110 * tree logging is a special write ahead log used to make sure that
111 * fsyncs and O_SYNCs can happen without doing full tree commits.
113 * Full tree commits are expensive because they require commonly
115 * extent tree an 4x-6x higher write load than ext3.
117 * Instead of doing a tree commit on every fsync, we use the
120 * a special tree (one per subvolume root), that tree is written to disk
123 * After a crash, items are copied out of the log-tree back into the
124 * subvolume tree. Any file data extents found are recorded in the extent
125 * allocation tree, and the log-tree freed.
127 * The log tree is read three times, once to pin down all the extents it is
128 * using in ram and once, once to create all the inodes logged in the tree
133 * start a sub transaction and setup the log tree
134 * this increments the log tree writer count to make the people
135 * syncing the tree wait for us to finish
220 * indicate we're done making changes to the log tree
245 * processing the log tree. The stage field tells us which part
246 * of the log tree processing we are currently doing. The others
251 * at transaction commit time while freeing a log tree
256 * while flushing the log tree to disk during a sync
261 * while flushing the log tree to disk for a sync
287 * tree. Note the extent_buffer might not be up to date when it is
331 * Item overwrite used by replay and tree logging. eb, slot and key all refer
334 * root is the tree we are copying into, and path is a scratch
338 * If the key is already in the destination tree the existing item is
365 /* look for the key in the destination tree */
402 * us from cowing blocks in the destination tree and doing
458 /* try to insert the key into the destination tree */
480 * was logged as zero. This is done when the tree logging code
485 * state of the tree found in the subvolume, and i_size is modified
504 * tree, otherwise we would be throwing valid data away.
565 * extents in the log tree have not been allocated out of the extent
566 * tree yet. So, this completes the allocation, taking a reference
568 * if it isn't in the extent allocation tree yet.
687 * but modifying extent tree all by ourselves.
689 * as the owner of the file extent changed from log tree
690 * (doesn't affect qgroup) to fs/file tree(affects qgroup)
707 * allocation tree? If so, just add a reference
726 * allocation tree
760 * below, we can get 2 csum items in the csum tree that
773 * that starts at disk byte 12845056, and the log tree
780 * csum tree gets the following csum item:
788 * csum items in our csum tree that overlap each other:
942 * helper function to check a log tree for a named back reference in
1067 * NOTE: we have searched root tree and checked the
1221 * Take an inode reference item from the log tree and iterate all names from the
1222 * inode reference item in the subvolume tree with the same key (if it exists).
1223 * For any name that is not in the inode reference item from the log tree, do a
1293 * check the subvolume tree. So after an unlink we must
1419 * replay one inode back reference item found in the log tree.
1420 * eb, slot and key refer to the buffer and key found in the log tree.
1553 * not, we check the subvolume tree. So after an
1584 * Before we overwrite the inode reference item in the subvolume tree
1585 * with the item from the log tree, we must unlink all names from the
1586 * parent directory that are in the subvolume's tree inode reference
1587 * item, otherwise we end up with an inconsistent subvolume tree where
1913 * fix up tree.
2209 /* check the next slot in the tree to see if it is a valid item */
2402 /* Doesn't exist in log tree, so delete it. */
2552 * the process_func used to replay items from the log tree. This
2708 * Correctly adjust the reserved bytes occupied by a log tree extent buffer
2877 * drop the reference count on the tree rooted at 'snap'. This traverses
2878 * the tree freeing any blocks that have a ref count of zero after being
2956 * in the tree of log roots
3048 * btrfs_sync_log does sends a given tree log down to the disk and
3090 /* wait for previous tree log sync to complete */
3153 * IO has been started, blocks of the log tree have WRITTEN flag set
3219 * now that we've moved on to the tree of log tree roots,
3331 * free all the extents used by the tree log. This should be called
3575 * directory. This also creates the range items in the log tree required
3779 * key in the range logged that is not present in the log tree, then it means
3863 * found the last guy with the objectid in this tree.
3978 * This would leave csum items in the log tree that cover the same range
3979 * and break the searches for checksums in the log tree, resulting in
3980 * some checksums missing in the fs/subvolume tree. So just delete (or
4104 * log tree while trying to change the log tree.
4321 * subvolume's root instead of iterating the inode's extent map tree because
4324 * are not in the extent map tree's list of modified extents.
4421 * and leading to duplicate keys in the log tree.
4465 struct extent_map_tree *tree = &inode->extent_tree;
4472 write_lock(&tree->lock);
4475 list_for_each_entry_safe(em, n, &tree->modified_extents, list) {
4484 list_del_init(&tree->modified_extents);
4516 clear_em_logging(tree, em);
4521 write_unlock(&tree->lock);
4524 write_lock(&tree->lock);
4525 clear_em_logging(tree, em);
4529 write_unlock(&tree->lock);
4605 * in the log tree and exists in the fs/subvol tree, we delete it. This is
5246 /* log a single inode in the tree log.
5247 * At least one parent directory for this inode must exist in the tree
5251 * to the log tree. An extra reference is taken on any extents in this
5253 * blocks that have been removed from the tree.
5308 * all directory indexes hit the fs/subvolume tree so we can find them
5313 * tree so copy_inode_items_to_log() / copy_items() can find it and copy
5314 * it to the log tree. For a non full sync, we always log the inode item
5643 * BTRFS_DIR_INDEX_KEY are added to fs/subvol tree and the logged inode item
5649 * name is added to the fs/subvol tree with both the dir_item and dir_index
5653 * item of the fs/subvol tree (see overwrite_item()).
6023 * need to iterate the fs/subvolume tree.
6075 * tree, so it releases the path as needed to avoid deadlocks.
6299 "Failed to pin buffers while recovering log root tree.");
6313 "Couldn't find tree log root.");
6331 "Couldn't read tree log root.");
6360 "Couldn't read target root for tree log recovery.");
6444 * Must be called before the unlink operations (updates to the subvolume tree,
6501 * that after replaying the log tree of the parent directory's root we will not
6502 * see the snapshot anymore and at log replay time we will not see any log tree
6504 * it after replaying the log tree of the parent directory (which would replay
6508 * parent root and tree of tree roots trees, etc) are done.