Commits

Armin Rigo committed 4bf9cf2

Kill the "marksweep" GC and the "markcompact" GC. The former was here
for historical reasons only but never made much sense performance-wise.
The latter is not maintained and slightly broken for now; it's revivable
if there is interest.

Comments (0)

Files changed (12)

pypy/config/test/test_pypyoption.py

 
 
 def test_frameworkgc():
-    for name in ["marksweep", "semispace"]:
+    for name in ["minimark", "semispace"]:
         conf = get_pypy_config()
         assert conf.translation.gctransformer != "framework"
         conf.translation.gc = name

pypy/config/translationoption.py

 
     # gc
     ChoiceOption("gc", "Garbage Collection Strategy",
-                 ["boehm", "ref", "marksweep", "semispace", "statistics",
-                  "generation", "hybrid", "markcompact", "minimark", "none"],
+                 ["boehm", "ref", "semispace", "statistics",
+                  "generation", "hybrid", "minimark", "none"],
                   "ref", requires={
                      "ref": [("translation.rweakref", False), # XXX
                              ("translation.gctransformer", "ref")],
                      "none": [("translation.rweakref", False), # XXX
                              ("translation.gctransformer", "none")],
                      "semispace": [("translation.gctransformer", "framework")],
-                     "marksweep": [("translation.gctransformer", "framework")],
                      "statistics": [("translation.gctransformer", "framework")],
                      "generation": [("translation.gctransformer", "framework")],
                      "hybrid": [("translation.gctransformer", "framework")],
                      "boehm": [("translation.continuation", False),  # breaks
                                ("translation.gctransformer", "boehm")],
-                     "markcompact": [("translation.gctransformer", "framework")],
                      "minimark": [("translation.gctransformer", "framework")],
                      },
                   cmdline="--gc"),

pypy/doc/garbage_collection.rst

 Mark and Sweep
 --------------
 
-Classical Mark and Sweep collector.  Also contains a lot of experimental
-and half-unmaintained features.  See `pypy/rpython/memory/gc/marksweep.py`_.
+Classical Mark and Sweep collector.  Also contained a lot of experimental
+and half-unmaintained features.  Was removed.
 
 Semispace copying collector
 ---------------------------
 Mark & Compact GC
 -----------------
 
