[PATCH -v4][RFC]: mutex: implement adaptive spinning Jan 9, 2009

http://lkml.org/lkml/2009/1/8/322

현재 mainline에서는 adaptive mutex의 대한 토론이 굉장히 뜨겁다.
정확히 우리나라 시간을 기준으로 어제 오전부터 이슈가 되기 시작해서 현재 시각 기준으로, 약 100개에 가까운 reply가 달려 있으며, reply 또한 당대의 최고의 kernel expert들이다. 내용을 간단히 요약하면 다음과 같다.

먼저, 간단히 커널의 mutex 구현을 overview하자면, 다음과 같다.
Mutex의 lock path는 두 가지가 있다. fast path와 slow path.
fast path는 lock을 소유하고 있는 프로세스가 없는 경우, lock을 소유하기 위하여
최소한의 instruction만을 생성하게끔 되어있다.
반면, slow path는 fast path에 대한 시도가 실패하였을 경우, 흔히 아는 일반적인 경우처럼, lock의 wait_list에 자신을 FIFO 형태로 넣어 놓고 sleep 상태로 들어가게 된다.
물론 예외가 있긴 하다. lock에 대한 요청이 TASK_UNINTERRUPTIBLE 상태의 요청이 아니라면 signal latency를 보장하기 위해 sleep으로 들어가지 않고 signal을 먼저 처리하고
mutex는 error를 반환할 수도 있다. (이 mutex는 application이 사용하는 mutex와는 상관이 없다. 즉 pthread_mutex와 같은 library function은 error를 반환할 일이 없으니 신경쓰지 않기를. 나중에 기회가 되면 futex에 대해서도 한번 다룰 예정이다)

Adaptive mutex spinning의 아이디어는 특정 task가 소유하려는 lock을 다른 task가 이미 소유하고 있으며, lock을 소유한 task가 현재 실행중이라면(SMP환경에서), 그리고 wait_list에 아무도 그 lock을 기다리지 않고 있다면(starvation 문제가 발생할 수 있기 때문에), context_switching을 2번 이상 발생시키면서, 또 그에 따른 TLB flush와 같이 시스템의 scalability가 커지면 커질수록 비용이 큰 operation들을 처리하지 말고, 차라리 spinning을 하자는 거다.

이는 lock을 소유하고 있는 프로세스가 현재 수행 중이라면 곧 그 작업은 끝날 것이라는 가정에서 출발한다. 물론 커널의 mutex를 사용하는 code들은 이미 충분히 review되고 있어, critical section이 크지 않다는 가정을 전제로 하기도 한다.

Linus와 당대 최고의 kernel expert(Linus, Peter, Ingo, Andrew, Steven, David, Andi등)들이 현재시각 기준 2009-01-09.03시15분 98개의 쓰레드로 토론을 하고 있다.

물론 mutex는 커널에서 굉장히 빈번한 operation중의 하나이고, 성능에 심각한 영향을 초래할 수 있는 core 설비중의 하나이긴 하지만, 이렇게 simple한 idea를 가지고도 그와 관련된 side effect 및 nice implement을 고려하기 위하여 많은 guru급 kernel 개발자들이 실시간 토론을 가능하게 해주는 OpenSource development의 힘에 새삼 놀라며, Linux kernel development process에 매료될 수 밖에 없게 만드는 좋은 예가 될 것 같아 posting한다.

끝으로 이 패치가 반영되기 전 mutex의 동작구조에 대한 간단한 문서를 첨부한다.

mutex

한스밴드의 '오락실' Jan 8, 2009

오늘은 불현듯 이 친구들이 생각난다.

IMF 시절에 다양한 악기에 대한 뛰어난 연주실력과 돈벌이에 급급하지 않으며,
자극적이지 않은 가사, 이 시대의 아픔을 노래했던 '오락실'이라는 곡의 한스밴드.

그리 화려하지 않은 외모지만, 교복을 입고 나와 꽤나 풋풋함을 강조했었던 신선한 밴드였으며,
외국의 다른 밴드처럼 실제 자매들로 이루어진 밴드였다. 4번째 막내도 뒤늦게 조인했었던 것으로 기억한다. 하지만 소속사와의 노예계약으로 결국 소송에 휘말리게 되고, 지금은 CCM만을 하는 것으로 알고 있다. 그녀들의 아버지 또한 목사님이었던 것으로 기억한다.

안타깝지만, 실력있는 어린 친구들은 그렇게 대중에게 잊혀지고 있다.
하지만, 요즘 다시 세상이 각박해지며, IMF 때보다 더 심하다는 기사 내용들이
다시 한스밴드의 이 노래가 생각나게 한다.

Increase dirty_ratio and dirty_background_ratio?

http://lkml.org/lkml/2009/1/7/278

금일 Jan Kara라는 suse개발자에 의해 kernel의 default dirty_ratio와 dirty_background_ratio를 바꾸고자 하는 질문이 들어왔다. 요는 기존의 40,10으로 각각 설정되어 있던 값을 10,5로 2007 4월에 Linus에 의해 바뀌어 테스트를 해보니 performance regression이 발생했다는 것이다. 테스트는 Berkeley DB를 사용한 workload였다. 이러한 workload들은 write io를 많이 발생시키기 때문에 io bottleneck이 생기며 pdflush가 굉장히 aggressive하게 동작하기 시작한다. 그래서 질문은 과연 그때 어떤 target을 위해 값을 그렇게 변경했냐는 것이다. 또한 이렇게 값을 다시 올리는 것이 negative impact이 없다면 SLES11 kernel의 default 값을 바꾸려고 한다는 것이다.

이에 대해 Peter, Linus, Andrew 정말 재야의 고수들이 다 답을 달아 주었다.
Peter의 답이 부족하여 Linus가 명확한 답을 달아 주었으며,
마지막으로 David Miller의 revert에 찬성하는 조의 발언에 Andrew가 인상적인 말을 남겼다.

"커널은 그런 일을 바르게 처리할 수 없다. 커널은 patters/workloads들의 사용을 알지 못한다.
배포판들이 이것 뿐만 아니라 다른 knob들도 알맞은 값으로 셋팅하기 위한 노력이 거의 없는 것 같아 실망스럽다."

Andrew는 initscripts들을 가지고도 시스템의 memory size, disk speed, workload등을 가지고 충분히 처리할 수 있다는 것이다.

맞는 말이기도 하고.. 한편으론 다른 부분들은 그러한 노력들이 있으니... Linus의 답변 중에도 다음과 같은 말이 있다.

(b) scale it dynamically by your IO performance. No, current -git does
_not_ support this.

뿐만 아니라, 커널의 readahead와 page reclaiming의 stream data를 먼저 회수하기 위한 노력들 또한 같은 선상에 있다. 문제는 그러한 노력들이 workload에 따라 약이 될 수도 있고 독이 될 수도 있다는 점이다. 그래서 mainline에 merge되기 또한 매우 어렵다는 것이다.

임베디드 업계에서 커널을 하는 사람들에게서 흔한 일이다. 특정 기능을 바로 커널에 넣어버리려는.. barrios는 그렇게 특정환경에 specific한 feature들을 별로 좋아하지 않는다. 유지보수 면에 있어서 어려움이 발생하고, code quality면에 있어서도 많은 부분을 놓치고 지나갈 수 있기 때문이며 무엇보다 side effect을 고려하지 못하는 짧은 생각에서 기인하는 경우가 흔하기 때문이다.

커널이 항상 능사는 아니다.

RCU에 대한 이해 Jan 6, 2009

RCU를 다룬 문서들이 많이 있다. Paul은 이미 많은 paper들을 작성해 왔으며, 많은 잡지의 기사들이 RCU에 대해 다뤄왔다. 그럼에도 불구하고 많은 사람들이 RCU를 정확히 이해하지 못하고 있다. 그것은 지금까지 우리가 자료구조 자체와 자료구조에 의해 관리되고 있는 데이터의 대한 동기화를 함께 생각하는 습관을 가지고 있기 때문이다.즉, 데이터를 보호하지 않고 항상 Code를 보호하는 습관을 들여왔기 때문이다.

RCU를 통해 보호되는 자료구조들은 자료 구조 자체에 있어서 well-define되어 있지만, 자료 구조에 의해 관리되는 데이터 중, stale한 데이터는 알고리즘에 의해 cover되어야 한다. RCU는 단연, stale한 데이터를 생성한다. 하지만 여러 알고리즘들은 이러한 데이터를 극복하고 있다.

아래 첨부는 그나마 RCU를 가장 쉽게 잘 설명한 LWN의 글을 의역한 것이다.
이 기사 또한 stale data에 대한 처리는 언급하지 않고 있다.
그러므로 읽는 사람들은 계속해서 혼동스러울 수 있다.

barrios는 앞으로 stale데이터에 대한 처리를 실제 kernel에서 구현된 예를 가지고 설명하려고 한다.
이 역시 시간이 있다면.. 하지만 이에 대한 이해 없이는 RCU를 절대 소화해 낼 수 없을 것이다.

RCU에 대한 이해

[patch] mm: fix lockless pagecache reordering bug (was Re: BUG: soft lockup - is this XFS problem?

http://lkml.org/lkml/2009/1/5/282

오늘 report된 버그이다. 이 문제는 Linus가 쓰레드에 참여할 만큼 쉽지 않은 문제이며, 심각한 문제이기도 하다.
Nick이 오랫동안 작업해서 mainline에 merge시킨 lockess pagecache의 버그가 발생하였다. 하지만 문제를 더 깊게 파고 내려가면 lockess pagecache의 bug라기 보다는 근본적인 원인은 lockless radix tree의 버그일 수도 있다.

현재 Linux와 Nick의 주장은 합의점을 찾지 못하고 있으며, 좀더 추이를 지켜봐야 할 듯 하다. 쓰레드에 Paul과 Peter까지 참여하였다. 당대 최고의 커널 expert들이 토론을 하고 있으니, 이 문제의 난위도가 어떨지는 쉽게 생각해 볼 수 있을 것이다. 문제는 굉장히 간단하다.

find_get_pages의 page_cache_get_speculative가 실패한 이후, 다시 radix_tree_deref_slot을 하는 과정에서 page의 _count값을 읽어오기 위해 memory로부터 값을 읽어오는 것이 아니라, 이미 register에 저장되어 있는 값을 계속 사용하기 때문에, page가 radix tree에서 제거되고 _count가 0이 되었음에도, page_cache_get_speculative가 보는 page의 _count는 0이 아니어서 또 실패하고, 다시 radix_tree_defef_slot을 실행하고.. . 해당 cache가 invalid될 때까지는 lockup이 되는 것이다. 아래는 find_get_pages의 컴파일 결과이다.

역어셈 코드 참조

.L220:
movq (%rbx), %rax #* ivtmp.1162, tmp82
movq (%rax), %rdi #, prephitmp.1149
.L218:
testb $1, %dil #, prephitmp.1149
jne .L217 #,
testq %rdi, %rdi # prephitmp.1149
je .L203 #,
cmpq $-1, %rdi #, prephitmp.1149
je .L217 #,
movl 8(%rdi), %esi # ._count.counter, c
testl %esi, %esi # c
je .L218 #,

그래서 Nick은 간단히, repeat의 다음 라인에 barrier를 추가하여 해결하려고 했으나, Linus는 Nick의 그런 제안에 문제점을 지적하였다. Linus의 주장은 그 문제는 lockess pagecache의 버그라기 보다는 RCU를 사용하여 lockless radix tree를 사용할 때 이미 근본적인 문제점을 가지고 있는 것이 아니냐는 것이다. Linus는 RCU를 사용하여 데이터를 보호할 때 RCU 사용하에서 변경될 수 있는 데이터의 필드들은 rcu_dereference를 사용하여 fetch해야 한다는 것이다. 하지만 이 의견에 대해 Nick과의 의견이 상충하고 있고, Paul은 이 문제에 대해 명확한 답을 주지 못하고, 지금부터 주의깊게 살펴볼 듯 하다.

결국 위의 코드는 패치로 인하여 다음과 같이 바뀌었다.
코드를 보면 rdi의 값을 rbx와 rax 레지스터를 이용하여 memory에서 직접 읽어오는 것을 볼 수 있다.

.L212:
movq (%rbx), %rax #* ivtmp.1109, tmp81
movq (%rax), %rdi #, ret
testb $1, %dil #, ret
jne .L211 #,
testq %rdi, %rdi # ret
je .L197 #,
cmpq $-1, %rdi #, ret
je .L211 #,
movl 8(%rdi), %esi # ._count.counter, c
testl %esi, %esi # c
je .L212 #,

mm:rewrite vmap layer Jan 4, 2009

2.6.28에서 Memory Scalability를 위해 추가된 split lru말고도 우리가 주목해야 할 patch는 vmap이다. Nick이 제안한 이 패치가 mm tree에서 드디어 mainline으로 merge되었다.

Nick이 주목한 문제는 vmalloc의 scalability이다. 정확하게는 vmap의 scalability이다. 더 정확하게는 vunmap의 scalability이다. vmalloc으로 할당한 주소를 해지하는 이 함수는 당연히 IPI를 통한 TLB flush를 해야만 하기 때문이다. 이는 processor가 많아지면 많아질 수록 overhead가 커질 수 밖에 없다. 그리고 vmalloc의 address space를 관리하는 자료구조가 linked list이고 global lock 하나였다는 것이다. Scalability에 치명적일 수 밖이 없는 구조였다.

세상에 multicore가 일반화되며 부각된 문제이다. 그러므로 Nick은 먼저 linked list를 없애기 위하여 red-block tree로 대치하였다. 다음 global lock을 없애기 위하여 작은 주소 공간을 각 per_cpu로 cache하여 관리하게끔 바꾸었다. per_cpu list는 32bit에서는 32개, 64bit에서는 64개까지 page를 cache할 수 있다.

마지막으로 lazy tlb flush를 제안하였다. 해지된 vmalloc의 address space는 시스템으로 회수되기 때문에 다시 할당되기 전까지는 사용될 수 없다. 결국, 어떤 code들도 이미 해지된 그 주소를 다시 사용할 수 없다(Bug가 아니고서야 :)). 하지만 우리가 보장해줘야 할 것은 다시 그 주소 영역이 할당되는 경우이다. 이때는 반드시 TLB consistency를 보장해줘야만 한다. 그러므로 Nick은 해지된 영역들을 충분히 쌓아두었다가 한번에 flush 하자는 것이다. 아이디어가 간단하고 이미 시스템 프로그래밍의 여러 부분에서 사용되고 있는 방법인 반면에, Linux core를 속속들이 이해하지 못하는 경우 생각할 수 없는 좋은 아이디어라고 생각한다. 좀 인위적인 테스트이긴 하지만 대략 기존보다 25배나 빨라진 것을 알 수 있다.

