Reliable Stacktrace

도입: 라이브패치에 필요한 신뢰성

이 문서는 신뢰 가능한 stacktrace의 기본 요구사항을 설명합니다. 라이브패치 consistency model은 현재 실행 상태를 가진 함수, 즉 그 순간 교체하면 안전하지 않을 수 있는 함수를 정확히 식별해야 합니다. Stacktrace는 그런 live function을 찾는 한 가지 방법입니다.

기존 stacktrace 구현은 live state를 가진 모든 함수를 항상 정확하게 보여 주지는 않습니다. 디버깅에는 유용한 best-effort trace도 누락을 허용하므로 라이브패치의 안전 판정에는 사용할 수 없습니다.

따라서 각 architecture는 trace에서 live function을 절대로 누락하지 않는 reliable stacktrace를 제공해야 합니다. 완전성을 확신할 수 없는 경우에는 성공한 것처럼 불완전한 trace를 반환하지 말고 명시적으로 실패해야 합니다.

===================
Reliable Stacktrace
===================

This document outlines basic information about reliable stacktracing.

.. Table of Contents:

.. contents:: :local:

1. Introduction
===============

The kernel livepatch consistency model relies on accurately identifying which
functions may have live state and therefore may not be safe to patch. One way
to identify which functions are live is to use a stacktrace.

Existing stacktrace code may not always give an accurate picture of all
functions with live state, and best-effort approaches which can be helpful for
debugging are unsound for livepatching. Livepatching depends on architectures
to provide a *reliable* stacktrace which ensures it never omits any live
functions from a trace.

필수 구현과 반환 계약

Architecture는 신뢰 가능한 stacktrace 함수 중 하나를 구현해야 합니다. `CONFIG_ARCH_STACKWALK`를 사용하는 architecture는 `arch_stack_walk_reliable()`을, 그렇지 않은 architecture는 `save_stack_trace_tsk_reliable()`을 구현합니다.

핵심 계약은 둘 중 하나입니다. Trace가 task가 복귀할 수 있는 모든 함수를 포함하면 신뢰 가능함을 나타내는 0을 반환하고, 그 조건을 보장할 수 없으면 0이 아닌 값을 반환해야 합니다.

특정 함수의 생략이 정당한 예외도 있지만, 이 문서가 뒤에서 명시하는 경우에 한정됩니다. 그 밖의 모든 복귀 가능 함수는 반드시 보고해야 합니다.

또한 stack이나 다른 unwind state가 손상되었거나 신뢰할 수 없는 상황에도 견고해야 합니다. 이런 상태를 가능한 한 탐지해 0이 아닌 오류를 반환해야 하며, 무한 loop에 빠지거나 안전하지 않은 memory에 접근해서는 안 됩니다.

2. Requirements
===============

Architectures must implement one of the reliable stacktrace functions.
Architectures using CONFIG_ARCH_STACKWALK must implement
'arch_stack_walk_reliable', and other architectures must implement
'save_stack_trace_tsk_reliable'.

Principally, the reliable stacktrace function must ensure that either:

* The trace includes all functions that the task may be returned to, and the
  return code is zero to indicate that the trace is reliable.

* The return code is non-zero to indicate that the trace is not reliable.

.. note::
   In some cases it is legitimate to omit specific functions from the trace,
   but all other functions must be reported. These cases are described in
   further detail below.

Secondly, the reliable stacktrace function must be robust to cases where
the stack or other unwind state is corrupt or otherwise unreliable. The
function should attempt to detect such cases and return a non-zero error
code, and should not get stuck in an infinite loop or access memory in
an unsafe way.  Specific cases are described in further detail below.

컴파일 시점 분석

모든 kernel code를 올바르게 unwind하려면 compiler가 unwinder의 예상 규칙을 따랐는지 architecture가 검증해야 할 수 있습니다. 예를 들어 stack pointer를 제한된 방식으로만 변경하거나, 모든 함수가 특정 prologue와 epilogue 순서를 사용해야 할 수 있습니다.

이런 제약이 있는 architecture는 `objtool`로 kernel compilation 결과를 검증해야 합니다. 소스의 의도만 보는 것이 아니라 실제 생성된 code가 unwinder의 가정을 만족하는지 확인하는 단계입니다.

Unwinder가 정확한 복원을 위해 metadata를 요구한다면 그 정보도 build 때 `objtool`로 생성해야 합니다. 런타임 추측 대신 검증된 metadata를 사용하면 함수 중간이나 예외 경계의 상태를 더 안전하게 판별할 수 있습니다.

