• Wonhyuk Yang

qspinlock note (feat. Paravirtualization)-WIP

최종 수정일: 7월 10일

최근에 ETRI와 함께 Memos라는 역가상화 연구에 참여했다. 주제는 Guest 커널의 spinlock을 수정하여 성능 개선을 하는 것이였다. 이 주제에 대해 공부하면서 얻게된 spinlock에 대한 지식들을 정리하는 시간을 가져보도록 하겠다. 현재 커널에서는 queued spinlock을 사용하고 있는데, 가상화 환경에서는 기존과 다른 문제들이 발생하며 이에 따라 다른 방식으로 spinlock이 동작한다. 따라서 해당 글에서는 queued spinlock과 가상화 환경에서의 이슈에 대해 다뤄보도록 하겠다.


그러기에 우선 전공 책에서 한 번은 보았을 CAS(compare&swap) lock을 왜 쓰지 않는지에 대해 알아보도록 하자. 실제 머신에서의 성능을 확인하기 위해 논문[3]에서 몇 가지 벤치마크 결과를 가져왔다.


Cache access performance

NUMA architecture에서 remote CPU의 cache에 접근하는 것은 local CPU의 cache에 접근하는 것보다 많은 시간이 걸린다. 아래의 그림과 같이 4개의 AMD Opteron 6172 CPUs로 구성된 시스템에서, L1 캐시에 미리 데이터를 로드한 다음 각각의 코어(Local, Remote)들이 cache에 접근하는 시간을 구해보도록 한다.



Local CPU가 L1 cache에 접근하는 데에 3 cycle이 걸렸고, 그래프에서는 초록색으로 표시된다. 같은 다이의 다른 코어의 L1 cache에 접근하는데 38 cycle이 소요되었고 그래프에서는 보라색으로 표시된다. Remote cache에 접근할 때는 2가지의 케이스가 존재한다. 만약 local 다이에 직접적으로 연결된 경로가 있다면 220 cycle이 소요되고, 그래프에서는 빨간색으로 표시된다. 직접적으로 연결된 경로가 없다면 추가적인 hop이 요구되므로 300 cycle이 소요되며, 이는 노랑색으로 그려진다.

Contention overhead

store instruction과 atomic instruction의 contention overhead를 측정하기 위해, custom benchmark를 이용한다. 해당 벤치 마크는 1개의 monitoring thread와 N개의 Non-monitoring thread로 구성되어 있다.

  • monitoring thread:shared variable에 대해 반복해서 store/atomic instruction을 실행하며 1000번의 실행할 때마다 소요된 시간을 측정한다.

  • non-monitoring thread: shared variable에 대해 반복해서 store/atomic instruction을 실행한다.

Towards more scalable mutual exclusion for multicore architectures, Figure 2.7: Cost of cache accesses and instructions

1 thread: 한 개의 thread(monitoring thread)만 실행될 때, store instruction은 73 cycle이 소요되었고 cas instruction은 98 cycle이 소요되었다. 이 경우, shared variable은 항상 monitoring thread의 L1 cache에 위치해 있다.


N thread: 한 개의 monitoring thread와 여러 개의 Non-monitoring thread가 개별적인 코어에서 실행된다. 따라서 cache coherence 프로토콜에 따라 다른 코어의 cache line을 invalid 하고 본인의 L1 cache로 fetch하는 과정이 수행된다. Thread가 늘어나면 늘어날 수록 요구되는 cache coherence traffic은 늘어나며, 48개 thread일 경우 소요되는 시간은 수 천 cycle에 이르게 된다.


Monitoring thread가 접근하는 shared variable가 local NUMA 메모리에 위치한 경우, Remote NUMA에 위치한 경우보다 더 좋은 성능을 보인다. 이미 L1 cache line에 로드하였기 때문에, RAM에 접근하지도 않지만 더 좋은 성능을 보인다. 이것은 AMD의 HT Assist technology 때문이다.


결론적으로, atomic operation은 scalable 하지 않으며 spinlock이 단순히 atomic operation으로 구현되었다면 scalable 하지 않을 것이다.


MCS Lock

compare-and-swap으로 구현된 spinlock이 NUMA system과 같은 곳에서 scalable 하지 않다는 것은 많이 알려진 사실이다. 이는 shared variable에 대해서 cost가 큰 inter node traffic이 빈번하게 발생하기 때문이다. 이러한 문제를 software 로 해결하는 방법 중 하나가 MCS lock이다.


MCS lock은

  • queue based lock이기 때문에 fairness를 보장한다.

  • 각각의 Thread들은 Busy waiting할 때, local varible에 대해서 spinning하기 때문에 inter node traffic을 유발하지 않는다.

MCS Lock의 pseudo code (C style)은 아래의 코드 스니펫에서 확인할 수 있다.


MCS Lock 알고리즘은 단방향 link로 연결된 queue을 사용하며, queue의 tail을 lock 변수가 가르키고 있다.

  • Queue Head의 CPU만 Critical section을 실행한다. (물론 명시적으로 Head가 존재하지 않는다.)

  • Critical section을 실행한 CPU는 다음 Node가 존재한다면, locked를 False로 변경한다.

  • 새로운 Node는 Queue의 tail에 삽입되며, locked가 False가 될 때까지 spinning한다.


결과적으로, 아래 그림에서 볼 수 있듯이 MCS Lock은 Highly contended(그림에서 Processor가 많은 상황)일 때 Test&Set Lock보다 성능이 우수하다. 하지만 uncontended인 경우 Test&Set Lock이 빠른데 이것은 실행해야 할 instruction의 수가 훨씬 적기 때문이다.


QSpinlock in Linux Kernel

기존의 spinlock을 MCS lock으로 대체하는 것은 다음과 같이 고려해야 할 구현 및 성능 이슈들이 있다.

  1. uncontended한 lock의 경우, MCS Lock의 성능이 기존의 lock보다 나쁘다.

  2. mcs lock의 lock/unlock api는 lock과 node를 요구하고, 이는 기존의 spinlock api와 다르다.

  3. spinlock 구조체 내부는 atomic_t로 구성되어 있는데 이는 4byte라 pointer를 저장할 수 없다.

  4. 가상 환경에서 성능 저하 이슈가 존재한다.

그렇다면 이제 각각의 이슈들을 어떤 방식으로 해결했는지 알아보도록 하자.


Issue 1.

MCS lock을 사용하기 위해서는 CONFIG_QUEUED_SPINLOCKS 옵션이 활성화 되어야 한다(아직, x86, arm64와 같은 특정 아키텍처만 지원한다.).


해당 옵션이 활성화 되면, arch_spin_x 들의 정의는 queue_spinlock에서 구현된 함수들로 매핑이 진행된다.


queue spin lock은 contention 상황에 따라 CAS 기반 또는 MCS로 사용될 지 결정되는 하이브리드 구조이다. 그것을 결정하는 로직은 단순하다. 아래와 같이 lock을 획득하면, CAS로 동작한 것과 동일하고 락을 얻지 못하면, slow path로 진입하며 MCS Lock으로 동작한다.


Issue 2,3

구현에 사용된 아이디어로,

  1. nested 될 수 있는 모든 가능성(task, softirq, hardirq, nmi)을 고려하여 Percpu 변수로 node들을 선언한다.(Line 7)

  2. node들은 cpu id와 context에 따라 결정되므로, 이 값들을 인코딩하여 32bit 내에 저장할 수 있도록 한다.(encode_tail, decode_tail)

위와 같은 구조로, lock을 할 때 인자로 node를 받지 않아도 된다. get_cpu()와 같은 함수로 얻을 수 있는 cpu 번호와 node 인덱스만 있으면 어떤 node를 사용해야 할 지 특정할 수 있다.


locking/qspinlock: Introduce a simple generic 4-byte queued spinlock

locking/qspinlock: Add pending bit


Issue 4

spinlock은 cpu가 preemption 되지 않을 것이라는 가정을 두고 있고, 이는 Physical machine에서는 유효하다. 하지만, 가상 머신의 vCPU는 Hypervisor의 schedule에 의해 preemption될 수 있기 때문에 더 이상 유효하지 않은 가정이다.

또한 가상 환경에서는 LHP(Lock Holder Preemption)과 LWP(Lock Waiter preemption) 문제가 발생할 수 있다.

  • LHP: Lock을 획득한 vCPU가 Hypervisor에 의해 preemption되는 경우

  • LWP: Lock을 얻기 위해 spinning 하는 vCPU가 Hypervisor에 의해 preemption되는 경우.

특히 ticket lock 혹은 mcs lock와 같은 fairness lock은 LWP로 인한 성능 저하가 크다. 아래의 테이블에서 vCPU가 늘어나면 Spinning Cycle(Busy waiting에 소요된 사이클)이 Total Cycles의 80% 이상을 차지하게 된다.

이러한 문제를 해결하기 위해 다영한 연구들이 진행되었고 이를 완화하기 위해 다양한 SW/HW 기법들이 제공된다.

  • Intel Pause loop detection: 지속적으로 pause instruction이 일어나면, Hypervisor로 trap이 발생한다.

  • Paravirtualized lock: Halt instruction과 kick-cpu hypervisor call을 통해 busy waiting 하는 vCPU를 sleep, wake up하게 하는 방법이다.


PARAVIRT 옵션을 활성화시키면, Kernel은 현재 Hypervisor 위에서 돌아가는지를 검사(detect)한다. Hypervisor마다 고유하게 식별할 수 특징이 있는데 kvm의 경우 cpuid instruction[4]을 이용하면 된다.

즉, Hypervisor 위에서 돌아가더라도 완전히 transparent 하지 않다. 물론 악의적인 사람이 hypervisor code를 수정하여 finger print를 제거할 수 있다. 이 경우에는 시간의 불연속성으로 detect할 수도 있다고 한다.

만약 커널이 hypervisor위에서 동작하면 paravirtualized된 함수들로 커널 control path를 변경한다. kvm 위에서 동작하고 PARAVIRT_SPINLOCKS 옵션을 활성화하였다면 kvm_spinlock_init 함수를 호출한다. Hypervisor가 PV spinlock 기능을 사용할 수 있으면 spinlock의 slowpath가 native_queued_spin_lock_slowpath (초기 값)이 아닌_pv_queued_spin_lock_slowpath가 사용된다.

또한 wait와 kick 함수에 kvm_wait/kvm_kick_cpu 함수를 등록하여 kvm Hypervisor가 처리할 수 있는 hypercall 또는 instruction을 사용할 수 있도록 한다. parvirtualized 기능을 사용하기 위해서 qspinlock slow path 중간 중간에 pv hook들이 존재한다.

pv_hook들은 내부적으로 pv_wait, pv_kick_cpu와 같은 함수들을 호출하며 이 함수들은 pv_ops.lock에 등록된 ops들을 사용한다.


Todo. pvhook과 pv 동작 방식 설명 추가 및 그림 추가


또한 pv 옵션이 활성화되어 있으면, 독특한 방식으로 컴파일이 된다. qspinlock.c에 정의된 queued_spin_lock_slowpath는 native_queeud_spin_lock_slowpath로 전처리되어 컴파일되며, __pv_queued_spin_lock_slowpath로 재정의하고 자기 자신을 include한다. 따라서 한 함수가 2개의 이름으로 컴파일된다.


좀 더 Code 수준에서 전반적인 이해를 하기 위해서는 해당 커밋(locking/pvqspinlock: Implement simple paravirt support for the qspinlock) 참고하며 된다. PV 패치에 대한 설명은 해당 링크[5]를 참고해도 도움이 된다.


Reference

[1] https://lwn.net/Articles/556141/

[2] FRIEBEL, Thomas; BIEMUELLER, Sebastian. How to deal with lock holder preemption. Xen Summit North America, 2008, 164.

[3] Lozi, Jean-Pierre. Towards more scalable mutual exclusion for multicore architectures. Diss. Université

Pierre et Marie Curie-Paris VI, 2014.

[4] https://kb.vmware.com/s/article/1009458

[5] https://lwn.net/Articles/556141/


조회수 56회댓글 0개

관련 게시물

전체 보기