아직 많이 미진하지만 분석 문서를 첨부한다.
이 문서는 앞으로 보다 세심히 업데이트 할 것이다.

vmalloc 문서

mm:rewrite vmap layer

[PATCH 0/2] pdflush fix and enhancement Jan 2, 2009

http://lkml.org/lkml/2008/12/30/245

Novell의 Peter W Morreale 는 현재 min, max가 2와 8로 고정되어 있는 pdflush의 갯수를 admin이 fine tuning할 수 있게끔 패치를 올렸다. 또한 SMP 시스템에서 동기화 문제로 인하여 pdflush 쓰레드의 갯수가 시스템이 정해놓은 boundary를 넘어가는 경우도 패치하였다. (이것이 point는 아니다.)

패치 자체는 굉장히 간단하다. 반면, 많은 것을 생각하고 고려했던 패치이다. Andi의 "그러한 knob들을 늘려가는 것은 결국 커널이 self-tuning을 포기하는 것이기 때문에 rationale이 명확해야 한다"는 comment에서 시작하여 굉장히 길게 토론되었다.

이 쓰레드의 포인트는 현재 pdflush 생성과 소멸의 시점에 문제이다. 현재 구현은 단순히 얼마나 pdflush 쓰레드들이 바쁘냐, 한가하냐만을 가지고 pdflush 스스로 자신의 갯수를 늘리거나 줄인다. 하지만 정말 중요한 문제는 pdflush의 쓰레드의 boudary magic value들, 즉 2와 8 또는 one pass 에 writeout 할 dirty page들의 갯수인 MAX_WRITEBACK_PAGES(1K) 값들이 문제이다. 이런 static magic value가 모든 경우를 cover할 수 없는 것이다. 컴퓨터 시스템은 다양한 block device들을 가지고 있다. RAID, IDE disk, SSD 등 .. 또한 다양한 device들은 서로 다른 bandwidth를 가지고 있다. 그러므로 500MB/s이 나오는 SSD의 block device에 더 많은 쓰레드를 할당하는 것이 IDE에 하는 것보다 좋지 않겠냐??. 또는 일반적으로 하나의 disk를 가지고 하나의 filesystem을 갖는 small system에서 8개의 쓰레드를 경쟁시키는 것이 과연 좋겠냐는 것이다. 반대로 많은 block device와 file system을 갖는 large server 환경에서 pdflush 쓰레드를 8개로 제한을 하는 것이 효율적일까?? pdflush는 block device들의 특성을 전혀 반영하지 못하고 있다.

또 다른 문제는 pdflush의 worker function인 background_writeout에서 발생한다. 이 함수는 filesystem을 traverse하며 super block들을 역순으로 writeout하기 시작한다. 즉 file system들의 dirty page들의 불균형이 올 수 있다는 것이다. 가장 마지막의 filesystem의 dirty page들이 우선적으로 고려되기 때문이다.

그러므로 이번에 올린 패치와는 무관하게 pdflush의 근본적인 redesign이 필요하다는 것이다.