3. Compile-time analysis
========================

To ensure that kernel code can be correctly unwound in all cases,
architectures may need to verify that code has been compiled in a manner
expected by the unwinder. For example, an unwinder may expect that
functions manipulate the stack pointer in a limited way, or that all
functions use specific prologue and epilogue sequences. Architectures
with such requirements should verify the kernel compilation using
objtool.

In some cases, an unwinder may require metadata to correctly unwind.
Where necessary, this metadata should be generated at build time using
objtool.

고려사항과 성공 종료 식별

Unwind 과정은 architecture의 procedure call standard와 kernel configuration에 따라 달라집니다. 공통적으로 stack 또는 frame pointer 손상, 드문 상황의 unwind 지원 누락이나 unwinder bug, eBPF 같은 동적 code 또는 EFI runtime service 같은 외부 code 때문에 예상보다 일찍 끝날 수 있습니다.

다른 검사에서 조기 종료를 잡지 못하더라도 함수 누락을 방지하려면 trace가 예상 위치에서 끝났는지 검증하는 것이 강하게 권장됩니다.

예상 종료점은 kernel 진입점인 특정 함수 내부, kernel entry point에 대응하는 stack의 특정 위치, 또는 architecture가 task stack과 IRQ stack을 나누는 경우처럼 진입점에 대응하는 특정 stack일 수 있습니다.

4. Considerations
=================

The unwinding process varies across architectures, their respective procedure
call standards, and kernel configurations. This section describes common
details that architectures should consider.

4.1 Identifying successful termination
--------------------------------------

Unwinding may terminate early for a number of reasons, including:

* Stack or frame pointer corruption.

* Missing unwind support for an uncommon scenario, or a bug in the unwinder.

* Dynamically generated code (e.g. eBPF) or foreign code (e.g. EFI runtime
  services) not following the conventions expected by the unwinder.

To ensure that this does not result in functions being omitted from the trace,
even if not caught by other checks, it is strongly recommended that
architectures verify that a stacktrace ends at an expected location, e.g.

* Within a specific function that is an entry point to the kernel.

* At a specific location on a stack expected for a kernel entry point.

* On a specific stack expected for a kernel entry point (e.g. if the
  architecture has separate task and IRQ stacks).

Unwind 가능한 code 식별

Unwinding은 보통 frame pointer 조작 같은 정해진 convention을 code가 따른다고 가정합니다. Exception vector와 entry assembly, PLT entry와 veneer function, ftrace·kprobes trampoline assembly, eBPF·optprobe trampoline처럼 동적으로 생성된 code, EFI runtime service 같은 외부 code는 이 규칙을 따르지 않거나 별도 처리가 필요할 수 있습니다.

이런 code 때문에 함수가 trace에서 누락되지 않도록 architecture는 unwind가 신뢰 가능하다고 알려진 code를 적극적으로 식별하고, 그 밖의 code에서 시작하는 unwind는 거부하는 방식이 권장됩니다.

`__kernel_text_address()`를 사용하면 module과 eBPF를 포함한 kernel code를 외부 code와 구별할 수 있습니다. 이 검사는 잘못된 return address가 kernel text 밖을 가리키는 stack 손상도 찾아내는 데 도움이 됩니다.

Architecture는 신뢰할 수 없는 code를 특별한 linker section에 배치해 그 범위에서의 unwind를 거부하거나, bounds information으로 특정 code 구간을 식별할 수 있습니다.

4.2 Identifying unwindable code
-------------------------------

Unwinding typically relies on code following specific conventions (e.g.
manipulating a frame pointer), but there can be code which may not follow these
conventions and may require special handling in the unwinder, e.g.

* Exception vectors and entry assembly.

* Procedure Linkage Table (PLT) entries and veneer functions.

* Trampoline assembly (e.g. ftrace, kprobes).

* Dynamically generated code (e.g. eBPF, optprobe trampolines).

* Foreign code (e.g. EFI runtime services).

To ensure that such cases do not result in functions being omitted from a
trace, it is strongly recommended that architectures positively identify code
which is known to be reliable to unwind from, and reject unwinding from all
other code.

Kernel code including modules and eBPF can be distinguished from foreign code
using '__kernel_text_address()'. Checking for this also helps to detect stack
corruption.

There are several ways an architecture may identify kernel code which is deemed
unreliable to unwind from, e.g.

