[리눅스 커널] Scheduler - process address space switching

글의 참고

- http://www.wowotech.net/process_management/context-switch-tlb.html
- http://www.wowotech.net/memory_management/tlb-flush.html
- https://www.cnblogs.com/sky-heaven/p/17735177.html
- https://zhuanlan.zhihu.com/p/540717796
- https://zhuanlan.zhihu.com/p/528760035
- https://www.halolinux.us/kernel-reference/tlb-mode-mechanism-it-is-usually-invoked-whenever-the-kernel-modifies-a-page-table-entry-relative-to-the-kernel-mode-address-space.html
- https://www.jabperf.com/how-to-deter-or-disarm-tlb-shootdowns/
- https://www.educative.io/answers/what-is-tlb-shootdown
- https://www.geeksforgeeks.org/translation-lookaside-buffer-tlb-in-paging/
- https://medium.com/@om.nara/arm64-system-memory-fbf71dce37ee

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.
- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

- Overview

" process switching 에는 굉장히 많은 내용들이 포함되어 있다. 그래서, 이 글에서는 process switching 중에 TLB 는 어떻게 처리하는지에 포커싱한다.
 
 

- single-core TLB

" TLB 와 Cache 는 기본적으로 performance 향상을 위해서 만들어졌다. 프로세스가 data 및 instruction 을 실행하려면 반드시 RAM 에 접근해서 해당 데이터들과 명령어를 읽어와야 한다. 그런데 문제는 RAM 에 액세스하는 속도가 느리다는 것이다. 그래서, address traslation(VA->PA) 향상을 위해 page table 의 일부를 `Translation Lookaside Buffer(TLB)` 에 캐쉬한다. 이렇게 하면 CPU 가 data 및 instruction 을 RAM 이 아닌 캐쉬에서 액세스한다.
 
 
(1) lagacy address space switching 
 " context switch 가 발생하면 process 만 교체되는게 아니라 address space switching 도 같이 발생한다. 왜냐면 process 마다 사용하는 메모리가 다르기 때문이다(그리고 여기서 말하는 address space switching 은 page table 교체를 의미한다). 그런데 한 번 생각해보자. 예를 들어 process A 에서 process B 로 context switch 가 발생했다고 가정하자. 이 시점에 TLB 와 Cache 에는 process A 와 관련된 데이터가 들어있을 것이다. 그런데 이제는 process B 가 실행되야 하기 때문에 TLB 와 Cache 를 flush 할 필요가 있다. 그런데 문제가 있다. context switch 이후 process B 가 작업을 시작하는 시점에 매번 TLB miss 와 Cache miss 가 발생해서 performance 에 악영향을 주게된다. 개선이 시급해보인다.

 

(2) How to improve the proformance of TLB
 
" 어떻게 TLB 및 Cache miss 를 줄일 수 있을까? 일단, context switch 가 발생했을 때 TLB 와 Cache 를 모두 flush 하는게 문제다. 구분이 필요해보인다. 즉, flush 할 주소와 아닌 주소로 말이다. 어떻게 해야 할까? 사실 process address space 는 2 가지로 나뉜다.

 

1. kernel address space
2. user address space

 
" 모든 프로세스(kernel thread 포함)들은 kernel address space 를 공유한다. 사실 이 말이 내포하는 의미는 kernel address space 는 사이즈와 위치가 고정되어 있다는 것을 의미한다. 그러므로 context switch 가 발생할 때 그게 어떠한 processes 들이건 관계없이 kernel virtual addesss 와 physical address 의 매핑 관계(translation) 는 변하지 않는다. 이 말은 TLB 에서 kernel address space 영역은 제거할 필요가 없다는 것을 의미한다.
 

" 이제 process A 가 process B 로 switching 될 때, TLB 안에 kernel address space 는 flush 할 필요가 없다는 것을 알았다. 왜냐면 kernel address space 는 모든 process 가 공유하다보니 process B 도 process A 가 캐시해놓은 TLB 를 이어서 사용할 수 있기 때문이다.

 

" 그러나 user process 같은 경우는 다르다. user process 자신만의 독립적인 address space 를 갖는다. 그래서 user process A 에서 user process B 로 switching 될 때 process A 와 연관된 TLB 는 process B 에게는 무의미한 데이터다. 그러므로 이전 데이터(user process A 의 데이터) 는 flush 할 필요가 있다.

 

" 그런데 위에서 나눈 address space 범위는 너무 크다. 즉, user 와 kernel 이라는 영역은 범위가 너무 크다. performance 최적화를 위해서 좀 더 작은 영역까지 컨트롤할 수 있어야 한다. 그리고 user space 라고 해서 모든 내용을 flush 해야 하는것도 아니고 kernel space 라고 모드 영역을 flush 하면 안되는 것도 아니다. 그렇기 때문에 page 단위로 해서 context switch 시에 flush 하면 안되는 page 와 flush 와 가능한 page 를 나눌 수 있어야한다[참고1].

