[LWN.net] Shrinking the kernel with link-time garbage collection

Shrinking the kernel with link-time garbage collection [LWN.net]

Linker Section Garbage Collection

C언어로 작성된 프로그램은 전처리기 -> 컴파일러 -> 링커의 순서를 거쳐서 바이너리가 생성된다. 이때 링커는 사용되지 않는 코드를 제거해서 코드의 크기를 줄일 수 있다. 물론 동적 링크에서는 그걸 링커가 알 수는 없지만, 커널은 정적으로 링크가 된 바이너리 파일이므로 여기서는 정적 링크만 생각한다.

 

간단한 C 프로그램을 살펴보자.

   int foo(void)  { return 1; }

   int bar(void)  { return foo() + 2; }

   int main(void) { return foo() + 4; }

 

위의 코드는 ARM에서 대략 아래처럼 컴파일이 될 것이다.

        .text

        .type   foo, %function
    foo:
        mov     r0, #1
        bx      lr

        .type   bar, %function
    bar:
        push    {r3, lr}
        bl      foo
        adds    r0, r0, #2
        pop     {r3, pc}

        .type   main, %function
    main:
        push    {r3, lr}
        bl      foo
        adds    r0, r0, #4
        pop     {r3, pc}

 

코드에서 bar()를 호출하는 부분이 없는데도, 컴파일러는 컴파일 시점에서 그걸 판단할 수 없으므로 bar()의 코드가 바이너리에 포함된다. 하지만 링커는 링크를 하는 시점에서 어떤 함수가 실제로 호출되지 않는 다는걸 판단할 수 있다.

 

하지만 링커도 해당 파일 내의 섹션들 (.text, .data, ...)을 제외하고는 아는게 없다. 링커는 단지 현재 파일의 심볼을 다른 파일에서 참조하면 링크를 해줄 뿐이다. 그래서 bar()를 쉽게 제거할 수가 없다.

 

하지만 다행히도 GCC는 모든 함수를 각각의 파일로 컴파일하는 컴파일 옵션을 제공한다. (-ffunction-sections). 이 옵션으로 컴파일하면 아래 처럼 함수별로 별도의 섹션으로 코드를 생성한다.

        .section .text.foo,"ax",%progbits
        .type   foo, %function
    foo:
        mov     r0, #1
        bx      lr

        .section .text.bar,"ax",%progbits
        .type   bar, %function
    bar:
        push    {r3, lr}
        bl      foo
        adds    r0, r0, #2
        pop     {r3, pc}

        .section .text.main,"ax",%progbits
        .type   main, %function
    main:
        push    {r3, lr}
        bl      foo
        adds    r0, r0, #4
        pop     {r3, pc}

 

이제 섹션마다 하나의 함수가 들어있기 때문에, 참조되지 않는 섹션은 버릴 수 있다. gcc에서는 링커에 -gc-sections 옵션을 넘기면 참조되지 않는 섹션을 제거할 수 있다.

$ gcc -O2 -o test test.c
$ ./test
$ echo $?
5
$ nm test | grep "foo\|bar"
00008520 T bar
000084fc T foo

O2는 메모리와 속도를 포기하지 않는 선에서 최적화를 하는 옵션이다. 이외의 별다른 옵션을 넘기지 않았을 때는 bar()는 코드에 포함된다.

$ gcc -ffunction-sections \
>     -Wl,-gc-sections -Wl,-print-gc-sections \
>     -O2 -o test test.c
ld: Removing unused section '.text.bar' in file 'test.o'
$ ./test
$ echo $?
5
$ nm test | grep "foo\|bar"
000084fc T foo

 

하지만 링커에 -gc-sections 옵션을 넘기면 bar() 함수가 제거된 것을 확인할 수 있다. 위에서 -Wl은 링커에 옵션을 보내기 위한 gcc 옵션이다. 참고로 gcc에서는 코드 뿐만 아니라 전역 변수에 대해서도 비슷한 옵션을 제공한다. (-fdata-sections) 보통 -fdata-sections와 -ffunction-sections를 같이 사용한다.

 

그럼 커널을 -fdata-sections, -ffunction-sections로 빌드하면 될까? 아쉽게도 그렇게 간단하지 않다. 그렇게 하면 제대로 부팅이 되지 않는다.

The problem

문제는 exception table에 있다. ARM에서의 put_user() 구현을 살펴보자. put_user()는 커널 데이터를 사용자 공간으로 복사하는 함수이다.

    #define __put_user_asm_word(x, __pu_addr, err)              \
        __asm__ __volatile__(                                   \
        "1:     strt    %1, [%2]\n"                             \
        "2:\n"                                                  \
        "       .pushsection .text.fixup,\"ax\"\n"              \
        "       .align  2\n"                                    \
        "3:     mov     %0, %3\n"                               \
        "       b       2b\n"                                   \
        "       .popsection\n"                                  \
        "       .pushsection __ex_table,\"a\"\n"                \
        "       .align  3\n"                                    \
        "       .long   1b, 3b\n"                               \
        "       .popsection"                                    \
        : "+r" (err)                                            \
        : "r" (x), "r" (__pu_addr), "i" (-EFAULT)               \
        : "cc")

이때 strt 명령어는 권한을 체크한 후 사용자 공간으로 데이터를 복사하는 명령어다. put_user()는 strt 명령어 외에도 .text.fixup과 __ex_table 섹션을 추가한다. 실제 코드를 한번 살펴보자. foobar()는 사용자 주소 공간을 가리키는 포인터 p에 0x5a를 복사한다.

    int foobar(int __user *p)
    {
        return put_user(0x5a, p);
    }

 

이 함수는 아래와 같은 코드를 생성한다.

        .section .text.foobar,"ax"
    foobar:
        mov     r3, #0
        mov     r2, #0x5a
    1:  strt    r2, [r0]
    2:  mov     r0, r3
        bx      lr

        .section .text.fixup,"ax"
    3:  mov     r3, #-EFAULT
        b       2b

        .section __ex_table,"a"
        .long   1b, 3b

위 코드에서 put_user()는 exception을 발생시킨다. 이때 exception handling에서 __ex_table를 찾아서 예외를 처리한다. 여기서 문제점은 어디에서도 __ex_table에 대한 직접적인 레퍼런스를 갖고있지는 않는다는 점이다. 따라서 -gc-sections옵션을 넘기면 __ex_table은 바이너리에서 사라진다. 따라서 빌드가 끝난 이후의 결과물이 exception table이 존재하지 않는 커널이 되기 때문에 제대로 부팅이 되지 않는다.

 

    __ex_table {
	__start___ex_table = .;
	KEEP(*(__ex_table))
	__stop___ex_table = .;
    }

 

한 가지 방법은 KEEP() 매크로를 사용해서 __ex_table을 -gc-sections 옵션으로부터 보호하는 것이다. 지금까지 설명한 것을 리눅스에서는 v4.10부터 CONFIG_LD_DEAD_CODE_DATA_ELIMINATION라는 옵션으로 제공한다.

The "backward reference" problem

그런데 아직도 끝나지 않았다. -_-

       .section .text.foo1,"ax"
    foo1:
    	...
	mov     r3, #0
    1:  strt    ...
    2:  ...

        .section .text.foo2,"ax"
    foo2:
   	...
        mov     r3, #0
    3:  strt    ...
    4:  ...

        .section .text.foo3,"ax"
    foo3:
	...
        mov     r3, #0
    5:  strt    ...
    6:  ...

        .section .text.fixup,"ax"
    7:  mov     r3, #-EFAULT
        b       2b
    8:  mov     r3, #-EFAULT
        b       4b
    9:  mov     r3, #-EFAULT
        b       6b

        .section __ex_table,"a"
        .long   1b, 7b
        .long   3b, 8b
        .long   5b, 9b

 

여기서 문제는 __ex_table과 .text.fixup 섹션에서 예외를 발생할만한 위치에 대한 backward reference를 갖고있다는 점이다. 그럼 실제로 put_user()를 호출하는 함수를 호출하지 않더라도 __ex_table과 .text.fixup에서 참조를 함으로 -gc-sections에 의해 제거되지 않는다.

 

이 문제에 대한 해결 방법은 __ex_table과 .text.fixup의 섹션 이름에 함수가 존재하는 섹션의 이름을 포함시키는 것이다. 따라서 foobar의 섹션 이름이 .text.foobar라고 할때, 이에 대한 __ex_table 섹션의 이름을 _ex_table.text.foobar로, foobar에 대한 fixup 섹션의 이름을 .text.foobar.fixup로 정하면 함수별로 다른 __ex_table과 fixup 섹션이 생성되므로 사용되지 않는 섹션을 쉽게 -gc-sections로 제거할 수 있다.

    #define __put_user_asm_word(x, __pu_addr, err)              \
        __asm__ __volatile__(                                   \
        "1:     strt    %1, [%2]\n"                             \
        "2:\n"                                                  \
        "       .pushsection %S.fixup,\"ax\"\n"                 \
        "       .align  2\n"                                    \
        "3:     mov     %0, %3\n"                               \
        "       b       2b\n"                                   \
        "       .popsection\n"                                  \
        "       .pushsection __ex_table%S,\"a\"\n"              \
        "       .align  3\n"                                    \
        "       .long   1b, 3b\n"                               \
        "       .popsection"                                    \
        : "+r" (err)                                            \
        : "r" (x), "r" (__pu_addr), "i" (-EFAULT)               \
        : "cc")

The "missing forward reference" problem

근데 사실 함수별로 별도의 섹션을 만들어주면 처음 얘기했던 문제로 다시 돌아간다. 아까는 __ex_table을 KEEP() 매크로로 보호해주었는데, 이제는 섹션의 이름이 함수마다 다르므로 부팅이 되지 않는다. 이걸 해결하려면 __ex_table에 대한 명시적인 참조를 추가해줄 필요가 있다.

 

       .section .text.foobar,"ax"
    foobar:
        mov     r3, #0
        mov     r2, #0x5a
    1:  strt    r2, [r0]
        .reloc  ., R_ARM_NONE, 4f
    2:  mov     r0, r3
        bx      lr

        .section .fixup.text.foobar,"ax"
    3:   mov     r3, #-EFAULT
        b       2b

        .section __ex_table.text.foobar,"a"
    4:      .long   1b, 3b

 

.reloc  ., R_ARM_NONE, 4f는 ARM에서 별도의 코드를 추가하지 않고도 4 (__ex_table.text.foobar)에 대한 forward reference를 추가하도록 해준다. 이제 앞에서 말한 exception table으로 인한 부팅 문제, 호출하지 않는 함수의 backward reference로 인한 메모리 낭비 문제를 모두 해결했다!

 

여기까지 우리는 Linker Section Garbage Collection에 대해서 알아봤다. 구체적으로는 어떻게 사용되지 않는 함수를 -gc-sections, -fdata-sections, -ffunction-sections로 제거하는지를 알아봤다. 생각보다 옵션을 적용한다고 문제가 바로 해결되지는 않았고, 코드를 어느정도 수정해야했다. 최적화에 비해 너무 많은 노력이 들어갔다. 글에서는 절에서는 LTO를 사용해서 더 간단한 방법으로 사용되지 않는 코드를 제거하는 방법을 설명한다.