* Placing such code into special linker sections, and rejecting unwinding from
  any code in these sections.

* Identifying specific portions of code using bounds information.

Interrupt와 exception 경계 넘기

함수 호출 경계에서는 stack과 unwind state가 일관된 상태일 것으로 기대할 수 있지만, 함수 실행 중간에는 그렇지 않을 수 있습니다. Prologue나 epilogue 도중에는 frame pointer가 일시적으로 무효할 수 있고, 함수 본문에서는 return address가 임의의 general-purpose register에 들어 있을 수 있습니다. Dynamic instrumentation 때문에 이 상태가 런타임에 바뀌기도 합니다.

Stack이나 unwind state가 불일치한 순간 interrupt 또는 다른 exception이 발생하면 reliable unwind가 불가능할 수 있으며, 그 결과가 신뢰 가능한지조차 판별하기 어려울 수 있습니다.

이 경우의 신뢰성을 식별할 수 없거나 항상 신뢰할 수 없는 architecture는 exception boundary를 넘는 unwind를 거부해야 합니다. IRQ는 안전하지만 NMI는 안전하지 않은 것처럼 exception 종류별 판단이 달라질 수 있습니다.

반대로 신뢰 가능한 시점을 식별할 수 있거나 이런 문제가 없는 architecture는 exception boundary를 넘어 unwind를 시도해야 합니다. 그러면 라이브패치 consistency check가 불필요하게 멈추는 일을 줄이고 transition을 더 빨리 완료할 수 있습니다.

4.3 Unwinding across interrupts and exceptions
----------------------------------------------

At function call boundaries the stack and other unwind state is expected to be
in a consistent state suitable for reliable unwinding, but this may not be the
case part-way through a function. For example, during a function prologue or
epilogue a frame pointer may be transiently invalid, or during the function
body the return address may be held in an arbitrary general purpose register.
For some architectures this may change at runtime as a result of dynamic
instrumentation.

If an interrupt or other exception is taken while the stack or other unwind
state is in an inconsistent state, it may not be possible to reliably unwind,
and it may not be possible to identify whether such unwinding will be reliable.
See below for examples.

Architectures which cannot identify when it is reliable to unwind such cases
(or where it is never reliable) must reject unwinding across exception
boundaries. Note that it may be reliable to unwind across certain
exceptions (e.g. IRQ) but unreliable to unwind across other exceptions
(e.g. NMI).

Architectures which can identify when it is reliable to unwind such cases (or
have no such cases) should attempt to unwind across exception boundaries, as
doing so can prevent unnecessarily stalling livepatch consistency checks and
permits livepatch transitions to complete more quickly.

Return address 재기록

일부 trampoline은 함수가 반환할 때 개입하기 위해 return address를 임시로 바꿉니다. Function graph tracing의 ftrace trampoline과 kretprobe를 위한 kprobes 또는 optprobes trampoline이 대표적입니다.

이때 원래 return address는 평소 위치에 없습니다. 라이브패치 대상이 아닌 trampoline에서 unwinder가 원래 주소를 확실하게 결정할 수 있고 다른 unwind state도 변경되지 않았다면 trampoline 대신 원래 return address를 보고하면서 trace를 신뢰 가능으로 처리할 수 있습니다. 그렇지 않으면 반드시 unreliable로 보고해야 합니다.

원래 return address의 위치는 entry trampoline과 return trampoline의 전체 실행 동안 일정하지 않으므로 특별한 주의가 필요합니다. x86_64의 `return_to_handler`가 그 예입니다.

추적 중인 함수가 실행되는 동안 stack의 return address는 `return_to_handler` 시작점을 가리키고, 원래 주소는 task의 `cur_ret_stack`에 저장됩니다. 이 구간에서는 `ftrace_graph_ret_addr()`로 원래 주소를 찾을 수 있습니다.

추적 함수가 `return_to_handler`로 반환한 뒤에는 stack에 return address가 더 이상 없습니다. 원래 주소는 잠시 `cur_ret_stack`에 남아 있지만, `ftrace_return_to_handler()`가 이를 꺼낸 뒤 compiler가 임의 위치로 옮겼다가 `rax`로 반환합니다. Trampoline은 값을 `rdi`로 옮긴 다음 그 주소로 jump합니다.

따라서 `ftrace_return_to_handler()`가 `cur_ret_stack`에서 주소를 제거한 뒤처럼 원래 주소의 위치를 확실히 알 수 없는 구간은 unwind하지 못할 수 있습니다.

