I added the following new functions to Python 3.6:

* _PyObject_FastCallDict()
* _PyObject_FastCallKeywords()
* _PyFunction_FastCallDict()
* _PyFunction_FastCallKeywords()
* _PyCFunction_FastCallDict()
* _PyCFunction_FastCallKeywords()

I'm not sure that these functions update correctly the "recursion_depth" counter using Py_EnterRecursiveCall() and Py_LeaveRecursiveCall().

I think basic idea is "wrap unknown function call at least once, and preferably only once".

_PyEval_EvalFrameDefault() calls Py_EnterRecursiveCall("").
So wrapping PyFunction_(Fast)Call* with Py_EnterRecursiveCall() seems redundant.

On the other hand, PyCFunction may calls method of extension module,
and it can cause recursive call.
So I think PyCFunction_*Call* methods calling function pointer it has
(e.g. _PyCFunction_FastCallKeywords) should call Py_EnterRecursiveCall().

And caller of them can skip Py_EnterRecursiveCall().
For example, _PyObject_FastCallDict() may call _PyFunction_FastCallDict() or
_PyCFunction_FastCallDict(), or tp_fastcall (via _Py_RawFastCallDict) or tp_call.
It can wrap all, but wrapping only tp_fastcall and tp_call is better.

Naoki: "On the other hand, PyCFunction may calls method of extension module, and it can cause recursive call. So I think PyCFunction_*Call* methods calling function pointer it has (e.g. _PyCFunction_FastCallKeywords) should call Py_EnterRecursiveCall()."

In Python 3.5, C functions are only calls inside Py_EnterRecursiveCall() if calls from PyObject_Call(). There are many other ways to call C functions which don't use Py_EnterRecursiveCall(). Examples:

* call_function() => call the C function
* call_function() => PyCFunction_Call() => call the C function
* call_function() => do_call() => PyCFunction_Call() => call the C function
* ext_do_call() => PyCFunction_Call() => call the C function

call_function() and do_call() have a special case for PyCFunction, otherwise they call the generic PyObject_Call() which uses Py_EnterRecursiveCall().

I agree that calling C functions with Py_EnterRecursiveCall() would help to prevent stack overflow crashs.

Attached enter_recursive_call.patch patch:

* _PyMethodDef_RawFastCallDict() (internal helper of _PyCFunction_FastCallDict()) and _PyCFunction_FastCallKeywords() now use Py_EnterRecursiveCall()
* _PyObject_FastCallKeywords(): move Py_EnterRecursiveCall() closer to the final call to simplify error handling
* Modify _PyObject_FastCallDict() to not call _PyFunction_FastCallDict() nor _PyCFunction_FastCallDict() inside Py_EnterRecursiveCall(), since these functions already use Py_EnterRecursiveCall() internally

New changeset 88ed9d9eabc1 by Victor Stinner in branch 'default':
Issue #29306: Fix usage of Py_EnterRecursiveCall()
https://hg.python.org/cpython/rev/88ed9d9eabc1

I still need to backport fixes to Python 3.6, maybe even Python 3.5.

New changeset 65d24ff4bbd3320acadb58a5e4d944c84536cb2c by Victor Stinner in branch 'master':
Issue #29306: Fix usage of Py_EnterRecursiveCall()
https://github.com/python/cpython/commit/65d24ff4bbd3320acadb58a5e4d944c84536cb2c

I needed this fix to work on issue #29465. I expected that my patch was reviewed, but woops, it wasn't the case and I missed a refleak. Hopefully, the refleak is now fixed!

New changeset 37705f89c72b by Victor Stinner in branch 'default':
Fix refleaks if Py_EnterRecursiveCall() fails
https://hg.python.org/cpython/rev/37705f89c72b

New changeset 1101819ba99afcb4d1b6495d49b17bdd0acfe761 by Victor Stinner in branch 'master':
Fix refleaks if Py_EnterRecursiveCall() fails
https://github.com/python/cpython/commit/1101819ba99afcb4d1b6495d49b17bdd0acfe761

enter_recursive_call_36.patch: Patch for Python 3.6.

* Add Py_EnterRecursiveCall() into C functions
* Don't call C functions inside a Py_EnterRecursiveCall() block in PyObject_Call()

check_recursion_depth.py: script using Python functions and C function (functools.partial) to check the recursion depth.

Example with Python 3.6:

haypo@selma$ ./python check_recursion_depth.py   # unpatched
got: 148, expected: 100

haypo@selma$ ./python check_recursion_depth.py   # patched
got: 100, expected: 100

Maybe we need "proxies" in _testcapi for each kind of function, a function taking a callback and calling this function. Function types:

* C function, METH_NOARGS
* C function, METH_O
* C function, METH_VARRGS
* C function, METH_VARRGS | METH_KEYWORDS
* C function, METH_FASTCALL
* Python function
* Maybe even most common C functions to call functions: PyObject_Call(), _PyObject_FastCallDict(), _PyObject_FastCallKeywords(), etc.

I tested check_recursion_depth.py: Python 2.7, 3.5 and 3.6 have the bug. Python 3.7 is already fixed.

I'm not sure about touching the stable branches. At least, the issue has been fixed since Python 3.7. I close the issue.