Skip to content

test_deep_nesting from test_plistlib triggers an exhausted stack protection in a debug build under WASI #111803

Closed
Closed
test_deep_nesting from test_plistlib triggers an exhausted stack protection in a debug build under WASI#111803
Labels
OS-macOS-wasitestsTests in the Lib/test dir

Activity

  1. brettcannon
    added
    OS-wasi
    on Nov 7, 2023
  2. brettcannon
    added this to WASI to tier 2on Nov 7, 2023
  3. github-project-automation
    moved this to Todo in WASI to tier 2on Nov 7, 2023

  4. brettcannon commented on Nov 8, 2023

    @brettcannon
    brettcannon
    on Nov 8, 2023
    MemberAuthor
             340: 0x25fff3 - <unknown>!_PyEval_EvalFrameDefault
         341: 0xefbc2 - <unknown>!gen_send_ex2
         342: 0xef8f0 - <unknown>!gen_iternext
         343: 0x105594 - <unknown>!list_extend
         344: 0x25fff3 - <unknown>!_PyEval_EvalFrameDefault
         345: 0x26f5dd - <unknown>!_PyEval_Vector
         346: 0xca244 - <unknown>!_PyFunction_Vectorcall
         347: 0xcc3f4 - <unknown>!_PyObject_VectorcallTstate
         348: 0xcc231 - <unknown>!method_vectorcall
         349: 0xc9e3e - <unknown>!_PyVectorcall_Call
         350: 0xc9ff7 - <unknown>!_PyObject_Call
         351: 0xca159 - <unknown>!PyObject_Call
         352: 0x2675a1 - <unknown>!_PyEval_EvalFrameDefault
         353: 0x26f5dd - <unknown>!_PyEval_Vector
         354: 0xca244 - <unknown>!_PyFunction_Vectorcall
         355: 0xc9282 - <unknown>!_PyObject_VectorcallDictTstate
         356: 0xca3fe - <unknown>!_PyObject_Call_Prepend
         357: 0x18c442 - <unknown>!slot_tp_call
         358: 0xc90af - <unknown>!_PyObject_MakeTpCall
         359: 0xc8da3 - <unknown>!_PyObject_VectorcallTstate
         360: 0xc9f44 - <unknown>!PyObject_Vectorcall
         361: 0x2695da - <unknown>!_PyEval_EvalFrameDefault
         362: 0x26f5dd - <unknown>!_PyEval_Vector
         363: 0xca244 - <unknown>!_PyFunction_Vectorcall
         364: 0xcc3f4 - <unknown>!_PyObject_VectorcallTstate
         365: 0xcc231 - <unknown>!method_vectorcall
         366: 0xc9e3e - <unknown>!_PyVectorcall_Call
         367: 0xc9ff7 - <unknown>!_PyObject_Call
         368: 0xca159 - <unknown>!PyObject_Call
         369: 0x2675a1 - <unknown>!_PyEval_EvalFrameDefault
         370: 0x26f5dd - <unknown>!_PyEval_Vector
         371: 0xca244 - <unknown>!_PyFunction_Vectorcall
         372: 0xc9282 - <unknown>!_PyObject_VectorcallDictTstate
         373: 0xca3fe - <unknown>!_PyObject_Call_Prepend
         374: 0x18c442 - <unknown>!slot_tp_call
         375: 0xc90af - <unknown>!_PyObject_MakeTpCall
         376: 0xc8da3 - <unknown>!_PyObject_VectorcallTstate
         377: 0xc9f44 - <unknown>!PyObject_Vectorcall
         378: 0x2695da - <unknown>!_PyEval_EvalFrameDefault
         379: 0x26f5dd - <unknown>!_PyEval_Vector
         380: 0xca244 - <unknown>!_PyFunction_Vectorcall
         381: 0xcc3f4 - <unknown>!_PyObject_VectorcallTstate
         382: 0xcc231 - <unknown>!method_vectorcall
         383: 0xc9e3e - <unknown>!_PyVectorcall_Call
         384: 0xc9ff7 - <unknown>!_PyObject_Call
         385: 0xca159 - <unknown>!PyObject_Call
         386: 0x2675a1 - <unknown>!_PyEval_EvalFrameDefault
         387: 0x26f5dd - <unknown>!_PyEval_Vector
         388: 0xca244 - <unknown>!_PyFunction_Vectorcall
         389: 0xc9282 - <unknown>!_PyObject_VectorcallDictTstate
         390: 0xca3fe - <unknown>!_PyObject_Call_Prepend
         391: 0x18c442 - <unknown>!slot_tp_call
         392: 0xc90af - <unknown>!_PyObject_MakeTpCall
         393: 0xc8da3 - <unknown>!_PyObject_VectorcallTstate
         394: 0xc9f44 - <unknown>!PyObject_Vectorcall
         395: 0x2695da - <unknown>!_PyEval_EvalFrameDefault
         396: 0x26f5dd - <unknown>!_PyEval_Vector
         397: 0xca244 - <unknown>!_PyFunction_Vectorcall
         398: 0xc9282 - <unknown>!_PyObject_VectorcallDictTstate
         399: 0xca3fe - <unknown>!_PyObject_Call_Prepend
         400: 0x18d4e5 - <unknown>!slot_tp_init
         401: 0x18197a - <unknown>!type_call
         402: 0xc90af - <unknown>!_PyObject_MakeTpCall
         403: 0xc8da3 - <unknown>!_PyObject_VectorcallTstate
         404: 0xc9f44 - <unknown>!PyObject_Vectorcall
         405: 0x2695da - <unknown>!_PyEval_EvalFrameDefault
         406: 0x248cc4 - <unknown>!PyEval_EvalCode
         407: 0x243a85 - <unknown>!builtin_exec
         408: 0x13e0bd - <unknown>!cfunction_vectorcall_FASTCALL_KEYWORDS
         409: 0xc8db9 - <unknown>!_PyObject_VectorcallTstate
         410: 0xc9f44 - <unknown>!PyObject_Vectorcall
         411: 0x2695da - <unknown>!_PyEval_EvalFrameDefault
         412: 0x26f5dd - <unknown>!_PyEval_Vector
         413: 0xca244 - <unknown>!_PyFunction_Vectorcall
         414: 0xc9e3e - <unknown>!_PyVectorcall_Call
         415: 0xc9ff7 - <unknown>!_PyObject_Call
         416: 0xca159 - <unknown>!PyObject_Call
         417: 0x343f99 - <unknown>!pymain_run_module
         418: 0x343461 - <unknown>!Py_RunMain
         419: 0x3445e9 - <unknown>!pymain_main
         420: 0x344692 - <unknown>!Py_BytesMain
         421: 0x5987 - <unknown>!main
         422: 0x52c681 - <unknown>!__main_void
         423: 0x5960 - <unknown>!_start
       note: using the `WASMTIME_BACKTRACE_DETAILS=1` environment variable may show more debugging information
    2: wasm trap: call stack exhausted
  5. brettcannon
    changed the title [-]`test_deep_nesting` from `test_plistlib` triggers stack overflow protection in a debug build under WASI[/-] [+]`test_deep_nesting` from `test_plistlib` triggers an exhausted stack protection in a debug build under WASI[/+] on Nov 8, 2023
  6. brettcannon
    added
    testsTests in the Lib/test dir
    on Jan 12, 2024

  7. brettcannon commented on Jan 12, 2024

    @brettcannon
    brettcannon
    on Jan 12, 2024
    MemberAuthor

    @ned-deily @ronaldoussoren what is test_deep_nesting() supposed to measure? A really nested file, or triggering RecursionError?

  8. brettcannon
    added
    OS-mac
    on Jan 12, 2024

  9. ronaldoussoren commented on Jan 13, 2024

    @ronaldoussoren
    ronaldoussoren
    on Jan 13, 2024
    Contributor

    The test was introduced in 34637a0 as part of this issue: https://bugs.python.org/issue42103

    The test appear to test a deeply nested list, but I don't know why the test itself ignores recursion errors. Maybe @serhiy-storchaka recalls why added that part of the test.

    The test is efffectively a no-op in main, both values of N result in a RecusionError on my laptop (--enable-framework --with-pydebug)

    This diff still tests fairly deep nesting without hitting RecursionError:

    diff --git a/Lib/test/test_plistlib.py b/Lib/test/test_plistlib.py