Another example in the Intel Pentium Pro, the page global enable (PGE) flag in the register CR4 and the global (G) flag of a page-directory or page-table entry can be used to prevent frequently used pages from being automatically invalidated in the TLBs on a task switch or a load of register CR3.

- 참고 : https://en.wikipedia.org/wiki/Translation_lookaside_buffer#Address-space_switch

 

" intel 같은 경우에는 CR4.PGE 라는 비트가 하나 존재한다. 풀네임은 `Page Global Enable` 의 약자로 `G` 플래그가 SET 된, page table entry 와 page directory entry 들이 invalidate 되는 것을 막는다. 이와 같은 기능을 통해 `flush 될 page` 와 `flush 되면 안되는 page` 로 나눌 수 있다. 
 
 
" 또 이런 상황을 가정해볼 수 있다. 위 그림에서 process A(user space 에서 실행 중) 가 kernel thread K 로 switching 될 경우 사실 address space 를 교체할 필요가 없다. 왜 그럴까? kernel thread K 는 kernel space 만 접근할 수 있고 user space 는 접근할 수 없다. 그렇기 때문에 process A 의 user address space 는 안전한 것이다. 그리고 모든 kernel threads 들은 kernel adress space 를 공유하기 때문에 kernel address space 도 교체할 필요가 없다. 결국 process A 에서 kernel thread K 로 context switching 이 될때 address space switching 이 발생하지 않았기 때문에 현재 TLB 에 캐쉬되어 있는 데이터가 process A 와 연관된 데이터라 할지라도 flush 할 필요가 없다. 또한 다시 kernel thread K 에서 process A 로 switching 될 때도 address space switching 이 발생할 필요가 없다. 그렇기 때문에 TLB 데이터는 여전히 valid 하다고 볼 수 있다. TLB miss 또한 상당히 줄일 수 있다. 


" 멀티 스레드 환경에서는 하나의 process 안에서 다수의 thread 간에 context switching 이 발생할 수 있다. 이 때 threads 들은 모두 하나의 process 안에서(동일 주소안에서) 동작하기 때문에 TLB 를 flush 할 필요가 없다. 그렇다면 thread 레벨에서 page table 이 존재하지 않는 건가? 즉, process 레벨에서만 page table 이 존재한다면 thread 레벨에서 context switch 는 단순히 레지스터 및 스택만 교체된다고 보면 될까? 컴퓨터 과학을 전공하면 `운영 체제` 시간에 `process versus thread` 주제에 대해 배운다. 그림으로 표현하면 다음과 같다.

https://users.cs.cf.ac.uk/Dave.Marshall/C/node29.html

 

 

" 1 개의 process 안에 존재하는 모든 threads 들은 code, heap, data 영역을 공유한다. 대신 자신만의 workspace 가 필요하기 때문에 각 threads 들은 2 가지 메모리 영역을 할당받는다. 여기서 반드시 기억해야 할 내용이 나온다. 자신만의 독립된 workspace 를 갖기 위해서는 반드시 아래 2 개의 메모리 영역이 필요하다는 것이다. 

1. stack
2. registers

 
 
 
(3) Further improve the proformance of TLB [참고1 참고2 참고3]
" 혹시 조금 더 TLB 의 performance 를 올릴 수 있는 방법이 없을까? 아예 TLB flush 를 하지 않는 방법은 없을까? 있다. 그런데 소프트웨어 기술만으로는 안된다. 하드웨어의 힘을 빌려야 한다. TLB performance 는 결국 TLB flush 를 줄이는게 핵심이다. TLB flush 의 대다수는 context switch 에서 발생한다. context switch 는 process 단위로 발생하기 때문에 process 에게 포커싱할 필요가 있다. 그래서 인텔과 같은 강력한 칩 제조사들에서 process 가 사용하는 TLB entry 를 별도로 관리함으로써, performance 를 한 단계 더 끌어올렸다.


" 이 방법은 TLB module 에서 각 프로세스의 address space 에 대한 정보를 알고 있어야 한다. 즉 하드웨어의 지원이 필요하다. 이러한 내용을 하드웨어 차원에서 구현되려면 TLB module 은 각 process 의 address space 를 구별할 수 있어야 한다. 그래서 도입된 것이 `Address Space ID(ASID)` 다. ASID 는 각 process 에게 고유하게 할당된다. 그리고 process 가 사용하는 TBL entry 들에게 process 의 ASID 가 할당된다. ASID 가 지원되는 상황에서 context switch 가 발생하면 TBL lookup 작업은 단지 새로 시작되는 process 의 ASID 와 TLB Cache 에 남아있는 TLB entry 의 ASID 를 비교해서 매칭된 TLB Entry 들만 사용한다. 예를 들어 process B 가 실행 될 경우 기존에 남아있는 TLB entry 중에 process B 의 ASID 와 매칭되는 entry 들만 사용한다는 것이다. 중요한 건 process B 의 ASID 와 다르다고 해서 TLB entry 를 flush 하지 않는다. 즉, ASID 를 도입하면 context switch 시에 TLB flush 를 완전히 없앨 수 있다. -> 그런데 TLB flush 를 안하면 나중에 실행되는 process 들은 TLB 를 아예 하나도 선점하지 못한다는 것 같은데 이 구조가 맞나?

