사슴농장의 추억 Jan 30, 2009

이 곡을 접한 것은 96년 이었다.
정박으로 딱 떨어지는 이 곡은 러쎌의 연주가 일품이다. (러쎌의 연주가 동영상으로 있으면 좋았으련만...)

이 곡을 떠올리면 한 선배의 사슴농장에서의 연주가 생각난다. 비가 부슬부슬 내리는 날 사슴 농장에서의
연주는 많은 사람들에게 어필할 수 밖에 없는 아름다운 연주였을 것이다. 게다가 그 선배의 연주 실력이야 이미
준 프로 수준이라고 해도 과언이 아닐 정도로 훌륭하였다.

운지가 결코 쉽지 않다. 그래서 빠른 곡은 아니어서 오른손은 여유롭지만 왼손의 기민함을 요구한다.
그 만큼 왼손의 유연함과 정확성을 기를 수 있는 곡이다.
중간 중간 나오는 슬러와 하이 플랫의 포지션은 정말 정확하게 운지를 짚지 못하면
좋은 소리를 내지 못한다.

barrios는 아직도 그 연습을 하고 있지만 뜻대로 되지 않는 운지 중 하나이다.

정말 오랜만에 맥주를 한잔했다. 항상 술이 있으면 음악이 떠오르는 것처럼...
기타가 치고 싶어진다.
이 취기에 얼마나 앉아 연주할 수 있을지는 모르겠지만(아쉽게도 새로운 악보를 일터에 놓고 왔다. 이게
있었으면 나를 boost시켜줄 수 있었을 텐데)

마음가는데로.... 연주하다 오늘 하루는 편안하게 잠들어야지
정말이지, 클래식 기타의 소리는 너무 부드럽다 :)

꼬랑지)

러쎌을 흉내냈지만 프로의 수준은 아니다. 하지만 연주자 뒤의 background가 인상적이다. ^^;
저건 madrigal 악보가 아닌데.

[RESEND][PATCH] cpuset: fix possible deadlock in async_rebuild_sched_domains Jan 21, 2009

http://lkml.org/lkml/2009/1/19/564

이 버그는 lockdep를 사용하여 발견된 버그이다.

=======================================================
[ INFO: possible circular locking dependency detected ]
2.6.29-rc1-00224-ga652504 #111
-------------------------------------------------------
bash/2968 is trying to acquire lock:
(events){--..}, at: [] flush_work+0x24/0xd8
but task is already holding lock:
(cgroup_mutex){--..}, at: [] cgroup_lock_live_group+0x12/0x29
which lock already depends on the new lock.

보는 것과 같이 circular locking deadlock 상황이 발생할 수 있음을 탐지하였다.
그럼 살펴보자. 어떻게 그런 deadlock이 발생할 수 있을지..
먼저, cgroup_mutex를 소유하고 있는 task가 있다고 말해주고 있다.
이 mutex는 cgroup_lock_live_group에서 소유하였다. 코드를 살펴보자.

cgroup_tasks_write
->cgroup_lock_live_group을 호출하여 cgrup_mutex를 소유한다.
->attach_task_by_pid
->cpuset_attach
->do_migrate_pages
->migrate_prep
->lru_add_drain_all
->schedule_work_on
->flush_work
->lock_map_acuire

반면, async_rebuild_sched_domains에서 호출한 run_workqueue를 살펴보자.

async_rebuild_sched_domains
->schedule_work (이것은 결국 eventd의 run_workqueue에 의해 실행되게 된다.)
->run_workqueue
->lock_map_acquire
->do_rebuild_sched_domains
->cgroup_lock
->cgroup_mutex 소유


위에서 보는 것과 같이 workqueue와 cgroup_mutex에 대해 circular lock이 형성된다.
이 얘기는 flush_work에 의해 완료되야 하는 worker function이 do_rebuild_sched_domains을 실행시킨 run_workqueue에 의해 lock되며 do_rebuild_sched_domains는 cgroup_mutex를 소유하기 위해 cgroup_tasks_write와 race하게 된다.

