OOM killer Internal Jun 13, 2010

최근 몇달간 OOM killer를 향상시키기 위한 많은 논의들이 있었다.
그 시작은 fork-bomb를 detect하는 것에서 시작하였으나, David는 OOM전체의
개선으로 긴 여정을 시작하였다.

현재 mmotm 2010-06-11-16-40에 merge되었다. 이 패치를 Andrew가 받아들이기
전까지 정말 많은 우여곡절이 있었다. 휴.. 얘기하자면 정말 재밌는데 온라인에서
글로 설명하기에는 한계가 있다. 이런 재밌는 얘기는 맥주한잔하며 재밌는 일화정도로
얘기하면 딱이다.

사실 이 패치들에 대해서 글을 쓰려고 하였으나, 최근 많은 분들이 OOM의
동작과정에 대해서 궁금해 하는 것 같아 OOM의 동작과정에 대해서 간단히 정리해 보았다.

워낙에 글솜씨가 없는 편에다 코드를 설명해야 하는 것은 말이든 글이든 더욱 소질이 없지만
이 별볼일 없는 설명이 도움이 되었으면 한다.

하지만 알아두어야 할 부분은 아래의 내용 중 일부는 곧 바뀌게 될 것이라는 것이다.

---

우선 OOM killer가 언제 호출되는지 살펴보도록 하자.

1. mm_fault_error
2. moom_callbak
3. __alloc_pages_may_oom

mm_fault_error가 호출되는 시점은 system의 page fault handler가
호출되어 fault를 처리하는 도중 필요한 메모리를 할당하지 못하고 반환되는
경우 호출된다. 일반적으로는 페이지를 할당하는 함수내에서 먼저 OOM killer가
동작하여 페이지를 회수하지만 그렇지 못할 경우 error는 page fault handler에게
까지 propagate되어 결국 mm_fault_error가 호출되어 OOM kill을 하게 된다.

이렇게 호출되는 out_of_memory는 다른 두 곳에서 호출되는 out_of_memory함수와는
다르다. 다른 out_of_memory 함수들은 out of memory 상황이 발생된 context를
알수 있는 반면 page fault handler를 통해 호출되는 out_of_memory에서는 알수 없다.

out of memory의 자세한 동작에 관해서는 3번 __alloc_pages_may_oom을 통해서
호출되는 경우를 통해 자세히 살펴보도록 하자.

Linux의 page allocator의 page 할당 실패는 우선 kswapd를 깨워
background reclaim을 하게 된다. 그래도 필요한 페이지 할당에 실패할 경우
direct reclaim을 하게 된다. direct reclaim을 한후마저 어떤 페이지도 회수하지
못하는 경우 __alloc_pages_may_oom을 호출하게 된다.

__alloc_pages_may_oom 함수는 zonelist의 OOM lock을 hold 시도한다.
zonelist란 현재 할당을 요구한 zone이하의 모든 zone을 의미한다. 모든 zone에서
OOM이 발생하지 않고있는 경우 OOM lock의 hold 시도는 성공하게 되지만 어느 한 zone이라도
이미 OOM killer가 동작하고 있는 경우라면 OOM lock hold에 실패하게 되며 더 진행하지
못하게 된다.

OOM lock을 획득한 경우 out_of_memory 함수를 호출하게 된다.
이 함수는 우선 constrained_alloc을 호출하여 현재 할당 요청에 constrain이
있었는지 파악한다. constrin은 2가지 경우가 있다.

1. MPOL_BIND와 같은 memory policy 때문에 발생한 경우
2. CPUSET의 softwall에 의해 발생한 경우

1에 의해 OOM이 발생한 경우는 oom_kill_process를 호출하고 current를 kill하게 된다.
이 함수는 추후 살펴보기로 한다.
2의 경우나 constrain이 없는 일반적인 경우 __out_of_memory 함수를 호출하게 된다.

__out_of_memory 함수는 우선 victim process를 찾기 위해 select_bad_process를 호출한다.
우선 victim의 대상은 시스템 전체의 process들이다. 하지만 kernel thread와
init process는 대상에서 제외된다.

또한 victim을 찾기위해 process들을 scanning하는 과정에서 이미 reserved memory를
사용하도록 허락된 process를 만나게 되면 scanning을 종료하고 반환한다.
TIF_MEMDIE가 process의 그러한 status를 나타내기 위해 사용되는데 이 flag가 지정된 경우
process가 종료하고 있는 과정에 있고 종료를 하기 전 까지(즉, KILL signal을 처리하기 전까지)
하던 작업을 마무리 하기 위해 dynamic memory가 필요할 수 있기 때문에 reserved memory를
사용하도록 허락한 것이다. 그러므로 다른 task 들에게도 reserved memory 사용하도록 허락하게
되면 앞의 task가 종료하기 위한 메모리가 모자라 livelock 상황에 처할 수도 있게 된다.