Translation table entries contain a non-global (nG) bit. If the nG bit is set for a particular page, it is associated with a specific task or application. If the bit is marked as 0, then the entry is global and applies to all tasks.

For non-global entries, when the TLB is updated and the entry is marked as non-global, a value is stored in the TLB entry in addition to the normal translation information. This value is called the Address Space ID (ASID), which is a number assigned by the OS to each individual task. Subsequent TLB look-ups only match on that entry if the current ASID matches with the ASID that is stored in the entry. This permits multiple valid TLB entries to be present for a particular page marked as non-global, but with different ASID values. In other words, we do not necessarily need to flush the TLBs when we context switch.

- 참고 : ARM Cortex-A Series Programmer’s Guide for ARMv8-A

 

" ASID 의 기능은 이 뿐만 아니다. TLB 안에 동일한 virtual address 를 갖는 TLB entry 가 여러 개 있을 수 있다. TLB 는 address translation 에서 ASID 를 판단해서 현재 process 와 매칭되는 entry 만 사용하기 때문에 virtual address 가 겹치는 entry 들을 flush 할 필요가 없다.
 
 
 

- multi-core TLB

" 멀티 코어 시스템에서 context switch 가 발생하면 싱글 코어일 때 보다 TLB 동작이 훨씬 복잡하다. 그 이유는 2가지가 있다.

1. CPU 마다 TLB 를 개별적으로 가지고 있다. 
1.1 Local TLB flush - Local TLB 를 flash 한다.
1.2 Global TLB flush - 모든 코어의 TLB 를 flash 한다.

2. 코어가 여러 개 이다보니 1 개의 process 가 여러 코어에서 실행될 수 있다. 즉, ASID 를 지원하는 경우에 TLB 가 너무 지저분해진다. 뒤에서 다시 알아본다.

 

" 아래 그림을 보자. single core 일 때에 비해 구조가 상당히 복잡해진것을 알 수 있다.
 

 
 
(1) TLB operation
 
" single-core TLB 에서 address translation(TLB) 을 2개의 타입으로 나눌 수 있다. single-core 에서는 process 가 기준이 된다. 즉, global 이란 모든 processes 들이 공유하는 것이고 local 은 특정 프로시스에게만 종속되는 것을 의미한다.

1. global - shared by each process
2. local - process specific

 

" 그러나 multi-core TLB 에서 global 과 local 은 single-core 때와는 약간 다르다. 기준이 CPU 가 된다. local flush 는 현재 CPU 의 TLB 만 flush 시키는 것을 의미하고 global flush 는 모든 CPU 의 TLB 를 flush 하는 것을 의미한다. 싱글 코어와 다른 점이 뭘까? 사실 크게 와닿지 않는다. 그래서 다시 ASID 가 등장한다.
 

" arm64 에서는 `non-global(nG)` 비트가 SET 되면 local TBL entry 로 판단하고 여기에 ASID 를 추가해서 TLB flush 가 크게 발생하는 것을 막을 수 있다(참고로, intel 에서도 PCID(Process Context ID) 라고해서 ASID 와 완전히 동일한 기능이 존재한다). 그런데 이게 싱글 코어에는 효과가 좋았는데 멀티 코어에서는 좋지 못한 경우들이 더 많다. 예를 들어 싱글 코어 시스템에서 TLB 가 2개의 process 를 감당할 수 있을만큼 충분하다고 가정해보자(실제로 현대의 CPU 들은 이러하다). 그리고 `process A -> process B -> process A` 순서로 switching 이 발생했다고 치자. process A 가 최종적으로 다시 resume 할 때 TLB 가 충분히 크기 때문에 TLB hot(TLB miss 적음) 상태를 유지할 가능성이 크고 이는 결국 performance 의 향상을 가져다준다. 
 

" 그런데 멀티 코어 시스템에서는 전혀 그렇지 못하다. `TLB shootdown(invalidate or update)` 으로 인해 performance 에 문제가 있다는 것이다. 멀티 코어 시스템에서 ASID 를 지원할 경우 context swtich 시에 ASID 매칭되는 TLB entry 는 flush 하지 않는다. 이 말은 여러 코어의 다양한 process 들의 TLB entry 가 지저분하게 남아있을 수 있다는 뜻이된다. 그 결과로 process 가 죽거나 page table 의 매핑 관계(VA<->PA 의 관계) 가 바뀌었을 때 해당 process 의 TLB entry 를 갖고 있는 CPUs 들에게 shootdown 하라는 명령을 요청해야 한다. 이 때 IPI 가 사용된다. 그런데 IPI 는 overhead 를 일으킨다. 그리고 사실 ASID 를 생성하고 관리하는데 overhead 가 든다. 그래서 x86 같은 경우는 더 이상 PCID 를 지원하지 않고 있고 arm 에서는 아직 ASID 를 지원한다.
 
 
 
(2) TLB shootdown
 
" TLB shootdown 이란 `page tables or memory mappings` 에 변화가 일어났을 때 TLB entries 들을 invalidate 및 update 하는 동작들과 관련이 있다. 예를 들어 'process migration, page table update, inter-processor communication(IPI)' 등과 같은 이벤트가 발생하면 반드시 virtual address 와 physical address 간에 일관성을 유지하기 위해서 TLB flush 가 발생하기 마련이다.

1. Process migration - process 가 사용하는 메모리 영역의 주소가 바뀌면 당연히 virtual address 와 physical address 간의 memory mapping 관계가 변경되었으므로 TLB 를 invalidate 시키기 위해 TLB shootdown 이 발생한다.

2. Page table update - page table 에 수정 사항이 생기면, 예를 들어 page table entry 를 추가 혹은 제거하거나 page permission 을 변경할 경우 해당 page entry 에 대응하는 TLB entries 들은 invalidated 혹은 udpaed 되어야 한다. 

3. Inter-Processor Communication(IPI) - 멀티 프로세서 시스템에서 다수의 코어에 데이터가 흩어지다 보니 TLB 동기화가 문제가 대두되었다. 이 시점에 TLB shootdown 이 발생한다. 즉 다수의 프로세서의 TLB 간에 latest memory mapping 및 consistency 를 유지하기 위해 TLB shootdown 이 trigger 된다.

 

" TLB shootdown 이 발생할 경우 멀티 프로세서 여부에 따라 처리 루틴이 달라진다. handling flow 를 순서도로 표현했다.

 

 

- TLB operation in context switch

(1) TLB lazy mode
 
" 아래 코드는 만약 next task 가 kernel thread 라면, enter_lazy_tlb() 함수를 호출해서 CPU status 를 lazy TLB mode 로 전환시킨다. arm64 에서 enter_lazy_tlb() 함수가 비어있기 때문에 x86 기반으로 설명을 이어간다.

// kernel/sched/core.c - v4.4.6
/*
 * context_switch - switch to the new MM and the new thread's register state.
 */
static inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next)
{
	....
	mm = next->mm;

	....
	if (!mm) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	if (!prev->mm) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}
	....
}

 
" 지금까지 이 글에서 다룬 TLB flush 동작은 아키텍처에 상당히 의존적이다. 즉, 어떤 아키텍처는 하드웨어에서 거의 다 해주고 어떤 아키텍처는 소프트웨어에서 TLB 를 일일히 컨트롤이 가능하다. 특히나 x86 같은 경우는 상당히 하드웨어에 의존적이다. x86 에서는 CPU 마다 CR3 레지스터라는 것이 있는데 이 레지스터에 page table 을 로드하면 해당 CPU 는 CR3 레지스터에 로드된 page table 을 사용하게 된다. process switching 시에도 process 간에 page table 을 교체하는데, 이 때 CR3 에 각 process 의 page table 을 로드함으로써 process address space switching 이 일어난다. 즉, 이 말은 x86 에서는 process switchig 시에 명시적으로 TLB flush 명령어를 호출할 필요가 없다는 것을 의미한다. 그러나 arm 같은 경우는 소프트웨어에 상당히 의존적이다. 예를 들어 arm 의 TTBR(Translation table base register) 레지스터가 switching 된다고 해서 하드웨어적으로 TLB flush 가 발생하는 일은 없다. 대신 SW 에서 직접 TLB flush 명령을 수행해야 한다.
 

" 만약 x86 에서 PCID 를 지원하면 어떻게 될까? 리눅스 커널 x86 진영은 TLB shootdown 때문에 리눅스에서 PCID 기능을 지원하지 않도록 했다. 그래서 x86 기반에서 process address space switching 이 발생하면 Local TBL entry 를 모두 flush 하게되서 side effect 가 발생한다.
 

" 그리고 arm64 같은 경우는 `tlbi vmalle1is` 명령어를 사용해서 inner shareable domain 에 있는 모든 코어들의 TLB 를 invalidate 할 수 있다. 그러나 x86 에서는 이러한 기능을 지원하지 않는다. 만약 x86 에서 여러 코어들의 TLB 를 flush 하고 싶다면 IPI 를 통해 다른 CPUs 들에게 TLB 를 flush 하라고 요청해야 한다[참고1 참고2].
 

" 이제 진짜 TLB lazy mode 에 대해 알아보자. 비록 process switching 시에 TLB flush 를 해야하지만 몇몇 상황에서는 flush 를 하지 않는 케이스도 존재한다. 다음에 나오는 시나리오는 process A 에서 process B 로 전환된 상황이며 TLB flush 는 할 필요가 없다고 가정한다. 

