Ramdisk vs Ramfs May 30, 2008

http://www.linuxdevices.com/articles/AT4017834659.html

A ramdisk (like initrd) is a ram based block device, which means it's a fixed size chunk of memory that can be formatted and mounted like a disk. This means the contents of the ramdisk have to be formatted and prepared with special tools (such as mke2fs and losetup), and like all block devices it requires a filesystem driver to interpret the data at runtime. This also imposes an artificial size limit that either wastes space (if the ramdisk isn't full, the extra memory it takes up still can't be used for anything else) or limits capacity (if the ramdisk fills up but other memory is still free, you can't expand it without reformatting it).

But ramdisks actually waste even more memory due to caching. Linux is designed to cache all files and directory entries read from or written to block devices, so Linux copies data to and from the ramdisk into the "page cache" (for file data), and the "dentry cache" (for directory entries). The downside of the ramdisk pretending to be a block device is it gets treated like a block device.

A few years ago, Linus Torvalds had a neat idea: what if Linux's cache could be mounted like a filesystem? Just keep the files in cache and never get rid of them until they're deleted or the system reboots? Linus wrote a tiny wrapper around the cache called "ramfs", and other kernel developers created an improved version called "tmpfs" (which can write the data to swap space, and limit the size of a given mount point so it fills up before consuming all available memory). Initramfs is an instance of tmpfs.

These ram based filesystems automatically grow or shrink to fit the size of the data they contain. Adding files to a ramfs (or extending existing files) automatically allocates more memory, and deleting or truncating files frees that memory. There's no duplication between block device and cache, because there's no block device. The copy in the cache is the only copy of the data. Best of all, this isn't new code but a new application for the existing Linux caching code, which means it adds almost no size, is very simple, and is based on extremely well tested infrastructure.

A system using initramfs as its root filesystem doesn't even need a single filesystem driver built into the kernel, because there are no block devices to interpret as filesystems. Just files living in memory.

The big kernel lock strikes again May 26, 2008

http://lwn.net/Articles/281938/

Yanmin Zhang은 최근 2.6.26-rc1 커널부터 system performance가 약 40%가량 더 나뻐졌다고 보고했다. 그가 한 테스트는 AIM을 이용한 것이며 AIM은 많은 task들을 생성하여 각 task들이 커널의 여러 subsystem에 관련된 작업을 하는 benchmark 툴이다.

그가 찾은 문제는 generic semaphore였다. 문제를 BKL로 촛점을 맞추는 데는 그리 오랜 시간이 걸리지 않았다. BKL은 몇년전 semaphore로 교체되었었다.

Ingo Molnar은 새로운 semaphore코드로 구현을 교체하여 해결하는 방식을 제안하였다.
문제는 기존의 semaphore 구현이 너무 공평하다는 것이다. 하지만 이 공평함은 상당히 비싸다. semaphore를 얻은 쓰레드는 다른 프로세서의 run queue에 있을 수 있으며 게다가 그 쓰레드는 오랫동안 실행권을 얻지 못하여 상당히 cache cold할 것이다. 심지어 그 쓰레드는 굉장히 낮은 priority를 가지고 있어 오랫동안 실행되지 못할 수도 있다. 그 동안 그 semaphore를 기다리고 있는 큐에 저 뒤쪽에 있는 쓰레드들 (즉, 공평성의 관점에서 봤을 때 요청의 시간이 늦어 q->list의 저 뒤족에 매달려 있는 놈들) 또한 실행권을 얻지 못하는 문제가 발생한다.

결과적으로 semaphore의 어떤 쓰레드도 실행하지 못하는 dead time이 상당히 늘어난 다는 것이다.

해결은 기존의 semaphore구현을 빌려오는 것이다. 즉 공평하지 않게 처리하는 것이다.
경쟁을 하여 누가 가져갈지 모른다는 것이다.

흥미로운 것은 이 패치가 2.6.26-rc2 이전에 mainline에 merge되었다가 다시 revert되었다는 것인데 그 이유는 그 패치가 몇몇 사황에서 semaphore를 broken시켰다는 것이다. 즉 semaphore가 몇몇 상황에서 쓰레드를 깨우는 데 실패하는 경우가 있었던 것이다.


Linus는 또 다른 패치를 넣어 이 문제를 해결하였다. BKL을 spinlock을 대체하는 패치였다. 대신에 느려터지지만 공평한 generic semaphore는 그대로 남겨두었다. 하지만 이 패치는 non-preemption구간을 증가시켜 rt guy들에게는 결코 환영받지 못하였다.

하지만 Linus가 이렇게 패치를 한 이유는 BKL이나 semaphore는 제거되거나 minimization되어야 하는 상당히 낡은 메커니즘이라는 것이다. 그러한 관점에서 더 복잡했던 semaphore 코드를 다시 되돌리자고 하는 노력은 가치가 없다고 판단하였다.

그래서 이러한 결론은 다시 BKL을 커널에서 제거하고자 하는 사람들에 또다시 격려가 될지도 모른다.

Generic Semaphore

http://lwn.net/Articles/273731/

현재 커널에서 semaphore는 굉장히 optimization이 되어 있고 각 arch에 specific하게 구현되어 있었다. 하지만 Mattew는 arch에 dependent한 semaphore들을 제거하고 하나의 semaphore로 교체하였다.

구현은 상당히 직관적이고 간단하였다.

    struct semaphore {
spinlock_t  lock;
int   count;
struct list_head wait_list;
 };

그럼 사람들은 궁금해 할지도 모른다. 왜 애초에 이렇게 하지 않았나?
그에 대한 대답은 2.6.16 이전에는 semaphore가 커널의 주요 mutual exclusion중의 하나였기 때문이다. 그래서 semaphore들은 상당히 performance-critical primitive였던 것이다. 지금은 많은 부분은 mutex로 대체되었기 때문에 semaphore의 비중이 커널에서 기존보다는 많이 줄어들게 되었기 때문이다.

다른 질문은 왜 아직도 이렇게 많은 semaphore들이 사용되고 있느냐이다.

2.6.16이후로 많은 semaphore들이 mutex로 교체된 것이 사실이지만 그래도 아직 많은 semaphore들이 남아 있다. 하지만 이렇게 교체하기 위해서는 많은 audit이 필요하다. 이러한 audit이 충분해지면 semaphore의 counting feature가 필요하지 않은 것들은 mutex로 계속해서 교체될 것이며 정말 필요한 것들만으로 semaphore가 남게 될 것이다.