unwind, perf: sframe user space unwinding

It's possible for irq_work_queue() to fail if the work has already been claimed. That can happen if a TWA_NMI_CURRENT task work is requested before a previous TWA_NMI_CURRENT IRQ work on the same CPU has gotten a chance to run.

The error has to be checked before the write to task->task_works. Also the try_cmpxchg() loop isn't needed in NMI context. The TWA_NMI_CURRENT case really is special, keep things simple by keeping its code all together in one place.

Quoted 4 lines · Josh Poimboeuf

It's possible for irq_work_queue() to fail if the work has already been claimed. That can happen if a TWA_NMI_CURRENT task work is requested before a previous TWA_NMI_CURRENT IRQ work on the same CPU has gotten a chance to run.

I'm confused, if it fails then it's already pending, and we'll get the notification already. You can still add the work.

Quoted 4 lines

The error has to be checked before the write to task->task_works. Also the try_cmpxchg() loop isn't needed in NMI context. The TWA_NMI_CURRENT case really is special, keep things simple by keeping its code all together in one place.

NMIs can nest,

consider #DB (which is NMI like)

doing task_work_add() and getting interrupted with NMI doing the same.

Quoted 8 lines · Peter Zijlstra

Quoted 4 lines · Josh Poimboeuf

It's possible for irq_work_queue() to fail if the work has already been claimed. That can happen if a TWA_NMI_CURRENT task work is requested before a previous TWA_NMI_CURRENT IRQ work on the same CPU has gotten a chance to run.

I'm confused, if it fails then it's already pending, and we'll get the notification already. You can still add the work.

Yeah, I suppose that makes sense. If the pending irq_work is already going to set TIF_NOTIFY_RESUME anyway, there's no need to do that again.

Quoted 6 lines

Quoted 4 lines

The error has to be checked before the write to task->task_works. Also the try_cmpxchg() loop isn't needed in NMI context. The TWA_NMI_CURRENT case really is special, keep things simple by keeping its code all together in one place.

NMIs can nest,

Just for my understanding: for nested NMIs, the entry code basically queues up the next NMI, so the C handler (exc_nmi) can't nest. Right?

Quoted 1 line

consider #DB (which is NMI like)

What exactly do you mean by "NMI like"? Is it because a #DB might be basically running in NMI context, if the NMI hit a breakpoint?

Quoted 1 line

doing task_work_add() and getting interrupted with NMI doing the same.

How exactly would that work? At least with my patch the #DB wouldn't be able to use TWA_NMI_CURRENT unless in_nmi() were true

Quoted 2 lines · Josh Poimboeuf

What exactly do you mean by "NMI like"? Is it because a #DB might be basically running in NMI context, if the NMI hit a breakpoint?

No, #DB, #BP and such are considered NMI (and will have in_nmi() true) because they can trigger anywhere, including sections where IRQs are disabled.

Quoted 7 lines · Peter Zijlstra

Quoted 2 lines · Josh Poimboeuf

What exactly do you mean by "NMI like"? Is it because a #DB might be basically running in NMI context, if the NMI hit a breakpoint?

No, #DB, #BP and such are considered NMI (and will have in_nmi() true) because they can trigger anywhere, including sections where IRQs are disabled.

So:

- while exceptions are technically not NMI, they're "NMI" because they can occur in NMI or IRQ-disabled regions

- such "NMI" exceptions can be preempted by NMIs and "NMIs"

- NMIs can be preempted by "NMIs" but not NMIs (except in entry code!)

... did I get all that right? Not subtle at all!

Quoted 4 lines

The error has to be checked before the write to task->task_works. Also the try_cmpxchg() loop isn't needed in NMI context. The TWA_NMI_CURRENT case really is special, keep things simple by keeping its code all together in one place.

NMIs can nest, consider #DB (which is NMI like) doing task_work_add() and getting interrupted with NMI doing the same.

If TWA_NMI_CURRENT task work is queued from an NMI triggered while running in __schedule() with IRQs disabled, task_work_set_notify_irq() ends up inadvertently running on the next scheduled task. So the original task doesn't get its TIF_NOTIFY_RESUME flag set and the task work may get delayed indefinitely, or may not get to run at all.

    __schedule()
	// disable irqs
	    <NMI>
		task_work_add(current, work, TWA_NMI_CURRENT);
	    </NMI>
	// current = next;
	// enable irqs
	    <IRQ>
		task_work_set_notify_irq()
		test_and_set_tsk_thread_flag(current, TIF_NOTIFY_RESUME); // wrong task!
	    </IRQ>
	// original task skips task work on its next return to user (or exit!)

Fix it by storing the task pointer along with the irq_work struct and passing that task to set_notify_resume().

So I'm a little confused, isn't something like this sufficient?

If we hit before schedule(), all just works as expected, if we hit after schedule(), the task will already have the TIF flag set, and we'll hit the return to user path once it gets scheduled again.

---

kernel/task_work.c +6 -1

index c969f1f26be5..155549c017b2 100644
@@ -9,7 +9,12 @@ static struct callback_head work_exited; /* all we need is ->next == NULL */
 #ifdef CONFIG_IRQ_WORK
 static void task_work_set_notify_irq(struct irq_work *entry)
 {
-	test_and_set_tsk_thread_flag(current, TIF_NOTIFY_RESUME);
+	/*
+	 * no-op IPI
+	 *
+	 * TWA_NMI_CURRENT will already have set the TIF flag, all
+	 * this interrupt does it tickle the return-to-user path.
+	 */
 }
 static DEFINE_PER_CPU(struct irq_work, irq_work_NMI_resume) =
 	IRQ_WORK_INIT_HARD(task_work_set_notify_irq);

The self-IPI is only needed when the NMI happened in user space, right? Would it make sense to have an optimized version of that?

Quoted 2 lines · Josh Poimboeuf

The self-IPI is only needed when the NMI happened in user space, right? Would it make sense to have an optimized version of that?

Actually, maybe not, that could be tricky if the NMI hits in the kernel after task work runs.

If we hit before schedule(), all just works as expected, if we hit after schedule(), the task will already have the TIF flag set, and we'll hit the return to user path once it gets scheduled again.

---

kernel/task_work.c +6 -1

index c969f1f26be5..155549c017b2 100644
@@ -9,7 +9,12 @@ static struct callback_head work_exited; /* all we need is ->next == NULL */
 #ifdef CONFIG_IRQ_WORK
 static void task_work_set_notify_irq(struct irq_work *entry)
 {
-	test_and_set_tsk_thread_flag(current, TIF_NOTIFY_RESUME);
+	/*
+	 * no-op IPI
+	 *
+	 * TWA_NMI_CURRENT will already have set the TIF flag, all
+	 * this interrupt does it tickle the return-to-user path.
+	 */
 }
 static DEFINE_PER_CPU(struct irq_work, irq_work_NMI_resume) =
 	IRQ_WORK_INIT_HARD(task_work_set_notify_irq);

Quoted 25 lines · On Wed, 22 Jan 2025 13:42:28 +0100 Peter Zijlstra <[email protected]> wrote:

If we hit before schedule(), all just works as expected, if we hit after schedule(), the task will already have the TIF flag set, and we'll hit the return to user path once it gets scheduled again.

---

kernel/task_work.c +6 -1

index c969f1f26be5..155549c017b2 100644
@@ -9,7 +9,12 @@ static struct callback_head work_exited; /* all we need is ->next == NULL */
 #ifdef CONFIG_IRQ_WORK
 static void task_work_set_notify_irq(struct irq_work *entry)
 {
-	test_and_set_tsk_thread_flag(current, TIF_NOTIFY_RESUME);
+	/*
+	 * no-op IPI
+	 *
+	 * TWA_NMI_CURRENT will already have set the TIF flag, all
+	 * this interrupt does it tickle the return-to-user path.
+	 */
 }
 static DEFINE_PER_CPU(struct irq_work, irq_work_NMI_resume) =
 	IRQ_WORK_INIT_HARD(task_work_set_notify_irq);

@@ -98,6 +103,7 @@ int task_work_add(struct task_struct *task, struct callback_head *work,
 		break;

kernel/task_work.c int task_work_add(struct task_struct *task, struct callback_head *work, · line 109

Quoted 6 lines

kernel/task_work.c +1 -0

 #ifdef CONFIG_IRQ_WORK
 	case TWA_NMI_CURRENT:
+		set_tsk_thread_flag(current, TIF_NOTIFY_RESUME);
 		irq_work_queue(this_cpu_ptr(&irq_work_NMI_resume));
 		break;
 #endif

Does this patch replace patches 1 and 2?

If so, Peter, can you give me a Signed-off-by?

-- Steve

It was decided years ago that .cfi_* annotations aren't maintainable in the kernel. They were replaced by objtool unwind hints. For the kernel proper, ensure the CFI_* macros don't do anything.

On the other hand the VDSO library *does* use them, so user space can unwind through it.

Make sure these macros only work for VDSO. They aren't actually being used outside of VDSO anyway, so there's no functional change.

Signed-off-by Josh Poimboeuf <[email protected]>

arch/x86/include/asm/dwarf2.h +0 -8

 
-#ifndef BUILD_VDSO
-	/*
-	 * Emit CFI data in .debug_frame sections, not .eh_frame sections.
-	 * The latter we currently just discard since we don't do DWARF
-	 * unwinding at runtime.  So only the offline DWARF information is
-	 * useful to anyone.  Note we should not use this directive if we
-	 * ever decide to enable DWARF unwinding at runtime.
-	 */

+/*
+ * On x86, these macros aren't used outside VDSO. As well they shouldn't be:
+ * they're fragile and very difficult to maintain.
+ */

Quoted 13 lines · Josh Poimboeuf

arch/x86/include/asm/dwarf2.h +0 -13

-#ifndef BUILD_VDSO
-	/*
-	 * Emit CFI data in .debug_frame sections, not .eh_frame sections.
-	 * The latter we currently just discard since we don't do DWARF
-	 * unwinding at runtime.  So only the offline DWARF information is
-	 * useful to anyone.  Note we should not use this directive if we
-	 * ever decide to enable DWARF unwinding at runtime.
-	 */
-	.cfi_sections .debug_frame
-#else
-	 /*
-	  * For the vDSO, emit both runtime unwind information and debug
-	  * symbols for the .dbg file.

arch/x86/include/asm/dwarf2.h line 34

Quoted 5 lines

arch/x86/include/asm/dwarf2.h +2 -3

-	  */
-	.cfi_sections .eh_frame, .debug_frame
-#endif
+#else /* !BUILD_VDSO */
+

Did you remove ".cfi_sections .debug_frame" on purpose from the !BUILD_VDSO path compared to V3?

Presumably to not only not emit DWARF CFI from assembler, but any source?

Enable sframe generation in the VDSO library so kernel and user space can unwind through it.

Signed-off-by Josh Poimboeuf <[email protected]>

arch/x86/include/asm/dwarf2.h line 15

Quoted 9 lines · Josh Poimboeuf

arch/x86/include/asm/dwarf2.h +0 -1

index b195b3c8677e..1c354f648505 100644
@@ -12,8 +12,11 @@
  	 * For the vDSO, emit both runtime unwind information and debug
  	 * symbols for the .dbg file.
  	 */
-

Nit: Deleted blank line you introduced in "[PATCH v4 05/39] x86/asm:
Avoid emitting DWARF CFI for non-VDSO".

arch/x86/include/asm/dwarf2.h line 15

Quoted 1 line

arch/x86/include/asm/dwarf2.h +1 -0

+#ifdef __x86_64__

#if defined(__x86_64__) && defined(CONFIG_AS_SFRAME)

AFAIK the kernel has a minimum binutils requirement of 2.25 [1] and assembler option "--gsframe" as well as directive ".cfi_sections .sframe" were introduced with 2.40.

Quoted 6 lines

arch/x86/include/asm/dwarf2.h +3 -0

+	.cfi_sections .eh_frame, .debug_frame, .sframe
+#else
  	.cfi_sections .eh_frame, .debug_frame
+#endif
  #define CFI_STARTPROC		.cfi_startproc
  #define CFI_ENDPROC		.cfi_endproc

Quoted 3 lines · Jens Remus

Quoted 1 line · Josh Poimboeuf

+#ifdef __x86_64__

Quoted 5 lines

#if defined(__x86_64__) && defined(CONFIG_AS_SFRAME)

AFAIK the kernel has a minimum binutils requirement of 2.25 [1] and assembler option "--gsframe" as well as directive ".cfi_sections .sframe" were introduced with 2.40.

True, I'll change it to just '#ifdef CONFIG_AS_SFRAME' since that's what really matters (and 32-bit doesn't support it anyway).

Quoted 13 lines · Jens Remus

arch/x86/include/asm/dwarf2.h line 15

Quoted 9 lines · Josh Poimboeuf

arch/x86/include/asm/dwarf2.h +0 -1

index b195b3c8677e..1c354f648505 100644
@@ -12,8 +12,11 @@
  	 * For the vDSO, emit both runtime unwind information and debug
  	 * symbols for the .dbg file.
  	 */
-  

Nit: Deleted blank line you introduced in "[PATCH v4 05/39] x86/asm:
Avoid emitting DWARF CFI for non-VDSO".

Indeed.

Enable sframe generation in the VDSO library so kernel and user space can unwind through it.

Signed-off-by Josh Poimboeuf <[email protected]>

Quoted 8 lines · Josh Poimboeuf

Enable sframe generation in the VDSO library so kernel and user space can unwind through it.

Signed-off-by Josh Poimboeuf <[email protected]>

arch/x86/entry/vdso/Makefile quiet_cmd_vdso2c = VDSO2C $@ · line 52

Quoted 6 lines

arch/x86/entry/vdso/Makefile +4 -0

@@ -47,13 +47,17 @@ quiet_cmd_vdso2c = VDSO2C  $@
  $(obj)/vdso-image-%.c: $(obj)/vdso%.so.dbg $(obj)/vdso%.so $(obj)/vdso2c FORCE
  	$(call if_changed,vdso2c)
+#ifdef CONFIG_AS_SFRAME
+SFRAME_CFLAGS := -Wa$(comma)-gsframe
+#endif
+

You probably erroneously mixed up C preprocessor and Makefile syntax? :-)

ifeq ($(CONFIG_AS_SFRAME),y)
SFRAME_CFLAGS := -Wa,--gsframe
endif

$(comma) does not appear to be required in this context.

kernel/unwind/user.c +4 -0

@@ -0,0 +1,59 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+* Generic interfaces for unwinding user space
+*/

kernel/unwind/user.c line 14

Quoted 5 lines · Josh Poimboeuf

kernel/unwind/user.c new file +5 -0

+int unwind_user_next(struct unwind_user_state *state)
+{
+	struct unwind_user_frame _frame;
+	struct unwind_user_frame *frame = &_frame;
+	unsigned long cfa = 0, fp, ra = 0;

Why are cfa and ra initialized to zero? Where is that important in subsequent patches?

"[PATCH v4 12/39] unwind_user: Add frame pointer support" does either unconditionally set both cfa and ra or bail out.

Introduce a generic API for unwinding user stacks.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 arch/Kconfig                      |  3 ++
 include/linux/unwind_user.h       | 15 ++++++++
 include/linux/unwind_user_types.h | 31 ++++++++++++++++
 kernel/Makefile                   |  1 +
 kernel/unwind/Makefile            |  1 +
 kernel/unwind/user.c              | 59 +++++++++++++++++++++++++++++++
 6 files changed, 110 insertions(+)
 create mode 100644 include/linux/unwind_user.h
 create mode 100644 include/linux/unwind_user_types.h
 create mode 100644 kernel/unwind/Makefile
 create mode 100644 kernel/unwind/user.c

kernel/unwind/user.c new file +4 -0

@@ -0,0 +1,59 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+* Generic interfaces for unwinding user space
+*/

kernel/unwind/user.c new file +1 -0

+}

kernel/unwind/user.c line 14

Quoted 5 lines · Josh Poimboeuf

kernel/unwind/user.c new file +5 -0

+int unwind_user_next(struct unwind_user_state *state)
+{
+       struct unwind_user_frame _frame;
+       struct unwind_user_frame *frame = &_frame;
+       unsigned long cfa = 0, fp, ra = 0;

wouldn't all the above generate compilation warnings about unused variables, potentially breaking bisection?

kernel/unwind/user.c line 17

Quoted 4 lines

kernel/unwind/user.c new file +3 -0

+
+       /* no implementation yet */
+       -EINVAL;

return missing?

kernel/unwind/user.c new file +20 -0

+int unwind_user_next(struct unwind_user_state *state)
+{
+	struct unwind_user_frame _frame;
+	struct unwind_user_frame *frame = &_frame;
+	unsigned long cfa = 0, fp, ra = 0;
+
+	/* no implementation yet */
+	-EINVAL;
+}
+
+int unwind_user_start(struct unwind_user_state *state)
+{
+	struct pt_regs *regs = task_pt_regs(current);
+
+	memset(state, 0, sizeof(*state));
+
+	if (!current->mm || !user_mode(regs)) {
+		state->done = true;
+		return -EINVAL;
+	}

kernel/unwind/user.c new file +20 -0

+int unwind_user(struct unwind_stacktrace *trace, unsigned int max_entries)
+{
+	struct unwind_user_state state;
+
+	trace->nr = 0;
+
+	if (!max_entries)
+		return -EINVAL;
+
+	if (!current->mm)
+		return 0;
+
+	for_each_user_frame(&state) {
+		trace->entries[trace->nr++] = state.ip;
+		if (trace->nr >= max_entries)
+			break;
+	}
+
+	return 0;
+}

Quoted 17 lines · On Tue, 21 Jan 2025 18:31:03 -0800 Josh Poimboeuf <[email protected]> wrote:

kernel/unwind/user.c new file +17 -0

+int unwind_user_start(struct unwind_user_state *state)
+{
+	struct pt_regs *regs = task_pt_regs(current);
+
+	memset(state, 0, sizeof(*state));
+
+	if (!current->mm || !user_mode(regs)) {
+		state->done = true;
+		return -EINVAL;
+	}
+
+	state->type = UNWIND_USER_TYPE_NONE;
+
+	state->ip = instruction_pointer(regs);
+	state->sp = user_stack_pointer(regs);
+	state->fp = frame_pointer(regs);
+

kernel/unwind/user.c line 39

Quoted 3 lines

kernel/unwind/user.c new file +3 -0

+	return 0;
+}
+

I know this is just an introductory of the interface, but this should really have kerneldoc attached to it, as I have no idea what these are supposed to be doing. This patch is meaningless without it. The change log is useless too.

Add optional support for user space frame pointer unwinding. If supported, the arch needs to enable CONFIG_HAVE_UNWIND_USER_FP and define ARCH_INIT_USER_FP_FRAME.

By encoding the frame offsets in struct unwind_user_frame, much of this code can also be reused for future unwinder implementations like sframe.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 arch/Kconfig                      |  4 +++
 include/asm-generic/unwind_user.h |  9 ++++++
 include/linux/unwind_user_types.h |  1 +
 kernel/unwind/user.c              | 49 +++++++++++++++++++++++++++++--
 4 files changed, 60 insertions(+), 3 deletions(-)
 create mode 100644 include/asm-generic/unwind_user.h

arch/Kconfig +4 -0

index c6fa2b3ecbc6..cf996cbb8142 100644
@@ -438,6 +438,10 @@ config HAVE_HARDLOCKUP_DETECTOR_ARCH
 config UNWIND_USER
        bool
 
+config HAVE_UNWIND_USER_FP
+       bool
+       select UNWIND_USER
+
 config AS_SFRAME
        def_bool $(as-instr,.cfi_sections .sframe\n.cfi_startproc\n.cfi_endproc)
 

Quoted 8 lines · Josh Poimboeuf

Add optional support for user space frame pointer unwinding. If supported, the arch needs to enable CONFIG_HAVE_UNWIND_USER_FP and define ARCH_INIT_USER_FP_FRAME.

By encoding the frame offsets in struct unwind_user_frame, much of this code can also be reused for future unwinder implementations like sframe.

Quoted 9 lines

Signed-off-by Josh Poimboeuf <[email protected]>

---
 arch/Kconfig                      |  4 +++
 include/asm-generic/unwind_user.h |  9 ++++++
 include/linux/unwind_user_types.h |  1 +
 kernel/unwind/user.c              | 49 +++++++++++++++++++++++++++++--
 4 files changed, 60 insertions(+), 3 deletions(-)
 create mode 100644 include/asm-generic/unwind_user.h

Do you plan to reuse this logic for stack unwinding done by perf subsystem in perf_callchain_user()? See is_uprobe_at_func_entry() parts and also fixup_uretprobe_trampoline_entries() for some of the quirks that have to be taken into account when doing frame pointer-based unwinding. It would be great not to lose those in this new reimplementation.

Not sure what's the best way to avoid duplicating the logic, but I thought I'd bring that up.

Quoted 9 lines

Do you plan to reuse this logic for stack unwinding done by perf subsystem in perf_callchain_user()? See is_uprobe_at_func_entry() parts and also fixup_uretprobe_trampoline_entries() for some of the quirks that have to be taken into account when doing frame pointer-based unwinding. It would be great not to lose those in this new reimplementation.

Not sure what's the best way to avoid duplicating the logic, but I thought I'd bring that up.

Indeed! That was on the todo list and somehow evaporated.

get_segment_base() will be used by the unwind_user code, so make it global and rename it so it doesn't conflict with a KVM function of the same name.

Quoted 3 lines · Josh Poimboeuf

get_segment_base() will be used by the unwind_user code, so make it global and rename it so it doesn't conflict with a KVM function of the same name.

Should it not also get moved out of the perf code in this case?

arch/x86/events/core.c valid_user_frame(const void __user *fp, unsigned long size) · line 2796

Quoted 13 lines · On Tue, 21 Jan 2025 18:31:06 -0800 Josh Poimboeuf <[email protected]> wrote:

arch/x86/events/core.c +1 -1

index c75c482d4c52..23ac6343cf86 100644
@@ -2790,7 +2790,7 @@ valid_user_frame(const void __user *fp, unsigned long size)
 	return __access_ok(fp, size);
 }
 
-static unsigned long get_segment_base(unsigned int segment)
+unsigned long segment_base_address(unsigned int segment)
 {
 	struct desc_struct *desc;
 	unsigned int idx = segment >> 3;

As this requires interrupts disabled, and if you do move this out of this file, you probably should add:

	lockdep_assert_irqs_disabled();

In preparation for unwinding user space stacks with sframe, add basic sframe compile infrastructure and support for reading the .sframe section header.

sframe_add_section() reads the header and unconditionally returns an error, so it's not very useful yet. A subsequent patch will improve that.

Signed-off-by Josh Poimboeuf <[email protected]>

---
 arch/Kconfig           |   3 +
 include/linux/sframe.h |  36 +++++++++++
 kernel/unwind/Makefile |   3 +-
 kernel/unwind/sframe.c | 136 +++++++++++++++++++++++++++++++++++++++++
 kernel/unwind/sframe.h |  71 +++++++++++++++++++++
 5 files changed, 248 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/sframe.h
 create mode 100644 kernel/unwind/sframe.c
 create mode 100644 kernel/unwind/sframe.h

include/linux/sframe.h new file +5 -0

+static inline int sframe_remove_section(unsigned long sframe_addr) { return -ENOSYS; }
+
+#endif /* CONFIG_HAVE_UNWIND_USER_SFRAME */
+
+#endif /* _LINUX_SFRAME_H */

kernel/unwind/sframe.c new file +4 -0

+static int sframe_read_header(struct sframe_section *sec)
+{
+       unsigned long header_end, fdes_start, fdes_end, fres_start, fres_end;
+       struct sframe_header shdr;

kernel/unwind/sframe.c new file +16 -0

+       if (fres_start < fdes_end || fres_end > sec->sframe_end) {
+               dbg("inconsistent fde/fre offsets\n");
+               return -EINVAL;
+       }
+
+       sec->num_fdes           = num_fdes;
+       sec->fdes_start         = fdes_start;
+       sec->fres_start         = fres_start;
+       sec->fres_end           = fres_end;
+
+       sec->ra_off             = shdr.cfa_fixed_ra_offset;
+       sec->fp_off             = shdr.cfa_fixed_fp_offset;
+
+       return 0;
+}
+

kernel/unwind/sframe.h new file +47 -0

new file mode 100644
index 000000000000..e9bfccfaf5b4
@@ -0,0 +1,71 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ * From https://www.sourceware.org/binutils/docs/sframe-spec.html
+ */
+#ifndef _SFRAME_H
+#define _SFRAME_H
+
+#include <linux/types.h>
+
+#define SFRAME_VERSION_1                       1
+#define SFRAME_VERSION_2                       2
+#define SFRAME_MAGIC                           0xdee2
+
+#define SFRAME_F_FDE_SORTED                    0x1
+#define SFRAME_F_FRAME_POINTER                 0x2
+
+#define SFRAME_ABI_AARCH64_ENDIAN_BIG          1
+#define SFRAME_ABI_AARCH64_ENDIAN_LITTLE       2
+#define SFRAME_ABI_AMD64_ENDIAN_LITTLE         3
+
+#define SFRAME_FDE_TYPE_PCINC                  0
+#define SFRAME_FDE_TYPE_PCMASK                 1
+
+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;
+
+#define SFRAME_HEADER_SIZE(header) \
+       ((sizeof(struct sframe_header) + header.auxhdr_len))
+
+#define SFRAME_AARCH64_PAUTH_KEY_A             0
+#define SFRAME_AARCH64_PAUTH_KEY_B             1

kernel/unwind/sframe.h new file +14 -1

+
+#define SFRAME_FUNC_FRE_TYPE(data)             (data & 0xf)
+#define SFRAME_FUNC_FDE_TYPE(data)             ((data >> 4) & 0x1)
+#define SFRAME_FUNC_PAUTH_KEY(data)            ((data >> 5) & 0x1)
+
+#define SFRAME_BASE_REG_FP                     0
+#define SFRAME_BASE_REG_SP                     1
+
+#define SFRAME_FRE_CFA_BASE_REG_ID(data)       (data & 0x1)
+#define SFRAME_FRE_OFFSET_COUNT(data)          ((data >> 1) & 0xf)
+#define SFRAME_FRE_OFFSET_SIZE(data)           ((data >> 5) & 0x3)
+#define SFRAME_FRE_MANGLED_RA_P(data)          ((data >> 7) & 0x1)
+
+#endif /* _SFRAME_H */
--

2.48.1

Quoted 1 line · Josh Poimboeuf

+static inline int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, unsigned long text_start, unsigned long text_end) { return -ENOSYS; }

nit: very-very long, wrap it?

kernel/unwind/sframe.c line 40

Quoted 3 lines

kernel/unwind/sframe.c new file +3 -0

+       if (shdr.preamble.magic != SFRAME_MAGIC ||
+           shdr.preamble.version != SFRAME_VERSION_2 ||
+           !(shdr.preamble.flags & SFRAME_F_FDE_SORTED) ||

probably more a question to Indu, but why is this sorting not mandatory and part of SFrame "standard"? How realistically non-sorted FDEs would work in practice? Ain't nobody got time to sort them just to unwind the stack...

Quoted 1 line

+ if (!shdr.num_fdes || !shdr.num_fres) {

given SFRAME_F_FRAME_POINTER in the header, is it really that nonsensical and illegal to have zero FDEs/FREs? Maybe we should allow that?

kernel/unwind/sframe.c line 52

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

Quoted 7 lines

kernel/unwind/sframe.c new file +7 -0

+               dbg("header doesn't fit in section\n");
+               return -EINVAL;
+       }
+
+       num_fdes   = shdr.num_fdes;
+       fdes_start = header_end + shdr.fdes_off;
+       fdes_end   = fdes_start + (num_fdes * sizeof(struct sframe_fde));

kernel/unwind/sframe.c line 63

Quoted 4 lines

kernel/unwind/sframe.c new file +4 -0

+
+       fres_start = header_end + shdr.fres_off;
+       fres_end   = fres_start + shdr.fre_len;
+

maybe use check_add_overflow() in all the above calculation, at least on 32-bit arches this all can overflow and it's not clear if below sanity check detects all possible overflows

Quoted 24 lines

kernel/unwind/sframe.h new file +24 -0

+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;
+
+struct sframe_fde {
+       s32     start_addr;
+       u32     func_size;
+       u32     fres_off;
+       u32     fres_num;

kernel/unwind/sframe.h line 57

Quoted 4 lines

kernel/unwind/sframe.h new file +4 -0

+       u8      info;
+       u8      rep_size;
+       u16 padding;
+} __packed;

I couldn't understand from SFrame itself, but why do sframe_header, sframe_preamble, and sframe_fde have to be marked __packed, if it's all naturally aligned (intentionally and by design)?..

Quoted 3 lines

given SFRAME_F_FRAME_POINTER in the header, is it really that nonsensical and illegal to have zero FDEs/FREs? Maybe we should allow that?

It would seem a bit silly to create an empty .sframe section just to set that SFRAME_F_FRAME_POINTER bit. Regardless, there's nothing the kernel can do with that.

Quoted 7 lines

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {  

Quoted 1 line

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Quoted 15 lines · On Fri, 24 Jan 2025 11:21:59 -0800 Josh Poimboeuf <[email protected]> wrote:

Quoted 3 lines

given SFRAME_F_FRAME_POINTER in the header, is it really that nonsensical and illegal to have zero FDEs/FREs? Maybe we should allow that?

It would seem a bit silly to create an empty .sframe section just to set that SFRAME_F_FRAME_POINTER bit. Regardless, there's nothing the kernel can do with that.

Quoted 7 lines

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {  

Quoted 3 lines

Quoted 1 line

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Hmm, could that be useful for implementing a way to dynamically grow or shrink an sframe because of jits? I'm just thinking about placeholders or sohething.

Quoted 4 lines · Andrii Nakryiko

Quoted 1 line · Josh Poimboeuf

+static inline int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, unsigned long text_start, unsigned long text_end) { return -ENOSYS; }

nit: very-very long, wrap it?

That was intentional as it's just an empty stub, but yeah, maybe 160 chars is a bit much.

Quoted 8 lines

kernel/unwind/sframe.c line 40

Quoted 3 lines

kernel/unwind/sframe.c new file +3 -0

+       if (shdr.preamble.magic != SFRAME_MAGIC ||
+           shdr.preamble.version != SFRAME_VERSION_2 ||
+           !(shdr.preamble.flags & SFRAME_F_FDE_SORTED) ||

probably more a question to Indu, but why is this sorting not mandatory and part of SFrame "standard"? How realistically non-sorted FDEs would work in practice? Ain't nobody got time to sort them just to unwind the stack...

No idea...

Quoted 2 lines

Quoted 1 line

+ if (!shdr.num_fdes || !shdr.num_fres) {

Quoted 3 lines

given SFRAME_F_FRAME_POINTER in the header, is it really that nonsensical and illegal to have zero FDEs/FREs? Maybe we should allow that?

It would seem a bit silly to create an empty .sframe section just to set that SFRAME_F_FRAME_POINTER bit. Regardless, there's nothing the kernel can do with that.

Quoted 8 lines

kernel/unwind/sframe.c line 52

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Quoted 7 lines

Quoted 7 lines

kernel/unwind/sframe.c new file +7 -0

+               dbg("header doesn't fit in section\n");
+               return -EINVAL;
+       }
+
+       num_fdes   = shdr.num_fdes;
+       fdes_start = header_end + shdr.fdes_off;
+       fdes_end   = fdes_start + (num_fdes * sizeof(struct sframe_fde));

Quoted 8 lines

kernel/unwind/sframe.c line 63

Quoted 4 lines

kernel/unwind/sframe.c new file +4 -0

+
+       fres_start = header_end + shdr.fres_off;
+       fres_end   = fres_start + shdr.fre_len;
+

maybe use check_add_overflow() in all the above calculation, at least on 32-bit arches this all can overflow and it's not clear if below sanity check detects all possible overflows

Ok, I'll look into it.

Quoted 24 lines

Quoted 24 lines

kernel/unwind/sframe.h new file +24 -0

+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;
+
+struct sframe_fde {
+       s32     start_addr;
+       u32     func_size;
+       u32     fres_off;
+       u32     fres_num;

Quoted 8 lines

kernel/unwind/sframe.h line 57

Quoted 4 lines

kernel/unwind/sframe.h new file +4 -0

+       u8      info;
+       u8      rep_size;
+       u16 padding;
+} __packed;

I couldn't understand from SFrame itself, but why do sframe_header, sframe_preamble, and sframe_fde have to be marked __packed, if it's all naturally aligned (intentionally and by design)?..

Right, but the spec says they're all packed. Maybe the point is that some future sframe version is free to introduce unaligned fields.

Quoted 22 lines · Josh Poimboeuf

Quoted 4 lines · Andrii Nakryiko

Quoted 1 line · Josh Poimboeuf

+static inline int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, unsigned long text_start, unsigned long text_end) { return -ENOSYS; }

nit: very-very long, wrap it?

That was intentional as it's just an empty stub, but yeah, maybe 160 chars is a bit much.

Quoted 8 lines

kernel/unwind/sframe.c line 40

Quoted 3 lines

kernel/unwind/sframe.c new file +3 -0

+       if (shdr.preamble.magic != SFRAME_MAGIC ||
+           shdr.preamble.version != SFRAME_VERSION_2 ||
+           !(shdr.preamble.flags & SFRAME_F_FDE_SORTED) ||

probably more a question to Indu, but why is this sorting not mandatory and part of SFrame "standard"? How realistically non-sorted FDEs would work in practice? Ain't nobody got time to sort them just to unwind the stack...

No idea...

Quoted 2 lines

Quoted 1 line

+ if (!shdr.num_fdes || !shdr.num_fres) {

Quoted 8 lines

Quoted 3 lines

given SFRAME_F_FRAME_POINTER in the header, is it really that nonsensical and illegal to have zero FDEs/FREs? Maybe we should allow that?

It would seem a bit silly to create an empty .sframe section just to set that SFRAME_F_FRAME_POINTER bit. Regardless, there's nothing the kernel can do with that.

Yes, in theory, it is allowed (as per the specification) to have an SFrame section with zero number of FDEs/FREs. But since such a section will not be useful, I share the opinion that it makes sense to disallow it in the current unwinding contexts, for now (JIT usecase may change things later).

SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all.

Quoted 10 lines

Quoted 8 lines

kernel/unwind/sframe.c line 52

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Quoted 52 lines

Quoted 16 lines

kernel/unwind/sframe.c line 63

Quoted 12 lines

kernel/unwind/sframe.c new file +11 -0

+               dbg("header doesn't fit in section\n");
+               return -EINVAL;
+       }
+
+       num_fdes   = shdr.num_fdes;
+       fdes_start = header_end + shdr.fdes_off;
+       fdes_end   = fdes_start + (num_fdes * sizeof(struct sframe_fde));
+
+       fres_start = header_end + shdr.fres_off;
+       fres_end   = fres_start + shdr.fre_len;
+

maybe use check_add_overflow() in all the above calculation, at least on 32-bit arches this all can overflow and it's not clear if below sanity check detects all possible overflows

Ok, I'll look into it.

Quoted 32 lines

Quoted 18 lines

kernel/unwind/sframe.h new file +18 -0

+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;

kernel/unwind/sframe.h line 57

Quoted 10 lines

kernel/unwind/sframe.h new file +10 -0

+
+struct sframe_fde {
+       s32     start_addr;
+       u32     func_size;
+       u32     fres_off;
+       u32     fres_num;
+       u8      info;
+       u8      rep_size;
+       u16 padding;
+} __packed;

I couldn't understand from SFrame itself, but why do sframe_header, sframe_preamble, and sframe_fde have to be marked __packed, if it's all naturally aligned (intentionally and by design)?..

Quoted 3 lines

Right, but the spec says they're all packed. Maybe the point is that some future sframe version is free to introduce unaligned fields.

SFrame specification aims to keep SFrame header and SFrame FDE members at aligned boundaries in future versions.

Only SFrame FRE related accesses may have unaligned accesses.

Quoted 6 lines

Yes, in theory, it is allowed (as per the specification) to have an SFrame section with zero number of FDEs/FREs. But since such a section will not be useful, I share the opinion that it makes sense to disallow it in the current unwinding contexts, for now (JIT usecase may change things later).

I disagree, actually. If it's a legal thing, it shouldn't be randomly rejected. If we later make use of that, we'd have to worry not to accidentally cause problems on older kernels that arbitrarily rejected empty FDE just because it didn't make sense at some point (without causing any issues).

Quoted 9 lines

SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Let's invert this. Is there any reason why it shouldn't be supported? ;)

But what if we take a struct-of-arrays approach and represent it more like:

struct FDE_and_FREs {
    struct sframe_func_desc_entry fde_metadata;
    u8|u16|u32 start_addrs[N]; /* can extend to u64 as well */
    u8 sfre_infos[N];
    u8 offsets8[M8];
    u16 offsets16[M16] __aligned(2);
    u32 offsets32[M32] __aligned(4);
    /* we can naturally extend to support also u64 offsets */
};

i.e., we split all FRE records into their three constituents: start addresses, info bytes, and then each FRE can fall into either 8-, 16-, or 32-bit offsets "bucket". We collect all the offsets, depending on their size, into these aligned offsets{8,16,32} arrays (with natural extension to 64 bits, if necessary), with at most wasting 1-3 bytes to ensure proper alignment everywhere.

Note, at this point we need to decide if we want to make FREs binary searchable or not.

If not, we don't really need anything extra. As we process each start_addrs[i] and sfre_infos[i] to find matching FRE, we keep track of how many 8-, 16-, and 32-bit offsets already processed FREs consumed, and when we find the right one, we know exactly the starting index within offset{8,16,32}. Done.

But if we were to make FREs binary searchable, we need to basically have an index of offset pointers to quickly find offsetsX[j] position corresponding to FRE #i. For that, we can have an extra array right next to start_addrs, "semantically parallel" to it:

u8|u16|u32 start_addrs[N];
u8|u16|u32 offset_idxs[N];

Quoted 7 lines · Andrii Nakryiko

Quoted 6 lines

Yes, in theory, it is allowed (as per the specification) to have an SFrame section with zero number of FDEs/FREs. But since such a section will not be useful, I share the opinion that it makes sense to disallow it in the current unwinding contexts, for now (JIT usecase may change things later).

Quoted 5 lines

I disagree, actually. If it's a legal thing, it shouldn't be randomly rejected. If we later make use of that, we'd have to worry not to accidentally cause problems on older kernels that arbitrarily rejected empty FDE just because it didn't make sense at some point (without causing any issues).

If such older kernels don't do anything with the section anyway, what's the point of pretending they do?

Returning an error would actually make more sense as it communicates that the kernel doesn't support whatever hypothetical thing you're trying to do with 0 FDEs.

Quoted 11 lines

Quoted 11 lines

SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all.

Quoted 9 lines

Quoted 8 lines

kernel/unwind/sframe.c line 52

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

Quoted 3 lines

Quoted 1 line

Quoted 1 line

I suppose so, but again I'm not seeing any reason to support that.

Let's invert this. Is there any reason why it shouldn't be supported? ;)

It's simple, we don't add code to "support" some vague hypothetical.

For whatever definition of "support", since there's literally nothing the kernel can do with that.

Quoted 13 lines

But what if we take a struct-of-arrays approach and represent it more like:

struct FDE_and_FREs {
    struct sframe_func_desc_entry fde_metadata;
    u8|u16|u32 start_addrs[N]; /* can extend to u64 as well */
    u8 sfre_infos[N];
    u8 offsets8[M8];
    u16 offsets16[M16] __aligned(2);
    u32 offsets32[M32] __aligned(4);
    /* we can naturally extend to support also u64 offsets */
};

Quoted 6 lines

i.e., we split all FRE records into their three constituents: start addresses, info bytes, and then each FRE can fall into either 8-, 16-, or 32-bit offsets "bucket". We collect all the offsets, depending on their size, into these aligned offsets{8,16,32} arrays (with natural extension to 64 bits, if necessary), with at most wasting 1-3 bytes to ensure proper alignment everywhere.

Makes sense. Though I also have another idea below.

Quoted 9 lines

Note, at this point we need to decide if we want to make FREs binary searchable or not.

If not, we don't really need anything extra. As we process each start_addrs[i] and sfre_infos[i] to find matching FRE, we keep track of how many 8-, 16-, and 32-bit offsets already processed FREs consumed, and when we find the right one, we know exactly the starting index within offset{8,16,32}. Done.

Quoted 7 lines

But if we were to make FREs binary searchable, we need to basically have an index of offset pointers to quickly find offsetsX[j] position corresponding to FRE #i. For that, we can have an extra array right next to start_addrs, "semantically parallel" to it:

u8|u16|u32 start_addrs[N];
u8|u16|u32 offset_idxs[N];

Binary search would definitely help. I did a crude histogram for "FREs per FDE" for a few binaries on my test system:

gdb (the biggest binary on my test system):

10th Percentile: 1
20th Percentile: 1
30th Percentile: 1
40th Percentile: 3
50th Percentile: 5
60th Percentile: 8
70th Percentile: 11
80th Percentile: 14
90th Percentile: 16
100th Percentile: 472

bash:

10th Percentile: 1
20th Percentile: 1
30th Percentile: 3
40th Percentile: 5
50th Percentile: 7
60th Percentile: 9
70th Percentile: 12
80th Percentile: 16
90th Percentile: 17
100th Percentile: 46

glibc:

10th Percentile: 1
20th Percentile: 1
30th Percentile: 1
40th Percentile: 1
50th Percentile: 4
60th Percentile: 6
70th Percentile: 9
80th Percentile: 14
90th Percentile: 16
100th Percentile: 44

libpython:

10th Percentile: 1
20th Percentile: 3
30th Percentile: 4
40th Percentile: 6
50th Percentile: 8
60th Percentile: 11
70th Percentile: 12
80th Percentile: 16
90th Percentile: 20
100th Percentile: 112

So binary search would help in a lot of cases.

However, if we're going that route, we might want to even consider a completely revamped data layout. For example:

One insight is that the vast majority of (cfa, fp, ra) tuples aren't unique. They could be deduped by storing the unique tuples in a standalone 'fre_data' array which is referenced by another address-specific array.

  struct fre_data {
        s8|s16|s32 cfa, fp, ra;
        u8 info;
  };
  struct fre_data fre_data[num_fre_data];

The storage sizes of cfa/fp/ra can be a constant specified in the global sframe header. It's fine all being the same size as it looks like this array wouldn't typically be more than a few hundred entries anyway.

Then there would be an array of sorted FRE entries which reference the fre_data[] entries:

  struct fre {
        s32|s64 start_address;
        u8|u16 fre_data_idx;

  } __packed;
  struct fre fres[num_fres];

(For alignment reasons that should probably be two separate arrays, even though not ideal for cache locality)

Here again the field storage sizes would be specified in the global sframe header.

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

But wait, there's more...

The binary search could be made significantly faster using a small fast lookup array which is indexed evenly across the text address offset space, similar to what ORC does:

  u32 fre_chunks[num_chunks];

The text address space (starting at offset 0) can be split into 'num_chunks' chunks of size 'chunk_size'. The value of fre_chunks[offset/chunk_size] is an index into the fres[] array.

Taking my gdb binary as an example:

.text is 6417058 bytes, with 146997 total sframe FREs. Assuming a chunk size of 1024, fre_chunks[] needs 6417058/1024 = 6267 entries.

For unwinding at text offset 0x400000, the index into fre_chunks[] would be 0x400000/1024 = 4096. If fre_chunks[4096] == 96074 and fre_chunks[4096+1] == 96098, you need only do a binary search of the 24 entries between fres[96074] && fres[96098] rather than searching the entire 146997 byte array.

.sframe size calculation:

    374 unique fre_data entries (out of 146997 total FREs!)
    = 374 * (2 * 3) = 2244 bytes

    146997 fre entries
    = 146997 * (4 + 2) = 881982 bytes

    .text size 6417058 (chunk_size = 1024, num_chunks=6267)
    = 6267 * 8 = 43869 bytes

Approximate total .sframe size would be 2244 + 881982 + 8192 = 906k, plus negligible header size. Which is smaller than the v2 .sframe on my gdb binary (985k).

With the chunked lookup table, the avg lookup is:

log2(146997/6267) = ~4.5 iterations

whereas a full binary search would be:

log2(146997) = 17 iterations

So assuming I got all that math right, it's over 3x faster and the binary is smaller (or at least should be roughly comparable).

Quoted 1 line

Quoted 1 line

0x0000000000775dd8 + 0x00000000007d3271 + 0x0000000011ad621c

Quoted 1 line

Quoted 1 line

hex(0x0000000011ad621c + 0x000000000b00e640)

Quoted 1 line

Quoted 1 line

0x000000001e600000 - 0x1cae485c

Of course the downside is it's an all new format. Presumably the linker would need to do more work than it's currently doing, e.g., find all the duplicates and set up the data accordingly.

--
Josh

On Tue, Jan 28, 2025 at 6:02 PM Josh Poimboeuf <[email protected]> wrote:
I'm not sure about this chunked lookup approach for arbitrary user space applications. Those executable sections can be a) big and b) discontiguous. E.g., one of the production binaries I looked at. Here are its three main executable sections:

...
[17] .bolt.org.text PROGBITS 000000000b00e640 0ae0d640

       0000000011ad621c  0000000000000000  AX       0     0     64
...
  [48] .text             PROGBITS         000000001e600000  1ce00000
       0000000000775dd8  0000000000000000  AX       0     0     2097152
  [49] .text.cold        PROGBITS         000000001ed75e00  1d575e00
       00000000007d3271  0000000000000000  AX       0     0     64

...

Total text size is about 300MB:

Quoted 1 line

Quoted 1 line

Quoted 1 line

0x0000000000775dd8 + 0x00000000007d3271 + 0x0000000011ad621c

312603237

Section #17 ends at:

Quoted 1 line

Quoted 1 line

Quoted 1 line

hex(0x0000000011ad621c + 0x000000000b00e640)

'0x1cae485c'

While .text starts at 000000001e600000, so we have a gap of ~28MB:

Quoted 1 line

Quoted 1 line

Quoted 1 line

0x000000001e600000 - 0x1cae485c

28424100

So unless we do something more clever to support multiple discontiguous chunks, this seems like a bad fit for user space.

I think having all this just binary searchable is already a big win anyways and should be plenty fast, no?

Quoted 7 lines · Andrii Nakryiko

Quoted 6 lines

Yes, in theory, it is allowed (as per the specification) to have an SFrame section with zero number of FDEs/FREs. But since such a section will not be useful, I share the opinion that it makes sense to disallow it in the current unwinding contexts, for now (JIT usecase may change things later).

Quoted 5 lines

I disagree, actually. If it's a legal thing, it shouldn't be randomly rejected. If we later make use of that, we'd have to worry not to accidentally cause problems on older kernels that arbitrarily rejected empty FDE just because it didn't make sense at some point (without causing any issues).

If such older kernels don't do anything with the section anyway, what's the point of pretending they do?

Returning an error would actually make more sense as it communicates that the kernel doesn't support whatever hypothetical thing you're trying to do with 0 FDEs.

Quoted 9 lines

Quoted 9 lines

SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

kernel/unwind/sframe.c new file +6 -0

+               dbg("no fde/fre entries\n");
+               return -EINVAL;
+       }
+
+       header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr);
+       if (header_end >= sec->sframe_end) {

Quoted 5 lines

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

if we allow zero FDEs/FREs, header_end == sec->sframe_end is legal, right?

I suppose so, but again I'm not seeing any reason to support that.

Let's invert this. Is there any reason why it shouldn't be supported? ;)

It's simple, we don't add code to "support" some vague hypothetical.

For whatever definition of "support", since there's literally nothing the kernel can do with that.

Quoted 12 lines

But what if we take a struct-of-arrays approach and represent it more like:

struct FDE_and_FREs {
     struct sframe_func_desc_entry fde_metadata;
     u8|u16|u32 start_addrs[N]; /* can extend to u64 as well */
     u8 sfre_infos[N];
     u8 offsets8[M8];
     u16 offsets16[M16] __aligned(2);
     u32 offsets32[M32] __aligned(4);
     /* we can naturally extend to support also u64 offsets */
};

Quoted 6 lines

i.e., we split all FRE records into their three constituents: start addresses, info bytes, and then each FRE can fall into either 8-, 16-, or 32-bit offsets "bucket". We collect all the offsets, depending on their size, into these aligned offsets{8,16,32} arrays (with natural extension to 64 bits, if necessary), with at most wasting 1-3 bytes to ensure proper alignment everywhere.

Makes sense. Though I also have another idea below.

Quoted 9 lines

Note, at this point we need to decide if we want to make FREs binary searchable or not.

If not, we don't really need anything extra. As we process each start_addrs[i] and sfre_infos[i] to find matching FRE, we keep track of how many 8-, 16-, and 32-bit offsets already processed FREs consumed, and when we find the right one, we know exactly the starting index within offset{8,16,32}. Done.

Quoted 7 lines

But if we were to make FREs binary searchable, we need to basically have an index of offset pointers to quickly find offsetsX[j] position corresponding to FRE #i. For that, we can have an extra array right next to start_addrs, "semantically parallel" to it:

u8|u16|u32 start_addrs[N];
u8|u16|u32 offset_idxs[N];

Binary search would definitely help. I did a crude histogram for "FREs per FDE" for a few binaries on my test system:

gdb (the biggest binary on my test system):

10th Percentile: 1
20th Percentile: 1
30th Percentile: 1
40th Percentile: 3
50th Percentile: 5
60th Percentile: 8
70th Percentile: 11
80th Percentile: 14
90th Percentile: 16
100th Percentile: 472

bash:

10th Percentile: 1
20th Percentile: 1
30th Percentile: 3
40th Percentile: 5
50th Percentile: 7
60th Percentile: 9
70th Percentile: 12
80th Percentile: 16
90th Percentile: 17
100th Percentile: 46

glibc:

10th Percentile: 1
20th Percentile: 1
30th Percentile: 1
40th Percentile: 1
50th Percentile: 4
60th Percentile: 6
70th Percentile: 9
80th Percentile: 14
90th Percentile: 16
100th Percentile: 44

libpython:

10th Percentile: 1
20th Percentile: 3
30th Percentile: 4
40th Percentile: 6
50th Percentile: 8
60th Percentile: 11
70th Percentile: 12
80th Percentile: 16
90th Percentile: 20
100th Percentile: 112

So binary search would help in a lot of cases.

However, if we're going that route, we might want to even consider a completely revamped data layout. For example:

One insight is that the vast majority of (cfa, fp, ra) tuples aren't unique. They could be deduped by storing the unique tuples in a standalone 'fre_data' array which is referenced by another address-specific array.

   struct fre_data {
	s8|s16|s32 cfa, fp, ra;
	u8 info;
   };
   struct fre_data fre_data[num_fre_data];

The storage sizes of cfa/fp/ra can be a constant specified in the global sframe header. It's fine all being the same size as it looks like this array wouldn't typically be more than a few hundred entries anyway.

Then there would be an array of sorted FRE entries which reference the fre_data[] entries:

   struct fre {
   	s32|s64 start_address;
	u8|u16 fre_data_idx;
	
   } __packed;
   struct fre fres[num_fres];

(For alignment reasons that should probably be two separate arrays, even though not ideal for cache locality)

Here again the field storage sizes would be specified in the global sframe header.

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

But wait, there's more...

The binary search could be made significantly faster using a small fast lookup array which is indexed evenly across the text address offset space, similar to what ORC does:

   u32 fre_chunks[num_chunks];

The text address space (starting at offset 0) can be split into 'num_chunks' chunks of size 'chunk_size'. The value of fre_chunks[offset/chunk_size] is an index into the fres[] array.

Taking my gdb binary as an example:

.text is 6417058 bytes, with 146997 total sframe FREs. Assuming a chunk size of 1024, fre_chunks[] needs 6417058/1024 = 6267 entries.

For unwinding at text offset 0x400000, the index into fre_chunks[] would be 0x400000/1024 = 4096. If fre_chunks[4096] == 96074 and fre_chunks[4096+1] == 96098, you need only do a binary search of the 24 entries between fres[96074] && fres[96098] rather than searching the entire 146997 byte array.

.sframe size calculation:

     374 unique fre_data entries (out of 146997 total FREs!)
     = 374 * (2 * 3) = 2244 bytes

     146997 fre entries
     = 146997 * (4 + 2) = 881982 bytes

     .text size 6417058 (chunk_size = 1024, num_chunks=6267)
     = 6267 * 8 = 43869 bytes

Approximate total .sframe size would be 2244 + 881982 + 8192 = 906k, plus negligible header size. Which is smaller than the v2 .sframe on my gdb binary (985k).

With the chunked lookup table, the avg lookup is:

   log2(146997/6267) = ~4.5 iterations

whereas a full binary search would be:

   log2(146997) = 17 iterations

So assuming I got all that math right, it's over 3x faster and the binary is smaller (or at least should be roughly comparable).

Of course the downside is it's an all new format. Presumably the linker would need to do more work than it's currently doing, e.g., find all the duplicates and set up the data accordingly.

Quoted 8 lines · Josh Poimboeuf

However, if we're going that route, we might want to even consider a completely revamped data layout. For example:

One insight is that the vast majority of (cfa, fp, ra) tuples aren't unique. They could be deduped by storing the unique tuples in a standalone 'fre_data' array which is referenced by another address-specific array.

Quoted 6 lines

   struct fre_data {
	s8|s16|s32 cfa, fp, ra;
	u8 info;
   };
   struct fre_data fre_data[num_fre_data];

We had the same observation at the time of SFrame V1. And this method of compaction (deduped tuples) was brain-stormed a bit. Back then, the costs were thought to be:
- more work at build time.
- an additional data access once the FRE is found (as there is
indirection).

So it was really compaction at the costs above. We did steer towards simplicity and the SFrame FRE is what it stands today.

The difference in the pros and cons now from then:
- pros: helps mitigate unaligned accesses
- cons: interferes slightly with the design goal of efficient addition and
removal of stack trace information per function for JIT. Think "removal" as the set of actions necessary for addressing fragmentation in SFrame section data in JIT usecase.

Quoted 4 lines

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

Splitting out information (start_address) to an FDE (as done in V1/V2) has the benefit that a job like relocating information is proportional to O(NumFunctions).

In the case above, IIUC, where the proposal puts start_address in the FRE, these costs will be (much) higher.

In addition, not being able to identify stack trace information per function will affect the JIT usecase. We need to able to mark stack trace information stale for functions in JIT environment.

Quoted 26 lines · Indu Bhagat

Quoted 8 lines · Josh Poimboeuf

However, if we're going that route, we might want to even consider a completely revamped data layout. For example:

One insight is that the vast majority of (cfa, fp, ra) tuples aren't unique. They could be deduped by storing the unique tuples in a standalone 'fre_data' array which is referenced by another address-specific array.

Quoted 6 lines

    struct fre_data {
	s8|s16|s32 cfa, fp, ra;
	u8 info;
    };
    struct fre_data fre_data[num_fre_data];

We had the same observation at the time of SFrame V1. And this method of compaction (deduped tuples) was brain-stormed a bit. Back then, the costs were thought to be:
- more work at build time.
- an additional data access once the FRE is found (as there is
indirection).

So it was really compaction at the costs above. We did steer towards simplicity and the SFrame FRE is what it stands today.

Quoted 6 lines

The difference in the pros and cons now from then:
- pros: helps mitigate unaligned accesses
- cons: interferes slightly with the design goal of efficient addition and
removal of stack trace information per function for JIT. Think "removal" as the set of actions necessary for addressing fragmentation in SFrame section data in JIT usecase.

If fre_data[] is allowed to have duplicates then the deduping could be optional.

Quoted 9 lines

Quoted 4 lines

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

Splitting out information (start_address) to an FDE (as done in V1/V2) has the benefit that a job like relocating information is proportional to O(NumFunctions).

Quoted 2 lines

In the case above, IIUC, where the proposal puts start_address in the FRE, these costs will be (much) higher.

I'm not sure I follow, is this referring to the link-time work of sorting things?

Quoted 3 lines

In addition, not being able to identify stack trace information per function will affect the JIT usecase. We need to able to mark stack trace information stale for functions in JIT environment.

Maybe, though it's hard to really say how any of these changes would affect JIT without knowing what those interfaces are going to look like.

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

Quoted 4 lines · Josh Poimboeuf

Note FDEs aren't even needed here as the unwinder doesn't need to know when a function begins/ends. The only info needed by the unwinder is just the fre_data struct. So a simple binary search of fres[] is all that's really needed.

In SFrame V2 FDEs specify ranges bound by function start address and length. FREs in contrast specify open ranges bounded by start address. Their effect ends either with the next FRE becoming into effect or when their FDE range ends.
This concept enables holes in the .text section which do not have any valid FDE/FRE information associated.

Your proposal lacks some sort of mechanism to replicate those holes. It could be FDEs with a flag (or no offsets?) that specifies their range has no valid information.

Quoted 34 lines

Quoted 34 lines

Quoted 23 lines

Quoted 23 lines

kernel/unwind/sframe.h new file +23 -0

+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;
+
+struct sframe_fde {
+       s32     start_addr;
+       u32     func_size;
+       u32     fres_off;

Quoted 8 lines

kernel/unwind/sframe.h line 57

Quoted 5 lines

kernel/unwind/sframe.h new file +5 -0

+       u32     fres_num;
+       u8      info;
+       u8      rep_size;
+       u16 padding;
+} __packed;

I couldn't understand from SFrame itself, but why do sframe_header, sframe_preamble, and sframe_fde have to be marked __packed, if it's all naturally aligned (intentionally and by design)?..

Right, but the spec says they're all packed. Maybe the point is that some future sframe version is free to introduce unaligned fields.

Quoted 4 lines

SFrame specification aims to keep SFrame header and SFrame FDE members at aligned boundaries in future versions.

Only SFrame FRE related accesses may have unaligned accesses.

Yeah, and it's actually bothering me quite a lot 🙂 I have a tentative proposal, maybe we can discuss this for SFrame v3? Let me briefly outline the idea.

So, currently in v2, FREs within FDEs use an array-of-structs layout. If we use preudo-C type definitions, it would be something like this for FDE + its FREs:

struct FDE_and_FREs {
     struct sframe_func_desc_entry fde_metadata;

     union FRE {
         struct FRE8 {
             u8 sfre_start_address;
             u8 sfre_info;
             u8|u16|u32 offsets[M];
         }
         struct FRE16 {
             u16 sfre_start_address;
             u16 sfre_info;
             u8|u16|u32 offsets[M];
         }
         struct FRE32 {
             u32 sfre_start_address;
             u32 sfre_info;
             u8|u16|u32 offsets[M];
         }
     } fres[N] __packed;
};

where all fres[i]s are one of those FRE8/FRE16/FRE32, so start addresses have the same size, but each FRE has potentially different offsets sizing, so there is no common alignment, and so everything has to be packed and unaligned.

But what if we take a struct-of-arrays approach and represent it more like:

struct FDE_and_FREs {
     struct sframe_func_desc_entry fde_metadata;
     u8|u16|u32 start_addrs[N]; /* can extend to u64 as well */
     u8 sfre_infos[N];
     u8 offsets8[M8];
     u16 offsets16[M16] __aligned(2);
     u32 offsets32[M32] __aligned(4);
     /* we can naturally extend to support also u64 offsets */
};

i.e., we split all FRE records into their three constituents: start addresses, info bytes, and then each FRE can fall into either 8-, 16-, or 32-bit offsets "bucket". We collect all the offsets, depending on their size, into these aligned offsets{8,16,32} arrays (with natural extension to 64 bits, if necessary), with at most wasting 1-3 bytes to ensure proper alignment everywhere.

Note, at this point we need to decide if we want to make FREs binary searchable or not.

If not, we don't really need anything extra. As we process each start_addrs[i] and sfre_infos[i] to find matching FRE, we keep track of how many 8-, 16-, and 32-bit offsets already processed FREs consumed, and when we find the right one, we know exactly the starting index within offset{8,16,32}. Done.

But if we were to make FREs binary searchable, we need to basically have an index of offset pointers to quickly find offsetsX[j] position corresponding to FRE #i. For that, we can have an extra array right next to start_addrs, "semantically parallel" to it:

u8|u16|u32 start_addrs[N];
u8|u16|u32 offset_idxs[N];

where start_addrs[i] corresponds to offset_idxs[i], and offset_idxs[i] points to the first offset corresponding to FRE #i in offsetX[] array (depending on FRE's "bitness"). This is a bit more storage for this offset index, but for FDEs with lots of FREs this might be a worthwhile tradeoff.

Few points:
a) we can decide this "binary searchability" per-FDE, and for FDEs
with 1-2-3 FREs not bother, while those with more FREs would be searchable ones with index. So we can combine both fast lookups, natural alignment of on-disk format, and compactness. The presence of index is just another bit in FDE metadata.

b) bitness of offset_idxs[] can be coupled with bitness of
start_addrs (for simplicity), or could be completely independent and identified by FDE's metadata (2 more bits to define this just like start_addr bitness is defined). Independent probably would be my preference, with linker (or whoever will be producing .sframe data) can pick the smallest bitness that is sufficient to represent everything.

Yes, it's a bit more complicated to draw and explain, but everything will be nicely aligned, extensible to 64 bits, and (optionally at least) binary searchable. Implementation-wise on the kernel side it shouldn't be significantly more involved. Maybe the compiler would need to be a bit smarter when producing FDE data, but it's no rocket science.

Thoughts?

Quoted 4 lines

Yeah, and it's actually bothering me quite a lot 🙂 I have a tentative proposal, maybe we can discuss this for SFrame v3? Let me briefly outline the idea.

I looked at the idea below. It could work wrt unaligned accesses.

Speaking of unaligned accesses, I will ask away: Is the reason to avoid unaligned accesses performance hit or are there other practical reasons to it ?

Combining the requirements from your email and Josh's follow up:
- No unaligned accesses
- Sorted FREs

I would put compaction as a "good to have" requirement. It appears to me that any compaction will mean a sort of post-processing which will interfere with JIT usecase.

Quoted 34 lines · Andrii Nakryiko

Quoted 34 lines

Quoted 34 lines

Quoted 23 lines

Quoted 23 lines

kernel/unwind/sframe.h new file +23 -0

+struct sframe_preamble {
+       u16     magic;
+       u8      version;
+       u8      flags;
+} __packed;
+
+struct sframe_header {
+       struct sframe_preamble preamble;
+       u8      abi_arch;
+       s8      cfa_fixed_fp_offset;
+       s8      cfa_fixed_ra_offset;
+       u8      auxhdr_len;
+       u32     num_fdes;
+       u32     num_fres;
+       u32     fre_len;
+       u32     fdes_off;
+       u32     fres_off;
+} __packed;
+
+struct sframe_fde {
+       s32     start_addr;
+       u32     func_size;
+       u32     fres_off;

Quoted 8 lines

kernel/unwind/sframe.h line 57

Quoted 5 lines

kernel/unwind/sframe.h new file +5 -0

+       u32     fres_num;
+       u8      info;
+       u8      rep_size;
+       u16 padding;
+} __packed;

I couldn't understand from SFrame itself, but why do sframe_header, sframe_preamble, and sframe_fde have to be marked __packed, if it's all naturally aligned (intentionally and by design)?..

Right, but the spec says they're all packed. Maybe the point is that some future sframe version is free to introduce unaligned fields.

Quoted 8 lines

Quoted 4 lines

SFrame specification aims to keep SFrame header and SFrame FDE members at aligned boundaries in future versions.

Only SFrame FRE related accesses may have unaligned accesses.

Yeah, and it's actually bothering me quite a lot 🙂 I have a tentative proposal, maybe we can discuss this for SFrame v3? Let me briefly outline the idea.

I looked at the idea below. It could work wrt unaligned accesses.

Speaking of unaligned accesses, I will ask away: Is the reason to avoid unaligned accesses performance hit or are there other practical reasons to it ?

Quoted 74 lines

So, currently in v2, FREs within FDEs use an array-of-structs layout. If we use preudo-C type definitions, it would be something like this for FDE + its FREs:

struct FDE_and_FREs {
     struct sframe_func_desc_entry fde_metadata;

     union FRE {
         struct FRE8 {
             u8 sfre_start_address;
             u8 sfre_info;
             u8|u16|u32 offsets[M];
         }
         struct FRE16 {
             u16 sfre_start_address;
             u16 sfre_info;
             u8|u16|u32 offsets[M];
         }
         struct FRE32 {
             u32 sfre_start_address;
             u32 sfre_info;
             u8|u16|u32 offsets[M];
         }
     } fres[N] __packed;
};

where all fres[i]s are one of those FRE8/FRE16/FRE32, so start addresses have the same size, but each FRE has potentially different offsets sizing, so there is no common alignment, and so everything has to be packed and unaligned.

But what if we take a struct-of-arrays approach and represent it more like:

struct FDE_and_FREs {
     struct sframe_func_desc_entry fde_metadata;
     u8|u16|u32 start_addrs[N]; /* can extend to u64 as well */
     u8 sfre_infos[N];
     u8 offsets8[M8];
     u16 offsets16[M16] __aligned(2);
     u32 offsets32[M32] __aligned(4);
     /* we can naturally extend to support also u64 offsets */
};

i.e., we split all FRE records into their three constituents: start addresses, info bytes, and then each FRE can fall into either 8-, 16-, or 32-bit offsets "bucket". We collect all the offsets, depending on their size, into these aligned offsets{8,16,32} arrays (with natural extension to 64 bits, if necessary), with at most wasting 1-3 bytes to ensure proper alignment everywhere.

Note, at this point we need to decide if we want to make FREs binary searchable or not.

If not, we don't really need anything extra. As we process each start_addrs[i] and sfre_infos[i] to find matching FRE, we keep track of how many 8-, 16-, and 32-bit offsets already processed FREs consumed, and when we find the right one, we know exactly the starting index within offset{8,16,32}. Done.

But if we were to make FREs binary searchable, we need to basically have an index of offset pointers to quickly find offsetsX[j] position corresponding to FRE #i. For that, we can have an extra array right next to start_addrs, "semantically parallel" to it:

u8|u16|u32 start_addrs[N];
u8|u16|u32 offset_idxs[N];

where start_addrs[i] corresponds to offset_idxs[i], and offset_idxs[i] points to the first offset corresponding to FRE #i in offsetX[] array (depending on FRE's "bitness"). This is a bit more storage for this offset index, but for FDEs with lots of FREs this might be a worthwhile tradeoff.

Quoted 6 lines

Few points:
a) we can decide this "binary searchability" per-FDE, and for FDEs
with 1-2-3 FREs not bother, while those with more FREs would be searchable ones with index. So we can combine both fast lookups, natural alignment of on-disk format, and compactness. The presence of index is just another bit in FDE metadata.

I have been going back and forth on this one. So there seem to be the following options here:
#1. Make "binary searchability" a per-FDE decision.
#2. Make "binary searchability" a per-section decision (I expect
aarch64 to have very low number of FREs per FDE).
#3. Bake "binary searchability" into the SFrame FRE specification.
So its always ON for all FDEs. The advantage is that it makes stack tracers simpler to implement with less code.

I do think #2, #3 appear simpler in concept.

Quoted 9 lines

b) bitness of offset_idxs[] can be coupled with bitness of
start_addrs (for simplicity), or could be completely independent and identified by FDE's metadata (2 more bits to define this just like start_addr bitness is defined). Independent probably would be my preference, with linker (or whoever will be producing .sframe data) can pick the smallest bitness that is sufficient to represent everything.

ATM, GAS does apply special logic to decide the bitness of start_addrs per function, and ld just uses that info. Coupling the bitness of offset_idx with bitness of start_addrs will be easy (or _easier_ I think), but for now, I leave it as "should be doable" :)

Quoted 9 lines

Yes, it's a bit more complicated to draw and explain, but everything will be nicely aligned, extensible to 64 bits, and (optionally at least) binary searchable. Implementation-wise on the kernel side it shouldn't be significantly more involved. Maybe the compiler would need to be a bit smarter when producing FDE data, but it's no rocket science.

Thoughts?

Combining the requirements from your email and Josh's follow up:
- No unaligned accesses
- Sorted FREs

I would put compaction as a "good to have" requirement. It appears to me that any compaction will mean a sort of post-processing which will interfere with JIT usecase.