bpo-40521: Make list free list per-interpreter (GH-20642)

Each interpreter now has its own list free list:

* Move list numfree and free_list into PyInterpreterState.
* Add _Py_list_state structure.
* Add tstate parameter to _PyList_ClearFreeList()
  and _PyList_Fini().
* Remove "#ifdef EXPERIMENTAL_ISOLATED_SUBINTERPRETERS".
* _PyGC_Fini() clears gcstate->garbage list which can be stored in
  the list free list. Call _PyGC_Fini() before _PyList_Fini() to
  prevent leaking this list.

7 files changed, 49 insertions, 40 deletions

diff --git a/Include/internal/pycore_gc.h b/Include/internal/pycore_gc.h
index 01265d3..3388b4d 100644
--- a/Include/internal/pycore_gc.h
+++ b/Include/internal/pycore_gc.h
@@ -168,7 +168,7 @@ PyAPI_FUNC(void) _PyGC_InitState(struct _gc_runtime_state *);
 extern void _PyFrame_ClearFreeList(PyThreadState *tstate);
 extern void _PyTuple_ClearFreeList(PyThreadState *tstate);
 extern void _PyFloat_ClearFreeList(PyThreadState *tstate);
-extern void _PyList_ClearFreeList(void);
+extern void _PyList_ClearFreeList(PyThreadState *tstate);
 extern void _PyDict_ClearFreeList(void);
 extern void _PyAsyncGen_ClearFreeLists(void);
 extern void _PyContext_ClearFreeList(void);
diff --git a/Include/internal/pycore_interp.h b/Include/internal/pycore_interp.h
index 9b805f0..0eab246 100644
--- a/Include/internal/pycore_interp.h
+++ b/Include/internal/pycore_interp.h
@@ -84,6 +84,16 @@ struct _Py_tuple_state {
 #endif
 };
 
+/* Empty list reuse scheme to save calls to malloc and free */
+#ifndef PyList_MAXFREELIST
+#  define PyList_MAXFREELIST 80
+#endif
+
+struct _Py_list_state {
+    PyListObject *free_list[PyList_MAXFREELIST];
+    int numfree;
+};
+
 struct _Py_float_state {
     /* Special free list
        free_list is a singly-linked list of available PyFloatObjects,
@@ -192,6 +202,7 @@ struct _is {
     PyLongObject* small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];
 #endif
     struct _Py_tuple_state tuple;
+    struct _Py_list_state list;
     struct _Py_float_state float_state;
     struct _Py_frame_state frame;
 
diff --git a/Include/internal/pycore_pylifecycle.h b/Include/internal/pycore_pylifecycle.h
index 06d2ac1..3c35ca2 100644
--- a/Include/internal/pycore_pylifecycle.h
+++ b/Include/internal/pycore_pylifecycle.h
@@ -61,7 +61,7 @@ extern PyStatus _PyGC_Init(PyThreadState *tstate);
 extern void _PyFrame_Fini(PyThreadState *tstate);
 extern void _PyDict_Fini(void);
 extern void _PyTuple_Fini(PyThreadState *tstate);
-extern void _PyList_Fini(void);
+extern void _PyList_Fini(PyThreadState *tstate);
 extern void _PySet_Fini(void);
 extern void _PyBytes_Fini(void);
 extern void _PyFloat_Fini(PyThreadState *tstate);
diff --git a/Misc/NEWS.d/next/Core and Builtins/2020-05-20-01-17-34.bpo-40521.wvAehI.rst b/Misc/NEWS.d/next/Core and Builtins/2020-05-20-01-17-34.bpo-40521.wvAehI.rst
index 71a1064..54cc600 100644
--- a/Misc/NEWS.d/next/Core and Builtins/2020-05-20-01-17-34.bpo-40521.wvAehI.rst
+++ b/Misc/NEWS.d/next/Core and Builtins/2020-05-20-01-17-34.bpo-40521.wvAehI.rst
@@ -1,3 +1,3 @@
-The tuple free lists, the empty tuple singleton, the float free list, the slice
-cache, and the frame free list are no longer shared by all interpreters: each
-interpreter now its has own free lists and caches.
+The tuple free lists, the empty tuple singleton, the list free list, the float
+free list, the slice cache, and the frame free list are no longer shared by all
+interpreters: each interpreter now its has own free lists and caches.
diff --git a/Modules/gcmodule.c b/Modules/gcmodule.c
index 45dc89d..2f062d0 100644
--- a/Modules/gcmodule.c
+++ b/Modules/gcmodule.c
@@ -1029,7 +1029,7 @@ clear_freelists(void)
     _PyFrame_ClearFreeList(tstate);
     _PyTuple_ClearFreeList(tstate);
     _PyFloat_ClearFreeList(tstate);
-    _PyList_ClearFreeList();
+    _PyList_ClearFreeList(tstate);
     _PyDict_ClearFreeList();
     _PyAsyncGen_ClearFreeLists();
     _PyContext_ClearFreeList();
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 30d2620..043256d 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -96,65 +96,59 @@ list_preallocate_exact(PyListObject *self, Py_ssize_t size)
     return 0;
 }
 
-/* Empty list reuse scheme to save calls to malloc and free */
-#ifndef PyList_MAXFREELIST
-#  define PyList_MAXFREELIST 80
-#endif
-
-/* bpo-40521: list free lists are shared by all interpreters. */
-#ifdef EXPERIMENTAL_ISOLATED_SUBINTERPRETERS
-#  undef PyList_MAXFREELIST
-#  define PyList_MAXFREELIST 0
-#endif
-
-static PyListObject *free_list[PyList_MAXFREELIST];
-static int numfree = 0;
-
 void
-_PyList_ClearFreeList(void)
+_PyList_ClearFreeList(PyThreadState *tstate)
 {
-    while (numfree) {
-        PyListObject *op = free_list[--numfree];
+    struct _Py_list_state *state = &tstate->interp->list;
+    while (state->numfree) {
+        PyListObject *op = state->free_list[--state->numfree];
         assert(PyList_CheckExact(op));
         PyObject_GC_Del(op);
     }
 }
 
 void
-_PyList_Fini(void)
+_PyList_Fini(PyThreadState *tstate)
 {
-    _PyList_ClearFreeList();
+    _PyList_ClearFreeList(tstate);
 }
 
 /* Print summary info about the state of the optimized allocator */
 void
 _PyList_DebugMallocStats(FILE *out)
 {
+    PyInterpreterState *interp = _PyInterpreterState_GET();
+    struct _Py_list_state *state = &interp->list;
     _PyDebugAllocatorStats(out,
                            "free PyListObject",
-                           numfree, sizeof(PyListObject));
+                           state->numfree, sizeof(PyListObject));
 }
 
 PyObject *
 PyList_New(Py_ssize_t size)
 {
-    PyListObject *op;
-
     if (size < 0) {
         PyErr_BadInternalCall();
         return NULL;
     }
-    if (numfree) {
-        numfree--;
-        op = free_list[numfree];
+
+    PyInterpreterState *interp = _PyInterpreterState_GET();
+    struct _Py_list_state *state = &interp->list;
+    PyListObject *op;
+    if (state->numfree) {
+        state->numfree--;
+        op = state->free_list[state->numfree];
         _Py_NewReference((PyObject *)op);
-    } else {
+    }
+    else {
         op = PyObject_GC_New(PyListObject, &PyList_Type);
-        if (op == NULL)
+        if (op == NULL) {
             return NULL;
+        }
     }
-    if (size <= 0)
+    if (size <= 0) {
         op->ob_item = NULL;
+    }
     else {
         op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
         if (op->ob_item == NULL) {
@@ -334,10 +328,14 @@ list_dealloc(PyListObject *op)
         }
         PyMem_FREE(op->ob_item);
     }
-    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
-        free_list[numfree++] = op;
-    else
+    PyInterpreterState *interp = _PyInterpreterState_GET();
+    struct _Py_list_state *state = &interp->list;
+    if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
+        state->free_list[state->numfree++] = op;
+    }
+    else {
         Py_TYPE(op)->tp_free((PyObject *)op);
+    }
     Py_TRASHCAN_END
 }
 
diff --git a/Python/pylifecycle.c b/Python/pylifecycle.c
index 1dbdbfd..09d4d88 100644
--- a/Python/pylifecycle.c
+++ b/Python/pylifecycle.c
@@ -1251,8 +1251,8 @@ finalize_interp_types(PyThreadState *tstate, int is_main_interp)
 {
     _PyFrame_Fini(tstate);
     _PyTuple_Fini(tstate);
+    _PyList_Fini(tstate);
     if (is_main_interp) {
-        _PyList_Fini();
         _PySet_Fini();
         _PyBytes_Fini();
     }
@@ -1296,6 +1296,8 @@ finalize_interp_clear(PyThreadState *tstate)
         _PyGC_CollectNoFail();
     }
 
+    _PyGC_Fini(tstate);
+
     finalize_interp_types(tstate, is_main_interp);
 
     if (is_main_interp) {
@@ -1309,8 +1311,6 @@ finalize_interp_clear(PyThreadState *tstate)
 
         _PyExc_Fini();
     }
-
-    _PyGC_Fini(tstate);
 }