classification
Title: Deques to adopt the standard clearing procedure for mutable objects
Type: behavior Stage: patch review
Components: Extension Modules Versions: Python 3.6, Python 3.5, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: python-dev, rhettinger, serhiy.storchaka, tim.peters, vstinner
Priority: normal Keywords: patch

Created on 2015-09-15 23:12 by rhettinger, last changed 2015-09-26 07:54 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
deque_nonreentrant_clear.diff rhettinger, 2015-09-15 23:13 Make the deque empty before clearing blocks. review
deque_nonreentrant_clear2.diff rhettinger, 2015-09-17 03:00 Fix final freeblock() call review
deque_nonreentrant_clear3.diff serhiy.storchaka, 2015-09-17 14:09 Don't create new block and don't use alternate method review
deque_nonreentrant_clear4.diff serhiy.storchaka, 2015-09-25 09:10 review
Messages (15)
msg250811 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-15 23:12
The clear method for deques is possibly reentrant.  Use the safer technique used in listobject.c, setobject.c, and dictobject.c.
msg250876 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-09-17 08:34
I left comments on Rietveld. Perhaps you missed Rietveld messages in the Spam folder.
msg250882 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-17 12:48
How does newblock() mutate the deque?  Does PyMem_Malloc() do anything other than call malloc()?  We hold the GIL so there doesn't seem to be a need to use PyMem_RawMalloc().
msg250883 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-09-17 12:58
"Does PyMem_Malloc() do anything other than call malloc()?  We hold the GIL so there doesn't seem to be a need to use PyMem_RawMalloc()."

Well, the difference between PyMem_Malloc() and PyMem_RawMalloc() is subtle. Right now, it should only impact debug tools hooking on the memory allocators.

But one day I would like to try to modify PyMem_Malloc() to reuse PyObject_Malloc(). I don't see why PyMem_Malloc() shouldn't be optimized for small applications. But it's hard to benchmark such change, and it depends on the platform. I already had to use different config for memory allocators depending on the platform :-/ The implementation of tracemalloc uses a different overallocation factor on Windows and on other platforms.
msg250890 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-09-17 14:09
Here is a patch that doesn't need newblock().
msg250913 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-17 19:24
Serhiy contends that calling newblock() can mutate the deque (its only external call is PyMem_Malloc()).  I'm trying understand how that could be possible if it is just a thin wrapper around malloc.

Before gumming-up the code in an effort to avoid calling newblock(), I want to understand whether there is an actual issue here and if so whether PyMem_RawMalloc() would solve the problem directly.
msg250915 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-09-17 19:51
I perhaps were overcautious. There is a difference between the case of deque and the case of lru_cache and OrderedDict. The latter creates Python object (PyDict_New) that can trigger garbage collecting, and the former calls only PyMem_Malloc. The latter can cause a crash in common use, and the former only with special memory allocation hooks (Victor, perhaps we should disable GC for executing hooks).

But my version of the patch solves not only this issue. It eliminates the use of possibly re-entrant alternate method.
msg251577 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-25 08:31
Victor, I was thinking of switching to PyMem_RawMalloc instead of PyMem_Malloc.  The advantages are that there are guaranteed to be no side-effects, the GIL doesn't need to be held, and there is less overhead.  Are there any disadvantage I should know about?

Serhiy, I'm still considering your patch.  I have a strong aversion to putting a big block on the stack and don't like having to do a full block memcpy every time a deque is cleared on deallocation.  If you don't see an actual bug in patch 2, I'm inclined to use that approach (especially since the popping fallback approach will likely never be called in practice).
msg251578 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-09-25 09:03
"Victor, I was thinking of switching to PyMem_RawMalloc instead of PyMem_Malloc.  The advantages are that there are guaranteed to be no side-effects, the GIL doesn't need to be held, and there is less overhead.  Are there any disadvantage I should know about?"

For me, PyMem_Malloc() can be faster than PyMem_RawMalloc() because the GIL is held. In practice... both function are very thin wrapper to malloc(), so it's exactly the same :-) In Objects/obmalloc.c, you have:

#define PYRAW_FUNCS _PyMem_RawMalloc, _PyMem_RawCalloc, _PyMem_RawRealloc, _PyMem_RawFree
...
#define PYMEM_FUNCS PYRAW_FUNCS

So PyMem_Malloc() and PyMem_RawMalloc() are *currently* exactly the same.

I'm not sure that you understand what you are trying to do. If you expect better performances, you should try to use PyObject_Malloc() instead, to benefit from the fast Python allocator for small allocations (512 bytes and less).
msg251579 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-09-25 09:10
Here is a patch that copies only used part of the block.

I don't see an actual bug in patch 2 besides that it fallbacks to current popping behavior.
msg251592 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-25 18:15
> I'm not sure that you understand what you are trying to do.

The goal is to avoid possible re-entrancy both now and in the future.  Since PyMem_RawMalloc is thread-safe and doesn't require the GIL to be held, it is guaranteed that there won't be a callback into regular Python that could mutate any of the data structures.
msg251595 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-09-25 18:51
The only way to be certain you're never going to face re-entrancy issues in the future is to call malloc() directly - and hope nobody redefines that too with some goofy macro ;-)

In the meantime, stick to PyMem_Malloc().  That's the intended way for code holding the GIL to do lowest-level memory allocation.  Uses of PyMem_RawMalloc() should be extremely rare, typically only in contexts where Python internals _know_ the GIL isn't being held, and can't reasonably try to acquire the GIL.  It's already being used in a few contexts where it probably shouldn't be, and each such use needlessly complicates future changes.

If PyMem_Malloc() does grow re-entrancy issues in the future, deques will be the least of our problems.  I'd strongly oppose it before then.  It's _intended_ to be as low level as possible (it was created to begin with just to worm around cross-platform insanity when called with a 0 argument).
msg251596 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-09-25 19:30
Thanks Timmy!
msg251638 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-09-26 07:16
New changeset 005590a4a005 by Raymond Hettinger in branch '3.5':
Issue #25135: Avoid possible reentrancy issues in deque_clear.
https://hg.python.org/cpython/rev/005590a4a005
msg251640 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-09-26 07:53
New changeset fc6d62db8d42 by Raymond Hettinger in branch '2.7':
Issue #25135: Avoid possible reentrancy issues in deque_clear.
https://hg.python.org/cpython/rev/fc6d62db8d42
History
Date User Action Args
2015-09-26 07:54:18rhettingersetstatus: open -> closed
type: behavior
resolution: fixed
versions: + Python 2.7, Python 3.5
2015-09-26 07:53:04python-devsetmessages: + msg251640
2015-09-26 07:16:16python-devsetnosy: + python-dev
messages: + msg251638
2015-09-25 19:30:56rhettingersetmessages: + msg251596
2015-09-25 18:51:34tim.peterssetnosy: + tim.peters
messages: + msg251595
2015-09-25 18:15:10rhettingersetmessages: + msg251592
2015-09-25 09:10:13serhiy.storchakasetfiles: + deque_nonreentrant_clear4.diff

messages: + msg251579
2015-09-25 09:03:25vstinnersetmessages: + msg251578
2015-09-25 08:31:09rhettingersetmessages: + msg251577
2015-09-17 19:51:40serhiy.storchakasetmessages: + msg250915
2015-09-17 19:24:33rhettingersetmessages: + msg250913
2015-09-17 14:09:59serhiy.storchakasetfiles: + deque_nonreentrant_clear3.diff

messages: + msg250890
2015-09-17 12:58:35vstinnersetnosy: + vstinner
messages: + msg250883
2015-09-17 12:48:26rhettingersetmessages: + msg250882
2015-09-17 08:34:07serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg250876
2015-09-17 03:00:10rhettingersetfiles: + deque_nonreentrant_clear2.diff
2015-09-15 23:13:32rhettingersetfiles: + deque_nonreentrant_clear.diff
keywords: + patch
2015-09-15 23:12:56rhettingercreate