Linux Foundation CTO leaves for Google Jan 16, 2010

http://www.internetnews.com/software/article.php/3858856/Linux+Foundation+CTO+Leaves+for+Google.htm

Ted 또한 Google로 자리를 옮겼다.
그는 IBM에 근무하는 동안 ext4를 성공적으로 Linux에 안착시켰으며,
Linux Foundation에서 2년간 CTO 업무를 수행하였다. 이번 2년간의
CTO 업무를 마감하며, Google로 자리를 옮기게 되었다.

Google로써는 또 한명의 재능있는 kernel hacker를 얻었으며, IBM으로써는
잃게 된 것이다. 개인적으로는 아직까지 구글이 kernel community에서 차지하는
위상이 그리 높지 않아, Ted의 앞으로의 kernel community에 대한 기여가
조금 걱정되기는 하나, Google의 기업 이미지 상 Ted가 뜻이 있다면 kernel community
활동을 하는데는 큰 지장이 없을 것으로 생각한다.

기사의 소개에 따르면 Ted가 맡게 될 첫번째 임무는 Google의 system들을 ext2에서
ext4로 migration시키는 것이다. 지난번 kernel summit에서도 말이 나온 것과 같이
Google은 현재 metadata 처리의 성능 개선을 위해 유별난 방법을 사용하고 있다.
결국 이 문제를 해결하기 위해 유별난 방법을 버리고 ext4로 migration을 시도하는 것 같다.

Ted는 Google에는 많은 재밌는 kernel project들과 뛰어난 kernel hacker들이 있는 것에
흥미를 느끼고 있다.

앞으로 Google에서의 Ted의 건투를 빈다.

Speculative Page Fault

Barrios는 page fault의 문제에 관하여 항상 관심을 가지고 있었다.

그 이유는 100T1P(100 Threads in 1 Process)의 application을 본 적이 있기 때문이다.
하지만 이러한 괴물 프로그램은 다른 곳에도 많이 있었다.
(지난 번 Google을 얘기하면서 이 문제를 언급한 적이 있었다.)

이 문제를 풀기 위해 Google은 I/O request 전 mmap_sem를 release하는 패치를 자체적으로
사용하고 있었으며, mainline에 submit을 시도하였었다(하지만 공식적인 패치는 아니였다.)
이 패치는 mmap_sem에 write-side lock으로 인해 다수의 reader들이 stuck되는 현상을 막기
위한 패치였다.

작년 11월경, 새로운 패치가 Kame에 의해 RFC되었다. 이 패치는 Google의 문제와는 달리,
mmap_sem의 contention에 대한 cache line bouncing문제를 해결하기 위한 패치였다.
제목은 speculative page fault였다. 제목 그대로 page fault에 대해 추측을 한후,
추측이 실패하였을 경우, retry를 하는 방식이다. 추측을 해서 얻으려고 하는 이득은
mmap_sem의 lock을 hold하지 않고 하겠다는 것이다. 해서 cache line bouncing을
없애겠다는 것이며, 추측이 틀렸을 경우, 제대로 다시 Lock을 hold하고 retry를 하겠다는
approach이다. approach 자체는 simple하지만 구현하기에 그리 순탄지는 않다.

이를 구현하기 위해 다양한 시도들을 했었다. vma에 reference counter를 두는 방식,
rb tree에 RCU를 적용하는 방식등.. 시도는 계속되었다.

Barrios는 이 패치들을 11월 첫 버젼 부터 review하기 시작했으며 12월 말까지 계속해서
Kame와 패치에 대해 얘기하고 있었다. 이런 와중, Peter는 Kame의 패치의 atomic operation에
대한 문제를 꼬집기 시작하였다. 문제는 atomic opeartion에 대한 비용은 거의 spin lock의
비용만큼이나 크다는 것이다. 우리는 기존의 page table lock과 RCU를 사용하여 atomic op를
사용하지 않고도 문제를 해결할 수 있다고 주장하였으며, 그에 대한 패치를 제시하였다.

Peter의 첫 패치는 부팅조차 되지 않는 상태였으나, 몇가지 버그를 해결하고 간신히 부팅은 되는
형태였지만 어디까지나 RFC 단계의 패치 형태였으며 방향성만을 보여주기 위한 것이었다.(Peter의
패치가 완성되기 위해서는 SRCU의 개선이 필요하였다. 이를 위해 Peter는 Paul과 얘기중이었으며,
패치는 빠르게 settle down되어가는 듯 하였다.)

패치는 굉장히 깔끔한 코드였다. 지금껏 Kame에 의해 만들어진 것 보다는 좋아 보였다.
하지만 한가지 치명적인 문제를 가지고 있었다. 문제는 vma 자체는 RCU에 의해 보호되지만,
vma와 연결된 VFS stack은 그렇지 못하다는 것이었다. 이 문제를 해결하기 위해서는
VFS stack 전체가 RCU에 의해 보호되어야 한다. 이는 전체 kernel core에 광범위한 패치가
필요하다, 또한 RCU에 의한 보호는 unmap path의 실행시간을 bound하기 어렵게 되는 문제 또한
가지고 있었다. 이 문제는 RCU를 sync하여 어느 정도 해결할 수 있지만 synchronize_rcu 함수의
비용은 상당히 크다. 그러므로 unmap path에 그런 함수를 넣는 것은 모두가 좋아하지 않고 있다.
또한 map path 만큼이나 unmap path의 성능이 중요한 application도 있다고 Peter는 조언하였다.

얘기가 이렇게 풀어가고 있을 무렵, Linus는 전체적인 잘못된 문제를 짚어주었다.
문제는 우리가 너무 technical detail에 매달리고 있다는 것이다. 이러한 문제는
더 높은 higher layer의 design을 통해 해결하는 것이 좋다는 의견이었다.

I would say that this whole series is _very_ far from being mergeable.
Peter seems to have been thinking about the details,
while missing all the subtle big picture effects that seem to actually
change semantics.

이 말에 대부분의 개발자들은 동의를 하였으며 그러던 중, Linus는 새로운 문제를 발견하였다.
Kame의 profile을 보는 순간 이 문제는 mmap_sem의 cache line bouncing문제가 아니라고
결론을 내린것이다. 그 이유는 profile data에 schedule footprint가 보이지 않는다는 것이다.
정말 mmap_sem에 대해서 서로 치열하기 가지려고 경쟁을 하였다면 wait 상태로 들어가건 runnable 상태로
들어가 건 schedule과 관련된 footprint이 보여야 한다. 하지만 profile 데이터 상에는 그러한
것은 보이지 않았다.

Linus는 문제의 원인을 X86_64의 naive한 spinlock구현을 지적하였다.
X86은 이미 xadd 명령을 이용하여 rw semaphore를 optimize하고 있었지만,
X86_64는 그렇지 못하고 있었다. 해서 X86_64의 rw semaphore는 generic한 형태의
rw semaphore를 그대로 사용하고 있었다.
사실 barrios도 Kame의 Test program을 x86에서 테스트 해보았지만 Kame와 같은 profile
결과를 얻지 못하였었다. barrios는 그것은 Kame의 테스트 환경이 2 socket 8 core 환경이었지만
barrios는 1 socket에 4 core 환경이어서 그런가보다 하고 넘어갔었는데 문제 자체가 X86과
X86_64의 spinlock구현에서 벌어진 것이었다.

Linus는 금방 최적화된 spinlock을 구현하여 패치를 올렸으며, 예상은 적중하였다.
Kame와 Peter의 패치 이상으로 결과가 좋았던 것이다.
결국 문제는 우리가 생각했던 것과는 다른 곳에 있었다.

이 문제는 불과 몇일 만에 80여개의 쓰레드를 만들어내며 결국 naive한 X86_64의 rw semaphore
의 문제를 해결하며 결론을 보았다.(하지만 아직까지 Linus의 패치는 최적화된 버젼이 아니며, Linus
는 누군가가 더 최적화해서 패치를 올려주길 기다리고 있는 것 같다.)
이 문제를 통해 아직 mmap_sem가 그리 큰 bottle neck은 아니라는 것이 반증되었다.

하지만 mmap_sem와 같은 coarse-grained lock은 언젠가 해결되어야 하며, 이 문제를 해결하기 위해서
lock 자체에 대한 수정 보다는 VMM의 page fault handling 자체를 redesign이 필요가 있을 것으로
생각된다.