Armin Rigo avatar Armin Rigo committed 99168b9

Move the 'rpython.rtyper.memory' subpackage to simply 'rpython.memory'.

Comments (0)

Files changed (112)

pypy/doc/garbage_collection.rst

 Two arenas of equal size, with only one arena in use and getting filled
 with new objects.  When the arena is full, the live objects are copied
 into the other arena using Cheney's algorithm.  The old arena is then
-cleared.  See `rpython/rtyper/memory/gc/semispace.py`_.
+cleared.  See `rpython/memory/gc/semispace.py`_.
 
 On Unix the clearing is done by reading ``/dev/zero`` into the arena,
 which is extremely memory efficient at least on Linux: it lets the
 Generational GC
 ---------------
 
-This is a two-generations GC.  See `rpython/rtyper/memory/gc/generation.py`_.
+This is a two-generations GC.  See `rpython/memory/gc/generation.py`_.
 
 It is implemented as a subclass of the Semispace copying collector.  It
 adds a nursery, which is a chunk of the current semispace.  Its size is
 Each generation is collected much less often than the previous one.  The
 division of the generations is slightly more complicated than just
 nursery / semispace / external; see the diagram at the start of the
-source code, in `rpython/rtyper/memory/gc/hybrid.py`_.
+source code, in `rpython/memory/gc/hybrid.py`_.
 
 Mark & Compact GC
 -----------------
   to the old stage. The dying case 2 objects are immediately freed.
 
 - The old stage is an area of memory containing old (small) objects.  It
-  is handled by `rpython/rtyper/memory/gc/minimarkpage.py`_.  It is organized
+  is handled by `rpython/memory/gc/minimarkpage.py`_.  It is organized
   as "arenas" of 256KB or 512KB, subdivided into "pages" of 4KB or 8KB.
   Each page can either be free, or contain small objects of all the same
   size.  Furthermore at any point in time each object location can be

pypy/doc/index.rst

 `rpython/rtyper/ootypesystem/`_    the `object-oriented type system`_
                                    for OO backends
 
-`rpython/rtyper/memory/`_          the `garbage collector`_ construction
+`rpython/memory/`_                 the `garbage collector`_ construction
                                    framework
 
 `rpython/translator/`_             translation_ backends and support code

rpython/jit/backend/arm/regalloc.py

             classptr = y_val
             # here, we have to go back from 'classptr' to the value expected
             # from reading the 16 bits in the object header
-            from rpython.rtyper.memory.gctypelayout import GCData
+            from rpython.memory.gctypelayout import GCData
             sizeof_ti = rffi.sizeof(GCData.TYPE_INFO)
             type_info_group = llop.gc_get_type_info_group(llmemory.Address)
             type_info_group = rffi.cast(lltype.Signed, type_info_group)

rpython/jit/backend/llsupport/gc.py

 from rpython.jit.backend.llsupport.descr import get_array_descr
 from rpython.jit.backend.llsupport.descr import get_call_descr
 from rpython.jit.backend.llsupport.rewrite import GcRewriterAssembler
-from rpython.rtyper.memory.gctransform import asmgcroot
+from rpython.memory.gctransform import asmgcroot
 
 # ____________________________________________________________
 
     def _make_layoutbuilder(self):
         # make a TransformerLayoutBuilder and save it on the translator
         # where it can be fished and reused by the FrameworkGCTransformer
-        from rpython.rtyper.memory.gctransform import framework
+        from rpython.memory.gctransform import framework
         translator = self.translator
         self.layoutbuilder = framework.TransformerLayoutBuilder(translator)
         self.layoutbuilder.delay_encoding()
         self.gcrootmap.add_jit2gc_hooks(translator._jit2gc)
 
     def _setup_gcclass(self):
-        from rpython.rtyper.memory.gcheader import GCHeaderBuilder
+        from rpython.memory.gcheader import GCHeaderBuilder
         self.GCClass = self.layoutbuilder.GCClass
         self.moving_gc = self.GCClass.moving_gc
         self.HDRPTR = lltype.Ptr(self.GCClass.HDR)
         self.write_barrier_descr = WriteBarrierDescr(self)
 
     def _make_functions(self, really_not_translated):
-        from rpython.rtyper.memory.gctypelayout import check_typeid
+        from rpython.memory.gctypelayout import check_typeid
         llop1 = self.llop1
         (self.standard_array_basesize, _, self.standard_array_length_ofs) = \
              symbolic.get_array_token(lltype.GcArray(lltype.Signed),
                                [lltype.Signed] * 2)
 
     def _bh_malloc(self, sizedescr):
-        from rpython.rtyper.memory.gctypelayout import check_typeid
+        from rpython.memory.gctypelayout import check_typeid
         llop1 = self.llop1
         type_id = llop.extract_ushort(llgroup.HALFWORD, sizedescr.tid)
         check_typeid(type_id)
                                                False, False, False)
 
     def _bh_malloc_array(self, num_elem, arraydescr):
-        from rpython.rtyper.memory.gctypelayout import check_typeid
+        from rpython.memory.gctypelayout import check_typeid
         llop1 = self.llop1
         type_id = llop.extract_ushort(llgroup.HALFWORD, arraydescr.tid)
         check_typeid(type_id)

rpython/jit/backend/llsupport/test/test_symbolic.py

 import py
 from rpython.jit.backend.llsupport.symbolic import *
 from rpython.rtyper.lltypesystem import lltype, rffi
-from rpython.rtyper.memory.lltypelayout import convert_offset_to_int
+from rpython.memory.lltypelayout import convert_offset_to_int
 
 
 WORD = rffi.sizeof(lltype.Signed)

rpython/jit/backend/x86/assembler.py

     @rgc.no_collect
     def _release_gil_asmgcc(css):
         # similar to trackgcroot.py:pypy_asm_stackwalk, first part
-        from rpython.rtyper.memory.gctransform import asmgcroot
+        from rpython.memory.gctransform import asmgcroot
         new = rffi.cast(asmgcroot.ASM_FRAMEDATA_HEAD_PTR, css)
         next = asmgcroot.gcrootanchor.next
         new.next = next
         if after:
             after()
         # similar to trackgcroot.py:pypy_asm_stackwalk, second part
-        from rpython.rtyper.memory.gctransform import asmgcroot
+        from rpython.memory.gctransform import asmgcroot
         old = rffi.cast(asmgcroot.ASM_FRAMEDATA_HEAD_PTR, css)
         prev = old.prev
         next = old.next
             # from reading the half-word in the object header.  Note that
             # this half-word is at offset 0 on a little-endian machine;
             # it would be at offset 2 or 4 on a big-endian machine.
-            from rpython.rtyper.memory.gctypelayout import GCData
+            from rpython.memory.gctypelayout import GCData
             sizeof_ti = rffi.sizeof(GCData.TYPE_INFO)
             type_info_group = llop.gc_get_type_info_group(llmemory.Address)
             type_info_group = rffi.cast(lltype.Signed, type_info_group)
             # like %eax that would be destroyed by this call, *and* they are
             # used by arglocs for the *next* call, then trouble; for now we
             # will just push/pop them.
