paging init() 분석 중

- swappder_pg_dir은 kernel image 내에 정의되어 있음 (링커 스크립트)
- swapper_pg_dir의 물리주소에 대한 임시 fixmap 가상 주소를 만들어서 받아온다 (pgd_set_fixmap)
- 받아온 가상 주소를 이용해서 map_kernel() 수행

map_kernel()
- vm_struct라는 구조체가 있음
- rodata_enable가 참이면 커널 페이지 attribute를 ROX로 하고 아니면 EXEC로 설정
- arm64 cpu가 bti를 지원하면 커널 텍스트 페이지를 guard page로 설정한다
- map_kernel_segment() 함수를 수행해서 page table를 생성?
- 분석 중

map_kernel_segment()
- fixmap으로 임시할당 받은 pgdp 가상주소, 가상/물리 시작주소, 크기, 페이지 attribute, vm_struct 구조체와 flag 등을 인수로 받아서 mapping하는 함수인듯
- __create_pgd_mapping() 함수로 pgdp에 pgd를 mapping한다
- 분석 중

__create_pgd_mapping()
- pgdir 주소를 받아서 pgd mapping을 생성하는 함수
- 가상 주소 시작에서 크기만큼 pgd entry에 하나씩 매핑한다
- 이 때 매핑을 위해서 함수 alloc_init_pud()를 사용한다
- 분석 중

alloc_init_pud()
- pgd entry에 써있는 물리주소를 읽어온다
- 만약 물리주소가 써있는게 없으면 early_pgtable_alloc() 함수를 실행해서 물리 주소 페이지 하나를 memblock에서 초기화해서 받아오고 pgd entry에 해당 물리주소를 적는다
- pgd entry에서 시작해서 가상주소 addr에 해당하는 pud 물리주소를 찾고, 해당 물리주소에 fixmap을 이용해서 임시 가상 주소 pudp를 할당받는다
- 할당받은 pudp로부터 size만큼 pud entry 하나씩 alloc_init_cont_pmd() 함수를 이용하여  mapping한다
- 이후 pud_clear_fixmap()으로 가상주소 pudp를 해제하고 리턴한다

early_pgtable_alloc(int shift)
- 인자 shift는 function pointer 사용을 위해서 그냥 존재하는 것으로 보인다
- 한 페이지를 memblock으로부터 할당 받아서 reserve 받고 해당 영역을 fixmap을 이용해서 0으로 초기화하여 그 물리주소를 리턴한다

alloc_init_cont_pmd()
- pud entry가 가리키는 물리주소가 없으면 early_pgtable_alloc()으로 페이지 하나를 memblock으로 할당받고 초기화한 후 그 물리주소를 pud entry가 가리키게 한다
- 매핑 가상주소에 해당하는 pmd entry를 구하고 init_pmd() 함수를 이용해서 pmd entry를 하나씩 초기화한다

init_pmd()
- pmd entry 물리주소에 fixmap을 이용해서 임시 가상주소 pmdp를 받는다
- alloc_init_cont_pte()를 이용해서 pmdp가 가리키는 pte entry를 하나씩 초기화한다
- pmdp 가상주소를 해제한다

alloc_init_cont_pte()
- pmd entry가 가리키는 물리주소가 없으면 fixmap을 이용해서 임시 가상주소 pte_phys를 할당받아 0으로 초기화한후 그 물리주소를 pdm entry가 가리키게 한다
- pdm entry로부터 pte를 하나씩 init_pte()를 이용해서 초기화한다

init_pte()
- pte entry의 물리주소에 fixmap을 이용해서 임시 가상주소 ptep를 받는다
- ptep를 이용해서 각 pte에 mapping하고자 하는 물리주소의 page frame number와 메모리 attribute를 기록한다
- ptep 임시주소를 해제한다

do while 문 loop 분석 필요함
- 4-level table에 더 많은 loop 단계가 있음

==============================================

qspinlock 스터디
- https://www.programmersought.com/article/69965557777/

kernel/locking/qspinlock.c

