diff mbox series

[18/26] fs: btrfs: Implement btrfs_lookup_path()

Message ID 20200422065009.69392-19-wqu@suse.com
State Superseded
Headers show
Series fs: btrfs: Re-implement btrfs support using the more widely used extent buffer base code | expand

Commit Message

Qu Wenruo April 22, 2020, 6:50 a.m. UTC
This is the extent buffer based path lookup routine.

To implement this, btrfs_lookup_dir_item() is cross ported from
btrfs-progs, and implement btrfs_lookup_path() from scratch.

Unlike the existing __btrfs_lookup_path(), since btrfs_read_fs_root()
will check whether a root is orphan at read time, there is no need to
check root backref, this make the code a little easier to read.

Signed-off-by: Qu Wenruo <wqu at suse.com>
---
 fs/btrfs/ctree.h    |   4 +
 fs/btrfs/dir-item.c | 106 +++++++++++++++++++
 fs/btrfs/inode.c    | 245 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 355 insertions(+)

Comments

Su Yue April 22, 2020, 9:37 a.m. UTC | #1
On Wed 22 Apr 2020 at 14:50, Qu Wenruo <wqu at suse.com> wrote:

> This is the extent buffer based path lookup routine.
>
> To implement this, btrfs_lookup_dir_item() is cross ported from
> btrfs-progs, and implement btrfs_lookup_path() from scratch.
>
> Unlike the existing __btrfs_lookup_path(), since
> btrfs_read_fs_root()
> will check whether a root is orphan at read time, there is no
> need to
> check root backref, this make the code a little easier to read.
>
> Signed-off-by: Qu Wenruo <wqu at suse.com>
> ---
>  fs/btrfs/ctree.h    |   4 +
>  fs/btrfs/dir-item.c | 106 +++++++++++++++++++
>  fs/btrfs/inode.c    | 245
>  ++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 355 insertions(+)
>
> diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
> index f702eaff293c..78f7746d1f32 100644
> --- a/fs/btrfs/ctree.h
> +++ b/fs/btrfs/ctree.h
> @@ -1284,6 +1284,10 @@ struct btrfs_dir_item
> *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
>  					     struct btrfs_path *path, u64 dir,
>  					     const char *name, int name_len,
>  					     int mod);
> +/* inode.c */
> +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);
>
>  /* ctree.c */
>  int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const
>  struct btrfs_key *k2);
> diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
> index aea621c72bb3..4bf45c2fa925 100644
> --- a/fs/btrfs/dir-item.c
> +++ b/fs/btrfs/dir-item.c
> @@ -8,6 +8,112 @@
>  #include "btrfs.h"
>  #include "disk-io.h"
>
> +static int verify_dir_item(struct btrfs_root *root,
> +		    struct extent_buffer *leaf,
> +		    struct btrfs_dir_item *dir_item)
> +{
> +	u16 namelen = BTRFS_NAME_LEN;
> +	u8 type = btrfs_dir_type(leaf, dir_item);
> +
> +	if (type == BTRFS_FT_XATTR)
> +		namelen = XATTR_NAME_MAX;
> +
> +	if (btrfs_dir_name_len(leaf, dir_item) > namelen) {
> +		fprintf(stderr, "invalid dir item name len: %u\n",
> +		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
> +		return 1;
> +	}
> +
> +	/* BTRFS_MAX_XATTR_SIZE is the same for all dir items */
> +	if ((btrfs_dir_data_len(leaf, dir_item) +
> +	     btrfs_dir_name_len(leaf, dir_item)) >
> +			BTRFS_MAX_XATTR_SIZE(root->fs_info)) {
> +		fprintf(stderr, "invalid dir item name + data len: %u +
> %u\n",
> +		       (unsigned)btrfs_dir_name_len(leaf, dir_item),
> +		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
> +		return 1;
> +	}
> +
> +	return 0;
> +}
> +
> +struct btrfs_dir_item *btrfs_match_dir_item_name(struct
> btrfs_root *root,
> +			      struct btrfs_path *path,
> +			      const char *name, int name_len)
> +{
> +	struct btrfs_dir_item *dir_item;
> +	unsigned long name_ptr;
> +	u32 total_len;
> +	u32 cur = 0;
> +	u32 this_len;
> +	struct extent_buffer *leaf;
> +
> +	leaf = path->nodes[0];
> +	dir_item = btrfs_item_ptr(leaf, path->slots[0], struct
> btrfs_dir_item);
> +	total_len = btrfs_item_size_nr(leaf, path->slots[0]);
> +	if (verify_dir_item(root, leaf, dir_item))
> +		return NULL;
> +
> +	while(cur < total_len) {
> +		this_len = sizeof(*dir_item) +
> +			btrfs_dir_name_len(leaf, dir_item) +
> +			btrfs_dir_data_len(leaf, dir_item);
> +		if (this_len > (total_len - cur)) {
> +			fprintf(stderr, "invalid dir item size\n");
> +			return NULL;
> +		}
> +
> +		name_ptr = (unsigned long)(dir_item + 1);
> +
> +		if (btrfs_dir_name_len(leaf, dir_item) == name_len &&
> +		    memcmp_extent_buffer(leaf, name, name_ptr, name_len)
> == 0)
> +			return dir_item;
> +
> +		cur += this_len;
> +		dir_item = (struct btrfs_dir_item *)((char *)dir_item +
> +						     this_len);
> +	}
> +	return NULL;
> +}
> +
> +struct btrfs_dir_item *btrfs_lookup_dir_item(struct
> btrfs_trans_handle *trans,
> +					     struct btrfs_root *root,
> +					     struct btrfs_path *path, u64 dir,
> +					     const char *name, int name_len,
> +					     int mod)
> +{
> +	int ret;
> +	struct btrfs_key key;
> +	int ins_len = mod < 0 ? -1 : 0;
> +	int cow = mod != 0;
> +	struct btrfs_key found_key;
> +	struct extent_buffer *leaf;
> +
> +	key.objectid = dir;
> +	key.type = BTRFS_DIR_ITEM_KEY;
> +
> +	key.offset = btrfs_name_hash(name, name_len);
> +
> +	ret = btrfs_search_slot(trans, root, &key, path, ins_len,
> cow);
> +	if (ret < 0)
> +		return ERR_PTR(ret);
> +	if (ret > 0) {
> +		if (path->slots[0] == 0)
> +			return NULL;
> +		path->slots[0]--;
> +	}
> +
> +	leaf = path->nodes[0];
> +	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
> +
> +	if (found_key.objectid != dir ||
> +	    found_key.type != BTRFS_DIR_ITEM_KEY ||
> +	    found_key.offset != key.offset)
> +		return NULL;
> +
> +	return btrfs_match_dir_item_name(root, path, name, name_len);
> +}
> +
>  static int __verify_dir_item(struct btrfs_dir_item *item, u32
>  start, u32 total)
>  {
>  	u16 max_len = BTRFS_NAME_LEN;
> diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
> index df2f6590bb40..af4f30bbd50c 100644
> --- a/fs/btrfs/inode.c
> +++ b/fs/btrfs/inode.c
> @@ -161,6 +161,115 @@ int __btrfs_readlink(const struct
> __btrfs_root *root, u64 inr, char *target)
>  	return 0;
>  }
>
> +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;
> +
> +		/* 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;
> +}
> +
>  /* inr must be a directory (for regular files with multiple
>  hard links this
>     function returns only one of the parents of the file) */
>  static u64 __get_parent_inode(struct __btrfs_root *root, u64
>  inr,
> @@ -235,6 +344,142 @@ static inline const char
> *skip_current_directories(const char *cur)
>  	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;
> +	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) {

next_length() promises @len <= BTRFS_NAME_LEN, so the check is
trivial.

> +			printf("%s: Name too long at \"%.*s\"\n", __func__,
> +			       BTRFS_NAME_LEN, cur);
> +			return -ENAMETOOLONG;
> +		}
> +		if (len == 1 && cur[0] == '.')
> +			break;
> +		/* Go one level up */
> +		if (len == 2 && cur[0] == '.' && cur[1] == '.') {
> +			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;
> +		/* Child inode is a subvolume */
> +		if (key.type == BTRFS_ROOT_ITEM_KEY) {
> +
> +			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);
> +			goto next;
> +		}
> +		/* Child inode is a symlink */
> +		if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0) {
> +			char *target;
> +
> +			if (symlink_limit == 0) {
> +				printf("%s: Too much symlinks!\n", __func__);
> +				return -EMLINK;
> +			}
> +			target = malloc(fs_info->sectorsize);
> +			if (!target)
> +				return -ENOMEM;
> +			ret = btrfs_readlink(root, ino, target);
> +			if (ret < 0) {
> +				free(target);
> +				return ret;
> +			}
> +			target[ret] = '\0';

It was done in btrfs_readlink() already.
> +
> +			ret = btrfs_lookup_path(root, ino, target, &next_root,
> +						&next_ino, &next_type,
> +						symlink_limit);

Just notify gentlely this is a recursive call here. I don't know
whether uboot cares about stack things. But, recursion makes
coding simpler :).

--
Su
> +			if (ret < 0)
> +				return ret;
> +			root = next_root;
> +			ino = next_ino;
> +			type = next_type;
> +			goto next;
> +		}
> +		/* Child inode is an inode */
> +		ino = key.objectid;
> +next:
> +		cur += len;
> +	}
> +	if (!ret) {
> +		*root_ret = root;
> +		*ino_ret = ino;
> +		*type_ret = type;
> +	}
> +	return ret;
> +}
> +
>  u64 __btrfs_lookup_path(struct __btrfs_root *root, u64 inr,
>  const char *path,
>  		      u8 *type_p, struct btrfs_inode_item *inode_item_p,
>  		      int symlink_limit)
Su Yue April 22, 2020, 9:46 a.m. UTC | #2
On Wed 22 Apr 2020 at 14:50, Qu Wenruo <wqu at suse.com> wrote:

