diff options
| author |   Jaegeuk Kim <jaegeuk.kim@samsung.com> | 2014-02-27 18:20:00 +0900 |
|---|---|---|
| committer | Jaegeuk Kim <jaegeuk.kim@samsung.com> | 2014-02-27 19:56:09 +0900 |
| commit | 3843154598a00408f4214a68bd536fdf27b1df10 (patch) | |
| tree | e4e89b1bc769996bf72851baffd62194d9a48385 /include/linux/f2fs_fs.h | |
| parent | f2fs: remove costly bit operations for f2fs_find_entry (diff) | |
| download | wireguard-linux-3843154598a00408f4214a68bd536fdf27b1df10.tar.xz wireguard-linux-3843154598a00408f4214a68bd536fdf27b1df10.zip | |
f2fs: introduce large directory support
This patch introduces an i_dir_level field to support large directory.
Previously, f2fs maintains multi-level hash tables to find a dentry quickly
from a bunch of chiild dentries in a directory, and the hash tables consist of
the following tree structure as below.
In Documentation/filesystems/f2fs.txt,
----------------------
A : bucket
B : block
N : MAX_DIR_HASH_DEPTH
----------------------
level #0 | A(2B)
|
level #1 | A(2B) - A(2B)
|
level #2 | A(2B) - A(2B) - A(2B) - A(2B)
. | . . . .
level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
. | . . . .
level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)
But, if we can guess that a directory will handle a number of child files,
we don't need to traverse the tree from level #0 to #N all the time.
Since the lower level tables contain relatively small number of dentries,
the miss ratio of the target dentry is likely to be high.
In order to avoid that, we can configure the hash tables sparsely from level #0
like this.
level #0 | A(2B) - A(2B) - A(2B) - A(2B)
level #1 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
. | . . . .
level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
. | . . . .
level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)
With this structure, we can skip the ineffective tree searches in lower level
hash tables.
This patch adds just a facility for this by introducing i_dir_level in
f2fs_inode.
Signed-off-by: Jaegeuk Kim <jaegeuk.kim@samsung.com>
Diffstat (limited to 'include/linux/f2fs_fs.h')
| -rw-r--r-- | include/linux/f2fs_fs.h | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/include/linux/f2fs_fs.h b/include/linux/f2fs_fs.h index da74d878dc4f..df53e1753a76 100644 --- a/include/linux/f2fs_fs.h +++ b/include/linux/f2fs_fs.h @@ -183,7 +183,7 @@ struct f2fs_inode { __le32 i_pino; /* parent inode number */ __le32 i_namelen; /* file name length */ __u8 i_name[F2FS_NAME_LEN]; /* file name for SPOR */ - __u8 i_reserved2; /* for backward compatibility */ + __u8 i_dir_level; /* dentry_level for large dir */ struct f2fs_extent i_ext; /* caching a largest extent */ |