fs/btrfs/inode.c - platform/external/u-boot - Gitiles

 // SPDX-License-Identifier: GPL-2.0+
 /*
  * BTRFS filesystem implementation for U-Boot
  *
  * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
  */

 #include <linux/kernel.h>
 #include <malloc.h>
 #include <memalign.h>
 #include "btrfs.h"
 #include "disk-io.h"
 #include "volumes.h"

 /*
  * Read the content of symlink inode @ino of @root, into @target.
  * NOTE: @target will not be \0 termiated, caller should handle it properly.
  *
  * Return the number of read data.
  * Return <0 for error.
  */
 int btrfs_readlink(struct btrfs_root *root, u64 ino, char *target)
 {
 	struct btrfs_path path;
 	struct btrfs_key key;
 	struct btrfs_file_extent_item *fi;
 	int ret;

 	key.objectid = ino;
 	key.type = BTRFS_EXTENT_DATA_KEY;
 	key.offset = 0;
 	btrfs_init_path(&path);

 	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 	if (ret < 0)
 		return ret;
 	if (ret > 0) {
 		ret = -ENOENT;
 		goto out;
 	}
 	fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
 			    struct btrfs_file_extent_item);
 	if (btrfs_file_extent_type(path.nodes[0], fi) !=
 	    BTRFS_FILE_EXTENT_INLINE) {
 		ret = -EUCLEAN;
 		error("Extent for symlink %llu must be INLINE type!", ino);
 		goto out;
 	}
 	if (btrfs_file_extent_compression(path.nodes[0], fi) !=
 	    BTRFS_COMPRESS_NONE) {
 		ret = -EUCLEAN;
 		error("Extent for symlink %llu must not be compressed!", ino);
 		goto out;
 	}
 	if (btrfs_file_extent_ram_bytes(path.nodes[0], fi) >=
 	    root->fs_info->sectorsize) {
 		ret = -EUCLEAN;
 		error("Symlink %llu extent data too large (%llu)!\n",
 			ino, btrfs_file_extent_ram_bytes(path.nodes[0], fi));
 		goto out;
 	}
 	read_extent_buffer(path.nodes[0], target,
 			btrfs_file_extent_inline_start(fi),
 			btrfs_file_extent_ram_bytes(path.nodes[0], fi));
 	ret = btrfs_file_extent_ram_bytes(path.nodes[0], fi);
 out:
 	btrfs_release_path(&path);
 	return ret;
 }

 static int lookup_root_ref(struct btrfs_fs_info *fs_info,
 			   u64 rootid, u64 *root_ret, u64 *dir_ret)
 {
 	struct btrfs_root *root = fs_info->tree_root;
 	struct btrfs_root_ref *root_ref;
 	struct btrfs_path path;
 	struct btrfs_key key;
 	int ret;

 	btrfs_init_path(&path);
 	key.objectid = rootid;
 	key.type = BTRFS_ROOT_BACKREF_KEY;
 	key.offset = (u64)-1;

 	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 	if (ret < 0)
 		return ret;
 	/* Should not happen */
 	if (ret == 0) {
 		ret = -EUCLEAN;
 		goto out;
 	}
 	ret = btrfs_previous_item(root, &path, rootid, BTRFS_ROOT_BACKREF_KEY);
 	if (ret < 0)
 		goto out;
 	if (ret > 0) {
 		ret = -ENOENT;
 		goto out;
 	}
 	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 	root_ref = btrfs_item_ptr(path.nodes[0], path.slots[0],
 				  struct btrfs_root_ref);
 	*root_ret = key.offset;
 	*dir_ret = btrfs_root_ref_dirid(path.nodes[0], root_ref);
 out:
 	btrfs_release_path(&path);
 	return ret;
 }

 /*
  * To get the parent inode of @ino of @root.
  *
  * @root_ret and @ino_ret will be filled.
  *
  * NOTE: This function is not reliable. It can only get one parent inode.
  * The get the proper parent inode, we need a full VFS inodes stack to
  * resolve properly.
  */
 static int get_parent_inode(struct btrfs_root *root, u64 ino,
 			    struct btrfs_root **root_ret, u64 *ino_ret)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct btrfs_path path;
 	struct btrfs_key key;
 	int ret;

 	if (ino == BTRFS_FIRST_FREE_OBJECTID) {
 		u64 parent_root = -1;

 		/* It's top level already, no more parent */
 		if (root->root_key.objectid == BTRFS_FS_TREE_OBJECTID) {
 			*root_ret = fs_info->fs_root;
 			*ino_ret = BTRFS_FIRST_FREE_OBJECTID;
 			return 0;
 		}

 		ret = lookup_root_ref(fs_info, root->root_key.objectid,
 				      &parent_root, ino_ret);
 		if (ret < 0)
 			return ret;

 		key.objectid = parent_root;
 		key.type = BTRFS_ROOT_ITEM_KEY;
 		key.offset = (u64)-1;
 		*root_ret = btrfs_read_fs_root(fs_info, &key);
 		if (IS_ERR(*root_ret))
 			return PTR_ERR(*root_ret);

 		return 0;
 	}

 	btrfs_init_path(&path);
 	key.objectid = ino;
 	key.type = BTRFS_INODE_REF_KEY;
 	key.offset = (u64)-1;

 	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 	if (ret < 0)
 		return ret;
 	/* Should not happen */
 	if (ret == 0) {
 		ret = -EUCLEAN;
 		goto out;
 	}
 	ret = btrfs_previous_item(root, &path, ino, BTRFS_INODE_REF_KEY);
 	if (ret < 0)
 		goto out;
 	if (ret > 0) {
 		ret = -ENOENT;
 		goto out;
 	}
 	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 	*root_ret = root;
 	*ino_ret = key.offset;
 out:
 	btrfs_release_path(&path);
 	return ret;
 }

 static inline int next_length(const char *path)
 {
 	int res = 0;
 	while (*path != '\0' && *path != '/') {
 		++res;
 		++path;
 		if (res > BTRFS_NAME_LEN)
 			break;
 	}
 	return res;
 }

 static inline const char *skip_current_directories(const char *cur)
 {
 	while (1) {
 		if (cur[0] == '/')
 			++cur;
 		else if (cur[0] == '.' && cur[1] == '/')
 			cur += 2;
 		else
 			break;
 	}

 	return cur;
 }

 /*
  * Resolve one filename of @ino of @root.
  *
  * key_ret:	The child key (either INODE_ITEM or ROOT_ITEM type)
  * type_ret:	BTRFS_FT_* of the child inode.
  *
  * Return 0 with above members filled.
  * Return <0 for error.
  */
 static int resolve_one_filename(struct btrfs_root *root, u64 ino,
 				const char *name, int namelen,
 				struct btrfs_key *key_ret, u8 *type_ret)
 {
 	struct btrfs_dir_item *dir_item;
 	struct btrfs_path path;
 	int ret = 0;

 	btrfs_init_path(&path);

 	dir_item = btrfs_lookup_dir_item(NULL, root, &path, ino, name,
 					 namelen, 0);
 	if (IS_ERR(dir_item)) {
 		ret = PTR_ERR(dir_item);
 		goto out;
 	}

 	btrfs_dir_item_key_to_cpu(path.nodes[0], dir_item, key_ret);
 	*type_ret = btrfs_dir_type(path.nodes[0], dir_item);
 out:
 	btrfs_release_path(&path);
 	return ret;
 }

 /*
  * Resolve a full path @filename. The start point is @ino of @root.
  *
  * The result will be filled into @root_ret, @ino_ret and @type_ret.
  */
 int btrfs_lookup_path(struct btrfs_root *root, u64 ino, const char *filename,
 			struct btrfs_root **root_ret, u64 *ino_ret,
 			u8 *type_ret, int symlink_limit)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct btrfs_root *next_root;
 	struct btrfs_key key;
 	const char *cur = filename;
 	u64 next_ino;
 	u8 next_type;
 	u8 type = BTRFS_FT_UNKNOWN;
 	int len;
 	int ret = 0;

 	/* If the path is absolute path, also search from fs root */
 	if (*cur == '/') {
 		root = fs_info->fs_root;
 		ino = btrfs_root_dirid(&root->root_item);
 		type = BTRFS_FT_DIR;
 	}

 	while (*cur != '\0') {
 		cur = skip_current_directories(cur);

 		len = next_length(cur);
 		if (len > BTRFS_NAME_LEN) {
 			error("%s: Name too long at \"%.*s\"", __func__,
 			       BTRFS_NAME_LEN, cur);
 			return -ENAMETOOLONG;
 		}

 		if (len == 1 && cur[0] == '.')
 			break;

 		if (len == 2 && cur[0] == '.' && cur[1] == '.') {
 			/* Go one level up */
 			ret = get_parent_inode(root, ino, &next_root, &next_ino);
 			if (ret < 0)
 				return ret;
 			root = next_root;
 			ino = next_ino;
 			goto next;
 		}

 		if (!*cur)
 			break;

 		ret = resolve_one_filename(root, ino, cur, len, &key, &type);
 		if (ret < 0)
 			return ret;

 		if (key.type == BTRFS_ROOT_ITEM_KEY) {
 			/* Child inode is a subvolume */

 			next_root = btrfs_read_fs_root(fs_info, &key);
 			if (IS_ERR(next_root))
 				return PTR_ERR(next_root);
 			root = next_root;
 			ino = btrfs_root_dirid(&root->root_item);
 		} else if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0) {
 			/* Child inode is a symlink */

 			char *target;

 			if (symlink_limit == 0) {
 				error("%s: Too much symlinks!", __func__);
 				return -EMLINK;
 			}
 			target = malloc(fs_info->sectorsize);
 			if (!target)
 				return -ENOMEM;
 			ret = btrfs_readlink(root, key.objectid, target);
 			if (ret < 0) {
 				free(target);
 				return ret;
 			}
 			target[ret] = '\0';

 			ret = btrfs_lookup_path(root, ino, target, &next_root,
 						&next_ino, &next_type,
 						symlink_limit);
 			if (ret < 0)
 				return ret;
 			root = next_root;
 			ino = next_ino;
 			type = next_type;
 		} else {
 			/* Child inode is an inode */
 			ino = key.objectid;
 		}
 next:
 		cur += len;
 	}

 	/* We haven't found anything, but still get no error? */
 	if (type == BTRFS_FT_UNKNOWN && !ret)
 		ret = -EUCLEAN;

 	if (!ret) {
 		*root_ret = root;
 		*ino_ret = ino;
 		*type_ret = type;
 	}

 	return ret;
 }

 /*
  * Read out inline extent.
  *
  * Since inline extent should only exist for offset 0, no need for extra
  * parameters.
  * Truncating should be handled by the caller.
  *
  * Return the number of bytes read.
  * Return <0 for error.
  */
 int btrfs_read_extent_inline(struct btrfs_path *path,
 			     struct btrfs_file_extent_item *fi, char *dest)
 {
 	struct extent_buffer *leaf = path->nodes[0];
 	int slot = path->slots[0];
 	char *cbuf = NULL;
 	char *dbuf = NULL;
 	u32 csize;
 	u32 dsize;
 	int ret;

 	csize = btrfs_file_extent_inline_item_len(leaf, btrfs_item_nr(slot));
 	if (btrfs_file_extent_compression(leaf, fi) == BTRFS_COMPRESS_NONE) {
 		/* Uncompressed, just read it out */
 		read_extent_buffer(leaf, dest,
 				btrfs_file_extent_inline_start(fi),
 				csize);
 		return csize;
 	}

 	/* Compressed extent, prepare the compressed and data buffer */
 	dsize = btrfs_file_extent_ram_bytes(leaf, fi);
 	cbuf = malloc(csize);
 	dbuf = malloc(dsize);
 	if (!cbuf || !dbuf) {
 		ret = -ENOMEM;
 		goto out;
 	}
 	read_extent_buffer(leaf, cbuf, btrfs_file_extent_inline_start(fi),
 			   csize);
 	ret = btrfs_decompress(btrfs_file_extent_compression(leaf, fi),
 			       cbuf, csize, dbuf, dsize);
 	if (ret < 0 || ret != dsize) {
 		ret = -EIO;
 		goto out;
 	}
 	memcpy(dest, dbuf, dsize);
 	ret = dsize;
 out:
 	free(cbuf);
 	free(dbuf);
 	return ret;
 }

 /*
  * Read out regular extent.
  *
  * Truncating should be handled by the caller.
  *
  * @offset and @len should not cross the extent boundary.
  * Return the number of bytes read.
  * Return <0 for error.
  */
 int btrfs_read_extent_reg(struct btrfs_path *path,
 			  struct btrfs_file_extent_item *fi, u64 offset,
 			  int len, char *dest)
 {
 	struct extent_buffer *leaf = path->nodes[0];
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	struct btrfs_key key;
 	u64 extent_num_bytes;
 	u64 disk_bytenr;
 	u64 read;
 	char *cbuf = NULL;
 	char *dbuf = NULL;
 	u32 csize;
 	u32 dsize;
 	bool finished = false;
 	int num_copies;
 	int i;
 	int slot = path->slots[0];
 	int ret;

 	btrfs_item_key_to_cpu(leaf, &key, slot);
 	extent_num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
 	ASSERT(IS_ALIGNED(offset, fs_info->sectorsize) &&
 	       IS_ALIGNED(len, fs_info->sectorsize));
 	ASSERT(offset >= key.offset &&
 	       offset + len <= key.offset + extent_num_bytes);

 	/* Preallocated or hole , fill @dest with zero */
 	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_PREALLOC ||
 	    btrfs_file_extent_disk_bytenr(leaf, fi) == 0) {
 		memset(dest, 0, len);
 		return len;
 	}

 	if (btrfs_file_extent_compression(leaf, fi) == BTRFS_COMPRESS_NONE) {
 		u64 logical;

 		logical = btrfs_file_extent_disk_bytenr(leaf, fi) +
 			  btrfs_file_extent_offset(leaf, fi) +
 			  offset - key.offset;
 		read = len;

 		num_copies = btrfs_num_copies(fs_info, logical, len);
 		for (i = 1; i <= num_copies; i++) {
 			ret = read_extent_data(fs_info, dest, logical, &read, i);
 			if (ret < 0 || read != len)
 				continue;
 			finished = true;
 			break;
 		}
 		if (!finished)
 			return -EIO;
 		return len;
 	}

 	csize = btrfs_file_extent_disk_num_bytes(leaf, fi);
 	dsize = btrfs_file_extent_ram_bytes(leaf, fi);
 	disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
 	num_copies = btrfs_num_copies(fs_info, disk_bytenr, csize);

 	cbuf = malloc_cache_aligned(csize);
 	dbuf = malloc_cache_aligned(dsize);
 	if (!cbuf || !dbuf) {
 		ret = -ENOMEM;
 		goto out;
 	}
 	/* For compressed extent, we must read the whole on-disk extent */
 	for (i = 1; i <= num_copies; i++) {
 		read = csize;
 		ret = read_extent_data(fs_info, cbuf, disk_bytenr,
 				       &read, i);
 		if (ret < 0 || read != csize)
 			continue;
 		finished = true;
 		break;
 	}
 	if (!finished) {
 		ret = -EIO;
 		goto out;
 	}

 	ret = btrfs_decompress(btrfs_file_extent_compression(leaf, fi), cbuf,
 			       csize, dbuf, dsize);
 	if (ret != dsize) {
 		ret = -EIO;
 		goto out;
 	}
 	/* Then copy the needed part */
 	memcpy(dest, dbuf + btrfs_file_extent_offset(leaf, fi), len);
 	ret = len;
 out:
 	free(cbuf);
 	free(dbuf);
 	return ret;
 }

 /*
  * Get the first file extent that covers bytenr @file_offset.
  *
  * @file_offset must be aligned to sectorsize.
  *
  * return 0 for found, and path points to the file extent.
  * return >0 for not found, and fill @next_offset.
  * @next_offset can be 0 if there is no next file extent.
  * return <0 for error.
  */
 static int lookup_data_extent(struct btrfs_root *root, struct btrfs_path *path,
 			      u64 ino, u64 file_offset, u64 *next_offset)
 {
 	struct btrfs_key key;
 	struct btrfs_file_extent_item *fi;
 	u8 extent_type;
 	int ret = 0;

 	ASSERT(IS_ALIGNED(file_offset, root->fs_info->sectorsize));
 	key.objectid = ino;
 	key.type = BTRFS_EXTENT_DATA_KEY;
 	key.offset = file_offset;

 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 	/* Error or we're already at the file extent */
 	if (ret <= 0)
 		return ret;
 	if (ret > 0) {
 		/* Check previous file extent */
 		ret = btrfs_previous_item(root, path, ino,
 					  BTRFS_EXTENT_DATA_KEY);
 		if (ret < 0)
 			return ret;
 		if (ret > 0)
 			goto check_next;
 	}
 	/* Now the key.offset must be smaller than @file_offset */
 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 	if (key.objectid != ino ||
 	    key.type != BTRFS_EXTENT_DATA_KEY)
 		goto check_next;

 	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 			    struct btrfs_file_extent_item);
 	extent_type = btrfs_file_extent_type(path->nodes[0], fi);
 	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
 		if (file_offset == 0)
 			return 0;
 		/* Inline extent should be the only extent, no next extent. */
 		*next_offset = 0;
 		return 1;
 	}

 	/* This file extent covers @file_offset */
 	if (key.offset <= file_offset && key.offset +
 	    btrfs_file_extent_num_bytes(path->nodes[0], fi) > file_offset)
 		return 0;
 check_next:
 	ret = btrfs_next_item(root, path);
 	if (ret < 0)
 		return ret;
 	if (ret > 0) {
 		*next_offset = 0;
 		return 1;
 	}

 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 			    struct btrfs_file_extent_item);
 	/* Next next data extent */
 	if (key.objectid != ino ||
 	    key.type != BTRFS_EXTENT_DATA_KEY) {
 		*next_offset = 0;
 		return 1;
 	}
 	/* Current file extent already beyond @file_offset */
 	if (key.offset > file_offset) {
 		*next_offset = key.offset;
 		return 1;
 	}
 	/* This file extent covers @file_offset */
 	if (key.offset <= file_offset && key.offset +
 	    btrfs_file_extent_num_bytes(path->nodes[0], fi) > file_offset)
 		return 0;
 	/* This file extent ends before @file_offset, check next */
 	ret = btrfs_next_item(root, path);
 	if (ret < 0)
 		return ret;
 	if (ret > 0) {
 		*next_offset = 0;
 		return 1;
 	}
 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 	if (key.type != BTRFS_EXTENT_DATA_KEY || key.objectid != ino) {
 		*next_offset = 0;
 		return 1;
 	}
 	*next_offset = key.offset;
 	return 1;
 }

 static int read_and_truncate_page(struct btrfs_path *path,
 				  struct btrfs_file_extent_item *fi,
 				  int start, int len, char *dest)
 {
 	struct extent_buffer *leaf = path->nodes[0];
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	u64 aligned_start = round_down(start, fs_info->sectorsize);
 	u8 extent_type;
 	char *buf;
 	int page_off = start - aligned_start;
 	int page_len = fs_info->sectorsize - page_off;
 	int ret;

 	ASSERT(start + len <= aligned_start + fs_info->sectorsize);
 	buf = malloc_cache_aligned(fs_info->sectorsize);
 	if (!buf)
 		return -ENOMEM;

 	extent_type = btrfs_file_extent_type(leaf, fi);
 	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
 		ret = btrfs_read_extent_inline(path, fi, buf);
 		memcpy(dest, buf + page_off, min(page_len, ret));
 		free(buf);
 		return len;
 	}

 	ret = btrfs_read_extent_reg(path, fi,
 			round_down(start, fs_info->sectorsize),
 			fs_info->sectorsize, buf);
 	if (ret < 0) {
 		free(buf);
 		return ret;
 	}
 	memcpy(dest, buf + page_off, page_len);
 	free(buf);
 	return len;
 }

 int btrfs_file_read(struct btrfs_root *root, u64 ino, u64 file_offset, u64 len,
 		    char *dest)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct btrfs_file_extent_item *fi;
 	struct btrfs_path path;
 	struct btrfs_key key;
 	u64 aligned_start = round_down(file_offset, fs_info->sectorsize);
 	u64 aligned_end = round_down(file_offset + len, fs_info->sectorsize);
 	u64 next_offset;
 	u64 cur = aligned_start;
 	int ret = 0;

 	btrfs_init_path(&path);

 	/* Set the whole dest all zero, so we won't need to bother holes */
 	memset(dest, 0, len);

 	/* Read out the leading unaligned part */
 	if (aligned_start != file_offset) {
 		ret = lookup_data_extent(root, &path, ino, aligned_start,
 					 &next_offset);
 		if (ret < 0)
 			goto out;
 		if (ret == 0) {
 			/* Read the unaligned part out*/
 			fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
 					struct btrfs_file_extent_item);
 			ret = read_and_truncate_page(&path, fi, file_offset,
 					round_up(file_offset, fs_info->sectorsize) -
 					file_offset, dest);
 			if (ret < 0)
 				goto out;
 			cur += fs_info->sectorsize;
 		} else {
 			/* The whole file is a hole */
 			if (!next_offset) {
 				memset(dest, 0, len);
 				return len;
 			}
 			cur = next_offset;
 		}
 	}

 	/* Read the aligned part */
 	while (cur < aligned_end) {
 		u64 extent_num_bytes;
 		u8 type;

 		btrfs_release_path(&path);
 		ret = lookup_data_extent(root, &path, ino, cur, &next_offset);
 		if (ret < 0)
 			goto out;
 		if (ret > 0) {
 			/* No next, direct exit */
 			if (!next_offset) {
 				ret = 0;
 				goto out;
 			}
 		}
 		fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
 				    struct btrfs_file_extent_item);
 		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 		type = btrfs_file_extent_type(path.nodes[0], fi);
 		if (type == BTRFS_FILE_EXTENT_INLINE) {
 			ret = btrfs_read_extent_inline(&path, fi, dest);
 			goto out;
 		}
 		/* Skip holes, as we have zeroed the dest */
 		if (type == BTRFS_FILE_EXTENT_PREALLOC ||
 		    btrfs_file_extent_disk_bytenr(path.nodes[0], fi) == 0) {
 			cur = key.offset + btrfs_file_extent_num_bytes(
 					path.nodes[0], fi);
 			continue;
 		}

 		/* Read the remaining part of the extent */
 		extent_num_bytes = btrfs_file_extent_num_bytes(path.nodes[0],
 							       fi);
 		ret = btrfs_read_extent_reg(&path, fi, cur,
 				min(extent_num_bytes, aligned_end - cur),
 				dest + cur - file_offset);
 		if (ret < 0)
 			goto out;
 		cur += min(extent_num_bytes, aligned_end - cur);
 	}

 	/* Read the tailing unaligned part*/
 	if (file_offset + len != aligned_end) {
 		btrfs_release_path(&path);
 		ret = lookup_data_extent(root, &path, ino, aligned_end,
 					 &next_offset);
 		/* <0 is error, >0 means no extent */
 		if (ret)
 			goto out;
 		fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
 				    struct btrfs_file_extent_item);
 		ret = read_and_truncate_page(&path, fi, aligned_end,
 				file_offset + len - aligned_end,
 				dest + aligned_end - file_offset);
 	}
 out:
 	btrfs_release_path(&path);
 	if (ret < 0)
 		return ret;
 	return len;
 }
	// SPDX-License-Identifier: GPL-2.0+
	/*
	* BTRFS filesystem implementation for U-Boot
	*
	* 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
	*/

	#include <linux/kernel.h>
	#include <malloc.h>
	#include <memalign.h>
	#include "btrfs.h"
	#include "disk-io.h"
	#include "volumes.h"

	/*
	* Read the content of symlink inode @ino of @root, into @target.
	* NOTE: @target will not be \0 termiated, caller should handle it properly.
	*
	* Return the number of read data.
	* Return <0 for error.
	*/
	int btrfs_readlink(struct btrfs_root root, u64 ino, char target)
	{
	struct btrfs_path path;
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	int ret;

	key.objectid = ino;
	key.type = BTRFS_EXTENT_DATA_KEY;
	key.offset = 0;
	btrfs_init_path(&path);

	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
	if (ret < 0)
	return ret;
	if (ret > 0) {
	ret = -ENOENT;
	goto out;
	}
	fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
	struct btrfs_file_extent_item);
	if (btrfs_file_extent_type(path.nodes[0], fi) !=
	BTRFS_FILE_EXTENT_INLINE) {
	ret = -EUCLEAN;
	error("Extent for symlink %llu must be INLINE type!", ino);
	goto out;
	}
	if (btrfs_file_extent_compression(path.nodes[0], fi) !=
	BTRFS_COMPRESS_NONE) {
	ret = -EUCLEAN;
	error("Extent for symlink %llu must not be compressed!", ino);
	goto out;
	}
	if (btrfs_file_extent_ram_bytes(path.nodes[0], fi) >=
	root->fs_info->sectorsize) {
	ret = -EUCLEAN;
	error("Symlink %llu extent data too large (%llu)!\n",
	ino, btrfs_file_extent_ram_bytes(path.nodes[0], fi));
	goto out;
	}
	read_extent_buffer(path.nodes[0], target,
	btrfs_file_extent_inline_start(fi),
	btrfs_file_extent_ram_bytes(path.nodes[0], fi));
	ret = btrfs_file_extent_ram_bytes(path.nodes[0], fi);
	out:
	btrfs_release_path(&path);
	return ret;
	}

	static int lookup_root_ref(struct btrfs_fs_info *fs_info,
	u64 rootid, u64 root_ret, u64 dir_ret)
	{
	struct btrfs_root *root = fs_info->tree_root;
	struct btrfs_root_ref *root_ref;
	struct btrfs_path path;
	struct btrfs_key key;
	int ret;

	btrfs_init_path(&path);
	key.objectid = rootid;
	key.type = BTRFS_ROOT_BACKREF_KEY;
	key.offset = (u64)-1;

	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
	if (ret < 0)
	return ret;
	/* Should not happen */
	if (ret == 0) {
	ret = -EUCLEAN;
	goto out;
	}
	ret = btrfs_previous_item(root, &path, rootid, BTRFS_ROOT_BACKREF_KEY);
	if (ret < 0)
	goto out;
	if (ret > 0) {
	ret = -ENOENT;
	goto out;
	}
	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
	root_ref = btrfs_item_ptr(path.nodes[0], path.slots[0],
	struct btrfs_root_ref);
	*root_ret = key.offset;
	*dir_ret = btrfs_root_ref_dirid(path.nodes[0], root_ref);
	out:
	btrfs_release_path(&path);
	return ret;
	}

	/*
	* To get the parent inode of @ino of @root.
	*
	* @root_ret and @ino_ret will be filled.
	*
	* NOTE: This function is not reliable. It can only get one parent inode.
	* The get the proper parent inode, we need a full VFS inodes stack to
	* resolve properly.
	*/
	static int get_parent_inode(struct btrfs_root *root, u64 ino,
	struct btrfs_root *root_ret, u64 ino_ret)
	{
	struct btrfs_fs_info *fs_info = root->fs_info;
	struct btrfs_path path;
	struct btrfs_key key;
	int ret;

	if (ino == BTRFS_FIRST_FREE_OBJECTID) {
	u64 parent_root = -1;

	/* It's top level already, no more parent */
	if (root->root_key.objectid == BTRFS_FS_TREE_OBJECTID) {
	*root_ret = fs_info->fs_root;
	*ino_ret = BTRFS_FIRST_FREE_OBJECTID;
	return 0;
	}

	ret = lookup_root_ref(fs_info, root->root_key.objectid,
	&parent_root, ino_ret);
	if (ret < 0)
	return ret;

	key.objectid = parent_root;
	key.type = BTRFS_ROOT_ITEM_KEY;
	key.offset = (u64)-1;
	*root_ret = btrfs_read_fs_root(fs_info, &key);
	if (IS_ERR(*root_ret))
	return PTR_ERR(*root_ret);

	return 0;
	}

	btrfs_init_path(&path);
	key.objectid = ino;
	key.type = BTRFS_INODE_REF_KEY;
	key.offset = (u64)-1;

	ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
	if (ret < 0)
	return ret;
	/* Should not happen */
	if (ret == 0) {
	ret = -EUCLEAN;
	goto out;
	}
	ret = btrfs_previous_item(root, &path, ino, BTRFS_INODE_REF_KEY);
	if (ret < 0)
	goto out;
	if (ret > 0) {
	ret = -ENOENT;
	goto out;
	}
	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
	*root_ret = root;
	*ino_ret = key.offset;
	out:
	btrfs_release_path(&path);
	return ret;
	}

	static inline int next_length(const char *path)
	{
	int res = 0;
	while (path != '\0' && path != '/') {
	++res;
	++path;
	if (res > BTRFS_NAME_LEN)
	break;
	}
	return res;
	}

	static inline const char skip_current_directories(const char cur)
	{
	while (1) {
	if (cur[0] == '/')
	++cur;
	else if (cur[0] == '.' && cur[1] == '/')
	cur += 2;
	else
	break;
	}

	return cur;
	}

	/*
	* Resolve one filename of @ino of @root.
	*
	* key_ret: The child key (either INODE_ITEM or ROOT_ITEM type)
	* type_ret: BTRFS_FT_* of the child inode.
	*
	* Return 0 with above members filled.
	* Return <0 for error.
	*/
	static int resolve_one_filename(struct btrfs_root *root, u64 ino,
	const char *name, int namelen,
	struct btrfs_key key_ret, u8 type_ret)
	{
	struct btrfs_dir_item *dir_item;
	struct btrfs_path path;
	int ret = 0;

	btrfs_init_path(&path);

	dir_item = btrfs_lookup_dir_item(NULL, root, &path, ino, name,
	namelen, 0);
	if (IS_ERR(dir_item)) {
	ret = PTR_ERR(dir_item);
	goto out;
	}

	btrfs_dir_item_key_to_cpu(path.nodes[0], dir_item, key_ret);
	*type_ret = btrfs_dir_type(path.nodes[0], dir_item);
	out:
	btrfs_release_path(&path);
	return ret;
	}

	/*
	* Resolve a full path @filename. The start point is @ino of @root.
	*
	* The result will be filled into @root_ret, @ino_ret and @type_ret.
	*/
	int btrfs_lookup_path(struct btrfs_root root, u64 ino, const char filename,
	struct btrfs_root *root_ret, u64 ino_ret,
	u8 *type_ret, int symlink_limit)
	{
	struct btrfs_fs_info *fs_info = root->fs_info;
	struct btrfs_root *next_root;
	struct btrfs_key key;
	const char *cur = filename;
	u64 next_ino;
	u8 next_type;
	u8 type = BTRFS_FT_UNKNOWN;
	int len;
	int ret = 0;

	/* If the path is absolute path, also search from fs root */
	if (*cur == '/') {
	root = fs_info->fs_root;
	ino = btrfs_root_dirid(&root->root_item);
	type = BTRFS_FT_DIR;
	}

	while (*cur != '\0') {
	cur = skip_current_directories(cur);

	len = next_length(cur);
	if (len > BTRFS_NAME_LEN) {
	error("%s: Name too long at \"%.*s\"", __func__,
	BTRFS_NAME_LEN, cur);
	return -ENAMETOOLONG;
	}

	if (len == 1 && cur[0] == '.')
	break;

	if (len == 2 && cur[0] == '.' && cur[1] == '.') {
	/* Go one level up */
	ret = get_parent_inode(root, ino, &next_root, &next_ino);
	if (ret < 0)
	return ret;
	root = next_root;
	ino = next_ino;
	goto next;
	}

	if (!*cur)
	break;

	ret = resolve_one_filename(root, ino, cur, len, &key, &type);
	if (ret < 0)
	return ret;

	if (key.type == BTRFS_ROOT_ITEM_KEY) {
	/* Child inode is a subvolume */

	next_root = btrfs_read_fs_root(fs_info, &key);
	if (IS_ERR(next_root))
	return PTR_ERR(next_root);
	root = next_root;
	ino = btrfs_root_dirid(&root->root_item);
	} else if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0) {
	/* Child inode is a symlink */

	char *target;

	if (symlink_limit == 0) {
	error("%s: Too much symlinks!", __func__);
	return -EMLINK;
	}
	target = malloc(fs_info->sectorsize);
	if (!target)
	return -ENOMEM;
	ret = btrfs_readlink(root, key.objectid, target);
	if (ret < 0) {
	free(target);
	return ret;
	}
	target[ret] = '\0';

	ret = btrfs_lookup_path(root, ino, target, &next_root,
	&next_ino, &next_type,
	symlink_limit);
	if (ret < 0)
	return ret;
	root = next_root;
	ino = next_ino;
	type = next_type;
	} else {
	/* Child inode is an inode */
	ino = key.objectid;
	}
	next:
	cur += len;
	}

	/* We haven't found anything, but still get no error? */
	if (type == BTRFS_FT_UNKNOWN && !ret)
	ret = -EUCLEAN;

	if (!ret) {
	*root_ret = root;
	*ino_ret = ino;
	*type_ret = type;
	}

	return ret;
	}

	/*
	* Read out inline extent.
	*
	* Since inline extent should only exist for offset 0, no need for extra
	* parameters.
	* Truncating should be handled by the caller.
	*
	* Return the number of bytes read.
	* Return <0 for error.
	*/
	int btrfs_read_extent_inline(struct btrfs_path *path,
	struct btrfs_file_extent_item fi, char dest)
	{
	struct extent_buffer *leaf = path->nodes[0];
	int slot = path->slots[0];
	char *cbuf = NULL;
	char *dbuf = NULL;
	u32 csize;
	u32 dsize;
	int ret;

	csize = btrfs_file_extent_inline_item_len(leaf, btrfs_item_nr(slot));
	if (btrfs_file_extent_compression(leaf, fi) == BTRFS_COMPRESS_NONE) {
	/* Uncompressed, just read it out */
	read_extent_buffer(leaf, dest,
	btrfs_file_extent_inline_start(fi),
	csize);
	return csize;
	}

	/* Compressed extent, prepare the compressed and data buffer */
	dsize = btrfs_file_extent_ram_bytes(leaf, fi);
	cbuf = malloc(csize);
	dbuf = malloc(dsize);
	if (!cbuf \|\| !dbuf) {
	ret = -ENOMEM;
	goto out;
	}
	read_extent_buffer(leaf, cbuf, btrfs_file_extent_inline_start(fi),
	csize);
	ret = btrfs_decompress(btrfs_file_extent_compression(leaf, fi),
	cbuf, csize, dbuf, dsize);
	if (ret < 0 \|\| ret != dsize) {
	ret = -EIO;
	goto out;
	}
	memcpy(dest, dbuf, dsize);
	ret = dsize;
	out:
	free(cbuf);
	free(dbuf);
	return ret;
	}

	/*
	* Read out regular extent.
	*
	* Truncating should be handled by the caller.
	*
	* @offset and @len should not cross the extent boundary.
	* Return the number of bytes read.
	* Return <0 for error.
	*/
	int btrfs_read_extent_reg(struct btrfs_path *path,
	struct btrfs_file_extent_item *fi, u64 offset,
	int len, char *dest)
	{
	struct extent_buffer *leaf = path->nodes[0];
	struct btrfs_fs_info *fs_info = leaf->fs_info;
	struct btrfs_key key;
	u64 extent_num_bytes;
	u64 disk_bytenr;
	u64 read;
	char *cbuf = NULL;
	char *dbuf = NULL;
	u32 csize;
	u32 dsize;
	bool finished = false;
	int num_copies;
	int i;
	int slot = path->slots[0];
	int ret;

	btrfs_item_key_to_cpu(leaf, &key, slot);
	extent_num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
	ASSERT(IS_ALIGNED(offset, fs_info->sectorsize) &&
	IS_ALIGNED(len, fs_info->sectorsize));
	ASSERT(offset >= key.offset &&
	offset + len <= key.offset + extent_num_bytes);

	/* Preallocated or hole , fill @dest with zero */
	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_PREALLOC \|\|
	btrfs_file_extent_disk_bytenr(leaf, fi) == 0) {
	memset(dest, 0, len);
	return len;
	}

	if (btrfs_file_extent_compression(leaf, fi) == BTRFS_COMPRESS_NONE) {
	u64 logical;

	logical = btrfs_file_extent_disk_bytenr(leaf, fi) +
	btrfs_file_extent_offset(leaf, fi) +
	offset - key.offset;
	read = len;

	num_copies = btrfs_num_copies(fs_info, logical, len);
	for (i = 1; i <= num_copies; i++) {
	ret = read_extent_data(fs_info, dest, logical, &read, i);
	if (ret < 0 \|\| read != len)
	continue;
	finished = true;
	break;
	}
	if (!finished)
	return -EIO;
	return len;
	}

	csize = btrfs_file_extent_disk_num_bytes(leaf, fi);
	dsize = btrfs_file_extent_ram_bytes(leaf, fi);
	disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
	num_copies = btrfs_num_copies(fs_info, disk_bytenr, csize);

	cbuf = malloc_cache_aligned(csize);
	dbuf = malloc_cache_aligned(dsize);
	if (!cbuf \|\| !dbuf) {
	ret = -ENOMEM;
	goto out;
	}
	/* For compressed extent, we must read the whole on-disk extent */
	for (i = 1; i <= num_copies; i++) {
	read = csize;
	ret = read_extent_data(fs_info, cbuf, disk_bytenr,
	&read, i);
	if (ret < 0 \|\| read != csize)
	continue;
	finished = true;
	break;
	}
	if (!finished) {
	ret = -EIO;
	goto out;
	}

	ret = btrfs_decompress(btrfs_file_extent_compression(leaf, fi), cbuf,
	csize, dbuf, dsize);
	if (ret != dsize) {
	ret = -EIO;
	goto out;
	}
	/* Then copy the needed part */
	memcpy(dest, dbuf + btrfs_file_extent_offset(leaf, fi), len);
	ret = len;
	out:
	free(cbuf);
	free(dbuf);
	return ret;
	}

	/*
	* Get the first file extent that covers bytenr @file_offset.
	*
	* @file_offset must be aligned to sectorsize.
	*
	* return 0 for found, and path points to the file extent.
	* return >0 for not found, and fill @next_offset.
	* @next_offset can be 0 if there is no next file extent.
	* return <0 for error.
	*/
	static int lookup_data_extent(struct btrfs_root root, struct btrfs_path path,
	u64 ino, u64 file_offset, u64 *next_offset)
	{
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	u8 extent_type;
	int ret = 0;

	ASSERT(IS_ALIGNED(file_offset, root->fs_info->sectorsize));
	key.objectid = ino;
	key.type = BTRFS_EXTENT_DATA_KEY;
	key.offset = file_offset;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	/* Error or we're already at the file extent */
	if (ret <= 0)
	return ret;
	if (ret > 0) {
	/* Check previous file extent */
	ret = btrfs_previous_item(root, path, ino,
	BTRFS_EXTENT_DATA_KEY);
	if (ret < 0)
	return ret;
	if (ret > 0)
	goto check_next;
	}
	/* Now the key.offset must be smaller than @file_offset */
	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
	if (key.objectid != ino \|\|
	key.type != BTRFS_EXTENT_DATA_KEY)
	goto check_next;

	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
	struct btrfs_file_extent_item);
	extent_type = btrfs_file_extent_type(path->nodes[0], fi);
	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
	if (file_offset == 0)
	return 0;
	/* Inline extent should be the only extent, no next extent. */
	*next_offset = 0;
	return 1;
	}

	/* This file extent covers @file_offset */
	if (key.offset <= file_offset && key.offset +
	btrfs_file_extent_num_bytes(path->nodes[0], fi) > file_offset)
	return 0;
	check_next:
	ret = btrfs_next_item(root, path);
	if (ret < 0)
	return ret;
	if (ret > 0) {
	*next_offset = 0;
	return 1;
	}

	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
	fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
	struct btrfs_file_extent_item);
	/* Next next data extent */
	if (key.objectid != ino \|\|
	key.type != BTRFS_EXTENT_DATA_KEY) {
	*next_offset = 0;
	return 1;
	}
	/* Current file extent already beyond @file_offset */
	if (key.offset > file_offset) {
	*next_offset = key.offset;
	return 1;
	}
	/* This file extent covers @file_offset */
	if (key.offset <= file_offset && key.offset +
	btrfs_file_extent_num_bytes(path->nodes[0], fi) > file_offset)
	return 0;
	/* This file extent ends before @file_offset, check next */
	ret = btrfs_next_item(root, path);
	if (ret < 0)
	return ret;
	if (ret > 0) {
	*next_offset = 0;
	return 1;
	}
	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
	if (key.type != BTRFS_EXTENT_DATA_KEY \|\| key.objectid != ino) {
	*next_offset = 0;
	return 1;
	}
	*next_offset = key.offset;
	return 1;
	}

	static int read_and_truncate_page(struct btrfs_path *path,
	struct btrfs_file_extent_item *fi,
	int start, int len, char *dest)
	{
	struct extent_buffer *leaf = path->nodes[0];
	struct btrfs_fs_info *fs_info = leaf->fs_info;
	u64 aligned_start = round_down(start, fs_info->sectorsize);
	u8 extent_type;
	char *buf;
	int page_off = start - aligned_start;
	int page_len = fs_info->sectorsize - page_off;
	int ret;

	ASSERT(start + len <= aligned_start + fs_info->sectorsize);
	buf = malloc_cache_aligned(fs_info->sectorsize);
	if (!buf)
	return -ENOMEM;

	extent_type = btrfs_file_extent_type(leaf, fi);
	if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
	ret = btrfs_read_extent_inline(path, fi, buf);
	memcpy(dest, buf + page_off, min(page_len, ret));
	free(buf);
	return len;
	}

	ret = btrfs_read_extent_reg(path, fi,
	round_down(start, fs_info->sectorsize),
	fs_info->sectorsize, buf);
	if (ret < 0) {
	free(buf);
	return ret;
	}
	memcpy(dest, buf + page_off, page_len);
	free(buf);
	return len;
	}

	int btrfs_file_read(struct btrfs_root *root, u64 ino, u64 file_offset, u64 len,
	char *dest)
	{
	struct btrfs_fs_info *fs_info = root->fs_info;
	struct btrfs_file_extent_item *fi;
	struct btrfs_path path;
	struct btrfs_key key;
	u64 aligned_start = round_down(file_offset, fs_info->sectorsize);
	u64 aligned_end = round_down(file_offset + len, fs_info->sectorsize);
	u64 next_offset;
	u64 cur = aligned_start;
	int ret = 0;

	btrfs_init_path(&path);

	/* Set the whole dest all zero, so we won't need to bother holes */
	memset(dest, 0, len);

	/* Read out the leading unaligned part */
	if (aligned_start != file_offset) {
	ret = lookup_data_extent(root, &path, ino, aligned_start,
	&next_offset);
	if (ret < 0)
	goto out;
	if (ret == 0) {
	/* Read the unaligned part out*/
	fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
	struct btrfs_file_extent_item);
	ret = read_and_truncate_page(&path, fi, file_offset,
	round_up(file_offset, fs_info->sectorsize) -
	file_offset, dest);
	if (ret < 0)
	goto out;
	cur += fs_info->sectorsize;
	} else {
	/* The whole file is a hole */
	if (!next_offset) {
	memset(dest, 0, len);
	return len;
	}
	cur = next_offset;
	}
	}

	/* Read the aligned part */
	while (cur < aligned_end) {
	u64 extent_num_bytes;
	u8 type;

	btrfs_release_path(&path);
	ret = lookup_data_extent(root, &path, ino, cur, &next_offset);
	if (ret < 0)
	goto out;
	if (ret > 0) {
	/* No next, direct exit */
	if (!next_offset) {
	ret = 0;
	goto out;
	}
	}
	fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
	struct btrfs_file_extent_item);
	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
	type = btrfs_file_extent_type(path.nodes[0], fi);
	if (type == BTRFS_FILE_EXTENT_INLINE) {
	ret = btrfs_read_extent_inline(&path, fi, dest);
	goto out;
	}
	/* Skip holes, as we have zeroed the dest */
	if (type == BTRFS_FILE_EXTENT_PREALLOC \|\|
	btrfs_file_extent_disk_bytenr(path.nodes[0], fi) == 0) {
	cur = key.offset + btrfs_file_extent_num_bytes(
	path.nodes[0], fi);
	continue;
	}

	/* Read the remaining part of the extent */
	extent_num_bytes = btrfs_file_extent_num_bytes(path.nodes[0],
	fi);
	ret = btrfs_read_extent_reg(&path, fi, cur,
	min(extent_num_bytes, aligned_end - cur),
	dest + cur - file_offset);
	if (ret < 0)
	goto out;
	cur += min(extent_num_bytes, aligned_end - cur);
	}

	/* Read the tailing unaligned part*/
	if (file_offset + len != aligned_end) {
	btrfs_release_path(&path);
	ret = lookup_data_extent(root, &path, ino, aligned_end,
	&next_offset);
	/* <0 is error, >0 means no extent */
	if (ret)
	goto out;
	fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
	struct btrfs_file_extent_item);
	ret = read_and_truncate_page(&path, fi, aligned_end,
	file_offset + len - aligned_end,
	dest + aligned_end - file_offset);
	}
	out:
	btrfs_release_path(&path);
	if (ret < 0)
	return ret;
	return len;
	}