obmalloc's 8-byte alignment causes undefined behavior #72174
Comments
|
ubsan complains about unaligned access when structs include "long double". An example error: This is because (on x86 anyway), long double is 16-bytes long and requires that alignment, but obmalloc only gives a 8-byte alignment. (glibc malloc() gives 16-byte alignment.) I'm attaching a POC patch. I don't know what the impact of increasing the alignment is on obmalloc's performance or memory usage. It's also unfortunate that this patch increases the size of PyGC_Head to 32 bytes from 24 bytes. One can imagine a more middle-ground solution to this by allowing types to specify their required alignment. |
benjaminp
added
3.7 (EOL)
|
What do we do if at some point a C type requires a larger alignment (for example a vector type readable using AVX512 instructions)? |
Can we use memcpy() to prevent such issue? |
|
My suggestion would be to pass alignof(type) into the allocator via macro. Then the allocator could at least assert it's providing good enough alignment if not provide the correct alignment. I believe 16-byte alignment is special because it's glibc's malloc's default. So "normal" code shouldn't really be expecting anything better than 16-byte alignment. Code with higher alignment requirements will have to use APIs like the one proposed in bpo-18835. |
Do you mean using some new PyMem_ function? Or as as new tp_ field on the type declaration? |
|
What matters when a Python object is allocated? The start of the PyObject structure, or the start of the PyGC_Head structure? Would it be possible to align the PyObject start? The simplest option is to store data which needs to be aligned in a second memory block allocated by PyMem_AlignedAlloc(). |
|
Change by Antoine Pitrou: "versions: -Python 2.7, Python 3.3, Python 3.4, Python 3.5, Python 3.6" The undefined behaviour exists and should be fixed in Python 2.7 and 3.6, no? Can we use memcpy()? |
Hmm, perhaps. Do you want to try it out (and measure any performance degradation)? |
|
Since we have "#define PYMEM_FUNCS PYOBJ_FUNCS", I think extensions that But guess technically they should. |
|
Yes, we could memcpy things around to obtain the desired alignment. It would be nicer to have a builtin solution, though. |
|
alignment.patch: + long double dummy; /* force worst-case alignment */ Would it be possible to use max_align_t mentioned by Stefan, at least when this type is available? What is the impact of the patch on objects size? |
|
On Wed, Nov 8, 2017, at 06:14, STINNER Victor wrote:
Yes, that would be the correct thing to do. I was looking for the quick
On 64-bit platforms, I believe it wastes a word for GC objects. |
|
FYI, this would seem to be an incentive to get my "bitmaps for small GC objects" idea implemented. I.e. https://mail.python.org/pipermail/python-dev/2017-September/149307.html If implemented, the extra size of the PyGC_Head would only apply to "large" objects. In my prototype, I'm thinking of using 512 bytes as the size limit for small GC objects. |
|
This bug causes miscompilation of Python 2.7 by GCC 8 on x86-64 (with no sanitizers enabled, just compiler optimization). I think this is a fairly conservative way for papering over the issue: https://mail.python.org/pipermail/python-dev/2018-January/152011.html |
|
While this issue looked purely theorical to me 3 years ago, it is now very concrete: bpo-36618 "clang expects memory aligned on 16 bytes, but pymalloc aligns to 8 bytes". |
|
Now PyGC_Head is 16byte on 64bit platform. How about 32bit platforms? |
|
PyGC_Head structure size depends on the Python version, sizes of 64-bit:
bpo-36618 "clang expects memory aligned on 16 bytes, but pymalloc aligns to 8 bytes" should be even worse on 3.7: 24 is not aligned on 16. I don't understand why nobody saw this alignment issue previously. Maybe clang only became stricer about 16 bytes alignment recently? 2.7: typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_prev;
Py_ssize_t gc_refs;
} gc;
double dummy; /* Force at least 8-byte alignment. */
char dummy_padding[sizeof(union _gc_head_old)];
} PyGC_Head;3.7: typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_prev;
Py_ssize_t gc_refs;
} gc;
double dummy; /* force worst-case alignment */
} PyGC_Head;3.8: typedef struct {
// Pointer to next object in the list.
// 0 means the object is not tracked
uintptr_t _gc_next;} PyGC_Head; In 3.8, the union used to ensure alignment on a C double is gone. |
|
I had not noticed bpo-33374 changed Python 2.7. |
|
The x86-64 ABI requires that memory allocated on the heap is aligned to 16 bytes. On x86-64, glibc malloc(size) aligns on 16 bytes for size >= 16, otherwise align to 8 bytes. So the glibc doesn't respect exactly the ABI. I understand that a compiler will not use instructions which require 16B align on a memory block smaller than 16B, so align to 8B for size < 16B should be fine *in practice*. Python objects are at least 16B because of PyObject header. Moreover, objects tracked by the GC gets additional 16B header from PyGC_Head. But pymalloc is also used for PyMem_Malloc() since Python 3.6, and PyMem_Malloc() is used to allocate things which are not PyObject. |
|
Minor correction: glibc malloc follows ABI on x86-64 and always returns a 16-byte-aligned pointer, independently of allocation size. However, other mallocs (such as jemalloc and tcmalloc) may return pointers with less alignment for allocation sizes less than 16 bytes, violating ABI. They still follow ABI for allocations of 16 bytes and more. But as you said, the distinction should not matter for Python because of the object header. Furthermore, without LTO, the compiler will not be able to detect that a pointer returned from Py_NewObject is a top-level allocation, and therefore has to be more conservative about alignment, using information from the type definitions only. |
Note that two uintptr_t is aligned 16bytes on 64bit platforms and 8bytes on 32bit platforms. Python 3.7 is worse than 3.8. But it means +8 bytes for all tuples. If we backport PR-12850 to 3.7, +8 bytes for 1/2 tuples, and +16 bytes for remaining tuples. Any ideas about reduce impact for Python 3.7? I wonder if we can add -fmax-type-align=8 for extension types... |
No, we cannot: it's a temporary fix. The flag causes compilation error if it's added to old version of clang or to a C compiler different than clang.
I don't think that it's a matter of performance here. What matters the most here is correctness. See Florian Weimer's message: "This issue potentially affects all compilers, not just Clang." |
$ ./python -m perf compare_to master.json align16.json -G --min-speed=1
Slower (13):
- pickle_list: 4.40 us +- 0.03 us -> 4.59 us +- 0.04 us: 1.04x slower (+4%)
- xml_etree_iterparse: 129 ms +- 2 ms -> 133 ms +- 2 ms: 1.04x slower (+4%)
- regex_dna: 201 ms +- 2 ms -> 207 ms +- 2 ms: 1.03x slower (+3%)
- scimark_sparse_mat_mult: 5.75 ms +- 0.01 ms -> 5.90 ms +- 0.05 ms: 1.03x slower (+3%)
- float: 147 ms +- 1 ms -> 151 ms +- 1 ms: 1.02x slower (+2%)
- unpickle: 19.0 us +- 0.6 us -> 19.4 us +- 0.7 us: 1.02x slower (+2%)
- nbody: 173 ms +- 1 ms -> 176 ms +- 1 ms: 1.02x slower (+2%)
- pickle: 12.4 us +- 0.1 us -> 12.6 us +- 0.2 us: 1.02x slower (+2%)
- html5lib: 121 ms +- 3 ms -> 123 ms +- 4 ms: 1.02x slower (+2%)
- unpickle_list: 4.88 us +- 0.04 us -> 4.95 us +- 0.12 us: 1.02x slower (+2%)
- xml_etree_process: 107 ms +- 1 ms -> 109 ms +- 1 ms: 1.01x slower (+1%)
- regex_effbot: 3.60 ms +- 0.05 ms -> 3.65 ms +- 0.03 ms: 1.01x slower (+1%)
- xml_etree_parse: 185 ms +- 1 ms -> 187 ms +- 3 ms: 1.01x slower (+1%)Faster (11):
Benchmark hidden because not significant (33): 2to3, chaos, crypto_pyaes, deltablue, go, hexiom, json_loads, logging_silent, logging_simple, mako, pickle_dict, pickle_pure_python, pidigits, python_startup, python_startup_no_site, raytrace, regex_compile, regex_v8, scimark_fft, scimark_lu, scimark_monte_carlo, scimark_sor, spectral_norm, sqlalchemy_declarative, sqlalchemy_imperative, sqlite_synth, sympy_integrate, sympy_sum, sympy_str, telco, unpack_sequence, unpickle_pure_python, xml_etree_generate |
$ ./python -m perf compare_to master-mem.json align16-mem.json -G --min-speed=2
Slower (30):
- float: 20.6 MB +- 12.6 kB -> 23.8 MB +- 30.3 kB: 1.16x slower (+16%)
- mako: 14.3 MB +- 760.5 kB -> 15.1 MB +- 54.1 kB: 1.06x slower (+6%)
- xml_etree_iterparse: 11.1 MB +- 11.8 kB -> 11.6 MB +- 22.1 kB: 1.05x slower (+5%)
- html5lib: 19.0 MB +- 31.0 kB -> 19.8 MB +- 51.8 kB: 1.04x slower (+4%)
- dulwich_log: 10.9 MB +- 133.1 kB -> 11.3 MB +- 29.1 kB: 1.03x slower (+3%)
- json_dumps: 7907.6 kB +- 6242 bytes -> 8156.0 kB +- 23.9 kB: 1.03x slower (+3%)
- sympy_str: 33.5 MB +- 17.5 kB -> 34.5 MB +- 23.2 kB: 1.03x slower (+3%)
- deltablue: 8163.2 kB +- 9220 bytes -> 8391.2 kB +- 15.6 kB: 1.03x slower (+3%)
- pathlib: 8296.0 kB +- 15.0 kB -> 8526.4 kB +- 33.4 kB: 1.03x slower (+3%)
- xml_etree_generate: 11.8 MB +- 87.2 kB -> 12.2 MB +- 108.2 kB: 1.03x slower (+3%)
- sympy_expand: 32.7 MB +- 15.1 kB -> 33.6 MB +- 19.9 kB: 1.03x slower (+3%)
- richards: 7081.6 kB +- 16.2 kB -> 7270.8 kB +- 55.2 kB: 1.03x slower (+3%)
- pickle: 7244.4 kB +- 12.1 kB -> 7436.4 kB +- 57.1 kB: 1.03x slower (+3%)
- pickle_pure_python: 7267.2 kB +- 12.2 kB -> 7455.2 kB +- 48.2 kB: 1.03x slower (+3%)
- pickle_dict: 7258.8 kB +- 27.6 kB -> 7446.0 kB +- 36.7 kB: 1.03x slower (+3%)
- hexiom: 7168.8 kB +- 25.1 kB -> 7352.8 kB +- 59.8 kB: 1.03x slower (+3%)
- raytrace: 7373.6 kB +- 17.0 kB -> 7562.8 kB +- 44.3 kB: 1.03x slower (+3%)
- pickle_list: 7246.8 kB +- 9067 bytes -> 7431.2 kB +- 60.2 kB: 1.03x slower (+3%)
- spectral_norm: 6913.2 kB +- 5127 bytes -> 7087.2 kB +- 39.8 kB: 1.03x slower (+3%)
- sympy_integrate: 32.6 MB +- 24.9 kB -> 33.4 MB +- 36.0 kB: 1.02x slower (+2%)
- regex_compile: 8188.4 kB +- 10.9 kB -> 8388.8 kB +- 27.2 kB: 1.02x slower (+2%)
- nqueens: 7153.6 kB +- 17.2 kB -> 7328.4 kB +- 38.3 kB: 1.02x slower (+2%)
- sqlalchemy_declarative: 18.1 MB +- 40.9 kB -> 18.5 MB +- 50.0 kB: 1.02x slower (+2%)
- django_template: 18.4 MB +- 50.2 kB -> 18.8 MB +- 23.7 kB: 1.02x slower (+2%)
- sympy_sum: 52.1 MB +- 30.8 kB -> 53.4 MB +- 26.7 kB: 1.02x slower (+2%)
- regex_v8: 8208.0 kB +- 11.2 kB -> 8399.2 kB +- 43.2 kB: 1.02x slower (+2%)
- sqlalchemy_imperative: 17.4 MB +- 51.0 kB -> 17.8 MB +- 47.9 kB: 1.02x slower (+2%)
- json_loads: 7025.6 kB +- 71.0 kB -> 7173.6 kB +- 9098 bytes: 1.02x slower (+2%)
- xml_etree_process: 11.6 MB +- 160.1 kB -> 11.8 MB +- 141.1 kB: 1.02x slower (+2%)
- logging_silent: 7275.6 kB +- 37.5 kB -> 7425.2 kB +- 41.9 kB: 1.02x slower (+2%)Faster (1):
Benchmark hidden because not significant (26): 2to3, chameleon, chaos, crypto_pyaes, fannkuch, go, logging_format, logging_simple, meteor_contest, nbody, pidigits, python_startup, python_startup_no_site, regex_dna, regex_effbot, scimark_fft, scimark_lu, scimark_monte_carlo, scimark_sor, scimark_sparse_mat_mult, telco, unpack_sequence, unpickle, unpickle_list, unpickle_pure_python, xml_etree_parse |
|
+16% for float seems pretty high though. |
|
yes. sys.getsizeof(3.14) is 24. And it becomes 32 byte in 16byte aligned pymalloc. (+33%) FYI, jemalloc has 8, 16, 32 size classes, but no 24 too. |
I've been doing some reading and trying to understand this issue. My understanding is that malloc() needs to return pointers that are 16-byte aligned on AMD64 but, in general, pointers don't have the be aligned that way. If you have a structure that contains a "long double" then that member also has to be 16-bit aligned. It seems to me that we don't need to have the PyObject structure containing a Python float to be 16-byte aligned. If so, could we introduce a new obmalloc API that returns memory with 8-byte alignment, for use by objects that know they don't require 16-byte alignment? floatobject.c could use this API to avoid the 33% overhead. The new obmalloc API could initially be internal use only until we can come up with a design we know we can live with long term. |
PyMem_Malloc / PyObject_Malloc only have one parameter: "size". It knows nothing about the allocated structure. bpo-18835 discussed the idea of adding a new API which accept an alignment parameter. The issue was closed because of the lack of concrete usage. In the clang crash bpo-36618 (which decided us to fix this issue), C alignof() function was discussed: Copy of serge-sans-paille's comment: "@vstinner: once you have a portable version of alignof, you can deciding to *not* use the pool allocator if the required alignment is greater than 8B, or you could modify the pool allocator to take alignment information as an extra parameter?" |
|
We now have a concrete use case. ;-) My idea was that we can introduce a new, CPython internal API that E.g. for non-subclasses of float, we know the PyObject structure does E.g. in PyFloat_FromDouble, rather than: PyObject_MALLOC(sizeof(PyFloatObject)) we could call something like: _PyObject_MALLOC_ALIGNED(sizeof(PyFloatObject), 8) This internal API would not be a permanent solution. Having to manually In the long term, we would need a better solution. E.g. an API that can |
|
Neil, I don't see the point of having this discussion here. |
|
long double was changed to double seven years ago to avoid a different kind of undefined behavior... e348c8d#diff-fb41bdaf12f733cf6ab8a82677d03adc We are going in circles here. Submitting that PR to 3.7 caused the undefined behavior sanitizer buildbot to go back to reporting a ton more damage. build before: https://buildbot.python.org/all/#/builders/137/builds/878 |
|
commit reverted in 2156fec |
|
I'm not marking this bug as "Fixed" as the original complaint about obmalloc'd structs with a long double not being aligned is still going to be true on 32-bit platforms for 2.7 - 3.7. We've merely increased the obmalloc alignment to 16-bytes on 64-bit platforms. So the problem should only remain for 32-bit users which at this point are likely only arm (rpi and similar low end friends not using a 64-bit OS). |
|
Here is what I've found for (32-bit) ARM:
And on (32-bit) x86, it looks like the standard alignment for "long double" is 4 bytes: So I don't think there's anything to change on 32-bit Python builds *if* we only really care about ARM and x86 (which is restrictive, but using "long double" in C extension types is a bit of an exotic issue). |
|
And of course, someone who has this issue can at worse recompile Python without pymalloc. |
|
if someone runs into an actual need for this on 32-bit builds, please provide details and feel free to reopen the issue. closing as i don't believe there is any more for us to do. |
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:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: