path: root/fs/btrfs/fiemap.c

// SPDX-License-Identifier: GPL-2.0

#include "backref.h"
#include "btrfs_inode.h"
#include "fiemap.h"
#include "file.h"
#include "file-item.h"

struct btrfs_fiemap_entry {
	u64 offset;
	u64 phys;
	u64 len;
	u32 flags;
};

/*
 * Indicate the caller of emit_fiemap_extent() that it needs to unlock the file
 * range from the inode's io tree, unlock the subvolume tree search path, flush
 * the fiemap cache and relock the file range and research the subvolume tree.
 * The value here is something negative that can't be confused with a valid
 * errno value and different from 1 because that's also a return value from
 * fiemap_fill_next_extent() and also it's often used to mean some btree search
 * did not find a key, so make it some distinct negative value.
 */
#define BTRFS_FIEMAP_FLUSH_CACHE (-(MAX_ERRNO + 1))

/*
 * Used to:
 *
 * - Cache the next entry to be emitted to the fiemap buffer, so that we can
 *   merge extents that are contiguous and can be grouped as a single one;
 *
 * - Store extents ready to be written to the fiemap buffer in an intermediary
 *   buffer. This intermediary buffer is to ensure that in case the fiemap
 *   buffer is memory mapped to the fiemap target file, we don't deadlock
 *   during btrfs_page_mkwrite(). This is because during fiemap we are locking
 *   an extent range in order to prevent races with delalloc flushing and
 *   ordered extent completion, which is needed in order to reliably detect
 *   delalloc in holes and prealloc extents. And this can lead to a deadlock
 *   if the fiemap buffer is memory mapped to the file we are running fiemap
 *   against (a silly, useless in practice scenario, but possible) because
 *   btrfs_page_mkwrite() will try to lock the same extent range.
 */
struct fiemap_cache {
	/* An array of ready fiemap entries. */
	struct btrfs_fiemap_entry *entries;
	/* Number of entries in the entries array. */
	int entries_size;
	/* Index of the next entry in the entries array to write to. */
	int entries_pos;
	/*
	 * Once the entries array is full, this indicates what's the offset for
	 * the next file extent item we must search for in the inode's subvolume
	 * tree after unlocking the extent range in the inode's io tree and
	 * releasing the search path.
	 */
	u64 next_search_offset;
	/*
	 * This matches struct fiemap_extent_info::fi_mapped_extents, we use it
	 * to count ourselves emitted extents and stop instead of relying on
	 * fiemap_fill_next_extent() because we buffer ready fiemap entries at
	 * the @entries array, and we want to stop as soon as we hit the max
	 * amount of extents to map, not just to save time but also to make the
	 * logic at extent_fiemap() simpler.
	 */
	unsigned int extents_mapped;
	/* Fields for the cached extent (unsubmitted, not ready, extent). */
	u64 offset;
	u64 phys;
	u64 len;
	u32 flags;
	bool cached;
};

static int flush_fiemap_cache(struct fiemap_extent_info *fieinfo,
			      struct fiemap_cache *cache)
{
	for (int i = 0; i < cache->entries_pos; i++) {
		struct btrfs_fiemap_entry *entry = &cache->entries[i];
		int ret;

		ret = fiemap_fill_next_extent(fieinfo, entry->offset,
					      entry->phys, entry->len,
					      entry->flags);
		/*
		 * Ignore 1 (reached max entries) because we keep track of that
		 * ourselves in emit_fiemap_extent().
		 */
		if (ret < 0)
			return ret;
	}
	cache->entries_pos = 0;

	return 0;
}

/*
 * Helper to submit fiemap extent.
 *
 * Will try to merge current fiemap extent specified by @offset, @phys,
 * @len and @flags with cached one.
 * And only when we fails to merge, cached one will be submitted as
 * fiemap extent.
 *
 * Return value is the same as fiemap_fill_next_extent().
 */
static int emit_fiemap_extent(struct fiemap_extent_info *fieinfo,
				struct fiemap_cache *cache,
				u64 offset, u64 phys, u64 len, u32 flags)
{
	struct btrfs_fiemap_entry *entry;
	u64 cache_end;

	/* Set at the end of extent_fiemap(). */
	ASSERT((flags & FIEMAP_EXTENT_LAST) == 0);

	if (!cache->cached)
		goto assign;

	/*
	 * When iterating the extents of the inode, at extent_fiemap(), we may
	 * find an extent that starts at an offset behind the end offset of the
	 * previous extent we processed. This happens if fiemap is called
	 * without FIEMAP_FLAG_SYNC and there are ordered extents completing
	 * after we had to unlock the file range, release the search path, emit
	 * the fiemap extents stored in the buffer (cache->entries array) and
	 * the lock the remainder of the range and re-search the btree.
	 *
	 * For example we are in leaf X processing its last item, which is the
	 * file extent item for file range [512K, 1M[, and after
	 * btrfs_next_leaf() releases the path, there's an ordered extent that
	 * completes for the file range [768K, 2M[, and that results in trimming
	 * the file extent item so that it now corresponds to the file range
	 * [512K, 768K[ and a new file extent item is inserted for the file
	 * range [768K, 2M[, which may end up as the last item of leaf X or as
	 * the first item of the next leaf - in either case btrfs_next_leaf()
	 * will leave us with a path pointing to the new extent item, for the
	 * file range [768K, 2M[, since that's the first key that follows the
	 * last one we processed. So in order not to report overlapping extents
	 * to user space, we trim the length of the previously cached extent and
	 * emit it.
	 *
	 * Upon calling btrfs_next_leaf() we may also find an extent with an
	 * offset smaller than or equals to cache->offset, and this happens
	 * when we had a hole or prealloc extent with several delalloc ranges in
	 * it, but after btrfs_next_leaf() released the path, delalloc was
	 * flushed and the resulting ordered extents were completed, so we can
	 * now have found a file extent item for an offset that is smaller than
	 * or equals to what we have in cache->offset. We deal with this as
	 * described below.
	 */
	cache_end = cache->offset + cache->len;
	if (cache_end > offset) {
		if (offset == cache->offset) {
			/*
			 * We cached a dealloc range (found in the io tree) for
			 * a hole or prealloc extent and we have now found a
			 * file extent item for the same offset. What we have
			 * now is more recent and up to date, so discard what
			 * we had in the cache and use what we have just found.
			 */
			goto assign;
		} else if (offset > cache->offset) {
			/*
			 * The extent range we previously found ends after the
			 * offset of the file extent item we found and that
			 * offset falls somewhere in the middle of that previous
			 * extent range. So adjust the range we previously found
			 * to end at the offset of the file extent item we have
			 * just found, since this extent is more up to date.
			 * Emit that adjusted range and cache the file extent
			 * item we have just found. This corresponds to the case
			 * where a previously found file extent item was split
			 * due to an ordered extent completing.
			 */
			cache->len = offset - cache->offset;
			goto emit;
		} else {
			const u64 range_end = offset + len;

			/*
			 * The offset of the file extent item we have just found
			 * is behind the cached offset. This means we were
			 * processing a hole or prealloc extent for which we
			 * have found delalloc ranges (in the io tree), so what
			 * we have in the cache is the last delalloc range we
			 * found while the file extent item we found can be
			 * either for a whole delalloc range we previously
			 * emitted or only a part of that range.
			 *
			 * We have two cases here:
			 *
			 * 1) The file extent item's range ends at or behind the
			 *    cached extent's end. In this case just ignore the
			 *    current file extent item because we don't want to
			 *    overlap with previous ranges that may have been
			 *    emitted already;
			 *
			 * 2) The file extent item starts behind the currently
			 *    cached extent but its end offset goes beyond the
			 *    end offset of the cached extent. We don't want to
			 *    overlap with a previous range that may have been
			 *    emitted already, so we emit the currently cached
			 *    extent and then partially store the current file
			 *    extent item's range in the cache, for the subrange
			 *    going the cached extent's end to the end of the
			 *    file extent item.
			 */
			if (range_end <= cache_end)
				return 0;

			if (!(flags & (FIEMAP_EXTENT_ENCODED | FIEMAP_EXTENT_DELALLOC)))
				phys += cache_end - offset;

			offset = cache_end;
			len = range_end - cache_end;
			goto emit;
		}
	}

	/*
	 * Only merges fiemap extents if
	 * 1) Their logical addresses are continuous
	 *
	 * 2) Their physical addresses are continuous
	 *    So truly compressed (physical size smaller than logical size)
	 *    extents won't get merged with each other
	 *
	 * 3) Share same flags
	 */
	if (cache->offset + cache->len  == offset &&
	    cache->phys + cache->len == phys  &&
	    cache->flags == flags) {
		cache->len += len;
		return 0;
	}

emit:
	/* Not mergeable, need to submit cached one */

	if (cache->entries_pos == cache->entries_size) {
		/*
		 * We will need to research for the end offset of the last
		 * stored extent and not from the current offset, because after
		 * unlocking the range and releasing the path, if there's a hole
		 * between that end offset and this current offset, a new extent
		 * may have been inserted due to a new write, so we don't want
		 * to miss it.
		 */
		entry = &cache->entries[cache->entries_size - 1];
		cache->next_search_offset = entry->offset + entry->len;
		cache->cached = false;

		return BTRFS_FIEMAP_FLUSH_CACHE;
	}

	entry = &cache->entries[cache->entries_pos];
	entry->offset = cache->offset;
	entry->phys = cache->phys;
	entry->len = cache->len;
	entry->flags = cache->flags;
	cache->entries_pos++;
	cache->extents_mapped++;

	if (cache->extents_mapped == fieinfo->fi_extents_max) {
		cache->cached = false;
		return 1;
	}
assign:
	cache->cached = true;
	cache->offset = offset;
	cache->phys = phys;