gh-100240: Use a consistent implementation for freelists (#121934)

This combines and updates our freelist handling to use a consistent
implementation. Objects in the freelist are linked together using the
first word of memory block.

If configured with freelists disabled, these operations are essentially
no-ops.

6 files changed, 13 insertions, 104 deletions

diff --git a/Python/context.c b/Python/context.c
index c32c15f..5cafde4 100644
--- a/Python/context.c
+++ b/Python/context.c
@@ -1,6 +1,7 @@
 #include "Python.h"
 #include "pycore_call.h"          // _PyObject_VectorcallTstate()
 #include "pycore_context.h"
+#include "pycore_freelist.h"      // _Py_FREELIST_FREE(), _Py_FREELIST_POP()
 #include "pycore_gc.h"            // _PyObject_GC_MAY_BE_TRACKED()
 #include "pycore_hamt.h"
 #include "pycore_initconfig.h"    // _PyStatus_OK()
@@ -64,16 +65,6 @@ static int
 contextvar_del(PyContextVar *var);
 
 
-#ifdef WITH_FREELISTS
-static struct _Py_context_freelist *
-get_context_freelist(void)
-{
-    struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
-    return &freelists->contexts;
-}
-#endif
-
-
 PyObject *
 _PyContext_NewHamtForTests(void)
 {
@@ -343,20 +334,8 @@ class _contextvars.Context "PyContext *" "&PyContext_Type"
 static inline PyContext *
 _context_alloc(void)
 {
-    PyContext *ctx;
-#ifdef WITH_FREELISTS
-    struct _Py_context_freelist *context_freelist = get_context_freelist();
-    if (context_freelist->numfree > 0) {
-        context_freelist->numfree--;
-        ctx = context_freelist->items;
-        context_freelist->items = (PyContext *)ctx->ctx_weakreflist;
-        OBJECT_STAT_INC(from_freelist);
-        ctx->ctx_weakreflist = NULL;
-        _Py_NewReference((PyObject *)ctx);
-    }
-    else
-#endif
-    {
+    PyContext *ctx = _Py_FREELIST_POP(PyContext, contexts);
+    if (ctx == NULL) {
         ctx = PyObject_GC_New(PyContext, &PyContext_Type);
         if (ctx == NULL) {
             return NULL;
@@ -471,19 +450,7 @@ context_tp_dealloc(PyContext *self)
     }
     (void)context_tp_clear(self);
 
-#ifdef WITH_FREELISTS
-    struct _Py_context_freelist *context_freelist = get_context_freelist();
-    if (context_freelist->numfree >= 0 && context_freelist->numfree < PyContext_MAXFREELIST) {
-        context_freelist->numfree++;
-        self->ctx_weakreflist = (PyObject *)context_freelist->items;
-        context_freelist->items = self;
-        OBJECT_STAT_INC(to_freelist);
-    }
-    else
-#endif
-    {
-        Py_TYPE(self)->tp_free(self);
-    }
+    _Py_FREELIST_FREE(contexts, self, Py_TYPE(self)->tp_free);
 }
 
 static PyObject *
@@ -1264,24 +1231,6 @@ get_token_missing(void)
 ///////////////////////////
 
 
-void
-_PyContext_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization)
-{
-#ifdef WITH_FREELISTS
-    struct _Py_context_freelist *state = &freelists->contexts;
-    for (; state->numfree > 0; state->numfree--) {
-        PyContext *ctx = state->items;
-        state->items = (PyContext *)ctx->ctx_weakreflist;
-        ctx->ctx_weakreflist = NULL;
-        PyObject_GC_Del(ctx);
-    }
-    if (is_finalization) {
-        state->numfree = -1;
-    }
-#endif
-}
-
-
 PyStatus
 _PyContext_Init(PyInterpreterState *interp)
 {
diff --git a/Python/gc_free_threading.c b/Python/gc_free_threading.c
index d1d5664..53f0416 100644
--- a/Python/gc_free_threading.c
+++ b/Python/gc_free_threading.c
@@ -4,6 +4,7 @@
 #include "pycore_ceval.h"         // _Py_set_eval_breaker_bit()
 #include "pycore_context.h"
 #include "pycore_dict.h"          // _PyDict_MaybeUntrack()
+#include "pycore_freelist.h"      // _PyObject_ClearFreeLists()
 #include "pycore_initconfig.h"
 #include "pycore_interp.h"        // PyInterpreterState.gc
 #include "pycore_object.h"
diff --git a/Python/gc_gil.c b/Python/gc_gil.c
index 48646c7..7d62a9e 100644
--- a/Python/gc_gil.c
+++ b/Python/gc_gil.c
@@ -1,5 +1,5 @@
 #include "Python.h"
-#include "pycore_pystate.h"   // _Py_ClearFreeLists()
+#include "pycore_freelist.h"   // _PyObject_ClearFreeLists()
 
 #ifndef Py_GIL_DISABLED
 
diff --git a/Python/object_stack.c b/Python/object_stack.c
index bd96968..bda3190 100644
--- a/Python/object_stack.c
+++ b/Python/object_stack.c
@@ -8,24 +8,11 @@
 extern _PyObjectStackChunk *_PyObjectStackChunk_New(void);
 extern void _PyObjectStackChunk_Free(_PyObjectStackChunk *);
 
-static struct _Py_object_stack_freelist *
-get_object_stack_freelist(void)
-{
-    struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
-    return &freelists->object_stacks;
-}
-
 _PyObjectStackChunk *
 _PyObjectStackChunk_New(void)
 {
-    _PyObjectStackChunk *buf;
-    struct _Py_object_stack_freelist *obj_stack_freelist = get_object_stack_freelist();
-    if (obj_stack_freelist->numfree > 0) {
-        buf = obj_stack_freelist->items;
-        obj_stack_freelist->items = buf->prev;
-        obj_stack_freelist->numfree--;
-    }
-    else {
+    _PyObjectStackChunk *buf = _Py_FREELIST_POP_MEM(object_stack_chunks);
+    if (buf == NULL) {
         // NOTE: we use PyMem_RawMalloc() here because this is used by the GC
         // during mimalloc heap traversal. In that context, it is not safe to
         // allocate mimalloc memory, such as via PyMem_Malloc().
@@ -43,17 +30,7 @@ void
 _PyObjectStackChunk_Free(_PyObjectStackChunk *buf)
 {
     assert(buf->n == 0);
-    struct _Py_object_stack_freelist *obj_stack_freelist = get_object_stack_freelist();
-    if (obj_stack_freelist->numfree >= 0 &&
-        obj_stack_freelist->numfree < _PyObjectStackChunk_MAXFREELIST)
-    {
-        buf->prev = obj_stack_freelist->items;
-        obj_stack_freelist->items = buf;
-        obj_stack_freelist->numfree++;
-    }
-    else {
-        PyMem_RawFree(buf);
-    }
+    _Py_FREELIST_FREE(object_stack_chunks, buf, PyMem_RawFree);
 }
 
 void
@@ -87,22 +64,3 @@ _PyObjectStack_Merge(_PyObjectStack *dst, _PyObjectStack *src)
     dst->head = src->head;
     src->head = NULL;
 }
-
-void
-_PyObjectStackChunk_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization)
-{
-    if (!is_finalization) {
-        // Ignore requests to clear the free list during GC. We use object
-        // stacks during GC, so emptying the free-list is counterproductive.
-        return;
-    }
-
-    struct _Py_object_stack_freelist *freelist = &freelists->object_stacks;
-    while (freelist->numfree > 0) {
-        _PyObjectStackChunk *buf = freelist->items;
-        freelist->items = buf->prev;
-        freelist->numfree--;
-        PyMem_RawFree(buf);
-    }
-    freelist->numfree = -1;
-}
diff --git a/Python/pylifecycle.c b/Python/pylifecycle.c
index 39eaa86..6b641c0 100644
--- a/Python/pylifecycle.c
+++ b/Python/pylifecycle.c
@@ -9,6 +9,7 @@
 #include "pycore_dict.h"          // _PyDict_Fini()
 #include "pycore_exceptions.h"    // _PyExc_InitTypes()
 #include "pycore_fileutils.h"     // _Py_ResetForceASCII()
+#include "pycore_freelist.h"      // _PyObject_ClearFreeLists()
 #include "pycore_floatobject.h"   // _PyFloat_InitTypes()
 #include "pycore_global_objects_fini_generated.h"  // "_PyStaticObjects_CheckRefcnt()
 #include "pycore_import.h"        // _PyImport_BootstrapImp()
@@ -1843,7 +1844,7 @@ finalize_interp_types(PyInterpreterState *interp)
 #ifndef Py_GIL_DISABLED
     // With Py_GIL_DISABLED:
     // the freelists for the current thread state have already been cleared.
-    struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
+    struct _Py_freelists *freelists = _Py_freelists_GET();
     _PyObject_ClearFreeLists(freelists, 1);
 #endif
 
diff --git a/Python/pystate.c b/Python/pystate.c
index f0452aa..6fbd17f 100644
--- a/Python/pystate.c
+++ b/Python/pystate.c
@@ -9,9 +9,9 @@
 #include "pycore_dtoa.h"          // _dtoa_state_INIT()
 #include "pycore_emscripten_trampoline.h"  // _Py_EmscriptenTrampoline_Init()
 #include "pycore_frame.h"
+#include "pycore_freelist.h"      // _PyObject_ClearFreeLists()
 #include "pycore_initconfig.h"    // _PyStatus_OK()
 #include "pycore_object.h"        // _PyType_InitCache()
-#include "pycore_object_stack.h"  // _PyObjectStackChunk_ClearFreeList()
 #include "pycore_parking_lot.h"   // _PyParkingLot_AfterFork()
 #include "pycore_pyerrors.h"      // _PyErr_Clear()
 #include "pycore_pylifecycle.h"   // _PyAST_Fini()
@@ -1738,7 +1738,7 @@ PyThreadState_Clear(PyThreadState *tstate)
 
 #ifdef Py_GIL_DISABLED
     // Each thread should clear own freelists in free-threading builds.
-    struct _Py_object_freelists *freelists = _Py_object_freelists_GET();
+    struct _Py_freelists *freelists = _Py_freelists_GET();
     _PyObject_ClearFreeLists(freelists, 1);
 
     // Remove ourself from the biased reference counting table of threads.