classification
Title: compact dict : SystemError: returned NULL without setting an error.
Type: Stage:
Components: Interpreter Core Versions: Python 3.7, Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: inada.naoki, mbussonn, ned.deily, python-dev, skrah, vstinner, xiang.zhang
Priority: deferred blocker Keywords: patch

Created on 2016-09-09 07:57 by mbussonn, last changed 2016-09-13 14:00 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
fix-compact-dict-deletion.patch inada.naoki, 2016-09-09 11:05 review
fix-compact-dict-deletion.patch inada.naoki, 2016-09-09 11:11 remove unused code review
fix-splittable-pop.patch inada.naoki, 2016-09-10 01:41 Add test review
poc.patch xiang.zhang, 2016-09-12 17:42 review
Messages (33)
msg275283 - (view) 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 <lambda>
  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 <module>
  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
msg275286 - (view) 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.
msg275304 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) 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.
msg275311 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-09-09 11:23
Are you sure INADA? The previous dict implementation has the same constraint but does merge in dict_pop.
msg275312 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-09-09 11:24
does should be does not. Sorry.
msg275317 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) 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.
msg275320 - (view) 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.
msg275322 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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).
msg275535 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2016-09-10 01:42
Added test which reproduce the issue on current master.
msg275554 - (view) Author: Roundup Robot (python-dev) (Python triager) 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
msg275558 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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.
msg276080 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) 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
msg276081 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) 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
msg276083 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) 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"]
msg276085 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) 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?
msg276090 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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.
msg276101 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2016-09-12 19:51
The Blaze test suite segfaults with 4a5b61b0d090.
msg276104 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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
msg276106 - (view) Author: Stefan Krah (skrah) * (Python committer) 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
msg276107 - (view) Author: Ned Deily (ned.deily) * (Python committer) 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.
msg276108 - (view) Author: Stefan Krah (skrah) * (Python committer) 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.
msg276110 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2016-09-12 20:14
OK, thanks, Stefan!  OK with you, Victor?
msg276115 - (view) Author: Stefan Krah (skrah) * (Python committer) 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. :)
msg276116 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2016-09-12 20:52
Yes, he's had a *long* day.  I'll take your advice, Stefan.  Thanks.
msg276120 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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 :-)
msg276125 - (view) Author: Stefan Krah (skrah) * (Python committer) 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)
msg276141 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) 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.
msg276200 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) 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.
msg276202 - (view) Author: Roundup Robot (python-dev) (Python triager) 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
msg276206 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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!
msg276222 - (view) Author: Stefan Krah (skrah) * (Python committer) 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.
msg276223 - (view) Author: STINNER Victor (vstinner) * (Python committer) 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!).
msg276274 - (view) Author: Roundup Robot (python-dev) (Python triager) 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
2016-09-13 14:00:18python-devsetmessages: + msg276274
2016-09-13 09:18:05vstinnersetmessages: + msg276223
2016-09-13 09:12:45skrahsetmessages: + msg276222
2016-09-13 07:48:31vstinnersetstatus: open -> closed
2016-09-13 07:48:24vstinnersetmessages: + msg276206
2016-09-13 07:42:29python-devsetmessages: + msg276202
2016-09-13 07:39:38xiang.zhangsetmessages: + msg276200
2016-09-13 00:20:38inada.naokisetmessages: + msg276141
2016-09-12 21:40:30skrahsetmessages: + msg276125
2016-09-12 21:03:59vstinnersetmessages: + msg276120
2016-09-12 20:52:25ned.deilysetmessages: + msg276116
2016-09-12 20:50:26skrahsetpriority: release blocker -> deferred blocker

messages: + msg276115
2016-09-12 20:14:10ned.deilysetmessages: + msg276110
2016-09-12 20:12:58skrahsetmessages: + msg276108
2016-09-12 20:05:48ned.deilysetmessages: + msg276107
2016-09-12 20:03:48skrahsetmessages: + msg276106
2016-09-12 19:57:32vstinnersetmessages: + msg276104
2016-09-12 19:54:01skrahsetpriority: normal -> release blocker
nosy: + ned.deily
2016-09-12 19:51:10skrahsetnosy: + skrah
messages: + msg276101
2016-09-12 19:02:59vstinnersetmessages: + msg276090
2016-09-12 18:17:26xiang.zhangsetmessages: + msg276085
2016-09-12 18:03:18inada.naokisetmessages: + msg276083
2016-09-12 17:47:59xiang.zhangsetmessages: + msg276081
2016-09-12 17:42:21xiang.zhangsetstatus: closed -> open
files: + poc.patch
messages: + msg276080
2016-09-10 03:36:04vstinnersetstatus: open -> closed
resolution: fixed
messages: + msg275558
2016-09-10 03:22:42python-devsetnosy: + python-dev
messages: + msg275554
2016-09-10 01:42:47inada.naokisetmessages: + msg275535
2016-09-10 01:41:39inada.naokisetfiles: + fix-splittable-pop.patch
2016-09-09 15:54:58vstinnersetmessages: + msg275322
2016-09-09 15:21:48xiang.zhangsetmessages: - msg275292
2016-09-09 15:21:18xiang.zhangsetfiles: - issue28040.patch
2016-09-09 14:57:13mbussonnsetmessages: + msg275320
2016-09-09 14:06:53inada.naokisetmessages: + msg275317
2016-09-09 11:24:49xiang.zhangsetmessages: + msg275312
2016-09-09 11:23:48xiang.zhangsetmessages: + msg275311
2016-09-09 11:11:20inada.naokisetfiles: + fix-compact-dict-deletion.patch
2016-09-09 11:05:15inada.naokisetfiles: + fix-compact-dict-deletion.patch

messages: + msg275304
2016-09-09 09:13:24xiang.zhangsetfiles: + issue28040.patch
keywords: + patch
2016-09-09 09:13:10xiang.zhangsetnosy: + xiang.zhang
messages: + msg275292
2016-09-09 09:10:03berker.peksagsetnosy: + vstinner, inada.naoki
2016-09-09 08:12:40mbussonnsetmessages: + msg275286
2016-09-09 07:57:28mbussonncreate