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.

11 files changed, 159 insertions, 160 deletions

diff --git a/Include/internal/pycore_context.h b/Include/internal/pycore_context.h
index 10c1f1e..2ecb40b 100644
--- a/Include/internal/pycore_context.h
+++ b/Include/internal/pycore_context.h
@@ -5,7 +5,6 @@
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"      // _PyFreeListState
 #include "pycore_hamt.h"          // PyHamtObject
 
 
diff --git a/Include/internal/pycore_dict.h b/Include/internal/pycore_dict.h
index 56cc494..a4bdf0d 100644
--- a/Include/internal/pycore_dict.h
+++ b/Include/internal/pycore_dict.h
@@ -8,7 +8,6 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"             // _PyFreeListState
 #include "pycore_object.h"               // PyManagedDictPointer
 #include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_ACQUIRE
 
diff --git a/Include/internal/pycore_floatobject.h b/Include/internal/pycore_floatobject.h
index f984df6..be1c6cc 100644
--- a/Include/internal/pycore_floatobject.h
+++ b/Include/internal/pycore_floatobject.h
@@ -8,7 +8,6 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"      // _PyFreeListState
 #include "pycore_unicodeobject.h" // _PyUnicodeWriter
 
 /* runtime lifecycle */
diff --git a/Include/internal/pycore_freelist.h b/Include/internal/pycore_freelist.h
index e684e08..1ac0fed 100644
--- a/Include/internal/pycore_freelist.h
+++ b/Include/internal/pycore_freelist.h
@@ -8,144 +8,109 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-// PyTuple_MAXSAVESIZE - largest tuple to save on free list
-// PyTuple_MAXFREELIST - maximum number of tuples of each size to save
-
-#ifdef WITH_FREELISTS
-// with freelists
-#  define PyTuple_MAXSAVESIZE 20
-#  define PyTuple_NFREELISTS PyTuple_MAXSAVESIZE
-#  define PyTuple_MAXFREELIST 2000
-#  define PyList_MAXFREELIST 80
-#  define PyDict_MAXFREELIST 80
-#  define PyFloat_MAXFREELIST 100
-#  define PyContext_MAXFREELIST 255
-# define _PyAsyncGen_MAXFREELIST 80
-#  define _PyObjectStackChunk_MAXFREELIST 4
-#else
-#  define PyTuple_NFREELISTS 0
-#  define PyTuple_MAXFREELIST 0
-#  define PyList_MAXFREELIST 0
-#  define PyDict_MAXFREELIST 0
-#  define PyFloat_MAXFREELIST 0
-#  define PyContext_MAXFREELIST 0
-#  define _PyAsyncGen_MAXFREELIST 0
-#  define _PyObjectStackChunk_MAXFREELIST 0
-#endif
-
-struct _Py_list_freelist {
-#ifdef WITH_FREELISTS
-    PyListObject *items[PyList_MAXFREELIST];
-    int numfree;
+#include "pycore_freelist_state.h"      // struct _Py_freelists
+#include "pycore_object.h"              // _PyObject_IS_GC
+#include "pycore_pystate.h"             // _PyThreadState_GET
+#include "pycore_code.h"                // OBJECT_STAT_INC
+
+static inline struct _Py_freelists *
+_Py_freelists_GET(void)
+{
+    PyThreadState *tstate = _PyThreadState_GET();
+#ifdef Py_DEBUG
+    _Py_EnsureTstateNotNULL(tstate);
 #endif
-};
-
-struct _Py_tuple_freelist {
-#if WITH_FREELISTS
-    /* There is one freelist for each size from 1 to PyTuple_MAXSAVESIZE.
-       The empty tuple is handled separately.
 
-       Each tuple stored in the array is the head of the linked list
-       (and the next available tuple) for that size.  The actual tuple
-       object is used as the linked list node, with its first item
-       (ob_item[0]) pointing to the next node (i.e. the previous head).
-       Each linked list is initially NULL. */
-    PyTupleObject *items[PyTuple_NFREELISTS];
-    int numfree[PyTuple_NFREELISTS];
+#ifdef Py_GIL_DISABLED
+    return &((_PyThreadStateImpl*)tstate)->freelists;
 #else
-    char _unused;  // Empty structs are not allowed.
-#endif
-};
-
-struct _Py_float_freelist {
-#ifdef WITH_FREELISTS
-    /* Special free list
-       free_list is a singly-linked list of available PyFloatObjects,
-       linked via abuse of their ob_type members. */
-    int numfree;
-    PyFloatObject *items;
-#endif
-};
-
-struct _Py_dict_freelist {
-#ifdef WITH_FREELISTS
-    /* Dictionary reuse scheme to save calls to malloc and free */
-    PyDictObject *items[PyDict_MAXFREELIST];
-    int numfree;
+    return &tstate->interp->object_state.freelists;
 #endif
-};
+}
 
-struct _Py_dictkeys_freelist {
-#ifdef WITH_FREELISTS
-    /* Dictionary keys reuse scheme to save calls to malloc and free */
-    PyDictKeysObject *items[PyDict_MAXFREELIST];
-    int numfree;
-#endif
-};
+#ifndef WITH_FREELISTS
+#define _Py_FREELIST_FREE(NAME, op, freefunc) freefunc(op)
+#define _Py_FREELIST_PUSH(NAME, op, limit) (0)
+#define _Py_FREELIST_POP(TYPE, NAME) (NULL)
+#define _Py_FREELIST_POP_MEM(NAME) (NULL)
+#define _Py_FREELIST_SIZE(NAME) (0)
+#else
+// Pushes `op` to the freelist, calls `freefunc` if the freelist is full
+#define _Py_FREELIST_FREE(NAME, op, freefunc) \
+    _PyFreeList_Free(&_Py_freelists_GET()->NAME, _PyObject_CAST(op), \
+                     Py_ ## NAME ## _MAXFREELIST, freefunc)
+// Pushes `op` to the freelist, returns 1 if successful, 0 if the freelist is full
+#define _Py_FREELIST_PUSH(NAME, op, limit) \
+    _PyFreeList_Push(&_Py_freelists_GET()->NAME, _PyObject_CAST(op), limit)
+
+// Pops a PyObject from the freelist, returns NULL if the freelist is empty.
+#define _Py_FREELIST_POP(TYPE, NAME) \
+    _Py_CAST(TYPE*, _PyFreeList_Pop(&_Py_freelists_GET()->NAME))
+
+// Pops a non-PyObject data structure from the freelist, returns NULL if the
+// freelist is empty.
+#define _Py_FREELIST_POP_MEM(NAME) \
+    _PyFreeList_PopMem(&_Py_freelists_GET()->NAME)
+
+#define _Py_FREELIST_SIZE(NAME) (int)((_Py_freelists_GET()->NAME).size)
+
+static inline int
+_PyFreeList_Push(struct _Py_freelist *fl, void *obj, Py_ssize_t maxsize)
+{
+    if (fl->size < maxsize && fl->size >= 0) {
+        *(void **)obj = fl->freelist;
+        fl->freelist = obj;
+        fl->size++;
+        OBJECT_STAT_INC(to_freelist);
+        return 1;
+    }
+    return 0;
+}
 
-struct _Py_slice_freelist {
-#ifdef WITH_FREELISTS
-    /* Using a cache is very effective since typically only a single slice is
-       created and then deleted again. */
-    PySliceObject *slice_cache;
-#endif
-};
+static inline void
+_PyFreeList_Free(struct _Py_freelist *fl, void *obj, Py_ssize_t maxsize,
+                 freefunc dofree)
+{
+    if (!_PyFreeList_Push(fl, obj, maxsize)) {
+        dofree(obj);
+    }
+}
 
-struct _Py_context_freelist {
-#ifdef WITH_FREELISTS
-    // List of free PyContext objects
-    PyContext *items;
-    int numfree;
-#endif
-};
+static inline void *
+_PyFreeList_PopNoStats(struct _Py_freelist *fl)
+{
+    void *obj = fl->freelist;
+    if (obj != NULL) {
+        assert(fl->size > 0);
+        fl->freelist = *(void **)obj;
+        fl->size--;
+    }
+    return obj;
+}
 
-struct _Py_async_gen_freelist {
-#ifdef WITH_FREELISTS
-    /* Freelists boost performance 6-10%; they also reduce memory
-       fragmentation, as _PyAsyncGenWrappedValue and PyAsyncGenASend
-       are short-living objects that are instantiated for every
-       __anext__() call. */
-    struct _PyAsyncGenWrappedValue* items[_PyAsyncGen_MAXFREELIST];
-    int numfree;
-#endif
-};
+static inline PyObject *
+_PyFreeList_Pop(struct _Py_freelist *fl)
+{
+    PyObject *op = _PyFreeList_PopNoStats(fl);
+    if (op != NULL) {
+        OBJECT_STAT_INC(from_freelist);
+        _Py_NewReference(op);
+    }
+    return op;
+}
 
-struct _Py_async_gen_asend_freelist {
-#ifdef WITH_FREELISTS
-    struct PyAsyncGenASend* items[_PyAsyncGen_MAXFREELIST];
-    int numfree;
+static inline void *
+_PyFreeList_PopMem(struct _Py_freelist *fl)
+{
+    void *op = _PyFreeList_PopNoStats(fl);
+    if (op != NULL) {
+        OBJECT_STAT_INC(from_freelist);
+    }
+    return op;
+}
 #endif
-};
-
-struct _PyObjectStackChunk;
-
-struct _Py_object_stack_freelist {
-    struct _PyObjectStackChunk *items;
-    Py_ssize_t numfree;
-};
-
-struct _Py_object_freelists {
-    struct _Py_float_freelist floats;
-    struct _Py_tuple_freelist tuples;
-    struct _Py_list_freelist lists;
-    struct _Py_dict_freelist dicts;
-    struct _Py_dictkeys_freelist dictkeys;
-    struct _Py_slice_freelist slices;
-    struct _Py_context_freelist contexts;
-    struct _Py_async_gen_freelist async_gens;
-    struct _Py_async_gen_asend_freelist async_gen_asends;
-    struct _Py_object_stack_freelist object_stacks;
-};
 
-extern void _PyObject_ClearFreeLists(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyTuple_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyFloat_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyList_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PySlice_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyDict_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyAsyncGen_ClearFreeLists(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyContext_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
-extern void _PyObjectStackChunk_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization);
+extern void _PyObject_ClearFreeLists(struct _Py_freelists *freelists, int is_finalization);
 
 #ifdef __cplusplus
 }
diff --git a/Include/internal/pycore_freelist_state.h b/Include/internal/pycore_freelist_state.h
new file mode 100644
index 0000000..d4c3d60
--- /dev/null
+++ b/Include/internal/pycore_freelist_state.h
@@ -0,0 +1,59 @@
+#ifndef Py_INTERNAL_FREELIST_STATE_H
+#define Py_INTERNAL_FREELIST_STATE_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifndef Py_BUILD_CORE
+#  error "this header requires Py_BUILD_CORE define"
+#endif
+
+#ifdef WITH_FREELISTS
+// with freelists
+#  define PyTuple_MAXSAVESIZE 20     // Largest tuple to save on freelist
+#  define Py_tuple_MAXFREELIST 2000  // Maximum number of tuples of each size to save
+#  define Py_lists_MAXFREELIST 80
+#  define Py_dicts_MAXFREELIST 80
+#  define Py_dictkeys_MAXFREELIST 80
+#  define Py_floats_MAXFREELIST 100
+#  define Py_slices_MAXFREELIST 1
+#  define Py_contexts_MAXFREELIST 255
+#  define Py_async_gens_MAXFREELIST 80
+#  define Py_async_gen_asends_MAXFREELIST 80
+#  define Py_object_stack_chunks_MAXFREELIST 4
+#else
+#  define PyTuple_MAXSAVESIZE 0
+#endif
+
+// A generic freelist of either PyObjects or other data structures.
+struct _Py_freelist {
+    // Entries are linked together using the first word of the the object.
+    // For PyObjects, this overlaps with the `ob_refcnt` field or the `ob_tid`
+    // field.
+    void *freelist;
+
+    // The number of items in the free list or -1 if the free list is disabled
+    Py_ssize_t size;
+};
+
+struct _Py_freelists {
+#ifdef WITH_FREELISTS
+    struct _Py_freelist floats;
+    struct _Py_freelist tuples[PyTuple_MAXSAVESIZE];
+    struct _Py_freelist lists;
+    struct _Py_freelist dicts;
+    struct _Py_freelist dictkeys;
+    struct _Py_freelist slices;
+    struct _Py_freelist contexts;
+    struct _Py_freelist async_gens;
+    struct _Py_freelist async_gen_asends;
+    struct _Py_freelist object_stack_chunks;
+#else
+    char _unused;  // Empty structs are not allowed.
+#endif
+};
+
+#ifdef __cplusplus
+}
+#endif
+#endif /* !Py_INTERNAL_FREELIST_STATE_H */
diff --git a/Include/internal/pycore_gc.h b/Include/internal/pycore_gc.h
index 28e34d3..b4bf36e 100644
--- a/Include/internal/pycore_gc.h
+++ b/Include/internal/pycore_gc.h
@@ -8,8 +8,6 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"   // _PyFreeListState
-
 /* GC information is stored BEFORE the object structure. */
 typedef struct {
     // Pointer to next object in the list.
diff --git a/Include/internal/pycore_list.h b/Include/internal/pycore_list.h
index 73695d1..56ddb54 100644
--- a/Include/internal/pycore_list.h
+++ b/Include/internal/pycore_list.h
@@ -8,8 +8,6 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"  // _PyFreeListState
-
 PyAPI_FUNC(PyObject*) _PyList_Extend(PyListObject *, PyObject *);
 extern void _PyList_DebugMallocStats(FILE *out);
 
diff --git a/Include/internal/pycore_object_stack.h b/Include/internal/pycore_object_stack.h
index fc130b1..c607ea8 100644
--- a/Include/internal/pycore_object_stack.h
+++ b/Include/internal/pycore_object_stack.h
@@ -1,8 +1,6 @@
 #ifndef Py_INTERNAL_OBJECT_STACK_H
 #define Py_INTERNAL_OBJECT_STACK_H
 
-#include "pycore_freelist.h"        // _PyFreeListState
-
 #ifdef __cplusplus
 extern "C" {
 #endif
diff --git a/Include/internal/pycore_object_state.h b/Include/internal/pycore_object_state.h
index cd7c933..e7fa7c1 100644
--- a/Include/internal/pycore_object_state.h
+++ b/Include/internal/pycore_object_state.h
@@ -8,8 +8,8 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"      // _PyObject_freelists
-#include "pycore_hashtable.h"     // _Py_hashtable_t
+#include "pycore_freelist_state.h"  // _Py_freelists
+#include "pycore_hashtable.h"       // _Py_hashtable_t
 
 struct _py_object_runtime_state {
 #ifdef Py_REF_DEBUG
@@ -20,7 +20,7 @@ struct _py_object_runtime_state {
 
 struct _py_object_state {
 #if !defined(Py_GIL_DISABLED)
-    struct _Py_object_freelists freelists;
+    struct _Py_freelists freelists;
 #endif
 #ifdef Py_REF_DEBUG
     Py_ssize_t reftotal;
diff --git a/Include/internal/pycore_pystate.h b/Include/internal/pycore_pystate.h
index b0e7252..fade559 100644
--- a/Include/internal/pycore_pystate.h
+++ b/Include/internal/pycore_pystate.h
@@ -8,11 +8,9 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_freelist.h"      // _PyFreeListState
 #include "pycore_runtime.h"       // _PyRuntime
 #include "pycore_tstate.h"        // _PyThreadStateImpl
 
-
 // Values for PyThreadState.state. A thread must be in the "attached" state
 // before calling most Python APIs. If the GIL is enabled, then "attached"
 // implies that the thread holds the GIL and "detached" implies that the
@@ -279,20 +277,6 @@ PyAPI_FUNC(const PyConfig*) _Py_GetConfig(void);
 // See also PyInterpreterState_Get() and _PyInterpreterState_GET().
 extern PyInterpreterState* _PyGILState_GetInterpreterStateUnsafe(void);
 
-static inline struct _Py_object_freelists* _Py_object_freelists_GET(void)
-{
-    PyThreadState *tstate = _PyThreadState_GET();
-#ifdef Py_DEBUG
-    _Py_EnsureTstateNotNULL(tstate);
-#endif
-
-#ifdef Py_GIL_DISABLED
-    return &((_PyThreadStateImpl*)tstate)->freelists;
-#else
-    return &tstate->interp->object_state.freelists;
-#endif
-}
-
 #ifdef __cplusplus
 }
 #endif
diff --git a/Include/internal/pycore_tstate.h b/Include/internal/pycore_tstate.h
index 1ed5b1d..18c972b 100644
--- a/Include/internal/pycore_tstate.h
+++ b/Include/internal/pycore_tstate.h
@@ -8,10 +8,10 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#include "pycore_brc.h"           // struct _brc_thread_state
-#include "pycore_freelist.h"      // struct _Py_freelist_state
-#include "pycore_mimalloc.h"      // struct _mimalloc_thread_state
-#include "pycore_qsbr.h"          // struct qsbr
+#include "pycore_brc.h"             // struct _brc_thread_state
+#include "pycore_freelist_state.h"  // struct _Py_freelists
+#include "pycore_mimalloc.h"        // struct _mimalloc_thread_state
+#include "pycore_qsbr.h"            // struct qsbr
 
 
 // Every PyThreadState is actually allocated as a _PyThreadStateImpl. The
@@ -29,7 +29,7 @@ typedef struct _PyThreadStateImpl {
 #ifdef Py_GIL_DISABLED
     struct _gc_thread_state gc;
     struct _mimalloc_thread_state mimalloc;
-    struct _Py_object_freelists freelists;
+    struct _Py_freelists freelists;
     struct _brc_thread_state brc;
 #endif