Re: [PATCH U-BOOT 18/26] fs: btrfs: Implement btrfs_lookup_path()

On Wed 22 Apr 2020 at 14:50, Qu Wenruo wqu@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@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)