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에 관한 또 다른 생각을 가지고 있는데 기회가 되면 나중에 한번 더
정리하도록 한다. 왜냐하면 고이자던 아들이 깨고 말았다.

How Google uses Linux Nov 8, 2009

http://lwn.net/Articles/357658/

구글보다 더 많이 Linux를 사용하는 조직은 없을 것이다. 하지만 kernel community는
구글이 어떻게 리눅스를 사용하고 있으며 어떤 문제들을 겪고 있는지 아는 바가 거의 없었다.
왜냐하면 구글은 kernel community에 모습을 잘 드러내지 않기 때문이다. 기껏해야
David Rientjes, Paul Manage정도가 주로 활동을 하고 있으며, 지금 우리나라의 개발자들이
관심이 많은 구글의 Android kernel 개발자들은 메일링 리스트에서 가끔 눈에 띄긴 하지만
그리 active하게 활동하진 않는다. 구글의 Android 커널 팀은 오늘의 주제와는 관련 없는
팀이며 오늘의 얘기는 구글의 서버를 maintain하고 있는 커널팀에 대한 얘기이다.

이번 JLS(Japan Linux Symposium)에서 구글의 커널팀 Mike Waychison은 Linux kernel community
에게 아주 흥미로운 주제들 몇가지 던지고 갔다. 비록 barrios는 JLS를 참가할 수 없어
직접들을수는 없었지만역시나 Jonathan Corbet이 잘 정리를 해주어서, LWN 기사로나마
그날의 흥미로움을 대신 전한다.

생각보다 구글의 커널 조직은 크지 않았다. 대략 30명 정도의 개발자로 이루어져있으며
Andrew Morton은 이 팀에 속하지 않는 것으로 판단된다. Kernel의 형상관리는 Git이 아니라
Perforce라는 툴을 사용한다고 한다. 시작을 관리 툴을 언급하며 Git을 사용하지 않는다는
것에 대해 멋적어서인지 웃음으로 시작하였다고 한다. 리눅스 커널을 Git을 사용하여 관리하지
않는다는 것이 그 만큼 창피한 일이 되어버린 것이다. 구글의 Perforce에는 단지 하나의
base tree만이 있을 뿐이며, 모든 개발자들이 그곳에 commit하고 있다.
17개월마다 mainline kernel을 base로 그 tree를 다시 rebase하고 있어 항상 porting에
애를 먹는다고 한다. Porting이 정상적으로 동작하기 시작하면 6개월마다 내부 release를
한번씩 한다. 그들이 Porting에 애를 먹는 것은 그들의 feature가 드라이버들이 아닌
core 패치들이기 때문이다. 이를 미루어 볼때 30여명의 core 개발자들로 이루어진 구글의
커널팀이 마냥 부럽기만 하다.

구글은 이와 같은 작업을 2.4.18부터 시작해왔으며 2000개 이상의 패치들 492,000 line정도를
수정했다고 말하고 있다. 대부분의 작업은 kernel core에 관한 작업들이다.
그래서 더욱 Porting에 있어 더욱 민감하며, 결국 구글은 일의 효율성을 위하여
mainline kernel community와 더욱 tightly 협력하도록 모든 것을 변경할 계획을 가지고 있다고
말하고 있다.

구글은 지금 2.6.26을 base로 하여 다시한번 rebase를 진행하고 있다.
2.6.26에 1208개의 패치를 하고 있으며, 300,000 line의 코드가 들어가고 있고, 이중의 25%는
새로운 feature라고 언급하고 있다. 이에 Linus는 물었다.
"왜 구글은 그러한 기능들을 upstream 올리지 않느냐? 구글은 그 코드들이 창피하냐?
아니면 보안해야 할 사항이냐? 그것도 아니면 내부 프로세스 문제이냐?" 라는 질문에
Mike는 간단히 "창피하다"라고 말했다. 2.4.18로부터 온 굉장히 ugly stuff라는 것이다.
또한 그러한 feature들이 다른 곳에 도움이 될지도 내부적으로 의문이 든다고 판단하고
있다는 것이다. 하지만 아마 코드의 반정도는 upstream될 수 있다고 보고 있다.
Mike가 솔직하게 대답하고 있다. 대부분의 회사가 그럴 것이다. 사실 mainline에 merge될
정도의 code quality로 일을 하는 회사가 Redhat, SUSE, IBM, Intel 정도를 빼고는
몇이나 있을까? 다들 자신들의 제품의 특성에 맞게 동작할 수준의 코드들로 QA나 Review없이
일단 동작하기만 하면 넘어갈 것이다. 회사의 특성상 바쁘다는 핑계로, 여력이 없다는 핑계로
말이다. 이렇게 넘어가자고 한 관리자의 말에 두 손을 들어버리면 결국 나중 그 관리안된 코드를
기반으로 눈덩이처럼 불어난 코드들과 그로 인한 버그들로 그때 그 관리자한테 뒤통수를 맞는
것은 다시 그 개발자가 될 뿐이다.

구글은 그 사실을 잘 알고 있으며, 더욱 중요한 것은 실천을 한다는 것이다.
별것도 아닌 기술을 IP라고 포장하여 언제까지나 Close하는 회사들에 비해서는 약간 앞서
있지만 솔직히 구글도 그러고 있을 것이라고는 생각치 못했었는데. barrios는 개인적으로
그렇게 생각하고 있었다.

현재 구글은 커널 소스 관리를 위해 Git으로 옮겨가고 있으며(이렇게 새로운 형상관리 툴로
전진해나가는 곳이 있는가 하면 후진하는 곳도 있다. 관리의 효율화와 일원화라는 명목하에 주객
이 전도되는 상황을 barrios는 늘상 보곤한다), 3달마다 한번씩 mainline kernel에
대해 rebase할 계획을 가지고 있다고 한다. 3달마다 한다는 것은 결국 mainline version의
출시와 발을 맞추겠다는 의도로 생각할 수 있으며, 그렇게 하려는 이유는 결국 개발자들의
code maintainace를 좋게 만들기 위해서 그리고 upstream kernel과 보조를 맞추기 위해서이다.
왜 upstream kernel과 보조를 맞추어야만 하는지에 대해 따로 설명하지 않겠다. 최소한
이 블로그의 글을 보는 사람이라면 이 문제에 대해서는 barrios가 굳이 설명을 안해도 될 것이다.

지금까지 구글이 이렇게 mainline kernel과 괴리가 있었던 것은 3가지 이유에서 기인한단고
barrios는 생각한다.

첫째로 그들이 사용하는 커널은 소프트웨어 회사 중 가장 큰 server farm을 자랑하는 server
들을 위한 커널이며,
둘재로 그들은 그 커널을 마음대로 주무를 수 있는 capability를 가지고 있다는 것이다.
셋째는 하지만 그들은 게을렀다는 것이며 이제는 그 결정을 다시 생각해야 할 때라는 것을
알고 JLS에서 세션 하나를 맡아 주었다는 것이다. ^^;

기사에 구글이 mainline kernel을 사용하며 겪었던 문제들을 열거하고 있다.
하나씩 살펴보기로 하자.

구글은 CFS로 넘어간 스케줄러에 대해서 별로 좋아하지 않고 있다.
구글은 user space lock mechanism을 위한 별도의 library를 가지고 있는 듯하다.
이에 문제가 발생한 것은 sched_yield의 semantics가 CFS가 도입되며 변했다는 것이다.
기존의 semantic은 가장 높은 우선순위의 태스크가 sched_yield를 호출할 경우,
같은 우선순위의 다른 task가 없다면, 자신이 다시 제어권을 받을 수 있음을 보장하였다.
하지만 CFS에서는 그렇지가 못하다. 이는 그들이 사용하는 locking관련 라이브러리에서의
high priority 쓰레드들의 sched_yield 함수 호출은 다른 task로의 스케줄링으로 이루어지며
많은 load balancing을 현상을 만들어 낸다는 것이다. 구글은 16~32개의 core의
시스템에 5000개의 쓰레드들을 돌리고 있기 때문에 이는 심각한 성능 문제를 야기할 수 있다.

