요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0
============
ORC unwinder
============
Overview
========
The kernel CONFIG_UNWINDER_ORC option enables the ORC unwinder, which is
similar in concept to a DWARF unwinder. The difference is that the
format of the ORC data is much simpler than DWARF, which in turn allows
the ORC unwinder to be much simpler and faster.
The ORC data consists of unwind tables which are generated by objtool.
They contain out-of-band data which is used by the in-kernel ORC
unwinder. Objtool generates the ORC data by first doing compile-time
stack metadata validation (CONFIG_STACK_VALIDATION). After analyzing
all the code paths of a .o file, it determines information about the
stack state at each instruction address in the file and outputs that
information to the .orc_unwind and .orc_unwind_ip sections.
The per-object ORC sections are combined at link time and are sorted and
post-processed at boot time. The unwinder uses the resulting data to
correlate instruction addresses with their stack states at run time.
ORC vs frame pointers
=====================
With frame pointers enabled, GCC adds instrumentation code to every
function in the kernel. The kernel's .text size increases by about
3.2%, resulting in a broad kernel-wide slowdown. Measurements by Mel
Gorman [1]_ have shown a slowdown of 5-10% for some workloads.
In contrast, the ORC unwinder has no effect on text size or runtime
performance, because the debuginfo is out of band. So if you disable
frame pointers and enable the ORC unwinder, you get a nice performance
improvement across the board, and still have reliable stack traces.
Ingo Molnar says:
"Note that it's not just a performance improvement, but also an
instruction cache locality improvement: 3.2% .text savings almost
directly transform into a similarly sized reduction in cache
footprint. That can transform to even higher speedups for workloads
whose cache locality is borderline."
Another benefit of ORC compared to frame pointers is that it can
reliably unwind across interrupts and exceptions. Frame pointer based
unwinds can sometimes skip the caller of the interrupted function, if it
was a leaf function or if the interrupt hit before the frame pointer was
saved.
The main disadvantage of the ORC unwinder compared to frame pointers is
that it needs more memory to store the ORC unwind tables: roughly 2-4MB
depending on the kernel config.
ORC vs DWARF
============
ORC debuginfo's advantage over DWARF itself is that it's much simpler.
It gets rid of the complex DWARF CFI state machine and also gets rid of
the tracking of unnecessary registers. This allows the unwinder to be
much simpler, meaning fewer bugs, which is especially important for
mission critical oops code.
The simpler debuginfo format also enables the unwinder to be much faster
than DWARF, which is important for perf and lockdep. In a basic
performance test by Jiri Slaby [2]_, the ORC unwinder was about 20x
faster than an out-of-tree DWARF unwinder. (Note: That measurement was
taken before some performance tweaks were added, which doubled
performance, so the speedup over DWARF may be closer to 40x.)
The ORC data format does have a few downsides compared to DWARF. ORC
unwind tables take up ~50% more RAM (+1.3MB on an x86 defconfig kernel)
than DWARF-based eh_frame tables.
Another potential downside is that, as GCC evolves, it's conceivable
that the ORC data may end up being *too* simple to describe the state of
the stack for certain optimizations. But IMO this is unlikely because
GCC saves the frame pointer for any unusual stack adjustments it does,
so I suspect we'll really only ever need to keep track of the stack
pointer and the frame pointer between call frames. But even if we do
end up having to track all the registers DWARF tracks, at least we will
still be able to control the format, e.g. no complex state machines.
ORC unwind table generation
===========================
The ORC data is generated by objtool. With the existing compile-time
stack metadata validation feature, objtool already follows all code
paths, and so it already has all the information it needs to be able to
generate ORC data from scratch. So it's an easy step to go from stack
validation to ORC data generation.
It should be possible to instead generate the ORC data with a simple
tool which converts DWARF to ORC data. However, such a solution would
be incomplete due to the kernel's extensive use of asm, inline asm, and
special sections like exception tables.
That could be rectified by manually annotating those special code paths
using GNU assembler .cfi annotations in .S files, and homegrown
annotations for inline asm in .c files. But asm annotations were tried
in the past and were found to be unmaintainable. They were often
incorrect/incomplete and made the code harder to read and keep updated.
And based on looking at glibc code, annotating inline asm in .c files
might be even worse.
Objtool still needs a few annotations, but only in code which does
unusual things to the stack like entry code. And even then, far fewer
annotations are needed than what DWARF would need, so they're much more
maintainable than DWARF CFI annotations.
So the advantages of using objtool to generate ORC data are that it
gives more accurate debuginfo, with very few annotations. It also
insulates the kernel from toolchain bugs which can be very painful to
deal with in the kernel since we often have to workaround issues in
older versions of the toolchain for years.
The downside is that the unwinder now becomes dependent on objtool's
ability to reverse engineer GCC code flow. If GCC optimizations become
too complicated for objtool to follow, the ORC data generation might
stop working or become incomplete. (It's worth noting that livepatch
already has such a dependency on objtool's ability to follow GCC code
flow.)
If newer versions of GCC come up with some optimizations which break
objtool, we may need to revisit the current implementation. Some
possible solutions would be asking GCC to make the optimizations more
palatable, or having objtool use DWARF as an additional input, or
creating a GCC plugin to assist objtool with its analysis. But for now,
objtool follows GCC code quite well.
Unwinder implementation details
===============================
Objtool generates the ORC data by integrating with the compile-time
stack metadata validation feature, which is described in detail in
tools/objtool/Documentation/objtool.txt. After analyzing all
the code paths of a .o file, it creates an array of orc_entry structs,
and a parallel array of instruction addresses associated with those
structs, and writes them to the .orc_unwind and .orc_unwind_ip sections
respectively.
The ORC data is split into the two arrays for performance reasons, to
make the searchable part of the data (.orc_unwind_ip) more compact. The
arrays are sorted in parallel at boot time.
Performance is further improved by the use of a fast lookup table which
is created at runtime. The fast lookup table associates a given address
with a range of indices for the .orc_unwind table, so that only a small
subset of the table needs to be searched.
Etymology
=========
Orcs, fearsome creatures of medieval folklore, are the Dwarves' natural
enemies. Similarly, the ORC unwinder was created in opposition to the
complexity and slowness of DWARF.
"Although Orcs rarely consider multiple solutions to a problem, they do
excel at getting things done because they are creatures of action, not
thought." [3]_ Similarly, unlike the esoteric DWARF unwinder, the
veracious ORC unwinder wastes no time or siloconic effort decoding
variable-length zero-extended unsigned-integer byte-coded
state-machine-based debug information entries.
Similar to how Orcs frequently unravel the well-intentioned plans of
their adversaries, the ORC unwinder frequently unravels stacks with
brutal, unyielding efficiency.
ORC stands for Oops Rewind Capability.
.. [1] https://lore.kernel.org/r/20170602104048.jkkzssljsompjdwy@suse.de
.. [2] https://lore.kernel.org/r/d2ca5435-6386-29b8-db87-7f227c2b713a@suse.cz
.. [3] http://dustin.wikidot.com/half-orcs-and-orcs
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
ORC unwinder 개요
1-26이 문서는 `SPDX-License-Identifier: GPL-2.0`으로 배포됩니다. kernel의 `CONFIG_UNWINDER_ORC` option은 개념상 DWARF unwinder와 비슷한 ORC unwinder를 활성화합니다. ORC data format은 DWARF보다 훨씬 단순하므로 unwinder도 더 단순하고 빠릅니다.
ORC data는 `objtool`이 생성하는 unwind table로 이루어집니다. 이 out-of-band data를 in-kernel ORC unwinder가 사용합니다. `objtool`은 먼저 compile-time stack metadata validation인 `CONFIG_STACK_VALIDATION`을 수행합니다.
각 `.o` file의 모든 code path를 분석한 뒤 file의 instruction address마다 stack state 정보를 결정하고, 이를 `.orc_unwind`와 `.orc_unwind_ip` section에 출력합니다.
object별 ORC section은 link time에 합쳐지고 boot time에 sort 및 post-process됩니다. runtime unwinder는 최종 data를 이용해 instruction address와 해당 stack state를 연결합니다.
ORC와 frame pointer 비교
27-59frame pointer를 활성화하면 GCC가 kernel의 모든 function에 instrumentation code를 추가합니다. kernel `.text` 크기가 약 3.2% 늘어 kernel 전반이 느려집니다. Mel Gorman의 측정 `[1]`에서는 일부 workload가 5-10% 느려졌습니다.
ORC debuginfo는 out-of-band이므로 `.text` 크기와 runtime performance에 영향을 주지 않습니다. frame pointer를 끄고 ORC unwinder를 켜면 전반적인 성능을 높이면서도 신뢰할 수 있는 stack trace를 유지합니다.
Ingo Molnar는 3.2%의 `.text` 절약이 instruction cache footprint도 비슷한 비율로 줄이며, cache locality가 경계에 있는 workload에서는 더 큰 성능 향상으로 이어질 수 있다고 설명합니다.
ORC는 interrupt와 exception을 가로질러도 안정적으로 unwind할 수 있습니다. frame-pointer 기반 unwind는 interrupted function이 leaf function이거나 frame pointer를 저장하기 전에 interrupt가 발생하면 그 function의 caller를 건너뛸 수 있습니다.
frame pointer와 비교한 ORC unwinder의 주된 단점은 ORC unwind table 저장에 더 많은 memory가 필요하다는 점입니다. kernel configuration에 따라 대략 2-4MB가 필요합니다.
ORC와 DWARF 비교
60-89ORC debuginfo는 DWARF CFI의 복잡한 state machine과 불필요한 register tracking을 제거해 DWARF 자체보다 훨씬 단순합니다. unwinder code가 단순해져 bug가 줄어들며, mission-critical oops code에서는 특히 중요합니다.
단순한 debuginfo format 덕분에 perf와 lockdep에 중요한 unwind 속도도 크게 높아집니다. Jiri Slaby의 기본 성능 시험 `[2]`에서 ORC는 out-of-tree DWARF unwinder보다 `20x`, 즉 약 20배 빨랐습니다. 이후 성능을 두 배로 높인 개선 전 측정이므로 실제 차이는 `40x`, 즉 40배에 가까울 수 있습니다.
반면 ORC unwind table은 DWARF 기반 `eh_frame` table보다 RAM을 약 50% 더 사용합니다. x86 defconfig kernel에서는 약 1.3MB가 추가됩니다.
향후 GCC optimization의 stack state를 ORC format이 설명하기에는 너무 단순해질 가능성도 있습니다. 하지만 GCC는 특이한 stack adjustment에서 frame pointer를 저장하므로 call frame 사이에서는 stack pointer와 frame pointer만 추적하면 될 가능성이 높습니다.
DWARF가 추적하는 모든 register를 결국 추적해야 하더라도 format 자체는 kernel이 제어할 수 있으므로 복잡한 state machine은 피할 수 있습니다.
ORC unwind table 생성
90-137`objtool`은 기존 compile-time stack metadata validation 과정에서 모든 code path를 이미 따라가므로 ORC data를 처음부터 생성하는 데 필요한 정보를 갖고 있습니다. stack validation에서 ORC 생성으로 확장하는 일은 자연스럽습니다.
DWARF를 ORC로 변환하는 단순 tool로도 생성할 수는 있지만, kernel이 asm, inline asm, exception table 같은 special section을 광범위하게 사용하므로 완전한 결과를 만들 수 없습니다.
`.S` file의 special code path에는 GNU assembler `.cfi` annotation을, `.c` file의 inline asm에는 자체 annotation을 수동으로 달아 보완할 수 있습니다. 그러나 과거 asm annotation은 자주 부정확하거나 불완전했고 code 가독성과 유지보수를 해쳐 관리 불가능한 것으로 드러났습니다. glibc code를 보면 `.c` file의 inline asm annotation은 더 나쁠 수 있습니다.
`objtool`도 entry code처럼 stack을 특이하게 다루는 code에는 일부 annotation이 필요하지만, DWARF가 요구하는 수보다 훨씬 적어 DWARF CFI annotation보다 유지하기 쉽습니다.
`objtool` 생성 방식은 적은 annotation으로 더 정확한 debuginfo를 제공하고 kernel을 toolchain bug로부터 격리합니다. kernel은 오래된 toolchain 문제를 수년간 workaround해야 하는 경우가 많으므로 중요한 장점입니다.
단점은 unwinder가 GCC code flow를 reverse engineer하는 `objtool`의 능력에 의존한다는 점입니다. GCC optimization이 너무 복잡해지면 ORC 생성이 중단되거나 불완전해질 수 있습니다. livepatch도 이미 GCC code flow를 따라가는 `objtool`의 능력에 의존합니다.
새 GCC optimization이 `objtool`을 깨뜨리면 구현을 재검토해야 합니다. GCC에 optimization을 더 분석하기 쉬운 형태로 요청하거나, `objtool`이 DWARF를 추가 input으로 사용하거나, 분석을 돕는 GCC plugin을 만드는 방법이 있습니다. 현재 `objtool`은 GCC code를 잘 따라갑니다.
unwinder 구현 세부사항
138-158`objtool`이 통합하는 compile-time stack metadata validation 기능은 `tools/objtool/Documentation/objtool.txt`에 자세히 설명되어 있습니다.
`.o` file의 모든 code path를 분석한 뒤 `orc_entry` struct array와 해당 struct에 연결된 instruction address의 parallel array를 만들고, 각각 `.orc_unwind`와 `.orc_unwind_ip` section에 기록합니다.
검색 대상인 `.orc_unwind_ip`를 더 compact하게 만들어 성능을 높이기 위해 ORC data를 두 array로 나눕니다. 두 array는 boot time에 병렬로 sort됩니다.
runtime에 생성하는 fast lookup table로 성능을 더 높입니다. 이 table은 address를 `.orc_unwind` table의 index range와 연결하므로 전체가 아니라 작은 subset만 검색하면 됩니다.
이름의 유래와 참고 자료
159-182중세 folklore의 Orc는 Dwarf의 천적으로 묘사됩니다. 마찬가지로 ORC unwinder는 DWARF의 복잡성과 느린 속도에 맞서 만들어졌습니다.
인용된 설정 설명 `[3]`은 Orc가 문제의 여러 해법을 잘 고려하지는 않지만 생각보다 행동을 앞세워 일을 끝내는 데 뛰어나다고 말합니다. 이에 빗대어 ORC unwinder는 난해한 DWARF unwinder와 달리 variable-length, zero-extended unsigned-integer, byte-coded state-machine debuginfo entry를 decode하는 데 시간이나 silicon effort를 낭비하지 않는다고 설명합니다.
상대의 계획을 풀어헤친다는 비유처럼 ORC unwinder는 stack을 단호하고 효율적으로 unwind합니다. ORC는 Oops Rewind Capability의 약자입니다.
참고 자료: `[1] https://lore.kernel.org/r/20170602104048.jkkzssljsompjdwy@suse.de`, `[2] https://lore.kernel.org/r/d2ca5435-6386-29b8-db87-7f227c2b713a@suse.cz`, `[3] http://dustin.wikidot.com/half-orcs-and-orcs`.
요약과 해설
orc-unwinder.rst:1-182ORC는 `objtool`이 instruction별 stack state를 `.orc_unwind`와 `.orc_unwind_ip`에 기록하는 out-of-band unwinder입니다. frame pointer instrumentation 없이 안정적인 stack trace를 제공하며 interrupt와 exception도 가로질러 unwind할 수 있습니다.