본문 바로가기

Programming

How Linux kernel implements raw_spin_lock

리눅스 커널의 어떤 부분들을 소스코드를 보면 이해가 더 안가는 부분들이 많이 있다.

너무나도 많은 조건부 컴파일 매크로들과 토큰연결 연산자로 결합되어 사실상 소스코드를 보는게 아니라

난독화된 코드를 리버싱하는 수준인 경우가 있는데, 이런경우는 차라리 컴파일된 커널이미지를 디버깅해서

어셈블리 코드를 보는것이 훨씬 이해하기 쉽다.


그런 경우중 하나가 스핀락인데, 기본적으로 커널코드는 여러 어플리케이션이 공유해서 쓰기때문에 Race Condition

처리에 굉장히 민감하다. 성능의 이슈를 고려해서 뮤텍스, 스핀락 등 여러가지가 사용되지만, 가장 단순하고 간단한

락이 바로 아래의 스핀락이다.


아래는 커널내부의 방대한 코드중 스핀락을 사용하는 한 부분인데, raw_spin_lock 은 한개의 변수에 대한 포인터를 파라미터로 받는것을 알 수 있다. 그리고 스핀락을 호출하는 코드들을 보면 공통적으로 Critical Section 을 지난뒤에 파라미터로 넘겼던 스핀락 변수에 +1 을 해준다. 즉, 이것이 바로 unlock 이라는것인데... 그럼 어떤방식으로 lock 을 잡길래 +1 을 해주므로써 언락을 할까?


.init.text:FFFFFFFF81CF7FDA                 mov     rdi, offset byte_FFFFFFFF81E7F570

.init.text:FFFFFFFF81CF7FE1                 mov     rbp, rsp

.init.text:FFFFFFFF81CF7FE4                 call    _raw_spin_lock

.init.text:FFFFFFFF81CF7FE9                 mov     rdi, offset byte_FFFFFFFF81E7F560

.init.text:FFFFFFFF81CF7FF0                 call    sub_FFFFFFFF812950A0

.init.text:FFFFFFFF81CF7FF5                 add     cs:byte_FFFFFFFF81E7F570, 1

.init.text:FFFFFFFF81CF7FFC                 test    rax, rax

.init.text:FFFFFFFF81CF7FFF                 jnz     short loc_FFFFFFFF81CF8019

.init.text:FFFFFFFF81CF8001                 mov     rdx, offset byte_FFFFFFFF81E7F560

.init.text:FFFFFFFF81CF8008                 mov     rsi, offset aSIosched ; "%s-iosched"

.init.text:FFFFFFFF81CF800F                 mov     edi, 1

.init.text:FFFFFFFF81CF8014                 call    sub_FFFFFFFF81054720



아래는 _raw_spin_lock 에 대한 코드다.

소스코드에서 볼때와는 다르게 너무나도 단순하다 -_-;;

단지 RDI 로 받은 포인터에 Atomic add 를 통해서 0x100 을 lock xadd 한다.

"lock xadd [rdi], ax"

이것이 무슨 의미인가? 디버깅해보면.. 일단 [rdi] 에 ax 를 더함과 동시에 [rdi] 의 하위 2바이트를 ax 로 가져온다(더하기 전의 값을)

즉, 기존의 AH, AL 값을 가져온뒤 AH 부분을 +1 하는것인데, 그러고난뒤에 AH, AL 두 바이트를 비교하여 서로 같으면 락을 획득한것으로 치고 넘어가고, 그렇지 않으면 이 두 값이 같아질때까지 무한루프(스핀) 를 돈다.


.text:FFFFFFFF8179A150 _raw_spin_lock  proc near               ; CODE XREF: sub_FFFFFFFF81003DD0+45p

.text:FFFFFFFF8179A150                                         ; sub_FFFFFFFF81003DD0+FFp ...

.text:FFFFFFFF8179A150                 push    rbp

.text:FFFFFFFF8179A151                 mov     rbp, rsp

.text:FFFFFFFF8179A154                 mov     eax, 100h

.text:FFFFFFFF8179A159                 lock xadd [rdi], ax

.text:FFFFFFFF8179A15E                 movzx   edx, ah

.text:FFFFFFFF8179A161                 cmp     dl, al

.text:FFFFFFFF8179A163                 jz      short loc_FFFFFFFF8179A171

.text:FFFFFFFF8179A165                 nop     dword ptr [rax]

.text:FFFFFFFF8179A168

.text:FFFFFFFF8179A168 loc_FFFFFFFF8179A168:                   ; CODE XREF: _raw_spin_lock+1Fj

.text:FFFFFFFF8179A168                 pause

.text:FFFFFFFF8179A16A                 movzx   eax, byte ptr [rdi]

.text:FFFFFFFF8179A16D                 cmp     al, dl

.text:FFFFFFFF8179A16F                 jnz     short loc_FFFFFFFF8179A168

.text:FFFFFFFF8179A171

.text:FFFFFFFF8179A171 loc_FFFFFFFF8179A171:                   ; CODE XREF: _raw_spin_lock+13j

.text:FFFFFFFF8179A171                 pop     rbp

.text:FFFFFFFF8179A172                 retn

.text:FFFFFFFF8179A172 _raw_spin_lock  endp


즉 AH, AL 이 다르다는것(메모리에서 xadd 를 통해서 가져온 2 바이트가) 은 누군가가 락을 잡고있다는 뜻이다. 그리고 위에서 보다시피 락을 잡을때 메모리상의 AH 에 대응되는 부분을 ++ 시키고, Unlock 을 할때는 AL 을 ++ 시킨다. 한마디로 아무도 락을 안잡고 있을때는 메모리상의 락 변수가 AH == AL 인 상태인데, 누군가 Lock 을 잡으면 AH 가 ++ 되서 AH == AL+1 이 된다.  그리고 이상태에서 누가 또 Lock 을 잡으려 시도하면 AH == AL+2 이 되고... 그다음의 누군가가 Lock 을 잡으려하면 AH==AL+3 가 되고... 

pause 부분 이후를 보면 AH(DL) 은 처음에 락변수에서 가져온 값을 그대로 유지하면서 AL 부분은 반복적으로 메모리상의 락변수에서 다시 가져온다. 각기 그러한 AL 과 AH 값을 비교하면서 같아질때까지 대기탄다.  그렇게되면 당연히 메모리상의 락변수에 대응되는 AL 을 1 증가시켜서 Lock 을 누군가 풀면 AH 가 AL 보다 1 큰상태로 대기타고 있던쓰레드가 락을 획득하는것이 되고 그 쓰레드가 다시한번더 AL++ 을 하게되면 AH==AL+2 인 상태로 락을 대기하던 쓰레드가 락을 획득하고... 즉 Queue 처럼 순서대로 Waiter 들이 락을 획득하게 된다.


처음에는 Lock 이 하나의 카운터 변수로 존재해서, 0 이면 waiter 가 없는상태라서 lock 을 획득할수 있고, 0 이상이면 누군가 Lock 을 해제할때 카운터 변수를 -- 해줘서 0 이 될때까지 대기한 뒤에 lock 을 잡는식으로 하지 않을까 생각했는데, 지금 생각해보면 이런방식으로 구현할경우 Waiter 쓰레드들의 우선순위가 랜덤이 되버린다 -_-


대기하던 waiter 들이 순서대로 lock 을 획득하게 해주면서 2바이트의 변수만을 이용하여 스핀락이 구현되어있다.