| Message ID | f27e8463783febfa0dabb0432a3dd6be8ad98412.1737511963.git.jpoimboe@kernel.org (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | unwind, perf: sframe user space unwinding | expand |
On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote: > > 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 <jpoimboe@kernel.org> > --- > 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 > [...] > + > +extern int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, > + unsigned long text_start, unsigned long text_end); > +extern int sframe_remove_section(unsigned long sframe_addr); > + > +#else /* !CONFIG_HAVE_UNWIND_USER_SFRAME */ > + > +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? > +static inline int sframe_remove_section(unsigned long sframe_addr) { return -ENOSYS; } > + > +#endif /* CONFIG_HAVE_UNWIND_USER_SFRAME */ > + > +#endif /* _LINUX_SFRAME_H */ [...] > +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; > + unsigned int num_fdes; > + > + if (copy_from_user(&shdr, (void __user *)sec->sframe_start, sizeof(shdr))) { > + dbg("header usercopy failed\n"); > + return -EFAULT; > + } > + > + 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... > + shdr.auxhdr_len) { > + dbg("bad/unsupported sframe header\n"); > + return -EINVAL; > + } > + > + 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? > + 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? > + 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 > + 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; > +} > + [...] > diff --git a/kernel/unwind/sframe.h b/kernel/unwind/sframe.h > new file mode 100644 > index 000000000000..e9bfccfaf5b4 > --- /dev/null > +++ b/kernel/unwind/sframe.h > @@ -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 > + > +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)?.. > + > +#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 >
On Fri, Jan 24, 2025 at 10:00:52AM -0800, Andrii Nakryiko wrote: > On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote: > > +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. > > + 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... > > + 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? 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. > > + 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. > > + 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. > > +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; > > + 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.
On Fri, 24 Jan 2025 11:21:59 -0800 Josh Poimboeuf <jpoimboe@kernel.org> wrote: > > 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. > > > > + 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. 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 something. -- Steve
On 1/24/25 10:00 AM, Andrii Nakryiko wrote: > On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf<jpoimboe@kernel.org> wrote: >> 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<jpoimboe@kernel.org> >> --- >> 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 >> > [...] > >> + >> +extern int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, >> + unsigned long text_start, unsigned long text_end); >> +extern int sframe_remove_section(unsigned long sframe_addr); >> + >> +#else /* !CONFIG_HAVE_UNWIND_USER_SFRAME */ >> + >> +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? > >> +static inline int sframe_remove_section(unsigned long sframe_addr) { return -ENOSYS; } >> + >> +#endif /* CONFIG_HAVE_UNWIND_USER_SFRAME */ >> + >> +#endif /* _LINUX_SFRAME_H */ > [...] > >> +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; >> + unsigned int num_fdes; >> + >> + if (copy_from_user(&shdr, (void __user *)sec->sframe_start, sizeof(shdr))) { >> + dbg("header usercopy failed\n"); >> + return -EFAULT; >> + } >> + >> + 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... It is not worthwhile for the assembler (even wasteful as it adds to build time for nothing) to generate an .sframe section with FDEs in sorted order of start PC of function. This is because the final order is decided by the linker as it merges all input sections. Thats one reason why it is already necessary that the specification allows SFRAME_F_FDE_SORTED not set in the section. I can also see how not making the sorting mandatory may also be necessary for JIT use-case.. FWIW, for non-JIT environments, non-sorted FDEs are not expected in linked binaries; such a thing does not seem to be useful in practice. Hope that helps Indu
On 1/24/25 11:21 AM, Josh Poimboeuf wrote: > On Fri, Jan 24, 2025 at 10:00:52AM -0800, Andrii Nakryiko wrote: >> On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote: >>> +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. > >>> + 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... > >>> + 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? > > 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. >>> + 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. > >>> + 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. > >>> +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; >>> + 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. > 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.
On Fri, Jan 24, 2025 at 03:13:40PM -0500, Steven Rostedt wrote: > On Fri, 24 Jan 2025 11:21:59 -0800 > Josh Poimboeuf <jpoimboe@kernel.org> wrote: > > > > 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. > > > > > > + 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. > > 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. Maybe? I was thinking the kernel would have sframe_section placeholders for JIT code sections, so when sframe_find() retrieves the struct for a given IP, it sees the JIT flag is set along with a pointer to the in-memory shared "sframe section", then goes to read that to get the corresponding sframe entry (insert erratic hand waving). It's still early days but it's quite possible the in-memory "sframe section" formats might end up looking pretty different from the .sframe file section spec.
On Fri, Jan 24, 2025 at 2:14 PM Indu Bhagat <indu.bhagat@oracle.com> wrote: > > On 1/24/25 11:21 AM, Josh Poimboeuf wrote: > > On Fri, Jan 24, 2025 at 10:00:52AM -0800, Andrii Nakryiko wrote: > >> On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote: > >>> +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. > > > >>> + 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... > > > >>> + 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? > > > > 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). > 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). > SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all. > > >>> + 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. Let's invert this. Is there any reason why it shouldn't be supported? ;) > > > >>> + 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. > > > >>> +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; > >>> + 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. > > > > 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?
On Mon, Jan 27, 2025 at 05:10:27PM -0800, Andrii Nakryiko wrote: > > 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). 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. > > SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all. > > > > >>> + 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. > > 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. > 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. Makes sense. Though I also have another idea below. > 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]; 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.
On Tue, Jan 28, 2025 at 6:02 PM Josh Poimboeuf <jpoimboe@kernel.org> wrote: > > On Mon, Jan 27, 2025 at 05:10:27PM -0800, Andrii Nakryiko wrote: > > > 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). > > 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. > > > > SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all. > > > > > > >>> + 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. > > > > 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. If under the format specification it's legal, there is no reason for the kernel to proactively reject it, IMO. But ok, whatever. > > > 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. > > Makes sense. Though I also have another idea below. > > > 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]; > > 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. yep, agreed, seems like a worthwhile thing to support, given the stats (I suspect big production C++ applications might be even worse in this regard) > > 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; even u16 seems dangerous, I'd use u32, not sure it's worth limiting the format just to 64K unique combinations > > } __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). 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: >>> 0x0000000000775dd8 + 0x00000000007d3271 + 0x0000000011ad621c 312603237 Section #17 ends at: >>> hex(0x0000000011ad621c + 0x000000000b00e640) '0x1cae485c' While .text starts at 000000001e600000, so we have a gap of ~28MB: >>> 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? > > 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. I do like the idea of deduplicating those records and just indexing them, as in practice this should probably be much more compact. So it might be worth looking into this some more. I'll defer to Indu. > > -- > Josh
On 1/27/25 5:10 PM, Andrii Nakryiko wrote: >>>>> +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; >>>>> + 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. >>> >> 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
On 1/28/25 6:02 PM, Josh Poimboeuf wrote: > On Mon, Jan 27, 2025 at 05:10:27PM -0800, Andrii Nakryiko wrote: >>> 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). > > 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. > >>> SFRAME_F_FRAME_POINTER flag is not being set currently by GAS/GNU ld at all. >>> >>>>>> + 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. >> >> 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. > >> 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. > > Makes sense. Though I also have another idea below. > >> 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]; > > 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. > Thanks for gathering this. I suspect on aarch64, the numbers will be very different (leaning towards very low number of FREs per FDE). Making SFrame FREs amenable to binary search can be targeted. Both your and Andrii's proposal do address that... > 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]; > 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. > 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. > 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. I think the first conceptual landing point in the information layout should be a per-function entry. > 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. >
diff --git a/arch/Kconfig b/arch/Kconfig index f1f7a3857c97..23edd0e4e16a 100644 --- a/arch/Kconfig +++ b/arch/Kconfig @@ -446,6 +446,9 @@ config HAVE_UNWIND_USER_COMPAT_FP bool depends on HAVE_UNWIND_USER_FP +config HAVE_UNWIND_USER_SFRAME + bool + config AS_SFRAME def_bool $(as-instr,.cfi_sections .sframe\n.cfi_startproc\n.cfi_endproc) diff --git a/include/linux/sframe.h b/include/linux/sframe.h new file mode 100644 index 000000000000..3bfaf21869c2 --- /dev/null +++ b/include/linux/sframe.h @@ -0,0 +1,36 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_SFRAME_H +#define _LINUX_SFRAME_H + +#include <linux/mm_types.h> +#include <linux/unwind_user_types.h> + +#ifdef CONFIG_HAVE_UNWIND_USER_SFRAME + +struct sframe_section { + unsigned long sframe_start; + unsigned long sframe_end; + unsigned long text_start; + unsigned long text_end; + + unsigned long fdes_start; + unsigned long fres_start; + unsigned long fres_end; + unsigned int num_fdes; + + signed char ra_off; + signed char fp_off; +}; + +extern int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, + unsigned long text_start, unsigned long text_end); +extern int sframe_remove_section(unsigned long sframe_addr); + +#else /* !CONFIG_HAVE_UNWIND_USER_SFRAME */ + +static inline int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, unsigned long text_start, unsigned long text_end) { return -ENOSYS; } +static inline int sframe_remove_section(unsigned long sframe_addr) { return -ENOSYS; } + +#endif /* CONFIG_HAVE_UNWIND_USER_SFRAME */ + +#endif /* _LINUX_SFRAME_H */ diff --git a/kernel/unwind/Makefile b/kernel/unwind/Makefile index 349ce3677526..f70380d7a6a6 100644 --- a/kernel/unwind/Makefile +++ b/kernel/unwind/Makefile @@ -1 +1,2 @@ - obj-$(CONFIG_UNWIND_USER) += user.o + obj-$(CONFIG_UNWIND_USER) += user.o + obj-$(CONFIG_HAVE_UNWIND_USER_SFRAME) += sframe.o diff --git a/kernel/unwind/sframe.c b/kernel/unwind/sframe.c new file mode 100644 index 000000000000..20287f795b36 --- /dev/null +++ b/kernel/unwind/sframe.c @@ -0,0 +1,136 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Userspace sframe access functions + */ + +#define pr_fmt(fmt) "sframe: " fmt + +#include <linux/sched.h> +#include <linux/slab.h> +#include <linux/srcu.h> +#include <linux/uaccess.h> +#include <linux/mm.h> +#include <linux/string_helpers.h> +#include <linux/sframe.h> +#include <linux/unwind_user_types.h> + +#include "sframe.h" + +#define dbg(fmt, ...) \ + pr_debug("%s (%d): " fmt, current->comm, current->pid, ##__VA_ARGS__) + +static void free_section(struct sframe_section *sec) +{ + kfree(sec); +} + +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; + unsigned int num_fdes; + + if (copy_from_user(&shdr, (void __user *)sec->sframe_start, sizeof(shdr))) { + dbg("header usercopy failed\n"); + return -EFAULT; + } + + if (shdr.preamble.magic != SFRAME_MAGIC || + shdr.preamble.version != SFRAME_VERSION_2 || + !(shdr.preamble.flags & SFRAME_F_FDE_SORTED) || + shdr.auxhdr_len) { + dbg("bad/unsupported sframe header\n"); + return -EINVAL; + } + + if (!shdr.num_fdes || !shdr.num_fres) { + dbg("no fde/fre entries\n"); + return -EINVAL; + } + + header_end = sec->sframe_start + SFRAME_HEADER_SIZE(shdr); + if (header_end >= sec->sframe_end) { + 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; + + 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; +} + +int sframe_add_section(unsigned long sframe_start, unsigned long sframe_end, + unsigned long text_start, unsigned long text_end) +{ + struct maple_tree *sframe_mt = ¤t->mm->sframe_mt; + struct vm_area_struct *sframe_vma, *text_vma; + struct mm_struct *mm = current->mm; + struct sframe_section *sec; + int ret; + + if (!sframe_start || !sframe_end || !text_start || !text_end) { + dbg("zero-length sframe/text address\n"); + return -EINVAL; + } + + scoped_guard(mmap_read_lock, mm) { + sframe_vma = vma_lookup(mm, sframe_start); + if (!sframe_vma || sframe_end > sframe_vma->vm_end) { + dbg("bad sframe address (0x%lx - 0x%lx)\n", + sframe_start, sframe_end); + return -EINVAL; + } + + text_vma = vma_lookup(mm, text_start); + if (!text_vma || + !(text_vma->vm_flags & VM_EXEC) || + text_end > text_vma->vm_end) { + dbg("bad text address (0x%lx - 0x%lx)\n", + text_start, text_end); + return -EINVAL; + } + } + + sec = kzalloc(sizeof(*sec), GFP_KERNEL); + if (!sec) + return -ENOMEM; + + sec->sframe_start = sframe_start; + sec->sframe_end = sframe_end; + sec->text_start = text_start; + sec->text_end = text_end; + + ret = sframe_read_header(sec); + if (ret) + goto err_free; + + /* TODO nowhere to store it yet - just free it and return an error */ + ret = -ENOSYS; + +err_free: + free_section(sec); + return ret; +} + +int sframe_remove_section(unsigned long sframe_start) +{ + return -ENOSYS; +} diff --git a/kernel/unwind/sframe.h b/kernel/unwind/sframe.h new file mode 100644 index 000000000000..e9bfccfaf5b4 --- /dev/null +++ b/kernel/unwind/sframe.h @@ -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 + +struct sframe_fde { + s32 start_addr; + u32 func_size; + u32 fres_off; + u32 fres_num; + u8 info; + u8 rep_size; + u16 padding; +} __packed; + +#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 */
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 <jpoimboe@kernel.org> --- 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