Architecture는 아직 `return_to_handler`로 복귀하기 전 상태는 unwind하는 것이 권장됩니다. 하지만 `return_to_handler` 한가운데나 return address를 바꾸는 다른 trampoline 내부를 반드시 unwind할 의무는 없으며, 이 구간을 unreliable로 보고해도 됩니다.

4.4 Rewriting of return addresses
---------------------------------

Some trampolines temporarily modify the return address of a function in order
to intercept when that function returns with a return trampoline, e.g.

* An ftrace trampoline may modify the return address so that function graph
  tracing can intercept returns.

* A kprobes (or optprobes) trampoline may modify the return address so that
  kretprobes can intercept returns.

When this happens, the original return address will not be in its usual
location. For trampolines which are not subject to live patching, where an
unwinder can reliably determine the original return address and no unwind state
is altered by the trampoline, the unwinder may report the original return
address in place of the trampoline and report this as reliable. Otherwise, an
unwinder must report these cases as unreliable.

Special care is required when identifying the original return address, as this
information is not in a consistent location for the duration of the entry
trampoline or return trampoline. For example, considering the x86_64
'return_to_handler' return trampoline:

.. code-block:: none

   SYM_CODE_START(return_to_handler)
           UNWIND_HINT_UNDEFINED
           subq  $24, %rsp

           /* Save the return values */
           movq %rax, (%rsp)
           movq %rdx, 8(%rsp)
           movq %rbp, %rdi

           call ftrace_return_to_handler

           movq %rax, %rdi
           movq 8(%rsp), %rdx
           movq (%rsp), %rax
           addq $24, %rsp
           JMP_NOSPEC rdi
   SYM_CODE_END(return_to_handler)

While the traced function runs its return address on the stack points to
the start of return_to_handler, and the original return address is stored in
the task's cur_ret_stack. During this time the unwinder can find the return
address using ftrace_graph_ret_addr().

When the traced function returns to return_to_handler, there is no longer a
return address on the stack, though the original return address is still stored
in the task's cur_ret_stack. Within ftrace_return_to_handler(), the original
return address is removed from cur_ret_stack and is transiently moved
arbitrarily by the compiler before being returned in rax. The return_to_handler
trampoline moves this into rdi before jumping to it.

Architectures might not always be able to unwind such sequences, such as when
ftrace_return_to_handler() has removed the address from cur_ret_stack, and the
location of the return address cannot be reliably determined.

It is recommended that architectures unwind cases where return_to_handler has
not yet been returned to, but architectures are not required to unwind from the
middle of return_to_handler and can report this as unreliable. Architectures
are not required to unwind from other trampolines which modify the return
address.

Return address 가림

일부 trampoline은 반환을 가로채려고 return address를 다시 쓰지는 않지만, 실행 도중 return address 또는 다른 unwind state를 일시적으로 덮어씁니다.

x86_64 optprobes는 probe 대상 함수에 연관된 optprobe trampoline으로 가는 `JMP` instruction을 삽입합니다. Probe가 실행되면 CPU가 trampoline으로 branch하지만 대상 함수 주소는 register에도 stack에도 남아 있지 않습니다.

arm64의 `DYNAMIC_FTRACE_WITH_REGS`는 `MOV X9, X30`으로 link register `X30`의 return address를 `X9`에 보존한 다음 `BL <trampoline>`을 수행합니다. `BL`이 link register를 덮어쓰므로 trampoline 시작점에서 추적 함수 주소는 일반적인 link register가 아니라 `X9`에 있습니다.

Architecture는 unwinder가 이런 경우를 확실하게 복원하도록 구현하거나, 복원을 보장할 수 없다면 해당 unwind를 unreliable로 보고해야 합니다.

4.5 Obscuring of return addresses
---------------------------------

Some trampolines do not rewrite the return address in order to intercept
returns, but do transiently clobber the return address or other unwind state.

For example, the x86_64 implementation of optprobes patches the probed function
with a JMP instruction which targets the associated optprobe trampoline. When
the probe is hit, the CPU will branch to the optprobe trampoline, and the
address of the probed function is not held in any register or on the stack.

Similarly, the arm64 implementation of DYNAMIC_FTRACE_WITH_REGS patches traced
functions with the following:

.. code-block:: none

   MOV X9, X30
   BL <trampoline>

The MOV saves the link register (X30) into X9 to preserve the return address
before the BL clobbers the link register and branches to the trampoline. At the
start of the trampoline, the address of the traced function is in X9 rather
than the link register as would usually be the case.

Architectures must either ensure that unwinders either reliably unwind
such cases, or report the unwinding as unreliable.

Link register의 비신뢰성

일부 architecture에서 call instruction은 return address를 link register에 넣고, return instruction은 register 값을 소비하지만 register 자체를 바꾸지는 않습니다. Software는 다른 함수를 호출하기 전에 이 주소를 stack에 저장해야 하므로 함수 실행 중 return address가 link register에만, stack에만, 또는 양쪽 모두에 있을 수 있습니다.

Unwinder가 link register가 항상 live라고 가정하면 잘못된 stacktrace가 나올 수 있습니다. Arm64의 단순 함수 예에서 진입 직후 `X30`은 caller를 가리키고 `X29`는 caller frame을 가리킵니다. `STP X29, X30, [SP, -16]!`와 `MOV X29, SP`가 새 frame을 만든 뒤에는 link register와 frame pointer가 모두 같은 함수의 return address를 설명합니다.

이 순간 trace를 만들면 함수가 두 번 나타날 수 있습니다. Function return tracing 중이라면 unwinder가 fgraph return stack에서 하나가 아니라 두 entry를 소비하는 오류로 이어질 수 있습니다.

`BL <other_function>`은 link register가 현재 함수의 `LDR` 위치를, frame pointer가 현재 함수의 stack frame을 가리키게 한 채 다른 함수를 호출합니다. `other_function`이 반환해도 link register는 `BL`을 가리킨 채 남으므로, 이 시점의 trace에서도 현재 함수가 두 번 나타날 수 있습니다.

함수가 의도적으로 LR을 덮어쓰는 경우도 있습니다. 예시의 `ADR LR, <callee>`는 `BLR LR` 전에 callee 주소를 LR에 넣습니다. `ADR` 직후 trace를 만들면 실제로는 caller의 자식인 `callee`가 caller의 부모처럼 잘못 보입니다.

이런 사례 때문에 link register 값은 함수 호출 경계에서만 신뢰 가능할 수 있습니다. 해당 제약이 있는 architecture는 `objtool`이 생성한 metadata 등으로 LR 값과 stack 값 중 무엇을 사용해야 하는지 확실히 식별할 수 없는 한 exception boundary를 넘는 unwind를 거부해야 합니다.

4.6 Link register unreliability
-------------------------------

On some other architectures, 'call' instructions place the return address into a
link register, and 'return' instructions consume the return address from the
link register without modifying the register. On these architectures software
must save the return address to the stack prior to making a function call. Over
the duration of a function call, the return address may be held in the link
register alone, on the stack alone, or in both locations.

Unwinders typically assume the link register is always live, but this
assumption can lead to unreliable stack traces. For example, consider the
following arm64 assembly for a simple function:

.. code-block:: none

   function:
           STP X29, X30, [SP, -16]!
           MOV X29, SP
           BL <other_function>
           LDP X29, X30, [SP], #16
           RET

At entry to the function, the link register (x30) points to the caller, and the
frame pointer (X29) points to the caller's frame including the caller's return
address. The first two instructions create a new stackframe and update the
frame pointer, and at this point the link register and the frame pointer both
describe this function's return address. A trace at this point may describe
this function twice, and if the function return is being traced, the unwinder
may consume two entries from the fgraph return stack rather than one entry.

The BL invokes 'other_function' with the link register pointing to this
function's LDR and the frame pointer pointing to this function's stackframe.
When 'other_function' returns, the link register is left pointing at the BL,
and so a trace at this point could result in 'function' appearing twice in the
backtrace.

Similarly, a function may deliberately clobber the LR, e.g.

.. code-block:: none

   caller:
           STP X29, X30, [SP, -16]!
           MOV X29, SP
           ADR LR, <callee>
           BLR LR
           LDP X29, X30, [SP], #16
           RET

The ADR places the address of 'callee' into the LR, before the BLR branches to
this address. If a trace is made immediately after the ADR, 'callee' will
appear to be the parent of 'caller', rather than the child.

Due to cases such as the above, it may only be possible to reliably consume a
link register value at a function call boundary. Architectures where this is
the case must reject unwinding across exception boundaries unless they can
reliably identify when the LR or stack value should be used (e.g. using
metadata generated by objtool).