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

[brettcannon]

Detected using WASI-SDK 20 and wasmtime 14.

Linked PRs

• gh-111803: Use more reasonable nesting in test_plistlib's test_deep_nesting #114020
• gh-111803: Support loading more deeply nested lists in binary plist format #114024
• gh-111803: Make test_deep_nesting from test_plistlib more strict #114026
• [3.12] gh-111803: Make test_deep_nesting from test_plistlib more strict (GH-114026) #114406
• [3.11] gh-111803: Make test_deep_nesting from test_plistlib more strict (GH-114026) #114407

[brettcannon]

         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

[brettcannon]

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

[ronaldoussoren]

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.

[ronaldoussoren]

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

[serhiy-storchaka]

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

[serhiy-storchaka]

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.

[serhiy-storchaka]

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.

[ronaldoussoren]

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