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이 필요가 있을 것으로
생각된다.

EOF of 2009 Dec 31, 2009

이렇게 의지와는 관계없이 2009년도 가버린다.
마음같아서는 잡을 수만 있으면 보내고 싶지 않은 해이다.

올해에 무엇보다 가장 큰 변화는 지금 내 무릎위에 앉아 나의
모니터를 함께 쳐다보고 있는 녀석이 생겼다는 것이다. 그 만큼 또
내 욕심이 늘었다. 자꾸 자꾸 버리는 것 없이 늘어만 가는 욕심에 갇혀
힘들적도 있지만 아직은 견딜만 하다.

돌이켜보면 그다지 후회가 남는 일은 없는 것으로 보아 선방한
해였다. 최근 몇가지 안 좋은 모습으로 스스로에게 약간 짜증이 나있는
상태이긴 하지만 금방 좋아질 것이라고 낙관한다.

올 한해 가장 와 닿았던 것은 내가 어찌 할 수 없는 일을 어찌해보려고
하는 것은 분명 정신건강에 좋지 않다는 것이다.
어찌 할 수 없었던 것은 능력이 부족한 나의 잘못임이 자명하니 능력밖의
일을 못한다고 투덜거려봐야... 부족하면 키우면 되는 것이고.
그런데 문제는 별로 키우고 싶지 않은 것들이 더 많다는 것이다.
절대적인 상생을 위한 타협이 필요하다.

내년을 위한 소망들도 몇가지 있다. 지금 막 떠오른 것도 있고 예전부터
계획한 것도 있고, 최근 수정된 것도 있다. 내가 어찌한들 가는 2009년
막을 재간은 없고, 계획된 2010년은 오고 있으니 선택의 여지가 없다.

다윈의 진화론을 기반으로 "한해 한해 진보하지 못한다면
나는 인간이 아니지 않을까?"는 궤변으로 올 한해 마무리하며, 내년에도
계속 인간일 수 있길 기대한다.

주위 모든 고마운 분들 내년에도 계속 행복하길 바란다.

Drop Andorid drivers in Staging tree Dec 27, 2009

최근 Greg은 Andorid를 staging tree에서 제거하기를 결정하였다.
그 이유는 다음과 같다.

"Google and no one else stepped up to maintain them, so they will be dropped. So sad..."

나도 슬프다. 어쩌다가 일이 이렇게 되었는지 모르겠다.

사실 구글의 커널 패치들은 mainline guy들과 여러차례 trouble을 일으켰다.
Barrios는 모든 패치를 review하진 못하였지만 low memory killer 패치는
review한적이 있으며, 그것이 얼마나 ugly한 코드였는지 언급한 바 있다.

몇몇 MM guys들은 심지어 구글의 커널 코드들을 staging tree에
add하는 것 조차 거부하였었다.

그 이유는 Google의 소극적인 태도와 코드 개선의 의지를 보여주지 않았었기 때문이다.
그럼에도 불구하고 Greg의 의지로 staging tree로의 입봉은 임베디드 리눅스 입장에서
상당히 고무적인 일이었다. Google의 의지와는 관계없이 Greg의 판단에
의해 merge되었기 때문이다.

하지만 결과가 이러하다. Open Source Community의 힘을 모르지 않는
구글에서 나온 결과이기 때문에 더욱 놀랍다. 무슨 생각으로, 왜 그러한 방향으로
driven한 것인지 잘 모르겠지만 Embedded Linux의 Best Practice가 하나 사라진 것에 대
해 상당히 아쉽다.

RCU mistakes Dec 24, 2009

http://lwn.net/Articles/366718/
http://lwn.net/Articles/366717/

지난 기사에 Thomas의 rwlock 제거 노력에 대한 언급을 하였었다.
지난주 corbet은 Thomas의 패치에 대한 기사를 또 다시 실었다.

주의하고 넘어가야 할 문제인 듯 싶어 언급한다.

Thomas는 tasklist_lock을 RCU로 바꾸려는 노력 가운데, 몇몇 코드들이 RCU를 잘못사용하고 있는 case를
발견하였다. 가장 흔히 하는 실수가 rcu_read_[un]lock을 사용하지 않는 것이다.

개발자들이 그런 실수를 하는 이유는 quiescent state를 보장받기 위해 해당 CPU의 preemption을
disable하면 충분하다고 판단하였기 때문이다. 맞다. Hierarchical RCU가 merge되기 전까지는 말이다.

HRCU는 RCU의 grace period를 위해 cpumask와 cpumask의 각 CPU에 해당하는 bit을 보호하기 위한
spinlock 사용으로 인하여 떨어지는 scalability의 문제를 극복하기 위해 추가된 feature이다.
또한 Classical RCU는 모든 CPU가 quiescent state를 거쳐야 하기 때문에 잠자고 있는 CPU마저도
모두 깨워야 하는 문제가 있다. 이는 16개의 core중 4개의 core만이 주로 사용되고 있다고 가정할 경우(
흔한 경우라 한다.) power consumption에 있어 큰 문제가 된다.

이 feature를 사용하게 될 경우, preemption disable만으로는 충분하지 못하다.
개발자들이 흔히 했던 실수라는 것은 caller가 이미 preemption을 disable하고 있을 경우(또는
preemption_disable primitive가 이미 포함된 spinlock 구간 또는 interrupt disable 구간),
굳이 rcu_read_lock을 호출하지 않았던 것이다. 이는 충분히 문제가 되는 경우이며, 진작에 문제가
터졌어야 정상인데 불행히도 아직까지 CONFIG_TREE_PREEMPT_RCU가 널리 사용되지 않고 있었기 때문이다.

이러한 부분들이 수정되가며 점점 tasklist_lock 또한 RCU로 바뀌어가고 있다.
이제 정말 얼마 안 남은 것 같다. rwlock이 사라질 날이.

Eliminating rwlocks and IRQF_DISABLED Dec 13, 2009

http://lwn.net/Articles/364583/

조만간 rwlock이 커널에서 사라질 것 같다.
rwlock은 unfair 하기로 유명한 lock이다.

write side는 reader side가 모두 release될 때 까지 기다려야 하며, 심지어는
기다리는 도중 새로운 reader side들 막지 못한다. 그러므로 계속되는 reader side는
system의 live lock 상황을 유발할 수 있게 된다.

위와 같은 상황은 상당히 발생하기 드물기는 하지만 최근 Nick은 이 문제로 인하여
심하게 performance regression이 발생하는 문제를 report하였으며 regression을
발생시키지 않으며 fair한 rwlock 구현을 생각하고 있다.

이를 위한 soluation으로는 reader side 의 lock grab을 write side가 기다리고 있는
한 허용하지 않게되면 간단하다. 허용하지 않겠다는 것은 reader side를 block시키겠다는
것인데 말만큼 간단한 문제가 아니다. 이는 rwlock이 nesting이 허용되는 primitive를
근간으로 한다.

예를 들어 Processor 1에서 reader side의 lock을 hold하고 있는 상태에서
Processor 2에서 해당 자원의 write lock을 요구한다고 하자.
Processor 2의 task는 spinning하게 될 것이다. 이때 다시 Processor 1이 interrupt되며
interrupt handler안에서 해당 자원을 다시 read lock하게 될 경우 deadlock 상황이 발생
할 수 있게 된다.

또 다른 해결책으로써는 lock을 잡을 때 IRQ를 disable해버리면 쉽게 해결 된다.
하지만 커널 전체의 regression은 이로 말할 수 없게 될 것이다.

rwlock에 대해서는 오랫동안 커널내에서 없애자는 움직이이 있어왔다. rwlock의 cost가
일반 spinlock에 비해 상당하기 때문이다. 그러므로 lock에서 소모되는 cost보다
훨씬 큰 benefit이 있지 않는 한 rwlock을 사용하는 것은 무모한 일이다.
그래서 많은 rwlock들이 spinlock, RCU등으로 바뀌어 왔다. rwlock을 spinlock으로
바꾸는 것은 굉장히 쉬운 일이지만 문제는 tasklist_lock이다.

이 lock은 커널의 core에서 많이 사용되어지고 있으며, 굉장히 critical한 fast path에서
사용되고 있다. 더욱 큰 문제는 tasklist_lock의 오남용은 실제 lock이 보호하는 것이
어떤 data인지 현재 명확하지 않고 있다는 것이다. 그러므로 함부로 lock을 바꿔서 생기게
되는 performance regression, stale data 문제등을 한번에 해결하기는 쉽지 않은
일이 되어 버렸다. 그래서 많은 커널 개발자들은 tasklist_lock을 손대는 것을
꺼려하여 왔다.

하지만 Thomas Gleixner가 이 문제를 해결하기 위해 칼을 빼들었다. LWN의 기사가
나올때까지는 어떤 움직임도 없었지만 최근 LKML에 tasklist_lock을 없애기 위한 patch들이
포스팅 되고 있다. Thomas Gleixner가 이 문제를 해결하게 되면 나머지 rwlock은 쉽게
제거될 수 있다. 결국 커널의 rwlock을 볼 날도 이제 얼마 남지 않았다.

IRQF_DISABLED

오래전 리눅스는 top half자체도 자체도 "fast", "slow"로 나눠져 있었다고 한다.
해서 fast interrupt handler는 모든 IRQ를 disable한 상태에서 빠르게 처리를 했고,
slow irq interrupt handler는 IRQ를 enable하여 다른 IRQ의 처리를 허용한 상태에서
동작하였다고 한다. 그렇지 않게 되면 다른 더 중요한 인터럽트들의 처리를 지연시켜
전체적인 시스템의 성능을 down시켰기 때문이다.

하지만 점차 CPU의 성능이 좋아지고, Device들이 똑똑해지며 device driver들 또한
성숙하여 점차 IRQ를 enable하고 처리해야 하는 slow path가 점차 사라지게 된 것이다.
이에 요즘 드라이버 개발자들은 인터럽트 핸들러를 등록할 때 IRQ를 enable하고 실행해야
할지 말아야 할지 조차 신경쓰지 않는다. 그럼에도 불구하고 여전히 인터럽트 핸들러를
등록할 때 우리는 인수를 신경써야 한다. 게다가 더 재밌는 것은 shared interrupt handler들은
IRQ를 disable되어 실행된다는 것을 보장받을 수 조차 없다는 것이다. 왜냐하면 해당
IRQ line에서 실행된 다른 interrupt handler가 IRQ를 enable할 수 있기 때문이다.

해결책은 간단하다. IRQF_DISABLED 인수를 없애버리고 모든 IRQ handler가 실행될 때
IRQ를 disable하는 것이다. 하지만 여전히 IRQ를 enable하고 실행해야 할 상황은 있다.
예를 들어 A interrupt handling의 time이 여전히 길다던가, 또는 A interrupt handling은
B의 interrupt handling에 의존적이라던가. 이와 같은 경우를 해결하기 위해서는 먼저 긴
시간이 길어지지 않게, 서로 다른 2 IRQ에 의존적이지 않게 redesign을 하는 것과,
또는 interrupt handler를 thread IRQ handling으로 처리되게 바꾸는 것이다.
thread IRQ handling은 선천적으로 모든 IRQ가 enable된 상태에서 동작하는 특성을
가지고 있기 때문이다. 그래도 안될 경우 마지막 보루로써 IRQF_NEEDS_IRQS_ENABLE를
사용하는 것이다.

현재로선 어떻게 될지 명확하지 않지만 머지 않아 모든 IRQ hanlder들은 IRQ를
disable한 상태로 수행되게 될 것이며, 해당 요구를 만족하지 못하는 드라이버들의 개선이
이루어질 것으로 보인다.

Toward a smarter OOM killer Nov 15, 2009

http://lwn.net/Articles/359998/

최근 Kame는 OOM patch series의 review를 부탁했다.

http://lwn.net/Articles/359886/

이 문제는 얼마전 mailing list에 올라왔던 어떤 응용 개발자의 한건의 report에서 시작한다.

시스템의 메모리가 부족하여 OOM이 발생하였는데, 실제 물리 메모리를 많이 사용하던
프로세스는 따로 있는데 X 또는 Gnome-Session이 죽는 경우가 발생한다는 것이다.
이 문제를 파악해본 결과 우리는 현재 OOM의 victim 선정에 다소 문제가 있다고
판단하였다.

Victim을 선정하는 데 있어, 현재 실행중인 프로세스의 가상 메모리 주소와
그 프로세스의 하위 프로세스들이 사용하는 가상 메모리 크기를 고려하는 것이
make sense하지 않다고 생각한 것이다.

위와 같은 알고리즘 덕택에 gnome-session이나 X와 같이 많은 자식 또는 많은 라이브러리를
사용하는 프로세스들은 실제 사용되는 물리 메모리와는 상관없이 상당히 큰
oom_score를 갖게 된다.

이에 barrios는 vm size가 아닌 rss size를 고려하기를 제안하였으며,
이를 바탕으로 kame가 구현하기 시작한 것이 이번 LWN의 주제인 OOM killer 패치이다.

http://lkml.org/lkml/2009/10/27/26


Kame와 barrios는 fork-bomb process를 구별하는 방법에 관해서도 의견을 나누었었지만,
barrios의 의견은 커널이 그것 까지 고려하는 것은 overhead가 크다는 것이었고,
그렇게 해서 알수 있다하더라도 정확한 구별을 할 수 없어 결국 innocent process가 여전
히 죽임을 당할 수 있다고 판단하였다. 이에 kame는 barrios 의견에 동의하였으며,
최근 KDE가 session manager를 위해 oom_adjust를 조정하도록 변경되었다는 점에 주목하며
일단락을 맺는 것으로 생각하였으나, 얼마 후 이 patch series를 만들었던 것이다.

이 패치에 대한 첫 인상은 굉장히 인상적이라는 것이다. 패치의 주된 내용은 다음과 같다.

1. fork-bomb process 식별 방법,
2. 오랫동안 실행되며 찔끔찔금 메모리 누수를 하는 프로세스 식별 방법
3. low memory를 가장 많이 사용하는 프로세스 식별 방법.
4. kill해서 가장 많은 메모리를 회수할 수 있는 프로세스
5. 최근 실행된 프로세스들에게 페널티를 주는 루틴의 삭제

위에 열거한 것들이 의미하는 것은 fork-bomb 프로세스, 메모리 누수 프로세스,
low memory를 많이 사용하는 프로세스, 현재 가장 많은 물리 메모리를
사용하고 있는 프로세스를 kill하겠다는 것이다. 이 중에 low memory 문제는
메모리 할당에 있어 low memory를 필요로 할때, (즉 커널이 물리 메모리를 필요로
하는 경우가 대부분 이 경우에 속한다|) low memory를 많이 사용하는 프로세스를
kill하겠다는 것이고, 나머지는 일반적인 경우이다.

LWN에서도 언급한 것과 같이 이 패치에 대해서 우려의 목소리가 있다. 너무 급진적인
변경이라는 것이다. 그 우려의 목소리가 barrios의 목소리이다.

개인적으로 barrios는 fork bomb detector는 현재의 OOM heuristic에 add되어 사용될 수
있을 것이라고 생각하였지만, 나머지들은 OOM hurisitic 계산의 큰 변경은 현재와는
상당히 다르기 때문에 차근차근 하나씩 변경해 나가는 것이 이미 널리 사용되고 있는
상용 운영체제의 문제 해결 과정이라고 생각한다.

최근 이 패치는 아직 RFC 단계이며, swapout page의 수를 체크하는 것 까지 mm tree에
merge되었으며 아직 갈길이 멀다. 이 문제는 위에서 언급하지 않았는데 swapout된
페이지를 많이 갖는 것은 그 만큼 많은 메모리를 사용했다고 볼 수도 있지만, 꼭
그렇다고만은 볼 수 없으며, OOM killer가 이런 프로세스를 죽인다고 해서 현재 가용한
물리 메모리를 확보하는 것은 아니다.

어쨌든 swap page count는 꼭 이 경우가 아니더라도 여러가지 유용함으로 현재 merge가
된 상태이다.

barrios는 OOM에 관한 또 다른 생각을 가지고 있는데 기회가 되면 나중에 한번 더
정리하도록 한다. 왜냐하면 고이자던 아들이 깨고 말았다.