> This is the extent buffer based path lookup routine.
>
> To implement this, btrfs_lookup_dir_item() is cross ported from
> btrfs-progs, and implement btrfs_lookup_path() from scratch.
>
> Unlike the existing __btrfs_lookup_path(), since btrfs_read_fs_root()
> will check whether a root is orphan at read time, there is no need to
> check root backref, this make the code a little easier to read.
>
> Signed-off-by: Qu Wenruo <wqu at suse.com>
> ---
>  fs/btrfs/ctree.h    |   4 +
>  fs/btrfs/dir-item.c | 106 +++++++++++++++++++
>  fs/btrfs/inode.c    | 245 ++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 355 insertions(+)
>
> diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
> index f702eaff293c..78f7746d1f32 100644
> --- a/fs/btrfs/ctree.h
> +++ b/fs/btrfs/ctree.h
> @@ -1284,6 +1284,10 @@ struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
>  					     struct btrfs_path *path, u64 dir,
>  					     const char *name, int name_len,
>  					     int mod);
> +/* inode.c */
> +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);
>
>  /* ctree.c */
>  int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2);
> diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
> index aea621c72bb3..4bf45c2fa925 100644
> --- a/fs/btrfs/dir-item.c
> +++ b/fs/btrfs/dir-item.c
> @@ -8,6 +8,112 @@
>  #include "btrfs.h"
>  #include "disk-io.h"
>
> +static int verify_dir_item(struct btrfs_root *root,
> +		    struct extent_buffer *leaf,
> +		    struct btrfs_dir_item *dir_item)
> +{
> +	u16 namelen = BTRFS_NAME_LEN;
> +	u8 type = btrfs_dir_type(leaf, dir_item);
> +
> +	if (type == BTRFS_FT_XATTR)
> +		namelen = XATTR_NAME_MAX;
> +
> +	if (btrfs_dir_name_len(leaf, dir_item) > namelen) {
> +		fprintf(stderr, "invalid dir item name len: %u\n",
> +		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
> +		return 1;
> +	}
> +
> +	/* BTRFS_MAX_XATTR_SIZE is the same for all dir items */
> +	if ((btrfs_dir_data_len(leaf, dir_item) +
> +	     btrfs_dir_name_len(leaf, dir_item)) >
> +			BTRFS_MAX_XATTR_SIZE(root->fs_info)) {
> +		fprintf(stderr, "invalid dir item name + data len: %u + %u\n",
> +		       (unsigned)btrfs_dir_name_len(leaf, dir_item),
> +		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
> +		return 1;
> +	}
> +
> +	return 0;
> +}
> +
> +struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root,
> +			      struct btrfs_path *path,
> +			      const char *name, int name_len)
> +{
> +	struct btrfs_dir_item *dir_item;
> +	unsigned long name_ptr;
> +	u32 total_len;
> +	u32 cur = 0;
> +	u32 this_len;
> +	struct extent_buffer *leaf;
> +
> +	leaf = path->nodes[0];
> +	dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
> +	total_len = btrfs_item_size_nr(leaf, path->slots[0]);
> +	if (verify_dir_item(root, leaf, dir_item))
> +		return NULL;
> +
> +	while(cur < total_len) {
> +		this_len = sizeof(*dir_item) +
> +			btrfs_dir_name_len(leaf, dir_item) +
> +			btrfs_dir_data_len(leaf, dir_item);
> +		if (this_len > (total_len - cur)) {
> +			fprintf(stderr, "invalid dir item size\n");
> +			return NULL;
> +		}
> +
> +		name_ptr = (unsigned long)(dir_item + 1);
> +
> +		if (btrfs_dir_name_len(leaf, dir_item) == name_len &&
> +		    memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)
> +			return dir_item;
> +
> +		cur += this_len;
> +		dir_item = (struct btrfs_dir_item *)((char *)dir_item +
> +						     this_len);
> +	}
> +	return NULL;
> +}
> +
> +struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
> +					     struct btrfs_root *root,
> +					     struct btrfs_path *path, u64 dir,
> +					     const char *name, int name_len,
> +					     int mod)
> +{
> +	int ret;
> +	struct btrfs_key key;
> +	int ins_len = mod < 0 ? -1 : 0;
> +	int cow = mod != 0;
> +	struct btrfs_key found_key;
> +	struct extent_buffer *leaf;
> +
> +	key.objectid = dir;
> +	key.type = BTRFS_DIR_ITEM_KEY;
> +
> +	key.offset = btrfs_name_hash(name, name_len);
> +
> +	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
> +	if (ret < 0)
> +		return ERR_PTR(ret);
> +	if (ret > 0) {
> +		if (path->slots[0] == 0)
> +			return NULL;
> +		path->slots[0]--;
> +	}
> +
> +	leaf = path->nodes[0];
> +	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
> +
> +	if (found_key.objectid != dir ||
> +	    found_key.type != BTRFS_DIR_ITEM_KEY ||
> +	    found_key.offset != key.offset)
> +		return NULL;
> +
> +	return btrfs_match_dir_item_name(root, path, name, name_len);
> +}
> +
>  static int __verify_dir_item(struct btrfs_dir_item *item, u32 start, u32 total)
>  {
>  	u16 max_len = BTRFS_NAME_LEN;
> diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
> index df2f6590bb40..af4f30bbd50c 100644
> --- a/fs/btrfs/inode.c
> +++ b/fs/btrfs/inode.c
> @@ -161,6 +161,115 @@ int __btrfs_readlink(const struct __btrfs_root *root, u64 inr, char *target)
>  	return 0;
>  }
>
> +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;
> +
> +		/* 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;
> +}
> +
>  /* inr must be a directory (for regular files with multiple hard links this
>     function returns only one of the parents of the file) */
>  static u64 __get_parent_inode(struct __btrfs_root *root, u64 inr,
> @@ -235,6 +344,142 @@ static inline const char *skip_current_directories(const char *cur)
>  	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;
> +	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) {

next_length() promises @len <= BTRFS_NAME_LEN, so the check is trivial.

> +			printf("%s: Name too long at \"%.*s\"\n", __func__,
> +			       BTRFS_NAME_LEN, cur);
> +			return -ENAMETOOLONG;
> +		}
> +		if (len == 1 && cur[0] == '.')
> +			break;
> +		/* Go one level up */
> +		if (len == 2 && cur[0] == '.' && cur[1] == '.') {
> +			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;
> +		/* Child inode is a subvolume */
> +		if (key.type == BTRFS_ROOT_ITEM_KEY) {
> +
> +			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);
> +			goto next;
> +		}
> +		/* Child inode is a symlink */
> +		if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0) {
> +			char *target;
> +
> +			if (symlink_limit == 0) {
> +				printf("%s: Too much symlinks!\n", __func__);
> +				return -EMLINK;
> +			}
> +			target = malloc(fs_info->sectorsize);
> +			if (!target)
> +				return -ENOMEM;
> +			ret = btrfs_readlink(root, ino, target);
> +			if (ret < 0) {
> +				free(target);
> +				return ret;
> +			}
> +			target[ret] = '\0';

It was done in btrfs_readlink() already.
> +
> +			ret = btrfs_lookup_path(root, ino, target, &next_root,
> +						&next_ino, &next_type,
> +						symlink_limit);

Just notify gentlely this is a recursive call here. I don't know
whether uboot cares about stack things. But, recursion makes coding simpler :).

