Abstract

This PR proposes a soft limit of one million (1 000 000), and a larger hard limit for various aspects of Python code and its implementation.

The Python language does not specify limits for many of its features. Not having any limit to these values seems to enhance programmer freedom, at least superficially, but in practice the CPython VM and other Python virtual machines have implicit limits or are forced to assume that the limits are astronomical, which is expensive.

This PR lists a number of features which are to have a limit of one million.

For CPython the hard limit will be eight million (8 000 000).

Motivation

There are many values that need to be represented in a virtual machine. If no limit is specified for these values, then the representation must either be inefficient or vulnerable to overflow. The CPython virtual machine represents values like line numbers, stack offsets and instruction offsets by 32 bit values. This is inefficient, and potentially unsafe.

It is inefficient as actual values rarely need more than a dozen or so bits to represent them.

It is unsafe as malicious or poorly generated code could cause values to exceed 2³².

For example, line numbers are represented by 32 bit values internally. This is inefficient, given that modules almost never exceed a few thousand lines. Despite being inefficient, it is still vulnerable to overflow as it is easy for an attacker to created a module with billions of newline characters.

Memory access is usually a limiting factor in the performance of modern CPUs. Better packing of data structures enhances locality and reduces memory bandwidth, at a modest increase in ALU usage (for shifting and masking). Being able to safely store important values in 20 bits would allow memory savings in several data structures including, but not limited to:

• Frame objects
• Object headers
• Code objects

There is also the potential for a more efficient instruction format, speeding up interpreter dispatch.

Rationale

Imposing a limit on values such as lines of code in a module, and the number of local variables, has significant advantages for ease of implementation and efficiency of virtual machines. If the limit is sufficiently large, there is no adverse effect on users of the language.

By selecting a fixed but large limit for these values, it is possible to have both safety and efficiency whilst causing no inconvenience to human programmers and only very rare problems for code generators.

Specification

This PR proposes that the following language features and runtime values have a soft limit of one million.

• The number of source code lines in a module
• The number of bytecode instructions in a code object.
• The sum of local variables and stack usage for a code object.
• The number of classes in a running interpreter.
• The recursion depth of Python code.

It is likely that memory constraints would be a limiting factor before the number of classes reaches one million.

Soft and hard limits

Implementations should emit a warning whenever a soft limit is exceeded, unless the hard limit has the same value as the soft limit. When a hard limit is exceeded, then an exception should be raised.

Depending on the implementation, different hard limits might apply. In some cases the hard limit might be below the soft limit. For example, many micropython ports are unlikely to be able to support such large limits.

struct header {
    uint32_t gc_flags:6; /* Needs finalisation, might be part of a cycle, etc. */
    uint32_t class_id:26; /* Can be efficiently mapped to address by ensuring suitable alignment of classes */
    uint32_t refcount; /* Limited memory or saturating */
}

Hard limits in CPython

CPython will enforce a hard limit on all the above values. The value of the hard limit will be 8 million.

It is hypothetically possible that some machine generated code exceeds one or more of the above limits. The author believes that to be incredibly unlikely and easily fixed by modifying the output stage of the code generator.

We would like to gain the benefit from the above limits for performance as soon as possible. To that end, CPython will start applying limits from version 3.9 onward. To ease the transition and minimize breakage, the initial limits will be 16 million, reducing to 8 million in a later version.

Backwards Compatibility

The actual hard limits enforced by CPython will be:

Given the rarity of code generators that would exceed the one million limits, and the environments in which they are typically used, it seems reasonable to start issuing warnings in 3.9 if any limited quantity exceeds one million.

Historically the recursion limit has been set at 1000. To avoid breaking code that implicitly relies on the value being small, the soft recursion limit will be increased gradually, as follows:

The hard limit will be set to 8 million immediately.

Other implementations

Implementations of Python other than CPython have different purposes, so different limits might be appropriate. This is acceptable, provided the limits are clearly documented.

Security Implications

Minimal. This reduces the attack surface of any Python virtual machine by a small amount.

Reference Implementation

None, as yet. This will be implemented in CPython, once the PEP has been accepted.

Rejected Ideas

Being able to modify the hard limits upwards at compile time was suggested by Tal Einat. This is rejected as the current limits of 2³² have not been an issue, and the practical advantages of allowing limits between 2²⁰ and 2³² seem slight compared to the additional code complexity of supporting such a feature.

Open Issues

None, as yet.

References

https://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf

Copyright

This document is placed in the public domain or under the CC0-1.0-Universal license, whichever is more permissive.