무엇보다 그런 big thread design의 문제는 mmap_sem의 lock contention이 심하다는 것과 signal을 large thread group에보낼때 많은 run queue들의 lock contention이 심하다는 것이다.
특히 mmap_sem에 관해서는 다음의 시나리오도 가능하다. 쓰레드 A,B,C가 있다고 가정하자.

A - readlock - Wait I/O
B - writelock -> Wait to complete readlock
C - readlock -> Wait to complete B's writelock

즉, A의 readlock으로 인해 B가 대기하게 되고, B의 writelock으로
인해 C의 readlock이 대기하는 상황에서, 갑작스레 A가 OOM kill이 된다고
가정하자. A,B,C를 포함하는 프로세스에 대한 mm관련 일들은 모두 halt될 것이며
이 프로세스가 어떤 프로세스냐에 따라 시스템의 halt까지 유발할 수도 있다.

mmap_sem 관려해서는 현재 Christoph가 per-cpu allocator와 mutex를 혼용하는
방법에 대한 새로운 패치를 내었다. barrios는 그 패치에 대한 몇가지 문제점을
지적해 놓은 상태이며 그 중의 일부 아이디어가 반영되어 다음 릴리즈에 반영되었다.
하지만 그보다 심각한 문제가 있기때문에 아직은 RFC 단계이며, 그 패치가 merge가
될 경우, mmap_sem의 readpath는 RW semaphore를 사용하는 것이 비하여 굉장히 빨라질 수 있다.

메모리 관리 측면에서는 dirty bit의 관리가 변경되며 kswapd는 small I/O operation들에
대해 예전에 비하여 잦은 writeout을 발생시키게 된다. 이는 다른 writeback들을
starving시키게 될 수 있다. 이 문제는 2.6.32에 merge될 per-BDI writeback에
의해 fix될 수 있다.

구글은 시스템의 성능이 overload되는 것을 막기 위해서 OOM killer를 사용하고 있다.
하지만 위에 언급한 것과 같이 oom kill되는 프로세스가 mutex를 hold하고 있을 경우,
시스템은 큰 문제에 빠질 수 있게 되는 문제를 가지고 있다. Mike가 궁금해했던
"memory가 tight하다면 단순히 allocation을 실패시키면되지, 왜 그렇게 열심히
OOM kill을 수행하는지"에 대한 답변은 kernel의 allocation은 그렇게 할 수 있으며
이미 그렇게 하고 있다. 이는 OOM이 아니라 page allocaion failure이다.
하지만 user page는 그렇게 할 수 없다. 그 이유는 Linux kernel은 Demand Paging을
사용하기 때문에 allocation을 하는 시점과 paging in되는 시점이 다르기 때문이다.
더 자세한 이야기는 오늘의 주제가 아니니 넘어가도록 하자.

그래서 구글은 지금 무엇을 하고 있는가?
구글은 그들의 work들을 3가지로 분류한다.

"latency sessitive", "production batch", "best effort" 그래서 이 분류들을
fake NUMA node 기능을 이용하여 분리하고 각 job들을 성격에 맞춰 하나 이상의
노드들에 assign하는 것이다. 구글이 add한 기능은 barrios의 충분한 관심을 끈다.
NUMA-aware VFS lru를 적요하고 있기 때문이다.
이는 예전에 Nick Piggin이 했던 것과 유사하며 그는 구글의 코드들을 보길 원해왔다.

구글은 SCHED_GIDLE 스케줄링 클래스를 만들었다. 어떤 spare CPU도 있지 않을 경우,
이 클래스에 job들은 실행되지 않을 것이다. 이때 발생할 수 있는 priority inversion 문제를
풀기 위해 SCHED_GIDLE 프로세스들이 커널에서 sleep하게 될때는 일시적으로 priority를
높이게 된다.