index f47982907d..5650a43d95 100644
--- a/Lib/test/test_plistlib.py
+++ b/Lib/test/test_plistlib.py
@@ -971,18 +971,15 @@ def test_cycles(self):
         self.assertIs(b['x'], b)
 
     def test_deep_nesting(self):
-        for N in [300, 100000]:
+        for N in [50, 100]:
+          with self.subTest(N=N):
             chunks = [b'\xa1' + (i + 1).to_bytes(4, 'big') for i in range(N)]
-            try:
-                result = self.decode(*chunks, b'\x54seed', offset_size=4, ref_size=4)
-            except RecursionError:
-                pass
-            else:
-                for i in range(N):
-                    self.assertIsInstance(result, list)
-                    self.assertEqual(len(result), 1)
-                    result = result[0]
-                self.assertEqual(result, 'seed')
+            result = self.decode(*chunks, b'\x54seed', offset_size=4, ref_size=4)
+            for i in range(N):
+                self.assertIsInstance(result, list)
+                self.assertEqual(len(result), 1)
+                result = result[0]
+            self.assertEqual(result, 'seed')
 
     def test_large_timestamp(self):
         # Issue #26709: 32-bit timestamp out of range

    On my laptop the max recursion that doesn't hit the recursion limit is about 160, keeping the max at 100 in the test keeps us far away from the actual limit. A value of 100 should still be a lot larger than the nesting seen in real plist files, although I don't know if decoding keyed archives (a secondary use case for some users) can run into this.

    I'd be in favour of adjusting the test. If there are users that run into the recursion limit with a real-world use-case we can always try to to improve the algorithm, but let's keep the code as-is for now.

  10. ronaldoussoren commented on Jan 13, 2024

    @ronaldoussoren
    ronaldoussoren
    on Jan 13, 2024
    Contributor

    The linked PR contains the inlined diff from my previous message.

  11. serhiy-storchaka commented on Jan 13, 2024

    @serhiy-storchaka
    serhiy-storchaka
    on Jan 13, 2024
    Member

    It is a regression. It works for N=300 in 3.10-3.12 and only hits the recursion limit in 3.13.

  12. serhiy-storchaka commented on Jan 13, 2024

    @serhiy-storchaka
    serhiy-storchaka
    on Jan 13, 2024
    Member

    The maximum depth was 320 in 3.10, 321 in 3.11, 484 in 3.12, and only 160 in 3.13. Or 1/3 of sys.getrecursionlimit() in 3.10 and 3.11, 1/2 in 3.12 and 1/6 in 3.13. A large regression, especially in comparison with 3.12.

    See also https://discuss.python.org/t/recursion-limits/33869.

  13. serhiy-storchaka
    added a commit that references this issue on Jan 13, 2024

    pythongh-111803: Support loading more deeply nested lists in binary p…

    2dfbdd0

  14. serhiy-storchaka commented on Jan 13, 2024

    @serhiy-storchaka
    serhiy-storchaka
    on Jan 13, 2024
    Member

    RecursionError for the lower limit is a sign of some general Python regression. Something related to generators or generator expressions.

    The stack overflow was because of recursive calls of list.extend() which consume the C stack which is very limited on WASI. #114024 gets rid of list.extend(). All recursion is now in pure Python and no longer depends on the size of the C stack. It is only limited by sys.getrecursionlimit() which can be increased unlimitedly for this task. The test works even for N=968.

    It is possible to implement the binary Plist loader in completely non-recursive way without relying on the fact that the pure Python recursion does not consume the C stack (CPython implementation detail), but it will be more complex and perhaps more slow for common cases.

  15. ronaldoussoren commented on Jan 13, 2024

    @ronaldoussoren
    ronaldoussoren
    on Jan 13, 2024
    Contributor

    @serhiy-storchaka, your fix is much better than just reducing the limit in the test case. Thanks for looking into this.

  16. 8 remaining items

  17. serhiy-storchaka commented on Jan 22, 2024

    @serhiy-storchaka
    serhiy-storchaka
    on Jan 22, 2024
    Member

    I created #114413 about an unexpected recursion limitation.

    But there is still an issue that a debug build under WASI crashes before reaching the recursion limit. Perhaps the sys.getrecursionlimit() value should be significantly reduced on this platform?

    @brettcannon, could you please test examples from #114413 on Python 3.11, 3.12 and main and find the minimal depth of crashing in these versions?

  18. kulikjak
    added 2 commits that reference this issue on Jan 22, 2024

    pythongh-111803: Support loading more deeply nested lists in binary p…

    6b94f88

    pythongh-111803: Make test_deep_nesting from test_plistlib more strict (

    ac79500
  19. serhiy-storchaka
    added 2 commits that reference this issue on Jan 22, 2024

    [3.12] gh-111803: Make test_deep_nesting from test_plistlib more stri…

    d1f731f

    [3.11] gh-111803: Make test_deep_nesting from test_plistlib more stri…

    804037e

  20. brettcannon commented on Jan 22, 2024

    @brettcannon
    brettcannon
    on Jan 22, 2024
    MemberAuthor

    But there is still an issue that a debug build under WASI crashes before reaching the recursion limit. Perhaps the sys.getrecursionlimit() value should be significantly reduced on this platform?

    The problem is if you reduce it to make one test happy, it has a cascading effect where other tests start to fail. I tried that and then suddenly I think test_json began failing.

    @brettcannon, could you please test examples from #114413 on Python 3.11, 3.12 and main and find the minimal depth of crashing in these versions?

    I can at least for main, but I'm not concerned for the other versions since the test suite won't pass anyway since all the fixes so far have been in main.

  21. brettcannon commented on Jan 22, 2024

    @brettcannon
    brettcannon
    on Jan 22, 2024
    MemberAuthor

    But there is still an issue that a debug build under WASI crashes before reaching the recursion limit. Perhaps the sys.getrecursionlimit() value should be significantly reduced on this platform?

    The problem is if you reduce it to make one test happy, it has a cascading effect where other tests start to fail. I tried that and then suddenly I think test_json began failing.

    If I drop it down to 150 then two tests fail.

    test_pickle

    ERROR: test_load_global_specialization_failure_keeps_oparg (__main__.RebindBuiltinsTests.test_load_global_specialization_failure_keeps_oparg)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Lib/test/test_dynamic.py", line 146, in test_load_global_specialization_failure_keeps_oparg
    sum_func = eval(code, MyGlobals())
               ~~~~^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded during compilation

    test_dynamic

    ERROR: test_unpickler (__main__.SizeofTests.test_unpickler)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Lib/test/test_pickle.py", line 405, in test_unpickler
    check_unpickler(recurse(100), 128, 140)
    ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Lib/test/test_pickle.py", line 385, in check_unpickler
    dump = pickle.dumps(data)
           ~~~~~~~~~~~~^^^^^^
RecursionError: maximum recursion depth exceeded while pickling an object

    Setting it to 175 and the stack depth check in #114413 triggers stack depth exhaustion in the WASI host.

  22. brettcannon commented on Jan 23, 2024

    @brettcannon
    brettcannon
    on Jan 23, 2024
    MemberAuthor

    I opened #114456 for changing the recursion limit.

  23. aisk
    added 2 commits that reference this issue on Feb 11, 2024

    pythongh-111803: Support loading more deeply nested lists in binary p…

    c334354

    pythongh-111803: Make test_deep_nesting from test_plistlib more strict (

    491bde6

  24. dawnwages commented on Feb 15, 2024

    @dawnwages
    dawnwages
    on Feb 15, 2024

    What's left to be done on this one?

  25. brettcannon commented on Feb 21, 2024

    @brettcannon
    brettcannon
    on Feb 21, 2024
    MemberAuthor

    What's left to be done on this one?

    I don't think anything, so I'm going to close it. Thanks for the ping!

  26. brettcannon
    closed this as completedon Feb 21, 2024
  27. Glyphack
    added 2 commits that reference this issue on Sep 2, 2024

    pythongh-111803: Support loading more deeply nested lists in binary p…

    d7e1438

    pythongh-111803: Make test_deep_nesting from test_plistlib more strict (

    a442562
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    OS-macOS-wasitestsTests in the Lib/test dir

    Projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions