bpo-18835: Add PyMem_AlignedAlloc() #4089

vstinner · 2017-10-23T17:08:01Z

Add aligned_alloc and aligned_free fields to PyMemAllocatorEx
Rename PyMemAllocatorEx structure to PyMemAllocatorEx2 to make sure
that C extensions are upgraded to fill the new aligned_alloc and
aligned_free fields
Add 6 new functions:
- PyMem_RawAlignedAlloc()
- PyMem_RawAlignedFree()
- PyMem_AlignedAlloc()
- PyMem_AlignedFree()
- PyObject_AlignedAlloc()
- PyObject_AlignedFree()

https://bugs.python.org/issue18835

pitrou · 2017-10-23T20:56:28Z

Doc/c-api/memory.rst

Do people have to provide aligned_alloc and aligned_free? Or can they leave those pointers NULL and get a default implementation?

Currently, you must provide all allocator functions, included aligned_alloc and aligned_free.

Technically, we can implement a fallback, but I'm not sure that I want to do that :-)

vstinner · 2017-10-24T10:38:48Z

AppVeyor crashed with a heap corruption (exception c0000374) on:

test__testcapi (test.test_capi.Test_testcapi) ... Windows fatal exception: code 0xc0000374

vstinner · 2017-10-25T14:35:14Z

TODO: _PyMem_DebugRawAlignedAlloc() is currently a copy of _PyMem_DebugRawAlloc(). Instead, it should trap such bug: PyMem_Free() called on a memory blocked allocated by PyMem_AlignedAlloc(). Maybe it should store the alignment as well, to dump it in a fatal error message?

vstinner · 2017-10-26T17:57:37Z

AppVeyor crashed with a heap corruption (...)

I rebuild Python from scratch in Debug|x64: I am unable to reproduce the bug. Strange.

skrah · 2017-10-27T07:56:26Z

Objects/obmalloc.c

As I understand the man page, posix_memalign() can return other error codes, which are not necessarily negative. I suggest != 0.

skrah · 2017-10-27T08:03:48Z

Objects/obmalloc.c

This looks like an accidental leftover from an earlier version. :)

The manual page doesn't explicitly say that posix_memalign() never returns NULL on success. Whereas NULL is documented as an error condition for aligned_alloc(), memalign(), valloc() et pvalloc(). Why does posix_memalign() return an integer if it cannot return NULL on success? In case of doubt, I chose to explicitly reject NULL.

At least, size=0 is replaced with size=1, as do in other Python memory allocators, to avoid returning NULL. posix_memalign() manual page:
"If size is 0, then the value placed in *memptr is either NULL, or a unique pointer value that can later be successfully passed to free(3)."

http://pubs.opengroup.org/onlinepubs/009695399/functions/posix_memalign.html is clearer:

"Upon successful completion, posix_memalign() shall return zero; otherwise, an error number shall be returned to indicate the error."

Why does posix_memalign() return an integer if it cannot return NULL on success?

Someone just thought it would be a good idea to return ENOMEM etc. directly. Perhaps
just to avoid the errno dance.

The opengroup wording sounds like "success if and only if the return value is 0".

Fixed: I replaced the test with an assertion ;-)

vstinner · 2017-10-27T10:12:43Z

TODO: _PyMem_DebugRawAlignedAlloc() is currently a copy of _PyMem_DebugRawAlloc(). Instead, it should trap such bug: PyMem_Free() called on a memory blocked allocated by PyMem_AlignedAlloc(). Maybe it should store the alignment as well, to dump it in a fatal error message?

Done. PyMem_Free(PyMem_AlignedAlloc()) now fails as expected. I simply chose to use uppercase for the API identifier. I added an unit test to test exactly this.

I also documented newly added functions. I'm not sure of my documentation on the alignment:

+   Depending on the platform, not all values of *alignment* are accepted. Some
+   platforms require *alignment* to be a power of 2, others require *alignment*
+   to be a multiple of ``sizeof(void*)``.

Windows requires alignment to be "an integer power of 2". Maybe we should suggest to always use powers of 2 to best portability? I would be surprised if PyMem_AlignedAlloc() fails with an alignment equals to a power of 2.

skrah · 2017-10-27T10:17:08Z

Objects/obmalloc.c

Thanks for the change. Still, why would the function return NULL on success if size is guaranteed to be > 0?

posix_memalign() would be spectacularly broken if it did that.

So I find the comment and assert() confusing.

I removed the comment but kept the assertion just in case.

I prefer an assertion to get an helpful error message rather than a crash in a random part of the code :-(

There would be no crash. People have to check the return value
of _PyMem_RawAlignedAlloc() for NULL in any case.

The thing is: Unusual asserts() have a cost for people reading the code. The reader wonders "does the Python core developer know something I don't".

"There would be no crash. People have to check the return value of _PyMem_RawAlignedAlloc() for NULL in any case."

If posix_memalign() returns NULL on success, but your code raises a MemoryError exception if the pointer is NULL, you leak memory and your fails whereas the allocation succeeded.

This case should never occur. I prefer to be super careful and make sure that posix_memalign() never returns NULL on success.

Unusual asserts() have a cost for people reading the code.

Do you want me to add a comment explaining the assertion?

Yes, please add something like:

"This should never happen since we make sure that size > 0".

Also, pedantically, if the assert() is there then I'd use void *ptr = NULL; in the declaration. Because if we check "can never happen" conditions we might as well check that posix_memalign() sets the pointer at all.

vstinner · 2017-10-27T10:32:44Z

According to the discussion on https://bugs.python.org/issue18835 it seems like the feature (aligned memory allocations) is needed, so I finished my implementation:

new functions are now documented
new functions are now tested for corner cases
hooks on new functions are tested
debug hooks detect API misuse: PyMem_Free(PyMem_AlignedAlloc()), test required for Windows -- PyMem_Free(PyMem_AlignedAlloc()) does crash immediately on Windows! The debug hook helps to prevent such "portability" bug.
I simplified the documentation to: "alignment should be a power of 2 for the best portability."

The PR is now ready for a review.

skrah · 2017-10-27T12:00:15Z

Doc/c-api/memory.rst

Should we enforce C11?

http://en.cppreference.com/w/c/memory/aligned_alloc

"size - number of bytes to allocate. An integral multiple of alignment"

posix_memalign and _aligned_malloc don't care about the multiple though.

It took 17 years to support ISO C99 in CPython 3.6 :-D Python doesn't have to enforce anything. I prefer a thin wrapper on top of system allocator.

The question is more on the documentation.

posix_memalign and _aligned_malloc don't care about the multiple though.

In that case, I suggest to not say anything about the alignment of the size argument.

vstinner · 2017-10-27T12:48:21Z

I asked a colleague who works on the glibc: posix_memalign() cannot return NULL on success in the glibc.
https://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c;h=f94d51cca1b35952b15926883bb0256229ffb1fe;hb=HEAD#l5327

Extract:

5341   void *address = RETURN_ADDRESS (0);
5342   mem = _mid_memalign (alignment, size, address);
5343 
5344   if (mem != NULL)
5345     {
5346       *memptr = mem;
5347       return 0;
5348     }
5349 
5350   return ENOMEM;

By the way, posix_memalign() rejects alignment == 0 and alignement which is not a power of 2:

5333   /* Test whether the SIZE argument is valid.  It must be a power of
5334      two multiple of sizeof (void *).  */
5335   if (alignment % sizeof (void *) != 0
5336       || !powerof2 (alignment / sizeof (void *))
5337       || alignment == 0)
5338     return EINVAL;

Oh. PyObject_AlignedAlloc() doesn't reject allignement == 0. Should we reject it as well? (Return NULL in that case.)

vstinner · 2017-10-27T12:58:46Z

Oh wow, on Windows, _aligned_malloc() "simply" crash with abort() if called with alignment=0 or alignment=3 (not a power of 2)!

vstinner · 2017-10-27T13:13:39Z

I added a new commit to check alignment. New documentation:

+   *alignment* must be a power of 2 and greater than 0. If *alignment* is equal
+   to zero or is not a a power of 2, the function fails with an assertion error
+   in debug mode, or returns *NULL* in release mode.

skrah · 2017-10-27T13:21:07Z

On Fri, Oct 27, 2017 at 05:59:09AM -0700, Victor Stinner wrote: Oh wow, on Windows, _aligned_malloc() "simply" crash with abort() if called with alignment=0 or alignment=3 (not a power of 2)!

Haha, that's old school. :) I think it is not entirely unreasonable for a high performance function. I'd do all the Posix checks on Windows. if (alignment % sizeof (void *) != 0 || !powerof2 (alignment / sizeof (void *)) || alignment == 0) Then the Posix semantics are sort of official.

Object_AlignedAlloc() doesn't reject allignement == 0. Should we reject it as well? (Return NULL in that case.)

Yes, I think it should reject align==0 and !powerof2(align).

vstinner · 2017-10-27T13:38:18Z

alignment % sizeof (void *) != 0

Oh. I checked and posix_memalign(2, 100) fails with EINVAL even if alignment (=2) is a power of 2.

I modified my PR to also check that in check_alignment().

I propose to always check the alignment in Python even if the glibc posix_memalign() fails nicely with EINVAL, to get the same behaviour on all platforms. For example, with my current PR, PyMem_RawAlignedAlloc(0, 100) returns NULL in release mode, rather than crashing (on abort()), on Windows.

vstinner · 2017-10-27T14:05:30Z

@skrah: Does the PR look better with the new alignment checks?

vstinner · 2017-10-27T14:05:44Z

@pitrou: Would you mind to review this big PR please?

skrah · 2017-10-27T14:09:05Z

Objects/obmalloc.c

Move check_alignment(alignment) only in this path?

Ah yes, it makes sense. Done.

I also merged master into this PR.

skrah · 2017-10-27T14:11:17Z

Objects/obmalloc.c

I really think we should trust posix_memalign. :)

The posix_memalign() function shall fail if: [EINVAL] The value of the alignment parameter is not a power of two multiple of sizeof( void *). [ENOMEM] There is insufficient memory available with the requested alignment.

So I'd put it in the Windows path.

Done.

"I really think we should trust posix_memalign."

I didn't want to rely on the glibc. Since you confirmed that EINVAL is part of the POSIX standard, I agree to rely on it.

skrah · 2017-10-27T17:20:18Z

I wish the call chains were easier to understand. This one ends up calling the
non-aligned version:

/* Execute this (--with-pydebug) */
char *foo = PyMem_AlignedAlloc(8, 10000);

/* Call chain */
PyMem_AlignedAlloc (alignment=alignment@entry=8, size=size@entry=10000) at Objects/obmalloc.c:585
_PyMem_DebugAlignedAlloc (ctx=0x898b40 <_PyMem_Debug+64>, alignment=8, size=10000) at Objects/obmalloc.c:1765
_PyMem_DebugRawAlignedAlloc (ctx=ctx@entry=0x898b40 <_PyMem_Debug+64>, alignment=alignment@entry=8, nbytes=nbytes@entry=10000)
    at Objects/obmalloc.c:1613
_PyObject_AlignedAlloc (ctx=0x0, alignment=8, size=10032) at Objects/obmalloc.c:1438
_PyObject_Alloc (use_calloc=use_calloc@entry=0, ctx=ctx@entry=0x0, nelem=nelem@entry=1, elsize=elsize@entry=10032) at Objects/obmalloc.c:906

   ==> Objects/obmalloc.c:1112    result = PyMem_RawMalloc(nbytes);

skrah · 2017-10-27T17:54:36Z

Objects/obmalloc.c

alignment <= ALIGNMENT && size <= SMALL_REQUEST_THRESHOLD

should fix the call chain problem.

vstinner · 2017-10-31T14:12:41Z

_PyObject_AlignedAlloc(void *ctx, size_t alignment, size_t size)
{
    if (alignment <= ALIGNMENT) {

@skrah: "alignment <= ALIGNMENT && size <= SMALL_REQUEST_THRESHOLD" should fix the call chain problem.

Wow, my code was completely wrong :-)

Before fixing this bug, I wrote an unit test to make sure that PyMem_AlignedAlloc() respects the alignment constraint...

Ooops again, _PyMem_DebugRawAlignedAlloc() was wrong too: it didn't align correctly the pointer... I fixed that too.

Sometimes, it helps to write unit tests ;-)

vstinner · 2017-10-31T15:51:05Z

Oh ok, I understood the failure on Windows. _PyObject_AlignedAlloc() still fell back on the raw allocator rather than the aligned allocator, when pymalloc failed to allocated memory.

I had to rewrite the pymalloc allocator to give control to the caller how to fall back on another allocator.

vstinner · 2017-10-31T16:20:01Z

This PR became too big, so I extracted two changes:

PR bpo-20064: Document PyObject_Malloc() #4199: bpo-20064: Document PyObject_Malloc()
PR bpo-18835: Cleanup pymalloc #4200: bpo-18835: Cleanup pymalloc

Once these PR will be merged, I will rebase this PR on top of master.

vstinner · 2017-11-01T01:44:39Z

Oh, the Travis CI failed again with https://bugs.python.org/issue31910 I restarted the job.

* Add aligned_alloc and aligned_free fields to PyMemAllocatorEx * Rename PyMemAllocatorEx structure to PyMemAllocatorEx2 to make sure that C extensions are upgraded to fill the new aligned_alloc and aligned_free fields * Add 6 new functions: * PyMem_RawAlignedAlloc() * PyMem_RawAlignedFree() * PyMem_AlignedAlloc() * PyMem_AlignedFree() * PyObject_AlignedAlloc() * PyObject_AlignedFree()

vstinner · 2017-11-01T02:50:51Z

I rebased my PR on top of master to get the fix for https://bugs.python.org/issue31910

vstinner · 2017-11-24T01:09:11Z

https://bugs.python.org/issue18835 has been rejected, so I closed this PR.

the-knights-who-say-ni added the CLA signed label Oct 23, 2017

bedevere-bot added the awaiting merge label Oct 23, 2017

vstinner changed the title ~~bpo-18835: Add PyMem_AlignedAlloc()~~ [WIP] bpo-18835: Add PyMem_AlignedAlloc() Oct 23, 2017

pitrou reviewed Oct 23, 2017

View reviewed changes

skrah reviewed Oct 27, 2017

View reviewed changes

vstinner changed the title ~~[WIP] bpo-18835: Add PyMem_AlignedAlloc()~~ bpo-18835: Add PyMem_AlignedAlloc() Oct 27, 2017

skrah reviewed Oct 27, 2017

View reviewed changes

Objects/obmalloc.c Outdated

Copy link

Contributor

skrah Oct 27, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

alignment <= ALIGNMENT && size <= SMALL_REQUEST_THRESHOLD

should fix the call chain problem.

vstinner mentioned this pull request Oct 31, 2017

bpo-18835: Cleanup pymalloc #4200

Merged

vstinner closed this Nov 24, 2017

vstinner deleted the memalign branch November 24, 2017 01:09

Uh oh!

bpo-18835: Add PyMem_AlignedAlloc() #4089

bpo-18835: Add PyMem_AlignedAlloc() #4089

Uh oh!

Conversation

vstinner commented Oct 23, 2017 • edited by bedevere-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vstinner commented Oct 24, 2017

Uh oh!

vstinner commented Oct 25, 2017

Uh oh!

vstinner commented Oct 26, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

skrah Oct 27, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

skrah Oct 27, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

skrah commented Oct 27, 2017 via email

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

vstinner commented Oct 27, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vstinner commented Oct 23, 2017 •

edited by bedevere-bot

Loading

skrah Oct 27, 2017 •

edited

Loading

skrah Oct 27, 2017 •

edited

Loading