+Killed in trunk.  The following documentation is for historical purposes
+only.
+
 Inspired, at least partially, by Squeak's garbage collector, this is a
 single-arena GC in which collection compacts the objects in-place.  The
 main point of this GC is to save as much memory as possible (to be not
 objects' header, in order to let the collector store temporary relation
 information in the regular headers.
 
-More details are available as comments at the start of the source
-in `pypy/rpython/memory/gc/markcompact.py`_.
-
 Minimark GC
 -----------
 

pypy/rpython/memory/gc/base.py

     def write_barrier(self, newvalue, addr_struct):
         pass
 
-    def statistics(self, index):
-        return -1
-
     def size_gc_header(self, typeid=0):
         return self.gcheaderbuilder.size_gc_header
 
     def set_max_heap_size(self, size):
         raise NotImplementedError
 
-    def x_swap_pool(self, newpool):
-        return newpool
-
-    def x_clone(self, clonedata):
-        raise RuntimeError("no support for x_clone in the GC")
-
     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
 def choose_gc_from_config(config):
     """Return a (GCClass, GC_PARAMS) from the given config object.
     """
-    if config.translation.gctransformer != "framework":   # for tests
-        config.translation.gc = "marksweep"     # crash if inconsistent
+    if config.translation.gctransformer != "framework":
+        raise AssertionError("fix this test")
 
-    classes = {"marksweep": "marksweep.MarkSweepGC",
-               "statistics": "marksweep.PrintingMarkSweepGC",
-               "semispace": "semispace.SemiSpaceGC",
+    classes = {"semispace": "semispace.SemiSpaceGC",
                "generation": "generation.GenerationGC",
                "hybrid": "hybrid.HybridGC",
-               "markcompact" : "markcompact.MarkCompactGC",
                "minimark" : "minimark.MiniMarkGC",
                }
     try:

pypy/rpython/memory/gc/markcompact.py

-from pypy.rpython.lltypesystem import lltype, llmemory, llarena, llgroup
-from pypy.rpython.memory.gc.base import MovingGCBase
-from pypy.rpython.memory.gc import env
-from pypy.rlib.debug import ll_assert, have_debug_prints
-from pypy.rlib.debug import debug_print, debug_start, debug_stop
-from pypy.rpython.memory.support import get_address_stack, get_address_deque
-from pypy.rpython.memory.support import AddressDict
-from pypy.rpython.lltypesystem.llmemory import NULL, raw_malloc_usage
-from pypy.rlib.rarithmetic import ovfcheck, LONG_BIT, intmask
-from pypy.rpython.lltypesystem.lloperation import llop
-from pypy.rlib.objectmodel import we_are_translated, running_on_llinterp
-from pypy.rpython.lltypesystem import rffi
-from pypy.rpython.memory.gcheader import GCHeaderBuilder
-from pypy.rlib.rarithmetic import is_valid_int
-
-
-# Mark'n'compact garbage collector
-#
-# main point of this GC is to save as much memory as possible
-# (not to be worse than semispace), but avoid having peaks of
-# memory during collection. Inspired, at least partly by squeak's
-# garbage collector
-
-# so, the idea as now is:
-
-# this gc works more or less like semispace, but has some essential
-# differencies. The main difference is that we have separate phases of
-# marking and assigning pointers, hence order of objects is preserved.
-# This means we can reuse the same space, overwriting it as we collect.
-
-# so the algorithm itself is performed in 3 stages (modulo weakrefs and
-# finalizers):
-
-# 1. We mark alive objects
-# 2. We walk all objects and assign forward pointers in the same order,
-#    also updating all references
-# 3. We compact the space by moving.  We use 'arena_new_view' trick, which
-#    looks like new space to tests, but compiles to the same pointer.
-#    Also we use raw_memmove in case the object overlaps with its destination.
-
-# After each collection, we bump 'next_collect_after' which is a marker
-# where to start each collection.  It should be exponential (but less
-# than 2) from the size occupied by objects so far.
-
-# field optimization - we don't need forward pointer and flags at the same
-# time. Instead we copy the TIDs in a list when we know how many objects are
-# alive, and store the forward pointer in the old object header.
-
-first_gcflag_bit = LONG_BIT//2
-first_gcflag = 1 << first_gcflag_bit
-GCFLAG_HASHTAKEN = first_gcflag << 0      # someone already asked for the hash
-GCFLAG_HASHFIELD = first_gcflag << 1      # we have an extra hash field
-# note that only the first 2 bits are preserved during a collection!
-GCFLAG_MARKBIT   = intmask(first_gcflag << (LONG_BIT//2-1))
-assert GCFLAG_MARKBIT < 0     # should be 0x80000000
-
-GCFLAG_SAVED_HASHTAKEN = GCFLAG_HASHTAKEN >> first_gcflag_bit
-GCFLAG_SAVED_HASHFIELD = GCFLAG_HASHFIELD >> first_gcflag_bit
-
-
-TID_TYPE = llgroup.HALFWORD
-BYTES_PER_TID = rffi.sizeof(TID_TYPE)
-TID_BACKUP = rffi.CArray(TID_TYPE)
-
-def translated_to_c():
-    return we_are_translated() and not running_on_llinterp
-
-
-class MarkCompactGC(MovingGCBase):
-    HDR = lltype.Struct('header', ('tid', lltype.Signed))
-    typeid_is_in_field = 'tid'
-    withhash_flag_is_in_field = 'tid', GCFLAG_HASHFIELD
-    # ^^^ all prebuilt objects have GCFLAG_HASHTAKEN, but only some have
-    #     GCFLAG_HASHFIELD (and then they are one word longer).
-
-    # The default space size is 1.9375 GB, i.e. almost 2 GB, allocated as
-    # a big mmap.  The process does not actually consume that space until
-    # needed, of course.
-    TRANSLATION_PARAMS = {'space_size': int((1 + 15.0/16)*1024*1024*1024),
-                          'min_next_collect_after': 16*1024*1024}   # 16MB
-
-    malloc_zero_filled = False
-    inline_simple_malloc = True
-    inline_simple_malloc_varsize = True
-    #total_collection_time = 0.0
-    #total_collection_count = 0
-
-    free = NULL
-    next_collect_after = -1
-
-    def __init__(self, config, space_size=4096,
-                 min_next_collect_after=128, **kwds):
-        import py
-        py.test.skip("the 'markcompact' gc needs fixing for custom tracers")
-        #
-        MovingGCBase.__init__(self, config, **kwds)
-        self.space_size = space_size
-        self.min_next_collect_after = min_next_collect_after
-
-    def next_collection(self, used_space, num_objects_so_far, requested_size):
-        used_space += BYTES_PER_TID * num_objects_so_far
-        ll_assert(used_space <= self.space_size,
-                  "used_space + num_objects_so_far overflow")
-        try:
-            next = (used_space // 3) * 2 + requested_size
-        except OverflowError:
-            next = self.space_size
-        if next < self.min_next_collect_after:
-            next = self.min_next_collect_after
-        if next > self.space_size - used_space:
-            next = self.space_size - used_space
-        # The value we return guarantees that used_space + next <= space_size,
-        # with 'BYTES_PER_TID*num_objects_so_far' included in used_space.
-        # Normally, the value we return should also be at least requested_size
-        # unless we are out of memory.
-        return next
-
-    def setup(self):
-        envsize = env.read_from_env('PYPY_MARKCOMPACTGC_MAX')
-        if envsize >= 4096:
-            self.space_size = envsize & ~4095
-        mincollect = env.read_from_env('PYPY_MARKCOMPACTGC_MIN')
-        if mincollect >= 4096:
-            self.min_next_collect_after = mincollect
-
-        #self.program_start_time = time.time()
-        self.space = llarena.arena_malloc(self.space_size, False)
-        if not self.space:
-            raise CannotAllocateGCArena
-        self.free = self.space
-        MovingGCBase.setup(self)
-        self.objects_with_finalizers = self.AddressDeque()
-        self.tid_backup = lltype.nullptr(TID_BACKUP)
-        self.next_collect_after = self.next_collection(0, 0, 0)
-
-    def init_gc_object(self, addr, typeid16, flags=0):
-        hdr = llmemory.cast_adr_to_ptr(addr, lltype.Ptr(self.HDR))
-        hdr.tid = self.combine(typeid16, flags)
-
-    def init_gc_object_immortal(self, addr, typeid16, flags=0):
-        hdr = llmemory.cast_adr_to_ptr(addr, lltype.Ptr(self.HDR))
-        flags |= GCFLAG_HASHTAKEN | GCFLAG_MARKBIT
-        # All prebuilt GC objects have the GCFLAG_MARKBIT always set.
-        # That's convenient to make the GC always think that they
-        # survive the current collection.
-        hdr.tid = self.combine(typeid16, flags)
-
-    def _get_memory(self, totalsize):
-        # also counts the space that will be needed during the following
-        # collection to store the TID
-        requested_size = raw_malloc_usage(totalsize) + BYTES_PER_TID
-        self.next_collect_after -= requested_size
-        if self.next_collect_after < 0:
-            result = self.obtain_free_space(requested_size)
-        else:
-            result = self.free
-        self.free += totalsize
-        llarena.arena_reserve(result, totalsize)
-        return result
-    _get_memory._always_inline_ = True
-
-    def _get_totalsize_var(self, nonvarsize, itemsize, length):
-        try:
-            varsize = ovfcheck(itemsize * length)
-        except OverflowError:
-            raise MemoryError
-        # Careful to detect overflows.  The following works even if varsize
-        # is almost equal to sys.maxint; morever, self.space_size is known
-        # to be at least 4095 bytes smaller than sys.maxint, so this function
-        # always raises instead of returning an integer >= sys.maxint-4095.
-        if (raw_malloc_usage(varsize) > self.space_size -
-                                        raw_malloc_usage(nonvarsize)):
-            raise MemoryError
-        return llarena.round_up_for_allocation(nonvarsize + varsize)
-    _get_totalsize_var._always_inline_ = True
-
-    def _setup_object(self, result, typeid16, has_finalizer):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        self.init_gc_object(result, typeid16)
-        if has_finalizer:
-            self.objects_with_finalizers.append(result + size_gc_header)
-        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
-    _setup_object._always_inline_ = True
-
-    def malloc_fixedsize(self, typeid16, size,
-                         has_finalizer=False, contains_weakptr=False):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        totalsize = size_gc_header + size
-        result = self._get_memory(totalsize)
-        return self._setup_object(result, typeid16, has_finalizer)
-
-    def malloc_fixedsize_clear(self, typeid16, size,
-                               has_finalizer=False, contains_weakptr=False):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        totalsize = size_gc_header + size
-        result = self._get_memory(totalsize)
-        llmemory.raw_memclear(result, totalsize)
-        return self._setup_object(result, typeid16, has_finalizer)
-
-    def malloc_varsize_clear(self, typeid16, length, size, itemsize,
-                             offset_to_length):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        nonvarsize = size_gc_header + size
-        totalsize = self._get_totalsize_var(nonvarsize, itemsize, length)
-        result = self._get_memory(totalsize)
-        llmemory.raw_memclear(result, totalsize)
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        return self._setup_object(result, typeid16, False)
-
-    def obtain_free_space(self, requested_size):
-        if self.free == NULL:
-            return self._emergency_initial_block(requested_size)
-        while True:
-            executed_some_finalizers = self.markcompactcollect(requested_size)
-            self.next_collect_after -= requested_size
-            if self.next_collect_after >= 0:
-                break    # ok
-            else:
-                if executed_some_finalizers:
-                    pass   # try again to do a collection
-                else:
-                    raise MemoryError
-        return self.free
-    obtain_free_space._dont_inline_ = True
-
-    def _emergency_initial_block(self, requested_size):
-        # xxx before the GC is fully setup, we might get there.  Hopefully
-        # we will only allocate a couple of strings, e.g. in read_from_env().
-        # Just allocate them raw and leak them.
-        debug_start("gc-initial-block")
-        debug_print("leaking", requested_size, "bytes")
-        debug_stop("gc-initial-block")
-        return llmemory.raw_malloc(requested_size)
-
-    def collect(self, gen=0):
-        self.markcompactcollect()
-
-    def markcompactcollect(self, requested_size=0):
-        self.debug_collect_start(requested_size)
-        self.debug_check_consistency()
-        #
-        # Mark alive objects
-        #
-        self.to_see = self.AddressDeque()
-        self.trace_from_roots()
-        self.to_see.delete()
-        #
-        # Prepare new views on the same memory
-        #
-        toaddr = llarena.arena_new_view(self.space)
-        maxnum = self.space_size - (self.free - self.space)
-        maxnum /= BYTES_PER_TID
-        llarena.arena_reserve(self.free, llmemory.sizeof(TID_BACKUP, maxnum))
-        self.tid_backup = llmemory.cast_adr_to_ptr(self.free,
-                                                   lltype.Ptr(TID_BACKUP))
-        #
-        # Walk all objects and assign forward pointers in the same order,
-        # also updating all references
-        #
-        self.update_forward_pointers(toaddr, maxnum)
-        if (self.run_finalizers.non_empty() or
-            self.objects_with_finalizers.non_empty()):
-            self.update_run_finalizers()
-
-        self.update_objects_with_id()
-        self.compact()
-        #
-        self.tid_backup = lltype.nullptr(TID_BACKUP)
-        self.free = self.finaladdr
-        self.next_collect_after = self.next_collection(self.finaladdr - toaddr,
-                                                       self.num_alive_objs,
-                                                       requested_size)
-        #
-        if not translated_to_c():
-            remaining_size = (toaddr + self.space_size) - self.finaladdr
-            llarena.arena_reset(self.finaladdr, remaining_size, False)
-            llarena.arena_free(self.space)
-            self.space = toaddr
-        #
-        self.debug_check_consistency()
-        self.debug_collect_finish()
-        if self.next_collect_after < 0:
-            raise MemoryError
-        #
-        if self.run_finalizers.non_empty():
-            self.execute_finalizers()
-            return True      # executed some finalizers
-        else:
-            return False     # no finalizer executed
-
-    def debug_collect_start(self, requested_size):
-        if 1:# have_debug_prints():
-            debug_start("gc-collect")
-            debug_print()
-            debug_print(".----------- Full collection -------------------")
-            debug_print("| requested size:",
-                        requested_size)
-            #start_time = time.time()
-            #return start_time
-        #return -1
-
-    def debug_collect_finish(self):
-        if 1:# start_time != -1:
-            #end_time = time.time()
-            #elapsed_time = end_time - start_time
-            #self.total_collection_time += elapsed_time
-            #self.total_collection_count += 1
-            #total_program_time = end_time - self.program_start_time
-            #ct = self.total_collection_time
-            #cc = self.total_collection_count
-            #debug_print("| number of collections so far       ", 
-            #            cc)
-            debug_print("| total space size                   ", 
-                        self.space_size)
-            debug_print("| number of objects alive            ", 
-                        self.num_alive_objs)
-            debug_print("| used space size                    ", 
-                        self.free - self.space)
-            debug_print("| next collection after              ", 
-                        self.next_collect_after)
-            #debug_print("| total collections per second:      ",
-            #            cc / total_program_time)
-            #debug_print("| total time in markcompact-collect: ",
-            #            ct, "seconds")
-            #debug_print("| percentage collection<->total time:",
-            #            ct * 100.0 / total_program_time, "%")
-            debug_print("`----------------------------------------------")
-            debug_stop("gc-collect")
-
-
-    def update_run_finalizers(self):
-        if self.run_finalizers.non_empty():     # uncommon case
-            run_finalizers = self.AddressDeque()
-            while self.run_finalizers.non_empty():
-                obj = self.run_finalizers.popleft()
-                run_finalizers.append(self.get_forwarding_address(obj))
-            self.run_finalizers.delete()
-            self.run_finalizers = run_finalizers
-        #
-        objects_with_finalizers = self.AddressDeque()
-        while self.objects_with_finalizers.non_empty():
-            obj = self.objects_with_finalizers.popleft()
-            objects_with_finalizers.append(self.get_forwarding_address(obj))
-        self.objects_with_finalizers.delete()
-        self.objects_with_finalizers = objects_with_finalizers
-
-    def header(self, addr):
-        # like header(), but asserts that we have a normal header
-        hdr = MovingGCBase.header(self, addr)
-        if not we_are_translated():
-            assert isinstance(hdr.tid, llgroup.CombinedSymbolic)
-        return hdr
-
-    def header_forwarded(self, addr):
-        # like header(), but asserts that we have a forwarding header
-        hdr = MovingGCBase.header(self, addr)
-        if not we_are_translated():
-            assert is_valid_int(hdr.tid)
-        return hdr
-
-    def combine(self, typeid16, flags):
-        return llop.combine_ushort(lltype.Signed, typeid16, flags)
-
-    def get_type_id(self, addr):
-        tid = self.header(addr).tid
-        return llop.extract_ushort(llgroup.HALFWORD, tid)
-
-    def trace_from_roots(self):
-        self.root_walker.walk_roots(
-            MarkCompactGC._mark_root,  # stack roots
-            MarkCompactGC._mark_root,  # static in prebuilt non-gc structures
-            MarkCompactGC._mark_root)  # static in prebuilt gc objects
-        if (self.objects_with_finalizers.non_empty() or
-            self.run_finalizers.non_empty()):
-            self.trace_from_objects_with_finalizers()
-        self._trace_and_mark()
-
-    def _trace_and_mark(self):
-        while self.to_see.non_empty():
-            obj = self.to_see.popleft()
-            self.trace(obj, self._mark_obj, None)
-
-    def _mark_obj(self, pointer, ignored):
-        self.mark(pointer.address[0])
-
-    def _mark_root(self, root):
-        self.mark(root.address[0])
-
-    def mark(self, obj):
-        if not self.marked(obj):
-            self.header(obj).tid |= GCFLAG_MARKBIT
-            self.to_see.append(obj)
-
-    def marked(self, obj):
-        # should work both if tid contains a CombinedSymbolic (for dying
-        # objects, at this point), or a plain integer.
-        return MovingGCBase.header(self, obj).tid & GCFLAG_MARKBIT
-
-    def toaddr_smaller_than_fromaddr(self, toaddr, fromaddr):
-        if translated_to_c():
-            return toaddr < fromaddr
-        else:
-            # convert the addresses to integers, because they are
-            # theoretically not from the same arena
-            return toaddr - self.base_forwarding_addr < fromaddr - self.space
-
-    def update_forward_pointers(self, toaddr, maxnum):
-        self.base_forwarding_addr = base_forwarding_addr = toaddr
-        fromaddr = self.space
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        num = 0
-        while fromaddr < self.free:
-            hdr = llmemory.cast_adr_to_ptr(fromaddr, lltype.Ptr(self.HDR))
-            obj = fromaddr + size_gc_header
-            # compute the original object size, including the
-            # optional hash field
-            basesize = size_gc_header + self.get_size(obj)
-            totalsrcsize = basesize
-            if hdr.tid & GCFLAG_HASHFIELD:  # already a hash field, copy it too
-                totalsrcsize += llmemory.sizeof(lltype.Signed)
-            #
-            if self.marked(obj):
-                # the object is marked as suriving.  Compute the new object
-                # size
-                totaldstsize = totalsrcsize
-                if (hdr.tid & (GCFLAG_HASHTAKEN|GCFLAG_HASHFIELD) ==
-                               GCFLAG_HASHTAKEN):
-                    # grow a new hash field -- with the exception: if
-                    # the object actually doesn't move, don't
-                    # (otherwise, we get a bogus toaddr > fromaddr)
-                    if self.toaddr_smaller_than_fromaddr(toaddr, fromaddr):
-                        totaldstsize += llmemory.sizeof(lltype.Signed)
-                #
-                if not translated_to_c():
-                    llarena.arena_reserve(toaddr, basesize)
-                    if (raw_malloc_usage(totaldstsize) >
-                        raw_malloc_usage(basesize)):
-                        llarena.arena_reserve(toaddr + basesize,
-                                              llmemory.sizeof(lltype.Signed))
-                #
-                # save the field hdr.tid in the array tid_backup
-                ll_assert(num < maxnum, "overflow of the tid_backup table")
-                self.tid_backup[num] = self.get_type_id(obj)
-                num += 1
-                # compute forward_offset, the offset to the future copy
-                # of this object
-                forward_offset = toaddr - base_forwarding_addr
-                # copy the first two gc flags in forward_offset
-                ll_assert(forward_offset & 3 == 0, "misalignment!")
-                forward_offset |= (hdr.tid >> first_gcflag_bit) & 3
-                hdr.tid = forward_offset | GCFLAG_MARKBIT
-                ll_assert(self.marked(obj), "re-marking object failed!")
-                # done
-                toaddr += totaldstsize
-            #
-            fromaddr += totalsrcsize
-            if not translated_to_c():
-                assert toaddr - base_forwarding_addr <= fromaddr - self.space
-        self.num_alive_objs = num
-        self.finaladdr = toaddr
-
-        # now update references
-        self.root_walker.walk_roots(
-            MarkCompactGC._update_ref,  # stack roots
-            MarkCompactGC._update_ref,  # static in prebuilt non-gc structures
-            MarkCompactGC._update_ref)  # static in prebuilt gc objects
-        self.walk_marked_objects(MarkCompactGC.trace_and_update_ref)
-
-    def walk_marked_objects(self, callback):
-        num = 0
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        fromaddr = self.space
-        toaddr = self.base_forwarding_addr
-        while fromaddr < self.free:
-            hdr = llmemory.cast_adr_to_ptr(fromaddr, lltype.Ptr(self.HDR))
-            obj = fromaddr + size_gc_header
-            survives = self.marked(obj)
-            if survives:
-                typeid = self.get_typeid_from_backup(num)
-                num += 1
-            else:
-                typeid = self.get_type_id(obj)
-            baseobjsize = self._get_size_for_typeid(obj, typeid)
-            basesize = size_gc_header + baseobjsize
-            totalsrcsize = basesize
-            #
-            if survives:
-                grow_hash_field = False
-                if hdr.tid & GCFLAG_SAVED_HASHFIELD:
-                    totalsrcsize += llmemory.sizeof(lltype.Signed)
-                totaldstsize = totalsrcsize
-                if (hdr.tid & (GCFLAG_SAVED_HASHTAKEN|GCFLAG_SAVED_HASHFIELD)
-                            == GCFLAG_SAVED_HASHTAKEN):
-                    if self.toaddr_smaller_than_fromaddr(toaddr, fromaddr):
-                        grow_hash_field = True
-                        totaldstsize += llmemory.sizeof(lltype.Signed)
-                callback(self, obj, typeid, basesize, toaddr, grow_hash_field)
-                toaddr += totaldstsize
-            else:
-                if hdr.tid & GCFLAG_HASHFIELD:
-                    totalsrcsize += llmemory.sizeof(lltype.Signed)
-            #
-            fromaddr += totalsrcsize
-    walk_marked_objects._annspecialcase_ = 'specialize:arg(1)'
-
-    def trace_and_update_ref(self, obj, typeid, _1, _2, _3):
-        """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.
-        """
-        if self.is_gcarrayofgcptr(typeid):
-            # a performance shortcut for GcArray(gcptr)
-            length = (obj + llmemory.gcarrayofptr_lengthoffset).signed[0]
-            item = obj + llmemory.gcarrayofptr_itemsoffset
-            while length > 0:
-                self._update_ref(item)
-                item += llmemory.gcarrayofptr_singleitemoffset
-                length -= 1
-            return
-        offsets = self.offsets_to_gc_pointers(typeid)
-        i = 0
-        while i < len(offsets):
-            item = obj + offsets[i]
-            self._update_ref(item)
-            i += 1
-        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]
-                    self._update_ref(itemobj)
-                    j += 1
-                item += itemlength
-                length -= 1
-        else:
-            weakofs = self.weakpointer_offset(typeid)
-            if weakofs >= 0:
-                self._update_weakref(obj + weakofs)
-
-    def _update_ref(self, pointer):
-        if self.points_to_valid_gc_object(pointer):
-            pointer.address[0] = self.get_forwarding_address(
-                pointer.address[0])
-
-    def _update_weakref(self, pointer):
-        # either update the weak pointer's destination, or
-        # if it dies, write a NULL
-        if self.points_to_valid_gc_object(pointer):
-            if self.marked(pointer.address[0]):
-                pointer.address[0] = self.get_forwarding_address(
-                    pointer.address[0])
-            else:
-                pointer.address[0] = NULL
-
-    def _is_external(self, obj):
-        return not (self.space <= obj < self.free)
-
-    def get_forwarding_address(self, obj):
-        if self._is_external(obj):
-            return obj
-        return self.get_header_forwarded_addr(obj)
-
-    def get_header_forwarded_addr(self, obj):
-        tid = self.header_forwarded(obj).tid
-        ll_assert(tid & GCFLAG_MARKBIT != 0, "dying object is not forwarded")
-        GCFLAG_MASK = ~(GCFLAG_MARKBIT | 3)
-        res = (self.base_forwarding_addr + (tid & GCFLAG_MASK) +
-               self.gcheaderbuilder.size_gc_header)
-        ll_assert(res < self.finaladdr, "forwarded address >= self.finaladdr")
-        return res
-
-    def surviving(self, obj):
-        return self.marked(obj)
-
-    def get_typeid_from_backup(self, num):
-        return self.tid_backup[num]
-
-    def compact(self):
-        self.walk_marked_objects(MarkCompactGC.copy_and_compact)
-
-    def copy_and_compact(self, obj, typeid, basesize, toaddr, grow_hash_field):
-        # 'basesize' is the size without any hash field
-        # restore the normal header
-        hdr = self.header_forwarded(obj)
-        gcflags = hdr.tid & 3
-        if grow_hash_field:
-            gcflags |= GCFLAG_SAVED_HASHFIELD
-            hashvalue = self.get_identityhash_from_addr(obj)
-        elif gcflags & GCFLAG_SAVED_HASHFIELD:
-            fromaddr = llarena.getfakearenaaddress(obj)
-            fromaddr -= self.gcheaderbuilder.size_gc_header
-            hashvalue = (fromaddr + basesize).signed[0]
-        else:
-            hashvalue = 0     # not used
-        #
-        hdr.tid = self.combine(typeid, gcflags << first_gcflag_bit)
-        #
-        fromaddr = obj - self.gcheaderbuilder.size_gc_header
-        if translated_to_c():
-            llmemory.raw_memmove(fromaddr, toaddr, basesize)
-        else:
-            llmemory.raw_memcopy(fromaddr, toaddr, basesize)
-        #
-        if gcflags & GCFLAG_SAVED_HASHFIELD:
-            (toaddr + basesize).signed[0] = hashvalue
-
-    def debug_check_object(self, obj):
-        type_id = self.get_type_id(obj)
-        self.has_gcptr_in_varsize(type_id)   # checks that the type_id is valid
-        #
-        tid = self.header(obj).tid
-        if self._is_external(obj):
-            # All external objects have GCFLAG_MARKBIT and GCFLAG_HASHTAKEN
-            # set.
-            assert tid & GCFLAG_MARKBIT
-            assert tid & GCFLAG_HASHTAKEN
-        else:
-            # Non-external objects have GCFLAG_MARKBIT that should not be set
-            # at the very start or at the very end of a collection -- only
-            # temporarily during the collection.
-            assert tid & GCFLAG_MARKBIT == 0
-
-    def trace_from_objects_with_finalizers(self):
-        if self.run_finalizers.non_empty():   # uncommon case
-            new_run_finalizers = self.AddressDeque()
-            while self.run_finalizers.non_empty():
-                x = self.run_finalizers.popleft()
-                self.mark(x)
-                new_run_finalizers.append(x)
-            self.run_finalizers.delete()
-            self.run_finalizers = new_run_finalizers
-        #
-        # xxx we get to run the finalizers in a random order
-        self._trace_and_mark()
-        new_with_finalizers = self.AddressDeque()
-        while self.objects_with_finalizers.non_empty():
-            x = self.objects_with_finalizers.popleft()
-            if self.marked(x):
-                new_with_finalizers.append(x)
-            else:
-                self.run_finalizers.append(x)
-                self.mark(x)
-                self._trace_and_mark()
-        self.objects_with_finalizers.delete()
-        self.objects_with_finalizers = new_with_finalizers
-
-    def identityhash(self, gcobj):
-        # Unlike SemiSpaceGC.identityhash(), this function does not have
-        # to care about reducing top_of_space.  The reason is as
-        # follows.  When we collect, each object either moves to the
-        # left or stays where it is.  If it moves to the left (and if it
-        # has GCFLAG_HASHTAKEN), we can give it a hash field, and the
-        # end of the new object cannot move to the right of the end of
-        # the old object.  If it stays where it is, then we don't need
-        # to add the hash field.  So collecting can never actually grow
-        # the consumed size.
-        obj = llmemory.cast_ptr_to_adr(gcobj)
-        hdr = self.header(obj)
-        #
-        if hdr.tid & GCFLAG_HASHFIELD:  # the hash is in a field at the end
-            obj = llarena.getfakearenaaddress(obj) + self.get_size(obj)
-            return obj.signed[0]
-        #
-        hdr.tid |= GCFLAG_HASHTAKEN
-        return self.get_identityhash_from_addr(obj)
-
-    def get_identityhash_from_addr(self, obj):
-        if translated_to_c():
-            return llmemory.cast_adr_to_int(obj)  # direct case
-        else:
-            try:
-                adr = llarena.getfakearenaaddress(obj)   # -> arena address
-            except RuntimeError:
-                return llmemory.cast_adr_to_int(obj)  # not in an arena...
-            return adr - self.space
-
-    def get_size_incl_hash(self, obj):
-        size = self.get_size(obj)
-        hdr = self.header(obj)
-        if hdr.tid & GCFLAG_HASHFIELD:
-            size += llmemory.sizeof(lltype.Signed)
-        return size
-
-# ____________________________________________________________
-
-class CannotAllocateGCArena(Exception):
-    pass

pypy/rpython/memory/gc/marksweep.py

-from pypy.rpython.lltypesystem.llmemory import raw_malloc, raw_free
-from pypy.rpython.lltypesystem.llmemory import raw_memcopy, raw_memclear
-from pypy.rpython.lltypesystem.llmemory import NULL, raw_malloc_usage
-from pypy.rpython.memory.support import get_address_stack
-from pypy.rpython.memory.gcheader import GCHeaderBuilder
-from pypy.rpython.lltypesystem import lltype, llmemory, rffi, llgroup
-from pypy.rlib.objectmodel import free_non_gc_object
-from pypy.rpython.lltypesystem.lloperation import llop
-from pypy.rlib.rarithmetic import ovfcheck
-from pypy.rlib.debug import debug_print, debug_start, debug_stop
-from pypy.rpython.memory.gc.base import GCBase
-
-
-import sys, os
-
-##X_POOL = lltype.GcOpaqueType('gc.pool')
-##X_POOL_PTR = lltype.Ptr(X_POOL)
-##X_CLONE = lltype.GcStruct('CloneData', ('gcobjectptr', llmemory.GCREF),
-##                                       ('pool',        X_POOL_PTR))
-##X_CLONE_PTR = lltype.Ptr(X_CLONE)
-
-FL_WITHHASH = 0x01
-##FL_CURPOOL  = 0x02
-
-memoryError = MemoryError()
-class MarkSweepGC(GCBase):
-    HDR = lltype.ForwardReference()
-    HDRPTR = lltype.Ptr(HDR)
-    # need to maintain a linked list of malloced objects, since we used the
-    # systems allocator and can't walk the heap
-    HDR.become(lltype.Struct('header', ('typeid16', llgroup.HALFWORD),
-                                       ('mark', lltype.Bool),
-                                       ('flags', lltype.Char),
-                                       ('next', HDRPTR)))
-    typeid_is_in_field = 'typeid16'
-    withhash_flag_is_in_field = 'flags', FL_WITHHASH
-
-    POOL = lltype.GcStruct('gc_pool')
-    POOLPTR = lltype.Ptr(POOL)
-
-    POOLNODE = lltype.ForwardReference()
-    POOLNODEPTR = lltype.Ptr(POOLNODE)
-    POOLNODE.become(lltype.Struct('gc_pool_node', ('linkedlist', HDRPTR),
-                                                  ('nextnode', POOLNODEPTR)))
-
-    # the following values override the default arguments of __init__ when
-    # translating to a real backend.
-    TRANSLATION_PARAMS = {'start_heap_size': 8*1024*1024} # XXX adjust
-
-    def __init__(self, config, start_heap_size=4096, **kwds):
-        self.param_start_heap_size = start_heap_size
-        GCBase.__init__(self, config, **kwds)
-
-    def setup(self):
-        GCBase.setup(self)
-        self.heap_usage = 0          # at the end of the latest collection
-        self.bytes_malloced = 0      # since the latest collection
-        self.bytes_malloced_threshold = self.param_start_heap_size
-        self.total_collection_time = 0.0
-        self.malloced_objects = lltype.nullptr(self.HDR)
-        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-        # these are usually only the small bits of memory that make a
-        # weakref object
-        self.objects_with_weak_pointers = lltype.nullptr(self.HDR)
-        # pools, for x_swap_pool():
-        #   'curpool' is the current pool, lazily allocated (i.e. NULL means
-        #   the current POOL object is not yet malloc'ed).  POOL objects are
-        #   usually at the start of a linked list of objects, via the HDRs.
-        #   The exception is 'curpool' whose linked list of objects is in
-        #   'self.malloced_objects' instead of in the header of 'curpool'.
-        #   POOL objects are never in the middle of a linked list themselves.
-        # XXX a likely cause for the current problems with pools is:
-        # not all objects live in malloced_objects, some also live in
-        # malloced_objects_with_finalizer and objects_with_weak_pointers
-        self.curpool = lltype.nullptr(self.POOL)
-        #   'poolnodes' is a linked list of all such linked lists.  Each
-        #   linked list will usually start with a POOL object, but it can
-        #   also contain only normal objects if the POOL object at the head
-        #   was already freed.  The objects in 'malloced_objects' are not
-        #   found via 'poolnodes'.
-        self.poolnodes = lltype.nullptr(self.POOLNODE)
-        self.collect_in_progress = False
-        self.prev_collect_end_time = 0.0
-
-    def maybe_collect(self):
-        if self.bytes_malloced > self.bytes_malloced_threshold:
-            self.collect()
-
-    def write_malloc_statistics(self, typeid16, size, result, varsize):
-        pass
-
-    def write_free_statistics(self, typeid16, result):
-        pass
-
-    def malloc_fixedsize(self, typeid16, size,
-                         has_finalizer=False, is_finalizer_light=False,
-                         contains_weakptr=False):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            tot_size = size_gc_header + size
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        if has_finalizer:
-            hdr.next = self.malloced_objects_with_finalizer
-            self.malloced_objects_with_finalizer = hdr
-        elif contains_weakptr:
-            hdr.next = self.objects_with_weak_pointers
-            self.objects_with_weak_pointers = hdr
-        else:
-            hdr.next = self.malloced_objects
-            self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, False)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_fixedsize._dont_inline_ = True
-
-    def malloc_fixedsize_clear(self, typeid16, size,
-                               has_finalizer=False,
-                               is_finalizer_light=False,
-                               contains_weakptr=False):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            tot_size = size_gc_header + size
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        raw_memclear(result, tot_size)
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        if has_finalizer:
-            hdr.next = self.malloced_objects_with_finalizer
-            self.malloced_objects_with_finalizer = hdr
-        elif contains_weakptr:
-            hdr.next = self.objects_with_weak_pointers
-            self.objects_with_weak_pointers = hdr
-        else:
-            hdr.next = self.malloced_objects
-            self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, False)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_fixedsize_clear._dont_inline_ = True
-
-    def malloc_varsize(self, typeid16, length, size, itemsize,
-                       offset_to_length):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            fixsize = size_gc_header + size
-            varsize = ovfcheck(itemsize * length)
-            tot_size = ovfcheck(fixsize + varsize)
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        hdr.next = self.malloced_objects
-        self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-            
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc_varsize length', length,
-        #                 'typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, True)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_varsize._dont_inline_ = True
-
-    def malloc_varsize_clear(self, typeid16, length, size, itemsize,
-                             offset_to_length):
-        self.maybe_collect()
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        try:
-            fixsize = size_gc_header + size
-            varsize = ovfcheck(itemsize * length)
-            tot_size = ovfcheck(fixsize + varsize)
-            usage = raw_malloc_usage(tot_size)
-            bytes_malloced = ovfcheck(self.bytes_malloced+usage)
-            ovfcheck(self.heap_usage + bytes_malloced)
-        except OverflowError:
-            raise memoryError
-        result = raw_malloc(tot_size)
-        if not result:
-            raise memoryError
-        raw_memclear(result, tot_size)        
-        (result + size_gc_header + offset_to_length).signed[0] = length
-        hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
-        hdr.typeid16 = typeid16
-        hdr.mark = False
-        hdr.flags = '\x00'
-        hdr.next = self.malloced_objects
-        self.malloced_objects = hdr
-        self.bytes_malloced = bytes_malloced
-            
-        result += size_gc_header
-        #llop.debug_print(lltype.Void, 'malloc_varsize length', length,
-        #                 'typeid', typeid16,
-        #                 '->', llmemory.cast_adr_to_int(result))
-        self.write_malloc_statistics(typeid16, tot_size, result, True)
-        return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)
-    malloc_varsize_clear._dont_inline_ = True
-
-    def collect(self, gen=0):
-        # 1. mark from the roots, and also the objects that objects-with-del
-        #    point to (using the list of malloced_objects_with_finalizer)
-        # 2. walk the list of objects-without-del and free the ones not marked
-        # 3. walk the list of objects-with-del and for the ones not marked:
-        #    call __del__, move the object to the list of object-without-del
-        import time
-        debug_start("gc-collect")
-        start_time = time.time()
-        self.collect_in_progress = True
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-##        llop.debug_view(lltype.Void, self.malloced_objects, self.poolnodes,
-##                        size_gc_header)
-
-        # push the roots on the mark stack
-        objects = self.AddressStack() # mark stack
-        self._mark_stack = objects
-        self.root_walker.walk_roots(
-            MarkSweepGC._mark_root,  # stack roots
-            MarkSweepGC._mark_root,  # static in prebuilt non-gc structures
-            MarkSweepGC._mark_root)  # static in prebuilt gc objects
-
-        # from this point onwards, no more mallocs should be possible
-        old_malloced = self.bytes_malloced
-        self.bytes_malloced = 0
-        curr_heap_size = 0
-        freed_size = 0
-
-        # mark objects reachable by objects with a finalizer, but not those
-        # themselves. add their size to curr_heap_size, since they always
-        # survive the collection
-        hdr = self.malloced_objects_with_finalizer
-        while hdr:
-            next = hdr.next
-            typeid = hdr.typeid16
-            gc_info = llmemory.cast_ptr_to_adr(hdr)
-            obj = gc_info + size_gc_header
-            if not hdr.mark:
-                self.add_reachable_to_stack(obj, objects)
-            addr = llmemory.cast_ptr_to_adr(hdr)
-            size = self.fixed_size(typeid)
-            if self.is_varsize(typeid):
-                length = (obj + self.varsize_offset_to_length(typeid)).signed[0]
-                size += self.varsize_item_sizes(typeid) * length
-            estimate = raw_malloc_usage(size_gc_header + size)
-            curr_heap_size += estimate
-            hdr = next
-
-        # mark thinks on the mark stack and put their descendants onto the
-        # stack until the stack is empty
-        while objects.non_empty():  #mark
-            curr = objects.pop()
-            gc_info = curr - size_gc_header
-            hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-            if hdr.mark:
-                continue
-            self.add_reachable_to_stack(curr, objects)
-            hdr.mark = True
-        objects.delete()
-        # also mark self.curpool
-        if self.curpool:
-            gc_info = llmemory.cast_ptr_to_adr(self.curpool) - size_gc_header
-            hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-            hdr.mark = True
-        # go through the list of objects containing weak pointers
-        # and kill the links if they go to dead objects
-        # if the object itself is not marked, free it
-        hdr = self.objects_with_weak_pointers
-        surviving = lltype.nullptr(self.HDR)
-        while hdr:
-            typeid = hdr.typeid16
-            next = hdr.next
-            addr = llmemory.cast_ptr_to_adr(hdr)
-            size = self.fixed_size(typeid)
-            estimate = raw_malloc_usage(size_gc_header + size)
-            if hdr.mark:
-                offset = self.weakpointer_offset(typeid)
-                hdr.mark = False
-                gc_info = llmemory.cast_ptr_to_adr(hdr)
-                weakref_obj = gc_info + size_gc_header
-                pointing_to = (weakref_obj + offset).address[0]
-                if pointing_to:
-                    gc_info_pointing_to = pointing_to - size_gc_header
-                    hdr_pointing_to = llmemory.cast_adr_to_ptr(
-                        gc_info_pointing_to, self.HDRPTR)
-                    # pointed to object will die
-                    # XXX what to do if the object has a finalizer which resurrects
-                    # the object?
-                    if not hdr_pointing_to.mark:
-                        (weakref_obj + offset).address[0] = NULL
-                hdr.next = surviving
-                surviving = hdr
-                curr_heap_size += estimate
-            else:
-                gc_info = llmemory.cast_ptr_to_adr(hdr)
-                weakref_obj = gc_info + size_gc_header
-                self.write_free_statistics(typeid, weakref_obj)
-                freed_size += estimate
-                raw_free(addr)
-            hdr = next
-        self.objects_with_weak_pointers = surviving
-        # sweep: delete objects without del if they are not marked
-        # unmark objects without del that are marked
-        firstpoolnode = lltype.malloc(self.POOLNODE, flavor='raw')
-        firstpoolnode.linkedlist = self.malloced_objects
-        firstpoolnode.nextnode = self.poolnodes
-        prevpoolnode = lltype.nullptr(self.POOLNODE)
-        poolnode = firstpoolnode
-        while poolnode:   #sweep
-            ppnext = llmemory.cast_ptr_to_adr(poolnode)
-            ppnext += llmemory.offsetof(self.POOLNODE, 'linkedlist')
-            hdr = poolnode.linkedlist
-            while hdr:  #sweep
-                typeid = hdr.typeid16
-                next = hdr.next
-                addr = llmemory.cast_ptr_to_adr(hdr)
-                size = self.fixed_size(typeid)
-                if self.is_varsize(typeid):
-                    length = (addr + size_gc_header + self.varsize_offset_to_length(typeid)).signed[0]
-                    size += self.varsize_item_sizes(typeid) * length
-                estimate = raw_malloc_usage(size_gc_header + size)
-                if hdr.mark:
-                    hdr.mark = False
-                    ppnext.address[0] = addr
-                    ppnext = llmemory.cast_ptr_to_adr(hdr)
-                    ppnext += llmemory.offsetof(self.HDR, 'next')
-                    curr_heap_size += estimate
-                else:
-                    gc_info = llmemory.cast_ptr_to_adr(hdr)
-                    obj = gc_info + size_gc_header
-                    self.write_free_statistics(typeid, obj)
-                    freed_size += estimate
-                    raw_free(addr)
-                hdr = next
-            ppnext.address[0] = llmemory.NULL
-            next = poolnode.nextnode
-            if not poolnode.linkedlist and prevpoolnode:
-                # completely empty node
-                prevpoolnode.nextnode = next
-                lltype.free(poolnode, flavor='raw')
-            else:
-                prevpoolnode = poolnode
-            poolnode = next
-        self.malloced_objects = firstpoolnode.linkedlist
-        self.poolnodes = firstpoolnode.nextnode
-        lltype.free(firstpoolnode, flavor='raw')
-        #llop.debug_view(lltype.Void, self.malloced_objects, self.malloced_objects_with_finalizer, size_gc_header)
-
-        end_time = time.time()
-        compute_time = start_time - self.prev_collect_end_time
-        collect_time = end_time - start_time
-
-        garbage_collected = old_malloced - (curr_heap_size - self.heap_usage)
-
-        if (collect_time * curr_heap_size >
-            0.02 * garbage_collected * compute_time): 
-            self.bytes_malloced_threshold += self.bytes_malloced_threshold / 2
-        if (collect_time * curr_heap_size <
-            0.005 * garbage_collected * compute_time):
-            self.bytes_malloced_threshold /= 2
-
-        # Use atleast as much memory as current live objects.
-        if curr_heap_size > self.bytes_malloced_threshold:
-            self.bytes_malloced_threshold = curr_heap_size
-
-        # Cap at 1/4 GB
-        self.bytes_malloced_threshold = min(self.bytes_malloced_threshold,
-                                            256 * 1024 * 1024)
-        self.total_collection_time += collect_time
-        self.prev_collect_end_time = end_time
-        debug_print("  malloced since previous collection:",
-                    old_malloced, "bytes")
-        debug_print("  heap usage at start of collection: ",
-                    self.heap_usage + old_malloced, "bytes")
-        debug_print("  freed:                             ",
-                    freed_size, "bytes")
-        debug_print("  new heap usage:                    ",
-                    curr_heap_size, "bytes")
-        debug_print("  total time spent collecting:       ",
-                    self.total_collection_time, "seconds")
-        debug_print("  collecting time:                   ",
-                    collect_time)
-        debug_print("  computing time:                    ",
-                    collect_time)
-        debug_print("  new threshold:                     ",
-                    self.bytes_malloced_threshold)
-##        llop.debug_view(lltype.Void, self.malloced_objects, self.poolnodes,
-##                        size_gc_header)
-        assert self.heap_usage + old_malloced == curr_heap_size + freed_size
-
-        self.heap_usage = curr_heap_size
-        hdr = self.malloced_objects_with_finalizer
-        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-        last = lltype.nullptr(self.HDR)
-        while hdr:
-            next = hdr.next
-            if hdr.mark:
-                hdr.next = lltype.nullptr(self.HDR)
-                if not self.malloced_objects_with_finalizer:
-                    self.malloced_objects_with_finalizer = hdr
-                else:
-                    last.next = hdr
-                hdr.mark = False
-                last = hdr
-            else:
-                obj = llmemory.cast_ptr_to_adr(hdr) + size_gc_header
-                finalizer = self.getfinalizer(hdr.typeid16)
-                # make malloced_objects_with_finalizer consistent
-                # for the sake of a possible collection caused by finalizer
-                if not self.malloced_objects_with_finalizer:
-                    self.malloced_objects_with_finalizer = next
-                else:
-                    last.next = next
-                hdr.next = self.malloced_objects
-                self.malloced_objects = hdr
-                #llop.debug_view(lltype.Void, self.malloced_objects, self.malloced_objects_with_finalizer, size_gc_header)
-                finalizer(obj, llmemory.NULL)
-                if not self.collect_in_progress: # another collection was caused?
-                    debug_print("outer collect interrupted "
-                                "by recursive collect")
-                    debug_stop("gc-collect")
-                    return
-                if not last:
-                    if self.malloced_objects_with_finalizer == next:
-                        self.malloced_objects_with_finalizer = lltype.nullptr(self.HDR)
-                    else:
-                        # now it gets annoying: finalizer caused a malloc of something
-                        # with a finalizer
-                        last = self.malloced_objects_with_finalizer
-                        while last.next != next:
-                            last = last.next
-                            last.next = lltype.nullptr(self.HDR)
-                else:
-                    last.next = lltype.nullptr(self.HDR)
-            hdr = next
-        self.collect_in_progress = False
-        debug_stop("gc-collect")
-
-    def _mark_root(self, root):   # 'root' is the address of the GCPTR
-        gcobjectaddr = root.address[0]
-        self._mark_stack.append(gcobjectaddr)
-
-    def _mark_root_and_clear_bit(self, root):
-        gcobjectaddr = root.address[0]
-        self._mark_stack.append(gcobjectaddr)
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        gc_info = gcobjectaddr - size_gc_header
-        hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-        hdr.mark = False
-
-    STAT_HEAP_USAGE     = 0
-    STAT_BYTES_MALLOCED = 1
-    STATISTICS_NUMBERS  = 2
-
-    def get_type_id(self, obj):
-        size_gc_header = self.gcheaderbuilder.size_gc_header
-        gc_info = obj - size_gc_header
-        hdr = llmemory.cast_adr_to_ptr(gc_info, self.HDRPTR)
-        return hdr.typeid16
-
-    def add_reachable_to_stack(self, obj, objects):
-        self.trace(obj, self._add_reachable, objects)
-
-    def _add_reachable(pointer, objects):
-        obj = pointer.address[0]
-        objects.append(obj)
-    _add_reachable = staticmethod(_add_reachable)
-
-    def statistics(self, index):
-        # no memory allocation here!
-        if index == self.STAT_HEAP_USAGE:
-            return self.heap_usage
-        if index == self.STAT_BYTES_MALLOCED:
-            return self.bytes_malloced
-        return -1
-
-    def init_gc_object(self, addr, typeid):
-        hdr = llmemory.cast_adr_to_ptr(addr, self.HDRPTR)
-        hdr.typeid16 = typeid
-        hdr.mark = False
-        hdr.flags = '\x00'
-
-    def init_gc_object_immortal(self, addr, typeid, flags=0):
-        # prebuilt gc structures always have the mark bit set
-        # ignore flags
-        hdr = llmemory.cast_adr_to_ptr(addr, self.HDRPTR)
-        hdr.typeid16 = typeid
-        hdr.mark = True
-        hdr.flags = '\x00'
-
-    # experimental support for thread cloning
-    def x_swap_pool(self, newpool):
-        raise NotImplementedError("old operation deprecated")
-
-    def x_clone(self, clonedata):
-        raise NotImplementedError("old operation deprecated")
-
-    def identityhash(self, obj):
-        obj = llmemory.cast_ptr_to_adr(obj)
-        hdr = self.header(obj)
-        if ord(hdr.flags) & FL_WITHHASH:
-            obj += self.get_size(obj)
-            return obj.signed[0]
-        else:
-            return llmemory.cast_adr_to_int(obj)
-
-
-class PrintingMarkSweepGC(MarkSweepGC):
-    _alloc_flavor_ = "raw"
-    COLLECT_EVERY = 2000
-
-    def __init__(self, config, **kwds):
-        MarkSweepGC.__init__(self, config, **kwds)
-        self.count_mallocs = 0
-
-    def maybe_collect(self):
-        self.count_mallocs += 1
-        if self.count_mallocs > self.COLLECT_EVERY:
-            self.collect()
-
-    def write_malloc_statistics(self, typeid, size, result, varsize):
-        if varsize:
-            what = "malloc_varsize"
-        else:
-            what = "malloc"
-        llop.debug_print(lltype.Void, what, typeid, " ", size, " ", result)
-
-    def write_free_statistics(self, typeid, result):
-        llop.debug_print(lltype.Void, "free", typeid, " ", result)
-
-    def collect(self, gen=0):
-        self.count_mallocs = 0
-        MarkSweepGC.collect(self, gen)

pypy/rpython/memory/gc/test/test_direct.py

         print hash
         assert is_valid_int(hash)
         assert hash == self.gc.identityhash(p_const)
-        # (5) p is actually moving (for the markcompact gc)
+        # (5) p is actually moving (for the markcompact gc only?)
         p0 = self.malloc(S)
         self.stackroots.append(p0)
         p = self.malloc(S)
         py.test.skip("does not support raw_mallocs(sizeof(S)+sizeof(hash))")
 
 
-class TestMarkCompactGC(DirectGCTest):
-    from pypy.rpython.memory.gc.markcompact import MarkCompactGC as GCClass
-
-    def test_many_objects(self):
-        DirectGCTest.test_many_objects(self)
-    test_many_objects.GC_PARAMS = {'space_size': 3 * 1024 * WORD}
-
-    def test_varsized_from_stack(self):
-        DirectGCTest.test_varsized_from_stack(self)
-    test_varsized_from_stack.GC_PARAMS = {'space_size': 2 * 1024 * WORD}
-
-    def test_varsized_from_prebuilt_gc(self):
-        DirectGCTest.test_varsized_from_prebuilt_gc(self)
-    test_varsized_from_prebuilt_gc.GC_PARAMS = {'space_size': 3 * 1024 * WORD}
-
-
 class TestMiniMarkGCSimple(DirectGCTest):
     from pypy.rpython.memory.gc.minimark import MiniMarkGC as GCClass
     from pypy.rpython.memory.gc.minimark import SimpleArenaCollection

pypy/rpython/memory/gctransform/framework.py

                                                          inline=True)
         if hasattr(self, 'GC_PARAMS'):
             # for tests: the GC choice can be specified as class attributes
-            from pypy.rpython.memory.gc.marksweep import MarkSweepGC
-            GCClass = getattr(self, 'GCClass', MarkSweepGC)
+            GCClass = self.GCClass
             GC_PARAMS = self.GC_PARAMS
         else:
             # for regular translation: pick the GC from the config
                                              getfn(func,
                                                    [annmodel.SomeAddress()],
                                                    annmodel.s_None)
-        self.statistics_ptr = getfn(GCClass.statistics.im_func,
-                                    [s_gc, annmodel.SomeInteger()],
-                                    annmodel.SomeInteger())
 
         # thread support
         if translator.config.translation.continuation:
         hop.genop("direct_call",
                   [self.root_walker.gc_start_fresh_new_state_ptr])
 
-    def gct_gc_x_swap_pool(self, hop):
-        raise NotImplementedError("old operation deprecated")
-    def gct_gc_x_clone(self, hop):
-        raise NotImplementedError("old operation deprecated")
-    def gct_gc_x_size_header(self, hop):
-        raise NotImplementedError("old operation deprecated")
-
     def gct_do_malloc_fixedsize_clear(self, hop):
         # used by the JIT (see pypy.jit.backend.llsupport.gc)
         op = hop.spaceop

pypy/rpython/memory/gctransform/test/test_framework.py

 from pypy.annotation.model import SomeInteger
 from pypy.objspace.flow.model import Constant, SpaceOperation
 from pypy.rpython.lltypesystem import lltype, rffi
-from pypy.rpython.memory.gc.marksweep import MarkSweepGC
+from pypy.rpython.memory.gc.semispace import SemiSpaceGC
 from pypy.rpython.memory.gctransform.framework import (CollectAnalyzer,
      find_initializing_stores, find_clean_setarrayitems)
 from pypy.rpython.memory.gctransform.shadowstack import (
 class WriteBarrierTransformer(ShadowStackFrameworkGCTransformer):
     clean_sets = {}
     GC_PARAMS = {}
-    class GCClass(MarkSweepGC):
+    class GCClass(SemiSpaceGC):
         needs_write_barrier = True
         def writebarrier_before_copy(self, source, dest,
                                      source_start, dest_start, length):

pypy/rpython/memory/test/test_gc.py

         return self.smallint + x + 3
 
 
-class TestMarkSweepGC(GCTest):
-    from pypy.rpython.memory.gc.marksweep import MarkSweepGC as GCClass
-
-    def test_weakref_to_object_with_finalizer_ordering(self):
-        py.test.skip("Does not work")
-
 class TestSemiSpaceGC(GCTest, snippet.SemiSpaceGCTests):
     from pypy.rpython.memory.gc.semispace import SemiSpaceGC as GCClass
     GC_CAN_MOVE = True
 class TestGenerationalGC(TestSemiSpaceGC):
     from pypy.rpython.memory.gc.generation import GenerationGC as GCClass
 
-class TestMarkCompactGC(TestSemiSpaceGC):
-    from pypy.rpython.memory.gc.markcompact import MarkCompactGC as GCClass
-    GC_PARAMS = {'space_size': 65536+16384}
-    GC_CAN_SHRINK_ARRAY = False
-    GC_CAN_SHRINK_BIG_ARRAY = False
-
-    def test_finalizer_order(self):
-        py.test.skip("Not implemented yet")
-
 class TestHybridGC(TestGenerationalGC):
     from pypy.rpython.memory.gc.hybrid import HybridGC as GCClass
     GC_CAN_MALLOC_NONMOVABLE = True

pypy/rpython/memory/test/test_transformed_gc.py

         cls.rtyper = t.rtyper
         cls.db = db
 
-    def runner(self, name, statistics=False, transformer=False):
+    def runner(self, name, transformer=False):
         db = self.db
         name_to_func = self.name_to_func
         entrygraph = self.entrygraph
             res = llinterp.eval_graph(entrygraph, [ll_args])
             return res
 
-        if statistics:
-            statisticsgraph = gct.statistics_ptr.value._obj.graph
-            ll_gc = gct.c_const_gc.value
-            def statistics(index):
-                return llinterp.eval_graph(statisticsgraph, [ll_gc, index])
-            return run, statistics
-        elif transformer:
+        if transformer:
             return run, gct
         else:
             return run
 class GenericGCTests(GCTest):
     GC_CAN_SHRINK_ARRAY = False
 
-    def heap_usage(self, statistics):
-        try:
-            GCClass = self.gcpolicy.transformerclass.GCClass
-        except AttributeError:
-            from pypy.rpython.memory.gc.marksweep import MarkSweepGC as GCClass
-        if hasattr(GCClass, 'STAT_HEAP_USAGE'):
-            return statistics(GCClass.STAT_HEAP_USAGE)
-        else:
-            return -1     # xxx
-
     def define_instances(cls):
         class A(object):
             pass
         return malloc_a_lot
 
     def test_instances(self):
-        run, statistics = self.runner("instances", statistics=True)
+        run = self.runner("instances")
         run([])
-        heap_size = self.heap_usage(statistics)
 
 
     def define_llinterp_lists(cls):
         return malloc_a_lot
 
     def test_llinterp_lists(self):
-        run, statistics = self.runner("llinterp_lists", statistics=True)
+        run = self.runner("llinterp_lists")
         run([])
-        heap_size = self.heap_usage(statistics)
-        assert heap_size < 16000 * WORD / 4 # xxx
 
     def define_llinterp_tuples(cls):
         def malloc_a_lot():
         return malloc_a_lot
 
     def test_llinterp_tuples(self):
-        run, statistics = self.runner("llinterp_tuples", statistics=True)
+        run = self.runner("llinterp_tuples")
         run([])
-        heap_size = self.heap_usage(statistics)
-        assert heap_size < 16000 * WORD / 4 # xxx
 
     def define_llinterp_dict(self):
         class A(object):
         return concat
 
     def test_string_concatenation(self):
-        run, statistics = self.runner("string_concatenation", statistics=True)
+        run = self.runner("string_concatenation")
         res = run([100, 0])
         assert res == len(''.join([str(x) for x in range(100)]))
-        heap_size = self.heap_usage(statistics)
-        assert heap_size < 16000 * WORD / 4 # xxx
 
     def define_nongc_static_root(cls):
         T1 = lltype.GcStruct("C", ('x', lltype.Signed))
 
 # ________________________________________________________________
 
-class TestMarkSweepGC(GenericGCTests):
-    gcname = "marksweep"
-    class gcpolicy(gc.BasicFrameworkGcPolicy):
-        class transformerclass(shadowstack.ShadowStackFrameworkGCTransformer):
-            GC_PARAMS = {'start_heap_size': 1024*WORD,
-                         'translated_to_c': False}
-            root_stack_depth = 200
-
-
-class TestPrintingGC(GenericGCTests):
-    gcname = "statistics"
-
-    class gcpolicy(gc.BasicFrameworkGcPolicy):
-        class transformerclass(shadowstack.ShadowStackFrameworkGCTransformer):
-            from pypy.rpython.memory.gc.marksweep import PrintingMarkSweepGC as GCClass
-            GC_PARAMS = {'start_heap_size': 1024*WORD,
-                         'translated_to_c': False}
-            root_stack_depth = 200
-
 class TestSemiSpaceGC(GenericMovingGCTests):
     gcname = "semispace"
     GC_CAN_SHRINK_ARRAY = True
                          'translated_to_c': False}
             root_stack_depth = 200
 
