More compact SFrames through deduplication

Mon Nov 10 08:28:31 GMT 2025

Hi Tatsuyuki,

On 11/8/25 5:21 PM, Jose E. Marchesi wrote:
> 
> Adding Elena in CC.
> 
>> [markdown version available at
>> https://github.com/ishitatsuyuki/compact-frame/blob/master/pre-proposal.md]
>> <https://github.com/ishitatsuyuki/compact-frame/blob/master/pre-proposal.md%5D>
>>

Thanks for your interest in SFrame and for sharing your usecase.

>> As many have suggested, compiling with frame pointers [1] is the
>> lowest overhead and least complicated way to profile on
>> Linux. But recently there have been lots of discussions for
>> alternatives to this. My personal case is to unwind Windows
>> applications without recompiling them; notably, with perf's `-g dwarf`
>> recording mode a userspace tool can later read PE
>> unwind info and unwind the stack accurately; and having a flamegraph
>> has helped me fix countless performance issues.
>>
>> Most recently there has been discussion on SFrame, which presents
>> itself as a simpler alternative to .eh_frame, that
>> runs fast, does not require stepping on CFI opcodes, and simple enough
>> to implement as an in-kernel unwinder. I am very
>> excited that we might finally be able to unwind without recompiling
>> for frame pointers. (Note, there needs to be some
>> way to generate SFrame, but it seems conversion is very much possible from DWARF and even PE.)
>>
>> Now, as MaskRay [2] and other have highlighted, the size overhead of
>> SFrame is at least as much as that of .eh_frame,
>> and this is large enough that it's a valid reason for people to turn
>> this off for embedded or mobile OSes. So reducing
>> size is an important goal if SFrame wants to be successful.
>>
>> ## The prior arts
>>
>> There are a few prior arts that we can draw ideas from.
>>
>> The first is Mach-O's compact unwind format [3], which is fairly
>> similar to a FRE in SFrame (which are expressions to
>> calculate old_rsp and old_rbp directly), except that it throws away
>> all the FREs for prologs and epilogs and treat the
>> entire function as function body. I personally see this as "SFrame but with less accuracy and smaller size".
>>
>> More interesting is PE's x64 and arm64 unwind code format [4,5]. The
>> x64 format is represented in terms of "opcodes",
>> i.e. bytecode that maps 1:1 to HW instructions that are executed in a
>> prolog. This has a size benefit since instructions
>> like push, which generates multiple CFI updates, can be compactly
>> represented. In arm64 this idea is taken further to
>> also encode the length of the instruction itself into the opcode. On the downside, I think this is a lot of
>> (arch-specific) semantics that needs to be implemented by the unwinder, and recovering the rule requires stepping
>> through the opcodes, which is slower than having the FRE directly. It
>> also imposes restrictions on how compilers can
>> emit the prolog (e.g. LLVM has some Windows-specific paths [6]).
>>
>> It's also worth noting that PE unwind codes can do in-kernel async
>> unwinds as well as C++-compatible full unwinds, with
>> the same metadata. This saves space.
>>
>> The most interesting idea from arm64 unwind code format is canonical
>> prologs as a common-path optimization. In addition
>> to constraining the instructions, the compiler needs to push and pop
>> registers in a very specific order. On the bright
>> side, the unwind info for the entire function can now be represented
>> with just (# of GP regs saved) + (# of FP regs
>> saved) + (stack alloc size) + (function length). This all fits in 32 bits and is extremely compact.
>>
>> ## Chunking CFIs
>>
>> With the diversity of toolchains we have on Linux (and absence of a
>> pre-existing restriction on prologs), it's unlikely
>> we can define a canonical prolog format. But this made me wonder how
>> diverse are things in practice. With some simple
>> dwarfdump experiments, it seems that each compiler does push register
>> in a fairly consistent order. And there is way
>> fewer unique CFI patterns compared to the number of FDEs we have.
>>
>> Here are some sample numbers. I took the AMD Vulkan driver from Mesa, because it's fast to compile and contains a
>> diverse set of libraries.
>>
>> | Binary | Compiler | Frame Pointer | `.text` (bytes) |
>> | `.eh_frame_hdr` (bytes) | `.eh_frame` (bytes) | FDE count |
>> | .text/FDE (bytes) | FRE count | Unique CFA states |
>> |---------------------|----------|---------------|-----------------|-------------------------|---------------------|-----------|-------------------|-----------|-------------------|
>> | libvulkan_radeon.so | GCC | No | 7,141,795 | 116,244 | 646,512 |
>> | 14,529 | 491 | 103,178 | 912 |
>> | libvulkan_radeon.so | GCC | Yes | 7,312,627 | 116,244 | 520,888 |
>> | 14,529 | 503 | 60,024 | 39 |
>> | libvulkan_radeon.so | Clang | No | 6,562,563 | 68,604 | 484,104 |
>> | 8,574 | 765 | 91,608 | 619 |
>> | libvulkan_radeon.so | Clang | Yes | 6,663,139 | 68,604 | 394,240 |
>> | 8,574 | 777 | 54,982 | 17 |
>>
>> My main idea is to have a registry of CFI chunks that is deduplicated,
>> and build up the main binary search table from
>> these chunks. Remember, the number of unique CFI pattern is very low,
>> so we can spend lots of bytes in the CFI itself,
>> making it self-describing and not needing to impose complexity on the unwinder or restrictions on the compiler.
>>
>> As an example, using x86 assembly:
>>
>> ```
>> [chunk A --- prolog]
>>      .cfi_def_cfa_offset 8
>>      push %<reg> ; callee-saved reg
>>      .cfi_def_cfa_offset (offset from retaddr)
>>      ...
>>
>>      sub $STACK_SIZE, %rsp
>> [chunk B --- inside function]
>>      .cfi_def_cfa_offset (offset from retaddr)
>>      .cfi_offset %<reg>, (offset from rsp) ; for all registers
>>      
>>      ... ; function body
>>
>>      add $STACK_SIZE, %rsp
>> [chunk C --- epilog]
>>      .cfi_def_cfa_offset (offset from retaddr)
>>      pop %reg ; callee-saved reg
>>      .cfi_def_cfa_offset (offset from retaddr)
>>      ...
>> ```
>>
>> Chunk A and C is independent of stack size and can be reused across
>> functions easily. Chunk B depends on the (saved
>> register, stack size), so we keep the # of duplicated rows minimal this way.
>>

While it is true that we may see many functions using Chunk A and Chunk 
C, the number of chunks used per function, in practice (for at least 
x86_64) may be larger than 4, creating enough diversity, and hence a 
potentially large(r) "chunk-based index".

[I think you know this already, as you have done the measurements above :)]

