커널 hashtable (dentry)

상황

open O_CREAT 시 생성되는 dentry 가 언제 커널 hashtable (dentry_hashtable) 에
들어가는지 궁금

• https://www.linuxjournal.com/article/7124

목적

새로 생성되는 dentry 의 hash 값을 직접 계산하고, hash bucket 을 구해서,
안에 새로 생성된 dentry 가 잘 들어가 있는지 따라가봤습니다.

새로 알게된 내용

hash 계산은 hash_name 함수가 수행하고, link_path_walk 시 호출하고 있습니다.
함수 입력으로는 name 과 'parent' dentry 가 사용됩니다.

• 아직 d_alloc_parallel 함수 (dentry 생성) 호출 전이므로 parent dentry 를 사용
• hash 계산과정에서 parent dentry 는 salt 로 사용

두 개의 task 에서 동일 name, 'parent' dentry 에 대해 d_alloc_parallel 함수를 부르면
중복 dentry 가 생성될수 있으므로, 같은 hash 값 을 사용하는 in_lookup_hashtable 를 이용해
dentry 중복생성을 방지하고 있습니다.

hash -- d_hash() --> dentry hash bucket
hash -- in_lookup_hash() --> in_lookup dentry hash bucket

d_alloc_parallel 함수는 in_lookup_hashtable 에서 hash 값이 일치하는 dentry 를 발견하면,
만들었던 dentry 는 해제시키고, 발견한 dentry 를 리턴합니다.

hash_name 의 개략적인 동작

1) name 은 "8바이트 단위" 로 나눠가며 0x00(NUL), 0x2f('/') 가 있는지 체크
2) 둘다 없으면 HASH_MIX 수행, 둘중 하나라도 있으면 루프 종료
3) 0x00(NUL), 0x2f('/') 가 있는 8바이트는 마스크를 씌워서 0x00, 0x2f 를 제거하고 xor
4) 마지막으로 fold_hash

hash_name 예시

name "test2.txt" 와 parent dentry 0xffff9e6a4dfd9480 를 주면
hash 값은 0xc748277 가 나오게 됩니다.

root@user-virtual-machine:~/hash_name# ./hash_name
0x8080808080808000
bits : 0x7fff
adata : 0x8080808080808000, bdata : 0x0, mask : 0xff
x : 0xca6ed79f6fe6390f, y : 0xd033187d266340b9, hash : 0xc748277  <-- test2.txt 의 hash 값
root@user-virtual-machine:~/hash_name#

현재 열려있는 test2.txt 의 hash 값을 확인하면 동일한걸 알수 있습니다.

crash> struct dentry.d_parent ffff9e6a4dde6b40
  d_parent = 0xffff9e6a4dfd9480,   <-- parent dentry
crash> struct dentry.d_name ffff9e6a4dde6b40 -x
  d_name = {
    {
      {
        hash = 0xc748277,    <-- hash 값 동일
        len = 0x9
      },
      hash_len = 0x90c748277
    },
    name = 0xffff9e6a4dde6b78 "test2.txt"
  },
crash> 

hash 값을 d_hash 함수에 넣으면, hash bucket 을 구할수 있으며, 25508 번째 entry 입니다.

crash> p dentry_hashtable
dentry_hashtable = $1 = (struct hlist_bl_head *) 0xffff9e6b79740000
crash> p d_hash_shift
d_hash_shift = $2 = 13

crash> eval (0xc748277 >> 13)
hexadecimal: 63a4
    decimal: 25508

dcache hashtable entries 갯수는 524288 개로, 허용범위 내입니다.

Oct  2 16:24:04 user-virtual-machine kernel: [    0.071023] Dentry cache hash table entries: 524288 (order: 10, 4194304 bytes, linear)
Oct  2 16:24:04 user-virtual-machine kernel: [    0.071023] Inode-cache hash table entries: 262144 (order: 9, 2097152 bytes, linear)
Oct  2 16:24:04 user-virtual-machine kernel: [    0.071023] mem auto-init: stack:off, heap alloc:on, heap free:off
Oct  2 16:24:04 user-virtual-machine kernel: [    0.071023] software IO TLB: area num 128.
Oct  2 16:24:04 user-virtual-machine kernel: [    0.101919] Memory: 3880820K/4193716K available (20480K kernel code, 4150K rwdata, 12696K rodata, 4664K init, 17644K bss, 312636K reserved, 0K cma-reserved)

hash bucket 은 ffff9e6b79771d20 입니다.

crash> struct hlist_bl_head -o -x
struct hlist_bl_head {
  [0x0] struct hlist_bl_node *first;
}
SIZE: 0x8
crash> eval 8 * 25508
hexadecimal: 31d20
    decimal: 204064
    
crash> eval 0xffff9e6b79740000 + 0x31d20
hexadecimal: ffff9e6b79771d20

hash bucket 에 test2.txt dentry 가 잘 들어있음이 확인됬습니다.

crash> struct hlist_bl_head ffff9e6b79771d20
struct hlist_bl_head {
  first = 0xffff9e6a4dde6b48
}
crash> struct dentry.d_hash -o -x
struct dentry {
   [0x8] struct hlist_bl_node d_hash;   <-- anchor (container_of)
}
crash> eval 0xffff9e6a4dde6b48 - 0x8
hexadecimal: ffff9e6a4dde6b40

crash> struct dentry.d_name ffff9e6a4dde6b40 -x
  d_name = {
    {
      {
        hash = 0xc748277,
        len = 0x9
      },
      hash_len = 0x90c748277
    },
    name = 0xffff9e6a4dde6b78 "test2.txt"
  },