lockdep는 이와 같이 여러 deadlock 상황을 발견하기 위해 만들어진 설비이다.
하지만 false positive를 만들어내는 상황도 있기 때문에 무조건 lockdep를 믿는 것도 좋지 않다.
많은 분들이 lockdep가 어떻게 동작하는지, 어떻게 사용하는지, 보고된 내용을 어떻게 해석해야 하는지 잘 알지 못하는 것 같다.
barrios는 조만간 lockdep에 대한 내용을 한번 다룰 예정이다.

[PATCH] Avoid lost wakeups in lock_page_killable() Jan 18, 2009

http://lkml.org/lkml/2009/1/17/195

이 패치는 lock_page_killable 함수의 버그를 패치하는 함수이다.
lock_page_killable 함수는 Matthew Wilcox에 의해 추가된 함수이다.

http://lkml.org/lkml/2007/10/18/424

NFS-mounted file system의 파일에 대하여 'cat' 명령어시 중간에 명령을 멈출 수가 없었던 문제를 해결하기 위하여,
page lock에 대하여 task들을 TASK_KILLABLE 상태로 signal에 반응하며 lock을 대기할 수 있게 해준 패치이다.

하지만 이 패치는 문제를 가지고 있다.
다음과 같은 경우를 생각해보자.

1) Task A가 lock을 소유하고 있다.
2) Task B와 Task C가 lock을 대기하고 있다.
3) Task A가 lock을 unlock하고 Task B를 깨운다.
4) 이때 마침 administator는 Task B를 kill한다.
5) 깨어난 Task B는 lock을 소유하지 않고, kill된다.
6) Task C는 아무도 잡지 않고 있는 lock을 누군가가 unlock하길 기다리며, 끝까지 기다린다!!!

이 버그가 여태까지 보고되지 않았던 이유는, 누구나 참을성을 가지고 ctrl + C를 하면 hang한 프로세스들을 kill할 수 있기 때문에 대부분 application의 버그라고 생각한 것 같다.

이 문제는 oracle의 Chris Mason(현재 btrfs의 maintainer)에 의해 패치되었다. 하지만 __lock_page_killable을 패치한 Chris의 아이디어 보다는, __wait_on_bit_lock을 패치한 Johannes Weiner의 아이디어가 더욱 make sense하다. Johannes는 다음과 같이 언급하고 있다.

__wait_on_bit_lock() employs exclusive waiters, which means that every
contender has to make sure to wake up the next one in the queue after
releasing the lock.

If the passed in action() returns a non-zero value, the lock is not
taken but the next waiter is not woken up either, leading to endless
waiting on an unlocked lock.

즉,__wait_on_bit_lock이 next wake up을 보장해 주어야 한다는 것이다. 그러므로 이것은
상위 layer에서 풀 문제가 아니라 __wait_on_bit_lock에서 푸는 것이 더욱 좋다는 것이다.
또한 Peter Zijlistra는 Chris의 패치에 대해서 spurious wakeup이 우려되긴 하나,
영원히 wake up을 읽어버리는 것 보다는 좋다고 말하고 있다. spurious wakeup문제는 Johannes의 패치에서도
여전히 나타날 수 있다. 단지 가능성을 약간 줄였을 뿐이다. (test_bit operation을 중간에 추가함으로써.. barrios는 이 부분의 패치에 대해서는 별로 agree하지 않는다. 단지 가능성을 줄일 뿐이지, spurious 문제는 여전히
발생할 수 있기 때문이다. 쓸데 없이 test_bit operation을 낭비하는 것이 될 것 같다.)
아직 Johannes는 패치는 peter에 의해 ack되진 않았다.
과연 이 패치가 spurious wakeup을 피할 수 있게 될지 좀더 주목해 볼 필요가 있다.

flush_dcache_page와 kmap_atomic Jan 15, 2009

왜 file system code들 중 kmap_atomic과 flush_dcache_page가 있을까?
아는 분의 도움으로 이 문제에 대해서 생각해 볼 기회가 생겼다.

먼저, flush_dcache_page 함수의 용도를 먼저 알아야 한다.
David Miller가 작성한 문서에는 다음과 같이 되어 있다.

void flush_dcache_page(struct page *page)

Any time the kernel writes to a page cache page, _OR_
the kernel is about to read from a page cache page and
user space shared/writable mappings of this page potentially
exist, this routine is called.

NOTE: This routine need only be called for page cache pages
which can potentially ever be mapped into the address
space of a user process. So for example, VFS layer code
handling vfs symlinks in the page cache need not call
this interface at all.

