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^