#define LAST_ITEM (1<<15) /* Complete this tree traversal */
#define ROOT_REF_MISSING (1<<16) /* ROOT_REF not found */
#define ROOT_REF_MISMATCH (1<<17) /* ROOT_REF found but not match */
+#define DIR_INDEX_MISSING (1<<18) /* INODE_INDEX not found */
+#define DIR_INDEX_MISMATCH (1<<19) /* INODE_INDEX found but not match */
static inline struct data_backref* to_data_backref(struct extent_backref *back)
{
}
/*
- * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
- * INODE_REF/INODE_EXTREF match.
+ * Find the @index according by @ino and name.
+ * Notice:time efficiency is O(N)
*
* @root: the root of the fs/file tree
- * @ref_key: the key of the INODE_REF/INODE_EXTREF
- * @key: the key of the DIR_ITEM/DIR_INDEX
- * @index: the index in the INODE_REF/INODE_EXTREF, be used to
- * distinguish root_dir between normal dir/file
- * @name: the name in the INODE_REF/INODE_EXTREF
- * @namelen: the length of name in the INODE_REF/INODE_EXTREF
- * @mode: the st_mode of INODE_ITEM
+ * @index_ret: the index as return value
+ * @namebuf: the name to match
+ * @name_len: the length of name to match
+ * @file_type: the file_type of INODE_ITEM to match
*
- * Return 0 if no error occurred.
- * Return ROOT_DIR_ERROR if found DIR_ITEM/DIR_INDEX for root_dir.
- * Return DIR_ITEM_MISSING if couldn't find DIR_ITEM/DIR_INDEX for normal
- * dir/file.
- * Return DIR_ITEM_MISMATCH if INODE_REF/INODE_EXTREF and DIR_ITEM/DIR_INDEX
- * not match for normal dir/file.
+ * Returns 0 if found and *@index_ret will be modified with right value
+ * Returns< 0 not found and *@index_ret will be (u64)-1
*/
-static int find_dir_item(struct btrfs_root *root, struct btrfs_key *ref_key,
- struct btrfs_key *key, u64 index, char *name,
- u32 namelen, u32 mode)
+static int find_dir_index(struct btrfs_root *root, u64 dirid, u64 location_id,
+ u64 *index_ret, char *namebuf, u32 name_len,
+ u8 file_type)
{
struct btrfs_path path;
struct extent_buffer *node;
struct btrfs_dir_item *di;
+ struct btrfs_key key;
struct btrfs_key location;
- char namebuf[BTRFS_NAME_LEN] = {0};
+ char name[BTRFS_NAME_LEN] = {0};
+
u32 total;
u32 cur = 0;
u32 len;
- u32 name_len;
u32 data_len;
u8 filetype;
int slot;
int ret;
+ ASSERT(index_ret);
+
+ /* search from the last index */
+ key.objectid = dirid;
+ key.offset = (u64)-1;
+ key.type = BTRFS_DIR_INDEX_KEY;
+
btrfs_init_path(&path);
- ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
- if (ret < 0) {
- ret = DIR_ITEM_MISSING;
+ ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
+ if (ret < 0)
+ return ret;
+
+loop:
+ ret = btrfs_previous_item(root, &path, dirid, BTRFS_DIR_INDEX_KEY);
+ if (ret) {
+ ret = -ENOENT;
+ *index_ret = (64)-1;
goto out;
}
+ /* Check whether inode_id/filetype/name match */
+ node = path.nodes[0];
+ slot = path.slots[0];
+ di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
+ total = btrfs_item_size_nr(node, slot);
+ while (cur < total) {
+ ret = -ENOENT;
+ len = btrfs_dir_name_len(node, di);
+ data_len = btrfs_dir_data_len(node, di);
- /* Process root dir and goto out*/
- if (index == 0) {
- if (ret == 0) {
- ret = ROOT_DIR_ERROR;
- error(
- "root %llu INODE %s[%llu %llu] ROOT_DIR shouldn't have %s",
- root->objectid,
- ref_key->type == BTRFS_INODE_REF_KEY ?
- "REF" : "EXTREF",
- ref_key->objectid, ref_key->offset,
- key->type == BTRFS_DIR_ITEM_KEY ?
- "DIR_ITEM" : "DIR_INDEX");
- } else {
- ret = 0;
- }
+ btrfs_dir_item_key_to_cpu(node, di, &location);
+ if (location.objectid != location_id ||
+ location.type != BTRFS_INODE_ITEM_KEY ||
+ location.offset != 0)
+ goto next;
+
+ filetype = btrfs_dir_type(node, di);
+ if (file_type != filetype)
+ goto next;
+
+ if (len > BTRFS_NAME_LEN)
+ len = BTRFS_NAME_LEN;
+
+ read_extent_buffer(node, name, (unsigned long)(di + 1), len);
+ if (len != name_len || strncmp(namebuf, name, len))
+ goto next;
+ btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+ *index_ret = key.offset;
+ ret = 0;
goto out;
+next:
+ len += sizeof(*di) + data_len;
+ di = (struct btrfs_dir_item *)((char *)di + len);
+ cur += len;
}
+ goto loop;
- /* Process normal file/dir */
- if (ret > 0) {
- ret = DIR_ITEM_MISSING;
- error(
- "root %llu INODE %s[%llu %llu] doesn't have related %s[%llu %llu] namelen %u filename %s filetype %d",
- root->objectid,
- ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF",
- ref_key->objectid, ref_key->offset,
- key->type == BTRFS_DIR_ITEM_KEY ?
- "DIR_ITEM" : "DIR_INDEX",
- key->objectid, key->offset, namelen, name,
- imode_to_type(mode));
+out:
+ btrfs_release_path(&path);
+ return ret;
+}
+
+/*
+ * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
+ * INODE_REF/INODE_EXTREF match.
+ *
+ * @root: the root of the fs/file tree
+ * @key: the key of the DIR_ITEM/DIR_INDEX, key->offset will be right
+ * value while find index
+ * @location_key: location key of the struct btrfs_dir_item to match
+ * @name: the name to match
+ * @namelen: the length of name
+ * @file_type: the type of file to math
+ *
+ * Return 0 if no error occurred.
+ * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find
+ * DIR_ITEM/DIR_INDEX
+ * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF
+ * and DIR_ITEM/DIR_INDEX mismatch
+ */
+static int find_dir_item(struct btrfs_root *root, struct btrfs_key *key,
+ struct btrfs_key *location_key, char *name,
+ u32 namelen, u8 file_type)
+{
+ struct btrfs_path path;
+ struct extent_buffer *node;
+ struct btrfs_dir_item *di;
+ struct btrfs_key location;
+ char namebuf[BTRFS_NAME_LEN] = {0};
+ u32 total;
+ u32 cur = 0;
+ u32 len;
+ u32 data_len;
+ u8 filetype;
+ int slot;
+ int ret;
+
+ /* get the index by traversing all index */
+ if (key->type == BTRFS_DIR_INDEX_KEY && key->offset == (u64)-1) {
+ ret = find_dir_index(root, key->objectid,
+ location_key->objectid, &key->offset,
+ name, namelen, file_type);
+ if (ret)
+ ret = DIR_INDEX_MISSING;
+ return ret;
+ }
+
+ btrfs_init_path(&path);
+ ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
+ if (ret) {
+ ret = key->type == BTRFS_DIR_ITEM_KEY ? DIR_ITEM_MISSING :
+ DIR_INDEX_MISSING;
goto out;
}
di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
total = btrfs_item_size_nr(node, slot);
while (cur < total) {
- ret = DIR_ITEM_MISMATCH;
- name_len = btrfs_dir_name_len(node, di);
+ ret = key->type == BTRFS_DIR_ITEM_KEY ?
+ DIR_ITEM_MISMATCH : DIR_INDEX_MISMATCH;
+
+ len = btrfs_dir_name_len(node, di);
data_len = btrfs_dir_data_len(node, di);
btrfs_dir_item_key_to_cpu(node, di, &location);
- if (location.objectid != ref_key->objectid ||
- location.type != BTRFS_INODE_ITEM_KEY ||
- location.offset != 0)
+ if (location.objectid != location_key->objectid ||
+ location.type != location_key->type ||
+ location.offset != location_key->offset)
goto next;
filetype = btrfs_dir_type(node, di);
- if (imode_to_type(mode) != filetype)
+ if (file_type != filetype)
goto next;
- if (cur + sizeof(*di) + name_len > total ||
- name_len > BTRFS_NAME_LEN) {
+ if (len > BTRFS_NAME_LEN) {
+ len = BTRFS_NAME_LEN;
warning("root %llu %s[%llu %llu] name too long %u, trimmed",
- root->objectid,
- key->type == BTRFS_DIR_ITEM_KEY ?
- "DIR_ITEM" : "DIR_INDEX",
- key->objectid, key->offset, name_len);
-
- if (cur + sizeof(*di) > total)
- break;
- len = min_t(u32, total - cur - sizeof(*di),
- BTRFS_NAME_LEN);
- } else {
- len = name_len;
+ root->objectid,
+ key->type == BTRFS_DIR_ITEM_KEY ?
+ "DIR_ITEM" : "DIR_INDEX",
+ key->objectid, key->offset, len);
}
-
- read_extent_buffer(node, namebuf, (unsigned long)(di + 1), len);
+ read_extent_buffer(node, namebuf, (unsigned long)(di + 1),
+ len);
if (len != namelen || strncmp(namebuf, name, len))
goto next;
ret = 0;
goto out;
next:
- len = sizeof(*di) + name_len + data_len;
+ len += sizeof(*di) + data_len;
di = (struct btrfs_dir_item *)((char *)di + len);
cur += len;
}
- if (ret == DIR_ITEM_MISMATCH)
- error(
- "root %llu INODE %s[%llu %llu] and %s[%llu %llu] mismatch namelen %u filename %s filetype %d",
- root->objectid,
- ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF",
- ref_key->objectid, ref_key->offset,
- key->type == BTRFS_DIR_ITEM_KEY ?
- "DIR_ITEM" : "DIR_INDEX",
- key->objectid, key->offset, namelen, name,
- imode_to_type(mode));
+
out:
btrfs_release_path(&path);
return ret;
int mode)
{
struct btrfs_key key;
+ struct btrfs_key location;
struct btrfs_inode_ref *ref;
char namebuf[BTRFS_NAME_LEN] = {0};
u32 total;
u32 len;
u32 name_len;
u64 index;
- int ret, err = 0;
+ int ret;
+ int err = 0;
+
+ location.objectid = ref_key->objectid;
+ location.type = BTRFS_INODE_ITEM_KEY;
+ location.offset = 0;
ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
total = btrfs_item_size_nr(node, slot);
key.objectid = ref_key->offset;
key.type = BTRFS_DIR_INDEX_KEY;
key.offset = index;
- ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+ ret = find_dir_item(root, &key, &location, namebuf, len, mode);
err |= ret;
/* Find related dir_item */
key.objectid = ref_key->offset;
key.type = BTRFS_DIR_ITEM_KEY;
key.offset = btrfs_name_hash(namebuf, len);
- ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+ ret = find_dir_item(root, &key, &location, namebuf, len, mode);
err |= ret;
len = sizeof(*ref) + name_len;
int mode)
{
struct btrfs_key key;
+ struct btrfs_key location;
struct btrfs_inode_extref *extref;
char namebuf[BTRFS_NAME_LEN] = {0};
u32 total;
int ret;
int err = 0;
+ location.objectid = ref_key->objectid;
+ location.type = BTRFS_INODE_ITEM_KEY;
+ location.offset = 0;
+
extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
total = btrfs_item_size_nr(node, slot);
key.objectid = parent;
key.type = BTRFS_DIR_INDEX_KEY;
key.offset = index;
- ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+ ret = find_dir_item(root, &key, &location, namebuf, len, mode);
err |= ret;
/* find related dir_item */
key.objectid = parent;
key.type = BTRFS_DIR_ITEM_KEY;
key.offset = btrfs_name_hash(namebuf, len);
- ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode);
+ ret = find_dir_item(root, &key, &location, namebuf, len, mode);
err |= ret;
len = sizeof(*extref) + name_len;