classification
Title: pyhash's siphash24 assumes alignment of the data pointer
Type: crash Stage: patch review
Components: Interpreter Core Versions: Python 3.7, Python 3.6, Python 3.5
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: doko Nosy List: benjamin.peterson, christian.heimes, doko, gco, ned.deily, pitrou, serhiy.storchaka, skrah, vstinner, ztane
Priority: high Keywords: patch

Created on 2016-09-09 23:29 by doko, last changed 2017-01-28 15:01 by pitrou.

Files
File name Uploaded Description Edit
pyhash.diff doko, 2016-09-13 12:14
pyhash2.diff doko, 2016-09-13 12:24
hash-bytes-alignment.patch benjamin.peterson, 2016-09-14 04:46 review
Messages (31)
msg275493 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-09 23:29
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.
msg275500 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-09 23:45
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.
msg275509 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2016-09-10 00:28
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.
msg275634 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-10 13:07
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.
msg275761 - (view) Author: Antti Haapala (ztane) * Date: 2016-09-11 10:00
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.
msg276255 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 11:52
updated patch that always used memcpy for the little endian case.
msg276257 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-13 12:15
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:

1) Have two loops, one for the aligned case with memcpy() and one for the unaligned case w/o memcpy()
2) Add a special variant of _le64toh() for PY_LITTLE_ENDIAN on ARM and use the current variant on X86_64.
3) 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.
msg276258 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-13 12:20
FWIW, MSVC optimizes memcpy:

  http://bugs.python.org/issue15993


The pgo issue has been fixed according to Steve Dower.
msg276259 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 12:24
a variant of the patch that keeps the parameter types of _le64toh.
msg276261 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 12:27
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).
msg276263 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-13 12:32
I created #28126 for MSVC.
msg276345 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 21:19
> 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.
msg276346 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 21:21
... would be to remove the autoconf check and make the selection of the hash method unconditional ...
msg276347 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-13 21:30
The main reason for two different hash algorithms was missing support for 64bit integer types. Python 3.4 was targeting platforms that had no 64bit integer support at all (IIRC SPARC). Nowaday Python requires 64bit ints to compile.

I'm all in favor to remove FVN2 and use SipHash24 on all platforms. Let's deprecated it now and remove it in 3.7.
msg276352 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2016-09-13 21:54
if the only concern is 32bit sparc, then please let's drop this in 3.6.

Looking at #28027 the new way to obsoleting things seems to be decreeing them (sorry about the sarcasm).  If I interpret your concerns correctly you care about platforms, which you are not supposed to care about. sparc32 doesn't have any use cases now, while ARM32 still has, and will have for some time.
msg276355 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-09-13 22:14
> IMO, though, we should just require alignment for the argument to _PyHash_Bytes. It's private after all.

And what to do with memoryview? Memoryview data can be not aligned.

> 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 .

Hash values shouldn't be leaked in pickle.
msg276374 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2016-09-14 04:46
Here's a patch that requires 8-byte alignment. It almost completely works except that on ABIs with 32-bit pointers, unicode objects can have their data pointers aligned at only 4-bytes. Perhaps we can get away with requiring only 4-byte alignment on 32-bit platforms because they generally have implement the 64-bit load as 2 32-bit loads anyway.
msg276394 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 08:03
For memoryview this is not possible: It is explicitly unaligned and the feature is used in e.g. NumPy.
msg276396 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-14 08:19
It's totally possible. Benjamin's patch implements it like I have suggested it.
msg276397 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 08:23
Ah, yes. But compilers optimize memcpy and this is a guaranteed slowdown for the unaligned memoryview case.
msg276399 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-14 08:39
How often does NumPy create a C-style, single dimensional, continuous memoryview? I would assume that it deals with matrices, Fortran data and/or other strides, multi-dimensional data in almost all cases.
msg276404 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 09:39
Numpy itself internally doesn't. Consumers of numpy arrays use
memoryviews. Numpy is often used as a library these days, even
for simple things like storing a 2-d table, which can easily be
several TB.

It is also easy to generate unaligned data by just taking a slice
of a bytes memoryview.
msg276406 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 09:42
s/unaligned/not 8-byte-aligned/
msg276407 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-14 09:43
memoryview() has to create a copy for NumPy memoryviews already.
msg276408 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 09:50
I don't understand this. Could you explain?
msg276409 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2016-09-14 09:54
memory_hash has to convert buffers unless the buffer is a single-dimensional, C-style and contiguous buffer. A NumPy matrix has more than one dimension, so it must be converted.

https://hg.python.org/cpython/file/tip/Objects/memoryobject.c#l2854

        if (!MV_C_CONTIGUOUS(self->flags)) {
            mem = PyMem_Malloc(view->len);
            if (mem == NULL) {
                PyErr_NoMemory();
                return -1;
            }
            if (buffer_to_contiguous(mem, view, 'C') < 0) {
                PyMem_Free(mem);
                return -1;
            }
        }
msg276411 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-14 10:01
I see. No, most NumPy arrays are C-contiguous. Multi-dimmensional arrays
are contiguous, too.

Non C-contiguous arrays arise mostly during slicing or if they're
Fortran-order to begin with.


But NumPy aside, it's weird to have slice of a huge regular bytes view
(this particular slice is still C-contiguous) that is suddenly copied
because the alignment requirements changed.

I really prefer a simple rule for memoryview: If the data is C-contiguous,
you get the fast path.
msg276412 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-09-14 10:16
I support Stefan. Just requiring 8-byte align is the easiest solution, but it doesn't work with memoryview without expensive memory allocation and copying.

Look at the FNV code. It supports non-4-byte aligned data, and does it in a safe and efficient way.
msg276495 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-09-14 22:56
Christian Heimes added the comment:
> The main reason for two different hash algorithms was missing support for
64bit integer types. Python 3.4 was targeting platforms that had no 64bit
integer support at all (IIRC SPARC). Nowaday Python requires 64bit ints to
compile.
>
> I'm all in favor to remove FVN2 and use SipHash24 on all platforms. Let's
deprecated it now and remove it in 3.7.

Python 3.5.0 doesn't compile if the compiler doesn't support 64 signed
integer: see pytime.h ;-)

Are you aware of platforms still using FVN2?

I'm also in favor of deprecating it. Maybe use #warning in C to log a
deprecation warning.
msg286391 - (view) Author: Greg Onufer (gco) Date: 2017-01-28 00:19
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.
msg286412 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-01-28 15:01
I agree with Stefan and Serhiy.  Unaligned memoryviews shouldn't trigger a copy when hashing.
History
Date User Action Args
2017-01-28 15:01:24pitrousetnosy: + pitrou
messages: + msg286412
2017-01-28 00:19:45gcosetnosy: + gco
messages: + msg286391
2016-09-15 03:41:09ned.deilysetpriority: normal -> high
stage: needs patch -> patch review
versions: + Python 3.7
2016-09-14 22:56:59vstinnersetmessages: + msg276495
2016-09-14 10:16:17serhiy.storchakasetmessages: + msg276412
2016-09-14 10:01:53skrahsetmessages: + msg276411
2016-09-14 09:54:06christian.heimessetmessages: + msg276409
2016-09-14 09:50:46skrahsetmessages: + msg276408
2016-09-14 09:43:07christian.heimessetmessages: + msg276407
2016-09-14 09:42:28skrahsetmessages: + msg276406
2016-09-14 09:39:46skrahsetmessages: + msg276404
2016-09-14 08:39:28christian.heimessetmessages: + msg276399
2016-09-14 08:23:38skrahsetmessages: + msg276397
2016-09-14 08:19:13christian.heimessetmessages: + msg276396
2016-09-14 08:03:37skrahsetmessages: + msg276394
2016-09-14 04:46:29benjamin.petersonsetfiles: + hash-bytes-alignment.patch

messages: + msg276374
2016-09-13 23:09:39gvanrossumsetnosy: - gvanrossum
2016-09-13 22:14:53serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg276355
2016-09-13 21:55:29dokosetnosy: + gvanrossum, ned.deily
2016-09-13 21:54:40dokosetmessages: + msg276352
2016-09-13 21:30:31christian.heimessetmessages: + msg276347
2016-09-13 21:21:55dokosetmessages: + msg276346
2016-09-13 21:19:40dokosetmessages: + msg276345
2016-09-13 12:32:53christian.heimessetmessages: + msg276263
2016-09-13 12:27:47vstinnersetnosy: + vstinner
2016-09-13 12:27:09dokosetmessages: + msg276261
2016-09-13 12:24:30dokosetfiles: + pyhash2.diff

messages: + msg276259
2016-09-13 12:20:20skrahsetnosy: + skrah
messages: + msg276258
2016-09-13 12:15:41christian.heimessettype: crash
messages: + msg276257
stage: needs patch
2016-09-13 12:14:40dokosetfiles: - pyhash.diff
2016-09-13 12:14:22dokosetfiles: + pyhash.diff
2016-09-13 11:52:27dokosetfiles: - pyhash.diff
2016-09-13 11:52:13dokosetfiles: + pyhash.diff

messages: + msg276255
2016-09-11 10:00:33ztanesetnosy: + ztane
messages: + msg275761
2016-09-10 13:07:53dokosetmessages: + msg275634
2016-09-10 00:28:59benjamin.petersonsetnosy: + benjamin.peterson
messages: + msg275509
2016-09-09 23:45:30christian.heimessetmessages: + msg275500
2016-09-09 23:42:54dokosetfiles: - pyhash.diff
2016-09-09 23:42:24dokosetfiles: + pyhash.diff
2016-09-09 23:29:50dokosetnosy: + christian.heimes
2016-09-09 23:29:02dokocreate