f2fs: introduce large directory support
Jaegeuk Kim [Thu, 27 Feb 2014 09:20:00 +0000 (18:20 +0900)]
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>

fs/f2fs/dir.c
fs/f2fs/f2fs.h
fs/f2fs/inode.c
include/linux/f2fs_fs.h

index 1cf90f7..65b5919 100644 (file)
@@ -21,12 +21,12 @@ static unsigned long dir_blocks(struct inode *inode)
                                                        >> PAGE_CACHE_SHIFT;
 }
 
-static unsigned int dir_buckets(unsigned int level)
+static unsigned int dir_buckets(unsigned int level, int dir_level)
 {
        if (level < MAX_DIR_HASH_DEPTH / 2)
-               return 1 << level;
+               return 1 << (level + dir_level);
        else
-               return 1 << ((MAX_DIR_HASH_DEPTH / 2) - 1);
+               return 1 << ((MAX_DIR_HASH_DEPTH / 2 + dir_level) - 1);
 }
 
 static unsigned int bucket_blocks(unsigned int level)
@@ -65,13 +65,14 @@ static void set_de_type(struct f2fs_dir_entry *de, struct inode *inode)
        de->file_type = f2fs_type_by_mode[(mode & S_IFMT) >> S_SHIFT];
 }
 
-static unsigned long dir_block_index(unsigned int level, unsigned int idx)
+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) * bucket_blocks(i);
+               bidx += dir_buckets(i, dir_level) * bucket_blocks(i);
        bidx += idx * bucket_blocks(level);
        return bidx;
 }
@@ -153,10 +154,11 @@ static struct f2fs_dir_entry *find_in_level(struct inode *dir,
 
        f2fs_bug_on(level > MAX_DIR_HASH_DEPTH);
 
-       nbucket = dir_buckets(level);
+       nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
        nblock = bucket_blocks(level);
 
-       bidx = dir_block_index(level, le32_to_cpu(namehash) % nbucket);
+       bidx = dir_block_index(level, F2FS_I(dir)->i_dir_level,
+                                       le32_to_cpu(namehash) % nbucket);
        end_block = bidx + nblock;
 
        for (; bidx < end_block; bidx++) {
@@ -485,10 +487,11 @@ start:
        if (level == current_depth)
                ++current_depth;
 
-       nbucket = dir_buckets(level);
+       nbucket = dir_buckets(level, F2FS_I(dir)->i_dir_level);
        nblock = bucket_blocks(level);
 
-       bidx = dir_block_index(level, (le32_to_cpu(dentry_hash) % nbucket));
+       bidx = dir_block_index(level, F2FS_I(dir)->i_dir_level,
+                               (le32_to_cpu(dentry_hash) % nbucket));
 
        for (block = bidx; block <= (bidx + nblock - 1); block++) {
                dentry_page = get_new_data_page(dir, NULL, block, true);
index fed95d1..1259267 100644 (file)
@@ -205,6 +205,7 @@ struct f2fs_inode_info {
        struct inode vfs_inode;         /* serve a vfs inode */
        unsigned long i_flags;          /* keep an inode flags for ioctl */
        unsigned char i_advise;         /* use to give file attribute hints */
+       unsigned char i_dir_level;      /* use for dentry level for large dir */
        unsigned int i_current_depth;   /* use only in directory structure */
        unsigned int i_pino;            /* parent inode number */
        umode_t i_acl_mode;             /* keep file acl mode temporarily */
index 08d69c9..d518e37 100644 (file)
@@ -107,6 +107,7 @@ static int do_read_inode(struct inode *inode)
        fi->flags = 0;
        fi->i_advise = ri->i_advise;
        fi->i_pino = le32_to_cpu(ri->i_pino);
+       fi->i_dir_level = ri->i_dir_level;
 
        get_extent_info(&fi->ext, ri->i_ext);
        get_inline_info(fi, ri);
@@ -204,6 +205,7 @@ void update_inode(struct inode *inode, struct page *node_page)
        ri->i_flags = cpu_to_le32(F2FS_I(inode)->i_flags);
        ri->i_pino = cpu_to_le32(F2FS_I(inode)->i_pino);
        ri->i_generation = cpu_to_le32(inode->i_generation);
+       ri->i_dir_level = F2FS_I(inode)->i_dir_level;
 
        __set_inode_rdev(inode, ri);
        set_cold_node(inode, node_page);
index da74d87..df53e17 100644 (file)
@@ -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 */