1. next task 가 kernel thread 라면 당분간은 TLB flush 를 할 필요가 없을 것이다. 왜냐면 kernel thread K 는 user space 에 액세스할 수 없고 user process A 가 사용하다 남은 TLB entries 들 또한 kernel thread K 의 동작에 영향을 주지 않기 때문이다. 결과적으로 process B 는 자신만의 user address space 가 없고 process A 와 kernel address space 는 공유한다.

2. 만약 process A 와 process B 가 동일한 address space 안에 있다면(2개의 thread 가 동일한 하나의 process 안에서 process switching 된 경우) TLB flush 는 당분간은 할 필요가 없다.

 
 
" TLB flush 케이스는 process switching 시나리오만 있는건 아니다. 가장 흔한 TLB flush 케이스는 다음과 같다.

 
" 위에 그림을 보면, 총 4개의 코어가 있고 P0, P1, P2 가 동일한 process address space 에 속해있다. P0, P2 는 각각 CPU[0] 과CPU[2] 에서 동작한다. CPU[1] 은 약간 특별하다. 여기서는 kernel thread 가 동작하고 있고, P1 의 address space 를 빌려서 쓰고있다. CPU[3] 에서는 Q 가 동작하고 있다(Q 는 이 시나리오와 따히 연관성이 없는 프로세스다).
 
" 만약, P0 이 자신의 address translation 을 변경하면(예를 들어, 0x4000_0000(VA) -> 0x1000_0000(PA) 를 0x3300_0000(VA) -> 0x1000_0000(PA) 로 변경), 단순히 CPU[0] 만 flush 해서는 안된다. CPU[1] 과 CPU[2] 까지도 notify 해줄 필요가 있다. 왜냐면, 현재 CPU[1] 과 CPU[2] 의 active address space 가 CPU[0] 과 같기 때문이다. P0 이 자신의 address translation 을 변경하면서, CPU[1] 과 CPU[2] 에서 가지고 있던 P0 의 cached TLB entries 가 모두 invalid 되었고 이제는 flush 가 필요한 시점이 되었다. 이와 같은 방식으로, 좀 더 개념을 확장하면, 예를 들어, CPU[n] 이 address mapping 관계를 수정할 경우, CPU[n] 과 관련된 모든 CPU`s 들의 TBL 들은 flushed 되어야 한다(여기서 `관련된` 은 동일한 address space 를 사용할 경우를 의미한다. 즉 task_struct->mm 이 동일한 경우를 의미한다). 
 
" 멀티 코어 시스템에서는 IPI 를 통한 TLB flush 요청 개수는 CPU 코어가 많을 수 록 증가한다. 그렇다면, 불필요한 TLB flush 를 줄일 수 있는 방법이 없을까? 위에 코드로 돌아가보자. next task 가 kernel thread 라면, switch_mm(TLB flush 를 발생시키는 함수) 함수를 호출하는 대신에 enter_lazy_tlb() 함수를 호출해서 lazy TLB mode 로 진입시킨다. x86 기반의 entry_lazy_tlb() 함수는 다음과 같다.

// arch/x86/include/asm/tlbflush.h - v4.4.6
#define TLBSTATE_OK	1
#define TLBSTATE_LAZY	2

// arch/x86/include/asm/mmu_context.h - 4.4.6
static inline void enter_lazy_tlb(struct mm_struct *mm, struct task_struct *tsk)
{
#ifdef CONFIG_SMP
	if (this_cpu_read(cpu_tlbstate.state) == TLBSTATE_OK)
		this_cpu_write(cpu_tlbstate.state, TLBSTATE_LAZY);
#endif
}

 
 
" x86 기반에서 lazy TLB mode 란, `cpu_tlbstate.state` 에 TLBSTATE_LAZY 를 설정하는 것과 같다. 이렇게, TLBSTATE_LAZY 가 설정되면, 루틴상 switch_mm() 함수가 호출되지 않게 되므로, process address space switching 도 발생하지 않게된다. 결국, 불필요한 TLB flush 를 막을 수 있게 되는 것이다. x86 기반의 entry_lazy_tlb() 함수는 하드웨어 차원의 동작은 없다. 단지, CPU 상태를 변경하는 것으로 lazy TLB mode 로 진입한다.
 
 
" kernel thread 로 switching 된후, kernel thread 는 exection state 가 된다(switching 된 후에도 kernel thread 는 계속 TLBSTATE_LAZY 상태를 유지. 즉, lazy TLB mode). 그런데, 아직 CPU[1] 의 TLB 에는 process A 의 user space TLB entries 들이 남아있다. 그러나, 이 user space entries 들은 kernel thread 가 작업을 수행하는데 전혀 지장을 주지 않기 때문에, flush 할 필요가 없다. 왜냐면, kernel thread 는 user space 에 액세스하지 못하기 때문이다. 여기서 다른 CPU`s 들이 TLB flush 를 요청하는 IPI 를 보내면 어떻게 될까? 일반적인 경우라면, 즉각적으로 TLB flush 하지만(cpu_tlbstate.state == TLBSTATE_OK), 그러나, lazy TLB mode 라면, 해당 요청을 수행하지 않는다[참고1 참고2]. 아래 코드를 보면, cpu_tlbstate.state == TBLSTATE_OK 가 아니면, 즉, lazy TLB mode 라면, TLB 를 남겨둔다(`leave_mm`).