>> In the end state it will be up to the compiler to decide on a chunking
>> scheme that deduplicates well. But until then,
>> external tool seeking to chunk on their own can use a simple heuristic: chunk at where the stack is deepest.
>>

IMHO making an optimizing compiler adapt optimization decisions/code 
generation for optimal chunking/compact stack tracing info should 
ideally be avoided.

That said, the good thing is that, ATM I dont see the need to influence 
the compiler for incorporating your suggestion of de-duplicating.

>> ## How can this be adopted in SFrame?
>>
>> The hierarchy of SFrame currently looks like:
>>
>> - Header
>> - FDEs (fixed size: initial addr, size, FRE offset, FRE size, other metadata)
>> - FREs (variable size)
>>
>> We could repurpose Function Descriptor Entries (FDEs) into Chunk
>> Descriptor Entries (CDEs), since both represent an
>> array of FREs. The main difference is that a chunk is not associated with a particular code address, nor it has a
>> fixed code size (e.g. in the above example, chunk B corresponds to
>> function body and have variable size). Size can be
>> defined implicitly by treating the next initial address as the end of current chunk.
>>
>> So the end result would be breaking up FDEs into a two-level indirection:
>>
>> - Header
>> - Addr-chunk table (fixed size: initial addr, CDE index)
>> - CDEs (fixed size; FRE offset, FRE size, other metadata)
>> - FREs (variable size)
>>
>> The addr-chunk is most size-sensitive. Let's assume for now we use 32
>> bits for addr and 16 bits for CDE index. Assuming
>> an average function is chunked into A+B+C+Gap, that would be four
>> chunk entries in the table, or 24 bytes per function.
>>

We too have observed that many of the FRE stack offsets are duplicates 
in a binary.  FRE data de-duplication was previously proposed by some 
folks too, but we did not evaluate this further.

https://sourceware.org/binutils/wiki/sframe/sframev3todo#Approach_2:_Deduplicated_stack_offsets

Given the interest in reducing the size of SFrame and your usecase, I 
think its worth revisiting.

IIUC, your proposal is on similar lines, just that the indexing of 
information is chunk-based rather than function-based.

>> Let's compare this to current SFrame, consider a function that does
>> not establish FP, does not clobber FP and save N
>> non-FP callee-saved registers. The size per function is
>> `20+(2+1)*(2*N+3)` bytes. To get a very rough ballpark estimate,
>> at N=4 SFrame would be 53 bytes, and the compressed scheme would be less than half of that.
>>

I dont understand the `20+(2+1)*(2*N+3)` bytes heuristic. Can you 
explain it ?

>> There are further size optimization ideas I want to pursue. But that
>> would be another long writing, so let's first
>> discuss whether this is a direction we want to go for, and we can come up with more ideas later.
>>

In principle, yes, improvements to SFrame as a stack tracing format are 
welcome and we are interested in evaluating them.

As for your current idea of chunk-based index with de-duplicated FRE 
data, I think it will be good to prototype this at some point and get 
some measurements.  I think we can prototype this such that the new 
layout is emitted at link-time in sframe_encoder_write () / 
sframe_encoder_write_sframe ().  SFrame data creation for PLT also 
invokes this path, but using --no-ld-generated-unwind-info should help 
for prototyping.

Before you prototype though, it will be good to discuss the exact 
representations that your proposal puts forth, to make sure the current 
flexibility of the format is not sacrificed.

Thanks,

>> [1]: https://www.brendangregg.com/blog/2024-03-17/the-return-of-the-frame-pointers.html
>> [2]: https://maskray.me/blog/2025-09-28-remarks-on-sframe
>> [3]: https://faultlore.com/blah/compact-unwinding/
>> [4]: https://learn.microsoft.com/en-us/cpp/build/exception-handling-x64
>> [5]: https://learn.microsoft.com/en-us/cpp/build/arm64-exception-handling
>> [6]: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/X86/X86FrameLowering.cpp