Improve scalability of rmap scanning of anonymous pages Feb 8, 2010

최근 Rik은 anon page들의 rmap을 통한 scanning overhead를
줄이기 위한 패치를 제출하였다. 지금까지의 문제는 다음과 같다.

A라는 프로세스가 있다고 가정하자. A라는 프로세스는 1000개의 page들로
이루어진 하나의 vma를 가지고 있다고 하자. 그리고 A는 1000개의 프로세스를
fork한다고 하자. 너무나도 잘 알듯이 A process의 vma에 해당되는
PTE들은 protect되어질 것이다. (For Copy-On Write)

이제 예를 들어 child 0이 vma의 0 page, child 1이 vma의 1 page,
child 2가 vma의 2 page.... child 999는 vma 999번째 page를
write한다고 가정하자.

무슨일이 일어날까?

Process A의 VMA의 anon_vma에 연결되는 vma들은 1001가 될 것이며,
페이지 회수를 위해서 하나의 page에 대한 matching vma 검색은
worst case 1000번의 mismatch가 발생할 것이다.

여기서 심각한 것은 1000개의 vma를 lookup하는 동안 anon_vma의
lock이 hold되고 있다는 것이다. 그러므로 모든 CPU에 anon_vma의 lock을
필요로 하는 모든 opeartion들 또한 위의 operation이 종료하기 전까지
모두 stuck되는 것이다.

이 문제를 풀기 위해 Rik이 제안한 방법은 anon_vma와 vma가 연결되는 방식을
하나의 vma가 여러개의 anon_vma들과 연결될 수 있도록 개선한 것이다.
fork시점에 각 child process들은 각자 자신의 anon_vma를 갖게 되며
COWed page들은 각 자식 프로세스들의 anon_vma에 연결되게 하는 것이다.
또한 COWed page가 속해 있는 vma는 parent의 anon_vma와도 연결된다.
왜냐하면 non-COWed page들이 child에 속해있을 수도 있기 때문이다.

이는 1000개의 child process들의 1/N개의 page들에 대한 rmap scanning
complexity를 O(N)에서 O(1)로 줄여준다. worst case 또한 O(N)에서 2,
base case 1이 될 것이다.

하지만 barrios가 우려하는 것은 이러한 anon_vma의 lock overhead는
server중에서도 heavily forkbomb workload 즉, apache와 같은 경우를
제외하곤 그리 흔한 workload는 아닐 것 같다는 것에 있다. 그러므로 가뜩이나
SWAP을 잘 사용하지 않아 anonymous page의 scanning이 필요하지 않은
embedded 동네에서 이 patch는 다소 overkill이라는 점이다.

이와 같은 우려의 목소리는 Rik에게 전달했으며 그 또한 충분히 공감하고 있음으로,
그에 대한 패치는 Rik이 하던, Barrios가 하던 어렵지 않게 merge될 것으로 생각된다.