Skip to content

bpo-39542: Exclude trashcan from the limited C API #18362

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
vstinner merged 1 commit into from
Feb 5, 2020
+89 −87
Merged

bpo-39542: Exclude trashcan from the limited C API #18362

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
86 changes: 86 additions & 0 deletions Include/cpython/object.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -455,6 +455,92 @@ PyAPI_FUNC(int) _PyObject_CheckConsistency(
PyObject *op,
int check_content);


/* Trashcan mechanism, thanks to Christian Tismer.

When deallocating a container object, it's possible to trigger an unbounded
chain of deallocations, as each Py_DECREF in turn drops the refcount on "the
next" object in the chain to 0. This can easily lead to stack overflows,
especially in threads (which typically have less stack space to work with).

A container object can avoid this by bracketing the body of its tp_dealloc
function with a pair of macros:

static void
mytype_dealloc(mytype *p)
{
... declarations go here ...

PyObject_GC_UnTrack(p); // must untrack first
Py_TRASHCAN_BEGIN(p, mytype_dealloc)
... The body of the deallocator goes here, including all calls ...
... to Py_DECREF on contained objects. ...
Py_TRASHCAN_END // there should be no code after this
}

CAUTION: Never return from the middle of the body! If the body needs to
"get out early", put a label immediately before the Py_TRASHCAN_END
call, and goto it. Else the call-depth counter (see below) will stay
above 0 forever, and the trashcan will never get emptied.

How it works: The BEGIN macro increments a call-depth counter. So long
as this counter is small, the body of the deallocator is run directly without
further ado. But if the counter gets large, it instead adds p to a list of
objects to be deallocated later, skips the body of the deallocator, and
resumes execution after the END macro. The tp_dealloc routine then returns
without deallocating anything (and so unbounded call-stack depth is avoided).

When the call stack finishes unwinding again, code generated by the END macro
notices this, and calls another routine to deallocate all the objects that
may have been added to the list of deferred deallocations. In effect, a
chain of N deallocations is broken into (N-1)/(PyTrash_UNWIND_LEVEL-1) pieces,
with the call stack never exceeding a depth of PyTrash_UNWIND_LEVEL.

Since the tp_dealloc of a subclass typically calls the tp_dealloc of the base
class, we need to ensure that the trashcan is only triggered on the tp_dealloc
of the actual class being deallocated. Otherwise we might end up with a
partially-deallocated object. To check this, the tp_dealloc function must be
passed as second argument to Py_TRASHCAN_BEGIN().
*/

/* The new thread-safe private API, invoked by the macros below. */
PyAPI_FUNC(void) _PyTrash_thread_deposit_object(PyObject*);
PyAPI_FUNC(void) _PyTrash_thread_destroy_chain(void);

#define PyTrash_UNWIND_LEVEL 50

#define Py_TRASHCAN_BEGIN_CONDITION(op, cond) \
do { \
PyThreadState *_tstate = NULL; \
/* If "cond" is false, then _tstate remains NULL and the deallocator \
* is run normally without involving the trashcan */ \
if (cond) { \
_tstate = PyThreadState_GET(); \
if (_tstate->trash_delete_nesting >= PyTrash_UNWIND_LEVEL) { \
/* Store the object (to be deallocated later) and jump past \
* Py_TRASHCAN_END, skipping the body of the deallocator */ \
_PyTrash_thread_deposit_object(_PyObject_CAST(op)); \
break; \
} \
++_tstate->trash_delete_nesting; \
}
/* The body of the deallocator is here. */
#define Py_TRASHCAN_END \
if (_tstate) { \
--_tstate->trash_delete_nesting; \
if (_tstate->trash_delete_later && _tstate->trash_delete_nesting <= 0) \
_PyTrash_thread_destroy_chain(); \
} \
} while (0);

#define Py_TRASHCAN_BEGIN(op, dealloc) Py_TRASHCAN_BEGIN_CONDITION(op, \
Py_TYPE(op)->tp_dealloc == (destructor)(dealloc))

/* For backwards compatibility, these macros enable the trashcan
* unconditionally */
#define Py_TRASHCAN_SAFE_BEGIN(op) Py_TRASHCAN_BEGIN_CONDITION(op, 1)
#define Py_TRASHCAN_SAFE_END(op) Py_TRASHCAN_END

#ifdef __cplusplus
}
#endif
87 changes: 0 additions & 87 deletions Include/object.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -607,93 +607,6 @@ it carefully, it may save lots of calls to Py_INCREF() and Py_DECREF() at
times.
*/


/* Trashcan mechanism, thanks to Christian Tismer.

When deallocating a container object, it's possible to trigger an unbounded
chain of deallocations, as each Py_DECREF in turn drops the refcount on "the
next" object in the chain to 0. This can easily lead to stack overflows,
especially in threads (which typically have less stack space to work with).

A container object can avoid this by bracketing the body of its tp_dealloc
function with a pair of macros:

static void
mytype_dealloc(mytype *p)
{
... declarations go here ...

PyObject_GC_UnTrack(p); // must untrack first
Py_TRASHCAN_BEGIN(p, mytype_dealloc)
... The body of the deallocator goes here, including all calls ...
... to Py_DECREF on contained objects. ...
Py_TRASHCAN_END // there should be no code after this
}

CAUTION: Never return from the middle of the body! If the body needs to
"get out early", put a label immediately before the Py_TRASHCAN_END
call, and goto it. Else the call-depth counter (see below) will stay
above 0 forever, and the trashcan will never get emptied.

How it works: The BEGIN macro increments a call-depth counter. So long
as this counter is small, the body of the deallocator is run directly without
further ado. But if the counter gets large, it instead adds p to a list of
objects to be deallocated later, skips the body of the deallocator, and
resumes execution after the END macro. The tp_dealloc routine then returns
without deallocating anything (and so unbounded call-stack depth is avoided).

When the call stack finishes unwinding again, code generated by the END macro
notices this, and calls another routine to deallocate all the objects that
may have been added to the list of deferred deallocations. In effect, a
chain of N deallocations is broken into (N-1)/(PyTrash_UNWIND_LEVEL-1) pieces,
with the call stack never exceeding a depth of PyTrash_UNWIND_LEVEL.

Since the tp_dealloc of a subclass typically calls the tp_dealloc of the base
class, we need to ensure that the trashcan is only triggered on the tp_dealloc
of the actual class being deallocated. Otherwise we might end up with a
partially-deallocated object. To check this, the tp_dealloc function must be
passed as second argument to Py_TRASHCAN_BEGIN().
*/

/* The new thread-safe private API, invoked by the macros below. */
PyAPI_FUNC(void) _PyTrash_thread_deposit_object(PyObject*);
PyAPI_FUNC(void) _PyTrash_thread_destroy_chain(void);

#define PyTrash_UNWIND_LEVEL 50

#define Py_TRASHCAN_BEGIN_CONDITION(op, cond) \
do { \
PyThreadState *_tstate = NULL; \
/* If "cond" is false, then _tstate remains NULL and the deallocator \
* is run normally without involving the trashcan */ \
if (cond) { \
_tstate = PyThreadState_GET(); \
if (_tstate->trash_delete_nesting >= PyTrash_UNWIND_LEVEL) { \
/* Store the object (to be deallocated later) and jump past \
* Py_TRASHCAN_END, skipping the body of the deallocator */ \
_PyTrash_thread_deposit_object(_PyObject_CAST(op)); \
break; \
} \
++_tstate->trash_delete_nesting; \
}
/* The body of the deallocator is here. */
#define Py_TRASHCAN_END \
if (_tstate) { \
--_tstate->trash_delete_nesting; \
if (_tstate->trash_delete_later && _tstate->trash_delete_nesting <= 0) \
_PyTrash_thread_destroy_chain(); \
} \
} while (0);

#define Py_TRASHCAN_BEGIN(op, dealloc) Py_TRASHCAN_BEGIN_CONDITION(op, \
Py_TYPE(op)->tp_dealloc == (destructor)(dealloc))

/* For backwards compatibility, these macros enable the trashcan
* unconditionally */
#define Py_TRASHCAN_SAFE_BEGIN(op) Py_TRASHCAN_BEGIN_CONDITION(op, 1)
#define Py_TRASHCAN_SAFE_END(op) Py_TRASHCAN_END


#ifndef Py_LIMITED_API
# define Py_CPYTHON_OBJECT_H
# include "cpython/object.h"
Expand Down
3 changes: 3 additions & 0 deletions Misc/NEWS.d/next/C API/2020-02-05-12-00-18.bpo-39542.RJCUKR.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
Exclude trashcan mechanism from the limited C API: it requires access to
PyTypeObject and PyThreadState structure fields, whereas these structures
are opaque in the limited C API.