-            from rpython.rtyper.memory.gctransform import asmgcroot
+            from rpython.memory.gctransform import asmgcroot
             css = self._regalloc.close_stack_struct
             if css == 0:
                 use_words = (2 + max(asmgcroot.INDEX_OF_EBP,

rpython/memory/__init__.py

+#
Add a comment to this file

rpython/memory/gc/__init__.py

Empty file added.

rpython/memory/gc/base.py

+from rpython.rtyper.lltypesystem import lltype, llmemory, llarena, rffi
+from rpython.rtyper.lltypesystem.lloperation import llop
+from rpython.rlib.debug import ll_assert
+from rpython.memory.gcheader import GCHeaderBuilder
+from rpython.memory.support import DEFAULT_CHUNK_SIZE
+from rpython.memory.support import get_address_stack, get_address_deque
+from rpython.memory.support import AddressDict, null_address_dict
+from rpython.rtyper.lltypesystem.llmemory import NULL, raw_malloc_usage
+
+TYPEID_MAP = lltype.GcStruct('TYPEID_MAP', ('count', lltype.Signed),
+                             ('size', lltype.Signed),
+                             ('links', lltype.Array(lltype.Signed)))
+ARRAY_TYPEID_MAP = lltype.GcArray(lltype.Ptr(TYPEID_MAP))
+
+class GCBase(object):
+    _alloc_flavor_ = "raw"
+    moving_gc = False
+    needs_write_barrier = False
+    malloc_zero_filled = False
+    prebuilt_gc_objects_are_static_roots = True
+    object_minimal_size = 0
+    gcflag_extra = 0   # or a real GC flag that is always 0 when not collecting
+
+    def __init__(self, config, chunk_size=DEFAULT_CHUNK_SIZE,
+                 translated_to_c=True):
+        self.gcheaderbuilder = GCHeaderBuilder(self.HDR)
+        self.AddressStack = get_address_stack(chunk_size)
+        self.AddressDeque = get_address_deque(chunk_size)
+        self.AddressDict = AddressDict
+        self.null_address_dict = null_address_dict
+        self.config = config
+        assert isinstance(translated_to_c, bool)
+        self.translated_to_c = translated_to_c
+
+    def setup(self):
+        # all runtime mutable values' setup should happen here
+        # and in its overriden versions! for the benefit of test_transformed_gc
+        self.finalizer_lock_count = 0
+        self.run_finalizers = self.AddressDeque()
+
+    def post_setup(self):
+        # More stuff that needs to be initialized when the GC is already
+        # fully working.  (Only called by gctransform/framework for now.)
+        from rpython.memory.gc import env
+        self.DEBUG = env.read_from_env('PYPY_GC_DEBUG')
+
+    def _teardown(self):
+        pass
+
+    def can_malloc_nonmovable(self):
+        return not self.moving_gc
+
+    def can_optimize_clean_setarrayitems(self):
+        return True     # False in case of card marking
+
+    # The following flag enables costly consistency checks after each
+    # collection.  It is automatically set to True by test_gc.py.  The
+    # checking logic is translatable, so the flag can be set to True
+    # here before translation.  At run-time, if PYPY_GC_DEBUG is set,
+    # then it is also set to True.
+    DEBUG = False
+
+    def set_query_functions(self, is_varsize, has_gcptr_in_varsize,
+                            is_gcarrayofgcptr,
+                            getfinalizer,
+                            getlightfinalizer,
+                            offsets_to_gc_pointers,
+                            fixed_size, varsize_item_sizes,
+                            varsize_offset_to_variable_part,
+                            varsize_offset_to_length,
+                            varsize_offsets_to_gcpointers_in_var_part,
+                            weakpointer_offset,
+                            member_index,
+                            is_rpython_class,
+                            has_custom_trace,
+                            get_custom_trace,
+                            fast_path_tracing):
+        self.getfinalizer = getfinalizer
+        self.getlightfinalizer = getlightfinalizer
+        self.is_varsize = is_varsize
+        self.has_gcptr_in_varsize = has_gcptr_in_varsize
+        self.is_gcarrayofgcptr = is_gcarrayofgcptr
+        self.offsets_to_gc_pointers = offsets_to_gc_pointers
+        self.fixed_size = fixed_size
+        self.varsize_item_sizes = varsize_item_sizes
+        self.varsize_offset_to_variable_part = varsize_offset_to_variable_part
+        self.varsize_offset_to_length = varsize_offset_to_length
+        self.varsize_offsets_to_gcpointers_in_var_part = varsize_offsets_to_gcpointers_in_var_part
+        self.weakpointer_offset = weakpointer_offset
+        self.member_index = member_index
+        self.is_rpython_class = is_rpython_class
+        self.has_custom_trace = has_custom_trace
+        self.get_custom_trace = get_custom_trace
+        self.fast_path_tracing = fast_path_tracing
+
+    def get_member_index(self, type_id):
+        return self.member_index(type_id)
+
+    def set_root_walker(self, root_walker):
+        self.root_walker = root_walker
+
+    def write_barrier(self, newvalue, addr_struct):
+        pass
+
+    def size_gc_header(self, typeid=0):
+        return self.gcheaderbuilder.size_gc_header
+
+    def header(self, addr):
+        addr -= self.gcheaderbuilder.size_gc_header
+        return llmemory.cast_adr_to_ptr(addr, lltype.Ptr(self.HDR))
+
+    def _get_size_for_typeid(self, obj, typeid):
+        size = self.fixed_size(typeid)
+        if self.is_varsize(typeid):
+            lenaddr = obj + self.varsize_offset_to_length(typeid)
+            length = lenaddr.signed[0]
+            size += length * self.varsize_item_sizes(typeid)
+            size = llarena.round_up_for_allocation(size)
+            # XXX maybe we should parametrize round_up_for_allocation()
+            # per GC; if we do, we also need to fix the call in
+            # gctypelayout.encode_type_shape()
+        return size
+
+    def get_size(self, obj):
+        return self._get_size_for_typeid(obj, self.get_type_id(obj))
+
+    def get_size_incl_hash(self, obj):
+        return self.get_size(obj)
+
+    def malloc(self, typeid, length=0, zero=False):
+        """For testing.  The interface used by the gctransformer is
+        the four malloc_[fixed,var]size[_clear]() functions.
+        """
+        # Rules about fallbacks in case of missing malloc methods:
+        #  * malloc_fixedsize_clear() and malloc_varsize_clear() are mandatory
+        #  * malloc_fixedsize() and malloc_varsize() fallback to the above
+        # XXX: as of r49360, gctransformer.framework never inserts calls
+        # to malloc_varsize(), but always uses malloc_varsize_clear()
+
+        size = self.fixed_size(typeid)
+        needs_finalizer = bool(self.getfinalizer(typeid))
+        finalizer_is_light = bool(self.getlightfinalizer(typeid))
+        contains_weakptr = self.weakpointer_offset(typeid) >= 0
+        assert not (needs_finalizer and contains_weakptr)
+        if self.is_varsize(typeid):
+            assert not contains_weakptr
+            assert not needs_finalizer
+            itemsize = self.varsize_item_sizes(typeid)
+            offset_to_length = self.varsize_offset_to_length(typeid)
+            if zero or not hasattr(self, 'malloc_varsize'):
+                malloc_varsize = self.malloc_varsize_clear
+            else:
+                malloc_varsize = self.malloc_varsize
+            ref = malloc_varsize(typeid, length, size, itemsize,
+                                 offset_to_length)
+        else:
+            if zero or not hasattr(self, 'malloc_fixedsize'):
+                malloc_fixedsize = self.malloc_fixedsize_clear
+            else:
+                malloc_fixedsize = self.malloc_fixedsize
+            ref = malloc_fixedsize(typeid, size, needs_finalizer,
+                                   finalizer_is_light,
+                                   contains_weakptr)
+        # lots of cast and reverse-cast around...
+        return llmemory.cast_ptr_to_adr(ref)
+
+    def malloc_nonmovable(self, typeid, length=0, zero=False):
+        return self.malloc(typeid, length, zero)
+
+    def id(self, ptr):
+        return lltype.cast_ptr_to_int(ptr)
+
+    def can_move(self, addr):
+        return False
+
+    def set_max_heap_size(self, size):
+        raise NotImplementedError
+
+    def trace(self, obj, callback, arg):
+        """Enumerate the locations inside the given obj that can contain
+        GC pointers.  For each such location, callback(pointer, arg) is
+        called, where 'pointer' is an address inside the object.
+        Typically, 'callback' is a bound method and 'arg' can be None.
+        """
+        typeid = self.get_type_id(obj)
+        #
+        # First, look if we need more than the simple fixed-size tracing
+        if not self.fast_path_tracing(typeid):
+            #
+            # Yes.  Two cases: either we are just a GcArray(gcptr), for
+            # which we have a special case for performance, or we call
+            # the slow path version.
+            if self.is_gcarrayofgcptr(typeid):
+                length = (obj + llmemory.gcarrayofptr_lengthoffset).signed[0]
+                item = obj + llmemory.gcarrayofptr_itemsoffset
+                while length > 0:
+                    if self.points_to_valid_gc_object(item):
+                        callback(item, arg)
+                    item += llmemory.gcarrayofptr_singleitemoffset
+                    length -= 1
+                return
+            self._trace_slow_path(obj, callback, arg)
+        #
+        # Do the tracing on the fixed-size part of the object.
+        offsets = self.offsets_to_gc_pointers(typeid)
+        i = 0
+        while i < len(offsets):
+            item = obj + offsets[i]
+            if self.points_to_valid_gc_object(item):
+                callback(item, arg)
+            i += 1
+    trace._annspecialcase_ = 'specialize:arg(2)'
+
+    def _trace_slow_path(self, obj, callback, arg):
+        typeid = self.get_type_id(obj)
+        if self.has_gcptr_in_varsize(typeid):
+            item = obj + self.varsize_offset_to_variable_part(typeid)
+            length = (obj + self.varsize_offset_to_length(typeid)).signed[0]
+            offsets = self.varsize_offsets_to_gcpointers_in_var_part(typeid)
+            itemlength = self.varsize_item_sizes(typeid)
+            while length > 0:
+                j = 0
+                while j < len(offsets):
+                    itemobj = item + offsets[j]
+                    if self.points_to_valid_gc_object(itemobj):
+                        callback(itemobj, arg)
+                    j += 1
+                item += itemlength
+                length -= 1
+        if self.has_custom_trace(typeid):
+            generator = self.get_custom_trace(typeid)
+            item = llmemory.NULL
+            while True:
+                item = generator(obj, item)
+                if not item:
+                    break
+                if self.points_to_valid_gc_object(item):
+                    callback(item, arg)
+    _trace_slow_path._annspecialcase_ = 'specialize:arg(2)'
+
+    def trace_partial(self, obj, start, stop, callback, arg):
+        """Like trace(), but only walk the array part, for indices in
+        range(start, stop).  Must only be called if has_gcptr_in_varsize().
+        """
+        length = stop - start
+        typeid = self.get_type_id(obj)
+        if self.is_gcarrayofgcptr(typeid):
+            # a performance shortcut for GcArray(gcptr)
+            item = obj + llmemory.gcarrayofptr_itemsoffset
+            item += llmemory.gcarrayofptr_singleitemoffset * start
+            while length > 0:
+                if self.points_to_valid_gc_object(item):
+                    callback(item, arg)
+                item += llmemory.gcarrayofptr_singleitemoffset
+                length -= 1
+            return
+        ll_assert(self.has_gcptr_in_varsize(typeid),
+                  "trace_partial() on object without has_gcptr_in_varsize()")
+        item = obj + self.varsize_offset_to_variable_part(typeid)
+        offsets = self.varsize_offsets_to_gcpointers_in_var_part(typeid)
+        itemlength = self.varsize_item_sizes(typeid)
+        item += itemlength * start
+        while length > 0:
+            j = 0
+            while j < len(offsets):
+                itemobj = item + offsets[j]
+                if self.points_to_valid_gc_object(itemobj):
+                    callback(itemobj, arg)
+                j += 1
+            item += itemlength
+            length -= 1
+    trace_partial._annspecialcase_ = 'specialize:arg(4)'
+
+    def points_to_valid_gc_object(self, addr):
+        return self.is_valid_gc_object(addr.address[0])
+
+    def is_valid_gc_object(self, addr):
+        return (addr != NULL and
+                (not self.config.taggedpointers or
+                 llmemory.cast_adr_to_int(addr) & 1 == 0))
+
+    def enumerate_all_roots(self, callback, arg):
+        """For each root object, invoke callback(obj, arg).
+        'callback' should not be a bound method.
+        Note that this method is not suitable for actually doing the
+        collection in a moving GC, because you cannot write back a
+        modified address.  It is there only for inspection.
+        """
+        # overridden in some subclasses, for GCs which have an additional
+        # list of last generation roots
+        callback2, attrname = _convert_callback_formats(callback)    # :-/
+        setattr(self, attrname, arg)
+        self.root_walker.walk_roots(callback2, callback2, callback2)
+        self.run_finalizers.foreach(callback, arg)
+    enumerate_all_roots._annspecialcase_ = 'specialize:arg(1)'
+
+    def debug_check_consistency(self):
+        """To use after a collection.  If self.DEBUG is set, this
+        enumerates all roots and traces all objects to check if we didn't
+        accidentally free a reachable object or forgot to update a pointer
+        to an object that moved.
+        """
+        if self.DEBUG:
+            from rpython.rlib.objectmodel import we_are_translated
+            from rpython.memory.support import AddressDict
+            self._debug_seen = AddressDict()
+            self._debug_pending = self.AddressStack()
+            if not we_are_translated():
+                self.root_walker._walk_prebuilt_gc(self._debug_record)
+            self.enumerate_all_roots(GCBase._debug_callback, self)
+            pending = self._debug_pending
+            while pending.non_empty():
+                obj = pending.pop()
+                self.trace(obj, self._debug_callback2, None)
+            self._debug_seen.delete()
+            self._debug_pending.delete()
+
+    def _debug_record(self, obj):
+        seen = self._debug_seen
+        if not seen.contains(obj):
+            seen.add(obj)
+            self.debug_check_object(obj)
+            self._debug_pending.append(obj)
+    @staticmethod
+    def _debug_callback(obj, self):
+        self._debug_record(obj)
+    def _debug_callback2(self, pointer, ignored):
+        obj = pointer.address[0]
+        ll_assert(bool(obj), "NULL address from self.trace()")
+        self._debug_record(obj)
+
+    def debug_check_object(self, obj):
+        pass
+
+    def execute_finalizers(self):
+        self.finalizer_lock_count += 1
+        try:
+            while self.run_finalizers.non_empty():
+                if self.finalizer_lock_count > 1:
+                    # the outer invocation of execute_finalizers() will do it
+                    break
+                obj = self.run_finalizers.popleft()
+                finalizer = self.getfinalizer(self.get_type_id(obj))
+                finalizer(obj, llmemory.NULL)
+        finally:
+            self.finalizer_lock_count -= 1
+
+
+class MovingGCBase(GCBase):
+    moving_gc = True
+
+    def setup(self):
+        GCBase.setup(self)
+        self.objects_with_id = self.AddressDict()
+        self.id_free_list = self.AddressStack()
+        self.next_free_id = 1
+
+    def can_move(self, addr):
+        return True
+
+    def id(self, ptr):
+        # Default implementation for id(), assuming that "external" objects
+        # never move.  Overriden in the HybridGC.
+        obj = llmemory.cast_ptr_to_adr(ptr)
+
+        # is it a tagged pointer? or an external object?
+        if not self.is_valid_gc_object(obj) or self._is_external(obj):
+            return llmemory.cast_adr_to_int(obj)
+
+        # tagged pointers have ids of the form 2n + 1
+        # external objects have ids of the form 4n (due to word alignment)
+        # self._compute_id returns addresses of the form 2n + 1
+        # if we multiply by 2, we get ids of the form 4n + 2, thus we get no
+        # clashes
+        return llmemory.cast_adr_to_int(self._compute_id(obj)) * 2
+
+    def _next_id(self):
+        # return an id not currently in use (as an address instead of an int)
+        if self.id_free_list.non_empty():
+            result = self.id_free_list.pop()    # reuse a dead id
+        else:
+            # make up a fresh id number
+            result = llmemory.cast_int_to_adr(self.next_free_id)
+            self.next_free_id += 2    # only odd numbers, to make lltype
+                                      # and llmemory happy and to avoid
+                                      # clashes with real addresses
+        return result
+
+    def _compute_id(self, obj):
+        # look if the object is listed in objects_with_id
+        result = self.objects_with_id.get(obj)
+        if not result:
+            result = self._next_id()
+            self.objects_with_id.setitem(obj, result)
+        return result
+
+    def update_objects_with_id(self):
+        old = self.objects_with_id
+        new_objects_with_id = self.AddressDict(old.length())
+        old.foreach(self._update_object_id_FAST, new_objects_with_id)
+        old.delete()
+        self.objects_with_id = new_objects_with_id
+
+    def _update_object_id(self, obj, id, new_objects_with_id):
+        # safe version (used by subclasses)
+        if self.surviving(obj):
+            newobj = self.get_forwarding_address(obj)
+            new_objects_with_id.setitem(newobj, id)
+        else:
+            self.id_free_list.append(id)
+
+    def _update_object_id_FAST(self, obj, id, new_objects_with_id):
+        # unsafe version, assumes that the new_objects_with_id is large enough
+        if self.surviving(obj):
+            newobj = self.get_forwarding_address(obj)
+            new_objects_with_id.insertclean(newobj, id)
+        else:
+            self.id_free_list.append(id)
+
+
+def choose_gc_from_config(config):
+    """Return a (GCClass, GC_PARAMS) from the given config object.
+    """
+    if config.translation.gctransformer != "framework":
+        raise AssertionError("fix this test")
+
+    classes = {"semispace": "semispace.SemiSpaceGC",
+               "generation": "generation.GenerationGC",
+               "hybrid": "hybrid.HybridGC",
+               "minimark" : "minimark.MiniMarkGC",
+               }
+    try:
+        modulename, classname = classes[config.translation.gc].split('.')
+    except KeyError:
+        raise ValueError("unknown value for translation.gc: %r" % (
+            config.translation.gc,))
+    module = __import__("rpython.memory.gc." + modulename,
+                        globals(), locals(), [classname])
+    GCClass = getattr(module, classname)
+    return GCClass, GCClass.TRANSLATION_PARAMS
+
+def _convert_callback_formats(callback):
+    callback = getattr(callback, 'im_func', callback)
+    if callback not in _converted_callback_formats:
+        def callback2(gc, root):
+            obj = root.address[0]
+            ll_assert(bool(obj), "NULL address from walk_roots()")
+            callback(obj, getattr(gc, attrname))
+        attrname = '_callback2_arg%d' % len(_converted_callback_formats)
+        _converted_callback_formats[callback] = callback2, attrname
+    return _converted_callback_formats[callback]
+
+_convert_callback_formats._annspecialcase_ = 'specialize:memo'
+_converted_callback_formats = {}

rpython/memory/gc/env.py

+"""
+Utilities to get environ variables and platform-specific memory-related values.
+"""
+import os, sys
+from rpython.rlib.rarithmetic import r_uint
+from rpython.rlib.debug import debug_print, debug_start, debug_stop
+from rpython.rtyper.lltypesystem import lltype, rffi
+from rpython.rtyper.lltypesystem.lloperation import llop
+
+# ____________________________________________________________
+# Reading env vars.  Supports returning ints, uints or floats,
+# and in the first two cases accepts the suffixes B, KB, MB and GB
+# (lower case or upper case).
+
+def _read_float_and_factor_from_env(varname):
+    value = os.environ.get(varname)
+    if value:
+        if len(value) > 1 and value[-1] in 'bB':
+            value = value[:-1]
+        realvalue = value[:-1]
+        if value[-1] in 'kK':
+            factor = 1024
+        elif value[-1] in 'mM':
+            factor = 1024*1024
+        elif value[-1] in 'gG':
+            factor = 1024*1024*1024
+        else:
+            factor = 1
+            realvalue = value
+        try:
+            return (float(realvalue), factor)
+        except ValueError:
+            pass
+    return (0.0, 0)
+
+def read_from_env(varname):
+    value, factor = _read_float_and_factor_from_env(varname)
+    return int(value * factor)
+
+def read_uint_from_env(varname):
+    value, factor = _read_float_and_factor_from_env(varname)
+    return r_uint(value * factor)
+
+def read_float_from_env(varname):
+    value, factor = _read_float_and_factor_from_env(varname)
+    if factor != 1:
+        return 0.0
+    return value
+
+
+# ____________________________________________________________
+# Get the total amount of RAM installed in a system.
+# On 32-bit systems, it will try to return at most the addressable size.
+# If unknown, it will just return the addressable size, which
+# will be huge on 64-bit systems.
+
+if sys.maxint == 2147483647:    # 32-bit
+    if sys.platform.startswith('linux'):
+        addressable_size = float(2**32)     # 4GB
+    elif sys.platform == 'win32':
+        addressable_size = float(2**31)     # 2GB
+    else:
+        addressable_size = float(2**31 + 2**30)   # 3GB (compromise)
+else:
+    addressable_size = float(2**63)    # 64-bit
+
+
+def get_total_memory_linux(filename):
+    debug_start("gc-hardware")
+    result = -1.0
+    try:
+        fd = os.open(filename, os.O_RDONLY, 0644)
+        try:
+            buf = os.read(fd, 4096)
+        finally:
+            os.close(fd)
+    except OSError:
+        pass
+    else:
+        if buf.startswith('MemTotal:'):
+            start = _skipspace(buf, len('MemTotal:'))
+            stop = start
+            while stop < len(buf) and buf[stop].isdigit():
+                stop += 1
+            if start < stop:
+                result = float(buf[start:stop]) * 1024.0   # assume kB
+    if result < 0.0:
+        debug_print("get_total_memory() failed")
+        result = addressable_size
+    else:
+        debug_print("memtotal =", result)
+        if result > addressable_size:
+            result = addressable_size
+    debug_stop("gc-hardware")
+    return result
+get_total_memory_linux2 = get_total_memory_linux3 = get_total_memory_linux
+
+def get_total_memory_darwin(result):
+    debug_start("gc-hardware")
+    if result <= 0:
+        debug_print("get_total_memory() failed")
+        result = addressable_size
+    else:
+        debug_print("memtotal = ", result)
+        if result > addressable_size:
+            result = addressable_size
+    debug_stop("gc-hardware")
+    return result
+
+
+if sys.platform.startswith('linux'):
+    def get_total_memory():
+        return get_total_memory_linux2('/proc/meminfo')
+
+elif sys.platform == 'darwin':
+    def get_total_memory():
+        return get_total_memory_darwin(get_darwin_sysctl_signed('hw.memsize'))
+
+elif 'freebsd' in sys.platform:
+    def get_total_memory():
+        return get_total_memory_darwin(get_darwin_sysctl_signed('hw.usermem'))
+
+else:
+    def get_total_memory():
+        return addressable_size       # XXX implement me for other platforms
+
+
+# ____________________________________________________________
+# Estimation of the nursery size, based on the L2 cache.
+
+# ---------- Linux2 ----------
+
+def get_L2cache_linux2(filename="/proc/cpuinfo"):
+    debug_start("gc-hardware")
+    L2cache = sys.maxint
+    try:
+        fd = os.open(filename, os.O_RDONLY, 0644)
+        try:
+            data = []
+            while True:
+                buf = os.read(fd, 4096)
+                if not buf:
+                    break
+                data.append(buf)
+        finally:
+            os.close(fd)
+    except OSError:
+        pass
+    else:
+        data = ''.join(data)
+        linepos = 0
+        while True:
+            start = _findend(data, '\ncache size', linepos)
+            if start < 0:
+                break    # done
+            linepos = _findend(data, '\n', start)
+            if linepos < 0:
+                break    # no end-of-line??
+            # *** data[start:linepos] == "   : 2048 KB\n"
+            start = _skipspace(data, start)
+            if data[start] != ':':
+                continue
+            # *** data[start:linepos] == ": 2048 KB\n"
+            start = _skipspace(data, start + 1)
+            # *** data[start:linepos] == "2048 KB\n"
+            end = start
+            while '0' <= data[end] <= '9':
+                end += 1
+            # *** data[start:end] == "2048"
+            if start == end:
+                continue
+            number = int(data[start:end])
+            # *** data[end:linepos] == " KB\n"
+            end = _skipspace(data, end)
+            if data[end] not in ('K', 'k'):    # assume kilobytes for now
+                continue
+            number = number * 1024
+            # for now we look for the smallest of the L2 caches of the CPUs
+            if number < L2cache:
+                L2cache = number
+
+    debug_print("L2cache =", L2cache)
+    debug_stop("gc-hardware")
+
+    if L2cache < sys.maxint:
+        return L2cache
+    else:
+        # Print a top-level warning even in non-debug builds
+        llop.debug_print(lltype.Void,
+            "Warning: cannot find your CPU L2 cache size in /proc/cpuinfo")
+        return -1
+
+def _findend(data, pattern, pos):
+    pos = data.find(pattern, pos)
+    if pos < 0:
+        return -1
+    return pos + len(pattern)
+
+def _skipspace(data, pos):
+    while data[pos] in (' ', '\t'):
+        pos += 1
+    return pos
+
+# ---------- Darwin ----------
+
+sysctlbyname = rffi.llexternal('sysctlbyname',
+                               [rffi.CCHARP, rffi.VOIDP, rffi.SIZE_TP,
+                                rffi.VOIDP, rffi.SIZE_T],
+                               rffi.INT,
+                               sandboxsafe=True)
+
+def get_darwin_sysctl_signed(sysctl_name):
+    rval_p = lltype.malloc(rffi.LONGLONGP.TO, 1, flavor='raw')
+    try:
+        len_p = lltype.malloc(rffi.SIZE_TP.TO, 1, flavor='raw')
+        try:
+            size = rffi.sizeof(rffi.LONGLONG)
+            rval_p[0] = rffi.cast(rffi.LONGLONG, 0)
+            len_p[0] = rffi.cast(rffi.SIZE_T, size)
+            # XXX a hack for llhelper not being robust-enough
+            result = sysctlbyname(sysctl_name,
+                                  rffi.cast(rffi.VOIDP, rval_p),
+                                  len_p,
+                                  lltype.nullptr(rffi.VOIDP.TO),
+                                  rffi.cast(rffi.SIZE_T, 0))
+            rval = 0
+            if (rffi.cast(lltype.Signed, result) == 0 and
+                rffi.cast(lltype.Signed, len_p[0]) == size):
+                rval = rffi.cast(lltype.Signed, rval_p[0])
+                if rffi.cast(rffi.LONGLONG, rval) != rval_p[0]:
+                    rval = 0    # overflow!
+            return rval
+        finally:
+            lltype.free(len_p, flavor='raw')
+    finally:
+        lltype.free(rval_p, flavor='raw')
+
+
+def get_L2cache_darwin():
+    """Try to estimate the best nursery size at run-time, depending
+    on the machine we are running on.
+    """
+    debug_start("gc-hardware")
+    L2cache = get_darwin_sysctl_signed("hw.l2cachesize")
+    L3cache = get_darwin_sysctl_signed("hw.l3cachesize")
+    debug_print("L2cache =", L2cache)
+    debug_print("L3cache =", L3cache)
+    debug_stop("gc-hardware")
+
+    mangled = L2cache + L3cache
+
+    if mangled > 0:
+        return mangled
+    else:
+        # Print a top-level warning even in non-debug builds
+        llop.debug_print(lltype.Void,
+            "Warning: cannot find your CPU L2 cache size with sysctl()")
+        return -1
+
+
+# --------------------
+
+get_L2cache = globals().get('get_L2cache_' + sys.platform,
+                            lambda: -1)     # implement me for other platforms
+
+NURSERY_SIZE_UNKNOWN_CACHE = 1024*1024
+# arbitrary 1M. better than default of 131k for most cases
+# in case it didn't work
+
+def best_nursery_size_for_L2cache(L2cache):
+    # Heuristically, the best nursery size to choose is about half
+    # of the L2 cache.
+    if L2cache > 0:
+        return L2cache // 2
+    else:
+        return NURSERY_SIZE_UNKNOWN_CACHE
+
+def estimate_best_nursery_size():
+    """Try to estimate the best nursery size at run-time, depending
+    on the machine we are running on.  Linux code."""
+    L2cache = get_L2cache()
+    return best_nursery_size_for_L2cache(L2cache)

rpython/memory/gc/generation.py

+import sys
+from rpython.memory.gc.semispace import SemiSpaceGC
+from rpython.memory.gc.semispace import GCFLAG_EXTERNAL, GCFLAG_FORWARDED
+from rpython.memory.gc.semispace import GC_HASH_TAKEN_ADDR
+from rpython.memory.gc import env
+from rpython.rtyper.lltypesystem.llmemory import NULL, raw_malloc_usage
+from rpython.rtyper.lltypesystem import lltype, llmemory, llarena
+from rpython.rlib.objectmodel import free_non_gc_object
+from rpython.rlib.debug import ll_assert
+from rpython.rlib.debug import debug_print, debug_start, debug_stop
+from rpython.rlib.rarithmetic import intmask, LONG_BIT
+from rpython.rtyper.lltypesystem.lloperation import llop
+
+WORD = LONG_BIT // 8
+
+# The following flag is never set on young objects, i.e. the ones living
+# in the nursery.  It is initially set on all prebuilt and old objects,
+# and gets cleared by the write_barrier() when we write in them a
+# pointer to a young object.
+GCFLAG_NO_YOUNG_PTRS = SemiSpaceGC.first_unused_gcflag << 0
+
+# The following flag is set on some last-generation objects (== prebuilt
+# objects for GenerationGC, but see also HybridGC).  The flag is set
+# unless the object is already listed in 'last_generation_root_objects'.
+# When a pointer is written inside an object with GCFLAG_NO_HEAP_PTRS
+# set, the write_barrier clears the flag and adds the object to
+# 'last_generation_root_objects'.
+GCFLAG_NO_HEAP_PTRS = SemiSpaceGC.first_unused_gcflag << 1
+
+class GenerationGC(SemiSpaceGC):
+    """A basic generational GC: it's a SemiSpaceGC with an additional
+    nursery for young objects.  A write barrier is used to ensure that
+    old objects that contain pointers to young objects are recorded in
+    a list.
+    """
+    inline_simple_malloc = True
+    inline_simple_malloc_varsize = True
+    needs_write_barrier = True
+    prebuilt_gc_objects_are_static_roots = False
+    first_unused_gcflag = SemiSpaceGC.first_unused_gcflag << 2
+
+    # the following values override the default arguments of __init__ when
+    # translating to a real backend.
+    TRANSLATION_PARAMS = {'space_size': 8*1024*1024,     # 8 MB
+                          'nursery_size': 3*1024*1024,   # 3 MB
+                          'min_nursery_size': 48*1024,
+                          'auto_nursery_size': True}
+
+    nursery_hash_base = -1
+
+    def __init__(self, config,
+                 nursery_size=32*WORD,
+                 min_nursery_size=32*WORD,
+                 auto_nursery_size=False,
+                 space_size=1024*WORD,
+                 max_space_size=sys.maxint//2+1,
+                 **kwds):
+        SemiSpaceGC.__init__(self, config,
+                             space_size = space_size,
+                             max_space_size = max_space_size,
+                             **kwds)
+        assert min_nursery_size <= nursery_size <= space_size // 2
+        self.initial_nursery_size = nursery_size
+        self.auto_nursery_size = auto_nursery_size
+        self.min_nursery_size = min_nursery_size
+
+        # define nursery fields
+        self.reset_nursery()
+        self._setup_wb()
+
+        # compute the constant lower bounds for the attributes
+        # largest_young_fixedsize and largest_young_var_basesize.
+        # It is expected that most (or all) objects have a fixedsize
+        # that is much lower anyway.
+        sz = self.get_young_fixedsize(self.min_nursery_size)
+        self.lb_young_fixedsize = sz
+        sz = self.get_young_var_basesize(self.min_nursery_size)
+        self.lb_young_var_basesize = sz
+
+    def setup(self):
+        self.old_objects_pointing_to_young = self.AddressStack()
+        # ^^^ a list of addresses inside the old objects space; it
+        # may contain static prebuilt objects as well.  More precisely,
+        # it lists exactly the old and static objects whose
+        # GCFLAG_NO_YOUNG_PTRS bit is not set.
+        self.young_objects_with_weakrefs = self.AddressStack()
+
+        self.last_generation_root_objects = self.AddressStack()
+        self.young_objects_with_id = self.AddressDict()
+        SemiSpaceGC.setup(self)
+        self.set_nursery_size(self.initial_nursery_size)
+        # the GC is fully setup now.  The rest can make use of it.
+        if self.auto_nursery_size:
+            newsize = nursery_size_from_env()
+            #if newsize <= 0:
+            #    ---disabled--- just use the default value.
+            #    newsize = env.estimate_best_nursery_size()
+            if newsize > 0:
+                self.set_nursery_size(newsize)
+
+        self.reset_nursery()
+
+    def _teardown(self):
+        self.collect() # should restore last gen objects flags
+        SemiSpaceGC._teardown(self)
+
+    def reset_nursery(self):
+        self.nursery      = NULL
+        self.nursery_top  = NULL
+        self.nursery_free = NULL
+
+    def set_nursery_size(self, newsize):
+        debug_start("gc-set-nursery-size")
+        if newsize < self.min_nursery_size:
+            newsize = self.min_nursery_size
+        if newsize > self.space_size // 2:
+            newsize = self.space_size // 2
+
+        # Compute the new bounds for how large young objects can be
+        # (larger objects are allocated directly old).   XXX adjust
+        self.nursery_size = newsize
+        self.largest_young_fixedsize = self.get_young_fixedsize(newsize)
+        self.largest_young_var_basesize = self.get_young_var_basesize(newsize)
+        scale = 0
+        while (self.min_nursery_size << (scale+1)) <= newsize:
+            scale += 1
+        self.nursery_scale = scale
+        debug_print("nursery_size =", newsize)
+        debug_print("largest_young_fixedsize =",
+                    self.largest_young_fixedsize)
+        debug_print("largest_young_var_basesize =",
+                    self.largest_young_var_basesize)
+        debug_print("nursery_scale =", scale)
+        # we get the following invariant:
+        assert self.nursery_size >= (self.min_nursery_size << scale)
+
+        # Force a full collect to remove the current nursery whose size
+        # no longer matches the bounds that we just computed.  This must
+        # be done after changing the bounds, because it might re-create
+        # a new nursery (e.g. if it invokes finalizers).
+        self.semispace_collect()
+        debug_stop("gc-set-nursery-size")
+
+    @staticmethod
+    def get_young_fixedsize(nursery_size):
+        return nursery_size // 2 - 1
+
+    @staticmethod
+    def get_young_var_basesize(nursery_size):
+        return nursery_size // 4 - 1
+
+    @classmethod
+    def JIT_max_size_of_young_obj(cls):
+        min_nurs_size = cls.TRANSLATION_PARAMS['min_nursery_size']
+        return cls.get_young_fixedsize(min_nurs_size)
+
+    def is_in_nursery(self, addr):
+        ll_assert(llmemory.cast_adr_to_int(addr) & 1 == 0,
+                  "odd-valued (i.e. tagged) pointer unexpected here")
+        return self.nursery <= addr < self.nursery_top
+
+    def appears_to_be_in_nursery(self, addr):
+        # same as is_in_nursery(), but may return True accidentally if
+        # 'addr' is a tagged pointer with just the wrong value.
+        if not self.translated_to_c:
+            if not self.is_valid_gc_object(addr):
+                return False
+        return self.nursery <= addr < self.nursery_top
+
+    def malloc_fixedsize_clear(self, typeid, size,
+                               has_finalizer=False,
+                               is_finalizer_light=False,
+                               contains_weakptr=False):
+        if (has_finalizer or
+            (raw_malloc_usage(size) > self.lb_young_fixedsize and
+             raw_malloc_usage(size) > self.largest_young_fixedsize)):
+            # ^^^ we do two size comparisons; the first one appears redundant,
+            #     but it can be constant-folded if 'size' is a constant; then
+            #     it almost always folds down to False, which kills the
+            #     second comparison as well.
+            ll_assert(not contains_weakptr, "wrong case for mallocing weakref")
+            # "non-simple" case or object too big: don't use the nursery
+            return SemiSpaceGC.malloc_fixedsize_clear(self, typeid, size,
+                                                      has_finalizer,
+                                                      is_finalizer_light,
+                                                      contains_weakptr)
+        size_gc_header = self.gcheaderbuilder.size_gc_header
+        totalsize = size_gc_header + size
+        result = self.nursery_free
+        if raw_malloc_usage(totalsize) > self.nursery_top - result:
+            result = self.collect_nursery()
+        llarena.arena_reserve(result, totalsize)
+        # GCFLAG_NO_YOUNG_PTRS is never set on young objs
+        self.init_gc_object(result, typeid, flags=0)
+        self.nursery_free = result + totalsize
+        if contains_weakptr:
+            self.young_objects_with_weakrefs.append(result + size_gc_header)
+        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
+
+    def malloc_varsize_clear(self, typeid, length, size, itemsize,
+                             offset_to_length):
+        # Only use the nursery if there are not too many items.
+        if not raw_malloc_usage(itemsize):
+            too_many_items = False
+        else:
+            # The following line is usually constant-folded because both
+            # min_nursery_size and itemsize are constants (the latter
+            # due to inlining).
+            maxlength_for_minimal_nursery = (self.min_nursery_size // 4 //
+                                             raw_malloc_usage(itemsize))
+            
+            # The actual maximum length for our nursery depends on how
+            # many times our nursery is bigger than the minimal size.
+            # The computation is done in this roundabout way so that
+            # only the only remaining computation is the following
+            # shift.
+            maxlength = maxlength_for_minimal_nursery << self.nursery_scale
+            too_many_items = length > maxlength
+
+        if (too_many_items or
+            (raw_malloc_usage(size) > self.lb_young_var_basesize and
+             raw_malloc_usage(size) > self.largest_young_var_basesize)):
+            # ^^^ we do two size comparisons; the first one appears redundant,
+            #     but it can be constant-folded if 'size' is a constant; then
+            #     it almost always folds down to False, which kills the
+            #     second comparison as well.
+            return SemiSpaceGC.malloc_varsize_clear(self, typeid, length, size,
+                                                    itemsize, offset_to_length)
+        # with the above checks we know now that totalsize cannot be more
+        # than about half of the nursery size; in particular, the + and *
+        # cannot overflow
+        size_gc_header = self.gcheaderbuilder.size_gc_header
+        totalsize = size_gc_header + size + itemsize * length
+        result = self.nursery_free
+        if raw_malloc_usage(totalsize) > self.nursery_top - result:
+            result = self.collect_nursery()
+        llarena.arena_reserve(result, totalsize)
+        # GCFLAG_NO_YOUNG_PTRS is never set on young objs
+        self.init_gc_object(result, typeid, flags=0)
+        (result + size_gc_header + offset_to_length).signed[0] = length
+        self.nursery_free = result + llarena.round_up_for_allocation(totalsize)
+        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
+
+    # override the init_gc_object methods to change the default value of 'flags',
+    # used by objects that are directly created outside the nursery by the SemiSpaceGC.
+    # These objects must have the GCFLAG_NO_YOUNG_PTRS flag set immediately.
+    def init_gc_object(self, addr, typeid, flags=GCFLAG_NO_YOUNG_PTRS):
+        SemiSpaceGC.init_gc_object(self, addr, typeid, flags)
+
+    def init_gc_object_immortal(self, addr, typeid,
+                                flags=GCFLAG_NO_YOUNG_PTRS|GCFLAG_NO_HEAP_PTRS):
+        SemiSpaceGC.init_gc_object_immortal(self, addr, typeid, flags)
+
+    # flags exposed for the HybridGC subclass
+    GCFLAGS_FOR_NEW_YOUNG_OBJECTS = 0   # NO_YOUNG_PTRS never set on young objs
+    GCFLAGS_FOR_NEW_EXTERNAL_OBJECTS = (GCFLAG_EXTERNAL | GCFLAG_FORWARDED |
+                                        GCFLAG_NO_YOUNG_PTRS |
+                                        GC_HASH_TAKEN_ADDR)
+
+    # ____________________________________________________________
+    # Support code for full collections
+
+    def collect(self, gen=1):
+        if gen == 0:
+            self.collect_nursery()
+        else:
+            SemiSpaceGC.collect(self)
+
+    def semispace_collect(self, size_changing=False):
+        self.reset_young_gcflags() # we are doing a full collection anyway
+        self.weakrefs_grow_older()
+        self.ids_grow_older()
+        self.reset_nursery()
+        SemiSpaceGC.semispace_collect(self, size_changing)
+
+    def make_a_copy(self, obj, objsize):
+        tid = self.header(obj).tid
+        # During a full collect, all copied objects might implicitly come
+        # from the nursery.  In case they do, we must add this flag:
+        tid |= GCFLAG_NO_YOUNG_PTRS
+        return self._make_a_copy_with_tid(obj, objsize, tid)
+        # history: this was missing and caused an object to become old but without the
+        # flag set.  Such an object is bogus in the sense that the write_barrier doesn't
+        # work on it.  So it can eventually contain a ptr to a young object but we didn't
+        # know about it.  That ptr was not updated in the next minor collect... boom at
+        # the next usage.
+
+    def reset_young_gcflags(self):
+        # This empties self.old_objects_pointing_to_young, and puts the
+        # GCFLAG_NO_YOUNG_PTRS back on all these objects.  We could put
+        # the flag back more lazily but we expect this list to be short
+        # anyway, and it's much saner to stick to the invariant:
+        # non-young objects all have GCFLAG_NO_YOUNG_PTRS set unless
+        # they are listed in old_objects_pointing_to_young.
+        oldlist = self.old_objects_pointing_to_young
+        while oldlist.non_empty():
+            obj = oldlist.pop()
+            hdr = self.header(obj)
+            hdr.tid |= GCFLAG_NO_YOUNG_PTRS
+
+    def weakrefs_grow_older(self):
+        while self.young_objects_with_weakrefs.non_empty():
+            obj = self.young_objects_with_weakrefs.pop()
+            self.objects_with_weakrefs.append(obj)
+
+    def collect_roots(self):
+        """GenerationGC: collects all roots.
+           HybridGC: collects all roots, excluding the generation 3 ones.
+        """
+        # Warning!  References from static (and possibly gen3) objects
+        # are found by collect_last_generation_roots(), which must be
+        # called *first*!  If it is called after walk_roots(), then the
+        # HybridGC explodes if one of the _collect_root causes an object
+        # to be added to self.last_generation_root_objects.  Indeed, in
+        # this case, the newly added object is traced twice: once by
+        # collect_last_generation_roots() and once because it was added
+        # in self.rawmalloced_objects_to_trace.
+        self.collect_last_generation_roots()
+        self.root_walker.walk_roots(
+            SemiSpaceGC._collect_root,  # stack roots
+            SemiSpaceGC._collect_root,  # static in prebuilt non-gc structures
+            None)   # we don't need the static in prebuilt gc objects
+
+    def collect_last_generation_roots(self):
+        stack = self.last_generation_root_objects
+        self.last_generation_root_objects = self.AddressStack()
+        while stack.non_empty():
+            obj = stack.pop()
+            self.header(obj).tid |= GCFLAG_NO_HEAP_PTRS
+            # ^^^ the flag we just added will be removed immediately if
+            # the object still contains pointers to younger objects
+            self.trace(obj, self._trace_external_obj, obj)
+        stack.delete()
+
+    def _trace_external_obj(self, pointer, obj):
+        addr = pointer.address[0]
+        newaddr = self.copy(addr)
+        pointer.address[0] = newaddr
+        self.write_into_last_generation_obj(obj, newaddr)
+
+    # ____________________________________________________________
+    # Implementation of nursery-only collections
+
+    def collect_nursery(self):
+        if self.nursery_size > self.top_of_space - self.free:
+            # the semispace is running out, do a full collect
+            self.obtain_free_space(self.nursery_size)
+            ll_assert(self.nursery_size <= self.top_of_space - self.free,
+                         "obtain_free_space failed to do its job")
+        if self.nursery:
+            debug_start("gc-minor")
+            debug_print("--- minor collect ---")
+            debug_print("nursery:", self.nursery, "to", self.nursery_top)
+            # a nursery-only collection
+            scan = beginning = self.free
+            self.collect_oldrefs_to_nursery()
+            self.collect_roots_in_nursery()
+            scan = self.scan_objects_just_copied_out_of_nursery(scan)
+            # at this point, all static and old objects have got their
+            # GCFLAG_NO_YOUNG_PTRS set again by trace_and_drag_out_of_nursery
+            if self.young_objects_with_weakrefs.non_empty():
+                self.invalidate_young_weakrefs()
+            if self.young_objects_with_id.length() > 0:
+                self.update_young_objects_with_id()
+            # mark the nursery as free and fill it with zeroes again
+            llarena.arena_reset(self.nursery, self.nursery_size, 2)
+            debug_print("survived (fraction of the size):",
+                        float(scan - beginning) / self.nursery_size)
+            debug_stop("gc-minor")
+            #self.debug_check_consistency()   # -- quite expensive
+        else:
+            # no nursery - this occurs after a full collect, triggered either
+            # just above or by some previous non-nursery-based allocation.
+            # Grab a piece of the current space for the nursery.
+            self.nursery = self.free
+            self.nursery_top = self.nursery + self.nursery_size
+            self.free = self.nursery_top
+        self.nursery_free = self.nursery
+        # at this point we know that the nursery is empty
+        self.change_nursery_hash_base()
+        return self.nursery_free
+
+    def change_nursery_hash_base(self):
+        # The following should be enough to ensure that young objects
+        # tend to always get a different hash.  It also makes sure that
+        # nursery_hash_base is not a multiple of 4, to avoid collisions
+        # with the hash of non-young objects.
+        hash_base = self.nursery_hash_base
+        hash_base += self.nursery_size - 1
+        if (hash_base & 3) == 0:
+            hash_base -= 1
+        self.nursery_hash_base = intmask(hash_base)
+
+    # NB. we can use self.copy() to move objects out of the nursery,
+    # but only if the object was really in the nursery.
+
+    def collect_oldrefs_to_nursery(self):
+        # Follow the old_objects_pointing_to_young list and move the
+        # young objects they point to out of the nursery.
+        count = 0
+        oldlist = self.old_objects_pointing_to_young
+        while oldlist.non_empty():
+            count += 1
+            obj = oldlist.pop()
+            hdr = self.header(obj)
+            hdr.tid |= GCFLAG_NO_YOUNG_PTRS
+            self.trace_and_drag_out_of_nursery(obj)
+        debug_print("collect_oldrefs_to_nursery", count)
+
+    def collect_roots_in_nursery(self):
+        # we don't need to trace prebuilt GcStructs during a minor collect:
+        # if a prebuilt GcStruct contains a pointer to a young object,
+        # then the write_barrier must have ensured that the prebuilt
+        # GcStruct is in the list self.old_objects_pointing_to_young.
+        self.root_walker.walk_roots(
+            GenerationGC._collect_root_in_nursery,  # stack roots
+            GenerationGC._collect_root_in_nursery,  # static in prebuilt non-gc
+            None)                                   # static in prebuilt gc
+
+    def _collect_root_in_nursery(self, root):
+        obj = root.address[0]
+        if self.is_in_nursery(obj):
+            root.address[0] = self.copy(obj)
+
+    def scan_objects_just_copied_out_of_nursery(self, scan):
+        while scan < self.free:
+            curr = scan + self.size_gc_header()
+            self.trace_and_drag_out_of_nursery(curr)
+            scan += self.size_gc_header() + self.get_size_incl_hash(curr)
+        return scan
+
+    def trace_and_drag_out_of_nursery(self, obj):
+        """obj must not be in the nursery.  This copies all the
+        young objects it references out of the nursery.
+        """
+        self.trace(obj, self._trace_drag_out, None)
+
+    def _trace_drag_out(self, pointer, ignored):
+        if self.is_in_nursery(pointer.address[0]):
+            pointer.address[0] = self.copy(pointer.address[0])
+
+    # The code relies on the fact that no weakref can be an old object
+    # weakly pointing to a young object.  Indeed, weakrefs are immutable
+    # so they cannot point to an object that was created after it.
+    def invalidate_young_weakrefs(self):
+        # walk over the list of objects that contain weakrefs and are in the
+        # nursery.  if the object it references survives then update the
+        # weakref; otherwise invalidate the weakref
+        while self.young_objects_with_weakrefs.non_empty():
+            obj = self.young_objects_with_weakrefs.pop()
+            if not self.surviving(obj):
+                continue # weakref itself dies
+            obj = self.get_forwarding_address(obj)
+            offset = self.weakpointer_offset(self.get_type_id(obj))
+            pointing_to = (obj + offset).address[0]
+            if self.is_in_nursery(pointing_to):
+                if self.surviving(pointing_to):
+                    (obj + offset).address[0] = self.get_forwarding_address(
+                        pointing_to)
+                else:
+                    (obj + offset).address[0] = NULL
+                    continue    # no need to remember this weakref any longer
+            self.objects_with_weakrefs.append(obj)
+
+    # for the JIT: a minimal description of the write_barrier() method
+    # (the JIT assumes it is of the shape
+    #  "if addr_struct.int0 & JIT_WB_IF_FLAG: remember_young_pointer()")
+    JIT_WB_IF_FLAG = GCFLAG_NO_YOUNG_PTRS
+
+    def write_barrier(self, newvalue, addr_struct):
+         if self.header(addr_struct).tid & GCFLAG_NO_YOUNG_PTRS:
+            self.remember_young_pointer(addr_struct, newvalue)
+
+    def _setup_wb(self):
+        DEBUG = self.DEBUG
+        # The purpose of attaching remember_young_pointer to the instance
+        # instead of keeping it as a regular method is to help the JIT call it.
+        # Additionally, it makes the code in write_barrier() marginally smaller
+        # (which is important because it is inlined *everywhere*).
+        # For x86, there is also an extra requirement: when the JIT calls
+        # remember_young_pointer(), it assumes that it will not touch the SSE
+        # registers, so it does not save and restore them (that's a *hack*!).
+        def remember_young_pointer(addr_struct, addr):
+            #llop.debug_print(lltype.Void, "\tremember_young_pointer",
+            #                 addr_struct, "<-", addr)
+            if DEBUG:
+                ll_assert(not self.is_in_nursery(addr_struct),
+                          "nursery object with GCFLAG_NO_YOUNG_PTRS")
+            #
+            # What is important in this function is that it *must*
+            # clear the flag GCFLAG_NO_YOUNG_PTRS from 'addr_struct'
+            # if 'addr' is in the nursery.  It is ok if, accidentally,
+            # it also clears the flag in some more rare cases, like
+            # 'addr' being a tagged pointer whose value happens to be
+            # a large integer that fools is_in_nursery().
+            if self.appears_to_be_in_nursery(addr):
+                self.old_objects_pointing_to_young.append(addr_struct)
+                self.header(addr_struct).tid &= ~GCFLAG_NO_YOUNG_PTRS
+            self.write_into_last_generation_obj(addr_struct, addr)
+        remember_young_pointer._dont_inline_ = True
+        self.remember_young_pointer = remember_young_pointer
+
+    def write_into_last_generation_obj(self, addr_struct, addr):
+        objhdr = self.header(addr_struct)
+        if objhdr.tid & GCFLAG_NO_HEAP_PTRS:
+            if (self.is_valid_gc_object(addr) and
+                    not self.is_last_generation(addr)):
+                objhdr.tid &= ~GCFLAG_NO_HEAP_PTRS
+                self.last_generation_root_objects.append(addr_struct)
+    write_into_last_generation_obj._always_inline_ = True
+
+    def assume_young_pointers(self, addr_struct):
+        objhdr = self.header(addr_struct)
+        if objhdr.tid & GCFLAG_NO_YOUNG_PTRS:
+            self.old_objects_pointing_to_young.append(addr_struct)
+            objhdr.tid &= ~GCFLAG_NO_YOUNG_PTRS
+        if objhdr.tid & GCFLAG_NO_HEAP_PTRS:
+            objhdr.tid &= ~GCFLAG_NO_HEAP_PTRS
+            self.last_generation_root_objects.append(addr_struct)
+
+    def writebarrier_before_copy(self, source_addr, dest_addr,
+                                 source_start, dest_start, length):
+        """ This has the same effect as calling writebarrier over
+        each element in dest copied from source, except it might reset
+        one of the following flags a bit too eagerly, which means we'll have
+        a bit more objects to track, but being on the safe side.
+        """
+        source_hdr = self.header(source_addr)
+        dest_hdr = self.header(dest_addr)
+        if dest_hdr.tid & GCFLAG_NO_YOUNG_PTRS == 0:
+            return True
+        # ^^^ a fast path of write-barrier
+        if source_hdr.tid & GCFLAG_NO_YOUNG_PTRS == 0:
+            # there might be an object in source that is in nursery
+            self.old_objects_pointing_to_young.append(dest_addr)
+            dest_hdr.tid &= ~GCFLAG_NO_YOUNG_PTRS
+        if dest_hdr.tid & GCFLAG_NO_HEAP_PTRS:
+            if source_hdr.tid & GCFLAG_NO_HEAP_PTRS == 0:
+                # ^^^ equivalend of addr from source not being in last
+                #     gen
+                dest_hdr.tid &= ~GCFLAG_NO_HEAP_PTRS
+                self.last_generation_root_objects.append(dest_addr)
+        return True
+
+    def is_last_generation(self, obj):
+        # overridden by HybridGC
+        return (self.header(obj).tid & GCFLAG_EXTERNAL) != 0
+
+    def _compute_id(self, obj):
+        if self.is_in_nursery(obj):
+            result = self.young_objects_with_id.get(obj)
+            if not result:
+                result = self._next_id()
+                self.young_objects_with_id.setitem(obj, result)
+            return result
+        else:
+            return SemiSpaceGC._compute_id(self, obj)
+
+    def update_young_objects_with_id(self):
+        self.young_objects_with_id.foreach(self._update_object_id,
+                                           self.objects_with_id)
+        self.young_objects_with_id.clear()
+        # NB. the clear() also makes the dictionary shrink back to its
+        # minimal size, which is actually a good idea: a large, mostly-empty
+        # table is bad for the next call to 'foreach'.
+
+    def ids_grow_older(self):
+        self.young_objects_with_id.foreach(self._id_grow_older, None)
+        self.young_objects_with_id.clear()
+
+    def _id_grow_older(self, obj, id, ignored):
+        self.objects_with_id.setitem(obj, id)
+
+    def _compute_current_nursery_hash(self, obj):
+        return intmask(llmemory.cast_adr_to_int(obj) + self.nursery_hash_base)
+
+    def enumerate_all_roots(self, callback, arg):
+        self.last_generation_root_objects.foreach(callback, arg)
+        SemiSpaceGC.enumerate_all_roots(self, callback, arg)
+    enumerate_all_roots._annspecialcase_ = 'specialize:arg(1)'
+
+    def debug_check_object(self, obj):
+        """Check the invariants about 'obj' that should be true
+        between collections."""
+        SemiSpaceGC.debug_check_object(self, obj)
+        tid = self.header(obj).tid
+        if tid & GCFLAG_NO_YOUNG_PTRS:
+            ll_assert(not self.is_in_nursery(obj),
+                      "nursery object with GCFLAG_NO_YOUNG_PTRS")
+            self.trace(obj, self._debug_no_nursery_pointer, None)
+        elif not self.is_in_nursery(obj):
+            ll_assert(self._d_oopty.contains(obj),
+                      "missing from old_objects_pointing_to_young")
+        if tid & GCFLAG_NO_HEAP_PTRS:
+            ll_assert(self.is_last_generation(obj),
+                      "GCFLAG_NO_HEAP_PTRS on non-3rd-generation object")
+            self.trace(obj, self._debug_no_gen1or2_pointer, None)
+        elif self.is_last_generation(obj):
+            ll_assert(self._d_lgro.contains(obj),
+                      "missing from last_generation_root_objects")
+
+    def _debug_no_nursery_pointer(self, root, ignored):
+        ll_assert(not self.is_in_nursery(root.address[0]),
+                  "GCFLAG_NO_YOUNG_PTRS but found a young pointer")
+    def _debug_no_gen1or2_pointer(self, root, ignored):
+        target = root.address[0]
+        ll_assert(not target or self.is_last_generation(target),
+                  "GCFLAG_NO_HEAP_PTRS but found a pointer to gen1or2")
+
+    def debug_check_consistency(self):
+        if self.DEBUG:
+            self._d_oopty = self.old_objects_pointing_to_young.stack2dict()
+            self._d_lgro = self.last_generation_root_objects.stack2dict()
+            SemiSpaceGC.debug_check_consistency(self)
+            self._d_oopty.delete()
+            self._d_lgro.delete()
+            self.old_objects_pointing_to_young.foreach(
+                self._debug_check_flag_1, None)
+            self.last_generation_root_objects.foreach(
+                self._debug_check_flag_2, None)
+
+    def _debug_check_flag_1(self, obj, ignored):
+        ll_assert(not (self.header(obj).tid & GCFLAG_NO_YOUNG_PTRS),
+                  "unexpected GCFLAG_NO_YOUNG_PTRS")
+    def _debug_check_flag_2(self, obj, ignored):
+        ll_assert(not (self.header(obj).tid & GCFLAG_NO_HEAP_PTRS),
+                  "unexpected GCFLAG_NO_HEAP_PTRS")
+
+    def debug_check_can_copy(self, obj):
+        if self.is_in_nursery(obj):
+            pass    # it's ok to copy an object out of the nursery
+        else:
+            SemiSpaceGC.debug_check_can_copy(self, obj)
+
+
+# ____________________________________________________________
+
+def nursery_size_from_env():
+    return env.read_from_env('PYPY_GENERATIONGC_NURSERY')

rpython/memory/gc/hybrid.py

+import sys
+from rpython.memory.gc.semispace import SemiSpaceGC
+from rpython.memory.gc.generation import GenerationGC, WORD
+from rpython.memory.gc.semispace import GCFLAG_EXTERNAL, GCFLAG_FORWARDED
+from rpython.memory.gc.semispace import GCFLAG_HASHMASK
+from rpython.memory.gc.generation import GCFLAG_NO_YOUNG_PTRS
+from rpython.memory.gc.generation import GCFLAG_NO_HEAP_PTRS
+from rpython.memory.gc.semispace import GC_HASH_TAKEN_ADDR
+from rpython.memory.gc.semispace import GC_HASH_HASFIELD
+from rpython.rtyper.lltypesystem import lltype, llmemory, llarena
+from rpython.rtyper.lltypesystem.llmemory import raw_malloc_usage
+from rpython.rtyper.lltypesystem.lloperation import llop
+from rpython.rlib.debug import ll_assert, have_debug_prints
+from rpython.rlib.debug import debug_print, debug_start, debug_stop
+from rpython.rlib.rarithmetic import ovfcheck
+from rpython.rtyper.lltypesystem import rffi
+
+#   _______in the semispaces_________      ______external (non-moving)_____
+#  /                                 \    /                                \
+#                                          ___raw_malloc'ed__    _prebuilt_
+#  +----------------------------------+   /                  \  /          \
+#  |    | | | | |    |                |
+#  |    | | | | |    |                |    age < max      age == max
+#  |nur-|o|o|o|o|    |                |      +---+      +---+      +---+
+#  |sery|b|b|b|b|free|     empty      |      |obj|      |obj|      |obj|  
+#  |    |j|j|j|j|    |                |      +---+      +---+      +---+  
+#  |    | | | | |    |                |       +---+      +---+      +---+
+#  +-----------------+----------------+       |obj|      |obj|      |obj|
+#        age <= max                           +---+      +---+      +---+
+#            
+#  |gen1|------------- generation 2 -----------------|-----generation 3-----|
+#
+# Object lists:
+#   * gen2_rawmalloced_objects
+#   * gen3_rawmalloced_objects
+#   * old_objects_pointing_to_young: gen2or3 objs that point to gen1 objs
+#   * last_generation_root_objects: gen3 objs that point to gen1or2 objs
+#
+# How to tell the objects apart:
+#   * external:      tid & GCFLAG_EXTERNAL
+#   * gen1:          is_in_nursery(obj)
+#   * gen3:          (tid & (GCFLAG_EXTERNAL|GCFLAG_AGE_MASK)) ==
+#                           (GCFLAG_EXTERNAL|GCFLAG_AGE_MAX)
+#
+# Some invariants:
+#   * gen3 are either GCFLAG_NO_HEAP_PTRS or in 'last_generation_root_objects'
+#   * between collections, GCFLAG_UNVISITED set exactly for gen2_rawmalloced
+#
+# A malloc_varsize() of large objects returns objects that are external
+# but initially of generation 2.  Old objects from the semispaces are
+# moved to external objects directly as generation 3.
+
+# The "age" of an object is the number of times it survived a full
+# collections, without counting the step that moved it out of the nursery.
+# When a semispace-based object would grow older than MAX_SEMISPACE_AGE,
+# it is instead copied to a nonmoving location.  For example, a value of 3
+# ensures that an object is copied at most 5 times in total: from the
+# nursery to the semispace, then three times between the two spaces,
+# then one last time to a nonmoving location.
+MAX_SEMISPACE_AGE = 3
+
+GCFLAG_UNVISITED = GenerationGC.first_unused_gcflag << 0
+_gcflag_next_bit = GenerationGC.first_unused_gcflag << 1
+GCFLAG_AGE_ONE   = _gcflag_next_bit
+GCFLAG_AGE_MAX   = _gcflag_next_bit * MAX_SEMISPACE_AGE
+GCFLAG_AGE_MASK  = 0
+while GCFLAG_AGE_MASK < GCFLAG_AGE_MAX:
+    GCFLAG_AGE_MASK |= _gcflag_next_bit
+    _gcflag_next_bit <<= 1
+
+# The 3rd generation objects are only collected after the following
+# number of calls to semispace_collect():
+GENERATION3_COLLECT_THRESHOLD = 20
+
+class HybridGC(GenerationGC):
+    """A two-generations semi-space GC like the GenerationGC,
+    except that objects above a certain size are handled separately:
+    they are allocated via raw_malloc/raw_free in a mark-n-sweep fashion.
+    """
+    first_unused_gcflag = _gcflag_next_bit
+    prebuilt_gc_objects_are_static_roots = True
+
+    # the following values override the default arguments of __init__ when
+    # translating to a real backend.
+    TRANSLATION_PARAMS = GenerationGC.TRANSLATION_PARAMS.copy()
+    TRANSLATION_PARAMS['large_object'] = 6*1024    # XXX adjust
+    TRANSLATION_PARAMS['large_object_gcptrs'] = 31*1024    # XXX adjust
+    TRANSLATION_PARAMS['min_nursery_size'] = 128*1024
+    # condition: large_object <= large_object_gcptrs < min_nursery_size/4
+
+    def __init__(self, *args, **kwds):
+        large_object = kwds.pop('large_object', 6*WORD)
+        large_object_gcptrs = kwds.pop('large_object_gcptrs', 8*WORD)
+        self.generation3_collect_threshold = kwds.pop(
+            'generation3_collect_threshold', GENERATION3_COLLECT_THRESHOLD)
+        GenerationGC.__init__(self, *args, **kwds)
+
+        # Objects whose total size is at least 'large_object' bytes are
+        # allocated separately in a mark-n-sweep fashion.  If the object
+        # has GC pointers in its varsized part, we use instead the
+        # higher limit 'large_object_gcptrs'.  The idea is that
+        # separately allocated objects are allocated immediately "old"
+        # and it's not good to have too many pointers from old to young
+        # objects.
+
+        # In this class, we assume that the 'large_object' limit is not
+        # very high, so that all objects that wouldn't easily fit in the
+        # nursery are considered large by this limit.  This is the
+        # meaning of the 'assert' below.
+        self.nonlarge_max = large_object - 1
+        self.nonlarge_gcptrs_max = large_object_gcptrs - 1
+        assert self.nonlarge_gcptrs_max <= self.lb_young_var_basesize
+        assert self.nonlarge_max <= self.nonlarge_gcptrs_max
+
+    def setup(self):
+        self.large_objects_collect_trigger = self.param_space_size
+        self._initial_trigger = self.large_objects_collect_trigger
+        self.rawmalloced_objects_to_trace = self.AddressStack()
+        self.count_semispaceonly_collects = 0
+
+        self.gen2_rawmalloced_objects = self.AddressStack()
+        self.gen3_rawmalloced_objects = self.AddressStack()
+        GenerationGC.setup(self)
+
+    def set_max_heap_size(self, size):
+        raise NotImplementedError
+
+    # NB. to simplify the code, only varsized objects can be considered
+    # 'large'.
+
+    def malloc_varsize_clear(self, typeid, length, size, itemsize,
+                             offset_to_length):
+        size_gc_header = self.gcheaderbuilder.size_gc_header
+        nonvarsize = size_gc_header + size
+
+        # Compute the maximal length that makes the object still
+        # below 'nonlarge_max'.  All the following logic is usually
+        # constant-folded because self.nonlarge_max, size and itemsize
+        # are all constants (the arguments are constant due to
+        # inlining) and self.has_gcptr_in_varsize() is constant-folded.
+        if self.has_gcptr_in_varsize(typeid):
+            nonlarge_max = self.nonlarge_gcptrs_max
+        else:
+            nonlarge_max = self.nonlarge_max
+
+        if not raw_malloc_usage(itemsize):
+            too_many_items = raw_malloc_usage(nonvarsize) > nonlarge_max
+        else:
+            maxlength = nonlarge_max - raw_malloc_usage(nonvarsize)
+            maxlength = maxlength // raw_malloc_usage(itemsize)
+            too_many_items = length > maxlength
+
+        if not too_many_items:
+            # With the above checks we know now that totalsize cannot be more
+            # than 'nonlarge_max'; in particular, the + and * cannot overflow.
+            # Let's try to fit the object in the nursery.
+            totalsize = nonvarsize + itemsize * length
+            result = self.nursery_free
+            if raw_malloc_usage(totalsize) <= self.nursery_top - result:
+                llarena.arena_reserve(result, totalsize)
+                # GCFLAG_NO_YOUNG_PTRS is never set on young objs
+                self.init_gc_object(result, typeid, flags=0)
+                (result + size_gc_header + offset_to_length).signed[0] = length
+                self.nursery_free = result + llarena.round_up_for_allocation(
+                    totalsize)
+                return llmemory.cast_adr_to_ptr(result+size_gc_header,
+                                                llmemory.GCREF)
+        return self.malloc_varsize_slowpath(typeid, length)
+
+    def malloc_varsize_slowpath(self, typeid, length, force_nonmovable=False):
+        # For objects that are too large, or when the nursery is exhausted.
+        # In order to keep malloc_varsize_clear() as compact as possible,
+        # we recompute what we need in this slow path instead of passing
+        # it all as function arguments.
+        size_gc_header = self.gcheaderbuilder.size_gc_header
+        nonvarsize = size_gc_header + self.fixed_size(typeid)
+        itemsize = self.varsize_item_sizes(typeid)
+        offset_to_length = self.varsize_offset_to_length(typeid)
+        try:
+            varsize = ovfcheck(itemsize * length)
+            totalsize = ovfcheck(nonvarsize + varsize)
+        except OverflowError:
+            raise MemoryError()
+        if self.has_gcptr_in_varsize(typeid):
+            nonlarge_max = self.nonlarge_gcptrs_max
+        else:
+            nonlarge_max = self.nonlarge_max
+        if force_nonmovable or raw_malloc_usage(totalsize) > nonlarge_max:
+            result = self.malloc_varsize_marknsweep(totalsize)
+            flags = self.GCFLAGS_FOR_NEW_EXTERNAL_OBJECTS | GCFLAG_UNVISITED
+        else:
+            result = self.malloc_varsize_collecting_nursery(totalsize)
+            flags = self.GCFLAGS_FOR_NEW_YOUNG_OBJECTS
+        self.init_gc_object(result, typeid, flags)
+        (result + size_gc_header + offset_to_length).signed[0] = length
+        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
+
+    malloc_varsize_slowpath._dont_inline_ = True
+
+    def malloc_varsize_nonmovable(self, typeid, length):
+        return self.malloc_varsize_slowpath(typeid, length, True)
+
+    def malloc_nonmovable(self, typeid, length, zero):
+        # helper for testing, same as GCBase.malloc
+        if self.is_varsize(typeid):
+            gcref = self.malloc_varsize_slowpath(typeid, length, True)
+        else:
+            raise NotImplementedError("Not supported")
+        return llmemory.cast_ptr_to_adr(gcref)
+
+    def can_move(self, addr):
+        tid = self.header(addr).tid
+        return not (tid & GCFLAG_EXTERNAL)
+
+    def malloc_varsize_collecting_nursery(self, totalsize):
+        result = self.collect_nursery()
+        ll_assert(raw_malloc_usage(totalsize) <= self.nursery_top - result,
+                  "not enough room in malloc_varsize_collecting_nursery()")
+        llarena.arena_reserve(result, totalsize)
+        self.nursery_free = result + llarena.round_up_for_allocation(
+            totalsize)
+        return result
+
+    def _check_rawsize_alloced(self, size_estimate):
+        self.large_objects_collect_trigger -= size_estimate
+        if self.large_objects_collect_trigger < 0:
+            debug_start("gc-rawsize-collect")
+            debug_print("allocated", (self._initial_trigger -
+                                      self.large_objects_collect_trigger),
+                        "bytes, triggering full collection")
+            self.semispace_collect()
+            debug_stop("gc-rawsize-collect")
+
+    def malloc_varsize_marknsweep(self, totalsize):
+        # In order to free the large objects from time to time, we
+        # arbitrarily force a full collect() if none occurs when we have
+        # allocated self.space_size + rawmalloced bytes of large objects.
+        self._check_rawsize_alloced(raw_malloc_usage(totalsize))
+        result = self.allocate_external_object(totalsize)
+        if not result:
+            raise MemoryError()
+        # The parent classes guarantee zero-filled allocations, so we
+        # need to follow suit.
+        llmemory.raw_memclear(result, totalsize)
+        size_gc_header = self.gcheaderbuilder.size_gc_header
+        self.gen2_rawmalloced_objects.append(result + size_gc_header)
+        return result
+
+    def allocate_external_object(self, totalsize):
+        # XXX maybe we should use arena_malloc() above a certain size?
+        # If so, we'd also use arena_reset() in malloc_varsize_marknsweep().
+        return llmemory.raw_malloc(totalsize)
+
+    def init_gc_object_immortal(self, addr, typeid,
+                                flags=(GCFLAG_NO_YOUNG_PTRS |
+                                       GCFLAG_NO_HEAP_PTRS |
+                                       GCFLAG_AGE_MAX)):
+        GenerationGC.init_gc_object_immortal(self, addr, typeid, flags)
+
+    # ___________________________________________________________________
+    # collect() and semispace_collect() are not synonyms in this GC: the
+    # former is a complete collect, while the latter is only collecting
+    # the semispaces and not always doing the mark-n-sweep pass over the
+    # external objects of 3rd generation.
+
+    def collect(self, gen=2):
+        if gen > 1:
+            self.count_semispaceonly_collects = self.generation3_collect_threshold
+        GenerationGC.collect(self, gen)
+
+    def is_collecting_gen3(self):
+        count = self.count_semispaceonly_collects
+        return count >= self.generation3_collect_threshold
+
+    # ___________________________________________________________________
+    # the following methods are hook into SemiSpaceGC.semispace_collect()
+
+    def starting_full_collect(self):
+        # At the start of a collection, the GCFLAG_UNVISITED bit is set
+        # exactly on the objects in gen2_rawmalloced_objects.  Only
+        # raw_malloc'ed objects can ever have this bit set.
+        self.count_semispaceonly_collects += 1
+        if self.is_collecting_gen3():
+            # set the GCFLAG_UNVISITED on all rawmalloced generation-3 objects
+            # as well, to let them be recorded by visit_external_object()
+            self.gen3_rawmalloced_objects.foreach(self._set_gcflag_unvisited,
+                                                  None)
+        ll_assert(not self.rawmalloced_objects_to_trace.non_empty(),
+                  "rawmalloced_objects_to_trace should be empty at start")
+        self._nonmoving_copy_count = 0
+        self._nonmoving_copy_size = 0
+
+    def _set_gcflag_unvisited(self, obj, ignored):
+        ll_assert(not (self.header(obj).tid & GCFLAG_UNVISITED),
+                  "bogus GCFLAG_UNVISITED on gen3 obj")
+        self.header(obj).tid |= GCFLAG_UNVISITED
+
+    def collect_roots(self):
+        if not self.is_collecting_gen3():
+            GenerationGC.collect_roots(self)
+        else:
+            # as we don't record which prebuilt gc objects point to
+            # rawmalloced generation 3 objects, we have to trace all
+            # the prebuilt gc objects.
+            self.root_walker.walk_roots(
+                SemiSpaceGC._collect_root,  # stack roots
+                SemiSpaceGC._collect_root,  # static in prebuilt non-gc structs
+                SemiSpaceGC._collect_root)  # static in prebuilt gc objects
+
+    def surviving(self, obj):
+        # To use during a collection.  The objects that survive are the
+        # ones with GCFLAG_FORWARDED set and GCFLAG_UNVISITED not set.
+        # This is equivalent to self.is_forwarded() for all objects except
+        # the ones obtained by raw_malloc.
+        flags = self.header(obj).tid & (GCFLAG_FORWARDED|GCFLAG_UNVISITED)
+        return flags == GCFLAG_FORWARDED
+
+    def is_last_generation(self, obj):
+        return ((self.header(obj).tid & (GCFLAG_EXTERNAL|GCFLAG_AGE_MASK)) ==
+                (GCFLAG_EXTERNAL|GCFLAG_AGE_MAX))
+
+    def visit_external_object(self, obj):
+        hdr = self.header(obj)
+        if hdr.tid & GCFLAG_UNVISITED:
+            # This is a not-visited-yet raw_malloced object.
+            hdr.tid &= ~GCFLAG_UNVISITED
+            self.rawmalloced_objects_to_trace.append(obj)
+
+    def make_a_copy(self, obj, objsize):
+        # During a full collect, all copied objects might implicitly come
+        # from the nursery.  If they do, we must add the GCFLAG_NO_YOUNG_PTRS.
+        # If they don't, we count how many times they are copied and when
+        # some threshold is reached we make the copy a non-movable "external"
+        # object.  The threshold is MAX_SEMISPACE_AGE.
+        tid = self.header(obj).tid
+        # XXX the following logic is not doing exactly what is explained
+        # above: any object without GCFLAG_NO_YOUNG_PTRS has its age not
+        # incremented.  This is accidental: it means that objects that
+        # are very often modified to point to young objects don't reach
+        # the 3rd generation.  For now I'll leave it this way because
+        # I'm not sure that it's a bad thing.
+        if not (tid & GCFLAG_NO_YOUNG_PTRS):
+            tid |= GCFLAG_NO_YOUNG_PTRS    # object comes from the nursery
+        elif (tid & GCFLAG_AGE_MASK) < GCFLAG_AGE_MAX:
+            tid += GCFLAG_AGE_ONE
+        else:
+            newobj = self.make_a_nonmoving_copy(obj, objsize)
+            if newobj:
+                return newobj
+            tid &= ~GCFLAG_AGE_MASK
+        # skip GenerationGC.make_a_copy() as we already did the right
+        # thing about GCFLAG_NO_YOUNG_PTRS
+        return self._make_a_copy_with_tid(obj, objsize, tid)
+
+    def make_a_nonmoving_copy(self, obj, objsize):
+        # NB. the object can have a finalizer or be a weakref, but
+        # it's not an issue.
+        totalsize = self.size_gc_header() + objsize
+        tid = self.header(obj).tid
+        if tid & GCFLAG_HASHMASK:
+            totalsize_incl_hash = totalsize + llmemory.sizeof(lltype.Signed)
+        else:
+            totalsize_incl_hash = totalsize
+        newaddr = self.allocate_external_object(totalsize_incl_hash)
+        if not newaddr:
+            return llmemory.NULL   # can't raise MemoryError during a collect()
+        self._nonmoving_copy_count += 1
+        self._nonmoving_copy_size += raw_malloc_usage(totalsize)
+
+        llmemory.raw_memcopy(obj - self.size_gc_header(), newaddr, totalsize)
+        if tid & GCFLAG_HASHMASK:
+            hash = self._get_object_hash(obj, objsize, tid)
+            (newaddr + totalsize).signed[0] = hash
+            tid |= GC_HASH_HASFIELD
+        #
+        # GCFLAG_UNVISITED is not set
+        # GCFLAG_NO_HEAP_PTRS is not set either, conservatively.  It may be
+        # set by the next collection's collect_last_generation_roots().
+        # This old object is immediately put at generation 3.
+        newobj = newaddr + self.size_gc_header()
+        hdr = self.header(newobj)
+        hdr.tid = tid | self.GCFLAGS_FOR_NEW_EXTERNAL_OBJECTS
+        ll_assert(self.is_last_generation(newobj),
+                  "make_a_nonmoving_copy: object too young")
+        self.gen3_rawmalloced_objects.append(newobj)
+        self.last_generation_root_objects.append(newobj)
+        self.rawmalloced_objects_to_trace.append(newobj)   # visit me
+        return newobj
+
+    def scan_copied(self, scan):
+        # Alternate between scanning the regular objects we just moved
+        # and scanning the raw_malloc'ed object we just visited.
+        progress = True
+        while progress:
+            newscan = GenerationGC.scan_copied(self, scan)
+            progress = newscan != scan
+            scan = newscan
+            while self.rawmalloced_objects_to_trace.non_empty():
+                obj = self.rawmalloced_objects_to_trace.pop()
+                self.trace_and_copy(obj)
+                progress = True
+        return scan
+
+    def finished_full_collect(self):
+        ll_assert(not self.rawmalloced_objects_to_trace.non_empty(),
+                  "rawmalloced_objects_to_trace should be empty at end")
+        debug_print("| [hybrid] made nonmoving:         ",
+                    self._nonmoving_copy_size, "bytes in",
+                    self._nonmoving_copy_count, "objs")
+        rawmalloced_trigger = 0
+        # sweep the nonmarked rawmalloced objects
+        if self.is_collecting_gen3():
+            rawmalloced_trigger += self.sweep_rawmalloced_objects(generation=3)
+        rawmalloced_trigger += self.sweep_rawmalloced_objects(generation=2)
+        self.large_objects_collect_trigger = (rawmalloced_trigger +
+                                              self.space_size)
+        if self.is_collecting_gen3():
+            self.count_semispaceonly_collects = 0
+        self._initial_trigger = self.large_objects_collect_trigger
+
+    def sweep_rawmalloced_objects(self, generation):
+        # free all the rawmalloced objects of the specified generation
+        # that have not been marked
+        if generation == 2:
+            objects = self.gen2_rawmalloced_objects
+            # generation 2 sweep: if A points to an object object B that
+            # moves from gen2 to gen3, it's possible that A no longer points
+            # to any gen2 object.  In this case, A remains a bit too long in
+            # last_generation_root_objects, but this will be fixed by the
+            # next collect_last_generation_roots().
+        elif generation == 3:
+            objects = self.gen3_rawmalloced_objects
+            # generation 3 sweep: remove from last_generation_root_objects
+            # all the objects that we are about to free
+            gen3roots = self.last_generation_root_objects
+            newgen3roots = self.AddressStack()
+            while gen3roots.non_empty():
+                obj = gen3roots.pop()
+                if not (self.header(obj).tid & GCFLAG_UNVISITED):
+                    newgen3roots.append(obj)
+            gen3roots.delete()