// arch/x86/mm/tlb.c - v4.4.6
/*
 * TLB flush funcation:
 * 1) Flush the tlb entries if the cpu uses the mm that's being flushed.
 * 2) Leave the mm if we are in the lazy tlb mode.
 */
static void flush_tlb_func(void *info)
{
	....
	if (this_cpu_read(cpu_tlbstate.state) == TLBSTATE_OK) {
		if (f->flush_end == TLB_FLUSH_ALL) {
			local_flush_tlb();
			....
		} 
        ....
	} else
		leave_mm(smp_processor_id());
}

 
" 그렇다면, 여기서 의문점이 생긴다. `남아있는 process A 의 TLB 는 언제 flush 해야 할까?` 정답은 `next process switching` 이다. 일단, kernel thread 가 schedule out 되고, new process 가 kernel thread 가 아니라면, switch_mm() 함수를 호출하게 되고 new process 의 address space 를 TLB 에 채우기 위해 이전의 TLB entries 들은 모두 flush 된다(x86 같은 경우 cr3 에 page table 로드). 정리하면, kernel thread 가 실행되는 동안에는 TLB flush 를 미룰 수 있다.
 
 
 

- ARM64 ASID

" x86(PCID) 과는 다르게 arm64 는 여전히 ASID 를 지원하고 있다. 그렇다면, arm64 는 TLB shootdown 문제를 해결했다고 말할 수 있을까? 글을 천천히 읽어봤다면, 멀티 프로세서에서 ASID 는 코어 개수에 비례해서 IPI 를 증가시키는 요인이된다. 그런데 사실, arm64 에서는 모든 CPU`s 코어의 TLB flush 를 요청하기 IPI 를 사용할 필요가 없다. 왜냐면, arm64 에서는 instruction set level 에서 동일 shareable domain 에 존재하는 모든 PE`s 들에게 적용할 수 있는 TLB flush 명령어가 존재하기 때문이다. 아마도, instruction set level 에서 지원해주기 때문에, IPI 보다는 overhead 가 적을 것이라 생각이 든다. 결과적으로, TLB flush 에 대한 비용이 줄어들면서, ASID 에 대한 지원여부를 고려해볼 수 있다. ASID 가 지원될 경우, process address space switching 시에 TLB flush 를 할 필요가 없어지고, 이와 동시에, instruction set level 에서 다른 코어의 TLB flush 를 지원하니 IPI 가 필요없어졌다. 즉, 그래서 arm64 에서 lazy TLB mode(`enter_lazy_tlb`) 를 사용하지 않는 것으로 추측된다.
 
" 리눅스에서 arm64 가 ASID 를 지원하면서, 또 다른 문제가 발생했다. 바로 `ASID 생성 및 관리` 문제다. ASID 는 하드웨어적으로 8-bit 혹은 16-bit 가 할당된다. 그렇면, 256 or 65,535 개의 ID 를 가질 수 있다. 그런데, 너무 작지 않나? ASID 가 overflow 가 발생할 여지가 있어보인다. 그래서, 소프트웨어적으로 overflow 가 발생할 지 않도록 해줄 의무가 있다. 예를 들어, 하드웨어적으로 256 개의 ASID`s 가 지원해준다고 가정하자. 이 말은 각 CPU 의 TLB entry 의 개수가 256 개를 넘지않을 때만 정상적으로 동작한다는 것을 의미한다. 만약, 256 개를 넘을 경우, 해당 CPU 의 모든 TLB entries 를 flush 하고 ASID 를 재분배 해야한다. 즉, 상한선(256)을 넘을 때 마다, TLB flush 가 발생하고, HW ASID 를 재할당한다.

