Julram's 개발 낙서장

Linux: 2.6.30
arch: x86

spin lock은 mutiprocessor system에서
여러 processor가 동시에 critical section에 진입하지 못하도록 하는 synchronization 기법이다.
한 processor가 lock을 가지고 있으면 다른 processor들은 unlock될 때까지 busy-wait하다가
lock을 차지하기 위해 동시에 lock 변수에 접근(write)한다.

여기서 두 가지 문제가 발생할 수 있는데
첫 번째는 각 processor 간에 lock을 획득하는 순서를 보장할 수 없기 때문에
먼저 spin lock을 기다리던 processor가 더 나중에 lock을 얻을 수도 있다는 것이다.
때문에 spin lock은 공정하지 못하다.

또 하나의 문제는 성능에 관련된 것으로
cache coherency로 인해 한 processor가 lock 변수에 write를 하게되면
다른 모든 processor의 cache line이 invalidate된다.
따라서 contention이 심한 경우 lock을 얻은 processor에서도 반복적으로 cache miss가 발생하여
실행 성능이 매우 나빠질 수 있다. (보통 lock 변수와 데이터는 같은 line에 놓여있을 것이다.)

ticket spin lock은 이를 개선하기 위해 2.6.25 버전부터 도입된 것으로
lock을 기다리는 각 processor들은 자신 만의 ticket을 부여받고
자기 차례가 돌아오는 경우에만 write를 시도하므로
순서대로 lock을 얻을 수 있으며 전체적으로 cache miss 횟수를 줄일 수 있다.

그럼 코드를 살펴보자.
spin_lock()은 다음과 같이 정의되어 있다.

/* include/linux/spinlock.h */ 
#define spin_lock(lock) _spin_lock(lock)
 /* kernel/spinlock.c */ 
void __lockfunc _spin_lock(spinlock_t *lock) 
{ 
           preempt_disable(); 
           spin_acquire(&lock->dep_map, 0, 0, _RET_IP_); 
           LOCK_CONTENDED(lock, _raw_spin_trylock, _raw_spin_lock); 
} 

먼저 커널 선점 기능을 disable한 후에 spin_acquire()를 호출하는데이는 CONFIG_LOCKDEP가 선택된 경우 lock을 얻으려는 processor의 정보를 기록하기 위한 것이다.

LOCK_CONTENDED의 경우도 비슷한데 CONFIG_LOCKSTAT이 설정되지 않은 경우에는
단순히 _raw_spin_lock()을 호출하는 코드로 확장된다.
_raw_spin_lock도 CONFIG_DEBUG_SPINLOCK이 설정되지 않았다면
단순히 __raw_spin_lock()을 호출하는 코드로 확장된다.
__raw_spin_lock 계열의 함수는 architecture-specific 함수로 x86의 경우 다음과 같이 정의된다.

static __always_inline void __raw_spin_lock(raw_spinlock_t *lock)
{
    __ticket_spin_lock(lock);
}

static __always_inline int __raw_spin_trylock(raw_spinlock_t *lock)
{
    return __ticket_spin_trylock(lock);
}

static __always_inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
    __ticket_spin_unlock(lock);
}

위에서 볼 수 있듯이 단순히 ticket_spin_lock 계열의 함수를 호출하는 방식으로 구현되어 있다.

먼저 간단한 unlock의 경우부터 살펴보기로 하자.
ticket spin lock은 processor의 수가 256 개를 넘어가는 머신의 경우를 구분하여 구현되어 있는데
여기서는 이 부분은 무시하고 NR_CPUS 값이 256 이하인 경우 만을 살펴볼 것이다.
따라서 spin lock을 기다라는 모든 processor의 정보는 한 byte 내에 포함할 수 있다. (TICKET_SHIFT = 8)

static __always_inline void __ticket_spin_unlock(raw_spinlock_t *lock)
{
    asm volatile(UNLOCK_LOCK_PREFIX "incb %0"
             : "+m" (lock->slock)
             :
             : "memory", "cc");
}

unlock은 단순히 raw_spinlock_t 구조체의 slock 변수를 1 증가시키는 일만 수행한다. 여기서 주의깊게 살펴보아야 할 부분은 incb로 최하위 바이트의 값 만을 증가시킨다는 것이다.

lock 변수는 개념적으로 두 부분으로 나누어지는데
위에서 언급한대로 NR_CPUS가 256보다 작은 경우에는 하위 두 바이트를 사용하며
상위 바이트는 lock을 기다리는 processor들을 위한 ticket 값이고 (next)
하위 바이트는 현재 lock을 가지고 있는 processor의 ticket 값이다. (owner)

nlock()이 호출되면 현재 processor가 lock을 반환한다는 의미이므로
다음 processor가 lock을 얻을 수 있도록 owner ticket을 증가시킨다.
lock은 자기가 보관하고 있는 next ticket 값과 owner ticket 값이 일치하는 경우에 얻는다.

 
static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock) 
{ 
          short inc = 0x0100;
          asm volatile ( LOCK_PREFIX "xaddw %w0, %1\n"
                          "1:\t" "cmpb %h0, %b0\n\t" 
                          "je 2f\n\t" "rep ; nop\n\t" 
                          "movb %1, %b0\n\t"
                           /* don't need lfence here, because loads are in-order */
                          "jmp 1b\n" "2:" : "+Q" (inc), 
                          "+m" (lock->slock) : : "memory", "cc"); 
} 

이 코드는 (동기화와 관련된 문제를 제외하면) 개념적으로 아래와 같다.

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
    short inc = 0x100;
    short tmp = (short) lock->slock;
    lock->slock += inc;

    while ((tmp >> 8) != (tmp & 0xFF)) {
        cpu_relax();
        tmp = (tmp & 0xFF00) | (unsigned char) lock->slock;
    }
}

우선 lock->slock 값을 읽어오고 동시에 next ticket을 증가시킨다. (lock; xaddw)읽어온 slock의 상위 바이트는 현재 processor의 ticket 값으로 저장하고

동시에 다음 processor가 lock을 얻기 위한 ticket을 증가시키는 것이다.
이는 LOCK_PREFIX가 붙어있으므로 atomic하게 수행된다.

그리고는 증가시키기 전의 slock 변수에서 next와 owner ticket이 동일한지 검사한다. (cmpb %h0, %b0)
만약 같다면 현재 processor가 lock을 얻은 것이므로 loop을 종료하고 critical section에 진입한다.
그렇지 않다면 계속 slock의 owner ticket 값을 갱신한 후 다시 검사한다. (movb %1, %b0)

즉, unlock이 수행된 후에 lock을 얻기 위해 다시 lock 변수를 write하지 않아도 된다!

trylock()은 slock 값을 먼저 살펴본 후 lock을 얻을 수 있는 경우에만 slock 변수를 write한다.

static __always_inline int __ticket_spin_trylock(raw_spinlock_t *lock)
{
    int tmp, new;

    asm volatile("movzwl %2, %0\n\t"
             "cmpb %h0,%b0\n\t"
             "leal 0x100(%k0), %1\n\t"
             "jne 1f\n\t"
             LOCK_PREFIX "cmpxchgw %w1,%2\n\t"
             "1:"
             "sete %b1\n\t"
             "movzbl %b1,%0\n\t"
             : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
             :
             : "memory", "cc");

    return tmp;
}

이 코드는 (동기화와 관련된 문제를 제외하면) 개념적으로 아래와 같다.

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
    short inc = 0x100;
    short tmp = (short) lock->slock;
    lock->slock += inc;

    while ((tmp >> 8) != (tmp & 0xFF)) {
        cpu_relax();
        tmp = (tmp & 0xFF00) | (unsigned char) lock->slock;
}

우선 lock->slock 값을 읽어오고 동시에 next ticket을 증가시킨다. (lock; xaddw)

읽어온 slock의 상위 바이트는 현재 processor의 ticket 값으로 저장하고
동시에 다음 processor가 lock을 얻기 위한 ticket을 증가시키는 것이다.
이는 LOCK_PREFIX가 붙어있으므로 atomic하게 수행된다.

그리고는 증가시키기 전의 slock 변수에서 next와 owner ticket이 동일한지 검사한다. (cmpb %h0, %b0)
만약 같다면 현재 processor가 lock을 얻은 것이므로 loop을 종료하고 critical section에 진입한다.
그렇지 않다면 계속 slock의 owner ticket 값을 갱신한 후 다시 검사한다. (movb %1, %b0)
즉, unlock이 수행된 후에 lock을 얻기 위해 다시 lock 변수를 write하지 않아도 된다!

trylock()은 slock 값을 먼저 살펴본 후 lock을 얻을 수 있는 경우에만 slock 변수를 write한다.

이 코드는 개념적으로 아래와 같다.

static __always_inline int __ticket_spin_trylock(raw_spinlock_t *lock)
{
    int tmp, new;

   tmp = (short) lock->slock;
    if ((tmp >> 8) != (tmp & 0xFF)) {
        return 0;

    new = tmp + 0x100;
    if (tmp == (short) lock->slock) {
        lock->slock = new;
        tmp = 1;
    } else {
        tmp = 0;
    }
    return tmp;
}

먼저 현재 slock 변수의 값을 읽어서 lock을 기다리는 processor가 있는지 확인한다. (movzwl %2, %0)
이는 next ticket과 owner ticket이 다른 경우이므로 바로 0을 return한다. (cmpb %h0, %b0)
그렇지 않다면 next ticket을 1 증가시켜두는데 (leal 0x100(%k0), %1)
이는 tmp(%0)의 값을 new(%1)로 옮기고 new 값을 증가시키는 작업을 한 번에 처리해주는 hack이다.

그 동안 slock값이 바뀌지 않았다면 증가시킨 값으로 갱신한다. (lock; cmpxchgw %w1,%2)
이도 LOCK_PREFIX가 붙어있으므로 atomic하게 수행된다.
cmpxchg의 결과는 ZF 플래그에 저장되므로 이 값을 읽어서 new 변수의 최하위 바이트에 저장하고 (sete %b1)
이를 다시 tmp 변수에 옮긴 후 return한다. (movzbl %b1,%0)

multi thread 프로그래밍이 발전하면서, 초기에 여러 thread간의 교통정리(synchronization)을 위해

lock이라는 메커니즘이 등장하게 됩니다.

초기에 존재했던 lock은 mutex(MUTually EXclusive lock)로 존재 했습니다.

mutex는 만약 다른 쓰레드가 lock을 잡고 있는 경우 쓰레드가 sleep하도록 설계되어,

쓰다보니 critical section이 매우 짧은 경우에 퍼포먼스가 낭비되는 단점이 있고,

lock을 잡지 못해서 thread가 sleep하는 경우, sleep을 하기 위한 작업을 하는 시간 안에

이미 lock이 풀려 버리기 때문이었죠.

그래서 spinlock이 등장하게 되는데, spinlock은 lock을 잡을 수 없을 때,

mutex처럼 sleep에 들어가는게 아니라, loop를 돌며 busy-waiting을 하게 하는 겁니다.

critical section이 짧은 경우는 굳이 mutex가 아니라 spinlock을 쓰면 더 빠르게 동작 할 수 있는 장점이 있습니다.

이렇게 해서 행복하게 마무리 되는가 싶었으나.....

인터럽트가 발생하는 경우 또 다른 문제가 야기 되게 됩니다.

thread가 spinlock을 잡고 일을 하고 있는데, 더 강력한 인터럽트가 발생해 버리면,

인터럽트 핸들러가 돌고 있는데, 그 인터럽트 핸들러가 spinlock을 잡으려고 하는 경우가 발생합니다.

이럴 경우, 원래 thread가 spinlock을 잡고 있었는데, 그 thread가 더 이상 돌지 못하게 되어 deadlock이 발생하게 됩니다.

그래서 등장한 것이 spin_lock_irq 함수이고, 이 놈은 spinlock을 잡으면서 인터럽트를 disable 시켜주죠.

(물론, enable 해주면 그 동안 발생한 인터럽트가 처리됩니다.)

spin_lock_irq를 쓰면 spinlock의 critical section내에서 인터럽트 자체가 처리되지 않으므로, 앞에서 언급한 그런 문제가

발생하지 않게 됩니다.

하지만, 함수를 nesting해서 쓰게 되는 경우, spin_lock_irq 함수가 까다로워 집니다.

몇번을 disable 했던지간에, enable은 한번만 해주면 결국 인터럽트가 다시 복구되는데,

spin_lock_irq를 하려는 함수가 들어왔을때 인터럽트가 enable 상태인지, disable 상태인지 모르면,

spin_unlock을 할 때 enable 해야 할지 말아야 할지 모르게 되버리는 상황이 생깁니다.

이런 경우에 사용하는게 spin_lock_irqsave 함수 인데요. 이 함수는 irq를 disable 하면서 irq가 이전에 enable인지 disable인지

를 변수에 저장해줍니다.

그래서 이 함수는 저장할 변수를 인자로 받게 됩니다.

interrupt disable 함수가 nesting 되어서 사용될 때에는 이 함수를 이용하시는게 좋습니다.

다만, 단순히 disable만 하는게 아니라 상태를 메모리에 저장도 하기 때문에,

퍼포먼스 오버헤드는  spin_lock_irq보다 살짝 크게 됩니다.

추가적으로, spin_lock()이 interrupt handler / softirq에서 사용할 수 없는 건 아닙니다.

Thread context 실행 중 임의의 시점에 중지되고 softirq나 irq가 실행될 수 있으며, softirq 실행 중엔 임의의 시점에 irq가 실행될 수 있습니다. 

위의 설명과 같이, 만약 같은 lock을 thread context와 irq에서 사용한다면 thread context에서 락을 잡고 있는 중에 irq가 실행되고 irq가 다시 같은 락을 획득하려고 할 수 있습니다. 

따라서, 위 현상은 데드락입니다. spin_lock_{irq[save]|bh}()는 이런 데드락을 피하기 위해서 사용합니다.

하나의 lock이 irq에서도 사용되고 softirq나 thread context에서도 사용된다면, 

softirq/thread context에선 spin_lock_irq()를 irq 코드에선 spin_lock()을 사용합니다. 

같은 코드를 irq와 다른 컨택스트에서 공유하거나해서 irq 상태를 알 수 없으면 spin_lock_irqsave()를 쓰면 됩니다. 

irq handler안에서는 spin_[un]lock_irq()를 쓰면 문제를 야기 시킬 수 있습니다. 

마찬가지로 softirq와 thread context가 공유하는 락은 thread context에서 spin_lock_bh()를 쓰면 됩니다. 

softirq disable은 카운팅이 되기 때문에 softirq안에서도 그냥 써도 무방합니다. (bh_save가 없는 이유 입니다).

하나의 컨택스트 (irq, softirq, thread context 중) 안에서만 사용되는 Lock은 spin_lock()을 씁니다.

하나 이상의 컨택스트에서 사용되는 락은 낮은 우선순위의 컨택스트에서 락을 잡을 때 락을 사용하는 컨택스트 중 가장 높은 우선순위를 막고 잡으면 됩니다.

정리

• spin_lock_init(spinlock)

spin_lock을 커널에 초기화 및 등록 합니다.

• spin_lock (spinlock)   ↔  spin_unlock (spinlock)

dead lock의 위험, interactivity등 시스템의 퍼포먼스에 영향이 크다.

기본이 spinlock. 다른걸 이용할 필요가 없다면 이걸 쓴다.

가장 퍼포먼스 오버헤드가 적다.

• spin_lock_irq (spin lock irq disable)   ↔  spin_unlock_irq(spinlock enable)

interrupt handler와 일반 thread가 spinlock을 공유하는 경우에 사용한다.

spinunlock irq enable로 unlock을 해 주면, 인터럽트가 몇번 disable됐는지 상관 않고

enable돼 버리므로 주의한다.

• spin_lock_irqsave (spin lock irq save)   ↔   spin_unlock_irqresotre(spin lock irqsave)

spin_lock_irq과 같지만, irq disable하기 직전의 interrupt enable여부를 변수에 저장한다.

spinlock을 이용하는 시점에서 interrupt enable여부를 확신할 수 없는 경우에 쓴다.

메모리에 상태를 저장하게 되므로, disable만 하는 함수에 비해서는 느리다.

• 비교