queued_spin_lock_slowpath()
- CPU 개수가 2^14 이하인 것 확인 --> 아니면 버그
- pending bit가 1이면 일단 잠시 기다린다
- 그래도 contention이 있으면 queueing으로 점프한다
- contention이 없으면 atomic exchange를 이용해서 pending을 건다
- concurrent locker가 있을 수 있으므로 old value에 lock 또는 pending이 있는지 보고 있으면 queuing으로 점프
- 특히 old value에 lock은 있는데 pending이 없다면 무한 루프 문제가 발생 가능하므로 pending을 다시 풀어준다
- pending 상태이므로 lock이 풀릴 때까지 spinning하면서 기다린다
- lock이 풀렸으면 pending bit을 풀고 lock bit을 set한 다음 lock을 잡고 리턴한다
- queuing으로 점프하는 경우 qnodes[0] mcs lock의 count를 increment한다
- 그리고 cpu id와 qnode index를 이용해서 tail값을 계산한다
- 만약 index가 3보다 크면 그냥 전통적인 spinlock을 수행한다. 즉 그냥 lock 잡을 때까지 busy waiting한다. 잡으면 release로 점프
- 아니면 msc lock을 구해서 초기화한다. 초기화하기 전에 barrier()로 컴파일러 배리어를 수행한다.
- 초기화는 locked = 0, next = NULL로 하여 이루어진다
- locked = 0은 아직 mcs lock이 풀리는 않았다는 것이고 next는 자신보다 바로 뒤에서 기다리는 mcs node를 가리킨다
- locked = 1이 되면 mcs lock은 풀린다
- 그 사이에 lock이 풀렸을 수도 있으니 lock을 다시 시도해보고 성공하면 release로 점프한다
- 아니면 이제 queue에 들어가서 줄 서야 한다. 이를 위해 lock의 tail을 업데이트해야 하므로 smp_wmb() 배리어를 수행하여 mcs node가 초기화 되었음을 확실히 한다
- qspinlock의 tail이 자신을 가리키도록 atomic exchange로 업데이트한다
- next는 NULL로 만든다
- old tail에 다른 mcs node가 있으면 해당 노드 뒤로 줄서야 한다
- 그러므로 old tail에서 mcs node값을 읽어서 (prev), prev->next를 나 자신을 가리키게 한다
- 그리고 mcs lock spinning에 들어간다. 나 자신 mcs node의 locked 변수가 1이 될 때까지 spinning을 수행한다 (나 바로 앞의 mcs node가 qspinlock owner가 될 때 풀어준다)
- mcs node의 locked 변수가 1이 되면 mcs lock은 풀린 것이다. 곧 내가 owner가 될 가능성이 크므로 내 바로 뒤에 있는 mcs node를 prefetch하여 cache에 올려 놓는다. (locked = 1로 업데이트해줘야 하기 때문)
- mcs lock이 풀렸으니 이제 qspinlock의 lock/pending이 모두 풀릴 때까지 spinning하며 기다린다
- qspinlock의 lock/pending도 모두 풀렸으면 이제 owner가 될 차례임
- 내 뒤에 또 기다리고 있는 mcs node가 있는지 확인하기 위해 qspinlock의 tail과 내 tail을 비교함
- 같으면 뒤에 아무도 없으므로 qspinlock의 tail을 0으로 만든다
- atomic compare exchange로 qspinlock 값을 1로 만들고 release로 점프
- 뒤에 기다리고 있는 mcs node가 있으면 qspinlock의 lock bit을 1로 set
- next가 NULL이면 node->next를 뒤에 기다리는 msc node를 가리킬 때까지 waiting (뒤에 있는 노드가 업데이트 해줌)
- 뒤에 있는 mcs node의 locked를 1로 setting하여 mcs lock을 풀어준다
- 이후 release로 이동하여 qnodes[0] mcs.count를 decrement하고 리턴

queued_spin_unlock()
- store release로 qspinlock의 locked byte를 0으로 만든다

barrier()가 initialization 이전에만 있어도 되는 이유
- preemption은 disable되어 있으므로 같은 cpu의 interrupt/nmi 등 끼리만 경쟁할 수 있는데 얘들은 같은 mcs node를 잡아도 상관없음 --> 어차피 먼저 수행되는 애가 spinlock을 완전히 끝나고 나가야 같은 mcs lock을 잡은 다른 애들이 수행될 것이기 때문

smp_wmb()
- store release에 해당됨

paravirtual spinlock
- Virtual machine 시스템에서 vCPU가 spinlock을 잡을 때 사용하는 기법인 것으로 보임
- https://lwn.net/Articles/289039/

361 line에서 pending을 지워주는 이유
- 535 line에서 자기가 마지막일 경우 (0, 0, 1)로 만들고 release로 점프한다
- 그런데 352에서 다른 애가 pending bit을 체크해버리면 cmpxchg가 실패해서 release로 갈 수 없고 551 line에서 새로운 노드가 올 때까지 무한 루프에 걸린다
- 따라서 pending bit을 해제해야 한다