구글의 I/O scheduleing의 경우에는 proportional I/O scheduling을 사용하고 있다고
한다. 그것 말고도 구글은 시스템 monitoring을 위한 많은 코드들을 add하고 있어,
disk, network traffic을 monitor하고 기록해두어 나중에 operation 분석을 위해
사용한다고 한다.

다음은 구글은 2010년까지의 목표이다.

* CPU limitations - latency-sensitive한 태스크들에게 더 높은 우선 순위 접근을
주면서도 전체 시스템을 장악하는 것은 막게 하겠다는 것.

* RPC-aware CPU scheduleing - 들어오는 RPC traffic을 살펴보고 어떤 프로세스를 응답으로 깨울 것이며 그 wakeup이 얼마나 중요한 지를 결정하는 것.

* Delayed scheduling - 대부분의 쓰레드들에게 있어 latency는 중요하지 않다. 하지만 kernel은 RPC msg가 들어왔을 때 즉시 그 쓰레드들을 실행시키려고 시도한다. 이 msg들은 CPU들에 고르게 분산되지 않아 심각한 load balancing 문제를 야기한다. 그래서 쓰레드들은 delayed scheduling으로 tagging될 수 있다. 즉, wakeup이 도달하면 즉시 run queue에 들어가는 것이 아니라 실제로 runnable해지기 전에 다음 global load balancing operation이 발생할때 까지 기다린다.

* Idel cycle injection - machine을 항상 최고 power로 실행할 수 있도록 power-management를 하겠다는 것, 하지만 system이 melt down되게 하지는 않겠다는.

* 커널 메모리 사용까지 accouting하는 향상된 memory controller

* offline memory - 저렴한 가격으로 메모리를 구입하는 것이 점점 어려워 진다는 판단하에 단지 몇 개의 cell만이 bad가 났음에도 전체 메모리를 교체하는 것은 옳지 않다는. 해서 HWPOISON을 통해 bad page들만을 따로 관리하겠다는.

* 동적으로 huge page들을 assemble하고 broken down하기 위한 방법

* block layer overhead를 줄여 high-speed flash의 속도를 최대한 내겠다는. block layer에서 disk 가속을 위해 flash를 사용하겠다는 것이다.

마지막으로 Mike는 몇가지 흥미있는 주제들을 던지며 그날 세션을 끝마쳤다.
구글이 원하는 것 중의 하나는 file system metadata를 memory에 pinning하는 것이다.
해서 I/O request를 service하는데 걸리는 시간을 bound하겠다는 것이다.
디스크로부터 하나의 블록을 읽는데 걸리는 시간은 알수 있지만,
관련 metadata가 메모리에 있지 않은 경우, 한번 이상의 disk I/O 이상이 필요해진다.
이것은 시스템을 느리게 만들고 있다고 말하고 있다. 구글은 현재 file data를
user space에서 raw disk device로부터 직접 읽음으로써 이러한 문제를 우회하고 있다고 한다.
하지만 언제까지 그렇게 할 수는 없고, 이제는 멈추고 싶어한다.

다른 문제는 caching advise를 제공하기 위한 system call overhead를 낮추는 것이다.
이 문제는 명확하지 않다.

Anyway, 이번 구글의 세션은 kernel community가 가장 큰 customer로부터 많은 걸 배울 수
있었던 성공적인 session이었다. 구글은 앞으로 더욱 큰 결실을 맺기 위해 community와
협업을 더 적극적으로 할 계획을 가지고 있으며 이는 모두에게 더 훌륭한 커널을 안겨줄 수
있는 좋은 기회가 될 것이다.

barrios는 위와 같은 선진 소프트웨어 회사들의 그 중에서도 커널 팀들의 행보를 지켜보며,
우리의 현수준을 직시하고, 우리가 가야할 길에 대한 생각을 멈추지 않을 것이다.
비록 지금은 먼 것 처럼 느껴지더라도, 조만간 쓸 일이 있지 않을까 한다.