Hi Arnd,
(replying to an old thread as this came up in the discussion regarding
misaligned loads and stored in siphash() when compiled for ARM
[f7e5b9bfa6c8820407b64eabc1f29c9a87e8993d])
On Fri, 14 May 2021 at 12:02, Arnd Bergmann <[email protected]> wrote:
>
> From: Arnd Bergmann <[email protected]>
>
> The get_unaligned()/put_unaligned() helpers are traditionally architecture
> specific, with the two main variants being the "access-ok.h" version
> that assumes unaligned pointer accesses always work on a particular
> architecture, and the "le-struct.h" version that casts the data to a
> byte aligned type before dereferencing, for architectures that cannot
> always do unaligned accesses in hardware.
>
> Based on the discussion linked below, it appears that the access-ok
> version is not realiable on any architecture, but the struct version
> probably has no downsides. This series changes the code to use the
> same implementation on all architectures, addressing the few exceptions
> separately.
>
> I've included this version in the asm-generic tree for 5.14 already,
> addressing the few issues that were pointed out in the RFC. If there
> are any remaining problems, I hope those can be addressed as follow-up
> patches.
>
I think this series is a huge improvement, but it does not solve the
UB problem completely. As we found, there are open issues in the GCC
bugzilla regarding assumptions in the compiler that aligned quantities
either overlap entirely or not at all. (e.g.,
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363)
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is used in many places to
conditionally emit code that violates C alignment rules. E.g., there
is this example in Documentation/core-api/unaligned-memory-access.rst:
bool ether_addr_equal(const u8 *addr1, const u8 *addr2)
{
#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
u32 fold = ((*(const u32 *)addr1) ^ (*(const u32 *)addr2)) |
((*(const u16 *)(addr1 + 4)) ^ (*(const u16 *)(addr2 + 4)));
return fold == 0;
#else
...
(which now deviates from its actual implementation, but the point is
the same) where CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is used in the
wrong way (IMHO).
The pattern seems to be
#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
// ignore alignment rules, just cast to a more aligned pointer type
#else
// use unaligned accessors, which could be either cheap or expensive,
// depending on the architecture
#endif
whereas the following pattern makes more sense, I think, and does not
violate any C rules in the common case:
#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
// use unaligned accessors, which are cheap or even entirely free
#else
// avoid unaligned accessors, as they are expensive; instead, reorganize
// the data so we don't need them (similar to setting NET_IP_ALIGN to 2)
#endif
The only remaining problem here is reinterpreting a char* pointer to a
u32*, e.g., for accessing the IP address in an Ethernet frame when
NET_IP_ALIGN == 2, which could suffer from the same UB problem again,
as I understand it.
In the 32-bit ARM case (v6+) [which is admittedly an outlier] this
makes a substantial difference, as ARMv6 does have efficient unaligned
accessors (load/store word or halfword may be used on misaligned
addresses) but requires that load/store double-word and load/store
multiple are only used on 32-bit aligned addresses. GCC does the right
thing with the unaligned accessors, but blindly casting away
misalignment may result in alignment traps if the compiler happened to
emit load-double or load-multiple instructions for the memory access
in question.
Jason already verifed that in the siphash() case, the aligned and
unaligned versions of the code actually compile to the same machine
code on x86, as the unaligned accessors just disappear. I suspect this
to be the case for many instances where
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is being used, mostly in the
networking stack.
So I intend to dig a bit deeper into this, and perhaps propose some
changes where the interpretation of
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is documented more clearly, and
tweaked according to my suggestion above (while ensuring that codegen
does not suffer, of course)
Thoughts, concerns, objections?
--
Ard.
> Link: https://lore.kernel.org/lkml/[email protected]/
> Link: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363
> Link: https://lore.kernel.org/lkml/[email protected]/
> Link: git://git.kernel.org/pub/scm/linux/kernel/git/arnd/asm-generic.git unaligned-rework-v2
>
>
> Arnd Bergmann (13):
> asm-generic: use asm-generic/unaligned.h for most architectures
> openrisc: always use unaligned-struct header
> sh: remove unaligned access for sh4a
> m68k: select CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
> powerpc: use linux/unaligned/le_struct.h on LE power7
> asm-generic: unaligned: remove byteshift helpers
> asm-generic: unaligned always use struct helpers
> partitions: msdos: fix one-byte get_unaligned()
> apparmor: use get_unaligned() only for multi-byte words
> mwifiex: re-fix for unaligned accesses
> netpoll: avoid put_unaligned() on single character
> asm-generic: uaccess: 1-byte access is always aligned
> asm-generic: simplify asm/unaligned.h
>
> arch/alpha/include/asm/unaligned.h | 12 --
> arch/arm/include/asm/unaligned.h | 27 ---
> arch/ia64/include/asm/unaligned.h | 12 --
> arch/m68k/Kconfig | 1 +
> arch/m68k/include/asm/unaligned.h | 26 ---
> arch/microblaze/include/asm/unaligned.h | 27 ---
> arch/mips/crypto/crc32-mips.c | 2 +-
> arch/openrisc/include/asm/unaligned.h | 47 -----
> arch/parisc/include/asm/unaligned.h | 6 +-
> arch/powerpc/include/asm/unaligned.h | 22 ---
> arch/sh/include/asm/unaligned-sh4a.h | 199 --------------------
> arch/sh/include/asm/unaligned.h | 13 --
> arch/sparc/include/asm/unaligned.h | 11 --
> arch/x86/include/asm/unaligned.h | 15 --
> arch/xtensa/include/asm/unaligned.h | 29 ---
> block/partitions/ldm.h | 2 +-
> block/partitions/msdos.c | 2 +-
> drivers/net/wireless/marvell/mwifiex/pcie.c | 10 +-
> include/asm-generic/uaccess.h | 4 +-
> include/asm-generic/unaligned.h | 141 +++++++++++---
> include/linux/unaligned/access_ok.h | 68 -------
> include/linux/unaligned/be_byteshift.h | 71 -------
> include/linux/unaligned/be_memmove.h | 37 ----
> include/linux/unaligned/be_struct.h | 37 ----
> include/linux/unaligned/generic.h | 115 -----------
> include/linux/unaligned/le_byteshift.h | 71 -------
> include/linux/unaligned/le_memmove.h | 37 ----
> include/linux/unaligned/le_struct.h | 37 ----
> include/linux/unaligned/memmove.h | 46 -----
> net/core/netpoll.c | 4 +-
> security/apparmor/policy_unpack.c | 2 +-
> 31 files changed, 131 insertions(+), 1002 deletions(-)
> delete mode 100644 arch/alpha/include/asm/unaligned.h
> delete mode 100644 arch/arm/include/asm/unaligned.h
> delete mode 100644 arch/ia64/include/asm/unaligned.h
> delete mode 100644 arch/m68k/include/asm/unaligned.h
> delete mode 100644 arch/microblaze/include/asm/unaligned.h
> delete mode 100644 arch/openrisc/include/asm/unaligned.h
> delete mode 100644 arch/powerpc/include/asm/unaligned.h
> delete mode 100644 arch/sh/include/asm/unaligned-sh4a.h
> delete mode 100644 arch/sh/include/asm/unaligned.h
> delete mode 100644 arch/sparc/include/asm/unaligned.h
> delete mode 100644 arch/x86/include/asm/unaligned.h
> delete mode 100644 arch/xtensa/include/asm/unaligned.h
> delete mode 100644 include/linux/unaligned/access_ok.h
> delete mode 100644 include/linux/unaligned/be_byteshift.h
> delete mode 100644 include/linux/unaligned/be_memmove.h
> delete mode 100644 include/linux/unaligned/be_struct.h
> delete mode 100644 include/linux/unaligned/generic.h
> delete mode 100644 include/linux/unaligned/le_byteshift.h
> delete mode 100644 include/linux/unaligned/le_memmove.h
> delete mode 100644 include/linux/unaligned/le_struct.h
> delete mode 100644 include/linux/unaligned/memmove.h
>
> --
> 2.29.2
>
> Cc: Amitkumar Karwar <[email protected]>
> Cc: Arnd Bergmann <[email protected]>
> Cc: Benjamin Herrenschmidt <[email protected]>
> Cc: Borislav Petkov <[email protected]>
> Cc: Eric Dumazet <[email protected]>
> Cc: Florian Fainelli <[email protected]>
> Cc: Ganapathi Bhat <[email protected]>
> Cc: Geert Uytterhoeven <[email protected]>
> Cc: "H. Peter Anvin" <[email protected]>
> Cc: Ingo Molnar <[email protected]>
> Cc: Jakub Kicinski <[email protected]>
> Cc: James Morris <[email protected]>
> Cc: Jens Axboe <[email protected]>
> Cc: John Johansen <[email protected]>
> Cc: Jonas Bonn <[email protected]>
> Cc: Kalle Valo <[email protected]>
> Cc: Michael Ellerman <[email protected]>
> Cc: Paul Mackerras <[email protected]>
> Cc: Rich Felker <[email protected]>
> Cc: "Richard Russon (FlatCap)" <[email protected]>
> Cc: Russell King <[email protected]>
> Cc: "Serge E. Hallyn" <[email protected]>
> Cc: Sharvari Harisangam <[email protected]>
> Cc: Stafford Horne <[email protected]>
> Cc: Stefan Kristiansson <[email protected]>
> Cc: Thomas Gleixner <[email protected]>
> Cc: Vladimir Oltean <[email protected]>
> Cc: Xinming Hu <[email protected]>
> Cc: Yoshinori Sato <[email protected]>
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
> Cc: [email protected]
>
>
On Thu, Dec 16, 2021 at 9:29 AM Ard Biesheuvel <[email protected]> wrote:
>
> CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is used in many places to
> conditionally emit code that violates C alignment rules. E.g., there
> is this example in Documentation/core-api/unaligned-memory-access.rst:
>
> bool ether_addr_equal(const u8 *addr1, const u8 *addr2)
> {
> #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
> u32 fold = ((*(const u32 *)addr1) ^ (*(const u32 *)addr2)) |
> ((*(const u16 *)(addr1 + 4)) ^ (*(const u16 *)(addr2 + 4)));
> return fold == 0;
> #else
It probably works fine in practice - the one case we had was really
pretty special, and about the vectorizer doing odd things.
But I think we should strive to convert these to use
"get_unaligned()", since code generation is fine. It still often makes
sense to have that test for the config variable, simply because the
approach might be different if we know unaligned accesses are slow.
So I'll happily take patches that do obvious conversions to
get_unaligned() where they make sense, but I don't think we should
consider this some huge hard requirement.
Linus
From: Ard Biesheuvel
> Sent: 16 December 2021 17:30
>
> Hi Arnd,
>
> (replying to an old thread as this came up in the discussion regarding
> misaligned loads and stored in siphash() when compiled for ARM
> [f7e5b9bfa6c8820407b64eabc1f29c9a87e8993d])
>
> On Fri, 14 May 2021 at 12:02, Arnd Bergmann <[email protected]> wrote:
> >
> > From: Arnd Bergmann <[email protected]>
> >
> > The get_unaligned()/put_unaligned() helpers are traditionally architecture
> > specific, with the two main variants being the "access-ok.h" version
> > that assumes unaligned pointer accesses always work on a particular
> > architecture, and the "le-struct.h" version that casts the data to a
> > byte aligned type before dereferencing, for architectures that cannot
> > always do unaligned accesses in hardware.
I'm pretty sure the compiler is allowed to 'read through' that cast
and still do an aligned access.
It has always been hard to get the compiler to 'forget' about known/expected
alignment - typically trying to stop memcpy() faulting on sparc.
Real function calls are usually required - but LTO may scupper that.
> >
> > Based on the discussion linked below, it appears that the access-ok
> > version is not realiable on any architecture, but the struct version
> > probably has no downsides. This series changes the code to use the
> > same implementation on all architectures, addressing the few exceptions
> > separately.
> >
> > I've included this version in the asm-generic tree for 5.14 already,
> > addressing the few issues that were pointed out in the RFC. If there
> > are any remaining problems, I hope those can be addressed as follow-up
> > patches.
> >
>
> I think this series is a huge improvement, but it does not solve the
> UB problem completely. As we found, there are open issues in the GCC
> bugzilla regarding assumptions in the compiler that aligned quantities
> either overlap entirely or not at all. (e.g.,
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363)
I think we can stop the compiler merging unaligned requests by adding a byte-sized
memory barrier for the base address before and after the access.
That should still support complex addressing modes (esp on x86).
Another option is to do the misaligned access from within an asm statement.
While architecture dependant, it only really depends on the syntax of the ld/st
instruction.
The compiler can't merge those because it doesn't know whether the data is
'frobbed' before/after the memory access.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On Thu, Dec 16, 2021 at 06:29:40PM +0100, Ard Biesheuvel wrote:
> I think this series is a huge improvement, but it does not solve the
> UB problem completely. As we found, there are open issues in the GCC
> bugzilla regarding assumptions in the compiler that aligned quantities
> either overlap entirely or not at all. (e.g.,
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363)
That isn't open, it was closed as INVALID back in May.
(Naturally) aligned quantities only overlap if they are the same datum.
This follows directly from the definition of (naturally) aligned. There
is no mystery here.
All unaligned data need to be marked up properly.
> CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is used in many places to
> conditionally emit code that violates C alignment rules.
Most of this is ABI, not C. It is the ABI that requires certain
alignments. Ignoring that plain does not work, but even if it would
you will end up with much slower generated code.
> whereas the following pattern makes more sense, I think, and does not
> violate any C rules in the common case:
>
> #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
> // use unaligned accessors, which are cheap or even entirely free
> #else
> // avoid unaligned accessors, as they are expensive; instead, reorganize
> // the data so we don't need them (similar to setting NET_IP_ALIGN to 2)
> #endif
Yes, this looks more reasonable.
> The only remaining problem here is reinterpreting a char* pointer to a
> u32*, e.g., for accessing the IP address in an Ethernet frame when
> NET_IP_ALIGN == 2, which could suffer from the same UB problem again,
> as I understand it.
The problem is never casting a pointer to pointer to character type, and
then later back to an appriopriate pointer type. These things are both
required to work. The problem always is accessing something as if it
was something of another type, which is not valid C. This however is
exactly what -fno-strict-aliasing allows, so that works as well.
But this does not have much to do with alignment.
Segher
From: Segher Boessenkool
> Sent: 16 December 2021 18:56
...
> > The only remaining problem here is reinterpreting a char* pointer to a
> > u32*, e.g., for accessing the IP address in an Ethernet frame when
> > NET_IP_ALIGN == 2, which could suffer from the same UB problem again,
> > as I understand it.
>
> The problem is never casting a pointer to pointer to character type, and
> then later back to an appriopriate pointer type.
> These things are both required to work.
I think that is true of 'void *', not 'char *'.
'char' is special in that 'strict aliasing' doesn't apply to it.
(Which is actually a pain sometimes.)
> The problem always is accessing something as if it
> was something of another type, which is not valid C. This however is
> exactly what -fno-strict-aliasing allows, so that works as well.
IIRC the C language only allows you to have pointers to valid data items.
(Since they can only be generated by the & operator on a valid item.)
Indirecting any other pointer is probably UB!
This (sort of) allows the compiler to 'look through' casts to find
what the actual type is (or might be).
It can then use that information to make optimisation choices.
This has caused grief with memcpy() calls that are trying to copy
a structure that the coder knows is misaligned to an aligned buffer.
So while *(unaligned_ptr *)char_ptr probably has to work.
If the compiler can see *(unaligned_ptr *)(char *)int_ptr it can
assume the alignment of the 'int_ptr' and do a single aligned access.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
On Fri, Dec 17, 2021 at 12:34:53PM +0000, David Laight wrote:
> From: Segher Boessenkool
> > Sent: 16 December 2021 18:56
> ...
> > > The only remaining problem here is reinterpreting a char* pointer to a
> > > u32*, e.g., for accessing the IP address in an Ethernet frame when
> > > NET_IP_ALIGN == 2, which could suffer from the same UB problem again,
> > > as I understand it.
> >
> > The problem is never casting a pointer to pointer to character type, and
> > then later back to an appriopriate pointer type.
> > These things are both required to work.
>
> I think that is true of 'void *', not 'char *'.
No, see 6.3.2.3/7. Both are allowed (and behave the same in fact).
> 'char' is special in that 'strict aliasing' doesn't apply to it.
> (Which is actually a pain sometimes.)
That has nothing to do with it. Yes, you can validly access any memory
as a character type, but that has nothing to do with what pointer casts
are allowed and which are not.
> > The problem always is accessing something as if it
> > was something of another type, which is not valid C. This however is
> > exactly what -fno-strict-aliasing allows, so that works as well.
>
> IIRC the C language only allows you to have pointers to valid data items.
> (Since they can only be generated by the & operator on a valid item.)
Not so. For example you are explicitly allowed to have pointers one
past the last element of an array (and do arithmetic on that!), and of
course null pointers are a thing.
C allows you to make up pointers from integers as well. This is
perfectly fine to do. Accessing anything via such pointers might well
be not standard C, of course.
> Indirecting any other pointer is probably UB!
If a pointer points to an object, indirecting it gives an lvalue of that
object. It does not matter how you got that pointer, all that matters
is that it points at a valid object.
> This (sort of) allows the compiler to 'look through' casts to find
> what the actual type is (or might be).
> It can then use that information to make optimisation choices.
> This has caused grief with memcpy() calls that are trying to copy
> a structure that the coder knows is misaligned to an aligned buffer.
This is 6.5/7.
Alignment is 6.2.8 but it doesn't actually come into play at all here.
> So while *(unaligned_ptr *)char_ptr probably has to work.
Only if the original pointer points to an object that is correct
(including correctly aligned) for such an lvalue.
> If the compiler can see *(unaligned_ptr *)(char *)int_ptr it can
> assume the alignment of the 'int_ptr' and do a single aligned access.
It is undefined behaviour to have an address in int_ptr that is not
correctly aligned for whatever type it points to.
Segher