More compact SFrames through deduplication

[Steven Rostedt]

On Tue, 10 Mar 2026 17:19:28 -0700
Indu Bhagat <indu.bhagat@oracle.com> wrote:

Hi Indu,

> Thanks for the well-documented POC and your proposal.
> 
> For benefit of readers and to ensure I got a grasp of your proposal, 
> here are some notes (summary) from my understanding.  (BTW, Tests added 
> in POC commit give a quick overview of expected CFrame for the curious 
> reader).

Thanks for the detailed summary.

> 
> * Design differences from SFrame V3
>    Today’s SFrame V3 FDE model is conceptually simple:
>      - each function has a fixed-size FDE entry,
>      - the FDE gives you start PC, size, and where the FRE data lives,
>      - then you parse the function’s FRE rows.  FRE data is the main 
> carrier of the stack trace info (e.g., CFA offsets, stack offsets, 
> register info etc).
> 
> The proposal replaces that with (CFrame):
>    - bit-wise PC lookup tables (using outer_bits, inner_bits, bottom_trim),
>    - an "outer table" that maps PC high bits to an inner-table buckets,
>    - an "inner table" containing address boundaries and FDE indices (or 
> GAP sentinels),
>    - an "FDE index table" that maps logical FDE (Chunk) IDs to 
> deduplicated FRE payload,
>    - intensive bit-packing in the above structures. Each CFrame section 
> defines the number of bits used for the specific tables above (based on 
> the entropy of that section). E.g., sample output of a CFrame section:
>      Bit parameters: bottom_trim=0, outer_bits=8, inner_bits=8
>      Bit-packing: fde_idx=8, outer_start=10, outer_count=5, 
> fre_offset=13, fre_count=5
>    - Chunking a single function into multiple ranges to increase FRE 
> payload reuse.  With the CHUNK_STRATEGY_CALLEE_SAVED strategy, the POC 
> finds "interesting" sequences (put roughly: the stack increment/stack 
> frame stable/stack decrement stubs) across functions.
>    - De-duplication of these FDE chunks (stack increment/stack frame 
> stable/stack decrement) across functions in a CFrame section.
> 
> PS: This is a substantial redesign to the specification, not an 
> incremental refinement to SFrame V3.

Right. My opinion is to keep moving forward on Sframe V3. This proposal may
need to be done separately and perhaps under a different section ("cframe"?).

I'm not a tool chain developer so I'm not sure how hard it would be to have
support for multiple stack walkers, but it shouldn't be too much of a
burden in the kernel. The unwind logic is made to handle multiple stack walkers.

> 
> * There is some clear value addition by the CFrame proposal:
>    - Reduced size

>    - Information lookup (using the two level index along with the FDE 
> index) is not asymptotically worse for stacktracers.

Yeah, as long as the stack tracer doesn't have to interpret code (DWARF),
multi-layered indexing should not be an issue. Unless it is determined to
be reading too much of user space (requiring more page faults).

>    - Flexibility to add new FDE types for future needs is still 
> maintained AFAICT.
> 
> * Workflow in POC: The POC parses eh_frame/debug_frame data to ascertain 
> the split of a function into epilogue/body/prologue. Then deduplicates 
> these "chunks" across functions.
> 
> * Miscellaneous critique points:
>    - On first look, the explicit GAP sentinels make me a bit 
> uncomfortable, but may be its just me. (As compared to SFrame's explicit 
> data on size of function) I think it may become a problem when there is 
> "sparse" layout of function data in .text* sections.
>    - For a few test runs on sample libraries, I tried to compare:
>      1. sframe2cframe -v --chunk-dwarf  --dump
>      2. sframe2cframe -v --chunk-dwarf --chunk-strategy=none
>      IIUC, #2 basically shows the benefit of bit-packing in the various 
> lookup tables, and #1 shows the benefit of bit-packing + de-dup of FRE 
> payloads.  Is that correct ?  If so, I #2 brings a major chunk of 
> benefits as compared to #1.  Is that consistent with your findings too ?
> 
> Now, at this time, my two main concerns are:
> 
> * Binary incompatibility with SFrame V3
>    As I mentioned above, this breaks binary compatibility with SFrame 
> V3.  CFrame is a substantial redesign of the information layout. 
> Readers of SFrame V3 will need a new decoder altogether, given the 
> differences in information layout (in lookup tables, FDE index).
> 
> * Implementation Complexity in toolchains
>    - Most of the unknowns/risks lie here ATM, as you point out.
>    - While the compiler is likely the most natural place to identify 
> semantically meaningful chunk boundaries (stack increment/stack frame 
> stable/stack decrement), its the linker that is best suited to a) create 
> that bit-packed, two level lookup table with FDE index and b) 
> deduplicate chunks across functions.
>    - Next, the linker must be able to see the mapping of chunks for each 
> function/symbol to implement garbage collection, ODR needing to discard 
> functions from output, etc.  Handling relocations also means its best to 
> avoid the CFrame index creation until link time.
>    - CFrame is not relocation friendly. The input to linker needs to be 
> "relocation friendly". CFrame as is cannot be fed to the linker (the 
> compact index of de-duped entries is one of the problem for linker 
> input).  This means that either a distinct relocatable representation 
> would be needed for ET_REL, and/or CFrame would be restricted to final 
> linked outputs (ET_DYN/ET_EXEC). In either case, the toolchain contract 
> does become more complicated than for current SFrame V3 IMO.
>    - Although obvious, but as we can see, the above points suggest a 
> newfound need for additional CFI directives as the new interface between 
> compiler and assembler (to identify the chunks).
> 
> Thoughts on managing these aspects of additional work/complexity (and 
> binary incompatibility with SFrame V3) ?

This Cframe idea looks promising, but as Indu pointed out, it has a lot of
hurdles to overcome before it can be added to production. It may be years
before something like his could be used. But I do like the brainstorming
of ideas ;-)

-- Steve