[Linux/Ext4] Order of file list of the directory in ext4

ext4에서 'readdir' system call을 이용해서 directory를 읽으면, directory가 가지는 file list를 읽을 수 있다.

이때, 읽히는 file의 순서는 어떻게 정해지는가?

경험적으로 대부분의 개발자라면, 이 순서가 일정하지 않다는 것을 알고 있을 것이다.

이 부분에 대해서 좀더 깊게 살펴보기도 하자.

linux kernel에서 ext4 관련 부분의 코드를 분석해 보면 아래의 사실들을 알아 낼 수 있다.

- ext4는 directory내에서 file search등을 빠르게 하기 위해서 htree(hash tree)를 이용한다.

- 이때 사용되는 hash값의 order가 곧 readdir 로 읽어들이는 file의 order이다.

- hash 값은 'HashFunc(<hash algorithm>, <hash seed>, <file name>)"을 통해서 구한다.

- hash algorithm과 hash seed의 경우, super block에 적힌 값을 사용하면, 없는 경우 default 값을 사용한다.

- directory내의 각 file의 hash값은 directory file의 'f_pos'값 (file position값)으로 사용된다.

즉, super block에 적힌 hash algorithm과 hash seed에 따라서, directory가 같은 이름들의 file을 가지고 있다고 하더라도, readdir이 읽어 오는 file의 순서가 달라진다는 말이다.

실제로 이를 확인하기 위해서는 'dumpe2fs' 와 'debugfs' tool을 사용할 수 있다.

Assumption : '/' 가 '/dev/sda1' 에 mount 되어 있음.

>$ sudo dumpe2fs -h /dev/sda1
...
Default directory hash:   half_md4     <== hash algorithm
Directory Hash Seed:      5841608b-14fe-405e-8d28-76236cc8c496  <== seed (UUID format)
...

이후 아래와 같은 방법으로 각 file name에 해당하는 hash 값을 알 수 있다.

>$ sudo debugfs /dev/sda1
dx_hash -h half_md4 -s c773a461-6150-4fe8-abe8-96acc6086d7e vmlinuz
Hash of /vmlinuz is 0xf097024e (minor 0x0)

추가적으로 'ls -f' 를 사용하면, sorting되지 않은 순서로 file list를 읽을 수 있는데, 이 순서가 바로, hash 값에 따른 순서 즉 readdir로 읽어 들이는 순서이다.

이를 확인하기 위해서는

>$ rm dxhashs; for e in $(ls -f /); do echo "dx_hash -h half_md4 -s 5841608b-14fe-405e-8d28-76236cc8c496 $e" >> dxhashs; done; sudo debugfs -f dxhashs /dev/sda1 | grep "Hash of" | cut -d' ' -f5

와 같이 하면, 정확하게 ascending order로 출력되는 hash 값을 볼 수 있다.

즉 'ls -f' 를 통해서 보여지는 file name의 순서가 hash값이 ascending order라는 뜻이고, hash 값이 ascending order에 따라 읽어 들이는 file name의 순서가 'readdir'로 읽어 들이는 순서와 일치한다.

Hash Seed를 바꾸는 방법은 아래와 같다.(간단한데, 나중에 분명히 잊어 먹을테니...)

/dev/sda2 가 /opt에 mount되어 있고, ext4 file system인 경우.

># unmount /opt
># debugfs -w /dev/sda2
>debugfs: ssv hash_seed ceeba115-4091-4b79-aac9-36ccee4a5349  <= UUID of hash seed to change