aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorChao Yu <chao2.yu@samsung.com>2016-03-16 11:05:14 +0800
committerluca020400 <luca.stefani.ge1@gmail.com>2016-04-04 17:17:56 +0200
commit1c8ee3ba2c07761e40351d1c8f3d49e8e8f8f7d1 (patch)
tree534c8057724ae5462b0949a7e51ae812a7ea3037
parent31365f7046d3458705dd9ccd398825a978d6d8ba (diff)
downloadandroid_external_f2fs-tools-1c8ee3ba2c07761e40351d1c8f3d49e8e8f8f7d1.tar.gz
android_external_f2fs-tools-1c8ee3ba2c07761e40351d1c8f3d49e8e8f8f7d1.tar.bz2
android_external_f2fs-tools-1c8ee3ba2c07761e40351d1c8f3d49e8e8f8f7d1.zip
fsck.f2fs: check dirent position
This patch enables fsck.f2fs to detect incorrect position where dirent locates in an hierarchical hash structure directory. Signed-off-by: Chao Yu <chao2.yu@samsung.com> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
-rw-r--r--fsck/fsck.c117
-rw-r--r--fsck/fsck.h2
-rw-r--r--include/f2fs_fs.h3
3 files changed, 108 insertions, 14 deletions
diff --git a/fsck/fsck.c b/fsck/fsck.c
index a4922fb..acdd5d4 100644
--- a/fsck/fsck.c
+++ b/fsck/fsck.c
@@ -565,12 +565,13 @@ void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
u32 *blk_cnt, struct node_info *ni)
{
struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
- struct child_info child = {2, 0, 0};
+ struct child_info child = {2, 0, 0, 0};
enum NODE_TYPE ntype;
u32 i_links = le32_to_cpu(node_blk->i.i_links);
u64 i_blocks = le64_to_cpu(node_blk->i.i_blocks);
child.p_ino = nid;
child.pp_ino = le32_to_cpu(node_blk->i.i_pino);
+ child.dir_level = node_blk->i.i_dir_level;
struct extent_info i_extent;
unsigned int idx = 0;
int need_fix = 0;
@@ -679,7 +680,8 @@ void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
}
/* check data blocks in inode */
- for (idx = 0; idx < ADDRS_PER_INODE(&node_blk->i); idx++) {
+ for (idx = 0; idx < ADDRS_PER_INODE(&node_blk->i);
+ idx++, child.pgofs++) {
block_t blkaddr = le32_to_cpu(node_blk->i.i_addr[idx]);
if (blkaddr != 0) {
@@ -712,19 +714,31 @@ void fsck_chk_inode_blk(struct f2fs_sb_info *sbi, u32 nid,
else
ASSERT(0);
- if (blkaddr != 0) {
- ret = fsck_chk_node_blk(sbi, &node_blk->i,
- blkaddr,
- NULL, ftype, ntype, blk_cnt, &child,
- &i_extent);
- if (!ret) {
- *blk_cnt = *blk_cnt + 1;
- } else if (config.fix_on) {
+ if (blkaddr == 0x0)
+ goto skip;
+
+ ret = fsck_chk_node_blk(sbi, &node_blk->i,
+ blkaddr,
+ NULL, ftype, ntype, blk_cnt, &child,
+ &i_extent);
+ if (!ret) {
+ *blk_cnt = *blk_cnt + 1;
+ } else if (ret == -EINVAL) {
+ if (config.fix_on) {
node_blk->i.i_nid[idx] = 0;
need_fix = 1;
FIX_MSG("[0x%x] i_nid[%d] = 0", nid, idx);
}
+skip:
+ if (ntype == TYPE_DIRECT_NODE)
+ child.pgofs += ADDRS_PER_BLOCK;
+ else if (ntype == TYPE_INDIRECT_NODE)
+ child.pgofs += ADDRS_PER_BLOCK * NIDS_PER_BLOCK;
+ else
+ child.pgofs += ADDRS_PER_BLOCK *
+ NIDS_PER_BLOCK * NIDS_PER_BLOCK;
}
+
}
if (i_extent.len || i_extent.fail) {
ASSERT_MSG("ino: 0x%x has wrong ext: untouched=%d, overlap=%d",
@@ -808,7 +822,7 @@ int fsck_chk_dnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
child->p_ino = nid;
child->pp_ino = le32_to_cpu(inode->i_pino);
- for (idx = 0; idx < ADDRS_PER_BLOCK; idx++) {
+ for (idx = 0; idx < ADDRS_PER_BLOCK; idx++, child->pgofs++) {
block_t blkaddr = le32_to_cpu(node_blk->dn.addr[idx]);
if (blkaddr == 0x0)
@@ -841,9 +855,9 @@ int fsck_chk_idnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
int need_fix = 0, ret;
int i = 0;
- for (i = 0 ; i < NIDS_PER_BLOCK; i++) {
+ for (i = 0; i < NIDS_PER_BLOCK; i++) {
if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
- continue;
+ goto skip;
ret = fsck_chk_node_blk(sbi, inode,
le32_to_cpu(node_blk->in.nid[i]), NULL,
ftype, TYPE_DIRECT_NODE, blk_cnt, child,
@@ -858,6 +872,8 @@ int fsck_chk_idnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
need_fix = 1;
FIX_MSG("Set indirect node 0x%x -> 0\n", i);
}
+skip:
+ child->pgofs += ADDRS_PER_BLOCK;
}
}
@@ -882,7 +898,7 @@ int fsck_chk_didnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
for (i = 0; i < NIDS_PER_BLOCK; i++) {
if (le32_to_cpu(node_blk->in.nid[i]) == 0x0)
- continue;
+ goto skip;
ret = fsck_chk_node_blk(sbi, inode,
le32_to_cpu(node_blk->in.nid[i]), NULL,
ftype, TYPE_INDIRECT_NODE, blk_cnt, child,
@@ -897,6 +913,8 @@ int fsck_chk_didnode_blk(struct f2fs_sb_info *sbi, struct f2fs_inode *inode,
need_fix = 1;
FIX_MSG("Set double indirect node 0x%x -> 0\n", i);
}
+skip:
+ child->pgofs += ADDRS_PER_BLOCK * NIDS_PER_BLOCK;
}
}
@@ -1022,6 +1040,73 @@ static int f2fs_check_hash_code(struct f2fs_dir_entry *dentry,
return 0;
}
+static unsigned int dir_buckets(unsigned int level, int dir_level)
+{
+ if (level + dir_level < MAX_DIR_HASH_DEPTH / 2)
+ return 1 << (level + dir_level);
+ else
+ return MAX_DIR_BUCKETS;
+}
+
+static unsigned int bucket_blocks(unsigned int level)
+{
+ if (level < MAX_DIR_HASH_DEPTH / 2)
+ return 2;
+ else
+ return 4;
+}
+
+static unsigned long dir_block_index(unsigned int level,
+ int dir_level, unsigned int idx)
+{
+ unsigned long i;
+ unsigned long bidx = 0;
+
+ for (i = 0; i < level; i++)
+ bidx += dir_buckets(i, dir_level) * bucket_blocks(i);
+ bidx += idx * bucket_blocks(level);
+ return bidx;
+}
+
+static int __get_current_level(int dir_level, u32 pgofs)
+{
+ unsigned int bidx = 0;
+ int i;
+
+ for (i = 0; i < MAX_DIR_HASH_DEPTH; i++) {
+ bidx += dir_buckets(i, dir_level) * bucket_blocks(i);
+ if (bidx > pgofs)
+ break;
+ }
+ return i;
+}
+
+static int f2fs_check_dirent_position(u8 *name, u16 name_len, u32 pgofs,
+ u8 dir_level, u32 pino)
+{
+ f2fs_hash_t namehash = f2fs_dentry_hash(name, name_len);
+ unsigned int nbucket, nblock;
+ unsigned int bidx, end_block;
+ int level;
+
+ level = __get_current_level(dir_level, pgofs);
+
+ nbucket = dir_buckets(level, dir_level);
+ nblock = bucket_blocks(level);
+
+ bidx = dir_block_index(level, dir_level,
+ le32_to_cpu(namehash) % nbucket);
+ end_block = bidx + nblock;
+
+ if (pgofs >= bidx && pgofs < end_block)
+ return 0;
+
+ ASSERT_MSG("Wrong position of dirent pino:%u, name:%s, level:%d, "
+ "dir_level:%d, pgofs:%u, correct range:[%u, %u]\n",
+ pino, name, level, dir_level, pgofs, bidx, end_block - 1);
+ return 1;
+}
+
static int __chk_dots_dentries(struct f2fs_sb_info *sbi,
struct f2fs_dir_entry *dentry,
struct child_info *child,
@@ -1195,6 +1280,10 @@ static int __chk_dentries(struct f2fs_sb_info *sbi, struct child_info *child,
if (f2fs_check_hash_code(dentry + i, name, name_len, encrypted))
fixed = 1;
+ if (max == NR_DENTRY_IN_BLOCK)
+ f2fs_check_dirent_position(name, name_len, child->pgofs,
+ child->dir_level, child->p_ino);
+
DBG(1, "[%3u]-[0x%x] name[%s] len[0x%x] ino[0x%x] type[0x%x]\n",
fsck->dentry_depth, i, name, name_len,
le32_to_cpu(dentry[i].ino),
diff --git a/fsck/fsck.h b/fsck/fsck.h
index aa3e8cf..b92a1e0 100644
--- a/fsck/fsck.h
+++ b/fsck/fsck.h
@@ -22,7 +22,9 @@ struct orphan_info {
struct child_info {
u32 links;
u32 files;
+ u32 pgofs;
u8 dots;
+ u8 dir_level;
u32 p_ino; /*parent ino*/
u32 pp_ino; /*parent parent ino*/
};
diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
index 40b665d..9006228 100644
--- a/include/f2fs_fs.h
+++ b/include/f2fs_fs.h
@@ -828,6 +828,9 @@ typedef __le32 f2fs_hash_t;
/* MAX level for dir lookup */
#define MAX_DIR_HASH_DEPTH 63
+/* MAX buckets in one level of dir */
+#define MAX_DIR_BUCKETS (1 << ((MAX_DIR_HASH_DEPTH / 2) - 1))
+
#define SIZE_OF_DIR_ENTRY 11 /* by byte */
#define SIZE_OF_DENTRY_BITMAP ((NR_DENTRY_IN_BLOCK + BITS_PER_BYTE - 1) / \
BITS_PER_BYTE)