5 files changed, 84 insertions, 0 deletions
diff --git a/Include/internal/pycore_brc.h b/Include/internal/pycore_brc.h
new file mode 100644
index 0000000..3453d83
--- /dev/null
+++ b/Include/internal/pycore_brc.h
@@ -0,0 +1,74 @@
+#ifndef Py_INTERNAL_BRC_H
+#define Py_INTERNAL_BRC_H
+
+#include <stdint.h>
+#include "pycore_llist.h"           // struct llist_node
+#include "pycore_lock.h"            // PyMutex
+#include "pycore_object_stack.h"    // _PyObjectStack
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifndef Py_BUILD_CORE
+#  error "this header requires Py_BUILD_CORE define"
+#endif
+
+#ifdef Py_GIL_DISABLED
+
+// Prime number to avoid correlations with memory addresses.
+#define _Py_BRC_NUM_BUCKETS 257
+
+// Hash table bucket
+struct _brc_bucket {
+    // Mutex protects both the bucket and thread state queues in this bucket.
+    PyMutex mutex;
+
+    // Linked list of _PyThreadStateImpl objects hashed to this bucket.
+    struct llist_node root;
+};
+
+// Per-interpreter biased reference counting state
+struct _brc_state {
+    // Hash table of thread states by thread-id. Thread states within a bucket
+    // are chained using a doubly-linked list.
+    struct _brc_bucket table[_Py_BRC_NUM_BUCKETS];
+};
+
+// Per-thread biased reference counting state
+struct _brc_thread_state {
+    // Linked-list of thread states per hash bucket
+    struct llist_node bucket_node;
+
+    // Thread-id as determined by _PyThread_Id()
+    uintptr_t tid;
+
+    // Objects with refcounts to be merged (protected by bucket mutex)
+    _PyObjectStack objects_to_merge;
+
+    // Local stack of objects to be merged (not accessed by other threads)
+    _PyObjectStack local_objects_to_merge;
+};
+
+// Initialize/finalize the per-thread biased reference counting state
+void _Py_brc_init_thread(PyThreadState *tstate);
+void _Py_brc_remove_thread(PyThreadState *tstate);
+
+// Initialize per-interpreter state
+void _Py_brc_init_state(PyInterpreterState *interp);
+
+void _Py_brc_after_fork(PyInterpreterState *interp);
+
+// Enqueues an object to be merged by it's owning thread (tid). This
+// steals a reference to the object.
+void _Py_brc_queue_object(PyObject *ob);
+
+// Merge the refcounts of queued objects for the current thread.
+void _Py_brc_merge_refcounts(PyThreadState *tstate);
+
+#endif /* Py_GIL_DISABLED */
+
+#ifdef __cplusplus
+}
+#endif
+#endif /* !Py_INTERNAL_BRC_H */
diff --git a/Include/internal/pycore_ceval.h b/Include/internal/pycore_ceval.h
index a66af13..b158fc9 100644
--- a/Include/internal/pycore_ceval.h
+++ b/Include/internal/pycore_ceval.h
@@ -206,6 +206,7 @@ void _PyEval_FrameClearAndPop(PyThreadState *tstate, _PyInterpreterFrame *frame)
 #define _PY_ASYNC_EXCEPTION_BIT 3
 #define _PY_GC_SCHEDULED_BIT 4
 #define _PY_EVAL_PLEASE_STOP_BIT 5
+#define _PY_EVAL_EXPLICIT_MERGE_BIT 6
 
 /* Reserve a few bits for future use */
 #define _PY_EVAL_EVENTS_BITS 8
diff --git a/Include/internal/pycore_interp.h b/Include/internal/pycore_interp.h
index f7c332e..31d8807 100644
--- a/Include/internal/pycore_interp.h
+++ b/Include/internal/pycore_interp.h
@@ -201,6 +201,7 @@ struct _is {
 
 #if defined(Py_GIL_DISABLED)
     struct _mimalloc_interp_state mimalloc;
+    struct _brc_state brc;  // biased reference counting state
 #endif
 
     // Per-interpreter state for the obmalloc allocator.  For the main
diff --git a/Include/internal/pycore_object_stack.h b/Include/internal/pycore_object_stack.h
index 1dc1c15..d042be2 100644
--- a/Include/internal/pycore_object_stack.h
+++ b/Include/internal/pycore_object_stack.h
@@ -1,6 +1,8 @@
 #ifndef Py_INTERNAL_OBJECT_STACK_H
 #define Py_INTERNAL_OBJECT_STACK_H
 
+#include "pycore_freelist.h"        // _PyFreeListState
+
 #ifdef __cplusplus
 extern "C" {
 #endif
@@ -74,6 +76,10 @@ _PyObjectStack_Pop(_PyObjectStack *stack)
     return obj;
 }
 
+// Merge src into dst, leaving src empty
+extern void
+_PyObjectStack_Merge(_PyObjectStack *dst, _PyObjectStack *src);
+
 // Remove all items from the stack
 extern void
 _PyObjectStack_Clear(_PyObjectStack *stack);
diff --git a/Include/internal/pycore_tstate.h b/Include/internal/pycore_tstate.h
index 472fa08..77a1dc5 100644
--- a/Include/internal/pycore_tstate.h
+++ b/Include/internal/pycore_tstate.h
@@ -10,6 +10,7 @@ extern "C" {
 
 #include "pycore_freelist.h"      // struct _Py_freelist_state
 #include "pycore_mimalloc.h"      // struct _mimalloc_thread_state
+#include "pycore_brc.h"           // struct _brc_thread_state
 
 
 // Every PyThreadState is actually allocated as a _PyThreadStateImpl. The
@@ -22,6 +23,7 @@ typedef struct _PyThreadStateImpl {
 #ifdef Py_GIL_DISABLED
     struct _mimalloc_thread_state mimalloc;
     struct _Py_freelist_state freelist_state;
+    struct _brc_thread_state brc;
 #endif
 
 } _PyThreadStateImpl;