또 다른 exception case로 task의 flag가 PF_EXITING인 경우가 있다.
PF_EXITING의 flag가 지정된 task는 종료처리를 하고 있는 과정임을 의미한다.
이 flag과 TIF_MEMDIE와의 다른 점은 TIF_MEMDIE는 kill signal을 보냈고 task의
빠른 종료를 위해 reserved memory를 사용해도 좋다는 것을 의미하는 반면 PF_EXITING은
kill signal을 처리해서 현재 do_exit 함수를 실행하고 있다는 것을 의미한다.
즉 PF_EXITING이 지정된 task가 실제 종료되고 있는 task이다. 이런 task를 만났을 경우,
그리고 그 task가 current가 아닌 경우 앞의 경우와 마찬가지로 무고한 task를 kill하지
않고 함수는 즉시 반환한다. 즉 무고한 다른 프로세스를 kill하지 않고 조금 기다리겠다는 것이다.
반면 current인 경우 한시라도 빨리 죽기를 희망하여 TIF_MEMDIE를 지정해주기 위해
그 task를 victim으로 선정한다. (reserved memory를 사용할 수 있게 해주기 위해서이다.)

위의 exception case에 걸리지 않는 일반적인 task들은 badness 함수를 호출하여 task의
oom point를 계산하게 된다.

badness 함수의 목적은 victim 프로세스를 최대한 다음과 같은 rule에 맞게 결정하기
위해 힘쓴다.

1. 최소한의 양의 일만을 잃을 것
2. 많은 memory를 회수할 것
3. 메모리를 많이 소비하는 task중에 죄없는 프로세스는 죽이지 말것
(즉, memory leak을 하고 있는 프로세스를 죽이자는 것이다.)
4. 최소한의 프로세스만 죽일 것
(되도록 한 프로세스만을 kill해서 시스템을 위급 상황에서 벗어나도록 하자는 것이다.)
5. 사용자가 죽길 원하는 프로세스를 죽이려고 노력할 것

우선 task가 OOM_DISABLE로 설정되어 있다면 score는 0이다.
즉, kill되지 않는다는 것이다.이는 oom_adj를 통해 설정할 수 있다.
자세한 것은 Documentation/filesystems/proc.txt 파일을 참조하라.

OOM_DISABLE이 되어 있지 않은 프로세스는 badness score를 계산히기 위해
total_vm의 크기를 base로 삼는다.p->flags가 PF_OOM_ORIGIN으로 되어있는
경우 별다른 계산 없이 OOM의 최대 score를 반환한다.
이 flag는 swapoff를 하는 시점이나 KSM을 실행시켰을 때 임의의 task에
설정될 수 있다. swapoff난 KSM이 실행될 때의 process context는 많은 메모리를
소모할 수 있기 때문에 그러한 task를 먼저 kill하도록 하는 것이다.

다음 task의 children 중 현재 task와 mm이 같지 않은 task들(!CLONE_VM)의
total_vm size의 1/2을 score에 더한다. 즉, 많은 task들을 fork한 fork-bomb를
detect하기 위함이다. 하지만 1/2을 더하는 이유는 실제로 children 중의 하나가 많은
메모리를 소모하고 있을 경우 parent보다는 child를 victim이 되게 하기 위해서다.

다음으로 task와 그 thread 그룹들이 시작된 이후로 얼마나 많은 CPU를 소모했는지에
따라 point값이 변하게 된다. CPU를 많이 사용했다는 것은 한 일이 많다는 것이다.
즉 1번 rule에 따라 많은 일을 한 프로세스의 score는 낮아진다. 또한 얼마나 오랫동안
실행되어 왔는지도 영향을 미친다. 오랫동안 실행된 프로세스가 많은 일을 했을 가능성이 높기
때문이다.

task의 nice가 고려된다. nice한 프로그램은 다른 프로그램보다 score가 배로 높아진다.
task가 superuser process들이라면 point 값은 낮아진다.

task를 구성하고 있는 쓰레드 그룹들이 OOM이 발생된 current와 같은 CPU_SET group을
가지고 있지 않다면 point를 낮춘다.

마지막으로 oom_adj 값을 가지고 지금까지 계산된 points를 가감한다.
oom_adj가 큰 양수일 수록 score 값은 높아지게된다.

위와 같은 rule에 의해 선정된 victim task는 oom_kill_process 함수를 통해 killing된다.
이 함수는 victim task의 child를 먼저 kill하고 children들이 모두 kill될 수 없는 경우만
parent인 victim task를 kill하게 된다.

실제 kill을 하는 함수는 oom_kill_task이다.

이 함수는 __oom_kill_task를 호출하여 SIGKILL을 보내게 된다.
이때 task의 time_slice 값을 HZ로 올려주어
task를 bump up시키며 task가 reserved mempool을 접근할 수 있도록
TIF_MEMDIE를 지정해준다.

lowmem_reserve_ratio

최근 어떤 개발자로부터 memory fragmentation으로 인한 문제를 들은적이 있다.
음. 많은분들이 lowmem_reserve_ratio에 관해 아직은 잘알지 못하고 있는 것 같아
정리한다.

일반적으로 1G 이상의 물리 메모리를 갖는 시스템에서 kernel은 동작의 효율을
위해 high memory 공간을 잘 활용하지 않는다. 왜냐하면 kernel이 highmem공간을
주소로 접근하기 위해서는 kmap/kmap_atomic과 같은 함수를 통해서 page-to-address
변환 작업이 필요하기 때문이다.(user process의 경우에는 문제 되지 않는다.)
그러므로 low memory는 커널이 제일 선호하는 공간이다.

그렇다면 이런 low memory를 application이 사용하게 되면 무슨 일이 벌어질 수 있을까?
사실, kernel은 application들의 사용을 위해 할당하는 메모리는 high memory를 사용하려고
애쓴다.하지만 high memory의 페이지가 부족할 경우, fallback zones 즉,
NORMAL, DMA32, DMA zone을 사용할 수 밖에 없게 된다. 이때 NORMAL zone에서
application을 위한 페이지를 할당하게 됐다고 가정할 경우, application이 해당 page를
mlock해버린다면 또는 임베디드 시스템에서와 같이 swap system을 가지고 있지 않을 경우, heap이나
stack을 위한 페이지를 할당하게 된다면 무슨 일이 발생할까?
이것이 의미하는 것은 kernel은 페이지 회수를 할 수 없게 된다는 것을 의미하고 이는
바로 memory fragmentation 문제로 이어지게 된다.

이러한 현상을 막기 위해 커널은 /proc/sys/vm/lowmem_reserve_ratio 라는 knob을 제공한다.
barrios의 system에서의 lowmem_reserve_ratio는 다음과 같이 출력된다.

#> cat /proc/sys/vm/lowmem_reserve_ratio
256 32 32

라고 출력된다.

이 값은 다음과 같이 사용된다.

1G RAM을 기준으로 DMA(16M), NORMAL(784M), HIGH(224M)를 쓰게 될 경우라고 가정하고
ZONE_DMA의 경우, ZONE_NORMAL의 target의 fallback으로 memory를 할당하게 될 경우,
784/256의 메모리를 reserve한다.
ZONE_DMA의 경우, ZONE_HIGHMEM의 target의 fallback으로 memory를 할당하게 될 경우,
(224 + 784) / 256의 메모리를 reserve하게 된다.
ZONE_NORMAL의 경우, ZONE_HIGHMEM의 target의 fallback으로 memory를 할당하게 될 경우,
224/32 의 메모리를 reserve하게 된다.

이것이 어떻게 사용되는지 살펴보자.

#> dmesg | grep zone
...
Normal zone: 221486 pages, LIFO batch:31
....
HighMem zone: 294356 pages, LIFO batch:31
...

barrios의 system에는 normal zone이 221486개의 page로 이루어져 있고
high zone이 294356의 page로 이루어져 있음을 볼 수 있다.
그러므로 위의 rule을 적용시켜 보면

- NORMAL zone을 대신해서 DMA_ZONE이 사용될 경우)

221486 / 256 = 865

- HIGHMEM zone을 대신해서 DMA_ZONE이 사용될 경우

(221486 + 294356) / 256 = 2015

의 메모리가 reserve된다는 것이다.
실제로 아래의 명령을 통해 확인해보자.

#> cat /proc/zoneinfo | more
...
protection: (0, 865, 2015, 2015)
...

위의 계산과 일치하는 것을 볼 수 있다.
마지막 2015는 ZONE_MOVABLE zone을 위한 것인데 지금은 신경쓰지 말자. (얘기할 기회가 있겠지)

이와 같이 하위 zone은 상위 zone들의 fallback으로 사용될 경우 위와 같은 rule에 의해
page를 reserve하게 된다.

