Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Wed, Feb 05, 2025 at 02:56:36PM +0100, Jens Remus wrote: > On 29.01.2025 03:02, Josh Poimboeuf wrote: > > > 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. In ORC, a hole is simply specified by an ORC entry (aka "FRE") of type UNDEFINED. That could be done here as well: the linker would replace a gap with an "undefined" FRE which could be identified either by setting a bit in the FRE header, or by using a special fre_data[] entry. For example, fre_data index 0 could just be a placeholder for the undefined FRE type. -- Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On 2/4/25 4:57 PM, Josh Poimboeuf wrote:
On Thu, Jan 30, 2025 at 01:39:52PM -0800, Indu Bhagat wrote:
On 1/28/25 6:02 PM, Josh Poimboeuf wrote:
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.
If fre_data[] is allowed to have duplicates then the deduping could be
optional.
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.
I'm not sure I follow, is this referring to the link-time work of
sorting things?
I meant the work of tracking the start address of each function. This
could be done at link-time as is done in most cases.
But also depending on the case : e.g., kernel module loader will need to
apply these relocations in the .rela.sframe section...
If the granularity is finer than a function, more number of relocations
will need to be applied.
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.
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Thu, Jan 30, 2025 at 1:21 PM Indu Bhagat wrote:
>
> 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 🙂 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 ?
Performance hit on architectures like x86-64 that do support
unaligned, but it's actually a CPU error for some other architectures,
so you'd need to code with that in mind, making local aligned copies,
etc. In general, I'd say it's a bit of a red flag that a format that
is meant to be memory-mapped (effectively) and used without
pre-processing requires dealing with unaligned accesses. So if we can
fix that, that would be a win.
>
> > 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_
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Wed, Feb 5, 2025 at 3:02 AM Jens Remus wrote:
>
> On 28.01.2025 02:10, Andrii Nakryiko wrote:
>
> > 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.
>
> Just for clarification of the SFrame V2 format, as there may be some
> misconception. Using pseudo-C type definition:
>
> struct sframe_fre8 {
> u8 sfre_start_address;
> u8 sfre_info;
> s8|s16|s32 offsets[M];
> };
> struct sframe_fre16 {
> u16 sfre_start_address;
> u8 sfre_info;
> s8|s16|s32 offsets[M];
> };
> struct sframe_fre32 {
> u32 sfre_start_address;
> u8 sfre_info;
> s8|s16|s32 offsets[M];
> };
>
yeah, sorry, copy/paste error for those sfre_info, it's always u8
> struct sframe_section {
> /* Headers. */
> struct sframe_preamble preamble;
> struct sframe_header header;
> struct sframe_auxiliary_header auxhdr;
>
> /* FDEs. */
> struct sframe_fde fdes[N_FDE];
>
> /* FRE8s / FRE16s / FRE32s per FDE. */
> struct sframe_fre{8|16|32} fres_fde1[N_FRE_FDE1] __packed;
> ...
> struct sframe_fre{8|16|32} fres_fdeN[N_FRE_FDEN] __packed;
> };
>
> Where:
> - fdes[] can be binary searched: All fdes[i] are of equal size and
>sorted on start address.
> - Each fdes[i] points at its fres_fdei[].
> - fres_fdei[] cannot be binary searched: For each fdes[i] they 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.
>
yep
> Regards,
> Jens
> --
> Jens Remus
> Linux on Z Development (D3303)
> +49-7031-16-1128 Office
> [email protected]
>
> IBM
>
> IBM Deutschland Research & Development GmbH; Vorsitzender des Aufsichtsrats:
> Wolfgang Wendt; Geschäftsführung: David Faller; Sitz der Gesellschaft:
> Böblingen; Registergericht: Amtsgericht Stuttgart, HRB 243294
> IBM Data Privacy Statement: https://www.ibm.com/privacy/
>
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On 29.01.2025 03:02, Josh Poimboeuf wrote: 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. Regards, Jens -- Jens Remus Linux on Z Development (D3303) +49-7031-16-1128 Office [email protected] IBM IBM Deutschland Research & Development GmbH; Vorsitzender des Aufsichtsrats: Wolfgang Wendt; Geschäftsführung: David Faller; Sitz der Gesellschaft: Böblingen; Registergericht: Amtsgericht Stuttgart, HRB 243294 IBM Data Privacy Statement: https://www.ibm.com/privacy/
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On 28.01.2025 02:10, Andrii Nakryiko wrote:
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.
Just for clarification of the SFrame V2 format, as there may be some
misconception. Using pseudo-C type definition:
struct sframe_fre8 {
u8 sfre_start_address;
u8 sfre_info;
s8|s16|s32 offsets[M];
};
struct sframe_fre16 {
u16 sfre_start_address;
u8 sfre_info;
s8|s16|s32 offsets[M];
};
struct sframe_fre32 {
u32 sfre_start_address;
u8 sfre_info;
s8|s16|s32 offsets[M];
};
struct sframe_section {
/* Headers. */
struct sframe_preamble preamble;
struct sframe_header header;
struct sframe_auxiliary_header auxhdr;
/* FDEs. */
struct sframe_fde fdes[N_FDE];
/* FRE8s / FRE16s / FRE32s per FDE. */
struct sframe_fre{8|16|32} fres_fde1[N_FRE_FDE1] __packed;
...
struct sframe_fre{8|16|32} fres_fdeN[N_FRE_FDEN] __packed;
};
Where:
- fdes[] can be binary searched: All fdes[i] are of equal size and
sorted on start address.
- Each fdes[i] points at its fres_fdei[].
- fres_fdei[] cannot be binary searched: For each fdes[i] they 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.
Regards,
Jens
--
Jens Remus
Linux on Z Development (D3303)
+49-7031-16-1128 Office
[email protected]
IBM
IBM Deutschland Research & Development GmbH; Vorsitzender des Aufsichtsrats:
Wolfgang Wendt; Geschäftsführung: David Faller; Sitz der Gesellschaft: Böblingen;
Registergericht: Amtsgericht Stuttgart, HRB 243294
IBM Data Privacy Statement: https://www.ibm.com/privacy/
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Thu, Jan 30, 2025 at 01:39:52PM -0800, Indu Bhagat wrote:
> On 1/28/25 6:02 PM, Josh Poimboeuf wrote:
> > 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.
If fre_data[] is allowed to have duplicates then the deduping could be
optional.
> > 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.
I'm not sure I follow, is this referring to the link-time work of
sorting things?
> 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.
--
Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Thu, Jan 30, 2025 at 01:21:21PM -0800, Indu Bhagat wrote: > > 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 ? I think performance is the main concern, though there are still some CPU arches out there which don't support unaligned accesses. > 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. I think we should still consider the fast lookup table. We might want to prototype something just to see what the speedup looks like. Similar to compaction it could just be an optional feature implemented by the linker which JIT doesn't have to use. -- Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Wed, Jan 29, 2025 at 04:02:34PM -0800, Andrii Nakryiko wrote: > On Tue, Jan 28, 2025 at 6:02 PM Josh Poimboeuf 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.textPROGBITS 0b00e640 0ae0d640 >11ad621c AX 0 0 64 > ... > [48] .text PROGBITS 1e60 1ce0 >00775dd8 AX 0 0 2097152 > [49] .text.coldPROGBITS 1ed75e00 1d575e00 >007d3271 AX 0 0 64 > ... > > Total text size is about 300MB: > >>> 0x00775dd8 + 0x007d3271 + 0x11ad621c > 312603237 > > Section #17 ends at: > > >>> hex(0x11ad621c + 0x0b00e640) > '0x1cae485c' > > While .text starts at 1e60, so we have a gap of ~28MB: > > >>> 0x1e60 - 0x1cae485c > 28424100 > > So unless we do something more clever to support multiple > discontiguous chunks, this seems like a bad fit for user space. Nothing clever needed, we could just have multiple sframe sections, each one with a pointer to its text segment. That would also have the benefit of allowing the sframe data to be much more compact for the noncontiguous cases. > I think having all this just binary searchable is already a big win > anyways and should be plenty fast, no? Sframe is trying to compete with frame pointers which are MUCH faster. 3-4x faster in my testing, not including the page faults (which tend to only affect performance in the very beginning). -- Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
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. An
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
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 🙂 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 ?
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.
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 advant
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Tue, Jan 28, 2025 at 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.
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 w
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
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 hu
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Fri, Jan 24, 2025 at 2:14 PM Indu Bhagat 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 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;
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Fri, Jan 24, 2025 at 03:13:40PM -0500, Steven Rostedt wrote:
> On Fri, 24 Jan 2025 11:21:59 -0800
> Josh Poimboeuf 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.
--
Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
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 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.
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Fri, 24 Jan 2025 11:21:59 -0800
Josh Poimboeuf 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
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On 1/24/25 10:00 AM, Andrii Nakryiko wrote:
On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf 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
---
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
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Fri, Jan 24, 2025 at 10:00:52AM -0800, Andrii Nakryiko wrote:
> On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf 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.
--
Josh
Re: [PATCH v4 17/39] unwind_user/sframe: Add support for reading .sframe headers
On Tue, Jan 21, 2025 at 6:32 PM Josh Poimboeuf 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
> ---
> 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 ..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
> +
> +#define SFRAME_VERSION_1 1
> +#define SFRAME_VERSION_2 2
> +#define SFRAME_MAGIC 0xdee2
> +
> +#define SFRAME_F_FDE_SORTED0x1
> +#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
> +
> +st
