Lockess page cache Jun 22, 2008

speculative page references, lockless pagecache, lockless gup

리눅스 커널이 2.6으로 오면서 많은 변화가 있었지만 많은 사람들이 O(1) 스케줄러 이외에는 뚜렷이 이렇다할 만한 것을 얘기하고 있지는 않다. 사실 개인적으로 생각하였을 때 더욱 중요한 것들이 많이 있다. 그 중에 하나가 항상 RCU이다.

RCU와 같은 새로운 Locking 메커니즘이 리눅스 커널에 도입되면서(사실, 2.4때부터 있어왔던 것들이다.) 커널에 많은 부분들이 RCU를 사용하여 scalability와 performance를 동시에 높여왔다. (RCU에 관한 것을 한번 다루고 싶은 데 사실 글로 언급하기가 좀 힘들다. 얼마전 아는 후배에게 RCU에 관하여 LWN에서 두른 기사를 가지고 아주 세심하게 설명하였음에도 불구하고 이해하기를 힘들어 하는 것이 글로써는 더욱 잘 설명할 자신이 없다. -_-).

하지만 위의 패치를 이해하기 위해서는 RCU에 대한 근본적인 이해가 있어야 한다. (또 정확하게는 몰라도 된다. 위의 패치는 RCU를 사용하기도 했고 사용하지 않기도 했으니..말이 애매모호하지만 Nick Piggin의 논문을 읽어보면 왜 RCU를 사용하지 않았는가를 알 수 있고(물론 RCU 를 이해하지 못하면 아무리 논문을 읽어도 왜 사용하지 않았는가를 이해할 수 없을 것이다) 또 왜 RCU를 사용했는가도 알 수 있을 것이다.

위의 패치의 내용은 page cache lookup의 read lock을 없애자는 것이다. 리눅스 커널에서 page cache lookup은 매우 빈번한 operation중의 하나이다. 그러므로 이 lock을 없앨 수 있다면 전체 성능에 큰 개선이 될 것이다. 더욱 중요한 것은 현재 사용하는 rwlock, spinlock은 CPU의 scalability에 큰 overhead가 된다는 것이다. 이 부분은 cache snooping과 bouncing으로 인한 문제이다. 그러므로 lock을 없애면 성능에 큰 개선이 될 수 있다.

그럼 생각해보자. page cache의 lock을 없애기 위해서는 먼저 page cache가 사용하는 radix tree의 lock을 없애야 한다. 그걸 하기 위해서 Nick은 먼저 lockess radix-tree를 만들어 mainline에 반영하였다. 이것이 lockess pagecache 를 하기 위함이었기 때문에 mainline에 반영이 되고나서도 한동안 사용자가 없었다. lockess radix-tree는 기존의 interface보다 다소 loose한 semantics를 갖게 되었다. 그러므로 이 loose함을 해결하기 위해서는 page cache의 새로운 알고리즘이 필요하게 되었으며 이것이 specualtive page reference이다.

specualtve page reference는 nick이 처음 논문에 실었던 내용과 거의 유사하지만 다소 변형되었다. No new page reference를 막기 위해서 새로운 page flag를 사용하지 않고 page_freeze_refs 인터페이스를 사용하기로 했다. 이는 이미 알고리즘에서 free page와의 race문제를 해결하기 사용한 인터페이스(get_page_unless_zero)의 특성을 이용한 것이다. 그러므로 굳이 새로운 page flag를 정의할 필요가 없게 되었다.

이 패치로 인해 앞으로 우리가 눈여겨 봐야 할 것은 새로운 페이지의 할당에 대해서 referece counter를 예측해서는 안된다는 것이다. 그 페이지는 이전에 page cache에 있었다 회수되어 재할당되었을 가능성이 있으며, 그런 페이지는 speculative page reference를 가지고 있을 수 있기 때문이다. 다른 하나는 radix tree의 update 전에 page를 freeze하여 lookup과의 race문제를 해결해야 한다는 것이다. lookup과 같은 reader는 더이상 rwlock에 의존하지 않기 때문에 reader와 writer의 race 문제가 발생할 수 있기 때문이다.