--
Su
> +			if (ret < 0)
> +				return ret;
> +			root = next_root;
> +			ino = next_ino;
> +			type = next_type;
> +			goto next;
> +		}
> +		/* Child inode is an inode */
> +		ino = key.objectid;
> +next:
> +		cur += len;
> +	}
> +	if (!ret) {
> +		*root_ret = root;
> +		*ino_ret = ino;
> +		*type_ret = type;
> +	}
> +	return ret;
> +}
> +
>  u64 __btrfs_lookup_path(struct __btrfs_root *root, u64 inr, const char *path,
>  		      u8 *type_p, struct btrfs_inode_item *inode_item_p,
>  		      int symlink_limit)
Marek BehĂșn April 22, 2020, 10:04 a.m. UTC | #3
On Wed, 22 Apr 2020 17:46:25 +0800
Su Yue <Damenly_Su at gmx.com> wrote:

> > +	while (*cur != '\0') {
> > +
> > +		cur = skip_current_directories(cur);
> > +		len = next_length(cur);
> > +		if (len > BTRFS_NAME_LEN) {  
> 
> next_length() promises @len <= BTRFS_NAME_LEN, so the check is trivial.

Hmm. This is a bug in next_length. I meant for next_length to return
len > BTRFS_NAME_LEN in case of too long name. Thanks for noticing.

> > +			ret = btrfs_readlink(root, ino, target);
> > +			if (ret < 0) {
> > +				free(target);
> > +				return ret;
> > +			}
> > +			target[ret] = '\0';  
> 
> It was done in btrfs_readlink() already.

It is in old btrfs_readlink, but is it even after this patches? I don't
see it in the new implementation.

> > +
> > +			ret = btrfs_lookup_path(root, ino, target, &next_root,
> > +						&next_ino, &next_type,
> > +						symlink_limit);  
> 
> Just notify gentlely this is a recursive call here. I don't know
> whether uboot cares about stack things. But, recursion makes coding simpler :).

It is limited by symlink_limit. Until somebody complains about stack
issues I would like to keep it simple.
Su Yue April 22, 2020, 2:17 p.m. UTC | #4
On Wed 22 Apr 2020 at 18:04, Marek Behun <marek.behun at nic.cz>
wrote:

> On Wed, 22 Apr 2020 17:46:25 +0800 Su Yue <Damenly_Su at gmx.com>
> wrote:
>
>> > +	while (*cur != '\0') { + +		cur =
>> > skip_current_directories(cur); +		len =
>> > next_length(cur); +		if (len > BTRFS_NAME_LEN) {
>>  next_length() promises @len <= BTRFS_NAME_LEN, so the check is
>> trivial.
>

Okay.
> Hmm. This is a bug in next_length. I meant for next_length to
> return len > BTRFS_NAME_LEN in case of too long name. Thanks for
> noticing.
>
>> > +			ret = btrfs_readlink(root, ino, target); +
>> > if (ret < 0) { +				free(target); +
>> > return ret; +			} +			target[ret] = '\0';
>>  It was done in btrfs_readlink() already.
>
> It is in old btrfs_readlink, but is it even after this patches?
> I don't see it in the new implementation.
>

You are right. The thing changed in the 17th patch.
btrfs_readlink()
doesn't set the null byte now.

--
Su
>> > +
>> > +			ret = btrfs_lookup_path(root, ino, target, &next_root,
>> > +						&next_ino, &next_type,
>> > +						symlink_limit);
>>
>> Just notify gentlely this is a recursive call here. I don't know
>> whether uboot cares about stack things. But, recursion makes coding simpler :).
>
> It is limited by symlink_limit. Until somebody complains about stack
> issues I would like to keep it simple.
Su Yue April 22, 2020, 2:44 p.m. UTC | #5
On Wed 22 Apr 2020 at 14:50, Qu Wenruo <wqu at suse.com> wrote:

> This is the extent buffer based path lookup routine.
>
> To implement this, btrfs_lookup_dir_item() is cross ported from
> btrfs-progs, and implement btrfs_lookup_path() from scratch.
>
> Unlike the existing __btrfs_lookup_path(), since
> btrfs_read_fs_root() will check whether a root is orphan at read
> time, there is no need to check root backref, this make the code
> a little easier to read.
>
> Signed-off-by: Qu Wenruo <wqu at suse.com> ---
>  fs/btrfs/ctree.h    |   4 + fs/btrfs/dir-item.c | 106
>  +++++++++++++++++++ fs/btrfs/inode.c    | 245
>  ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed,
>  355 insertions(+)
>
> diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index
> f702eaff293c..78f7746d1f32 100644 --- a/fs/btrfs/ctree.h +++
> b/fs/btrfs/ctree.h @@ -1284,6 +1284,10 @@ struct btrfs_dir_item
> *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
>  					     struct btrfs_path *path, u64 dir, const
>  char *name, int name_len, int mod);
> +/* inode.c */ +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);
>   /* ctree.c */ int btrfs_comp_cpu_keys(const struct btrfs_key
>  *k1, const struct btrfs_key *k2);
> diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c index
> aea621c72bb3..4bf45c2fa925 100644 --- a/fs/btrfs/dir-item.c +++
> b/fs/btrfs/dir-item.c @@ -8,6 +8,112 @@
>  #include "btrfs.h" #include "disk-io.h"
> +static int verify_dir_item(struct btrfs_root *root, +
> struct extent_buffer *leaf, +		    struct btrfs_dir_item
> *dir_item) +{ +	u16 namelen = BTRFS_NAME_LEN; +	u8 type =
> btrfs_dir_type(leaf, dir_item); + +	if (type ==
> BTRFS_FT_XATTR) +		namelen = XATTR_NAME_MAX; + +	if
> (btrfs_dir_name_len(leaf, dir_item) > namelen) { +
> fprintf(stderr, "invalid dir item name len: %u\n", +
> (unsigned)btrfs_dir_data_len(leaf, dir_item)); +		return 1;
> +	} + +	/* BTRFS_MAX_XATTR_SIZE is the same for all dir items
> */ +	if ((btrfs_dir_data_len(leaf, dir_item) + +
> btrfs_dir_name_len(leaf, dir_item)) > +
> BTRFS_MAX_XATTR_SIZE(root->fs_info)) { +		fprintf(stderr,
> "invalid dir item name + data len: %u + %u\n", +
> (unsigned)btrfs_dir_name_len(leaf, dir_item), +
> (unsigned)btrfs_dir_data_len(leaf, dir_item)); +		return 1;
> +	} + +	return 0; +} + +struct btrfs_dir_item
> *btrfs_match_dir_item_name(struct btrfs_root *root, +
> struct btrfs_path *path, +			      const char *name,
> int name_len) +{ +	struct btrfs_dir_item *dir_item; +
> unsigned long name_ptr; +	u32 total_len; +	u32 cur = 0; +
> u32 this_len; +	struct extent_buffer *leaf; + +	leaf =
> path->nodes[0]; +	dir_item = btrfs_item_ptr(leaf,
> path->slots[0], struct btrfs_dir_item); +	total_len =
> btrfs_item_size_nr(leaf, path->slots[0]); +	if
> (verify_dir_item(root, leaf, dir_item)) +		return NULL; + +
> while(cur < total_len) { +		this_len = sizeof(*dir_item) +
> +			btrfs_dir_name_len(leaf, dir_item) + +
> btrfs_dir_data_len(leaf, dir_item); +		if (this_len >
> (total_len - cur)) { +			fprintf(stderr, "invalid dir
> item size\n"); +			return NULL; +		} + +
> name_ptr = (unsigned long)(dir_item + 1); + +		if
> (btrfs_dir_name_len(leaf, dir_item) == name_len && +
> memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) +
> return dir_item; + +		cur += this_len; +		dir_item =
> (struct btrfs_dir_item *)((char *)dir_item + +
> this_len); +	} +	return NULL; +} + +struct btrfs_dir_item
> *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans, +
> struct btrfs_root *root, +					     struct
> btrfs_path *path, u64 dir, +					     const char
> *name, int name_len, +					     int mod) +{ +
> int ret; +	struct btrfs_key key; +	int ins_len = mod < 0 ? -1
> : 0; +	int cow = mod != 0; +	struct btrfs_key found_key; +
> struct extent_buffer *leaf; + +	key.objectid = dir; +
> key.type = BTRFS_DIR_ITEM_KEY; + +	key.offset =
> btrfs_name_hash(name, name_len); + +	ret =
> btrfs_search_slot(trans, root, &key, path, ins_len, cow); +	if
> (ret < 0) +		return ERR_PTR(ret); +	if (ret > 0) { +
> if (path->slots[0] == 0) +			return NULL; +
> path->slots[0]--; +	} + +	leaf = path->nodes[0]; +
> btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); + +	if
> (found_key.objectid != dir || +	    found_key.type !=
> BTRFS_DIR_ITEM_KEY || +	    found_key.offset != key.offset) +
> return NULL; + +	return btrfs_match_dir_item_name(root, path,
> name, name_len); +} +
>  static int __verify_dir_item(struct btrfs_dir_item *item, u32
>  start, u32 total) { u16 max_len = BTRFS_NAME_LEN;
> diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index
> df2f6590bb40..af4f30bbd50c 100644 --- a/fs/btrfs/inode.c +++
> b/fs/btrfs/inode.c @@ -161,6 +161,115 @@ int
> __btrfs_readlink(const struct __btrfs_root *root, u64 inr, char
> *target)
>  	return 0; }
> +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; + +
> /* 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; +} +
>  /* inr must be a directory (for regular files with multiple
>  hard links this
>     function returns only one of the parents of the file) */
>  static u64 __get_parent_inode(struct __btrfs_root *root, u64
>  inr,
> @@ -235,6 +344,142 @@ static inline const char
> *skip_current_directories(const char *cur)
>  	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; +	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) { +			printf("%s: Name too long
> at \"%.*s\"\n", __func__, +			       BTRFS_NAME_LEN,
> cur); +			return -ENAMETOOLONG; +		} +		if (len ==
> 1 && cur[0] == '.')  +			break; +		/* Go one
> level up */ +		if (len == 2 && cur[0] == '.' && cur[1] ==
> '.') { +			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; +		/* Child inode is
> a subvolume */ +		if (key.type == BTRFS_ROOT_ITEM_KEY) { + +
> 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); +			goto next; +
> } +		/* Child inode is a symlink */ +		if (type ==
> BTRFS_FT_SYMLINK && symlink_limit >= 0) { +			char
> *target; + +			if (symlink_limit == 0) { +
> printf("%s: Too much symlinks!\n", __func__); +
> return -EMLINK; +			} +			target =
> malloc(fs_info->sectorsize); +			if (!target) +
> return -ENOMEM; +			ret = btrfs_readlink(root, ino,
> 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);

Looked through older codes, should be "symlink_limit - 1"?

--
Su
> +			if (ret < 0)
> +				return ret;
> +			root = next_root;
> +			ino = next_ino;
> +			type = next_type;
> +			goto next;
> +		}
> +		/* Child inode is an inode */
> +		ino = key.objectid;
> +next:
> +		cur += len;
> +	}
> +	if (!ret) {
> +		*root_ret = root;
> +		*ino_ret = ino;
> +		*type_ret = type;
> +	}
> +	return ret;
> +}
> +
>  u64 __btrfs_lookup_path(struct __btrfs_root *root, u64 inr, const char *path,
>  		      u8 *type_p, struct btrfs_inode_item *inode_item_p,
>  		      int symlink_limit)
Marek BehĂșn April 22, 2020, 2:49 p.m. UTC | #6
On Wed, 22 Apr 2020 22:44:43 +0800
Su Yue <Damenly_Su at gmx.com> wrote:

> Looked through older codes, should be "symlink_limit - 1"?

OMG yes :) without this it can break :)
diff mbox series

Patch

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index f702eaff293c..78f7746d1f32 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1284,6 +1284,10 @@  struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
 					     struct btrfs_path *path, u64 dir,
 					     const char *name, int name_len,
 					     int mod);
+/* inode.c */
+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);
 
 /* ctree.c */
 int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2);
diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c
index aea621c72bb3..4bf45c2fa925 100644
--- a/fs/btrfs/dir-item.c
+++ b/fs/btrfs/dir-item.c
@@ -8,6 +8,112 @@ 
 #include "btrfs.h"
 #include "disk-io.h"
 
+static int verify_dir_item(struct btrfs_root *root,
+		    struct extent_buffer *leaf,
+		    struct btrfs_dir_item *dir_item)
+{
+	u16 namelen = BTRFS_NAME_LEN;
+	u8 type = btrfs_dir_type(leaf, dir_item);
+
+	if (type == BTRFS_FT_XATTR)
+		namelen = XATTR_NAME_MAX;
+
+	if (btrfs_dir_name_len(leaf, dir_item) > namelen) {
+		fprintf(stderr, "invalid dir item name len: %u\n",
+		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
+		return 1;
+	}
+
+	/* BTRFS_MAX_XATTR_SIZE is the same for all dir items */
+	if ((btrfs_dir_data_len(leaf, dir_item) +
+	     btrfs_dir_name_len(leaf, dir_item)) >
+			BTRFS_MAX_XATTR_SIZE(root->fs_info)) {
+		fprintf(stderr, "invalid dir item name + data len: %u + %u\n",
+		       (unsigned)btrfs_dir_name_len(leaf, dir_item),
+		       (unsigned)btrfs_dir_data_len(leaf, dir_item));
+		return 1;
+	}
+
+	return 0;
+}
+
+struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root,
+			      struct btrfs_path *path,
+			      const char *name, int name_len)
+{
+	struct btrfs_dir_item *dir_item;
+	unsigned long name_ptr;
+	u32 total_len;
+	u32 cur = 0;
+	u32 this_len;
+	struct extent_buffer *leaf;
+
+	leaf = path->nodes[0];
+	dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
+	total_len = btrfs_item_size_nr(leaf, path->slots[0]);
+	if (verify_dir_item(root, leaf, dir_item))
+		return NULL;
+
+	while(cur < total_len) {
+		this_len = sizeof(*dir_item) +
+			btrfs_dir_name_len(leaf, dir_item) +
+			btrfs_dir_data_len(leaf, dir_item);
+		if (this_len > (total_len - cur)) {
+			fprintf(stderr, "invalid dir item size\n");
+			return NULL;
+		}
+
+		name_ptr = (unsigned long)(dir_item + 1);
+
+		if (btrfs_dir_name_len(leaf, dir_item) == name_len &&
+		    memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)
+			return dir_item;
+
+		cur += this_len;
+		dir_item = (struct btrfs_dir_item *)((char *)dir_item +
+						     this_len);
+	}
+	return NULL;
+}
+
+struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
+					     struct btrfs_root *root,
+					     struct btrfs_path *path, u64 dir,
+					     const char *name, int name_len,
+					     int mod)
+{
+	int ret;
+	struct btrfs_key key;
+	int ins_len = mod < 0 ? -1 : 0;
+	int cow = mod != 0;
+	struct btrfs_key found_key;
+	struct extent_buffer *leaf;
+
+	key.objectid = dir;
+	key.type = BTRFS_DIR_ITEM_KEY;
+
+	key.offset = btrfs_name_hash(name, name_len);
+
+	ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
+	if (ret < 0)
+		return ERR_PTR(ret);
+	if (ret > 0) {
+		if (path->slots[0] == 0)
+			return NULL;
+		path->slots[0]--;
+	}
+
+	leaf = path->nodes[0];
+	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+
+	if (found_key.objectid != dir ||
+	    found_key.type != BTRFS_DIR_ITEM_KEY ||
+	    found_key.offset != key.offset)
+		return NULL;
+
+	return btrfs_match_dir_item_name(root, path, name, name_len);
+}
+
 static int __verify_dir_item(struct btrfs_dir_item *item, u32 start, u32 total)
 {
 	u16 max_len = BTRFS_NAME_LEN;
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index df2f6590bb40..af4f30bbd50c 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -161,6 +161,115 @@  int __btrfs_readlink(const struct __btrfs_root *root, u64 inr, char *target)
 	return 0;
 }
 
+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;
+
+		/* 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;
+}
+
 /* inr must be a directory (for regular files with multiple hard links this
    function returns only one of the parents of the file) */
 static u64 __get_parent_inode(struct __btrfs_root *root, u64 inr,
@@ -235,6 +344,142 @@  static inline const char *skip_current_directories(const char *cur)
 	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;
+	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) {
+			printf("%s: Name too long at \"%.*s\"\n", __func__,
+			       BTRFS_NAME_LEN, cur);
+			return -ENAMETOOLONG;
+		}
+		if (len == 1 && cur[0] == '.')
+			break;
+		/* Go one level up */
+		if (len == 2 && cur[0] == '.' && cur[1] == '.') {
+			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;
+		/* Child inode is a subvolume */
+		if (key.type == BTRFS_ROOT_ITEM_KEY) {
+
+			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);
+			goto next;
+		}
+		/* Child inode is a symlink */
+		if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0) {
+			char *target;
+
+			if (symlink_limit == 0) {
+				printf("%s: Too much symlinks!\n", __func__);
+				return -EMLINK;
+			}
+			target = malloc(fs_info->sectorsize);
+			if (!target)
+				return -ENOMEM;
+			ret = btrfs_readlink(root, ino, 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;
+			goto next;
+		}
+		/* Child inode is an inode */
+		ino = key.objectid;
+next:
+		cur += len;
+	}
+	if (!ret) {
+		*root_ret = root;
+		*ino_ret = ino;
+		*type_ret = type;
+	}
+	return ret;
+}
+
 u64 __btrfs_lookup_path(struct __btrfs_root *root, u64 inr, const char *path,
 		      u8 *type_p, struct btrfs_inode_item *inode_item_p,
 		      int symlink_limit)