Hash List
- https://kjy8901.github.io/blog/2019/10/28/kernel_list.html
- pprev가 double pointer이므로 head의 사이즈를 줄일 수 있고 head를 직접 가리킬 수 있다

구조체 hlist_bl_head
- hlist와 같은데 first의 0번째 비트를 일종의 lock 변수로 사용한다
- modification을 위해 0번째 비트를 1로 set해야 한다

전역변수 hlist_bl_head 배열 in_lookup_hashtable[]
- inode lookup hash table
- 1024개 엔트리

전역 변수 hlist_bl_head 포인터 dentry_hashtable
- dcache 구현을 위한 hash table 전역 변수
- 전역 변수 d_hash_shift는 hash lookup을 위한 shift 값
- hash lookup은 dentry_hashtable[hash >> d_hash_shift]로 이루어짐

vfs_caches_init_early()
- in_lookup_hashtable의 각 엔트리에 대해서 first를 NULL로 초기화한다
- 함수 dcache_init_early()와 inode_init_early()를 이용해서 dcache, inode_cache hash table 메모리를 할당받는다

dcache_init_early()
- 전역 변수 hashdist가 0이 아니면 그냥 리턴
- hashdist는 NUMA이면 1이고 아니면 0으로 세팅되어있다. 커널 커맨드라인으로 변경 가능
- 함수 alloc_large_system_hash()를 이용해서 dcache를 위한 hash table 메모리를 할당받는다
- scale은 13, flag는 HASH_EARLY, HASH_ZERO이고 limit은 0이다
- numentries 인자 (dhash_entries)는 0으로 들어간다
- mask는 받아오지 않는다

inode_init_early()
- 전역 변수 hashdist가 0이 아니면 그냥 리턴
- 함수 alloc_large_system_hash()를 이용해서 inode cache를 위한 hash table 메모리를 할당받는다
- scale은 14, flag는 HASH_EARLY, HASH_ZERO이고 limit은 0이다
- numentries 인자 (ihash_entries)는 0으로 들어간다
- mask는 i_hash_mask로 받아온다

alloc_large_system_hash()
- 인자들을 받아서 hash table을 위한 메모리를 할당받는다
- 인자로 table name, bucket size, numentries, scale, flags, low_limit, high_limit을 받는다
- 출력으로 hash shift, hash mask가 있으며 할당한 hash table 메모리 주소를 리턴한다

- numentries가 0이면 새로 엔트리 수를 계산한다
    - 커널 페이지 수에서 arch_reserved_kernel_pages()를 빼서 numentries를 계산한다
    - 페이지 크기가 1MB보다 작으면 numentries를 1MB 단위로 2의 승수 단위로 올린다
        - 4KB 단위인 경우 커널 페이지 총 크기가 4KB 단위이므로 1MB로 올림하고, 다시 2의 승수로 올림한 뒤 4KB 단위로 나누어서 numentries를 구한다
    - 시스템 메모리가 커서 numentries가 64G보다 크면 64G보다 4배씩 numentries가 커질 때마다 scale을 1씩 증가시킨다. 이러면 결국 엔트리수가 제한된다.
    - numentries를 page 사이즈 만큼 곱하고 2^scale 만큼 나눈다
    - 즉 2^scale 바이트 당 entry 1개로 엔트리 수를 제한
    - flag 인자에 HASH_SMALL가 on이면 numentries를 최소 1 << *_hash_shift 로 맞춰준다
    - HASH_SMALL가 on인데 HASH_EARLY가 off이면 경고를 출력한다
    - flag 인자에 HASH_SMALL가 off이고 numentries x bucketsize < PAGE_SIZE 이면 numentries = PAGE_SIZE/bucketsize로 맞춘다 (즉 테이블 사이즈를 최소 페이지 사이즈로 맞춤)

- numentries를 2의 승수로 올림한다
- max_limit = 0이면 총 메모리의 1/16로 테이블 사이즈를 제한한다
- numentries를 max_limit, low_limit으로 제한한다
- numentries에 로그를 취해서 log2qty를 계산한다
- bucket size << log2qty를 size로 놓고 memblock으로 테이블 메모리를 할당 요청한다
- 여기서 HASH_ZERO인 경우 메모리를 zeroing하고 아니면 하지 않는다
- 할당을 실패하면 log2qty를 1 감소시키고 size를 계산해서 다시 할당 요청한다 (엔트리 개수 절반 감소)
- 단 요청 크기가 페이지 사이즈보다는 커야 재요청한다