정리하자면, 커널은 메모리 요구가 발생하였을 경우, 호출자가 선호하는 zone에서 page를 할당하기
위해 노력한다. 하지만 그 요구를 만족시키지 못할 경우 어쩔 수 없이 fallback list에서(ex, 하위 zone들)
에서 페이지 할당을 하게 된다. 이는 자원을 효율적으로 사용한다는 측면에서 나쁘지는 않다. 하지만 각 zone들은
원래의 목적이 있기 마련인데 다른 목적을 위해 페이지가 사용될 경우, 원래의 목적에 페이지가 필요한 경우
페이지가 모자라게 되어 심각한 문제가 발생할 수 있다. 이는 order 0 페이지의 경우에는 덜하지만
order가 커지면 커질수록 문제가 발생할 확률이 커지게 된다.

이글이 memory fragmentation으로 인해 문제를 겪는 몇몇 분들에게 도움이 되었으면 한다.

P.S) 한국:그리스 = 2:0 ^O^

2010 Linux Foundation Collaboration Summit Apr 20, 2010

LWN에 재밌는 기사가 떠서 그냥 넘어갈 수가 없었다.
원문은 subscriber만 볼수 있는 시기이기 때문에 1주가 지나고 나면 link를 걸 예정이다.

San Francisco에서 열린 LFCS(Linux Foundation Collaboration Summit)에 관한 요약 기사이다.
이 summit은 barrios 개인적으로는 굉장히 참석해보고 싶은 summit이었지만 여
건이 절대 허락하지 않는 멋쟁이 회사에서 근무하고 있기 때문에 절대 불가능한 일이라
꿈도 꾸지 않는다.

Barrios의 눈길을 단숨에 사로잡은 것은 Graybeards에 관한 기사였다.
요는 커널 개발자들의 젊은피(새로운 피라고 해석하는 것이 더 좋을 것 같다.)가 수혈되지 않는
다는 것에 관한 토론이었다.

하지만 결론은 그렇지 않다는 것이다. 매 커널 릴리즈 주기마다 1000명 이상의 개발자들이
관계하고 있고 그 중의 상당 부분이 처음으로 contribution을 하는 사람들이며 그 중에
20%정도는 barrios와 같이 취미(돈을 받지 않고 자신이 원해서 contribution하는)로
즐기는 사람이라고 말하고 있으며 오히려 contributor중 일부는 다른 application project로
발을 돌리는 것이 차라리 나을 것이라고 말한 것을 들은적까지 있다고 말할 정도로 많은 개발자들이
충원되고 있고 발전하고 있다는 것이다.

하지만 글에 link되어 있는 다른 기사에서는 http://www.jfplayhouse.com/2010/04/why-linux-is-not-attracting-young.html 좀 다른 말을 하고 있다.
새로운 피들이 모이지 않는 이유가 Linux는 이미 corporation stakeholder에 의해 점유되어
발전되고 있다고 말하고 있으며, 이러한 가운데 개인이 취미로 활동하는 작은 부분(ex, webcam driver)에서
얻을 수 있는 만족감이 크지 않다는 것이다. 하지만 barrios는 그렇게 생각하지 않는다.
Mainline kernel community에서는 대부분 그들만의 무대가 있다. 각자의 무대에서 각자의 분야에
집중하다 보면 자연스레 충분한 만족할 수 있다. 물론 개인별로 어느 정도의 만족을 느껴야만 자신이
그 프로젝트에서 큰 contribution을 하고 있다고 느끼는지는 모르겠지만.

하지만 Linux kernel이 이미 돈을 받으며 contribution하고 있는 full-time developer들의 비중이
크다는 것은 부정하지 않는다. 그들이 paid full-time developer가 된 것은 알이 먼저인지 닭이 먼저인지
문제이긴 하지만. 이로 인해 사실 부정적인 영향도 있는 것도 사실이다. 하지만 전체로 보았을 때 긍정적인
면이 훨씬 많기 때문에 지금까지 그래왔듯이 Linux kernel은 잘 진화하고 있는 것이라고 생각한다.

또 다른 얘기로는 Andrew Morton이 말한 kernel core developer들의 경험치와 자신감이 쌓여가며,
점점 더 복잡한 코드들을 넣고 있다는 것이다. 이로 인해 커널 개발의 진입장벽은 점점 높아지며
그로 인해 복잡한 코드들을 유지보수하기 어려워질 것이라는 이슈가 있다.

이것도 정말 공감한다. 지금 리눅스 커널은 barrios가 linux를 보기 시작한 몇년전에 비해 너무나도
급변하고 있으며 너무나도 복잡해지고 있다. 또한 점점 많은 feature들이 들어가며 알아야 할 것들이
너무 많아지고 있는 추세이다. 이는 새로운 커널 개발자들의 진입을 저해하기에 안성맞춤이다.
최근 몇년 전가지는 훌륭한 커널 서적들이 많았으나, 최근 주춤하는 시기에 커널은 급변했고,
저자들은 black hole(Robert Love)로 들어갔거나, 박사학위 준비중에 바쁘거나(Mel),
먹고 사느라 힘들기(Jonathan) 때문에 Gap을 채워줄 훌륭한 material들이 절대 부족하다.
다행스러운 것은 kernel의 document들과 source code들의 주석, git등이 점점 잘 되어가고 있다는
것이다.