crash>

hash_name 예제코드 링크

hash 계산에 사용한 예제코드입니다.

• 계산 시 유의사항들은 주석에 적어두었습니다.

https://gitlab.com/feather973/hash_name

cf1. hash_name 이후

hash_name 이후 link_path_walk 는 다음 동작을 수행합니다.

1) 계산된 hash 값은 nd->last.hash_len 에 담습니다.
2) name 이 끝났으므로(NUL byte) walk_component 를 불러서 nd->last 에 대해 lookup 을 수행합니다.
3) dentry 가 없으므로 lookup_fast 는 실패하고, lookup_slow 을 탑니다.
4) lookup_slow 는 d_alloc_parallel 를 불러서 3가지 동작을 수행합니다.

• 신규 dentry 생성
• nd->last.hash_len 을 신규 dentry 의 hash 로 세팅
• 신규 dentry 를 "in_lookup_hashtable" 에 등록합니다.
  (아직 dentry hashtable 에 등록되지 않은 상태)

struct dentry *d_alloc_parallel(struct dentry *parent,
                const struct qstr *name,
                wait_queue_head_t *wq)
{
    unsigned int hash = name->hash;
    struct hlist_bl_head *b = in_lookup_hash(parent, hash);    <-- 이미 만든 dentry 인지 체크
....
    /*
     * No changes for the parent since the beginning of d_lookup().
     * Since all removals from the chain happen with hlist_bl_lock(),
     * any potential in-lookup matches are going to stay here until
     * we unlock the chain.  All fields are stable in everything
     * we encounter.
     */
    hlist_bl_for_each_entry(dentry, node, b, d_u.d_in_lookup_hash) {
        if (dentry->d_name.hash != hash)
            continue;
        if (dentry->d_parent != parent)
            continue;
        if (!d_same_name(dentry, parent, name))
            continue;
        hlist_bl_unlock(b);
        /* now we can try to grab a reference */
        if (!lockref_get_not_dead(&dentry->d_lockref)) {
            rcu_read_unlock();
            goto retry;
        }

        rcu_read_unlock();
        /*
         * somebody is likely to be still doing lookup for it;
         * wait for them to finish
         */
        spin_lock(&dentry->d_lock);
        d_wait_lookup(dentry);
        /*
         * it's not in-lookup anymore; in principle we should repeat
         * everything from dcache lookup, but it's likely to be what
         * d_lookup() would've found anyway.  If it is, just return it;
         * otherwise we really have to repeat the whole thing.
         */
        if (unlikely(dentry->d_name.hash != hash))
            goto mismatch;
        if (unlikely(dentry->d_parent != parent))
            goto mismatch;
        if (unlikely(d_unhashed(dentry)))
            goto mismatch;
        if (unlikely(!d_same_name(dentry, parent, name)))
            goto mismatch;
        /* OK, it *is* a hashed match; return it */
        spin_unlock(&dentry->d_lock);
        dput(new);   <-- 새로 만든건 해제
        return dentry;    <-- 이미 만든 dentry 이므로 새로 만들지 말고, 기존것을 리턴
    }
    rcu_read_unlock();
    /* we can't take ->d_lock here; it's OK, though. */
    new->d_flags |= DCACHE_PAR_LOOKUP;    
    new->d_wait = wq;
    hlist_bl_add_head_rcu(&new->d_u.d_in_lookup_hash, b);  <-- 만든적이 없는 dentry, in_lookup 에 등록한다.
    hlist_bl_unlock(b);
    return new;

cf2. dentry hashtable 에 등록

link_path_walk 리턴후, open_lask_lookups 에서 수행하게 됩니다.

lookup 상태인 dentry 가 확인되면

• ext4_lookup 을 부르고
• d_splice_alias --> d_add --> __d_rehash 과정을 거쳐 dentry_hashtable 에 등록되고,
• in_lookup_hashtable 에서 제거됩니다.

            test-4285    [000] ...1. 15273.716792: myprobe: (__d_rehash+0x0/0xc0)
            test-4285    [000] ...1. 15273.716813: <stack trace>
 => __d_rehash    <-- 5) dentry->d_inode 에 inode 넣고, dentry hashtable 에 등록
 => d_splice_alias   <-- 4) d_add
 => ext4_lookup.part.0
 => ext4_lookup    <-- 3) negative dentry (new dentry) 를 위한 inode 만들고 d_splice_alias
 => lookup_open.isra.0
 => open_last_lookups   <-- 2) link_path_walk 에서 생성된 dentry 를 갖고 lookup_open
 => path_openat     <-- 1) link_path_walk 와 open_last_lookups 가 번갈아서 호출
 => do_filp_open
 => do_sys_openat2
 => __x64_sys_openat
 => do_syscall_64
 => entry_SYSCALL_64_after_hwframe

static struct dentry *lookup_open(struct nameidata *nd, struct file *file,
                  const struct open_flags *op,
                  bool got_write)
{
....
    if (d_in_lookup(dentry)) {    <-- lookup 상태인 dentry
        struct dentry *res = dir_inode->i_op->lookup(dir_inode, dentry,
                                 nd->flags);   <-- ext4_lookup 호출
        d_lookup_done(dentry);    <-- in_lookup_hashtable 에서 제거
        if (unlikely(res)) {
            if (IS_ERR(res)) {
                error = PTR_ERR(res);
                goto out_dput;
            }
            dput(dentry);
            dentry = res;
        }
    }