gh-108634: Py_TRACE_REFS uses a hash table (#108663)

Python built with "configure --with-trace-refs" (tracing references)
is now ABI compatible with Python release build and debug build.
Moreover, it now also supports the Limited API.

Change Py_TRACE_REFS build:

* Remove _PyObject_EXTRA_INIT macro.
* The PyObject structure no longer has two extra members (_ob_prev
  and _ob_next).
* Use a hash table (_Py_hashtable_t) to trace references (all
  objects): PyInterpreterState.object_state.refchain.
* Py_TRACE_REFS build is now ABI compatible with release build and
  debug build.
* Limited C API extensions can now be built with Py_TRACE_REFS:
  xxlimited, xxlimited_35, _testclinic_limited.
* No longer rename PyModule_Create2() and PyModule_FromDefAndSpec2()
  functions to PyModule_Create2TraceRefs() and
  PyModule_FromDefAndSpec2TraceRefs().
* _Py_PrintReferenceAddresses() is now called before
  finalize_interp_delete() which deletes the refchain hash table.
* test_tracemalloc find_trace() now also filters by size to ignore
  the memory allocated by _PyRefchain_Trace().

Test changes for Py_TRACE_REFS:

* Add test.support.Py_TRACE_REFS constant.
* Add test_sys.test_getobjects() to test sys.getobjects() function.
* test_exceptions skips test_recursion_normalizing_with_no_memory()
  and test_memory_error_in_PyErr_PrintEx() if Python is built with
  Py_TRACE_REFS.
* test_repl skips test_no_memory().
* test_capi skisp test_set_nomemory().

3 files changed, 10 insertions, 8 deletions

diff --git a/Include/internal/pycore_object.h b/Include/internal/pycore_object.h
index 7c142b3..d842816 100644
--- a/Include/internal/pycore_object.h
+++ b/Include/internal/pycore_object.h
@@ -55,7 +55,6 @@ PyAPI_FUNC(int) _PyObject_IsFreed(PyObject *);
    backwards compatible solution */
 #define _PyObject_HEAD_INIT(type)         \
     {                                     \
-        _PyObject_EXTRA_INIT              \
         .ob_refcnt = _Py_IMMORTAL_REFCNT, \
         .ob_type = (type)                 \
     },
@@ -184,6 +183,8 @@ _PyType_HasFeature(PyTypeObject *type, unsigned long feature) {
 extern void _PyType_InitCache(PyInterpreterState *interp);
 
 extern void _PyObject_InitState(PyInterpreterState *interp);
+extern void _PyObject_FiniState(PyInterpreterState *interp);
+extern bool _PyRefchain_IsTraced(PyInterpreterState *interp, PyObject *obj);
 
 /* Inline functions trading binary compatibility for speed:
    _PyObject_Init() is the fast version of PyObject_Init(), and
@@ -302,7 +303,7 @@ extern void _PyDebug_PrintTotalRefs(void);
 #endif
 
 #ifdef Py_TRACE_REFS
-extern void _Py_AddToAllObjects(PyObject *op, int force);
+extern void _Py_AddToAllObjects(PyObject *op);
 extern void _Py_PrintReferences(PyInterpreterState *, FILE *);
 extern void _Py_PrintReferenceAddresses(PyInterpreterState *, FILE *);
 #endif
diff --git a/Include/internal/pycore_object_state.h b/Include/internal/pycore_object_state.h
index 65feb5a..9eac27b1 100644
--- a/Include/internal/pycore_object_state.h
+++ b/Include/internal/pycore_object_state.h
@@ -8,6 +8,8 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
+#include "pycore_hashtable.h"     // _Py_hashtable_t
+
 struct _py_object_runtime_state {
 #ifdef Py_REF_DEBUG
     Py_ssize_t interpreter_leaks;
@@ -20,11 +22,10 @@ struct _py_object_state {
     Py_ssize_t reftotal;
 #endif
 #ifdef Py_TRACE_REFS
-    /* Head of circular doubly-linked list of all objects.  These are linked
-     * together via the _ob_prev and _ob_next members of a PyObject, which
-     * exist only in a Py_TRACE_REFS build.
-     */
-    PyObject refchain;
+    // Hash table storing all objects. The key is the object pointer
+    // (PyObject*) and the value is always the number 1 (as uintptr_t).
+    // See _PyRefchain_IsTraced() and _PyRefchain_Trace() functions.
+    _Py_hashtable_t *refchain;
 #endif
     int _not_used;
 };
diff --git a/Include/internal/pycore_runtime_init.h b/Include/internal/pycore_runtime_init.h
index c775a8a..2deba02 100644
--- a/Include/internal/pycore_runtime_init.h
+++ b/Include/internal/pycore_runtime_init.h
@@ -192,7 +192,7 @@ extern PyTypeObject _PyExc_MemoryError;
 #ifdef Py_TRACE_REFS
 # define _py_object_state_INIT(INTERP) \
     { \
-        .refchain = {&INTERP.object_state.refchain, &INTERP.object_state.refchain}, \
+        .refchain = NULL, \
     }
 #else
 # define _py_object_state_INIT(INTERP) \