Justifying FS-Cache Jan 11, 2009

http://lwn.net/Articles/312708/

David Howells은 오랫동안 이 작업을 진행해왔다. FS-Cache의 목적은 원격의 remote disk로의 읽기가 매우 느리니, 자신의 local disk에 데이터를 캐시하기 위한 generic cache mechanism을 두겠다는 것이다. 그러므로 네트워크 파일 시스템이 주요 고객층이 될 것이다. 네트워크 파일 시스템은 원격지의 데이터와 로컬 데이터의 consistency 문제 때문에 리눅스 커널의 generic page cache mechanism으로 page를 캐시하기 어려워왔다.

이 패치들은 기존의 VFS layer에 대한 많은 수정을 요하는 조금은 파격적인 패치들이라고 말하고 있다. Andrew는 이와 같이 파격적인 패치를 요하는 user들의 목소리나, 어떤 benmark자료들에 대해 요구했고, David는 그에 대한 benchmark 자료와 이미 redhat에서는 이 패치를 적용하고 있고, entertainment industry의 사용자의 목소리 또한 전해주었다. 이것으로 Andrew의 concern은 어느정도 해결이 된 것 같다.

하지만 앞으로 또 어떤 concern들이 나오게 될지는 더 두고 봐야 할 것이다.

Btrfs and Squashfs merged for 2.6.29

http://lwn.net/Articles/314325/

2.6.29에 btrfs가 merge될 것으로 보인다.
btrfs는 지난 번 Jonathan Corbet의 세미나에서와 마찬가지로(Jonathan 뿐만 아니라 mainline에서는 이미 공공연한 사실이다), 앞으로 ext 파일 시스템을 대치하는 Linux의 future default file system이 될 수 도 있을 정도로 issue가 되는 file system이다. 기본 concept부터가 기존의 filesystem과는 많이 다르다고 알고 있다. 애석하게도 아직 barrios는 btrfs의 코드를 제대로 분석해보지 못했다. 앞으로 굉장히 linux vm에 많은 패치들을 불러올 수 있는 파일 시스템이어서 조만간 이 파일 시스템에 대해 한번 다뤄야 겠다. 참고로 이 파일시스템은 oracle에 의개 개발되어 open된 파일 시스템이며, maintainer는 Chris Mason이다.

다음으로, Squashfs 또한 드디어 2.6.29에 merge될 예정이다. 참 긴 여정이었다.
이미 많은 배포판들에 의해 탑재되어 그 성능과 안정성을 입증받은 Squashfs가 coding style과 약간 기형적인 자신만의 캐시 정책들을 수정하여 마지막으로 mainline 입봉에 성공하였다. Linus 마저 OK 했음으로, Andrew는 더 이상 반론의 여지가 별로 없어 보였다. :)
앞으로 임베디드 개발자들이 조금 더 편해질 것으로 보인다.

Squashfs에 대한 몇몇 개발자들의 말이 재미있다.

Andrew Morton put it: "We've long needed a filesystem named after a vegetable."

Harvey Harrison said: "I always preferred my squash with butter, it appears 2.6.30 will be a very tasty kernel."

Alan Cox adds:
And vegetables are much [healthier] than FAT ...

[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 #,