- 최종적으로 할당 실패하면 커널 패닉을 일으킨다
- 할당 성공하면 테이블 이름, 엔트리 수, order (버디 시스템에서 메모리를 관리하는 단위로 연속된 페이지들을 2의 승수 단위로 묶어서 관리한다), 페이지 크기를 로그에 출력한다

- _hash_shift에 log2qty를 전달한다
- _hash_mask에 (1 << log2qty) - 1을 전달한다

- 할당받은 테이블 메모리 주소를 리턴하고 종료

Exception table 개념
- http://jake.dothome.co.kr/exception-table/
- http://jake.dothome.co.kr/arm64-fault/
- 커널이 프로세스 페이지를 읽다가 에러가 발생한 경우 exception handler에서 fixup을 수행할 수 있도록 만든 테이블
- 커널 코드 중 프로세스 페이지를 access하는 커널 API를 사용하는 경우 해당 코드의 주소와 (insn) 해당 API의 fixup 코드의 주소를 exception table entry로 만들어서 exception table 영역에 저장한다
- Fault handler에서 fault 발생 주소가 exception table entry의 insn 주소와 같으면 fixup을 수행한다
- Exception table은 현재 RO 영역과 합쳐져 있다
- include/asm-generic/vmlinux.lds.h : RO_EXCEPTION_TABLE

처리 과정
- vector table kernel_ventry 1, h, 64, sync = el1h_64_sync 발생
- entry_handler 1, h, 64, sync = el1h_64_sync_handler() 수행
- el1h_64_sync_handler() 에서 el1_abort() 수행
- do_mem_abort() 수행
- inf->fn() = do_page_fault() 수행 (함수 위 fault_info[] 테이블 참조)
- __do_kernel_fault() 수행
- fixup_exception() 수행
- search_exception_tables() 함수로 exception table entry의 fixup search
- regs->pc를 fixup code로 변경하고 리턴하여 fixup code 수행하도록 함

참조 : copy_from_user()
- 커널에서 유저 공간에 잠시 접근하게 한 후 데이터를 유저 공간에서 카피한다
- SW적으로 TTBR0_EL1을 조정해서 통제하는 방법과 HW적으로 PAN 기능을 사용하는 방식이 존재함
- 최근 패치에서는 PAN 기능을 쓰는 패치는 사라짐
- https://github.com/torvalds/linux/commit/7cf283c7bd6260ae43a74cd213f5ec9d665a19b5
- 대신 LDTR, STTR 명령어를 사용하는 듯함 —> PAN이 켜져 있어도 유저 공간 접근 가능
- UAO는 LDTR, STTR을 LDR, STR로 바꿔주는 역할임
- https://developer.arm.com/documentation/102376/0100/Permissions-attributes
- https://developer.arm.com/documentation/ddi0595/2021-06/AArch64-Registers/UAO--User-Access-Override

sort_main_extable()
- exception table sorting을 수행한다
- 전역 변수 main_extable_sort_needed = 1일 때만 수행된다. 디폴트는 main_extable_sort_needed = 1 이지만 빌드 타임시 테이블이 이미 정렬되어 있으면 0으로 변경된다
- exception table entry는 구조체 exception_table_entry로 정의되고 이는 insn, fixup 두 개의 int 변수로 구성된다
- exception table 영역은 링크 스크립트에 __ex_table 영역에 정의되어 있고 시작은 __start___ex_table, 끝은 __stop___ex_table로 구성된다
- main_extable_sort_needed = 1 이고 __start___ex_table < __stop___ex_table 인 경우 정렬을 수행한다
- 정렬은 sort_extable() 함수로 수행된다

sort_extable()
- 인자로 exception table entry start, finish를 받아서 insn 기준으로 entry를 정렬한다
- 함수 sort()를 사용해서 sorting을 수행한다