// arch/arm64/mm/context.c - 4.4.6
static u64 new_context(struct mm_struct *mm, unsigned int cpu)
{
	static u32 cur_idx = 1;
	u64 asid = atomic64_read(&mm->context.id);
	u64 generation = atomic64_read(&asid_generation);

	if (asid != 0) { // --- 1
		u64 newasid = generation | (asid & ~ASID_MASK);

		/*
		 * If our current ASID was active during a rollover, we
		 * can continue to use it and this was just a false alarm.
		 */
		if (check_update_reserved_asid(asid, newasid)) // --- 1
			return newasid;

		/*
		 * We had a valid ASID in a previous life, so try to re-use
		 * it if possible.
		 */
		asid &= ~ASID_MASK;
		if (!__test_and_set_bit(asid, asid_map))
			return newasid;
	}

	/*
	 * Allocate a free ASID. If we can't find one, take a note of the
	 * currently active ASIDs and mark the TLBs as requiring flushes.
	 * We always count from ASID #1, as we use ASID #0 when setting a
	 * reserved TTBR0 for the init_mm.
	 */
	asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, cur_idx); // --- 2
	if (asid != NUM_USER_ASIDS)
		goto set_asid;

	/* We're out of ASIDs, so increment the global generation count */
	generation = atomic64_add_return_relaxed(ASID_FIRST_VERSION, // --- 3
						 &asid_generation);
	flush_context(cpu);

	/* We have at least 1 ASID per CPU, so this will always succeed */
	asid = find_next_zero_bit(asid_map, NUM_USER_ASIDS, 1); // --- 4

set_asid:
	__set_bit(asid, asid_map);
	cur_idx = asid;
	return asid | generation;
}

1. 새로운 process 가 생성되면, mm(memory descriptor) 이 할당되고, mm->context.id(software ASID) 는 초기값으로 0 이 할당된다. 그런데, 만약 SW ASID 가 0 이 아니라면, 이미 할당받았음을 의미한다. 이럴 경우, generaton 만 new generation 으로 변경하고 HW ASID 는 그대로 사용하게 한다.

" 그런데, new generation 을 기준으로 모든 CPU 에서 해당 SW ASID 를 사용하고 있다면, 새로운 ASID 를 할당해야 한다.

2.  만약 SW ASID 가 0 라면, 새로운 HW ASID 를 할당해야 한다. free HW ASID 를 찾을 때는, 가장 먼저 발견되는 free HW ASID 를 사용한다. 만약, free HW ASID 를 발견하면, `set_asid` 로 점프한다. `NUM_USER_ASIDS-1` 는 할당받을 수 있는 HW ASID 의 최대 개수를 의미한다. 즉, 새로 할당받은 HW ASID 가 NUM_USER_ASIDS 라면, overflow 가 발생했다는 것을 의미한다.

// arch/arm64/mm/context.c - V4.4.6
#define ASID_FIRST_VERSION	(1UL << asid_bits)
#define NUM_USER_ASIDS		ASID_FIRST_VERSION​

3. 만약, free HW ASID 가 없다면, 즉, HW ASID 를 모두 소진했다면, 이제 asid generation 을 증가시켜야 한다. 그렇다면, 얼마나 증가시킬까? ASID_FIRST_VERSION 만큼 증가시킨다. 이 갑은 asdi generation 의 초기값이다(뒤에서 다시 설명함). asid generation 의 할당 방식은 마치, page frame 구조와 비슷하다. page number + page offset 에서 page number 와 같은 기능을 한다고 보면 된다. 예를 들어, 각 asid generation 마다 256 개의 HW ASID 가 할당 가능하다. HW ASID 개수가 overflow 가 나면, asid generation 을 증가시켜 HW ASID 를 다시 초기화하는 방식이다. 당연히, generation 이 바뀌면, 이전 generation 을 사용하는 SW ASID 들은 폐기되야 한다. 즉, 이 때 모든 CPU 에서 TLB flush 를 발생시킨다.  

" flush_context() 함수는 new generation 이 발생해야 할 때, 호출되는 함수다. 즉, 모든 CPU 들에게 TLB flush 를 발생시키는 함수다(`tlb_flush_pending` 플래그를 SET). 그리고, asid_map 에서 HW ASID 를 초기화한다.

4. flush_context() 함수를 통해서 new generation 에 대한 HW ASID 가 초기화했다. 이제부터는 새로운 HW ASID 를 할당받으면, 1 부터 다시 시작한다(`0` 은 예약되어 있음).

 
 
" 이제 arm64 의 process switching 과정에서 TLB flush 를 어떻게 진행하는지 알아보자.

// arch/arm64/mm/context.c - v4.4.6
void check_and_switch_context(struct mm_struct *mm, unsigned int cpu)
{
	unsigned long flags;
	u64 asid;

	asid = atomic64_read(&mm->context.id); // --- 1

	/*
	 * The memory ordering here is subtle. We rely on the control
	 * dependency between the generation read and the update of
	 * active_asids to ensure that we are synchronised with a
	 * parallel rollover (i.e. this pairs with the smp_wmb() in
	 * flush_context).
	 */
	if (!((asid ^ atomic64_read(&asid_generation)) >> asid_bits) // --- 2
	    && atomic64_xchg_relaxed(&per_cpu(active_asids, cpu), asid))
		goto switch_mm_fastpath;

	raw_spin_lock_irqsave(&cpu_asid_lock, flags);
	/* Check that our ASID belongs to the current generation. */
	asid = atomic64_read(&mm->context.id);
	if ((asid ^ atomic64_read(&asid_generation)) >> asid_bits) { // --- 3
		asid = new_context(mm, cpu);
		atomic64_set(&mm->context.id, asid);
	}

	if (cpumask_test_and_clear_cpu(cpu, &tlb_flush_pending)) // --- 4
		local_flush_tlb_all();

	atomic64_set(&per_cpu(active_asids, cpu), asid);
	raw_spin_unlock_irqrestore(&cpu_asid_lock, flags);

switch_mm_fastpath:
	cpu_switch_mm(mm->pgd, mm);
}

 
 