이 말고도 이번 Summit에서는 Google의 Open Source Program Manager인 Chris DiBona의 talk도
있었다. 구글은 Open Source Developer의 black hole이라는 평판을 들을 정도로 한번 구글로 입사한
개발자들은 Open Source Community에서 모습을 감추는 경우가 종종 있다.(이것에 대해서는 구글 나름데로
이유가 있는데 다음에 기회가 되며 얘기하기로 하고..) 이번 talk에서 Chris는 구글이 Open Source 진영에
얼마나 많은 contribution을 하고 있는가를 설명하며 사과를 해야하는 입장이 아니라 오히려 칭찬받아야 하는
입장이라고 말한다고 전하고 있다. 하지만 많은 사람들이 수긍하는 분위기는 아니었던 것 같다.
Android에 관해서는 자신들의 코드를 upstream에 merge시킬 메조키스트가
필요하다고 말하고 있다. 이 말에서 늬앙스는 mainline kernel의 upstream에 merge시키는 프로세스와
따가운 시선들(many reviewers)을 다 극복하고 자신의 에너지를 쏟아 부어 그 안에서 보람을
느끼는 사람이 없다는 것이다. Barrios는 거꾸로 메조키스트를 언급한 것을 보면 구글 내부적으로 그러한
일을 못하게 하지는 않지만 누군가 총대를 매고 하지 않는 한 굳이 시간과 노력을 당분간은 들이고 싶지
않겠다는 뜻으로 해석한다. 어쨌든 그의 talk은 성공적이지 못했다고 전하고 있으며, 더욱 중요한 것은
성공적이지 못한 talk 대신에 그의 세션을 참석했던 모든 사람에게 Nexus One phone을 주었다는 것이다.
이것은 많은 blame들을 잠재우는 데 크게 한 몫 했다는 후문이다. 이게 오늘의 Point이다. 대인배 구글.
원래 barrios와 같이 소심한 엔지니어들은 이런 사소한(?) 것 하나하나에도 마음이 휘둘리기 쉽상이다. -_-;;

세션이 끝나고 Jonathan은 따로 Android 커널 개발자들을 만났다고 한다. 이들의 얘기는
Chris의 얘기는와는 또 달랐다고 한다. 그들은 굉장히 여느 embedded systems developer와
같았으며 즉, 언제나 상품 개발 주기는 매우 짧고, 시간은 항상 부족하고 해서 upstream에 source를
merge시킬 엄두를 못내고 있다고 한다.(이 말에 절대 "우리도"라고 동조하지 말자. 우리는 시간이
없어서가 아니라 우선 가장 크게는 "mind가 안되어 있고" 둘째로 "내공"이 부족하다.
솔직히 인정할 건 인정하자.엔지니어니까)이 부분은 barrios도 상당부분 공감한다.

하여튼 Android 커널 개발자들은 점점 외톨이가 되가고 있음을 느끼고 있으며 그것은
그들을 좌절시킨다고 느끼고 있다고 전하고 있다. Jonathan은 이 시점에서 Android 커널 개발자들이
community가 그들과 소통하려고 하고 있는 것을 들어왔고 잘 이해하고 있다고 말하며,
이번 기회를 발판으로 그들의 merge 시도를 좀더 도와줘야 하는 시점이라고 말하고 있다.

Barrios야 예전부터 android kernel의 입봉을 원하고 있었기 때문엔 당연히 그런 시점이 오면
절대적으로 support할 것이다.^^

Problem of direct reclaim page writeback Apr 19, 2010

오랜만이다. 이렇게 블로깅을 하는 것은.
이유야 여러가지가 있지만 구구절절 말할만한 상황은 아니고.

그동안 mainline에는 재미있는 일이 너무나도 많았다.
그 많은 것을 다 같이 공유하고 싶은 마음이 큰데 시간과 barrios의
게으름이 허락치 않는다. 가장 최근에 벌어지는 이슈에 대해서만 먼저
한번 얘기해보자. (나머지는 차차 기회가 있겠지)

http://lkml.org/lkml/2010/4/12/366

지금 barrios가 가장 관심을 가지고 있는 issue는 direct reclaim의
page write back문제이다. 다들 잘 알고 있겠지만 kernel은 OOM 상황을
막기 위해 시스템의 process들의 귀중한 시간을 훔친다. 즉, 하찮은 커널이
무대의 주인공인 프로세스들의 context에서 프로세스를 위해 일을 하는 것이 아니라,
메모리를 회수하기 위해 귀중한 프로세스의 resource를 것도 많이 사용한다는 것이다.

이 자체가 썩 유쾌하지 못한 상황이긴 하지만 kernel 입장에서는 어쩔수가 없다.
프로세스를 죽이는 것 보다야 낫지 않는가.

어쨌든, 지금 이슈는 이 direct reclaim path에서 stack overflow가
발생한다는 것이다. 이 문제를 제일 먼저 report한 이는 xfs의 maintainer라고
볼 수 있는 Dave Chinner이다.

Depth Size Location (47 entries)
----- ---- --------
0) 7568 16 mempool_alloc_slab+0x16/0x20
1) 7552 144 mempool_alloc+0x65/0x140
2) 7408 96 get_request+0x124/0x370
3) 7312 144 get_request_wait+0x29/0x1b0
4) 7168 96 __make_request+0x9b/0x490
5) 7072 208 generic_make_request+0x3df/0x4d0
6) 6864 80 submit_bio+0x7c/0x100
7) 6784 96 _xfs_buf_ioapply+0x128/0x2c0 [xfs]
....
32) 3184 64 xfs_vm_writepage+0xab/0x160 [xfs]
33) 3120 384 shrink_page_list+0x65e/0x840
34) 2736 528 shrink_zone+0x63f/0xe10
35) 2208 112 do_try_to_free_pages+0xc2/0x3c0
36) 2096 128 try_to_free_pages+0x77/0x80
37) 1968 240 __alloc_pages_nodemask+0x3e4/0x710
38) 1728 48 alloc_pages_current+0x8c/0xe0
39) 1680 16 __get_free_pages+0xe/0x50
40) 1664 48 __pollwait+0xca/0x110
41) 1616 32 unix_poll+0x28/0xc0
42) 1584 16 sock_poll+0x1d/0x20
43) 1568 912 do_select+0x3d6/0x700
44) 656 416 core_sys_select+0x18c/0x2c0
45) 240 112 sys_select+0x4f/0x110
46) 128 128 system_call_fastpath+0x16/0x1b

위의 로그를 살펴보면 direct reclaim path전까지 3.1K정도의
stack이 사용되어졌으며 XFS가 3.5K를 사용하는 것을 볼 수 있다.
다음 block layer와 몇가지 더 하면 금방 8K가 바닥이 나버린다.
XFS가 3.5K를 사용하는 것도 크지만 direct reclaim path만도
대략 1.1K나 사용하고 있다. 불과 함수 몇개가 말이다.

이 report는 또 다른 문제를 언급하고 있다. VM의 reclaim으로 인해
발생하는 I/O와 flusher가 발생시키는 I/O가 섞여 결국 random write가
발생하게 되고 이는 reclaimer와 flusher의 throughput을 떨어뜨리게
될 것이다.

이를 해결하기 위해 Dave가 제안한 것은 direct reclaim path에서
아예 writeback을 하지 말자는것이다. 굉장히 공격적인 방법이다.
그러므로 해당 thread는 현재 74개의 메일들로 토론이 진행되고 있다.

처음 토론이 진행되었던 것은 lumpy reclaim 문제이다.
Mel의 lumpy reclaim은 LRU distance와는 관계없이 특정 상황이 되면
lru list에 있던 페이지들에 물리적으로 근접해 있는 페이지들을 회수하여
big order contiguous page들을 만들어 내는 것이다. 이때 필요에
따라 우리는 dirty page들을 flush해야 하는 상황이 필연적으로 발생한다.
그런데 pageout을 생략하게 되면 그러한 lumpy reclaim이 직접적으로 타격을
받게 되는 것이다.

그래서 Mel과 Kosaki는 stack diet를 시도하고 있고, 반면 그것이 근본적인
해결책이 아니라고 사람들도 있다. barrios도 처음에는 전자의 편에 있었지만
좀더 생각해보니 후자가 더 좋을 것이라고 생각한다. 위의 로그를 보면
direct reclaim path도 stack을 많이 사용하였지만 XFS 또한 많이 사용하였다.
그리고 direct reclaim path전에도 무시하지 못한다.
결국 stack diet를 해서 어느 한 곳을 줄여봐야 모든 곳을 줄이지 못하면 언젠가
다시 이 문제를 만나게 될 것이라고 생각한다(우리는 함수가 nesting되는 경우나
다른 함수들을 통해서 호출되는 경우도 생각해야 한다. 위에서 보는 log의 사용량이
절대 worst case가 될 수 없다는 것이다.) 또한 barrios는 앞으로 reclaim path를
수정할때마다 stack 사용량을 일일이 계산하며(ie, 걱정하며 :)) coding하고 싶지 않다.

그렇다고 direct reclaim path에서 I/O를 하지 않게 되면 우리는 보다 많은
OOM을 만나게 될 것이다. 사실 direct reclaim path에서의 writeback은
process들의 progress를 다소 완화시켜주는 역할도 하기 때문이다.

이 와중 Andrew Morton은 양심고백을 하나 하였다.
사실 direct reclaim path에서의 write가 어느날 갑자기 심해졌다는 것이다.
아마 2.6.16 근처였던 것으로 기억하며 아무도 그 문제에 대해서 fix하려고
시도하지 않았다는 것이다. 또한 writeback을 다른 곳으로 돌리는 것은
2.5.10에 시도되었었지만 그리 효과가 없었다고 말하며 address_space를
pinning할 수 없어 writearound 자체가 구현하기 쉽지 않다고 말하고 있다.

Dave의 patch에 관해서는 flusher는 target zone을 고려하지 않고 있어
잘못된 페이지들만을 계속해서 flush하는 상황이 발생하며 이는 system을
livelockable하게 만들수도 있다고 한다. 여기에 barrios는 한가지 더 우려가
되는 것은 LRU distance와 상관없는 페이지들을 대거 writeout함으로써
이어지는 write-merge등에 손해를 볼 수 있고, working set들이 밀려나가게
되어버리는 일도 발생할 수 있다고 생각한다.

Andrew는 I/O pattern 문제를 해결하기 위해서 이전에 언급했던
"왜 갑자기 direct reclaim path에서 많은 I/O가 발생하기 시작하였나?
우리가 그 문제를 피할수는 없는 것인가?" 부터 생각해야 하며
Stack Overflow문제를 풀기 위해서는 자신없어하며 target page를
다른 쓰레드에게 패스하여 해당 쓰레드와 동기를 맞추면 어떨까 한다.

현재까지 이 문제에 대한 별다른 해결책이 없어 보이는 가운데
James Bottomley는 이번 MM summit과 FS summit이 함께 열리기 때문에
그때까지도 문제가 해결이 되지 않으면 그 자리에서 안건을 올려 한번 얘기해보자고
하고 이에 다른 개발자들은 이 제안에 환영하고 있다. 그 이유는 이미 FS 개발자들에게
random I/O 문제는 consensus를 이룬 문제이며, 정말 문제는 MM guys들이
이 문제를 이해하지 못하고 있다고 생각하고 있기 때문이다. 사실 MM guys들이
이해를 못하고 있는 것이 아니라, 어떻게든 많은 부분을 수정하지 않고 고쳐보려고
하는 것이다. -_-;; 하지만 barrios의 생각으론 FS guys들의 의견에 전적으로
동의한다. 간만에 MM summit이 열리는데 재밌는 안건이 될 것이다.
비록 참석은 못하더라도 재밌는 토론거리가 될 것 같다.

Innovators get Linux to boot in 1 second Mar 7, 2010

http://lwn.net/Articles/377507/
http://www.edn.com/article/CA6720353.html

Montavista가 1초 부트를 했다는 기사가 떴다.
자동차 계기판 시스템을 Linux를 사용하여 한 것 같다.

기술내용은 위의 글들로 미루어보아

첫째, 불필요한 커널 옵션 정리, 부트로더에서 redundant한 부분 정리
(임베디드에서 하드웨어가 한번 fix되면 변하지 않는 성질을 응용)

둘째, Linux의 부팅과정 중 필요한 여러 일들을 수행함에 있어 필요한 task들을 로딩하거나
파일들을 읽어오기 위한 Flash와 Memory의 복사 비용을 DMA를 사용하여 줄임.
이때 CPU는 다른 task를 수행함(요즘 CPU는 예전에 비하여 상대적으로 큰 cache를 가지고 있기
때문에 대부분 필요한 일들을 cache에서 hit시켜 위의 여러 작업을 병렬적으로 할 수 있다.)

셋째, 부팅시에 필요한 즉, 사용자에게 마치 모든 작업이 완료되어 당신의 입력을 기다리고
있어요라고 말할만큼의 일을 하기 위해 필요한 application들만을 모아서 ramfs 사용(ramdisk 아님)
으로 생각된다.

기술적으로 별것 아니라고 하면 별것 아닐수도 있지만 한편으로 대단하다 생각하면
대단하기도 하다.
위의 기술들이 upstream에 merge될 수 있느냐, 없느냐가 중요한 것은 아닌 것 같다.
중요한 건 지금 그들은 1초 부트를 하고 있다는 것 뿐이고 다른 사람들은 아직 Linux를
가지고 1초 부트를 하지 못하고 있다는 것이다.

또 여러 사람 고생할게 눈에 불 보듯 선하다.

sys_membarrier() Mar 1, 2010

http://lwn.net/Articles/369567/

최근 membarrier에 대한 system call추가에 관한 논의가 계속되어 왔다.

이 새로운 system call은 Mathieu Desnoyers에 의해 시작되었으며,
자신이 만들고 있는 LTTng tracing toolkit에서 성능을 높이기 위한 목적으로
사용하려고 한다.

Mathieu는 얼마전 Paul과 User-Level RCU library를 만들었었다.
물론 이 library또한 LTTng tracing toolkit에서 사용하기 위해 만들었던 것이다.

User-Level RCU라 하면 가장 먼저 드는 의문이 어떻게 Kernel-Level RCU의
(wait for pre-existing RCU readers to complete) property를 만족시킬
것인가이다. Kernel-Level RCU는 rcu_read_lock의 kernel preemption을 disable하는
특성으로 위의 property를 만족시키고 있다. 하지만 User-Level에서 kernel preemption을
막는다는 것은 ugly한 방법을 사용하지 않고는 가능하지 않다. (일시적으로 task를 제일 높은
priority의 RT task로 변환하면 가능하지만 다른 RT task를 선점하는 좋지 않은 side effect
이 발생한다.)

그리하여 User-Level RCU에서 취한 방법은 thread가 RCU critical section에 있다는
것을 표헌하기 위해 특정 메모리 영역에 변수를 setting하는 것이다.
하지만 이과 같은 approach의 문제는 memory misordering 문제에서 시작된다.
CPU 1에서 실행되고 있는 A 라는 쓰레드가 RCU critical section이 완료되었다는 것을
보장받기 위해 CPU 2에서 실행되는 B 라는 쓰레드는 synchronize_rcu를 호출할 것이다.
하지만 이때 synchronize_rcu는 memory misordering문제로 인하여 A 쓰레드가
RCU critical section에 존재한다는 것을 missing할수 있게 된다. 즉 B가 모든 RCU
critical section이 완료되었다고 판단하였지만 실제로는 쓰레드 A가 RCU critical section
에 남아 있을 수 있다는 것이다. 이는 A가 사용하는 자원이 갑자기 사라질 수 있음을 의미한다.

이 문제는 간단히 rcu_read_lock/unlock에 memory barrier를 두면 해결되는 문제이지만,
일반적으로 RCU reader들은 fast path에 속하기 때문에 간혹 수행되는 slow RCU updater들로
인해 fast path에 성능을 손해봐야 한다는 것은 기본적으로 RCU policy에 적합하지 않다.

이와 같은 문제를 해결하기 위해 Mathieu는 membarrier라는 새로운 system call을 추가하고자 한다.
이 새로운 membarrier를 통해서 기존의 rcu_read_lock/unlock은 Kernel-Level RCU와 마찬가지로
compiler level의 reordering만을 막고(CPU level의 reordering을 막는 것은 아니다), 대신
updater가 동기화를 요구할 때 새로운 system call을 호출하여 reader들의 memory barrier들을
실행하는 것이다. Update의 실행이 적은 RCU의 policy에 잘 만족하는 overhead 분산이다.

이 함수의 초기 구현은 시스템의 모든 CPU에 IPI를 날리고 그 반응으로 각 CPU에서 memory barrier
를 실행하는 것이었다. 하지만 이와 같은 방법은 user space가 모든 CPU에 강제로 interrupt를
날릴수 있는 기회를 제공함으로써 또하나의 DoS attack을 만들수 있는 기회를 제공한다는 문제가 있다.
또 다른 문제점은 실제 membarrier를 호출한 프로세스와 관계없는 CPU들까지(즉, 다른 task들을
수행하고 있는 CPU)까지 쓸데 없이 interrupt을 한다는 것이다. 다른 task가 RT task라면 문제는
더욱 심각해질 것이다. 또 다른 문제는 인터럽트된 프로세서가 sleep mode에 있었다면....
Green IT 하자고 난리인 이 판국에.

이 패치는 많은 lock expert들에 의해 in-depth review가 이루어지며 optimization작업이
진행되어 왔다. 현재 이 system call은 시스템에 모든 CPU를 살펴 caller와 같은
address space를 공유하는 녀석들이 실행되고 있는 CPU들만을 참조하여 IPI를 보내게 된다.
이 방법은 위에서 문제되었던, DoS, RT task performance, Energy Consumption 문제를
해결한다.

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될 것으로 생각된다.

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