-class TestMarkCompactGC(GenericMovingGCTests):
-    gcname = 'markcompact'
-
-    class gcpolicy(gc.BasicFrameworkGcPolicy):
-        class transformerclass(shadowstack.ShadowStackFrameworkGCTransformer):
-            from pypy.rpython.memory.gc.markcompact import MarkCompactGC as GCClass
-            GC_PARAMS = {'space_size': 4096*WORD,
-                         'translated_to_c': False}
-            root_stack_depth = 200
-
 class TestGenerationGC(GenericMovingGCTests):
     gcname = "generation"
     GC_CAN_SHRINK_ARRAY = True
         return self.smallint + x + 3
 
 
-class TestMarkSweepTaggedPointerGC(TaggedPointerGCTests):
-    gcname = "marksweep"
-    class gcpolicy(gc.BasicFrameworkGcPolicy):
-        class transformerclass(shadowstack.ShadowStackFrameworkGCTransformer):
-            GC_PARAMS = {'start_heap_size': 1024*WORD,
-                         'translated_to_c': False}
-            root_stack_depth = 200
-
 class TestHybridTaggedPointerGC(TaggedPointerGCTests):
     gcname = "hybrid"
 
                          'nursery_size': 32*WORD,
                          'translated_to_c': False}
             root_stack_depth = 200