" 코드를 보면, arm64 에서 ASID 를 지원하더라도, TBL flush 를 한다는 것을 확인할 수 있다. 즉, ASID 를 지원할 경우, 이상적으로는 TLB flsuh 가 필요없을 것 처럼 보였지만, 실제는 그렇지 않다는 것을 보여준다.

1. 새롭게 process switching 될 process 의 address space 를 검사해야 한다. 먼저, mm 은 new process 의 memory descriptor 를 의미한다. 여기서, mm->context.id 는 new process 의 SW ASID 를 의미한다. 여기서 하위 16 or 8 비트만 HW ASID 를 의미한다.

2. 이론적으로, arm64 에서 ASID 를 지원할 경우, process switching 시에 TLB flush 는 필요가 없어진다. 그러나, HW ASID 를 할당할 주소가 부족하기 때문에, SW 적으로 주소 공간을 확장시킨다. 이 때, 주소 공간은 64-bit 로 확장되며, 이것을 SW ASID 라고 부른다. 여기서 하위 8 ~ 16 비트는 HW ASID 로 사용되며, 상위 17 ~ 63 비트는 asid generation(global asid version) 이라고 부른다. 
" asid generation 의 초기값은 ASID_FIRST_VERSION 이다. 아래 볼 수 있다시피, ASID_FIRST_VERSION 은 8 혹은 16 이다.

// arch/arm64/mm/context.c - v4.4.6
#define ASID_FIRST_VERSION	(1UL << asid_bits)​

" HW ASID 가 overflow 가 발생하면, asid generation 이 1씩 증가한다. asid_bits 는 HW 적으로 지원되는 ASID 의 개수를 의미한다. 즉, 8 혹은 16 이다. HW 적으로 지원되는 ASID 를 알기 위해서는 `ID_AA64MMFR0_EL1` 레지스터를 읽어보면 된다.

" 새롭게 process switching 될 process 의 SW ASID generation 과 현재 시점에서 커널의 관리되고 있는 asid generation 과 같다면, TLB flush 를 할 필요가 없다. 즉, ASID 관련 작업을 진행할 필요없이, 직접적으로 `switch_mm_fastpath` 로 jump 해서 cpu_switch_mm() 함수를 호출할 수 있다.

" 그런데, 연산 과정이 조금 까다로울 수 있다. 그래서, 그림을 첨부한다. 핵심은 asid generation 만 판단한다는 것이다.


3. 새롭게 process switching 될 process 의 SW ASID generation 과 현재 시점에서 커널의 관리되고 있는 asid generation 과 다르다면, new software asid 를 할당해야 하는 시점이다. 그러므로, new_context() 함수를 호출해서 새로운 new software ASID 를 할당하고, 이 값을 mm->context.id 에 설정한다.

4. tlb_flush_pending 플래그는 TLB flush 가 필요한 CPU 번호를 저장한다. 예를 들어, `tlb_flush_pending` 가 0x0000_0007 이라면, 0,1,2번 CPU 에 TLB flush 가 필요함을 의미한다. local_flush_tlb_all 함수는 local TLB 를 flush 한다. 그렇다면, tlb_flush_pending 는 언제 SET 될까? generation 이 증가할 경우, 이전 SW ASID 는 모두 invalidation 된다. 이 시점이 모든 CPU`s TLB 를 flush 하는 시점이 된다.

 
 
" 최종적으로 `cpu_switch_mm` 함수를 통해서 level 0 translation table 의 physical address 를 TTBR0_EL1 레지스터에 write 한다.

// arch/arm64/include/asm/proc-fns.h - v4.4.6
#define cpu_switch_mm(pgd,mm)				\
do {							\
	BUG_ON(pgd == swapper_pg_dir);			\
	cpu_do_switch_mm(virt_to_phys(pgd),mm);		\
} while (0)

// arch/arm64/mm/proc.S - v4.4.6
/*
 *	cpu_do_switch_mm(pgd_phys, tsk)
 *
 *	Set the translation table base pointer to be pgd_phys.
 *
 *	- pgd_phys - physical address of new TTB
 */
ENTRY(cpu_do_switch_mm)
	mmid	x1, x1				// get mm->context.id
	bfi	x0, x1, #48, #16		// set the ASID
	msr	ttbr0_el1, x0			// set TTBR0
	isb
	ret
ENDPROC(cpu_do_switch_mm)