text: 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, get_address_deque
  from pypy.rpython.memory.support import AddressDict
  from pypy.rpython.lltypesystem import lltype, llmemory, llarena, rffi, llgroup
  from pypy.rlib.objectmodel import free_non_gc_object
  from pypy.rlib.debug import ll_assert, have_debug_prints
  from pypy.rlib.debug import debug_print, debug_start, debug_stop
  from pypy.rpython.lltypesystem.lloperation import llop
  from pypy.rlib.rarithmetic import ovfcheck, LONG_BIT
  from pypy.rpython.memory.gc.base import MovingGCBase, ARRAY_TYPEID_MAP,\
       TYPEID_MAP
  
  import sys, os
  
  first_gcflag = 1 << (LONG_BIT//2)
  GCFLAG_FORWARDED = first_gcflag
  # GCFLAG_EXTERNAL is set on objects not living in the semispace:
  # either immortal objects or (for HybridGC) externally raw_malloc'ed
  GCFLAG_EXTERNAL = first_gcflag << 1
  GCFLAG_FINALIZATION_ORDERING = first_gcflag << 2
  
  _GCFLAG_HASH_BASE = first_gcflag << 3
  GCFLAG_HASHMASK = _GCFLAG_HASH_BASE * 0x3   # also consumes 'first_gcflag << 4'
  # the two bits in GCFLAG_HASHMASK can have one of the following values:
  #   - nobody ever asked for the hash of the object
  GC_HASH_NOTTAKEN   = _GCFLAG_HASH_BASE * 0x0
  #   - someone asked, and we gave the address of the object
  GC_HASH_TAKEN_ADDR = _GCFLAG_HASH_BASE * 0x1
  #   - someone asked, and we gave the address plus 'nursery_hash_base'
  GC_HASH_TAKEN_NURS = _GCFLAG_HASH_BASE * 0x2
  #   - we have our own extra field to store the hash
  GC_HASH_HASFIELD   = _GCFLAG_HASH_BASE * 0x3
  
  memoryError = MemoryError()
  
  
  class SemiSpaceGC(MovingGCBase):
      _alloc_flavor_ = "raw"
      inline_simple_malloc = True
      inline_simple_malloc_varsize = True
      malloc_zero_filled = True
      first_unused_gcflag = first_gcflag << 5
      gcflag_extra = GCFLAG_FINALIZATION_ORDERING
  
      HDR = lltype.Struct('header', ('tid', lltype.Signed))   # XXX or rffi.INT?
      typeid_is_in_field = 'tid'
      withhash_flag_is_in_field = 'tid', _GCFLAG_HASH_BASE * 0x2
      # ^^^ prebuilt objects either have GC_HASH_TAKEN_ADDR or they
      #     have GC_HASH_HASFIELD (and then they are one word longer).
      FORWARDSTUB = lltype.GcStruct('forwarding_stub',
                                    ('forw', llmemory.Address))
      FORWARDSTUBPTR = lltype.Ptr(FORWARDSTUB)
  
      object_minimal_size = llmemory.sizeof(FORWARDSTUB)
  
      # the following values override the default arguments of __init__ when
      # translating to a real backend.
      TRANSLATION_PARAMS = {'space_size': 8*1024*1024} # XXX adjust
  
      def __init__(self, config, space_size=4096, max_space_size=sys.maxint//2+1,
                   **kwds):
          self.param_space_size = space_size
          self.param_max_space_size = max_space_size
          MovingGCBase.__init__(self, config, **kwds)
  
      def setup(self):
          #self.total_collection_time = 0.0
          self.total_collection_count = 0
  
          self.space_size = self.param_space_size
          self.max_space_size = self.param_max_space_size
          self.red_zone = 0
  
          #self.program_start_time = time.time()
          self.tospace = llarena.arena_malloc(self.space_size, True)
          ll_assert(bool(self.tospace), "couldn't allocate tospace")
          self.top_of_space = self.tospace + self.space_size
          self.fromspace = llarena.arena_malloc(self.space_size, True)
          ll_assert(bool(self.fromspace), "couldn't allocate fromspace")
          self.free = self.tospace
          MovingGCBase.setup(self)
          self.objects_with_finalizers = self.AddressDeque()
          self.objects_with_light_finalizers = self.AddressStack()
          self.objects_with_weakrefs = self.AddressStack()
  
      def _teardown(self):
          debug_print("Teardown")
          llarena.arena_free(self.fromspace)
          llarena.arena_free(self.tospace)
  
      # This class only defines the malloc_{fixed,var}size_clear() methods
      # because the spaces are filled with zeroes in advance.
  
      def malloc_fixedsize_clear(self, typeid16, size,
                                 has_finalizer=False,
                                 is_finalizer_light=False,
                                 contains_weakptr=False):
          size_gc_header = self.gcheaderbuilder.size_gc_header
          totalsize = size_gc_header + size
          result = self.free
          if raw_malloc_usage(totalsize) > self.top_of_space - result:
              result = self.obtain_free_space(totalsize)
          llarena.arena_reserve(result, totalsize)
          self.init_gc_object(result, typeid16)
          self.free = result + totalsize
          #if is_finalizer_light:
          #    self.objects_with_light_finalizers.append(result + size_gc_header)
          #else:
          if has_finalizer:
              self.objects_with_finalizers.append(result + size_gc_header)
          if contains_weakptr:
              self.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, typeid16, length, size, itemsize,
                               offset_to_length):
          size_gc_header = self.gcheaderbuilder.size_gc_header
          nonvarsize = size_gc_header + size
          try:
              varsize = ovfcheck(itemsize * length)
              totalsize = ovfcheck(nonvarsize + varsize)
          except OverflowError:
              raise memoryError
          result = self.free
          if raw_malloc_usage(totalsize) > self.top_of_space - result:
              result = self.obtain_free_space(totalsize)
          llarena.arena_reserve(result, totalsize)
          self.init_gc_object(result, typeid16)
          (result + size_gc_header + offset_to_length).signed[0] = length
          self.free = result + llarena.round_up_for_allocation(totalsize)
          return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)
  
      def shrink_array(self, addr, smallerlength):
          size_gc_header = self.gcheaderbuilder.size_gc_header
          if self._is_in_the_space(addr - size_gc_header):
              typeid = self.get_type_id(addr)
              totalsmallersize = (
                  size_gc_header + self.fixed_size(typeid) +
                  self.varsize_item_sizes(typeid) * smallerlength)
              llarena.arena_shrink_obj(addr - size_gc_header, totalsmallersize)
              #
              offset_to_length = self.varsize_offset_to_length(typeid)
              (addr + offset_to_length).signed[0] = smallerlength
              return True
          else:
              return False
  
      def obtain_free_space(self, needed):
          # a bit of tweaking to maximize the performance and minimize the
          # amount of code in an inlined version of malloc_fixedsize_clear()
          if not self.try_obtain_free_space(needed):
              raise memoryError
          return self.free
      obtain_free_space._dont_inline_ = True
  
      def try_obtain_free_space(self, needed):
          # XXX for bonus points do big objects differently
          needed = raw_malloc_usage(needed)
          if (self.red_zone >= 2 and self.space_size < self.max_space_size and
              self.double_space_size()):
              pass    # collect was done during double_space_size()
          else:
              self.semispace_collect()
          missing = needed - (self.top_of_space - self.free)
          if missing <= 0:
              return True      # success
          else:
              # first check if the object could possibly fit
              proposed_size = self.space_size
              while missing > 0:
                  if proposed_size >= self.max_space_size:
                      return False    # no way
                  missing -= proposed_size
                  proposed_size *= 2
              # For address space fragmentation reasons, we double the space
              # size possibly several times, moving the objects at each step,
              # instead of going directly for the final size.  We assume that
              # it's a rare case anyway.
              while self.space_size < proposed_size:
                  if not self.double_space_size():
                      return False
              ll_assert(needed <= self.top_of_space - self.free,
                           "double_space_size() failed to do its job")
              return True
  
      def double_space_size(self):
          self.red_zone = 0
          old_fromspace = self.fromspace
          newsize = self.space_size * 2
          newspace = llarena.arena_malloc(newsize, True)
          if not newspace:
              return False    # out of memory
          llarena.arena_free(old_fromspace)
          self.fromspace = newspace
          # now self.tospace contains the existing objects and
          # self.fromspace is the freshly allocated bigger space
  
          self.semispace_collect(size_changing=True)
          self.top_of_space = self.tospace + newsize
          # now self.tospace is the freshly allocated bigger space,
          # and self.fromspace is the old smaller space, now empty
          llarena.arena_free(self.fromspace)
  
          newspace = llarena.arena_malloc(newsize, True)
          if not newspace:
              # Complex failure case: we have in self.tospace a big chunk
              # of memory, and the two smaller original spaces are already gone.
              # Unsure if it's worth these efforts, but we can artificially
              # split self.tospace in two again...
              self.max_space_size = self.space_size    # don't try to grow again,
              #              because doing arena_free(self.fromspace) would crash
              self.fromspace = self.tospace + self.space_size
              self.top_of_space = self.fromspace
              ll_assert(self.free <= self.top_of_space,
                           "unexpected growth of GC space usage during collect")
              return False     # out of memory
  
          self.fromspace = newspace
          self.space_size = newsize
          return True    # success
  
      def set_max_heap_size(self, size):
          # Set the maximum semispace size.
          # The size is rounded down to the next power of two.  Also, this is
          # the size of one semispace only, so actual usage can be the double
          # during a collection.  Finally, note that this will never shrink
          # an already-allocated heap.
          if size < 1:
              size = 1     # actually, the minimum is 8MB in default translations
          self.max_space_size = sys.maxint//2+1
          while self.max_space_size > size:
              self.max_space_size >>= 1
  
      @classmethod
      def JIT_minimal_size_in_nursery(cls):
          return cls.object_minimal_size
  
      def collect(self, gen=0):
          self.debug_check_consistency()
          self.semispace_collect()
          # the indirection is required by the fact that collect() is referred
          # to by the gc transformer, and the default argument would crash
          # (this is also a hook for the HybridGC)
  
      def semispace_collect(self, size_changing=False):
          debug_start("gc-collect")
          debug_print()
          debug_print(".----------- Full collection ------------------")
          start_usage = self.free - self.tospace
          debug_print("| used before collection:          ",
                      start_usage, "bytes")
          #start_time = time.time()
          #llop.debug_print(lltype.Void, 'semispace_collect', int(size_changing))
  
          # Switch the spaces.  We copy everything over to the empty space
          # (self.fromspace at the beginning of the collection), and clear the old
          # one (self.tospace at the beginning).  Their purposes will be reversed
          # for the next collection.
          tospace = self.fromspace
          fromspace = self.tospace
          self.fromspace = fromspace
          self.tospace = tospace
          self.top_of_space = tospace + self.space_size
          scan = self.free = tospace
          self.starting_full_collect()
          self.collect_roots()
          if self.run_finalizers.non_empty():
              self.update_run_finalizers()
          scan = self.scan_copied(scan)
          if self.objects_with_light_finalizers.non_empty():
              self.deal_with_objects_with_light_finalizers()
          if self.objects_with_finalizers.non_empty():
              scan = self.deal_with_objects_with_finalizers(scan)
          if self.objects_with_weakrefs.non_empty():
              self.invalidate_weakrefs()
          self.update_objects_with_id()
          self.finished_full_collect()
          self.debug_check_consistency()
          if not size_changing:
              llarena.arena_reset(fromspace, self.space_size, True)
              self.record_red_zone()
              self.execute_finalizers()
          #llop.debug_print(lltype.Void, 'collected', self.space_size, size_changing, self.top_of_space - self.free)
          if have_debug_prints():
              #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
              end_usage = self.free - self.tospace
              debug_print("| used after collection:           ",
                          end_usage, "bytes")
              debug_print("| freed:                           ",
                          start_usage - end_usage, "bytes")
              debug_print("| size of each semispace:          ",
                          self.space_size, "bytes")
              debug_print("| fraction of semispace now used:  ",
                          end_usage * 100.0 / self.space_size, "%")
              #ct = self.total_collection_time
              cc = self.total_collection_count
              debug_print("| number of semispace_collects:    ",
                          cc)
              #debug_print("|                         i.e.:    ",
              #            cc / total_program_time, "per second")
              #debug_print("| total time in semispace_collect: ",
              #            ct, "seconds")
              #debug_print("|                            i.e.: ",
              #            ct * 100.0 / total_program_time, "%")
              debug_print("`----------------------------------------------")
          debug_stop("gc-collect")
  
      def starting_full_collect(self):
          pass    # hook for the HybridGC
  
      def finished_full_collect(self):
          pass    # hook for the HybridGC
  
      def record_red_zone(self):
          # red zone: if the space is more than 80% full, the next collection
          # should double its size.  If it is more than 66% full twice in a row,
          # then it should double its size too.  (XXX adjust)
          # The goal is to avoid many repeated collection that don't free a lot
          # of memory each, if the size of the live object set is just below the
          # size of the space.
          free_after_collection = self.top_of_space - self.free
          if free_after_collection > self.space_size // 3:
              self.red_zone = 0
          else:
              self.red_zone += 1
              if free_after_collection < self.space_size // 5:
                  self.red_zone += 1
  
      def get_size_incl_hash(self, obj):
          size = self.get_size(obj)
          hdr = self.header(obj)
          if (hdr.tid & GCFLAG_HASHMASK) == GC_HASH_HASFIELD:
              size += llmemory.sizeof(lltype.Signed)
          return size
  
      def scan_copied(self, scan):
          while scan < self.free:
              curr = scan + self.size_gc_header()
              self.trace_and_copy(curr)
              scan += self.size_gc_header() + self.get_size_incl_hash(curr)
          return scan
  
      def collect_roots(self):
          self.root_walker.walk_roots(
              SemiSpaceGC._collect_root,  # stack roots
              SemiSpaceGC._collect_root,  # static in prebuilt non-gc structures
              SemiSpaceGC._collect_root)  # static in prebuilt gc objects
  
      def _collect_root(self, root):
          root.address[0] = self.copy(root.address[0])
  
      def copy(self, obj):
          if self.DEBUG:
              self.debug_check_can_copy(obj)
          if self.is_forwarded(obj):
              #llop.debug_print(lltype.Void, obj, "already copied to", self.get_forwarding_address(obj))
              return self.get_forwarding_address(obj)
          else:
              objsize = self.get_size(obj)
              newobj = self.make_a_copy(obj, objsize)
              #llop.debug_print(lltype.Void, obj, "copied to", newobj,
              #                 "tid", self.header(obj).tid,
              #                 "size", totalsize)
              self.set_forwarding_address(obj, newobj, objsize)
              return newobj
  
      def _get_object_hash(self, obj, objsize, tid):
          # Returns the hash of the object, which must not be GC_HASH_NOTTAKEN.
          gc_hash = tid & GCFLAG_HASHMASK
          if gc_hash == GC_HASH_HASFIELD:
              obj = llarena.getfakearenaaddress(obj)
              return (obj + objsize).signed[0]
          elif gc_hash == GC_HASH_TAKEN_ADDR:
              return llmemory.cast_adr_to_int(obj)
          elif gc_hash == GC_HASH_TAKEN_NURS:
              return self._compute_current_nursery_hash(obj)
          else:
              assert 0, "gc_hash == GC_HASH_NOTTAKEN"
  
      def _make_a_copy_with_tid(self, obj, objsize, tid):
          totalsize = self.size_gc_header() + objsize
          newaddr = self.free
          llarena.arena_reserve(newaddr, totalsize)
          raw_memcopy(obj - self.size_gc_header(), newaddr, totalsize)
          if tid & GCFLAG_HASHMASK:
              hash = self._get_object_hash(obj, objsize, tid)
              llarena.arena_reserve(newaddr + totalsize,
                                    llmemory.sizeof(lltype.Signed))
              (newaddr + totalsize).signed[0] = hash
              tid |= GC_HASH_HASFIELD
              totalsize += llmemory.sizeof(lltype.Signed)
          self.free += totalsize
          newhdr = llmemory.cast_adr_to_ptr(newaddr, lltype.Ptr(self.HDR))
          newhdr.tid = tid
          newobj = newaddr + self.size_gc_header()
          return newobj
  
      def make_a_copy(self, obj, objsize):
          tid = self.header(obj).tid
          return self._make_a_copy_with_tid(obj, objsize, tid)
  
      def trace_and_copy(self, obj):
          self.trace(obj, self._trace_copy, None)
  
      def _trace_copy(self, pointer, ignored):
          pointer.address[0] = self.copy(pointer.address[0])
  
      def surviving(self, obj):
          # To use during a collection.  Check if the object is currently
          # marked as surviving the collection.  This is equivalent to
          # self.is_forwarded() for all objects except the nonmoving objects
          # created by the HybridGC subclass.  In all cases, if an object
          # survives, self.get_forwarding_address() returns its new address.
          return self.is_forwarded(obj)
  
      def is_forwarded(self, obj):
          return self.header(obj).tid & GCFLAG_FORWARDED != 0
          # note: all prebuilt objects also have this flag set
  
      def get_forwarding_address(self, obj):
          tid = self.header(obj).tid
          if tid & GCFLAG_EXTERNAL:
              self.visit_external_object(obj)
              return obj      # external or prebuilt objects are "forwarded"
                              # to themselves
          else:
              stub = llmemory.cast_adr_to_ptr(obj, self.FORWARDSTUBPTR)
              return stub.forw
  
      def visit_external_object(self, obj):
          pass    # hook for the HybridGC
  
      def set_forwarding_address(self, obj, newobj, objsize):
          # To mark an object as forwarded, we set the GCFLAG_FORWARDED and
          # overwrite the object with a FORWARDSTUB.  Doing so is a bit
          # long-winded on llarena, but it all melts down to two memory
          # writes after translation to C.
          size_gc_header = self.size_gc_header()
          stubsize = llmemory.sizeof(self.FORWARDSTUB)
          tid = self.header(obj).tid
          ll_assert(tid & GCFLAG_EXTERNAL == 0,  "unexpected GCFLAG_EXTERNAL")
          ll_assert(tid & GCFLAG_FORWARDED == 0, "unexpected GCFLAG_FORWARDED")
          # replace the object at 'obj' with a FORWARDSTUB.
          hdraddr = obj - size_gc_header
          llarena.arena_reset(hdraddr, size_gc_header + objsize, False)
          llarena.arena_reserve(hdraddr, size_gc_header + stubsize)
          hdr = llmemory.cast_adr_to_ptr(hdraddr, lltype.Ptr(self.HDR))
          hdr.tid = tid | GCFLAG_FORWARDED
          stub = llmemory.cast_adr_to_ptr(obj, self.FORWARDSTUBPTR)
          stub.forw = newobj
  
      def combine(self, typeid16, flags):
          return llop.combine_ushort(lltype.Signed, typeid16, flags)
  
      def get_type_id(self, addr):
          tid = self.header(addr).tid
          ll_assert(tid & (GCFLAG_FORWARDED|GCFLAG_EXTERNAL) != GCFLAG_FORWARDED,
                    "get_type_id on forwarded obj")
          # Non-prebuilt forwarded objects are overwritten with a FORWARDSTUB.
          # Although calling get_type_id() on a forwarded object works by itself,
          # we catch it as an error because it's likely that what is then
          # done with the typeid is bogus.
          return llop.extract_ushort(llgroup.HALFWORD, tid)
  
      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_EXTERNAL | GCFLAG_FORWARDED | GC_HASH_TAKEN_ADDR
          hdr.tid = self.combine(typeid16, flags)
          # immortal objects always have GCFLAG_FORWARDED set;
          # see get_forwarding_address().
  
      def deal_with_objects_with_light_finalizers(self):
          """ This is a much simpler version of dealing with finalizers
          and an optimization - we can reasonably assume that those finalizers
          don't do anything fancy and *just* call them. Among other things
          they won't resurrect objects
          """
          new_objects = self.AddressStack()
          while self.objects_with_light_finalizers.non_empty():
              obj = self.objects_with_light_finalizers.pop()
              if self.surviving(obj):
                  new_objects.append(self.get_forwarding_address(obj))
              else:
                  finalizer = self.getfinalizer(self.get_type_id(obj))
                  finalizer(obj, llmemory.NULL)
          self.objects_with_light_finalizers.delete()
          self.objects_with_light_finalizers = new_objects
  
      def deal_with_objects_with_finalizers(self, scan):
          # walk over list of objects with finalizers
          # if it is not copied, add it to the list of to-be-called finalizers
          # and copy it, to me make the finalizer runnable
          # We try to run the finalizers in a "reasonable" order, like
          # CPython does.  The details of this algorithm are in
          # pypy/doc/discussion/finalizer-order.txt.
          new_with_finalizer = self.AddressDeque()
          marked = self.AddressDeque()
          pending = self.AddressStack()
          self.tmpstack = self.AddressStack()
          while self.objects_with_finalizers.non_empty():
              x = self.objects_with_finalizers.popleft()
              ll_assert(self._finalization_state(x) != 1, 
                        "bad finalization state 1")
              if self.surviving(x):
                  new_with_finalizer.append(self.get_forwarding_address(x))
                  continue
              marked.append(x)
              pending.append(x)
              while pending.non_empty():
                  y = pending.pop()
                  state = self._finalization_state(y)
                  if state == 0:
                      self._bump_finalization_state_from_0_to_1(y)
                      self.trace(y, self._append_if_nonnull, pending)
                  elif state == 2:
                      self._recursively_bump_finalization_state_from_2_to_3(y)
              scan = self._recursively_bump_finalization_state_from_1_to_2(
                         x, scan)
  
          while marked.non_empty():
              x = marked.popleft()
              state = self._finalization_state(x)
              ll_assert(state >= 2, "unexpected finalization state < 2")
              newx = self.get_forwarding_address(x)
              if state == 2:
                  self.run_finalizers.append(newx)
                  # we must also fix the state from 2 to 3 here, otherwise
                  # we leave the GCFLAG_FINALIZATION_ORDERING bit behind
                  # which will confuse the next collection
                  self._recursively_bump_finalization_state_from_2_to_3(x)
              else:
                  new_with_finalizer.append(newx)
  
          self.tmpstack.delete()
          pending.delete()
          marked.delete()
          self.objects_with_finalizers.delete()
          self.objects_with_finalizers = new_with_finalizer
          return scan
  
      def _append_if_nonnull(pointer, stack):
          stack.append(pointer.address[0])
      _append_if_nonnull = staticmethod(_append_if_nonnull)
  
      def _finalization_state(self, obj):
          if self.surviving(obj):
              newobj = self.get_forwarding_address(obj)
              hdr = self.header(newobj)
              if hdr.tid & GCFLAG_FINALIZATION_ORDERING:
                  return 2
              else:
                  return 3
          else:
              hdr = self.header(obj)
              if hdr.tid & GCFLAG_FINALIZATION_ORDERING:
                  return 1
              else:
                  return 0
  
      def _bump_finalization_state_from_0_to_1(self, obj):
          ll_assert(self._finalization_state(obj) == 0,
                    "unexpected finalization state != 0")
          hdr = self.header(obj)
          hdr.tid |= GCFLAG_FINALIZATION_ORDERING
  
      def _recursively_bump_finalization_state_from_2_to_3(self, obj):
          ll_assert(self._finalization_state(obj) == 2,
                    "unexpected finalization state != 2")
          newobj = self.get_forwarding_address(obj)
          pending = self.tmpstack
          ll_assert(not pending.non_empty(), "tmpstack not empty")
          pending.append(newobj)
          while pending.non_empty():
              y = pending.pop()
              hdr = self.header(y)
              if hdr.tid & GCFLAG_FINALIZATION_ORDERING:     # state 2 ?
                  hdr.tid &= ~GCFLAG_FINALIZATION_ORDERING   # change to state 3
                  self.trace(y, self._append_if_nonnull, pending)
  
      def _recursively_bump_finalization_state_from_1_to_2(self, obj, scan):
          # recursively convert objects from state 1 to state 2.
          # Note that copy() copies all bits, including the
          # GCFLAG_FINALIZATION_ORDERING.  The mapping between
          # state numbers and the presence of this bit was designed
          # for the following to work :-)
          self.copy(obj)
          return self.scan_copied(scan)
  
      def invalidate_weakrefs(self):
          # walk over list of objects that contain weakrefs
          # if the object it references survives then update the weakref
          # otherwise invalidate the weakref
          new_with_weakref = self.AddressStack()
          while self.objects_with_weakrefs.non_empty():
              obj = self.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]
              # XXX I think that pointing_to cannot be NULL here
              if pointing_to:
                  if self.surviving(pointing_to):
                      (obj + offset).address[0] = self.get_forwarding_address(
                          pointing_to)
                      new_with_weakref.append(obj)
                  else:
                      (obj + offset).address[0] = NULL
          self.objects_with_weakrefs.delete()
          self.objects_with_weakrefs = new_with_weakref
  
      def update_run_finalizers(self):
          # we are in an inner collection, caused by a finalizer
          # the run_finalizers objects need to be copied
          new_run_finalizer = self.AddressDeque()
          while self.run_finalizers.non_empty():
              obj = self.run_finalizers.popleft()
              new_run_finalizer.append(self.copy(obj))
          self.run_finalizers.delete()
          self.run_finalizers = new_run_finalizer
  
      def _is_external(self, obj):
          return (self.header(obj).tid & GCFLAG_EXTERNAL) != 0
  
      def _is_in_the_space(self, obj):
          return self.tospace <= obj < self.free
  
      def debug_check_object(self, obj):
          """Check the invariants about 'obj' that should be true
          between collections."""
          tid = self.header(obj).tid
          if tid & GCFLAG_EXTERNAL:
              ll_assert(tid & GCFLAG_FORWARDED != 0, "bug: external+!forwarded")
              ll_assert(not (self.tospace <= obj < self.free),
                        "external flag but object inside the semispaces")
          else:
              ll_assert(not (tid & GCFLAG_FORWARDED), "bug: !external+forwarded")
              ll_assert(self.tospace <= obj < self.free,
                        "!external flag but object outside the semispaces")
          ll_assert(not (tid & GCFLAG_FINALIZATION_ORDERING),
                    "unexpected GCFLAG_FINALIZATION_ORDERING")
  
      def debug_check_can_copy(self, obj):
          ll_assert(not (self.tospace <= obj < self.free),
                    "copy() on already-copied object")
  
      STATISTICS_NUMBERS = 0
  
      def is_in_nursery(self, addr):
          # overridden in generation.py.
          return False
  
      def _compute_current_nursery_hash(self, obj):
          # overridden in generation.py.
          raise AssertionError("should not be called")
  
      def identityhash(self, gcobj):
          # The following loop should run at most twice.
          while 1:
              obj = llmemory.cast_ptr_to_adr(gcobj)
              hdr = self.header(obj)
              if hdr.tid & GCFLAG_HASHMASK:
                  break
              # It's the first time we ask for a hash, and it's not an
              # external object.  Shrink the top of space by the extra
              # hash word that will be needed after a collect.
              shrunk_top = self.top_of_space - llmemory.sizeof(lltype.Signed)
              if shrunk_top < self.free:
                  # Cannot shrink!  Do a collection, asking for at least
                  # one word of free space, and try again.  May raise
                  # MemoryError.  Obscure: not called directly, but
                  # across an llop, to make sure that there is the
                  # correct push_roots/pop_roots around the call...
                  llop.gc_obtain_free_space(llmemory.Address,
                                            llmemory.sizeof(lltype.Signed))
                  continue
              else:
                  # Now we can have side-effects: lower the top of space
                  # and set one of the GC_HASH_TAKEN_xxx flags.
                  self.top_of_space = shrunk_top
                  if self.is_in_nursery(obj):
                      hdr.tid |= GC_HASH_TAKEN_NURS
                  else:
                      hdr.tid |= GC_HASH_TAKEN_ADDR
                  break
          # Now we can return the result
          objsize = self.get_size(obj)
          return self._get_object_hash(obj, objsize, hdr.tid)
  
      def track_heap_parent(self, obj, parent):
          addr = obj.address[0]
          parent_idx = llop.get_member_index(lltype.Signed,
                                             self.get_type_id(parent))
          idx = llop.get_member_index(lltype.Signed, self.get_type_id(addr))
          self._ll_typeid_map[parent_idx].links[idx] += 1
          self.track_heap(addr)
  
      def track_heap(self, adr):
          if self._tracked_dict.contains(adr):
              return
          self._tracked_dict.add(adr)
          idx = llop.get_member_index(lltype.Signed, self.get_type_id(adr))
          self._ll_typeid_map[idx].count += 1
          totsize = self.get_size(adr) + self.size_gc_header()
          self._ll_typeid_map[idx].size += llmemory.raw_malloc_usage(totsize)
          self.trace(adr, self.track_heap_parent, adr)
  
      @staticmethod
      def _track_heap_root(obj, self):
          self.track_heap(obj)
  
      def heap_stats(self):
          self._tracked_dict = self.AddressDict()
          max_tid = self.root_walker.gcdata.max_type_id
          ll_typeid_map = lltype.malloc(ARRAY_TYPEID_MAP, max_tid, zero=True)
          for i in range(max_tid):
              ll_typeid_map[i] = lltype.malloc(TYPEID_MAP, max_tid, zero=True)
          self._ll_typeid_map = ll_typeid_map
          self._tracked_dict.add(llmemory.cast_ptr_to_adr(ll_typeid_map))
          i = 0
          while i < max_tid:
              self._tracked_dict.add(llmemory.cast_ptr_to_adr(ll_typeid_map[i]))
              i += 1
          self.enumerate_all_roots(SemiSpaceGC._track_heap_root, self)
          self._ll_typeid_map = lltype.nullptr(ARRAY_TYPEID_MAP)
          self._tracked_dict.delete()
          return ll_typeid_map
  