Author: Stefan Beyer <[email protected]>
Branch: cpyext-gc-trialdeletion
Changeset: r91867:f8d7bb5f29b6
Date: 2017-07-14 13:47 +0200
http://bitbucket.org/pypy/pypy/changeset/f8d7bb5f29b6/
Log: Implemented flags for concurrent cycle deletion (Bacon and Rajan
2001) with overflow handling for refcount and removed unnecessary
code
diff --git a/pypy/module/cpyext/include/object.h
b/pypy/module/cpyext/include/object.h
--- a/pypy/module/cpyext/include/object.h
+++ b/pypy/module/cpyext/include/object.h
@@ -2,6 +2,7 @@
#define Py_OBJECT_H
#include <stdio.h>
+#include <math.h>
#ifdef __cplusplus
extern "C" {
@@ -9,10 +10,17 @@
#include "cpyext_object.h"
+int* foo;
#define PY_SSIZE_T_MAX ((Py_ssize_t)(((size_t)-1)>>1))
#define PY_SSIZE_T_MIN (-PY_SSIZE_T_MAX-1)
-#define Py_RETURN_NONE return Py_INCREF(Py_None), Py_None
+#define PY_REFCNT_FROM_PYPY (4L << ((long)(log(PY_SSIZE_T_MAX) / log(2) - 2)))
+#define PY_REFCNT_GREEN (4L << ((long)(log(PY_SSIZE_T_MAX) / log(2) - 6)))
+#define PY_REFCNT_OVERFLOW (1L << ((long)(log(PY_SSIZE_T_MAX) / log(2) - 6) /
2L - 1L))
+#define PY_REFCNT_MASK ((PY_REFCNT_OVERFLOW << 1L) - 1L)
+
+#define Py_RETURN_NONE return (((((PyObject *)(Py_None))->ob_refcnt &
PY_REFCNT_OVERFLOW) == 0) ? \
+ ((PyObject *)(Py_None))->ob_refcnt++ :
Py_IncRef((PyObject *)(Py_None))), Py_None
/*
CPython has this for backwards compatibility with really old extensions, and
now
@@ -26,26 +34,34 @@
#define PyVarObject_HEAD_INIT(type, size) \
PyObject_HEAD_INIT(type) size,
-// #ifdef PYPY_DEBUG_REFCOUNT
-// /* Slow version, but useful for debugging */
+#ifdef PYPY_DEBUG_REFCOUNT
+/* Slow version, but useful for debugging */
#define Py_INCREF(ob) (Py_IncRef((PyObject *)(ob)))
#define Py_DECREF(ob) (Py_DecRef((PyObject *)(ob)))
#define Py_XINCREF(ob) (Py_IncRef((PyObject *)(ob)))
#define Py_XDECREF(ob) (Py_DecRef((PyObject *)(ob)))
-// #else
-// /* Fast version */
-// #define Py_INCREF(ob) (((PyObject *)(ob))->ob_refcnt++)
-// #define Py_DECREF(op) \
-// do { \
-// if (--((PyObject *)(op))->ob_refcnt != 0) \
-// ; \
-// else \
-// _Py_Dealloc((PyObject *)(op)); \
-// } while (0)
-
-// #define Py_XINCREF(op) do { if ((op) == NULL) ; else Py_INCREF(op); } while
(0)
-// #define Py_XDECREF(op) do { if ((op) == NULL) ; else Py_DECREF(op); } while
(0)
-// #endif
+#else
+/* Fast version */
+#define Py_INCREF(ob)
\
+ do {
\
+ if (!(((PyObject *)(ob))->ob_refcnt & PY_REFCNT_OVERFLOW))
\
+ ((PyObject *)(ob))->ob_refcnt++;
\
+ else
\
+ Py_IncRef((PyObject *)(ob));
\
+ } while (0)
+#define Py_DECREF(ob)
\
+ do {
\
+ if (!(((PyObject *)(ob))->ob_refcnt & PY_REFCNT_GREEN) ||
\
+ (((PyObject *)(ob))->ob_refcnt & PY_REFCNT_OVERFLOW))
\
+ Py_DecRef((PyObject *)(ob));
\
+ else if (--((PyObject *)(ob))->ob_refcnt & PY_REFCNT_MASK)
\
+ ;
\
+ else if (!((PyObject *)(ob))->ob_refcnt & PY_REFCNT_FROM_PYPY)
\
+ _Py_Dealloc((PyObject *)(ob));
\
+ } while (0)
+#define Py_XINCREF(op) do { if ((op) == NULL) ; else Py_INCREF(op); } while (0)
+#define Py_XDECREF(op) do { if ((op) == NULL) ; else Py_DECREF(op); } while (0)
+#endif
#define Py_CLEAR(op) \
do { \
@@ -56,7 +72,8 @@
} \
} while (0)
-#define Py_REFCNT(ob) (((PyObject*)(ob))->ob_refcnt)
+#define Py_REFCNT(ob) ((((PyObject *)(ob))->ob_refcnt & PY_REFCNT_OVERFLOW ==
0) ? \
+ (((PyObject*)(ob))->ob_refcnt & PY_REFCNT_MASK) :
_Py_RefCnt_Overflow(ob))
#define Py_TYPE(ob) (((PyObject*)(ob))->ob_type)
#define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)
diff --git a/pypy/module/cpyext/object.py b/pypy/module/cpyext/object.py
--- a/pypy/module/cpyext/object.py
+++ b/pypy/module/cpyext/object.py
@@ -11,6 +11,7 @@
from pypy.module.cpyext.pyerrors import PyErr_NoMemory, PyErr_BadInternalCall
from pypy.objspace.std.typeobject import W_TypeObject
from pypy.interpreter.error import OperationError, oefmt
+from rpython.rlib.rawrefcount import REFCNT_MASK
import pypy.module.__builtin__.operation as operation
@@ -61,7 +62,7 @@
def _dealloc(space, obj):
# This frees an object after its refcount dropped to zero, so we
# assert that it is really zero here.
- assert obj.c_ob_refcnt == 0
+ assert obj.c_ob_refcnt & REFCNT_MASK == 0
pto = obj.c_ob_type
obj_voidp = rffi.cast(rffi.VOIDP, obj)
generic_cpy_call(space, pto.c_tp_free, obj_voidp)
diff --git a/pypy/module/cpyext/pyobject.py b/pypy/module/cpyext/pyobject.py
--- a/pypy/module/cpyext/pyobject.py
+++ b/pypy/module/cpyext/pyobject.py
@@ -270,6 +270,27 @@
hop.exception_cannot_occur()
return hop.inputconst(lltype.Bool, hop.s_result.const)
+def _decref(pyobj):
+ if pyobj.c_ob_refcnt & rawrefcount.REFCNT_OVERFLOW == 0:
+ pyobj.c_ob_refcnt -= 1
+ else:
+ if pyobj.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW:
+ pyobj.c_ob_refcnt -= 1
+ elif rawrefcount.overflow_sub(pyobj):
+ pyobj.c_ob_refcnt -= 1
+
+def _incref(pyobj):
+ if pyobj.c_ob_refcnt & rawrefcount.REFCNT_OVERFLOW == 0:
+ pyobj.c_ob_refcnt += 1
+ else:
+ if pyobj.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW:
+ pyobj.c_ob_refcnt += 1
+ rawrefcount.overflow_new(pyobj)
+ else:
+ rawrefcount.overflow_add(pyobj)
+
@specialize.ll()
def make_ref(space, obj, w_userdata=None):
"""Increment the reference counter of the PyObject and return it.
@@ -280,8 +301,7 @@
else:
pyobj = as_pyobj(space, obj, w_userdata)
if pyobj:
- assert pyobj.c_ob_refcnt > 0
- pyobj.c_ob_refcnt += 1
+ _incref(pyobj)
if not is_pyobj(obj):
keepalive_until_here(obj)
return pyobj
@@ -301,12 +321,10 @@
w_obj = obj
pyobj = as_pyobj(space, w_obj)
if pyobj:
- pyobj.c_ob_refcnt -= 1
- assert pyobj.c_ob_refcnt >= rawrefcount.REFCNT_FROM_PYPY
+ _decref(pyobj)
keepalive_until_here(w_obj)
return w_obj
-
@specialize.ll()
def incref(space, obj):
make_ref(space, obj)
@@ -316,20 +334,33 @@
if is_pyobj(obj):
obj = rffi.cast(PyObject, obj)
if obj:
- assert obj.c_ob_refcnt > 0
- obj.c_ob_refcnt -= 1
- if obj.c_ob_refcnt == 0 and \
+ _decref(obj)
+
+ if obj.c_ob_refcnt & rawrefcount.REFCNT_MASK == 0 and \
rawrefcount.get_trialdeletion_phase() != 1:
- debug_print("dealloc", obj)
- _Py_Dealloc(space, obj)
- elif obj.c_ob_refcnt == rawrefcount.REFCNT_FROM_PYPY:
- debug_print("dead", obj)
- else:
+ if obj.c_ob_refcnt & rawrefcount.REFCNT_FROM_PYPY == 0:
+ _Py_Dealloc(space, obj)
+ elif obj.c_ob_refcnt & rawrefcount.REFCNT_CLR_GREEN == 0:
if rawrefcount.get_trialdeletion_phase() == 0:
trial_delete(space, obj)
else:
get_w_obj_and_decref(space, obj)
[email protected]()
+def refcnt_overflow(space, obj):
+ if is_pyobj(obj):
+ pyobj = rffi.cast(PyObject, obj)
+ else:
+ pyobj = as_pyobj(space, obj, None)
+ if pyobj:
+ if (pyobj.c_ob_refcnt & rawrefcount.REFCNT_MASK ==
+ rawrefcount.REFCNT_OVERFLOW):
+ return rawrefcount.REFCNT_OVERFLOW
+ else:
+ return (pyobj.c_ob_refcnt & rawrefcount.REFCNT_MASK) \
+ + rawrefcount.overflow_get(pyobj)
+ return 0
+
def traverse(space, obj, visit):
from pypy.module.cpyext.api import generic_cpy_call
if obj.c_ob_type and obj.c_ob_type.c_tp_traverse:
@@ -343,7 +374,7 @@
@slot_function([PyObject, rffi.VOIDP], rffi.INT_real, error=-1)
def visit_decref(space, obj, args):
- obj.c_ob_refcnt = obj.c_ob_refcnt - 1
+ _decref(obj)
debug_print("visited dec", obj, "new refcnt", obj.c_ob_refcnt)
if (obj not in rawrefcount.get_visited()):
rawrefcount.add_visited(obj)
@@ -353,7 +384,7 @@
@slot_function([PyObject, rffi.VOIDP], rffi.INT_real, error=-1)
def visit_incref(space, obj, args):
- obj.c_ob_refcnt = obj.c_ob_refcnt + 1
+ _incref(obj)
debug_print("visited inc", obj, "new refcnt", obj.c_ob_refcnt)
if (obj not in rawrefcount.get_visited()):
rawrefcount.add_visited(obj)
@@ -364,6 +395,7 @@
@specialize.ll()
def trial_delete(space, obj):
if not obj.c_ob_type or not obj.c_ob_type.c_tp_traverse:
+ obj.c_ob_refcnt = obj.c_ob_refcnt | rawrefcount.REFCNT_CLR_GREEN
return
from pypy.module.cpyext.slotdefs import llslot
@@ -427,6 +459,10 @@
def Py_DecRef(space, obj):
decref(space, obj)
+@cpython_api([PyObject], lltype.SignedLongLong, error=CANNOT_FAIL)
+def _Py_RefCnt_Overflow(space, obj):
+ return refcnt_overflow(space, obj)
+
@cpython_api([PyObject], lltype.Void)
def _Py_NewReference(space, obj):
obj.c_ob_refcnt = 1
@@ -444,10 +480,6 @@
rawrefcount.mark_deallocating(w_marker_deallocating, obj)
generic_cpy_call(space, pto.c_tp_dealloc, obj)
-@cpython_api([PyObject], lltype.Void)
-def _Py_Mark(space, obj):
- rawrefcount.add_marked(obj)
-
@cpython_api([rffi.VOIDP], lltype.Signed, error=CANNOT_FAIL)
def _Py_HashPointer(space, ptr):
return rffi.cast(lltype.Signed, ptr)
diff --git a/pypy/module/cpyext/test/test_bytesobject.py
b/pypy/module/cpyext/test/test_bytesobject.py
--- a/pypy/module/cpyext/test/test_bytesobject.py
+++ b/pypy/module/cpyext/test/test_bytesobject.py
@@ -1,5 +1,6 @@
# encoding: utf-8
import pytest
+from rpython.rlib import rawrefcount
from rpython.rtyper.lltypesystem import rffi, lltype
from pypy.interpreter.error import OperationError
from pypy.module.cpyext.test.test_api import BaseApiTest, raises_w
@@ -9,8 +10,10 @@
PyString_ConcatAndDel, PyString_Format, PyString_InternFromString,
PyString_AsEncodedObject, PyString_AsDecodedObject, _PyString_Eq,
_PyString_Join)
-from pypy.module.cpyext.api import PyObjectP, PyObject, Py_ssize_tP,
generic_cpy_call
-from pypy.module.cpyext.pyobject import Py_DecRef, from_ref, make_ref
+from pypy.module.cpyext.api import (
+ PyObjectP, PyObject, Py_ssize_tP, generic_cpy_call)
+from pypy.module.cpyext.pyobject import (
+ Py_DecRef, Py_IncRef, _Py_RefCnt_Overflow, from_ref, make_ref)
from pypy.module.cpyext.object import PyObject_AsCharBuffer
from pypy.module.cpyext.api import PyTypeObjectPtr
@@ -498,9 +501,9 @@
ref = make_ref(space, space.wrap('abc'))
ptr = lltype.malloc(PyObjectP.TO, 1, flavor='raw')
ptr[0] = ref
- prev_refcnt = ref.c_ob_refcnt
+ prev_refcnt = ref.c_ob_refcnt & rawrefcount.REFCNT_MASK
PyString_Concat(space, ptr, space.wrap('def'))
- assert ref.c_ob_refcnt == prev_refcnt - 1
+ assert ref.c_ob_refcnt & rawrefcount.REFCNT_MASK == prev_refcnt - 1
assert space.str_w(from_ref(space, ptr[0])) == 'abcdef'
with pytest.raises(OperationError):
PyString_Concat(space, ptr, space.w_None)
@@ -536,9 +539,9 @@
w_text = space.wrap("text")
ref = make_ref(space, w_text)
- prev_refcnt = ref.c_ob_refcnt
+ prev_refcnt = ref.c_ob_refcnt & rawrefcount.REFCNT_MASK
assert PyObject_AsCharBuffer(space, ref, bufp, lenp) == 0
- assert ref.c_ob_refcnt == prev_refcnt
+ assert ref.c_ob_refcnt & rawrefcount.REFCNT_MASK == prev_refcnt
assert lenp[0] == 4
assert rffi.charp2str(bufp[0]) == 'text'
lltype.free(bufp, flavor='raw')
@@ -597,3 +600,53 @@
w_seq = space.wrap(['a', 'b'])
w_joined = _PyString_Join(space, w_sep, w_seq)
assert space.unwrap(w_joined) == 'a<sep>b'
+
+ def test_refcnt_overflow(self, space):
+ ref1 = make_ref(space, space.wrap('foo'))
+ ref1.c_ob_refcnt = rawrefcount.REFCNT_OVERFLOW - 1
+
+ Py_IncRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW
+
+ Py_IncRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+
+ Py_IncRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW + 2
+
+ Py_IncRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW + 3
+
+ Py_DecRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW + 2
+
+ Py_DecRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW + 1
+
+ Py_DecRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW
+ assert _Py_RefCnt_Overflow(space, ref1) \
+ == rawrefcount.REFCNT_OVERFLOW
+
+ Py_DecRef(space, ref1)
+ assert ref1.c_ob_refcnt & rawrefcount.REFCNT_MASK \
+ == rawrefcount.REFCNT_OVERFLOW - 1
diff --git a/rpython/rlib/rawrefcount.py b/rpython/rlib/rawrefcount.py
--- a/rpython/rlib/rawrefcount.py
+++ b/rpython/rlib/rawrefcount.py
@@ -4,7 +4,7 @@
# This is meant for pypy's cpyext module, but is a generally
# useful interface over our GC. XXX "pypy" should be removed here
#
-import sys, weakref, py
+import sys, weakref, py, math
from rpython.rtyper.lltypesystem import lltype, llmemory, rffi
from rpython.rlib.objectmodel import we_are_translated, specialize, not_rpython
from rpython.rtyper.extregistry import ExtRegistryEntry
@@ -12,8 +12,37 @@
from rpython.rlib import rgc
-REFCNT_FROM_PYPY = sys.maxint // 4 + 1
-REFCNT_FROM_PYPY_LIGHT = REFCNT_FROM_PYPY + (sys.maxint // 2 + 1)
+MAX_BIT = int(math.log(sys.maxint, 2))
+
+REFCNT_FROM_PYPY = 1 << MAX_BIT - 2
+REFCNT_FROM_PYPY_LIGHT = (1 << MAX_BIT - 1) + REFCNT_FROM_PYPY
+
+# Object either in Roots or Cycle Buffer (= Link-object exists)
+REFCNT_CYCLE_BUFFERED = 1 << MAX_BIT - 3
+
+# Offsets and sizes
+REFCNT_CLR_OFFS = MAX_BIT - 6
+REFCNT_CRC_OFFS = REFCNT_CLR_OFFS / 2
+REFCNT_BITS = REFCNT_CRC_OFFS - 1
+
+# Concurrent cycle collection colors
+REFCNT_CLR_BLACK = 0 << REFCNT_CLR_OFFS # In use or free (Default)
+REFCNT_CLR_GRAY = 1 << REFCNT_CLR_OFFS # Possible member of cycle
+REFCNT_CLR_WHITE = 2 << REFCNT_CLR_OFFS # Member of garbage cycle
+REFCNT_CLR_PURPLE = 3 << REFCNT_CLR_OFFS # Possible root of cycle
+REFCNT_CLR_GREEN = 4 << REFCNT_CLR_OFFS # Acyclic
+REFCNT_CLR_RED = 5 << REFCNT_CLR_OFFS # Cand cycle undergoing SIGMA-comp.
+REFCNT_CLR_ORANGE = 6 << REFCNT_CLR_OFFS # Cand cycle awaiting epoch boundary
+
+# Cyclic reference count with overflow bit
+REFCNT_CRC_OVERFLOW = 1 << REFCNT_CRC_OFFS + REFCNT_BITS
+REFCNT_CRC_MASK = (1 << REFCNT_CRC_OFFS + REFCNT_BITS + 1) - 1
+REFCNT_CRC = 1 < REFCNT_CRC_OFFS
+
+# True reference count with overflow bit
+REFCNT_OVERFLOW = 1 << REFCNT_BITS
+REFCNT_MASK = (1 << REFCNT_BITS + 1) - 1
+
RAWREFCOUNT_DEALLOC_TRIGGER = lltype.Ptr(lltype.FuncType([], lltype.Void))
@@ -24,25 +53,40 @@
return res
_trial_deletion_phase = 0
-_visited = []
-_marked = []
def set_trialdeletion_phase(value):
_trial_deletion_phase = value
def get_trialdeletion_phase():
return _trial_deletion_phase
+
+_visited = []
+
def add_visited(obj):
_visited.append(obj)
def get_visited():
return _visited
def clear_visited():
del _visited[:]
-def add_marked(obj):
- _marked.append(obj)
-def get_marked():
- return marked
-def clear_marked():
- del _marked[:]
+
+_refcount_overflow = dict()
+
+# TODO: if object moves, address changes!
+def overflow_new(obj):
+ _refcount_overflow[id(obj)] = 0
+def overflow_add(obj):
+ _refcount_overflow[id(obj)] += 1
+def overflow_sub(obj):
+ c = _refcount_overflow[id(obj)]
+ if c > 0:
+ _refcount_overflow[id(obj)] = c - 1
+ return False
+ else:
+ _refcount_overflow.pop(id(obj))
+ return True
+def overflow_get(obj):
+ return _refcount_overflow[id(obj)]
+
+# TODO: _cyclic_refcount_overflow = dict()
@not_rpython
def init(dealloc_trigger_callback=None):
@@ -142,7 +186,8 @@
wr_p_list = []
new_p_list = []
for ob in reversed(_p_list):
- if ob.c_ob_refcnt not in (REFCNT_FROM_PYPY, REFCNT_FROM_PYPY_LIGHT):
+ if ob.c_ob_refcnt & REFCNT_MASK > 0 \
+ or ob.c_ob_refcnt & REFCNT_FROM_PYPY == 0:
new_p_list.append(ob)
else:
p = detach(ob, wr_p_list)
@@ -175,7 +220,8 @@
if ob.c_ob_refcnt >= REFCNT_FROM_PYPY_LIGHT:
ob.c_ob_refcnt -= REFCNT_FROM_PYPY_LIGHT
ob.c_ob_pypy_link = 0
- if ob.c_ob_refcnt == 0:
+ if ob.c_ob_refcnt & REFCNT_MASK == 0 \
+ and ob.c_ob_refcnt < REFCNT_FROM_PYPY:
lltype.free(ob, flavor='raw',
track_allocation=track_allocation)
else:
@@ -183,8 +229,9 @@
assert ob.c_ob_refcnt < int(REFCNT_FROM_PYPY_LIGHT * 0.99)
ob.c_ob_refcnt -= REFCNT_FROM_PYPY
ob.c_ob_pypy_link = 0
- if ob.c_ob_refcnt == 0:
- ob.c_ob_refcnt = 1
+ if ob.c_ob_refcnt & REFCNT_MASK == 0 \
+ and ob.c_ob_refcnt < REFCNT_FROM_PYPY:
+ ob.c_ob_refcnt += 1
_d_list.append(ob)
return None
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
