pyhash's siphash24 assumes alignment of the data pointer

@doko42

BPO	28055
Nosy	@doko42, @pitrou, @vstinner, @tiran, @benjaminp, @ned-deily, @skrah, @serhiy-storchaka, @ztane, @miss-islington, @DerDakon
PRs	bpo-28055: fix unaligned accesses in siphash24() #6123 [3.7] bpo-28055: Fix unaligned accesses in siphash24(). (GH-6123) #6777 [3.6] bpo-28055: Fix unaligned accesses in siphash24(). (GH-6123) #6778
Files	pyhash.diff pyhash2.diff hash-bytes-alignment.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/doko42'
closed_at = <Date 2019-04-12.22:36:32.781>
created_at = <Date 2016-09-09.23:29:02.147>
labels = ['interpreter-core', '3.7', '3.8', 'type-crash']
title = "pyhash's siphash24 assumes alignment of the data pointer"
updated_at = <Date 2019-04-12.22:36:32.780>
user = 'https://github.com/doko42'

bugs.python.org fields:

activity = <Date 2019-04-12.22:36:32.780>
actor = 'vstinner'
assignee = 'doko'
closed = True
closed_date = <Date 2019-04-12.22:36:32.781>
closer = 'vstinner'
components = ['Interpreter Core']
creation = <Date 2016-09-09.23:29:02.147>
creator = 'doko'
dependencies = []
files = ['44629', '44630', '44648']
hgrepos = []
issue_num = 28055
keywords = ['patch']
message_count = 41.0
messages = ['275493', '275500', '275509', '275634', '275761', '276255', '276257', '276258', '276259', '276261', '276263', '276345', '276346', '276347', '276352', '276355', '276374', '276394', '276396', '276397', '276399', '276404', '276406', '276407', '276408', '276409', '276411', '276412', '276495', '286391', '286412', '314472', '315998', '316459', '316461', '316463', '316469', '316470', '322097', '322135', '340125']
nosy_count = 13.0
nosy_names = ['doko', 'pitrou', 'vstinner', 'christian.heimes', 'benjamin.peterson', 'ned.deily', 'skrah', 'serhiy.storchaka', 'ztane', 'Jeffrey.Walton', 'gco', 'miss-islington', 'Dakon']
pr_nums = ['6123', '6777', '6778']
priority = 'high'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue28055'
versions = ['Python 3.6', 'Python 3.7', 'Python 3.8']

pyhash's siphash24 assumes alignment of the data pointer, casting a void pointer (src) to an uint64_t pointer, increasing the required alignment from 1 to 4 bytes. That's invalid code. siphash24 can't assume that the pointer to the data to hash is 4-byte aligned.

Seen as a bus error trying to run a ARM32 binary on a AArch64 kernel.

./python -c 'import datetime; print(hash(datetime.datetime(2015, 1, 1)))'

the datetime type is defined as

#define _PyTZINFO_HEAD \
    PyObject_HEAD \
    Py_hash_t hashcode; \
    char hastzinfo; /* boolean flag */

typedef struct
{
    _PyTZINFO_HEAD
    unsigned char data[_PyDateTime_DATE_DATASIZE];
} PyDateTime_Date;

and data is used to calculate the hash of the object, not being 4 byte aligned, you get the bus error. Inserting three fill bytes, are making the data member 4-byte aligned solves the issue, however introducing an ABI change makes the new datetime ABI incompatible, and we don't know about the alignment of objects outside the standard library.

The solution is to use a memcpy instead of the cast to uint64_t, for now limited to the little endian ARM targets, but I don't see why the memcpy cannot always be used on little endian targets instead of the cast.

Good catch! I had trouble with the data structures in the TZ module before.

I'm fine with memcpy() on just ARM platforms as a temporary workaround. Let's discuss the issue another time. Right now I'm busy with ssl improvements for 3.6.0b1.

I believe the unaligned memory access configure check is supposed to prevent siphash from being used, so we might look into why that's not working.

IMO, though, we should just require alignment for the argument to _PyHash_Bytes. It's private after all.

I don't like that configure check, because it depends on the kernel being used at runtime. For many architectures you can define in the kernel if the kernel should allow unaligned accesses or not. Sure this is not an issue for linux distro builds, but might be unexpected for third party builds.

There is no need to ifdef anything, the memcpy is the only correct way to do it. As memcpy is also a reserved identifier in C, the compiler can and will optimize this into a 64-bit access on those platforms where it can be safely done so (x86 for example), e.g. GCC compiles

    uint64_t func(char *buf) {
        uint64_t rv;
        memcpy(&rv, buf+3, sizeof(rv));
        return rv;
    }

into

movq    3(%rdi), %rax
ret

On Linux 64-bit ABI.

updated patch that always used memcpy for the little endian case.

I'm a bit worried that the patch might slow down the general case of SipHash24. When I was working on SipHash24 I made sure that the general case in PyBytes_Object and PyUnicode_Object are fast and always aligned. Do all compilers optimize that case? For MSVC we still have a specialized Py_MEMCPY() variant in pyports.h.

I can see three more ways to fix the issue:

