[C API] Heap types (PyType_FromSpec) must fully implement the GC protocol

[vstinner]

BPO	42972
Nosy	@nascheme, @ncoghlan, @vstinner, @tiran, @corona10, @pablogsal, @miss-islington, @shihai1991, @erlend-aasland, @Fidget-Spinner
PRs	bpo-42972: Fully implement GC protocol for sqlite3 heap types #26104 bpo-42972: Fully implement GC protocol for arraymodule types #26114 [3.10] bpo-42972: Fully implement GC protocol for sqlite3 heap types (GH-26104) #26361 [3.10] bpo-42972: Fully implement GC protocol for arraymodule types (GH-26114) #26362 bpo-42972: Fully implement GC protocol for functools keywrapper and partial types #26363 bpo-42972: Fully implement GC protocol for re types #26368 bpo-42972: Fully implement GC protocol for ssl heap types (GH-26370) #26370 bpo-42972: Fully support GC protocol for operator heap types #26371 bpo-42972: Fully support GC protocol for _queue.SimpleQueue #26372 bpo-42972: Fully support GC for mmap heap types #26373 bpo-42972: Fully support GC for hashlib heap types (GH-26374) #26374 bpo-42972: Fully support GC for pyexpat, unicodedata, and dbm/gdbm heap types #26376 bpo-42972: Fully support GC for _winapi.Overlapped #26381 [3.10] bpo-42972: Fully support GC for pyexpat, unicodedata, and dbm/gdbm heap types (GH-26376) #26397 [3.10] bpo-42972: Fully support GC for hashlib heap types (GH-26374) #26398 [3.10] bpo-42972: Fully implement GC protocol for ssl heap types (GH-26370) #26399 [3.10] bpo-42972: Fully support GC protocol for _queue.SimpleQueue (GH-26372) #26406 [3.10] bpo-42972: Fully support GC for mmap heap types (GH-26373) #26407 [3.10] bpo-42972: Fully implement GC protocol for re types (GH-26368) #26411 [3.10] bpo-42972: Fully support GC protocol for _operator heap types (GH-26371) #26413 [3.10] bpo-42972: Fully implement GC protocol for re types (GH-26368) #26414 bpo-42972: Fully implement GC protocol for functools LRU cache #26423 [3.10] bpo-42972: Fully implement GC protocol for functools keywrapper and partial types (GH-26363) #26424 [3.10] bpo-42972: Fully implement GC protocol for functools LRU cache (GH-26423) #26425 [3.10] bpo-42972: Fully support GC for _winapi.Overlapped (GH-26381) #26426 [3.10] bpo-42972: Fully support GC for _winapi.Overlapped (GH-26381) #26427 bpo-42972: Fix GC assertion error in _winapi by untracking Overlapped earlier #26429 [3.10] bpo-42972: Fully support GC for _winapi.Overlapped (GH-26381) #26430 [3.10] bpo-42972: Fully support GC for _winapi.Overlapped (GH-26381) #26431 bpo-42972: Fully implement GC protocol for xxlimited.Xxo #26451 bpo-42972: Fix sqlite3 traverse/clear #26452 [3.10] bpo-42972: Fully implement GC protocol for xxlimited (GH-26451) #26460 [3.10] bpo-42972: Fix sqlite3 traverse/clear functions (GH-26452) #26461 bpo-42972: Track sqlite3 statement objects #26475 [3.10] bpo-42972: Track sqlite3 statement objects (GH-26475) #26515 bpo-42972: _thread.RLock type implements tp_traverse #26734 [3.10] bpo-42972: _thread.RLock implements the GH protocol (GH-26734) #26735

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2021-01-19.21:54:26.099>
labels = ['expert-C-API', 'type-bug', '3.10']
title = '[C API] Heap types (PyType_FromSpec) must fully implement the GC protocol'
updated_at = <Date 2021-09-29.00:01:08.612>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2021-09-29.00:01:08.612>
actor = 'vstinner'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['C API']
creation = <Date 2021-01-19.21:54:26.099>
creator = 'vstinner'
dependencies = []
files = []
hgrepos = []
issue_num = 42972
keywords = ['patch']
message_count = 56.0
messages = ['385297', '385299', '385883', '393547', '393609', '393668', '394383', '394385', '394386', '394388', '394402', '394403', '394404', '394409', '394416', '394427', '394446', '394450', '394516', '394517', '394518', '394519', '394520', '394532', '394541', '394547', '394554', '394555', '394562', '394564', '394566', '394568', '394574', '394575', '394583', '394594', '394601', '394609', '394622', '394643', '394645', '394646', '394647', '394658', '394659', '394662', '394669', '394676', '394789', '394795', '394797', '394801', '394852', '395015', '395878', '395879']
nosy_count = 11.0
nosy_names = ['nascheme', 'ncoghlan', 'vstinner', 'christian.heimes', 'corona10', 'pablogsal', 'miss-islington', 'shihai1991', 'erlendaasland', 'kj', 'soffieswan015']
pr_nums = ['26104', '26114', '26361', '26362', '26363', '26368', '26370', '26371', '26372', '26373', '26374', '26376', '26381', '26397', '26398', '26399', '26406', '26407', '26411', '26413', '26414', '26423', '26424', '26425', '26426', '26427', '26429', '26430', '26431', '26451', '26452', '26460', '26461', '26475', '26515', '26734', '26735']
priority = None
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue42972'
versions = ['Python 3.10']

