[patch] vmscan: initialize sc.order in indirect shrink_list() users Feb 17, 2009

http://lkml.org/lkml/2009/2/10/231

Hannes의 패치이다.
얼마전 Hannes는 offline mail을 통해서 barrios에게 유익한 정보를 알려주었다.
이는 다음 기회에 소개하기로 하고, 지금은 이 패치의 내용에 대해 살펴보자.

Hannes가 패치한 내용은 memory 회수 루틴 중 2곳에서 현재 메모리 requestor의 order가 반영되지 않았다는 것이다. 첫번째 장손는, 명시적으로 0을 지정할 필요가 없다는 것을 얼마전 Andrew가 친절히 설명해 주었었다.
이번 issue는 두번째인 zone_reclaim 함수에서의 order값 지정의 생략이다.

zone_reclaim 함수의 목적은 page를 할당하기 전, early reclaim을 하는 것이다. early reclaim의 대상은
slab 페이지들과 unmapped file backed page들이다. 즉, read와 같은 system call을 통해서 읽혀진 페이지나, mapped file backed page들 중에, 현재는 unmapped되어 있는 페이지들이다.

이 함수에서 order를 requestor의 order로 지정하지 않은 것이 문제의 시작이다.
하지만 이 쓰레드의 Hannes와 Mel의 대화 속에는 약간의 오해가 있다.

먼저, Hannes가 order를 의도적으로 0으로 지정하지 않았다고 생각하는 이유는 다음과 같다.

Page allocator는 page를 할당하려고 할 때 몇 단계를 거치며 할당자에 pressure를 가한다.
그 pressure는 다음의 flag들로 지정된다.

#define ALLOC_NO_WATERMARKS 0x01 /* don't check watermarks at all */
#define ALLOC_WMARK_MIN 0x02 /* use pages_min watermark */
#define ALLOC_WMARK_LOW 0x04 /* use pages_low watermark */
#define ALLOC_WMARK_HIGH 0x08 /* use pages_high watermark */
#define ALLOC_HARDER 0x10 /* try to alloc harder */

NO_WATERMARK 쪽으로 갈 수록 memory pressure가 심한 것이다.
Page allocator의 첫번째 try는 ALLOC_WMARK_LOW를 사용하게 된다. Hannes가 생각한 것은
WMARK_LOW에서 order를 지정하게 되면, 현재 memory pressure가 별로 없는 상태에서 결국 lumpy reclaim을
하게 되어, 불필요하게 working set page들이 evict되어 버린다는 것이다. 그래서 의도적으로 order를 지정하지 않았다고 생각한다.

이에 대해, Mel은 분명히 잘못된 것이라고 지적하고 있다. 즉 Hannes의 패치가 맞다는 것이다.
그것으로 인해 어떤 차이가 생길지는 알기 어렵지만, zone_reclaim의 semantics상 order를 지정하는 것이 make sense하다는 것이다. 또한 Mel은 Hannes가 걱정한 working set page의 evict에 대해서 high order reclaim에 대한 어쩔수 없는 cost라고 말하고 있다.

마지막 쓰레드의 Hannes와 Mel의 대화를 다시 보면, Mel은 Hannes의 말을 여전히 오해하고 있다. Hannes가 의도한 것은 low watermark에서 굳이 lumpy reclaim까지는 하지 않아도 upcoming allocation은 성공할 것이기 때문에 그렇게 했을 거라는 말이고, Mel은 그 말을 오해하고, 이렇게 언급하며 쓰레드를 끝낸다.

I think I get you now. You are saying that reclaiming order-0 pages increases
the free count so we might get over the watermarks and the allocation would
succeed. Thing is, watermarks calculated in zone_watermark_ok() take order
as a parameter and has this in it.

for (o = 0; o < order; o++) {
/* At the next order, this order's pages become * unavailable */
free_pages -= z->free_area[o].nr_free << o;
So, to reach the low watermarks for a high-order allocation, we still
need lumpy reclaim.

즉, Mel은 "order-0 page를 reclaim하는 것이 전체 free page의 수를 증가시킬 것이며 이는 watermark 이상이 될수 있기 때문에 allocation이 성공할 것이다" 라고 Hannes가 말하고 있다고 생각한다. 하지만 앞서 언급한 바와 같이 Hannes의 의도는 그렇지는 않다. Anyway, Mel로부터 배울 것이 있다. order-0 page를 아무리 reclaim하더라도 결국 zone_watermark_ok는 위와 같이 계산하기 때문에 requestor의 order를 만족시킬 수는 없게 된다는 것이다. 결국 allocation이 성공할 수 없다는 것이다.

Taming the OOM killer Feb 14, 2009

http://lwn.net/Articles/317814/

OOM killer도 역시 embedded에서 hot issue 중의 하나이다.
현재 Linux system의 OOM killer의 가장 큰 문제는 유연성의 부재이다.

Linux kernel은 Out of Memory 상황이 오면 몇가지 heuristic을 사용하여 비교적 시스템에 해가 적게가며, 많은 메모리를 반환할 수 있는 프로세스를 kill하게 된다. 하지만 그 결정은 kernel의 생각이지, 시스템을 운영하는 admin이나 사용하는 user의 의견이 반영된 결정은 아니다.

그렇게 까지 얘기하면 너무 심한가?
사실, User들도 커널의 결정을 거들수는 있다. 그것이 /proc/pid/oom_adj란 knob이다.
이 값은 커널의 여러 heuristic과 같이 각 프로세스의 oom_score의 값을 결정하는 데 기여한다. 커널은 결국 가장 큰 oom_score를 가진 프로세를 kill하게 되므로 사용자의 의견이 어느 정도 반영이 될 수는 있다.

이러한 설비들이 있긴 하지만, 시스템을 admin하는 입장에서 그러한 설비만으로 OOM policy를 구현하기가 그리 만만치가 않다. 생각을 해보아라. 그러한 설비만으로 시스템에 생성되는 모든 프로세스들의 oom_adj를 runtime에 조절하는 것이 과연 얼마나 수월할까? 여러 사람들의 서버로 사용되는 server computer를 생각해보자. 그 안에서 어떤 user가, 어떤 time에, 어떤 job을 어떤 order로 얼마나 많은 memory를 필요로 하며 실행될지...

그러므로 효율적인 OOM policy를 구현하기 위해서는 그 이상의 유연한 설비가 보다 OOM policy를 결정하는데 도움을 줄 것이다.

얼마전 LKML에서는 Alan Cox의 제안에 의해 Nikanth Karthikesan가 cgroup controller를 base로 oom_killer controller를 구현하였었다. cgroup을 사용하였기 때문에 기존보다는 OOM priority별 task들을 grouping하기가 수월해졌다. 하지만 이 approach는 CPU set을 고려하지 않았다.
CPU set A, B가 있다고 가정하자. CPU set A의 한 프로세스가 더 높은 oom.priority를 가지고 있을 경우, CPU set B가 OOM 상황을 만나게 되더라도 결국, CPU set A의 그 프로세스가 죽게 되는 것이다. 여러 토의 끝에, 결국 OOM 상황을 user space에 다루자는 얘기가 나왔다. 커널은 user space로 notify만 해주고 application들이 각자 자신의 cache를 drop한다거나 해서 OOM 상황에 대처하자는 것이다. Application들의 action이 충분한 free memory를 확보하는데 실패하였을 경우에만 커널이 마지막으로 기존의 OOM killer policy를 사용한다는 것이다.

2008년 초 Kosaki-san이 구현했던 mem_notify가 그러한 policy를 구현하기 위한 첫 발걸음이었다. 하지만 이 패치는 현재 mainline에 반영되지 못했다. 그 이유는 여러 이유가 있지만 그 중에서도 가장 큰 것은 2.6.28에서 memory reclaiming이 크게 변경되었기 때문이다. 그 패치의 notify 시점은 커널의 memory reclaim 루틴과 굉장히 밀접하게 관련되어 있었기 때문에 memory reclaiming이 많이 변하게 되면서 mem_notify가 동작할 수 없는 환경이 되버린 것이다. Memory reclaiming을 같이 작업한 Rik과 Kosaki 그리고 약간의 도움을 준 barrios는 이 상황에 대해서 잘 알고 있으며, barrios는 mem_notify 패치의 마지막 메일 또한 기억하고 있다.

마지막 토론에서의 문제는 실제 mem_notify가 필요할 때 notify를 해주지 못한다는 것이다. 즉, user가 notify를 받은 시점은 user가 어떤 action을 취하기에 늦어버렸다는 것이다. 그것은 현재 linux kernel의 문제이기도 하며, android가 별도의 low memory killer를 구현한 이유이기도 하다. 하지만 지금도 mem_notify의 design과 goal들은 여전히 유효하다.

한동안 Android의 Low memory killer가 staging tree에 들어간 것에 대해서 여로 토의가 있었다(http://lkml.org/lkml/2009/1/13/558). barrios 또한 staging tree에 반영되었던 low memory killer의 소스를 보았지만 사실 너무 specific하게 구현되어 있어 질타를 받기 딱 좋은 코드였다. OOM issue는 embedded뿐만이 아닌 server에서도 필요한 이슈이다. 하지만 android 팀의 코드는 embedded 중에서도 자신들의 android 플랫폼만을 위한 specific한 코드를 구현하였고, Greg은 그것을 stating tree에 반영한 것이다. Staging tree의 특성상 앞으로 더욱 발전시키면 되지, staging tree에 들어가질 못할 정도는 아니었음에도 불구하고, barrios의 생각으론 다국적을 가진 사람들이 토의하다보니 영어를 약간 잘못 해석하여 분쟁이 일어나 결국 code를 다시 revert하라는 말까지 나올 정도로 좀 소란스러웠었던 issue이다.

커널 트리에는 low_memory killer만 있고, 그 신호를 어떻게 user에서 처리하는지 잘 몰랐는데 LWN에 쉽게 잘 설명이 되어 있다. 첫번째 threshold에서는 background process들이 자신들의 state를 save하고, 점점 memory pressure가 심해지면 backgroud process 중 state를 save한 critical하지 않은 프로세스들을 kill하고, 마지막으론 foreground process들마저도 kill한다는 것이다. Android 팀이 이러한 설비가 필요했던 것 또한, 현재 linux kernel의 OOM killer의 반응은 너무 늦으며(Android팀은 보다 이른 신호가 필요하였다. 그래서 사전에 application에서 할 수 있는 일을 하려고 했던 것이다) 또한 그리 똑똑하지 못하다는 것을 반증하고 있다.

지금이다. Linux kernel의 OOM killer구조가 재설계되야 할 때는!!

lru_add_drain_all problem Feb 8, 2009

http://lkml.org/lkml/2008/10/21/205
http://lkml.org/lkml/2008/11/5/347

또 다시 circulary dependency problem이다.
문제의 원인은 lru_add_drain_all이 mmap_sem을 hold한 채로 worqueue를 사용하기 때문이다. 이 문제는 작년 10월 처음으로 보고 되었고, 쓰레드를 읽어 보면 알수 있는 바와 같이,
문제를 해결하려는 시도는 2가지의 방향으로 시도 되었다.

첫번째는 keventd가 아닌 별도의 workqueue를 만들어 schedule_on_each_cpu를 keventd가 아닌 별도의 workqueue안에서 호출하자는 것이다.

이렇게 한 이유는, 이미 많은 드라이버들이 keventd를 이용한 workqueue를 사용하고 있는 상황에서 그 driver들이 어떤 lock을 hold한채로 workqueue 사용하고 있는지를 알 수 없기 때문에, 비교적 적게 사용되는 schedule_on_each_cpu로 하여금 별도의 workqueue를 사용하자는 주장이다.

하지만 이 방법에 대해서는 Peter가 별로 달가워하지 않았다.

그 이유는 이미 커널에는 수많은 커널 쓰레드들이 있다는 것이다. 그 상황을 더욱 악화시키지 말자는 것이다. barrios의 생각도 마찬가지이다. 비록 지금은 schedule_on_each_cpu를 호출하는 것이 pagevec을 drain하는 lru_add_drain_all 함수 하나이지만, 그러한 함수들은 얼마든지 더 생길 수 있고 그럴때마다 새로운 workqueue를 만드는 것은 시스템의 커널 쓰레드들의 수를 증가시키게 된다.

하지만 이 상황은 지금은 더 나아질 수도 있을 것 같다. 왜냐하면 이전에 소개했던 기사 처럼 Arjan의 An asynchronous function call infrastructure가 mainline에 merge될 것이기 때문이다. 이 설비를 이용하게 되면 worker function을 새로운 쓰레드에서 실행하게 할 수 있으며, 해당 쓰레드는 필요 없을 때 종료될 수 있기 때문이다. 하지만 생성된 쓰레드를 재활용하는 Arjan의 패치에 약간의 개선이 필요하다. 모든 함수가 새로운 쓰레드에서 호출되며, 그 쓰레드는 다른 함수를 호출하지 않고 종료되게 끔 되어야 ciculary locking problem이 발생하지 않기 때문이다.
이와 함께 이 패치 또한 고려되어야 한다. 이는 비동기 함수 호출이 아닌 커널 쓰레드 자체에 관하여 비동기적으로 생성하자는 패치이다. 하지만 Arjan의 패치와 역할이 많이 겹치고 있다. http://lkml.org/lkml/2009/1/27/410)

두번째는 lru_add_drain_all을 호출하는 path에서 mmap_sem를 hold하지 않은 채로 호출하자는 것이다. Christoph는 migration중 mmap_sem을 hold하는 문제의 패치를 만들어 제출하였고, Kosaki 또한 munlockpath에서 lru_add_drain_all을 호출하지 않아도 시스템의 mlocked page memory leak이 발생하지 않는다는 문제에 agree하였고, 결국 다시 패치를 만들어 제출하였다.

barrios가 이 문제를 언급하는 이유는 작년 11월에 반영된 kosaki의 패치가 아직 반영되지 않았기 때문이다. 그러므로 barrios는 28-rc2-mm1의 테스트 중 그러한 circulary dependency locking report를 받았기 때문이다.

이 문제에 대해서 차주 kosaki와 얘기를 좀 더 해볼 필요가 있으며, 필요하다면 Arjan의 패치에 새로운 기능을 넣어 해결 할 수도 있을 것 같다.

An asynchronous function call infrastructure Feb 1, 2009

http://lwn.net/Articles/314808/

2.6.29-rc3가 몇일전 release되었지만 이제서야 2.6.29-rc1에 들어간 기능을 review한다.
그 동안 some bug를 digging 하느라 정신이 없었다. 사실 아직도 debugging 중이다.

kernel compile을 하는 동안 LWN 기사를 하나 review한다.

Intel의 Arjan이 시도하는 fastboot project의 일부이다.
Fastboot은 많은 사람들이 관심을 가지고 있는 주제중의 하나이며, 그 동안 많은 시도들이 있었다.
특히 embedded guy들이 많은 관심을 가지고 있던 주제중의 하나이다.
하지만 Arjan은 embedded가 아닌 desktop을 위해 Fastboot을 진행중이다. 물론 몇몇 기술들은
embedded에도 유용할 것이다. 하지만 오늘 소개하는 이 patch는 embedded와는 별로 관계가 없다.

사실, device probing을 parallel하게 하자는 시도는 예전부터 있어왔었다. 하지만 device ordering,
concurrent access등과 같은 문제들로 인하여 system stability의 문제가 있어 general하게
적용되지 못해왔다.

이 문제를 Arjan은 모든 device들을 한번에 해결하려는 시도보다는 libata subsystem과 SCSI로 국한하여
parallel probing을 시도하였으며(그래서 barrios는 embedded와는 현재로선 거리가 멀다고 얘기한 것이다. 하지만 이 비동기 framework 자체는 fastboot뿐만이 아니라 여러면에서 도움이 될 것으로 생각된다.), API를 잘 추상화하여 나머지 subsystem들은 아무 영향을 받지 않도록 설계하였다.

실제 동작 원리는 복잡하지 않다. 비동기 함수를 관리하는 async_pending list와 async_running list를 두어,
비동기 함수의 실행을 요청하는 async_schedule을 호춢하게 되면 callback function을 async_pending list에 넣고, 그 함수를 실행시키기 위해 async_manager_thread를 깨우게 된다. async_manager_thread는 새로운 async_thread를 생성하여 pending list에 있는 비동기 함수를 실행하게 된다. async_thread는 1초 async_pending list에 pending된 비동기 함수들이 없을 경우 스스로 소멸되게 된다.
또한, 한꺼번에 많은 비동기 함수들의 요청이 들어올 경우, kernel thread는 갑자기 많아 질 수 있다.
현재는 kernel thread를 MAX_THREAD(256)개로 제한하고 있다.

static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct list_head *running)
{
struct async_entry *entry;
unsigned long flags;
async_cookie_t newcookie;


/* allow irq-off callers */
entry = kzalloc(sizeof(struct async_entry), GFP_ATOMIC);

/*
* If we're out of memory or if there's too much work
* pending already, we execute synchronously.
*/
if (!async_enabled || !entry || atomic_read(&entry_count) > MAX_WORK) {
kfree(entry);
spin_lock_irqsave(&async_lock, flags);
newcookie = next_cookie++;
spin_unlock_irqrestore(&async_lock, flags);

/* low on memory.. run synchronously */
ptr(data, newcookie);
return newcookie;
}
entry->func = ptr;
entry->data = data;
entry->running = running;

spin_lock_irqsave(&async_lock, flags);
newcookie = entry->cookie = next_cookie++;
list_add_tail(&entry->list, &async_pending);
atomic_inc(&entry_count);
spin_unlock_irqrestore(&async_lock, flags);
wake_up(&async_new);
return newcookie;
}

하지만 아직까지 이 patch는 많은 문제를 가지고 있는 것 같다. 2.6.29-rc1에 들어가자마자 많은 문제들이 보고되기 시작했으며, 현재 Arjan은 Linus에게 이 기능을 disable 시켜달라고 요청한 상태이다.

이번주 LWN의 기사가 다시한번 이 주제를 다루고 있기 때문에, 몇일 뒤 무료로 기사를 볼 수 있게 될 경우, 이 문제가 어떻게 풀려나가고 있는지 다시한번 review를 하도록 하자.