-
-class TestMarkCompactTaggedpointerGC(TaggedPointerGCTests):
-    gcname = 'markcompact'
-
-    class gcpolicy(gc.BasicFrameworkGcPolicy):
-        class transformerclass(shadowstack.ShadowStackFrameworkGCTransformer):
-            from pypy.rpython.memory.gc.markcompact import MarkCompactGC as GCClass
-            GC_PARAMS = {'space_size': 4096*WORD,
-                         'translated_to_c': False}
-            root_stack_depth = 200

pypy/translator/c/test/test_newgc.py

 from pypy.translator.interactive import Translation
 
 
-class TestUsingFramework(object):
-    gcpolicy = "marksweep"
+class UsingFrameworkTest(object):
+    #gcpolicy = ... specified by subclasses
     should_be_moving = False
     removetypeptr = False
     taggedpointers = False
         self.run("gcflag_extra")
 
 
-class TestSemiSpaceGC(TestUsingFramework, snippet.SemiSpaceGCTestDefines):
+class TestSemiSpaceGC(UsingFrameworkTest, snippet.SemiSpaceGCTestDefines):
     gcpolicy = "semispace"
     should_be_moving = True
     GC_CAN_MOVE = True
     removetypeptr = True
 
 
-class TestMarkCompactGC(TestSemiSpaceGC):
-    gcpolicy = "markcompact"
-    should_be_moving = True
-    GC_CAN_SHRINK_ARRAY = False
-
-    def test_gc_set_max_heap_size(self):
-        py.test.skip("not implemented")
-
-    def test_gc_heap_stats(self):
-        py.test.skip("not implemented")
-
-    def test_finalizer_order(self):
-        py.test.skip("not implemented")
-
-    def define_adding_a_hash(cls):
-        from pypy.rlib.objectmodel import compute_identity_hash
-        S1 = lltype.GcStruct('S1', ('x', lltype.Signed))
-        S2 = lltype.GcStruct('S2', ('p1', lltype.Ptr(S1)),
-                                   ('p2', lltype.Ptr(S1)),
-                                   ('p3', lltype.Ptr(S1)),
-                                   ('p4', lltype.Ptr(S1)),
-                                   ('p5', lltype.Ptr(S1)),
-                                   ('p6', lltype.Ptr(S1)),
-                                   ('p7', lltype.Ptr(S1)),
-                                   ('p8', lltype.Ptr(S1)),
-                                   ('p9', lltype.Ptr(S1)))
-        def g():
-            lltype.malloc(S1)   # forgotten, will be shifted over
-            s2 = lltype.malloc(S2)   # a big object, overlaps its old position
-            s2.p1 = lltype.malloc(S1); s2.p1.x = 1010
-            s2.p2 = lltype.malloc(S1); s2.p2.x = 1020
-            s2.p3 = lltype.malloc(S1); s2.p3.x = 1030
-            s2.p4 = lltype.malloc(S1); s2.p4.x = 1040
-            s2.p5 = lltype.malloc(S1); s2.p5.x = 1050
-            s2.p6 = lltype.malloc(S1); s2.p6.x = 1060
-            s2.p7 = lltype.malloc(S1); s2.p7.x = 1070
-            s2.p8 = lltype.malloc(S1); s2.p8.x = 1080
-            s2.p9 = lltype.malloc(S1); s2.p9.x = 1090
-            return s2
-        def f():
-            rgc.collect()
-            s2 = g()
-            h2 = compute_identity_hash(s2)
-            rgc.collect()    # shift s2 to the left, but add a hash field
-            assert s2.p1.x == 1010
-            assert s2.p2.x == 1020
-            assert s2.p3.x == 1030
-            assert s2.p4.x == 1040
-            assert s2.p5.x == 1050
-            assert s2.p6.x == 1060
-            assert s2.p7.x == 1070
-            assert s2.p8.x == 1080
-            assert s2.p9.x == 1090
-            return h2 - compute_identity_hash(s2)
-        return f
-
-    def test_adding_a_hash(self):
-        res = self.run("adding_a_hash")
-        assert res == 0
-
-
 class TestMiniMarkGC(TestSemiSpaceGC):
     gcpolicy = "minimark"
     should_be_moving = True
     pass
 
 
-class TestMarkCompactGCMostCompact(TaggedPointersTest, TestMarkCompactGC):
-    removetypeptr = True
-
-
 class TestMiniMarkGCMostCompact(TaggedPointersTest, TestMiniMarkGC):
     removetypeptr = True