[RFC] Support for Backtraces in CTF format

[Indu Bhagat]

Hello people,

In the GNU Tools Track at LPC 2021 this year, we talked briefly about 
our plan for CTF V4, especially support for backtraces.

https://linuxplumbersconf.org/event/11/contributions/1003/

To summarize, the motivation to add support for backtraces in CTF is to 
support the use case of online stack unwinding. A couple of large 
applications of interest (yes, one of them is the Linux Kernel) have 
adopted ad-hoc solutions because:
- eh_frame-based unwinders are complex and slow for them to manage with
- eh_frame-based unwinders are large as they need to deal with DWARF 
opcodes via a stack machine implementation

Such ad-hoc solutions are reaching their limits because the workflow is 
based on offline tools that inspect the generated binary to reconstruct 
the control-flow, and to determine the stack frame size in general. 
Other issues include needing to fix issues around the stubs included 
from system libraries from time to time. This whole effort is compounded 
with every new architecture the application supports. An interesting 
detail is that each project has come up with their own "unwind format" 
best tailored to their respective needs.

Some of the above issues were also highlighted at the Toolchain and 
Kernel MC at LPC 2021 
https://linuxplumbersconf.org/event/11/contributions/971/.

So, at a high-level, following requirements for CTF backtraces are aimed 
for:

1. Support asynchronous stack unwinding
2. Keep the format minimal, simple and compact. There should be no 
complex encodings to decipher (avoid DWARF-like expressions), no 
location lists and no stack machine to process any of this.
3. Provide means to gather the original value of the arguments of the 
functions, when possible. For some projects, which are interested in 
fast online stack tracing, this is a must have.

Stack Unwinding
---------------

First up is information for stack unwinding. The proposal is to include 
information to recover the CFA, and Return Address, given a PC. The 
other set of callee-saved registers are not included for recovery across 
frames. All this information for stack unwinding can be generated by the 
assembler using the existing .cfi_* directives (with linker doing its 
due part of merging them later). In other words, this will be based on 
the standard set of CFI directives already emitted by GCC.

This information is made available via a new section called .ctf_frame. 
It will be possible to have all of .eh_frame, .debug_frame and
.ctf_frame generated by the assembler and in the same object, if so 
desired.

Q1. The .ctf_frame section needs to be SEC_LOAD and SEC_ALLOC to support 
the use-case of fast virtual stack unwinding, correct ? What are some 
other issues that need attention here ?

At a high-level, .ctf_frame section will contain:

1. A sorted index mapping Start PC of a function to its set of CTF Frame 
Record Entries (FRE). So, something like:

  [FuncStart PC1]---FRE_section_offset11
  [FuncStart PC2]---FRE_section_offset21
  [FuncStart PC3]---FRE_section_offset31
   ...

Just specifying the offset to the first FRE of the function is enough, 
as the FREs are generated per function by the assembler and not 
rearranged later on (by the linker).

2. A set of FREs one per block of instructions with the required 
information to recover the CFA and RA.

  [FRE11] @ FRE_section_offset11
  [FRE12] @ FRE_section_offset12
  ...
  [FRE21] @ FRE_section_offset21
  [FRE22] @ FRE_section_offset22
  [FRE23] @ FRE_section_offset23
  ...
  [FRE31] @ FRE_section_offset31
  [FRE32] @ FRE_section_offset32
  [FRE33] @ FRE_section_offset33
  ...

where FRE11, FRE12 belong to function 1, FRE21, FRE22, FRE23 belong to 
function 2 and so on.

The format for FRE can be discussed in our follow up discussions. What 
do you think ? Particularly:

Q2. Is there value in keeping the index in #1 above in a separate 
section ? So something like .ctf_frame *and* and a .ctf_frame_index ?

Original value of arguments
---------------------------

[Original-value-of-arguments PHASE 1]

Next, let's see what can be done about #3, format changes to gather the 
original value of the arguments to the functions. A proposal is to view 
the challenge of specifying the argument location by splitting it into 
two separate steps:

[Step 1] Argument classification: Given a high-level language type of 
the argument, what is the machine type?
[Step 2] Argument marshaling: Given the machine type(s) for an argument, 
which storage locations are used for argument passing ?

The proposal is that the CTF format does the step #1 of assigning 
storage classes to each argument, and encodes it in the format. E.g. for 
AMD64, it identifies unambiguously a set of storage classes from INTEGER 
/ SSE / SSEUP / X87/ X87UP / MEMORY etc. per argument (for args of 
composite type, it specifies a set of storage classes as applicable). 
And next, it is the backtrace client which performs the step #2, by 
internalizing some knowledge of the ABI of the binary. In other words, 
the natural location of the original value of the argument is not 
encoded in the debug format, it is inferred by the (backtrace) client 
using the position and storage class of the argument and the knowledge 
of the associated ABI.

Thoughts on this ? Particularly:

Q3. The client is expected to know the ABI specific rules and perform 
the argument marshaling. Will this work in practice ? Most ABI docs do 
lay out the rules unambiguously.

Q4. Clearly, the CTF format will need a way to accommodate "many" 
important ABIs to be useful across the board.  At this point, we have 
started with AARCH64 and AMD64. I am curious to know what others think 
about the support for AARCH64 and AMD64 as the beginning point. Will CTF 
support for backtraces be useful enough with support for just two ABIs ? 
Do you have any other ABIs in mind that should be accommodated ?

[Original-value-of-arguments PHASE 2]

Because of the nature of our programs, it is understood that recovering 
original value of the arguments via registers may not always be 
possible, especially because the callee-saved registers will not be 
recoverable. Most importantly, the desire is to keep the format simple 
so there cannot be any new special purpose bytecodes needing 
interpretation at run time. For this, a solution where original 
arguments are saved on stack for recovery can be adopted.

Please share your thoughts/feedback, it will surely impact the shape of 
the proposal. Thanks for taking time to read through this RFC :-).

The support for CTF backtraces needs to be integrated into the toolchain 
so that the overhead and prevalence of the ad-hoc solutions for 
generating backtraces can be avoided.

Thanks