• Jaegeuk Kim's avatar
    f2fs: introduce large directory support · 38431545
    Jaegeuk Kim authored
    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: default avatarJaegeuk Kim <jaegeuk.kim@samsung.com>
    38431545
f2fs.h 40.4 KB