The phrase "kernel writes to a page cache page" means,
specifically, that the kernel executes store instructions
that dirty data in that page at the page->virtual mapping
of that page. It is important to flush here to handle
D-cache aliasing, to make sure these kernel stores are
visible to user space mappings of that page.

즉, 커널이 page cache page에 write를 하는 경우, 또는 user space로 shared/writable로 매핑된 페이지를 읽으려고 하는 경우, 이 함수가 호출된다는 것이다. 또한 이 함수는 user-space로 매핑된 페이지 캐시의 경우에만 호출된다는 것이다. D-cache aliasing 문제를 막기 위함이다. ( cache aliasing 문제에 대해서는 James Bottomley가 작성한 다음 페이지에 잘 설명되있다. http://www.linuxjournal.com/article/7105)

D-cache aliasing 문제란, PIPT(Physical Index Physical Tag)가 아닌 VIVT(Virtual Index Virtual Tag) 또는 VIPT(Virtual Index Virtu Tag) cache 구조에서 발생하는 문제이다. cache의 서로 다른 line에 다른 virtual address로 인하여 같은 physical ram의 데이터가 들어가 있는 경우이다. D-cache aliasing이 발생하는 경우는, user application이 mmap 시스템 콜을 통하여 하나의 파일을 자신의 주소 공간 여러 virtual address에 매핑하는 경우, 또는 서로 다른 프로세스가 하나의 파일에 대해서 writable/shared 상태로 mapping을 서로 다른 virtual address를 통해서 같은 영역을 접근하는 경우 발생할 수 있다.

그럼 위의 flush_dcache_page 함수의 호출 경로 두 곳을 생각해보자.

1. page cache의 page 대하여 write operation을 호출하는 경우

이 경우는 당연히 flush_dcache_page를 호출해야 한다 왜냐하면 해당 page cache의 페이지는 다른 프로세스 또는 같은 프로세스의 다른 virtual address에 매핑되어 있을 수 있다. 그러므로 해당 page에 대한 write와 동시에 해당 page를 매핑하고 있는 모든 cache들을 flush해주어야 한다. 그렇지않은 경우 해당 page를 접근하는 다른 프로세스나 같은 프로세스의 다른 쓰레드는 stale한 데이터를 보게 될 수 있다.

2. shared/writable한 영역의 페이지를 커널이 읽을 때,

커널이 읽고 있는 페이지가 다른 프로세서에서 수행되고 있는 어플리케이션에 의해 write가 될 수 있기 때문에, 읽기 전 flush_dcache_page를 호출하여 cache를 먼저 flush 시킨 후 읽어야 한다.

Cache aliasing문제가 발생하는 것은 user application의 virtual address들로 인하여 하나의 물리 페이지가 여러 다른 virtual address space에 매핑된 경우에사 발생한다는 것을 유념하자.

자 그럼 squashfs_readpage를 이용해서 살펴보자.

다음과 같은 루틴이 있다.

452 for (i = start_index; i <= end_index && bytes > 0; i++,
453 bytes -= PAGE_CACHE_SIZE, offset += PAGE_CACHE_SIZE) {
454 struct page *push_page;
455 int avail = sparse ? 0 : min_t(int, bytes, PAGE_CACHE_SIZE);
456
457 TRACE("bytes %d, i %d, available_bytes %d\n", bytes, i, avail);
458
459 push_page = (i == page->index) ? page :
460 grab_cache_page_nowait(page->mapping, i);
461
462 if (!push_page)
463 continue;
464
465 if (PageUptodate(push_page))
466 goto skip_page;
467
468 pageaddr = kmap_atomic(push_page, KM_USER0);
469 squashfs_copy_data(pageaddr, buffer, offset, avail);
470 memset(pageaddr + avail, 0, PAGE_CACHE_SIZE - avail);
471 kunmap_atomic(pageaddr, KM_USER0);
472 flush_dcache_page(push_page);
473 SetPageUptodate(push_page);
474 skip_page:
475 unlock_page(push_page);
476 if (i != page->index)
477 page_cache_release(push_page);
478 }

이 함수의 인수로 넘어온 page에 대해서 먼저, kmap_atomic을 실행하여 operation을 한후, flush_dcache_page를 호출하는 것을 볼 수 있다. page가 인수로 넘어온 페이지는 새로 할당된 페이지 이기 때문에 굳이 flush_dcache_page를 호출할 필요는 없지만, grab_cache_page_nowait를 통해 반환된 페이지는 page cache의 페이지일수도 있기 때문에 flush_dcache_page를 호출하는 것이다. 의심의 여지가 없다. flush_dcache_page의 문서 내용대로 page cache 페이지에 write를 했으니 flush_dcache_page를 호출하는 것이다.

다음, kmap_atomic을 왜 호출 했는지 살펴보자.
그러기 위해선 kmap_atomic이 어떤 함수인지 먼저 알아야 한다. 이 함수는 커널에게 direct mapping되지 못한 메모리 공간에 커널이 접근하기 위해 필요한 함수이다. 대부분의 config설정 변경을 하지 않은 시스템에서는 커널은 1G의 메모리 주소를 갖는다. 그러므로 램의 1G 까지가 커널의 1G에 direct로 매핑될 수 있다고 생각할 수 있다. 하지만 그렇지는 않다. x86과 같은 경우 896M의 물리 램만이 direct mapping될 수 있다. 그 이유는 많은 서적들에서 얘기하고 있음으로 설명을 생략한다. 그럼 상위 1G 이상의 물리 램의 영역들은 어떻게 접근 할 것인가? 그것을 하기 위한 설비가 kmap_xxx 설비이다. atomic의 postfix가 붙은 것은 해당 매핑중 sleep되어서는 안되기 때문이다.

커널이 접근할 수 있는 1G 중, 896M를 제외한 나머지 영역은 여러 용도로 나누어져 예약이 되어 있다. 그 중 한 영역이 kmap_을 하기 위한 영역이다. 즉, 1G 이상의 메모리 영역을 일시적으로 (896M < x < 1G )주소에 매핑시켜(정확한 값은 아니다. 정확한 값은 arch마다 틀리며 지금 그거까지 찾아보기는 귀찮다. 적당히 하고 넘어가자) opeartion을 수행하고 다른 사용자를 위해 매핑을 끊어 버리는 것이다.

그렇다면 squashfs_readpage에 인수로 넘어온 page가 high memory의 page일 수 있다는 것인가?
=> 그렇다.

그렇다면 왜 high memory일 수 있을까?

=> 이것까지 생각해 봤다면 당신은 kernel newbie는 아니다.
그 이유는 page cache page들은 커널에게 있어서 있어도 그만, 없어도 그만인 페이지이다.
해당 페이지가 없다고 해서 시스템이 동작하는 데 문제가 있는 것은 아니다. 단순히 성능이 좀 떨어지겠지만.. 하지만 low memory(0~896M)의 메모리들은 커널의 동작에 있어 꼭 필요한 자료구조들과 데이터들을 관리하기 위해서 사용된다. 지금과 같이 데스크탑이 램 4G를 꼽는 경우를 생각해보면, 커널이 내부 수행을 위해 관리하는 자료구조들과 데이터들은 더욱 많은 low memory를 사용하게 된다. 그러므로 쓸데 없이 low memory를 낭비하는 것은 커널의 memory pressure를 높이는 꼴이 된다. 이는 시스템의 성능을 크게 저하시키게 된다.

이런 이유로 page cache 페이지들은 가능하면 high memory에 할당을 하려고 하는 것이다. 그러면 어떻게 그것을 알 수 있을까? 그것을 알기 위해서는 squashfs_readpage에 인수로 넘어오는 page 인수가 어떻게 어디서 할당이 되었느냐를 알아야 한다.

자, 찾아보자.

아까 얘기했었다. filemap_fault를 통해 호출이 되었을 것이라고.
아니나 다를까. 가보면 다음과 같은 code가 있다.

error = mapping->a_ops->readpage(file, page);

저 인수로 넘어가는 page는 과연 누가 할당했을까?
그 페이지는 page_cache_read 함수 안에서 page_cache_alloc_cold를 통해 할당되었음을 알 수 있다. 이때 인수로 넘어가는 address_space와 그 함수안에 mapping_gfp_mask를 보면, 결국 address_space의 flags에 어떤 값이 들어가 있느냐에 따라 페이지 할당 위치가 결정된다.

그러면 address_space의 flags에는 어떤 값이 들어가 있는지는 어떻게 아는가?
page_cache_read 함수를 보면 address_space를 구하기 위해서 file->f_mapping을 구해오는 것을 볼 수 있다. 그러므로 file의 f_mapping이 언제 어떻게 설정되느냐를 찾아 봐야 한다.

__dentry_open함수를 살펴보면, inode->i_mmaping 필드로 f->f_mapping을 지정하는 것을 볼 수 있다. 그러면 이번에는 inode->i_mapping 필드가 누가 언제 어떻게 지정하느냐를 또 찾아봐야 한다. 생각해보면 금방 알 수 있다. inode가 만들어질 때 하지 않겠는가!

그렇다면 squshfs 파일 시스템에서 inode를 어떻게 만드는지 살펴보아야 한다.
suqashfs_iget 함수를 살펴보니 알 수 있을 것 같다. iget_locked 함수를 통해서 해당 inode를 찾아보고 시스템에 없다면 get_new_inode_fast 함수를 통해 할당하는 것을 볼 수 있다. get_new_inode_fast 함수는 alloc_inode를 통해 inode를 할당하고 있다.
alloc_inode 함수는 squshfs의 경우에는 kmem_cache_alloc을 통해서 할당받게 되며 inode_init_always 함수를 통해 초기화 하는 것을 알 수 있다. 짐작할 수 있다. 저 함수안에서 초기화 할 것이라고...

mapping->flags = 0;
mapping_set_gfp_mask(mapping, GFP_HIGHUSER_MOVABLE);

위와 같이 초기화 하는 것을 알 수 있다. GFP_HIGHUSER_MOVABLE 함수는 __GFP_HIGHMEM을 포함하고 있다. 결국 해당 페이지는 high memory를 통해서 할당 받을 수 있다는 것이다.

마지막으로 간단히 GFP_HIGHUSER_MOVABLE에 대해서 설명하면, user가 사용하는 페이지들을 주로 high memory에 할당하는 memory fragementation avoidance 메커니즘이다. 즉, 시스템의 huge page 할당을 위해 연속된 큰 order의 페이지가 필요할 때, movable zone의 페이지들을 swap out시키거나 pageout 시켜, 연속된 메모리 공간을 할당하고자 하는 것이다.

Add support for IO CPU affinity Jan 14, 2009

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=c7c22e4d5c1fdebfac4dba76de7d0338c2b0d832

이번에 살펴볼 패치는 IO CPU affinity이다. x86의 server side 제품군들이 NUMA로 간지는 오래다. NUMA는 멀티 프로세서 시스템의 공유 메모리에 대한 FSB(Front-Side Bus) bottleneck을 줄이기 위한 시도였다. 하지만 NUMA로 인해 수면위로 드러났던 문제는 cache-miss 문제이다. cache-miss 문제야 이미 오래전 부터 많이 연구되었던 문제지만 NUMA에서는 cache-miss로 인한 cost가 보다 훨씬 크기 때문에 더욱 중요해 졌다. remote node로부터의 cache-to-cache transfer는 시스템의 성능 저하에 큰 요소로 작용한다. 결국, 시스템의 cache hit을 높이는 것이 갈수록 중요해지고 있는데, 이의 일환으로 이번 2.6.28에 들어간 패치 중의 하나가 IO CPU affinity이다. 이미 CPU affinity와 IRQ affinity는 이미 mainline kernel에 들어가 있는 상태이다. 이번에 추가된 IO CPU affinity는 착각하면 IRQ affinity처럼 생각할 수 있지만, IRQ와는 달리 IO를 submit한 CPU에서 IO complete routine도 처리하고자 하는 것이다. 이는 시스템의 cache hit을 높여, 성능측정 결과 20~40%의 성능 향상을 보였다고 한다. 하지만 arch에 따라 지원 여부가 결정된다는 단점이 있다. 해당 arch가 CONFIG_USE_GENERIC_SMP_HELPERS를 지원해야만 사용할 수 있다는 단점이 있다. 지원하지 않는다면 기존과 마찬가지로 여느 CPU에서나 동작하게 될 것이다.

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

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이 필요하다는 것이다.