MMU notifier and page-table locking

Page-table lock 안에서 알려야 하는 경우

PTE 또는 PMD를 지울 때 page-table lock 안에서 notify 형태의 `*_clear_flush` 호출이나 `mmu_notifier_invalidate_range`를 통해 event를 알릴 수 있습니다. 하지만 모든 경우에 이 notification이 필요한 것은 아닙니다.

IOMMU TLB나 device TLB 같은 secondary TLB가 있을 때, PTE 또는 PMD를 지우면서 page-table lock을 유지한 채 notify해야 하는 경우는 두 가지뿐입니다. Device가 ATS/PASID 같은 기능으로 IOMMU가 CPU page table을 walk하게 하여 process virtual-address space에 접근하는 상황을 포함합니다.

• A. Page를 뒷받침하는 address가 `mmu_notifier_invalidate_range_end()` 전에 해제됩니다.
• B. Page-table entry가 새 page를 가리키도록 갱신됩니다. COW, zero page의 write fault, `__replace_page()` 등이 해당합니다.

Case A는 명백합니다. Device가 이제 전혀 다른 task가 사용할 수 있는 page에 쓰게 되는 위험을 허용하면 안 됩니다.

Case B는 더 미묘합니다. Correctness를 위해 page-table lock을 얻고, page-table entry를 지우면서 `[pmd/pte]p_huge_clear_flush_notify()`로 알린 뒤, page-table entry가 새 page를 가리키게 해야 합니다.

• Page-table lock 획득
• Page-table entry 제거 및 notification
• Page-table entry가 새 page를 가리키도록 설정

Page-table entry를 지운 뒤 새 PTE 또는 PMD 값을 설정하기 전에 notify하지 않으면 device 관점에서 C11 또는 C++11 같은 memory model을 깨뜨릴 수 있습니다.

When do you need to notify inside page table lock ?
===================================================

When clearing a pte/pmd we are given a choice to notify the event through
(notify version of \*_clear_flush call mmu_notifier_invalidate_range) under
the page table lock. But that notification is not necessary in all cases.

For secondary TLB (non CPU TLB) like IOMMU TLB or device TLB (when device use
thing like ATS/PASID to get the IOMMU to walk the CPU page table to access a
process virtual address space). There is only 2 cases when you need to notify
those secondary TLB while holding page table lock when clearing a pte/pmd:

  A) page backing address is free before mmu_notifier_invalidate_range_end()
  B) a page table entry is updated to point to a new page (COW, write fault
     on zero page, __replace_page(), ...)

Case A is obvious you do not want to take the risk for the device to write to
a page that might now be used by some completely different task.

Case B is more subtle. For correctness it requires the following sequence to
happen:

  - take page table lock
  - clear page table entry and notify ([pmd/pte]p_huge_clear_flush_notify())
  - set page table entry to point to new page

If clearing the page table entry is not followed by a notify before setting
the new pte/pmd value then you can break memory model like C11 or C++11 for
the device.

Secondary TLB ordering이 깨지는 예

ATS/PASID와 비슷한 기능을 쓰는 device를 생각해 봅시다. `|addrA - addrB| >= PAGE_SIZE`인 두 주소 `addrA`, `addrB`가 있고 둘 다 COW를 위해 write-protected 상태라고 가정합니다. Case B의 다른 상황에도 같은 논리가 적용됩니다.

::

[Time N] --------------------------------------------------------------------
CPU-thread-0  {try to write to addrA}
CPU-thread-1  {try to write to addrB}
CPU-thread-2  {}
CPU-thread-3  {}
DEV-thread-0  {read addrA and populate device TLB}
DEV-thread-2  {read addrB and populate device TLB}
[Time N+1] ------------------------------------------------------------------
CPU-thread-0  {COW_step0: {mmu_notifier_invalidate_range_start(addrA)}}
CPU-thread-1  {COW_step0: {mmu_notifier_invalidate_range_start(addrB)}}
CPU-thread-2  {}
CPU-thread-3  {}
DEV-thread-0  {}
DEV-thread-2  {}
[Time N+2] ------------------------------------------------------------------
CPU-thread-0  {COW_step1: {update page table to point to new page for addrA}}
CPU-thread-1  {COW_step1: {update page table to point to new page for addrB}}
CPU-thread-2  {}
CPU-thread-3  {}
DEV-thread-0  {}
DEV-thread-2  {}
[Time N+3] ------------------------------------------------------------------
CPU-thread-0  {preempted}
CPU-thread-1  {preempted}
CPU-thread-2  {write to addrA which is a write to new page}
CPU-thread-3  {}
DEV-thread-0  {}
DEV-thread-2  {}
[Time N+3] ------------------------------------------------------------------
CPU-thread-0  {preempted}
CPU-thread-1  {preempted}
CPU-thread-2  {}
CPU-thread-3  {write to addrB which is a write to new page}
DEV-thread-0  {}
DEV-thread-2  {}
[Time N+4] ------------------------------------------------------------------
CPU-thread-0  {preempted}
CPU-thread-1  {COW_step3: {mmu_notifier_invalidate_range_end(addrB)}}
CPU-thread-2  {}
CPU-thread-3  {}
DEV-thread-0  {}
DEV-thread-2  {}
[Time N+5] ------------------------------------------------------------------
CPU-thread-0  {preempted}
CPU-thread-1  {}
CPU-thread-2  {}
CPU-thread-3  {}
DEV-thread-0  {read addrA from old page}
DEV-thread-2  {read addrB from new page}

Time N에 CPU thread 0과 1이 각각 `addrA`와 `addrB`에 쓰려고 하고, device thread가 두 주소를 읽어 device TLB를 채웁니다. N+1에 두 CPU thread가 각 주소의 `mmu_notifier_invalidate_range_start()`를 호출합니다. N+2에는 두 page-table entry가 각 주소의 새 page를 가리키게 됩니다. N+3에 CPU thread 2와 3이 새 page의 `addrA`, `addrB`에 차례로 쓰고, CPU thread 0과 1은 preempt될 수 있습니다. N+4에는 `addrB`의 invalidate-range end만 완료됩니다. N+5에 device는 stale TLB를 통해 `addrA`를 old page에서 읽지만 `addrB`는 new page에서 읽습니다.

즉 N+2에 page-table entry를 지운 동작과 secondary-TLB invalidation notification을 짝지어 수행하지 않았기 때문에 device가 `addrA`의 새 값보다 `addrB`의 새 값을 먼저 보게 됩니다. 이는 device의 total memory ordering을 깨뜨립니다.

Consider the following scenario (device use a feature similar to ATS/PASID):

Two address addrA and addrB such that \|addrA - addrB\| >= PAGE_SIZE we assume
they are write protected for COW (other case of B apply too).

::

 [Time N] --------------------------------------------------------------------
 CPU-thread-0  {try to write to addrA}
 CPU-thread-1  {try to write to addrB}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {read addrA and populate device TLB}
 DEV-thread-2  {read addrB and populate device TLB}
 [Time N+1] ------------------------------------------------------------------
 CPU-thread-0  {COW_step0: {mmu_notifier_invalidate_range_start(addrA)}}
 CPU-thread-1  {COW_step0: {mmu_notifier_invalidate_range_start(addrB)}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+2] ------------------------------------------------------------------
 CPU-thread-0  {COW_step1: {update page table to point to new page for addrA}}
 CPU-thread-1  {COW_step1: {update page table to point to new page for addrB}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+3] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {preempted}
 CPU-thread-2  {write to addrA which is a write to new page}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+3] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {preempted}
 CPU-thread-2  {}
 CPU-thread-3  {write to addrB which is a write to new page}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+4] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {COW_step3: {mmu_notifier_invalidate_range_end(addrB)}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+5] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {read addrA from old page}
 DEV-thread-2  {read addrB from new page}

So here because at time N+2 the clear page table entry was not pair with a
notification to invalidate the secondary TLB, the device see the new value for
addrB before seeing the new value for addrA. This break total memory ordering
for the device.

Notification을 lock 밖으로 미뤄도 되는 경우

PTE를 write-protected 상태로 바꾸거나 같은 content를 가진 새 write-protected page, 즉 KSM page를 가리키게 할 때는 `mmu_notifier_invalidate_range` 호출을 page-table lock 밖의 `mmu_notifier_invalidate_range_end()`까지 미뤄도 됩니다. Page table을 갱신한 thread가 lock을 놓은 직후 `mmu_notifier_invalidate_range_end()`를 호출하기 전에 preempt되더라도 마찬가지입니다.

When changing a pte to write protect or to point to a new write protected page
with same content (KSM) it is fine to delay the mmu_notifier_invalidate_range
call to mmu_notifier_invalidate_range_end() outside the page table lock. This
is true even if the thread doing the page table update is preempted right after
releasing page table lock but before call mmu_notifier_invalidate_range_end().