Have two loops, one for the aligned case with memcpy() and one for the unaligned case w/o memcpy()
Add a special variant of _le64toh() for PY_LITTLE_ENDIAN on ARM and use the current variant on X86_64.
Make it illegal to call _Py_HashBytes() with non-aligned pointer and require the caller to provide an aligned buffer. It's easy for datetime but requires an extra buffer memoryview. Memoryview already uses a buffer for all but single-strided C contiguous views. We can easily add another case for non-aligned buffers.

FWIW, MSVC optimizes memcpy:

http://bugs.python.org/issue15993

The pgo issue has been fixed according to Steve Dower.

a variant of the patch that keeps the parameter types of _le64toh.

I can check, if the memcpy is optimized away. As an alternative, we could use __builtin_memcpy. That is available for clang as well (would have to check icc).

I created bpo-28126 for MSVC.

I believe the unaligned memory access configure check is supposed to
prevent siphash from being used, so we might look into why that's not
working.

IMO, though, we should just require alignment for the argument to
_PyHash_Bytes. It's private after all.

If I understand it correctly, the hash value differs depending on the kernel configuration when the python binary is built, leading to different pickle objects which cannot be shared, making them incompatible . I think the safest thing would be to remove the hash make the selection of the hash method unconditional, and to make this hash function working for all cases.

32-bit and 64-bit SPARC ABIs have 64-bit integer data types.

SPARC, like many RISC architectures, also has natural alignment requirements. Attempting to dereference a pointer to a 4-byte-sized object requires 4-byte alignment, for example. 2-byte-sized objects require 2-byte alignment. 8-byte-sized objects require 8-byte alignment.

siphash24 is encountering this bug on modern SPARC (32-bit ABI currently, haven't tried compiling as 64-bit yet). The code simply is not portable.

Benjamin's patch gets the failing self-test (test_plistlib) to pass as well as the simple test case in msg275493 above.

I agree with Stefan and Serhiy. Unaligned memoryviews shouldn't trigger a copy when hashing.

So, what is the problem with this? Either the compiler knows that unaligned accesses are no problem and optimizes them away anyway, or it is kept because it would crash otherwise. I can confirm that no sparc version >= 3.5 (have not tried older) survives the test suite on Gentoo Sparc (64 bit kernel, 32 bit userspace) without memcpy().

What's the status of this? It looks like Serhiy has reviewed and approved Dakon's PR 6123. Is everyone OK with merging it? Anything more needed?

New changeset 1e2ec8a by Serhiy Storchaka (Rolf Eike Beer) in branch 'master':
bpo-28055: Fix unaligned accesses in siphash24(). (GH-6123)
1e2ec8a

New changeset 8ed545f by Miss Islington (bot) in branch '3.7':
bpo-28055: Fix unaligned accesses in siphash24(). (GH-6123)
8ed545f

New changeset 0d17e60 by Miss Islington (bot) in branch '3.6':
bpo-28055: Fix unaligned accesses in siphash24(). (GH-6123)
0d17e60

MSVC optimizes memcpy() to an assignment, sometimes too well (pgo): https://bugs.python.org/issue15993

But that is fixed long ago, so I also think that the memcpy() approach is best.

Indeed the memcpy() approach is the common idiom in such situations, and sounds like the right thing.

I know this is a bit late but I wanted to share...

OpenCSW has a build farm with Solaris machines and Sparc hardware. The farm provides x86 and Sparc machines with Solaris 9 through 11.

I believe OpenCSW operates in the same spirit as GCC compile farm. They welcome open source developers and upstream maintainers to help ensure packages build and run on Solaris machines.

You can read about it at
https://www.opencsw.org/extend-it/signup/to-upstream-maintainers/ .

If Python is performing memory access patterns as discussed in the report then it would probably benefit the project to test on a Sparc machine with Solaris 11.

I would say that Python no longer officially supports sparc and solaris
because of the lack of volunteer.

I see that a fix has been pushed. I'm not sure why this issue is still open, so I close it.

Navigation Menu

Repository navigation

pyhash's siphash24 assumes alignment of the data pointer #72242

18 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

pyhash's siphash24 assumes alignment of the data pointer #72242

Description

Activity

doko42 commented on Sep 9, 2016

tiran commented on Sep 9, 2016

benjaminp commented on Sep 10, 2016

doko42 commented on Sep 10, 2016

ztane commented on Sep 11, 2016

doko42 commented on Sep 13, 2016

tiran commented on Sep 13, 2016

skrah commented on Sep 13, 2016

doko42 commented on Sep 13, 2016

doko42 commented on Sep 13, 2016

tiran commented on Sep 13, 2016

doko42 commented on Sep 13, 2016

18 remaining items

gco commented on Jan 28, 2017

pitrou commented on Jan 28, 2017

DerDakon commented on Mar 26, 2018

ned-deily commented on May 1, 2018

serhiy-storchaka commented on May 13, 2018

miss-islington commented on May 13, 2018

miss-islington commented on May 13, 2018

skrah commented on May 13, 2018

pitrou commented on May 13, 2018

JeffreyWalton commented on Jul 21, 2018

vstinner commented on Jul 22, 2018

vstinner commented on Apr 12, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions