[Python-checkins] bpo-45753: Make recursion checks more efficient. (GH-29524)
markshannon
webhook-mailer at python.org
Tue Nov 16 06:02:06 EST 2021
https://github.com/python/cpython/commit/b9310773756f40f77e075f221a90dd41e6964efc
commit: b9310773756f40f77e075f221a90dd41e6964efc
branch: main
author: Mark Shannon <mark at hotpy.org>
committer: markshannon <mark at hotpy.org>
date: 2021-11-16T11:01:57Z
summary:
bpo-45753: Make recursion checks more efficient. (GH-29524)
* Uses recursion remaining, instead of recursion depth to speed up check against recursion limit.
files:
A Misc/NEWS.d/next/Core and Builtins/2021-11-11-17-14-21.bpo-45753.nEBFcC.rst
M Include/cpython/pystate.h
M Include/internal/pycore_ceval.h
M Modules/_testinternalcapi.c
M Python/ast.c
M Python/ast_opt.c
M Python/ceval.c
M Python/pystate.c
M Python/symtable.c
M Python/sysmodule.c
diff --git a/Include/cpython/pystate.h b/Include/cpython/pystate.h
index cf69c72028a3a..9ac0a298baab4 100644
--- a/Include/cpython/pystate.h
+++ b/Include/cpython/pystate.h
@@ -79,9 +79,9 @@ struct _ts {
struct _ts *next;
PyInterpreterState *interp;
- int recursion_depth;
+ int recursion_remaining;
+ int recursion_limit;
int recursion_headroom; /* Allow 50 more calls to handle any errors. */
- int stackcheck_counter;
/* 'tracing' keeps track of the execution depth when tracing/profiling.
This is to prevent the actual trace/profile code from being recorded in
diff --git a/Include/internal/pycore_ceval.h b/Include/internal/pycore_ceval.h
index 53580b99d33ac..c2251b04be65d 100644
--- a/Include/internal/pycore_ceval.h
+++ b/Include/internal/pycore_ceval.h
@@ -75,12 +75,12 @@ extern void _PyEval_DeactivateOpCache(void);
/* With USE_STACKCHECK macro defined, trigger stack checks in
_Py_CheckRecursiveCall() on every 64th call to Py_EnterRecursiveCall. */
static inline int _Py_MakeRecCheck(PyThreadState *tstate) {
- return (++tstate->recursion_depth > tstate->interp->ceval.recursion_limit
- || ++tstate->stackcheck_counter > 64);
+ return (tstate->recursion_remaining-- <= 0
+ || (tstate->recursion_remaining & 63) == 0);
}
#else
static inline int _Py_MakeRecCheck(PyThreadState *tstate) {
- return (++tstate->recursion_depth > tstate->interp->ceval.recursion_limit);
+ return tstate->recursion_remaining-- <= 0;
}
#endif
@@ -101,7 +101,7 @@ static inline int _Py_EnterRecursiveCall_inline(const char *where) {
#define Py_EnterRecursiveCall(where) _Py_EnterRecursiveCall_inline(where)
static inline void _Py_LeaveRecursiveCall(PyThreadState *tstate) {
- tstate->recursion_depth--;
+ tstate->recursion_remaining++;
}
static inline void _Py_LeaveRecursiveCall_inline(void) {
diff --git a/Misc/NEWS.d/next/Core and Builtins/2021-11-11-17-14-21.bpo-45753.nEBFcC.rst b/Misc/NEWS.d/next/Core and Builtins/2021-11-11-17-14-21.bpo-45753.nEBFcC.rst
new file mode 100644
index 0000000000000..327f00d68911b
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2021-11-11-17-14-21.bpo-45753.nEBFcC.rst
@@ -0,0 +1,2 @@
+Make recursion checks a bit more efficient by tracking amount of calls left
+before overflow.
diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c
index 1f205b873beaf..c230ba28d6111 100644
--- a/Modules/_testinternalcapi.c
+++ b/Modules/_testinternalcapi.c
@@ -37,7 +37,8 @@ get_recursion_depth(PyObject *self, PyObject *Py_UNUSED(args))
PyThreadState *tstate = _PyThreadState_GET();
/* subtract one to ignore the frame of the get_recursion_depth() call */
- return PyLong_FromLong(tstate->recursion_depth - 1);
+
+ return PyLong_FromLong(tstate->recursion_limit - tstate->recursion_remaining - 1);
}
diff --git a/Python/ast.c b/Python/ast.c
index 2113124dbd51c..0c3121d3ee7b6 100644
--- a/Python/ast.c
+++ b/Python/ast.c
@@ -933,8 +933,9 @@ _PyAST_Validate(mod_ty mod)
return 0;
}
/* Be careful here to prevent overflow. */
- starting_recursion_depth = (tstate->recursion_depth < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
- tstate->recursion_depth * COMPILER_STACK_FRAME_SCALE : tstate->recursion_depth;
+ int recursion_depth = tstate->recursion_limit - tstate->recursion_remaining;
+ starting_recursion_depth = (recursion_depth< INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
+ recursion_depth * COMPILER_STACK_FRAME_SCALE : recursion_depth;
state.recursion_depth = starting_recursion_depth;
state.recursion_limit = (recursion_limit < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
recursion_limit * COMPILER_STACK_FRAME_SCALE : recursion_limit;
diff --git a/Python/ast_opt.c b/Python/ast_opt.c
index f6506cef035cd..356f60e2d5399 100644
--- a/Python/ast_opt.c
+++ b/Python/ast_opt.c
@@ -1098,8 +1098,9 @@ _PyAST_Optimize(mod_ty mod, PyArena *arena, _PyASTOptimizeState *state)
return 0;
}
/* Be careful here to prevent overflow. */
- starting_recursion_depth = (tstate->recursion_depth < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
- tstate->recursion_depth * COMPILER_STACK_FRAME_SCALE : tstate->recursion_depth;
+ int recursion_depth = tstate->recursion_limit - tstate->recursion_remaining;
+ starting_recursion_depth = (recursion_depth < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
+ recursion_depth * COMPILER_STACK_FRAME_SCALE : recursion_depth;
state->recursion_depth = starting_recursion_depth;
state->recursion_limit = (recursion_limit < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
recursion_limit * COMPILER_STACK_FRAME_SCALE : recursion_limit;
diff --git a/Python/ceval.c b/Python/ceval.c
index e808aeed73a22..bf4e22dc6fec4 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -785,42 +785,49 @@ Py_GetRecursionLimit(void)
void
Py_SetRecursionLimit(int new_limit)
{
- PyThreadState *tstate = _PyThreadState_GET();
- tstate->interp->ceval.recursion_limit = new_limit;
+ PyInterpreterState *interp = _PyInterpreterState_GET();
+ interp->ceval.recursion_limit = new_limit;
+ for (PyThreadState *p = interp->tstate_head; p != NULL; p = p->next) {
+ int depth = p->recursion_limit - p->recursion_remaining;
+ p->recursion_limit = new_limit;
+ p->recursion_remaining = new_limit - depth;
+ }
}
/* The function _Py_EnterRecursiveCall() only calls _Py_CheckRecursiveCall()
- if the recursion_depth reaches recursion_limit.
- If USE_STACKCHECK, the macro decrements recursion_limit
- to guarantee that _Py_CheckRecursiveCall() is regularly called.
- Without USE_STACKCHECK, there is no need for this. */
+ if the recursion_depth reaches recursion_limit. */
int
_Py_CheckRecursiveCall(PyThreadState *tstate, const char *where)
{
- int recursion_limit = tstate->interp->ceval.recursion_limit;
-
+ /* Check against global limit first. */
+ int depth = tstate->recursion_limit - tstate->recursion_remaining;
+ if (depth < tstate->interp->ceval.recursion_limit) {
+ tstate->recursion_limit = tstate->interp->ceval.recursion_limit;
+ tstate->recursion_remaining = tstate->recursion_limit - depth;
+ assert(tstate->recursion_remaining > 0);
+ return 0;
+ }
#ifdef USE_STACKCHECK
- tstate->stackcheck_counter = 0;
if (PyOS_CheckStack()) {
- --tstate->recursion_depth;
+ ++tstate->recursion_remaining;
_PyErr_SetString(tstate, PyExc_MemoryError, "Stack overflow");
return -1;
}
#endif
if (tstate->recursion_headroom) {
- if (tstate->recursion_depth > recursion_limit + 50) {
+ if (tstate->recursion_remaining < -50) {
/* Overflowing while handling an overflow. Give up. */
Py_FatalError("Cannot recover from stack overflow.");
}
}
else {
- if (tstate->recursion_depth > recursion_limit) {
+ if (tstate->recursion_remaining <= 0) {
tstate->recursion_headroom++;
_PyErr_Format(tstate, PyExc_RecursionError,
"maximum recursion depth exceeded%s",
where);
tstate->recursion_headroom--;
- --tstate->recursion_depth;
+ ++tstate->recursion_remaining;
return -1;
}
}
@@ -1582,7 +1589,7 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, InterpreterFrame *frame, int thr
start_frame:
if (_Py_EnterRecursiveCall(tstate, "")) {
- tstate->recursion_depth++;
+ tstate->recursion_remaining--;
goto exit_eval_frame;
}
@@ -5688,13 +5695,13 @@ _PyEvalFramePushAndInit(PyThreadState *tstate, PyFrameConstructor *con,
static int
_PyEvalFrameClearAndPop(PyThreadState *tstate, InterpreterFrame * frame)
{
- ++tstate->recursion_depth;
+ --tstate->recursion_remaining;
assert(frame->frame_obj == NULL || frame->frame_obj->f_own_locals_memory == 0);
if (_PyFrame_Clear(frame, 0)) {
- --tstate->recursion_depth;
+ ++tstate->recursion_remaining;
return -1;
}
- --tstate->recursion_depth;
+ ++tstate->recursion_remaining;
_PyThreadState_PopFrame(tstate, frame);
return 0;
}
diff --git a/Python/pystate.c b/Python/pystate.c
index a9ed08a7e34be..8df28078f2a4e 100644
--- a/Python/pystate.c
+++ b/Python/pystate.c
@@ -636,9 +636,9 @@ new_threadstate(PyInterpreterState *interp, int init)
tstate->interp = interp;
- tstate->recursion_depth = 0;
+ tstate->recursion_limit = interp->ceval.recursion_limit;
+ tstate->recursion_remaining = interp->ceval.recursion_limit;
tstate->recursion_headroom = 0;
- tstate->stackcheck_counter = 0;
tstate->tracing = 0;
tstate->root_cframe.use_tracing = 0;
tstate->root_cframe.current_frame = NULL;
diff --git a/Python/symtable.c b/Python/symtable.c
index 64c1635fba760..dc5426cf3b426 100644
--- a/Python/symtable.c
+++ b/Python/symtable.c
@@ -298,8 +298,9 @@ _PySymtable_Build(mod_ty mod, PyObject *filename, PyFutureFeatures *future)
return NULL;
}
/* Be careful here to prevent overflow. */
- starting_recursion_depth = (tstate->recursion_depth < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
- tstate->recursion_depth * COMPILER_STACK_FRAME_SCALE : tstate->recursion_depth;
+ int recursion_depth = tstate->recursion_limit - tstate->recursion_remaining;
+ starting_recursion_depth = (recursion_depth < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
+ recursion_depth * COMPILER_STACK_FRAME_SCALE : recursion_depth;
st->recursion_depth = starting_recursion_depth;
st->recursion_limit = (recursion_limit < INT_MAX / COMPILER_STACK_FRAME_SCALE) ?
recursion_limit * COMPILER_STACK_FRAME_SCALE : recursion_limit;
diff --git a/Python/sysmodule.c b/Python/sysmodule.c
index 27937a03e8968..3e2091e70ab8a 100644
--- a/Python/sysmodule.c
+++ b/Python/sysmodule.c
@@ -1187,20 +1187,14 @@ sys_setrecursionlimit_impl(PyObject *module, int new_limit)
return NULL;
}
- /* Issue #25274: When the recursion depth hits the recursion limit in
- _Py_CheckRecursiveCall(), the overflowed flag of the thread state is
- set to 1 and a RecursionError is raised. The overflowed flag is reset
- to 0 when the recursion depth goes below the low-water mark: see
- Py_LeaveRecursiveCall().
-
- Reject too low new limit if the current recursion depth is higher than
- the new low-water mark. Otherwise it may not be possible anymore to
- reset the overflowed flag to 0. */
- if (tstate->recursion_depth >= new_limit) {
+ /* Reject too low new limit if the current recursion depth is higher than
+ the new low-water mark. */
+ int depth = tstate->recursion_limit - tstate->recursion_remaining;
+ if (depth >= new_limit) {
_PyErr_Format(tstate, PyExc_RecursionError,
"cannot set the recursion limit to %i at "
"the recursion depth %i: the limit is too low",
- new_limit, tstate->recursion_depth);
+ new_limit, depth);
return NULL;
}
More information about the Python-checkins
mailing list