Issue 28040: compact dict : SystemError: returned NULL without setting an error. (original) (raw)
Created on 2016-09-09 07:57 by mbussonn, last changed 2022-04-11 14:58 by admin. This issue is now closed.
Messages (33)
Author: Matthias Bussonnier (mbussonn) *
Date: 2016-09-09 07:57
I've been able to reliably trigger dict.pop to raise a system error:
See https://github.com/pytest-dev/pytest/issues/1925
I have issues getting a small test-case that triggers it, though by changing the pop method of dict to print the returned value:
PyObject * _PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt){ ... printf("\nreturn End value %x\n", old_value ); return old_value;
}
I've been able to see that the last return sometime return Null:
[snip]
return End value 0 Fatal Python error: a function returned NULL without setting an error SystemError: <built-in method pop of dict object at 0x10473f238> returned NULL without setting an error
Current thread 0x00007fff77139300 (most recent call first): File "/usr/local/lib/python3.6/site-packages/_pytest/capture.py", line 83 in reset_capturings File "/usr/local/lib/python3.6/site-packages/_pytest/config.py", line 869 in _ensure_unconfigure File "/usr/local/lib/python3.6/site-packages/_pytest/main.py", line 121 in wrap_session File "/usr/local/lib/python3.6/site-packages/_pytest/main.py", line 125 in pytest_cmdline_main File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 596 in execute File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 333 in File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 338 in _hookexec File "/usr/local/lib/python3.6/site-packages/_pytest/vendored_packages/pluggy.py", line 724 in call File "/usr/local/lib/python3.6/site-packages/_pytest/config.py", line 57 in main File "/usr/local/lib/python3.6/site-packages/pytest.py", line 17 in File "/Users/bussonniermatthias/dev/git-cpython/Lib/runpy.py", line 85 in _run_code File "/Users/bussonniermatthias/dev/git-cpython/Lib/runpy.py", line 193 in _run_module_as_main
Aborted
Which I suppose is not desirable.
I'm quite uncomfortable with C so I'm far from being able to propose a patch or describe why this would happen...
Victor Stinner seem to have made the last changes to these methods in http://bugs.python.org/issue27350 . Not sure if the etiquette is to add them to the nosy list in this case.
Discovered because of nightly continuous integration with travis on github.com/xonsh/xonsh
Author: Matthias Bussonnier (mbussonn) *
Date: 2016-09-09 08:12
Oh, also I've bisect it to the compact-dict commit, and the exact instance of dict.pop that fails depends on the machine.
Reliable same location on travis-ci and locally, but travis-ci location and local differ on where it triggers this.
Author: Inada Naoki (methane) * 
Date: 2016-09-09 11:05
I've forgot to convert split table into combined table when del and .pop(). I'm sorry, and thanks to finding it.
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-09 11:23
Are you sure INADA? The previous dict implementation has the same constraint but does merge in dict_pop.
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-09 11:24
does should be does not. Sorry.
Author: Inada Naoki (methane) *
Date: 2016-09-09 14:06
Xiang Zhang added the comment:
Are you sure INADA? The previous dict implementation has the same constraint but does merge in dict_pop.
Yes. New dict implementation preserves insertion order.
class A: ...
a, b = A(), A() a.a, a.b, a.c = 1, 2, 3 b.a, b.b, b.c = 4, 5, 6 del a.b # or a.pop('b') a.b = 7
assert list(a.dict) == ["a", "c", "b"] assert list(b.dict) == ["a", "b", "c"]
This is difficult for key-sharing dict (aka. split table).
We may be able to allow some simple del and pop operation for split table. But we should keep best balance between simplicity and efficiency. And we don't have enough time before 3.6b1.
Author: Matthias Bussonnier (mbussonn) *
Date: 2016-09-09 14:57
I'm sorry, and thanks to finding it.
No worries, that's what nightly are for right ? And I only dug up a failing tests :-) Thanks to you for writing this !
[snip] This is difficult for key-sharing dict (aka. split table).
I'm not going to pretend I understand the details, though I applied the latest patch: fix-compact-dict-deletion.patch methane, 2016-09-09 04:11
And it does fix this issue for me (at least on my local machine)
Looking at the code the only thing I see is that you seem to return NULL in Pop and -1 in Clear. Not sure if this what you meant, I'm un familar with all this; but thanks a lot again for the your work and the quick response.
Author: STINNER Victor (vstinner) *
Date: 2016-09-09 15:54
I would really appreciate if someone can write an unit test.
I'm not confident to fix a bug without unit test, on such tricky part of Python internals (splitted/combined dict).
Author: Inada Naoki (methane) *
Date: 2016-09-10 01:42
Added test which reproduce the issue on current master.
Author: Roundup Robot (python-dev) 
Date: 2016-09-10 03:22
New changeset 4a5b61b0d090 by Victor Stinner in branch 'default': Fix SystemError in compact dict https://hg.python.org/cpython/rev/4a5b61b0d090
Author: STINNER Victor (vstinner) *
Date: 2016-09-10 03:36
Added test which reproduce the issue on current master.
Oh, great :-) Thanks for the quick fix AND test.
I pushed your latest change.
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-12 17:42
I'd like to reopen this one since I still don't think this change is needed and suggest to revert since this change make split table combined on deletion.
Deletion will not alter split dict's order. Only insertion after deletion will. But this case is already handled in insertdict[0]. So I think we don't have to combine once an item is deleted from split dict.
The example INADA gives works well with the previous implementation(before this change). The problem there is a SystemError I think is dict.pop() doesn't handle pending state (del dict does, so you can produce the same failure when try del dict[]). We only add || *value_addr == NULL as delitem does.
poc.patch reverts the change (preserve the tests, eliminating the size compare part) and add pending state handling in dict.pop(). It passes. And if you remove the pending state handling, you can product the SystemError.
I'd like to know if my idea is totally wrong. :)
[0] https://hg.python.org/cpython/file/tip/Objects/dictobject.c#l1057
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-12 17:47
Ohh, mistakes.
so you can produce can should be can not
We only add We only need to add
you can product the product should be produce
Author: Inada Naoki (methane) *
Date: 2016-09-12 18:03
Xiang: Preserving insertion order in shared-key dict is possible, but it's hard. If we allow it, we should add tons of test for shared-key dict.
I'll describe why it's harder than you think.
Current implementation allow insertion to split table only when:
/* When insertion order is different from shared key, we can't share
* the key anymore. Convert this instance to combine table.
*/
if (_PyDict_HasSplitTable(mp) &&
((ix >= 0 && *value_addr == NULL && mp->ma_used != ix) ||
(ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
if (insertion_resize(mp) < 0) {ix >= 0 && *value_addr == NULL means it's pending slot.
mp->ma_used == ix ensure insertion order. And if we allow deletion, this check will be broken.
For example:
a, b = C() a.a, a.b, a.c = 1, 2, 3 # shared-key order b.a, b.b, b.c = 1, 2, 3 # same order, no problem
del b.a # mp->ma_used = 2 del b.b # mp->ma_used = 1
b.b = 42 # It's OK because mp->ma_used == ix == 1. Keep sharing.
assert(list(b.dict.keys()) == ["c", "b"]) # AssertionError! Actual order is [(PENDING "a",) "b", "c"]
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-12 18:17
add tons of test for shared-key dict
So what if we delete mp->ma_used == ix or use mp->ma_keys->dk_nentries == ix? Do we still have any case breaking the order?
Author: STINNER Victor (vstinner) *
Date: 2016-09-12 19:02
Xiang: I will remove the now useless check, but after beta 1.
This issue is about SystemError and you now want to reuse the issue to implement an optimization. Please open a new issue for supporting deletion on split table if you consider that it's possible and that it would be a good idea.
Author: Stefan Krah (skrah) *
Date: 2016-09-12 19:51
The Blaze test suite segfaults with 4a5b61b0d090.
Author: STINNER Victor (vstinner) *
Date: 2016-09-12 19:57
The Blaze test suite segfaults with 4a5b61b0d090.
What is the Blaze test suite?
Are you sure that you really recompiled Python from scratch? Try:
make distclean && ./configure --with-pydebug && make
Author: Stefan Krah (skrah) *
Date: 2016-09-12 20:03
Yes, I'm sure. I even cloned a fresh repo. Also, I tested in release mode (not --with-pydebug).
https://github.com/blaze/blaze
Author: Ned Deily (ned.deily) *
Date: 2016-09-12 20:05
The immediate question is: is this serious enough to block 3.6.0b1 or can it wait for b2? The b1 bits are just about ready to be published.
Author: Stefan Krah (skrah) *
Date: 2016-09-12 20:12
I'm not sure. In the Blaze test suite, 1e7b636b6009 has the SystemError. 4a5b61b0d090 segfaults.
Blaze is pushing Python's dynamic capabilities to absolute limits, so perhaps this is specific to a few applications only.
For Blaze itself there is no difference whether this is fixed now or in the next beta. So releasing 3.6.0b1 now and setting this back to blocker afterwards sounds good to me.
Author: Ned Deily (ned.deily) *
Date: 2016-09-12 20:14
OK, thanks, Stefan! OK with you, Victor?
Author: Stefan Krah (skrah) *
Date: 2016-09-12 20:50
If Victor can't reply now (it's getting late in Europe), I'd just release. Pretend that I set it to deferred blocker. :)
Author: Ned Deily (ned.deily) *
Date: 2016-09-12 20:52
Yes, he's had a long day. I'll take your advice, Stefan. Thanks.
Author: STINNER Victor (vstinner) *
Date: 2016-09-12 21:03
I didn't see any segfault on the Python test suite on buildbots. It's either a bug in Blaze (Python C API change like METH_CALL) or a real bug in CPython. It's a beta, we can fix bugs later :-)
Author: Stefan Krah (skrah) *
Date: 2016-09-12 21:40
It could still be a stack overflow, but on the surface it does not look like one. It's definitely related to the aforementioned revision:
==3442== Invalid read of size 8 ==3442== at 0x49DBD8: _PyDict_Pop (dictobject.c:1743) ==3442== by 0x4A0BE2: dict_pop (dictobject.c:2732) ==3442== by 0x4AA5F8: _PyCFunction_FastCallDict (methodobject.c:229) ==3442== by 0x4AA70B: _PyCFunction_FastCallKeywords (methodobject.c:267) ==3442== by 0x55FE63: call_function (ceval.c:4794) ==3442== by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267) ==3442== by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718) ==3442== by 0x560123: _PyFunction_FastCall (ceval.c:4876) ==3442== by 0x56023B: fast_function (ceval.c:4906) ==3442== by 0x55FF91: call_function (ceval.c:4815) ==3442== by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267) ==3442== by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718) ==3442== Address 0x0 is not stack'd, malloc'd or (recently) free'd ==3442== ==3442== ==3442== Process terminating with default action of signal 11 (SIGSEGV) ==3442== Access not within mapped region at address 0x0 ==3442== at 0x49DBD8: _PyDict_Pop (dictobject.c:1743) ==3442== by 0x4A0BE2: dict_pop (dictobject.c:2732) ==3442== by 0x4AA5F8: _PyCFunction_FastCallDict (methodobject.c:229) ==3442== by 0x4AA70B: _PyCFunction_FastCallKeywords (methodobject.c:267) ==3442== by 0x55FE63: call_function (ceval.c:4794) ==3442== by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267) ==3442== by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718) ==3442== by 0x560123: _PyFunction_FastCall (ceval.c:4876) ==3442== by 0x56023B: fast_function (ceval.c:4906) ==3442== by 0x55FF91: call_function (ceval.c:4815) ==3442== by 0x55AA82: _PyEval_EvalFrameDefault (ceval.c:3267) ==3442== by 0x54D9CC: PyEval_EvalFrameEx (ceval.c:718)
Author: Inada Naoki (methane) *
Date: 2016-09-13 00:20
So what if we delete mp->ma_used == ix or use mp->ma_keys->dk_nentries == ix? Do we still have any case breaking the order?
Yes. mp->ma_used == ix means no more guard about key ordering.
class C: ...
a, b = C() a.a, a.b = 1, 2 # shared key order is [a, b]
b has [a, b] pending slot too, and no guard when inserting pending slot.
b.b, b.a = 3, 4 # continue to using sharing key
assert list(b.dict.keys()) == ['b', 'a']) # AssertionError!
mp->ma_keys->dk_nentries == ix is nonsense. It prohibits to inserting pending slot:
a, b = C() a.a, a.b = 1, 2 # shared key order is [a, b]
Since ma_keys is shared, b's dk_nentries == 2
b.a = 3 # ix = 0, dk_nentries = 2; stop using sharing keys.
To keep using sharing key, my idea is adding one more member to dict: mp->ma_values_end.
When inserting to pending or empty slot, check that ix >= mp_ma_values_end to ensure ordering
and set mp->ma_values_end = ix+1 if it's OK.
a, b = C() # Both of ma_values_end = 0 a.a, a.b = 1, 2 # shared key order is [a, b], a's ma_values_end = 2 b.b = 3 # ma_values_end (=0) <= ix (=1); OK; set ma_values_end = 2 b.a = 4 # ma_values_end (=2) > ix (=0); NG; convert to combined table
But testing such an implementation detail is hard from pure Python. (No API for checking ma_values_end, the dict is split or combined, and two dict share keys).
I don't know adding such hack is worth enough. Dict is made by tons of hacks, you know.
I think new OrderedDict implementation based on new dict implementation is more worth. If dict is far more efficient than OrderedDict, people may use dict even when OrderedDict should be used. But I don't know it can be done after beta1.
Author: Xiang Zhang (xiang.zhang) *
Date: 2016-09-13 07:39
assert list(b.dict.keys()) == ['b', 'a']) # AssertionError!
No, there is no error. Once an pending slot is encountered it is combined. But inserting pending slots is prohibited and it's far from ideal.
We need to know if the pending slot is the last entry or not. But it seems we can't achieve it using the current implementation. Sad. :(
In short, I give up. Sorry for the noise.
Author: Roundup Robot (python-dev)
Date: 2016-09-13 07:42
New changeset 579141d6e353 by Victor Stinner in branch 'default': Issue #28040: Cleanup find_empty_slot() https://hg.python.org/cpython/rev/579141d6e353
Author: STINNER Victor (vstinner) *
Date: 2016-09-13 07:48
Stefan Krah: "It could still be a stack overflow, but on the surface it does not look like one. It's definitely related to the aforementioned revision: (...)"
The initial bug reported in this issue is now fixed. Even if the Blaze issue is related, I would really prefer to discuss it in a different issue, so I created #28120: "The Blaze test suite segfaults with 4a5b61b0d090".
@Xiang: I simplified find_empty_slot() to remove code to support split table. Again, if you want to support deletion in split table, please open a new issue.
I now close this issue. Thanks for the report Matthias! Thanks for the quick fix and the unit test Naoki!
Author: Stefan Krah (skrah) *
Date: 2016-09-13 09:12
I don't understand how the original issue is fixed if 1e7b636b6009 exhibits the SystemError and the very next revision 4a5b61b0d090 (the fix) segfaults. And the test suite works with the previous dict.
Sure, it can be a third party issue, but this constellation does seem pretty strange.
Happy to discuss it in another issue though.
Author: STINNER Victor (vstinner) *
Date: 2016-09-13 09:18
Stefan Krah: "I don't understand how the original issue is fixed if 1e7b636b6009 exhibits the SystemError"
"SystemError: returned NULL without setting an error" is a generic error, basically it says that a C function has bug :-) It's hard to know exactly which C function has the issue.
"and the very next revision 4a5b61b0d090 (the fix) segfaults"
A segfault is not a SystemError: it's a new bug.
"Sure, it can be a third party issue, but this constellation does seem pretty strange."
In case of doubt, I prefer to open a new issue. Please let's continue in the issue #28120 (see my questions there!).
Author: Roundup Robot (python-dev)
Date: 2016-09-13 14:00
New changeset 3c7456e28777 by Victor Stinner in branch '3.6': Issue #28040: Cleanup find_empty_slot() https://hg.python.org/cpython/rev/3c7456e28777
History
Date
User
Action
Args
2022-04-11 14:58:36
admin
set
github: 72227
2016-09-13 14:00:18
python-dev
set
messages: +
2016-09-13 09🔞05
vstinner
set
messages: +
2016-09-13 09:12:45
skrah
set
messages: +
2016-09-13 07:48:31
vstinner
set
status: open -> closed
2016-09-13 07:48:24
vstinner
set
messages: +
2016-09-13 07:42:29
python-dev
set
messages: +
2016-09-13 07:39:38
xiang.zhang
set
messages: +
2016-09-13 00:20:38
methane
set
messages: +
2016-09-12 21:40:30
skrah
set
messages: +
2016-09-12 21:03:59
vstinner
set
messages: +
2016-09-12 20:52:25
ned.deily
set
messages: +
2016-09-12 20:50:26
skrah
set
priority: release blocker -> deferred blocker
messages: +
2016-09-12 20:14:10
ned.deily
set
messages: +
2016-09-12 20:12:58
skrah
set
messages: +
2016-09-12 20:05:48
ned.deily
set
messages: +
2016-09-12 20:03:48
skrah
set
messages: +
2016-09-12 19:57:32
vstinner
set
messages: +
2016-09-12 19:54:01
skrah
set
priority: normal -> release blocker
nosy: + ned.deily
2016-09-12 19:51:10
skrah
set
nosy: + skrah
messages: +
2016-09-12 19:02:59
vstinner
set
messages: +
2016-09-12 18:17:26
xiang.zhang
set
messages: +
2016-09-12 18:03:18
methane
set
messages: +
2016-09-12 17:47:59
xiang.zhang
set
messages: +
2016-09-12 17:42:21
xiang.zhang
set
status: closed -> open
files: + poc.patch
messages: +
2016-09-10 03:36:04
vstinner
set
status: open -> closed
resolution: fixed
messages: +
2016-09-10 03:22:42
python-dev
set
nosy: + python-dev
messages: +
2016-09-10 01:42:47
methane
set
messages: +
2016-09-10 01:41:39
methane
set
files: + fix-splittable-pop.patch
2016-09-09 15:54:58
vstinner
set
messages: +
2016-09-09 15:21:48
xiang.zhang
set
messages: -
2016-09-09 15:21:18
xiang.zhang
set
files: - issue28040.patch
2016-09-09 14:57:13
mbussonn
set
messages: +
2016-09-09 14:06:53
methane
set
messages: +
2016-09-09 11:24:49
xiang.zhang
set
messages: +
2016-09-09 11:23:48
xiang.zhang
set
messages: +
2016-09-09 11:11:20
methane
set
files: + fix-compact-dict-deletion.patch
2016-09-09 11:05:15
methane
set
files: + fix-compact-dict-deletion.patch
messages: +
2016-09-09 09:13:24
xiang.zhang
set
files: + issue28040.patch
keywords: + patch
2016-09-09 09:13:10
xiang.zhang
set
nosy: + xiang.zhang
messages: +
2016-09-09 09:10:03
berker.peksag
set
2016-09-09 08:12:40
mbussonn
set
messages: +
2016-09-09 07:57:28
mbussonn
create