[Linux Kernel] spinlock

arm 리눅스 커널의 spin lock 구현부를 보면 다음과 같다.

 

typedef struct {
	union {
		u32 slock;
		struct __raw_tickets {
#ifdef __ARMEB__
			u16 next;
			u16 owner;
#else
			u16 owner;
			u16 next;
#endif
		} tickets;
	};
} arch_spinlock_t;

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
	unsigned long tmp;
	u32 newval;
	arch_spinlock_t lockval;
 
	prefetchw(&lock->slock);
	__asm__ __volatile__(
"1:	ldrex	%0, [%3]\n"
"	add	%1, %0, %4\n"
"	strex	%2, %1, [%3]\n"
"	teq	%2, #0\n"
"	bne	1b"
	: "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
	: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
	: "cc");
 
	while (lockval.tickets.next != lockval.tickets.owner) {
		wfe();
		lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
	}
 
	smp_mb();
}
 

 

arch_spinlock_t 타입의 락 변수 lock의 tickets을 보면 next와 owner로 구성되어 있는데,

next == owner이면 해당 스핀락은 점유되지 않은 상태이고,

next가 owner보다 크다면 현재 점유되고 있는 상태이다.

 

여기서 arch_spin_lock 코드를 보면 인라인 어셈블리 코드에서 lock의 next를 1 증가시키고

이 후 while문에서 기존 lock의 next 값(1 증가시키기 전)과 owner 값을 비교하여 둘이 같으면 함수를 종료한다.

(owner 값은 busy-waiting이 끝날 수 있도록 while문 내에서 READ_ONCE를 통해 계속 최신 값을 업데이트한다.)

 

즉, next = owner = 1인 상황에서 spin_lock을 호출하면 

1) next = 2, owner = 1이 됨

2) 기존 next와 owner가 1이므로 함수 종료

가 된다.

 

이 상태에서 unlock하지 않고 (next = 2, owner = 1) 다른 프로세스가 다시 한번 spin_lock을 호출하면

1) next = 3, owner = 1이 됨

2) 기존 next와 owner가 같지 않으므로 while문 반복

2-1) lock ticket의 owner값을 읽음

2-2) 먼저 락을 획득한 프로세스가 unlock하여 owner값이 2가 되면 기존 next와 owner값이 같아져서 while문 탈출

3) 함수 종료

 

가 된다.

 

여기서 체크 -> 증가 순서가 아닌, 증가 -> 체크를 하는 것에 의아할 수 있다.

선 증가 후 체크라면 여러개의 프로세스가 동시에 점유되어있는 스핀락을 잠그려고 시도하면 버그가 일어나지 않을까 생각할 수 있다.

예를 들어, next = 2, owner = 1인 상태에서 A와 B가 동시에 lock을 시도한다고 하면

1) A가 next를 3으로 증가시킴

2) B가 next를 4로 증가시킴

3) 기존 태스크가 unlock함

4) 기존 next는 2이며 owner는 2로 업데이트되어 A와 B가 동시에 함수를 빠져나감

5) A와 B가 동시에 lock을 획득해버렸음

같은 상황이 나올 수 있다고 생각할 수 있다.

하지만 이는 strex라는 exclusive monitor instruction에 의해 방지된다.

 

인라인 어셈블리 내용을 조금 자세히 살펴보면 다음과 같다.

1. __asm__ __volatile__(
2. "1: ldrex %0, [%3]\n"
3. " add %1, %0, %4\n"
4. " strex %2, %1, [%3]\n"
5. " teq %2, #0\n"
6. " bne 1b"
7. : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
8. : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
9. : "cc");

%0, %1, %2, %3, %4는 차례대로 lockval, newval, tmp, &lock->slock, 1 << TICKET_SHIFT가 된다.

2번 라인에서 lock의 ticket 값을 lockval에 로드한다.

3번 라인에서 lockval + (1 << TICKET_SHIFT) 값을 newval에 저장한다.

4번 라인에서 lock의 ticket 값을 newval 값으로 업데이트한다.

여기서 lock의 ticket값을 자신만 업데이트하였다면 exclusive monitor status가 변경되지 않아 tmp가 0으로 업데이트된다. 만약 다른 누군가가 lock의 ticket값을 건드렸다면, exclusive monitor status가 변경되어 tmp가 1이 된다.

5번 라인에서 tmp값이 0인지 확인한다.

6번 라인에서 tmp값이 0이 아니라면 1번 레이블로 돌아가서 처음부터 다시 수행한다.

 

 

따라서 위 시나리오의 1번과 2번에서 A와 B가 동시에 next를 증가시켜 next가 4가 될 수 없다.

STREX 명령어에 대해 더 자세히 알고싶다면 다음 링크를 참고한다.

 

아무튼 arm상에서 스핀락의 구현은 위와 같다.

(참고로 x86/amd64상에서는 스핀락이 struct qspinlock으로 구현되어있다.

lock/unlock 함수들의 구현은 mutex와 상당히 유사하다.)