Kernel Likely/Unlikely

Likely and Unlikely

Likely() 와 Unlikely() 의 사용법과 용도를 알아보자. 원본 URL : http://kernelnewbies.org/FAQ/LikelyUnlikely

이 함수들은 뭐하는 건가?

예제를 보자.

bvl = bvec_alloc(gfp_mask, nr_iovecs, &idx);
if (unlikely(!bvl)) {
  mempool_free(bio, bio_pool);
  bio = NULL;
  goto out;
}

위와 같이, 특정 condition 을 확인하는 용도로 사용되는데 위의 code는 bvec_alloc으로 할당 받고 bvl 이 유효하지 않는 address이라면 free 하고 NULL 로 만들어주는 code이다. 

likely(), unlikely() 는 include/linux/compiler.h 에 정의된 macro 이다. 이것의 용도는 컴파일러에게 branch 예측을 도와 주는 용도로 사용이된다. 즉, 대부분 0으로 예측이 된다면 unlikely(x) 의 형태로 쓰고, 1로 예상되는 값을 likely(x) 로 쓴다. 예측을 도와 줌으로써 성능의 향상을 볼 수 있도록 하는 것이다.

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

__builtin_expect() 함수는 GCC 문서의 설명을 살펴보면,(원본은 http://kernelnewbies.org/FAQ/LikelyUnlikely 여기에서 보시길)

-- Built-in Function: long __builtin_expect (long EXP, long C)
   '__builtin_expect' 를 사용하는 것은 compiler 에게 branch prediction 정보를 제공해주기 위한 것이다. 일반적으로 개발자들은 자신의 program이 실제로 어떻게 수행되는지 알기가 힘들기 때문에 '-fprofile-arcs' option을 통해 profile 을 feedback 받는 것을 선호합니다. 그렇지만, 어떤 application들은 이것 조차도 수집하기 힘든경우가 있긴 하다.


반환 값은(return value)는 EXP 인 완전한(?) 표현이어야 한다.(아래의 예제를 통해..) EXP와 C는 서로 같아야 합니다.(EXP == C)


    if (__builtin_expect (x, 0))
       foo ();
이렇게 구현한 것의 의미는 foo() 라는 함수가 불리지 않기를 기대하는 것입니다. 즉, 'x' 는 대부분 0 의 값을 가졌으면 한다는 것이다. 또 다른 방법으로는 EXP 에 "식"으로 사용할 수 있다.


    if (__builtin_expect (ptr != NULL, 1))
       error ();
예제가 조금 이상하다. ptr != NULL 인 경우가 대부분이라고 알려주는 것인데, NULL 이 아닐때는 error() 가 실행된다. 아닌 경우라면 bypass.

아래의 예제를 보자.

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

int main(char *argv[], int argc)
{
   int a;

   /* Get the value from somewhere GCC can't optimize */
   a = atoi (argv[1]);

   if (unlikely (a == 2))
      a++;
   else
      a--;

   printf ("%d\n", a);

   return 0;
}

위의 code를 편집기에 붙여 넣고 저장 한뒤,(test.c)

$ gcc -o test test.c -O2

$ objdump -S test

하면 많은 내용들이 나오는데 그 중에 <main> 이라는 부분을 찾아보면

080483b0 <main>:
 // Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             Test the value
 80483ca:       83 f8 02                cmp    $0x2,%eax
 //             --------------------------------------------------------
 //             If 'a' equal to 2 (which is unlikely), then jump,
 //             otherwise continue directly, without jump, so that it
 //             doesn't flush the pipeline.
 //             --------------------------------------------------------
 80483cd:       74 12                   je     80483e1 <main+0x31>
 80483cf:       48                      dec    %eax
 //             Call printf
 80483d0:       52                      push   %edx
 80483d1:       52                      push   %edx
 80483d2:       50                      push   %eax
 80483d3:       68 c8 84 04 08          push   $0x80484c8
 80483d8:       e8 f7 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483dd:       31 c0                   xor    %eax,%eax
 80483df:       c9                      leave
 80483e0:       c3                      ret

이것도 원본 URL 에서 붙여 넣은 것인데, 직접 해보니 조금 짤린 부분이 있는 것으로 보인다. a == 2가 같은 것이 참이라면 0x80483e1 으로 jump 를 하게 되는데 jump 되는 주소의 instruction 이 복사가 안된 듯 하다. 거기에 mov command 로 a++ 인 "3"을 직접 넣어주고 printf 를 호출해야 하니, 80483d0의 주소로 바로 jump 하는 instruction 이 있을 것이다.

주석에서 보듯이, unlikely() 의 경우 a의 값과 2가 같지 않는것이 대부분이라고 해준것이다. 만약 2와 같지 않으면 jmp instruction 을 수행하지 않고 pipeline flush 가 일어나지 않도록 하여 성능 향상을 주는 것이다.

반대로 likely() 로 변경하여 진행해보자.

컴파일을 다시 하고, objdump 로 disassem 해보면,

080483b0 <main>:
 //             Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             --------------------------------------------------
 //             If 'a' equal 2 (which is likely), we will continue
 //             without branching, so without flusing the pipeline. The
 //             jump only occurs when a != 2, which is unlikely.
 //             ---------------------------------------------------
 80483ca:       83 f8 02                cmp    $0x2,%eax
 80483cd:       75 13                   jne    80483e2 <main+0x32>
 //             Here the a++ incrementation has been optimized by gcc
 80483cf:       b0 03                   mov    $0x3,%al
 //             Call printf()
 80483d1:       52                      push   %edx
 80483d2:       52                      push   %edx
 80483d3:       50                      push   %eax
 80483d4:       68 c8 84 04 08          push   $0x80484c8
 80483d9:       e8 f6 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483de:       31 c0                   xor    %eax,%eax
 80483e0:       c9                      leave
 80483e1:       c3                      ret

여기도 마지막 두 line 이 짤려져 있다. jne 로 jump 하게 되면 거기에 2 라는 값을 eax 에 넣어주고 printf 를 호출 하도록 하는 code일 것이다. 

위에서 보듯이 likely() 로 하면 대부분 2와 같을 것이라고 컴파일러에게 알려줘서 최대한 jmp instruction 이 수행되지 않게 될 것이다.

이렇게 개발자가 예측할 수 있는 부분에 대해 거의 대부분이 x와 같을 것이다 혹은 다를 것이다라는 것을 컴파일러에게 알려주는 방식으로 적용하여 program을 만들 수 있을 것이다.