Linked PRs

• gh-87138: convert blake2b/2s types to heap types #127669
• gh-87138: convert SHA-3 object type to heap type #127670

[vstinner]

Copy of my email sent to python-dev:
https://mail.python.org/archives/list/python-dev@python.org/thread/C4ILXGPKBJQYUN5YDMTJOEOX7RHOD4S3/

Hi,

In the Python stdlib, many heap types currently don't "properly"
(fully?) implement the GC protocol which can prevent to destroy these
types at Python exit. As a side effect, some other Python objects can
also remain alive, and so are not destroyed neither.

There is an on-going effect to destroy all Python objects at exit
(bpo-1635741). This problem is getting worse when subinterpreters are
involved: Refleaks buildbots failures which prevent to spot other
regressions, and so these "leaks" / "GC bugs" must be fixed as soon as
possible. In my experience, many leaks spotted by tests using
subinterpreters were quite old, it's just that they were ignored
previously.

It's an hard problem and I don't see any simple/obvious solution right
now, except of workarounds that I dislike. Maybe the only good
solution is to fix all heap types, one by one.

== Only the Python stdlib should be affected ==

PyType_FromSpec() was added to Python 3.2 by the PEP-384 to define
"heap types" in C, but I'm not sure if it's popular in practice (ex:
Cython doesn't use it, but defines static types). I expect that most
types to still be defined the old style (static types) in a vas
majority of third party extension modules.

To be clear, static types are not affected by this email.

Third party extension modules using the limited C API (to use the
stable ABI) and PyType_FromSpec() can be affected (if they don't fully
implement the GC protocol).

== Heap type instances now stores a strong reference to their type ==

In March 2019, the PyObject_Init() function was modified in bpo-35810
to keep a strong reference (INCREF) to the type if the type is a heap
type. The fixed problem was that heap types could be destroyed before
the last instance is destroyed.

== GC and heap types ==

The new problem is that most heap types don't collaborate well with
the garbage collector. The garbage collector doesn't know anything
about Python objects, types, reference counting or anything. It only
uses the PyGC_Head header and the traverse functions. If an object
holds a strong reference to an object but its type does not define a
traverse function, the GC cannot guess/infer this reference.

A heap type must respect the following 3 conditions to collaborate with the GC:

Have the Py_TPFLAGS_HAVE_GC flag;
Define a traverse function (tp_traverse) which visits the type: Py_VISIT(Py_TYPE(self));
Instances must be tracked by the GC.

If one of these conditions is not met, the GC can fail to destroy a
type during a GC collection. If an instance is kept alive late while a
Python interpreter is being deleted, it's possible that the type is
never deleted, which can keep indirectly many objects alive and so
don't delete them neither.

In practice, when a type is not deleted, a test using subinterpreter
starts to fail on Refleaks buildbot since it leaks references. Without
subinterpreters, such leak is simply ignored, whereas this is an
on-going effect to delete Python objects at exit (bpo-1635741).

== Boring traverse functions ==

Currently, there is no default traverse implementation which visits the type.

For example, I had the implement the following function for _thread.LockType:

static int
lock_traverse(lockobject self, visitproc visit, void arg)
{
 Py_VISIT(Py_TYPE(self));
 return 0;
}

It's a little bit annoying to have to implement the GC protocol
whereas a lock cannot contain other Python objects, it's not a
container. It's just a thin wrapper to a C lock.

There is exactly one strong reference: to the type.

== Workaround: loop on gc.collect() ==

A workaround is to run gc.collect() in a loop until it returns 0 (no
object was collected).

== Traverse automatically? Nope. ==

Pablo Galindo attempts to automatically visit the type in the traverse function:

https://bugs.python.org/issue40217
0169d30...

Moreover, What's New in Python 3.9 contains a long section suggesting
to implement a traverse function for this problem, but it doesn't
suggest to track instances:
https://docs.python.org/dev/whatsnew/3.9.html#changes-in-the-c-api

This solution causes too many troubles, and so instead, traverse
functions were defined on heap types to visit the type.

Currently in the master branch, 89 types are defined as heap types on
a total of 206 types (117 types are defined statically). I don't think
that these 89 heap types respect the 3 conditions to collaborate with
the GC.

== How should we address this issue? ==

I'm not sure what should be done. Working around the issue by
triggering multiple GC collections? Emit a warning in development mode
if a heap type doesn't collaborate well with the GC?

If core developers miss these bugs and have troubles to debug them, I
expect that extension module authors would suffer even more.

== GC+heap type bugs became common ==

I'm fixing such GC issue for 1 year as part as the work on cleaning
Python objects at exit, and also indirectly related to
subinterpreters. The behavior is surprising, it's really hard to dig
into GC internals and understand what's going on. I wrote an article
on this kind of "GC bugs":
https://vstinner.github.io/subinterpreter-leaks.html

Today, I learnt the hard way that defining a traverse is not enough.
The type constructor (tp_new) must also track instances! See my fix
for _multibytecodec related to CJK codecs:

11ef53a...
https://bugs.python.org/issue42866

== Reference cycles are common ==

The GC only serves to break reference cycles. But reference cycles are
rare, right? Well...

First of all, most types create reference cycles involing themselves.
For example, a type __mro__ tuple contains the type which already
creates a ref cycle. Type methods can also contain a reference to the
type.

=> The GC must break the cycle, otherwise the type cannot be destroyed

When a function is defined in a Python module, the function
__globals__ is the module namespace (module.__dict__) which...
contains the function. Defining a function in a Python module also
creates a reference cycle which prevents to delete the module
namespace.

If a function is used as a callback somewhere, the whole module
remains "alive" until the reference to the callback is cleared.
Example. os.register_at_fork() and codecs.register() callbacks are
cleared really late during Python finalization. Currently, it's
basically the last objects which are cleared at Python exit. After
that, there is exactly one final GC collection.

=> The GC

== Debug GC issues ==

gc.get_referents() and gc.get_referrers() can be used to check traverse functions.
gc.is_tracked() can be used to check if the GC tracks an object.
Using the gdb debugger on gc_collect_main() helps to see which objects are collected. See for example the finalize_garbage() functions which calls finalizers on unreachable objects.
The solution is usually a missing traverse functions or a missing Py_VISIT() in an existing traverse function.

== __del__ hack for debugging ==

If you want to play with the issue or if you have to debug a GC issue,
you can use an object which logs a message when it's being deleted:

class VerboseDel:
 def __del__(self):
 print("DELETE OBJECT")
obj = VerboseDel()

Warning: creating such object in a module also prevents to destroy the
module namespace when the last reference to the module is deleted!
__del__.__globals__ contains a reference to the module namespace, and
obj.__class__ contains a reference to the type... Yeah, ref cycle and
GC issues are fun!

== Long email ==

Yeah, I like to put titles in my long emails. Enjoy. Happy hacking!
Victor

--
Night gathers, and now my watch begins. It shall not end until my death

[vstinner]

In June 2020, I create PR 20983 to attempt to automatically traverse the type:
"Provide a default tp_traverse implementation for the base object
type for heap types which have no tp_traverse function. The
traverse function visits the type if the type is a heap type."

I abandoned my PR.

I marked bpo-41036 as a duplicate of this issue.

[erlend-aasland]

Should we proceed with fixing GC for all heap types before continuing work with bpo-40077?

[pablogsal]

I'm marking this as a 3.10 release blocker untill all converted types that are in 3.10 have GC support.

[erlend-aasland]

I've added a checkbox for types that fully implement the GC protocol to https://discuss.python.org/t/list-of-built-in-types-converted-to-heap-types/8403/1.

Heap types that fully implement the GC protocol:

• _abc._abc_data
• _bz2.BZ2Compressor
• _bz2.BZ2Decompressor
• _csv.Dialect
• _csv.reader
• _csv.writer
• _json.Encoder
• _json.Scanner
• _lzma.LZMACompressor
• _lzma.LZMADecompressor
• _multibytecodec.MultibyteCodec
• _struct.unpack_iterator
• _thread._local
• _thread.lock
• ast.AST

Heap types that do not fully implement the GC protocol:

• _curses_panel.panel
• _dbm.dbm
• _gdbm.gdbm
• _hashlib.HASH
• _hashlib.HASHXOF
• _lsprof.Profiler
• _md5.md5
• _multibytecodec.MultibyteIncrementalDecoder
• _multibytecodec.MultibyteIncrementalEncoder
• _multibytecodec.MultibyteStreamReader
• _multibytecodec.MultibyteStreamWriter
• _overlapped.Overlapped
• _queue.SimpleQueue
• _random.Random
• _sha1.sha1
• _sha256.sha224
• _sha256.sha256
• _sha512.sha384
• _sha512.sha512
• _sre.SRE_Scanner
• _ssl.MemoryBIO
• _ssl.SSLSession
• _ssl._SSLContext
• _ssl._SSLSocket
• _struct.Struct
• _thread.RLock
• _thread._localdummy
• _tkinter.Tcl_Obj
• _tkinter.tkapp
• _tkinter.tktimertoken
• array.array
• array.arrayiterator
• functools.KeyWrapper
• functools._lru_cache_wrapper
• functools._lru_list_elem
• functools.partial
• mmap.mmap
• operator.attrgetter
• operator.itemgetter
• operator.methodcaller
• posix.DirEntry
• posix.ScandirIterator
• pyexpat.xmlparser
• re.Match
• re.Pattern
• select.devpoll
• select.epoll
• select.kevent
• select.kqueue
• select.poll
• sqlite3.Cache
• sqlite3.Connection
• sqlite3.Cursor
• sqlite3.Node
• sqlite3.PrepareProtocol
• sqlite3.Row
• sqlite3.Statement
• ssl.SSLError
• unicodedata.UCD
• winapi__overlapped.Overlapped
• zlib.Compress
• zlib.Decompress

[erlend-aasland]

Is there a deterministic way to test these changes? Will something a la this be sufficient:

import gc
import sys

gc.collect()
before = sys.gettotalrefcount()

import somemod
del sys.modules['somemod']
del somemod

gc.collect()
after = sys.gettotalrefcount()

assert after == before

[pablogsal]

New changeset d3c277a by Erlend Egeberg Aasland in branch 'main':
bpo-42972: Fully implement GC protocol for sqlite3 heap types (GH-26104)
d3c277a

[miss-islington]

New changeset e8d9df0 by Miss Islington (bot) in branch '3.10':
bpo-42972: Fully implement GC protocol for sqlite3 heap types (GH-26104)
e8d9df0

[pablogsal]

New changeset bd404cc by Erlend Egeberg Aasland in branch 'main':
bpo-42972: Fully implement GC protocol for arraymodule types (GH-26114)
bd404cc