Segfault compiling a very large source file

Bug report

A friend trying to package the Python library samson for the Arch User Repository encountered crashes while bytecode compiling. This was narrowed down to this file within that package (a copy, renamed with a .txt instead of .py suffix to bypass GitHub restrictions, is attached; it imports other modules from the original library, but still appears to trigger the bug when compiled on its own, probably because the bug occurs before the imports are reached).

The file consists mostly of several very, very large dict and list literals.

The crash is a memory access violation, apparently an out-of-bounds write (I suspect into the output buffer), possibly the result of an off-by-one error. It is preceded by allocation of several Gbytes of memory, and occurs whether -O or -OO is used, or if the module is imported from a REPL. A valgrind trace from a run on my machine is included below:

$ valgrind python3 -OO english_data.py
==10383== Memcheck, a memory error detector
==10383== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10383== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==10383== Command: python3 -OO english_data.py
==10383== 
==10383== Warning: set address range perms: large range [0x61c0e028, 0x71c0e079) (noaccess)
==10383== Warning: set address range perms: large range [0xb1c10061, 0xd1c10061) (undefined)
==10383== Warning: set address range perms: large range [0x71c0f028, 0x91c0f079) (noaccess)
==10383== Warning: set address range perms: large range [0x111c11061, 0x151c11061) (undefined)
==10383== Warning: set address range perms: large range [0x91c10028, 0xd1c10079) (noaccess)
==10383== Invalid write of size 1
==10383==    at 0x4981293: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49811DD: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x52506060 is 0 bytes after a block of size 41,943,072 alloc'd
==10383==    at 0x48A26D5: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10383==    by 0x494537B: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x494758E: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x4947AB7: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x494A3A1: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497F361: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497EDC2: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497ED76: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x498025E: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49F1333: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497FC72: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497D48C: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383== 
==10383== Invalid write of size 1
==10383==    at 0x4981296: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49811DD: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x52506061 is 1 bytes after a block of size 41,943,072 alloc'd
==10383==    at 0x48A26D5: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==10383==    by 0x494537B: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x494758E: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x4947AB7: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x494A3A1: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497F361: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497EDC2: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497ED76: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x498025E: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49F1333: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497FC72: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x497D48C: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383== 
==10383== Invalid write of size 1
==10383==    at 0x4981293: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x4981242: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x525064fc is 41,944,252 bytes inside a block of size 41,947,040 in arena "client"
==10383== 
==10383== Invalid write of size 1
==10383==    at 0x4981296: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x4981242: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x525064fd is 41,944,253 bytes inside a block of size 41,947,040 in arena "client"
==10383== 
==10383== Invalid write of size 1
==10383==    at 0x4981293: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49811FA: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x525064fe is 41,944,254 bytes inside a block of size 41,947,040 in arena "client"
==10383== 
==10383== Invalid write of size 1
==10383==    at 0x4981296: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49811FA: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  Address 0x525064ff is 41,944,255 bytes inside a block of size 41,947,040 in arena "client"
==10383== 
==10383== 
==10383== Process terminating with default action of signal 11 (SIGSEGV)
==10383==  Access not within mapped region at address 0x52507000
==10383==    at 0x4981293: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49811DD: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C7EE3: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C32A1: _PyAST_Compile (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49C2E94: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B483: ??? (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B26F: _PyRun_SimpleFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x490B876: _PyRun_AnyFileObject (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49D9581: Py_RunMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x49A22D6: Py_BytesMain (in /usr/lib/libpython3.10.so.1.0)
==10383==    by 0x401CA21: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==    by 0x401C9FA: ??? (in /lib/ld-musl-x86_64.so.1)
==10383==  If you believe this happened as a result of a stack
==10383==  overflow in your program's main thread (unlikely but
==10383==  possible), you can try to increase the size of the
==10383==  main thread stack using the --main-stacksize= flag.
==10383==  The main thread stack size used in this run was 8388608.
==10383== 
==10383== HEAP SUMMARY:
==10383==     in use at exit: 3,123,221,892 bytes in 88,369 blocks
==10383==   total heap usage: 90,302 allocs, 1,933 frees, 5,849,230,023 bytes allocated
==10383== 
==10383== LEAK SUMMARY:
==10383==    definitely lost: 0 bytes in 0 blocks
==10383==    indirectly lost: 0 bytes in 0 blocks
==10383==      possibly lost: 851,816 bytes in 12 blocks
==10383==    still reachable: 3,122,370,076 bytes in 88,357 blocks
==10383==         suppressed: 0 bytes in 0 blocks
==10383== Rerun with --leak-check=full to see details of leaked memory
==10383== 
==10383== For lists of detected and suppressed errors, rerun with: -s
==10383== ERROR SUMMARY: 4001 errors from 6 contexts (suppressed: 0 from 0)

Your environment

• CPython versions tested on: 3.10.3 and 3.10.5
• Operating system and architecture: Alpine Linux Edge x86-64 (with musl libc 1.2.3) and Arch Linux x86-64 (with glibc 2.35), respectively

[sweeneyde]

I replicated on 3.10, but not any of 3.8, 3.9, 3.11, 3.12

[sweeneyde]

I got a segfault on this line in assemble_emit_linetable_pair:

cpython/Python/compile.c

Line 6615 in 5e30ba1

*lnotab++ = bdelta;

Here, bdelta=0, ldelta=-127, and len=2147483648=0x80000000

With this traceback (in 3.10):

• assemble_emit_linetable_pair(assembler * a, int bdelta, int ldelta), Line 6615
• assemble_line_range(assembler * a), Line 6644
• assemble_lnotab(assembler * a, instr * i), Line 6671
• assemble_emit(assembler * a, instr * i), Line 6693
• assemble(compiler * c, int addNone), Line 7178

[sweeneyde]

I'm not 100% sure, but this might be enough to fix it:

-    if (a->a_lnotab_off + 2 >= len) {
+    if (a->a_lnotab_off >= len - 2) {

[sweeneyde]

Actually, it seems there are several issues here:

• Adding instead of subtracting
• multiplying by 2 without checking for overflow
• Using int instead of Py_ssize_t for a_lnotab_off.

It's the third one that I believe is actually causing the issue in this case.

[sweeneyde]

On a pragmatic level, it may be more appropriate and performant to use JSON and load it with the json module rather than using python literals. But thanks for the report -- we should try not to segfault in these overflow cases.

[markshannon]

This points to a problem with the line number table.

The code example is "only" a million lines or so, yet the line number table is exceeding 2 billion bytes in size.
There is something decidedly non-linear in there.

What I suspect is happening is that line numbers are alternating from ~0 to ~1million and back.
In 3.10 (and prior) large deltas are encoding a sequence of small deltas, so a delta of 1 million will take several thousand bytes.
The 3.11 table format should be fine, as it uses variable length integer encodings; a million line delta takes 4 bytes.

@pablogsal This might be a useful test case for location table encodings.

[pablogsal]

Can someone confirm that this doesn't reproduce on 3.11?

[markshannon]

I can confirm:
3.10: Seg fault (eventually, it takes a while)
3.11: Good
3.12: Good