Kernel level exception handling

user address 검증 비용과 hardware fault

이 `GPL-2.0` 문서는 kernel-level exception handling을 설명하며 Joerg Pommnitz `<joerg@raleigh.ibm.com>`가 해설했습니다. kernel mode process는 untrusted program이 넘긴 user-mode memory address에 자주 접근하므로 kernel 자신을 보호하기 위해 address를 검증해야 합니다.

오래된 Linux는 이후 `access_ok()`로 대체된 `int verify_area(int type, const void * addr, unsigned long size)`를 사용했습니다. `addr`에서 시작해 `size`만큼인 area가 `type`의 read/write operation에 접근 가능한지 확인했습니다.

`verify_read`는 address를 포함하는 virtual memory area(VMA)를 lookup해야 했습니다. 정상 program에서는 거의 항상 성공하고 일부 buggy program에서만 실패했지만, profiling에서는 보통 불필요한 이 검증이 상당한 시간을 소비했습니다.

이를 해결하기 위해 Linus는 Linux-capable CPU마다 있는 virtual-memory hardware가 검사를 담당하게 했습니다.

exc_page_fault와 fixup address

kernel이 현재 접근할 수 없는 address를 access하면 CPU는 page-fault exception을 만들고 `arch/x86/mm/fault.c`의 page-fault handler를 호출합니다.

void exc_page_fault(struct pt_regs *regs, unsigned long error_code)

stack parameter는 `arch/x86/entry/entry_32.S`의 low-level assembly glue가 준비합니다. `regs`는 stack에 저장한 register를 가리키고 `error_code`는 exception reason code를 담습니다.

`exc_page_fault()`는 먼저 CPU control register `CR2`에서 inaccessible address를 얻습니다. process virtual-address space 안이라면 page가 swap-in되지 않았거나 write-protected인 상황일 수 있습니다. 이 문서가 다루는 경우는 해당 address를 포함하는 VMA가 없어 invalid인 경우이며 kernel은 `bad_area` label로 갑니다.

`bad_area`에서는 exception을 일으킨 instruction address `regs->eip`로 execution을 계속할 fixup address를 찾습니다. search가 성공하면 fault handler가 return address인 `regs->eip`를 fixup으로 바꾸고 return하므로 execution은 fixup code에서 계속됩니다.

fixup은 executable code를 가리키며 user-access macro 안에 숨겨져 있습니다. 문서는 `arch/x86/include/asm/uaccess.h`의 `get_user()`와 `drivers/char/sysrq.c` line 587의 call을 예로 분석합니다.

get_user()가 생성한 inline assembly

원래 `sysrq.c` code는 다음 한 줄입니다.

get_user(c, buf);

preprocessor와 compiler를 거치면 읽기 좋게 편집해도 다음처럼 복잡한 code가 됩니다. `__gu_err`는 기본 `-14`(`-EFAULT`), `__gu_val`은 0이며 address 범위를 확인한 뒤 object size 1, 2, 4 byte에 맞는 inline assembly를 선택합니다.

(
  {
    long __gu_err = - 14 , __gu_val = 0;
    const __typeof__(*( (  buf ) )) *__gu_addr = ((buf));
    if (((((0 + current_set[0])->tss.segment) == 0x18 )  ||
      (((sizeof(*(buf))) <= 0xC0000000UL) &&
      ((unsigned long)(__gu_addr ) <= 0xC0000000UL - (sizeof(*(buf)))))))
      do {
        __gu_err  = 0;
        switch ((sizeof(*(buf)))) {
          case 1:
            __asm__ __volatile__(
              "1:      mov" "b" " %2,%" "b" "1\n"
              "2:\n"
              ".section .fixup,\"ax\"\n"
              "3:      movl %3,%0\n"
              "        xor" "b" " %" "b" "1,%" "b" "1\n"
              "        jmp 2b\n"
              ".section __ex_table,\"a\"\n"
              "        .align 4\n"
              "        .long 1b,3b\n"
              ".text"        : "=r"(__gu_err), "=q" (__gu_val): "m"((*(struct __large_struct *)
                            (   __gu_addr   )) ), "i"(- 14 ), "0"(  __gu_err  )) ;
              break;
          case 2:
            __asm__ __volatile__(
              "1:      mov" "w" " %2,%" "w" "1\n"
              "2:\n"
              ".section .fixup,\"ax\"\n"
              "3:      movl %3,%0\n"
              "        xor" "w" " %" "w" "1,%" "w" "1\n"
              "        jmp 2b\n"
              ".section __ex_table,\"a\"\n"
              "        .align 4\n"
              "        .long 1b,3b\n"
              ".text"        : "=r"(__gu_err), "=r" (__gu_val) : "m"((*(struct __large_struct *)
                            (   __gu_addr   )) ), "i"(- 14 ), "0"(  __gu_err  ));
              break;
          case 4:
            __asm__ __volatile__(
              "1:      mov" "l" " %2,%" "" "1\n"
              "2:\n"
              ".section .fixup,\"ax\"\n"
              "3:      movl %3,%0\n"
              "        xor" "l" " %" "" "1,%" "" "1\n"
              "        jmp 2b\n"
              ".section __ex_table,\"a\"\n"
              "        .align 4\n"        "        .long 1b,3b\n"
              ".text"        : "=r"(__gu_err), "=r" (__gu_val) : "m"((*(struct __large_struct *)
                            (   __gu_addr   )) ), "i"(- 14 ), "0"(__gu_err));
              break;
          default:
            (__gu_val) = __get_user_bad();
        }
      } while (0) ;
    ((c)) = (__typeof__(*((buf))))__gu_val;
    __gu_err;
  }
);

각 size case는 label `1`에서 실제 user access를 하고 label `2`가 normal continuation입니다. `.fixup` section의 label `3`은 error를 `-14`로 설정하고 read value를 0으로 만든 뒤 `2b`로 jump합니다. `__ex_table`에는 faulting label `1b`와 handler label `3b` pair를 기록합니다. 지원하지 않는 size는 `__get_user_bad()`로 갑니다.

optimizer가 만든 normal path

GCC optimizer는 복잡한 macro를 다음처럼 이해 가능한 assembly로 줄입니다. 실제 user access는 `movb (%ebx),%dl`입니다.

>         xorl %edx,%edx
>         movl current_set,%eax
>         cmpl $24,788(%eax)
>         je .L1424
>         cmpl $-1073741825,64(%esp)
>         ja .L1423
> .L1424:
>         movl %edx,%eax
>         movl 64(%esp),%ebx
> #APP
> 1:      movb (%ebx),%dl                /* this is the actual user access */
> 2:
> .section .fixup,"ax"
> 3:      movl $-14,%eax
>         xorb %dl,%dl
>         jmp 2b
> .section __ex_table,"a"
>         .align 4
>         .long 1b,3b
> .text
> #NO_APP
> .L1423:
>         movzbl %dl,%esi

unified address space 덕분에 user-memory address를 직접 access할 수 있습니다. normal path는 짧지만 `.section` directive 사이 code가 어떤 역할을 하는지는 final kernel ELF를 살펴봐야 알 수 있습니다.

vmlinux의 .fixup과 __ex_table

먼저 `vmlinux` section header를 확인합니다.

> objdump --section-headers vmlinux
>
> vmlinux:     file format elf32-i386
>
> Sections:
> Idx Name          Size      VMA       LMA       File off  Algn
>   0 .text         00098f40  c0100000  c0100000  00001000  2**4
>                   CONTENTS, ALLOC, LOAD, READONLY, CODE
>   1 .fixup        000016bc  c0198f40  c0198f40  00099f40  2**0
>                   CONTENTS, ALLOC, LOAD, READONLY, CODE
>   2 .rodata       0000f127  c019a5fc  c019a5fc  0009b5fc  2**2
>                   CONTENTS, ALLOC, LOAD, READONLY, DATA
>   3 __ex_table    000015c0  c01a9724  c01a9724  000aa724  2**2
>                   CONTENTS, ALLOC, LOAD, READONLY, DATA
>   4 .data         0000ea58  c01abcf0  c01abcf0  000abcf0  2**4
>                   CONTENTS, ALLOC, LOAD, DATA
>   5 .bss          00018e21  c01ba748  c01ba748  000ba748  2**2
>                   ALLOC
>   6 .comment      00000ec4  00000000  00000000  000ba748  2**0
>                   CONTENTS, READONLY
>   7 .note         00001068  00000ec4  00000ec4  000bb60c  2**0
>                   CONTENTS, READONLY

generated object에는 standard section 외에 executable `.fixup`과 read-only data `__ex_table` 두 section이 있습니다. normal `.text`에서 example user access가 어떻게 link됐는지 disassemble하면 다음과 같습니다.

> objdump --disassemble --section=.text vmlinux
>
> c017e785 <do_con_write+c1> xorl   %edx,%edx
> c017e787 <do_con_write+c3> movl   0xc01c7bec,%eax
> c017e78c <do_con_write+c8> cmpl   $0x18,0x314(%eax)
> c017e793 <do_con_write+cf> je     c017e79f <do_con_write+db>
> c017e795 <do_con_write+d1> cmpl   $0xbfffffff,0x40(%esp,1)
> c017e79d <do_con_write+d9> ja     c017e7a7 <do_con_write+e3>
> c017e79f <do_con_write+db> movl   %edx,%eax
> c017e7a1 <do_con_write+dd> movl   0x40(%esp,1),%ebx
> c017e7a5 <do_con_write+e1> movb   (%ebx),%dl
> c017e7a7 <do_con_write+e3> movzbl %dl,%esi

user-memory access 전체는 x86 instruction 10개로 줄었습니다. `.section` directive 안 instruction은 normal execution path에서 빠져 executable의 별도 `.fixup` section에 놓입니다.

> objdump --disassemble --section=.fixup vmlinux
>
> c0199ff5 <.fixup+10b5> movl   $0xfffffff2,%eax
> c0199ffa <.fixup+10ba> xorb   %dl,%dl
> c0199ffc <.fixup+10bc> jmp    c017e7a7 <do_con_write+e3>

마지막으로 `__ex_table`의 raw content는 다음과 같습니다.

 > objdump --full-contents --section=__ex_table vmlinux
 >
 >  c01aa7c4 93c017c0 e09f19c0 97c017c0 99c017c0  ................
 >  c01aa7d4 f6c217c0 e99f19c0 a5e717c0 f59f19c0  ................
 >  c01aa7e4 080a18c0 01a019c0 0a0a18c0 04a019c0  ................

or in human readable byte order::

 >  c01aa7c4 c017c093 c0199fe0 c017c097 c017c099  ................
 >  c01aa7d4 c017c2f6 c0199fe9 c017e7a5 c0199ff5  ................
                               ^^^^^^^^^^^^^^^^^
                               this is the interesting part!
 >  c01aa7e4 c0180a08 c019a001 c0180a0a c019a004  ................

human-readable byte order에서 흥미로운 pair는 faulting instruction `c017e7a5`와 fixup `c0199ff5`입니다.

local label과 exception-table pair

다음 assembly directive가 뒤따르는 code를 지정 ELF section으로 옮깁니다.

.section .fixup,"ax"
.section __ex_table,"a"

그래서 다음 handler instruction은 `.fixup` section에 들어갑니다.

3:      movl $-14,%eax
        xorb %dl,%dl
        jmp 2b

다음 address pair는 `__ex_table` section에 들어갑니다.

.long 1b,3b

`1b`와 `3b`는 local label입니다. `1b`는 뒤쪽(backward)의 다음 label 1, 즉 fault 가능 instruction address `c017e7a5`를 뜻합니다. source와 linked `vmlinux` 표현은 다음과 같습니다.

the original assembly code: > 1:      movb (%ebx),%dl
and linked in vmlinux     : > c017e7a5 <do_con_write+e1> movb   (%ebx),%dl

local label `3b`는 fault handler code address이며 실제 값은 `c0199ff5`입니다.

the original assembly code: > 3:      movl $-14,%eax
and linked in vmlinux     : > c0199ff5 <.fixup+10b5> movl   $0xfffffff2,%eax

fixup이 exception을 처리하면 faulting instruction 직후인 local label `2b`로 control flow를 돌려줄 수 있습니다. `__ex_table` directive와 그 결과 pair는 다음과 같습니다.

 > .section __ex_table,"a"
 >         .align 4
 >         .long 1b,3b

becomes the value pair::

 >  c01aa7d4 c017c2f6 c0199fe9 c017e7a5 c0199ff5  ................
                               ^this is ^this is
                               1b       3b

따라서 kernel exception table에는 `c017e7a5,c0199ff5` pair가 저장됩니다.

invalid access에서 -EFAULT 복구까지

적합한 VMA가 없는 kernel-mode fault의 실제 순서는 다음과 같습니다.

마지막 값 변경과 jump는 faulting instruction을 일정한 방식으로 emulate합니다. `get_user()`는 성공하면 0, 실패하면 `-EFAULT`를 반환하므로 handler가 EAX를 `-EFAULT`로 설정합니다. original caller가 return value를 검사하지 않더라도 inline assembly는 값을 반환하며 GCC가 EAX를 선택했습니다.

64-bit relative offset와 handler field

x86 Linux에 64-bit support를 추가할 때 두 entry를 32 bit에서 64 bit로 늘려 exception-table size를 두 배로 만들지 않았습니다. 대신 table 자신을 기준으로 한 relative offset을 저장합니다.

  .long 1b,3b
to:
        .long (from) - .
        .long (to) - .

C code는 relative value를 다음처럼 absolute address로 되돌립니다.

ex_insn_addr(const struct exception_table_entry *x)
{
        return (unsigned long)&x->insn + x->insn;
}

v4.6에서는 exception-table entry에 32-bit `handler` field를 추가했습니다. 이는 세 번째 relative function pointer이며 현재 다음 handler 중 하나를 가리킵니다.

• `int ex_handler_default(const struct exception_table_entry *fixup)`: fixup code로 jump하는 legacy case입니다.
• `int ex_handler_fault(const struct exception_table_entry *fixup)`: `entry->insn`에서 발생한 trap의 fault number를 제공해 page fault와 machine check를 구별합니다.

필요하면 handler function을 더 추가할 수 있습니다.

build-time sort와 binary search

`CONFIG_BUILDTIME_TABLE_SORT`는 kernel image link 뒤 host utility `scripts/sorttable`로 `__ex_table` section을 정렬합니다. 이 utility는 `main_extable_sort_needed` symbol을 0으로 설정해 boot-time sort를 피합니다.

정렬된 exception table은 runtime exception에서 binary search로 entry를 빠르게 찾게 합니다. 이는 단순한 boot-time optimization만이 아닙니다. 일부 architecture는 boot 초기 exception 처리를 위해 sorted table이 필요합니다. 예를 들어 i386은 paging support를 enable하기 전부터 이 exception handling 형식을 사용합니다.