def estimate_best_nursery_size():
     """Try to estimate the best nursery size at run-time, depending
     on the machine we are running on.
     """
     L2cache = 0
     l2cache_p = lltype.malloc(rffi.LONGLONGP.TO, 1, flavor='raw')
     try:
         len_p = lltype.malloc(rffi.SIZE_TP.TO, 1, flavor='raw')
         try:
             size = rffi.sizeof(rffi.LONGLONG)
             l2cache_p[0] = rffi.cast(rffi.LONGLONG, 0)
             len_p[0] = rffi.cast(rffi.SIZE_T, size)
             result = sysctlbyname("hw.l2cachesize",
                                   rffi.cast(rffi.VOIDP, l2cache_p),
                                   len_p,
                                   lltype.nullptr(rffi.VOIDP.TO), 
                                   rffi.cast(rffi.SIZE_T, 0))
             if (rffi.cast(lltype.Signed, result) == 0 and
                 rffi.cast(lltype.Signed, len_p[0]) == size):
                 L2cache = rffi.cast(lltype.Signed, l2cache_p[0])
                 if rffi.cast(rffi.LONGLONG, L2cache) != l2cache_p[0]:
                     L2cache = 0    # overflow!
         finally:
             lltype.free(len_p, flavor='raw')
     finally:
         lltype.free(l2cache_p, flavor='raw')
     if L2cache > 0:
         return best_nursery_size_for_L2cache(L2cache)
     else:
         # Print a warning even in non-debug builds
         llop.debug_print(lltype.Void,
             "Warning: cannot find your CPU L2 cache size with sysctl()")
         return -1

 def collect_nursery(self):
     if self.nursery_size > self.top_of_space - self.free:
         # the semispace is running out, do a full collect
         self.obtain_free_space(self.nursery_size)
         ll_assert(self.nursery_size <= self.top_of_space - self.free,
                      "obtain_free_space failed to do its job")
     if self.nursery:
         if DEBUG_PRINT:
             llop.debug_print(lltype.Void, "minor collect")
         # a nursery-only collection
         scan = beginning = self.free
         self.collect_oldrefs_to_nursery()
         self.collect_roots_in_nursery()
         scan = self.scan_objects_just_copied_out_of_nursery(scan)
         # at this point, all static and old objects have got their
         # GCFLAG_NO_YOUNG_PTRS set again by trace_and_drag_out_of_nursery
         if self.young_objects_with_weakrefs.non_empty():
             self.invalidate_young_weakrefs()
         self.notify_objects_just_moved()
         # mark the nursery as free and fill it with zeroes again
         llarena.arena_reset(self.nursery, self.nursery_size, True)
         if DEBUG_PRINT:
             llop.debug_print(lltype.Void, "percent survived:", float(scan - beginning) / self.nursery_size)
     else:
         # no nursery - this occurs after a full collect, triggered either
         # just above or by some previous non-nursery-based allocation.
         # Grab a piece of the current space for the nursery.
         self.nursery = self.free
         self.nursery_top = self.nursery + self.nursery_size
         self.free = self.nursery_top
     self.nursery_free = self.nursery
     return self.nursery_free

        def do_call(result, path, index, remaining_depth):
            # clone the while path
            clonedata.gcobjectptr = lltype.cast_opaque_ptr(llmemory.GCREF,
                                                           path)
            clonedata.pool = lltype.nullptr(X_POOL)
            llop.gc_x_clone(lltype.Void, clonedata)
            # install the new pool as the current one
            parentpool = llop.gc_x_swap_pool(X_POOL_PTR, clonedata.pool)
            path = lltype.cast_opaque_ptr(lltype.Ptr(NODE),
                                          clonedata.gcobjectptr)

            # The above should have the same effect as:
            #    path = clone(path)

            # bump all the path node counters by one
            p = path
            while p:
                p.counter += 1
                p = p.next

            if remaining_depth == 0:
                llop.debug_print(lltype.Void, "setting", index, "with", path)
                result[index] = path   # leaf
            else:
                node = lltype.malloc(NODE)
                node.index = index * 2
                node.counter = 0
                node.next = path
                do_call(result, node, index * 2, remaining_depth - 1)
                node.index += 1    # mutation!
                do_call(result, node, index * 2 + 1, remaining_depth - 1)

            # restore the parent pool
            llop.gc_x_swap_pool(X_POOL_PTR, parentpool)

 def debug_collect_start(self):
     if self.config.gcconfig.debugprint:
         llop.debug_print(lltype.Void)
         llop.debug_print(lltype.Void,
                          ".----------- Full collection ------------------")
         start_time = time.time()
         return start_time 

def get_L2cache_linux2(filename="/proc/cpuinfo"):
    debug_start("gc-hardware")
    L2cache = sys.maxint
    try:
        fd = os.open(filename, os.O_RDONLY, 0644)
        try:
            data = []
            while True:
                buf = os.read(fd, 4096)
                if not buf:
                    break
                data.append(buf)
        finally:
            os.close(fd)
    except OSError:
        pass
    else:
        data = ''.join(data)
        linepos = 0
        while True:
            start = _findend(data, '\ncache size', linepos)
            if start < 0:
                break    # done
            linepos = _findend(data, '\n', start)
            if linepos < 0:
                break    # no end-of-line??
            # *** data[start:linepos] == "   : 2048 KB\n"
            start = _skipspace(data, start)
            if data[start] != ':':
                continue
            # *** data[start:linepos] == ": 2048 KB\n"
            start = _skipspace(data, start + 1)
            # *** data[start:linepos] == "2048 KB\n"
            end = start
            while '0' <= data[end] <= '9':
                end += 1
            # *** data[start:end] == "2048"
            if start == end:
                continue
            number = int(data[start:end])
            # *** data[end:linepos] == " KB\n"
            end = _skipspace(data, end)
            if data[end] not in ('K', 'k'):    # assume kilobytes for now
                continue
            number = number * 1024
            # for now we look for the smallest of the L2 caches of the CPUs
            if number < L2cache:
                L2cache = number

    debug_print("L2cache =", L2cache)
    debug_stop("gc-hardware")

    if L2cache < sys.maxint:
        return L2cache
    else:
        # Print a top-level warning even in non-debug builds
        llop.debug_print(lltype.Void,
            "Warning: cannot find your CPU L2 cache size in /proc/cpuinfo")
        return -1

 def semispace_collect(self, size_changing=False):
     self.reset_young_gcflags() # we are doing a full collection anyway
     self.weakrefs_grow_older()
     self.reset_nursery()
     if DEBUG_PRINT:
         llop.debug_print(lltype.Void, "major collect, size changing", size_changing)
     SemiSpaceGC.semispace_collect(self, size_changing)
     if DEBUG_PRINT and not size_changing:
         llop.debug_print(lltype.Void, "percent survived", float(self.free - self.tospace) / self.space_size)

 def _check_rawsize_alloced(self, size_estimate, can_collect=True):
     self.large_objects_collect_trigger -= size_estimate
     if can_collect and self.large_objects_collect_trigger < 0:
         if self.config.gcconfig.debugprint:
             llop.debug_print(lltype.Void, "allocated",
                              self._initial_trigger -
                                  self.large_objects_collect_trigger,
                              "bytes, triggering full collection")
         self.semispace_collect()

 def collect_oldrefs_to_nursery(self):
     # Follow the old_objects_pointing_to_young list and move the
     # young objects they point to out of the nursery.
     count = 0
     oldlist = self.old_objects_pointing_to_young
     while oldlist.non_empty():
         count += 1
         obj = oldlist.pop()
         self.trace_and_drag_out_of_nursery(obj)
     if DEBUG_PRINT:
         llop.debug_print(lltype.Void, "collect_oldrefs_to_nursery", count)

 def collect_oldrefs_to_nursery(self):
     # Follow the old_objects_pointing_to_young list and move the
     # young objects they point to out of the nursery.
     count = 0
     oldlist = self.old_objects_pointing_to_young
     while oldlist.non_empty():
         count += 1
         obj = oldlist.pop()
         hdr = self.header(obj)
         hdr.tid |= GCFLAG_NO_YOUNG_PTRS
         self.trace_and_drag_out_of_nursery(obj)
     if self.config.gcconfig.debugprint:
         llop.debug_print(lltype.Void, "collect_oldrefs_to_nursery", count)

    def set_nursery_size(self, newsize):
        if newsize < self.min_nursery_size:
            newsize = self.min_nursery_size
        if newsize > self.space_size // 2:
            newsize = self.space_size // 2

        # Compute the new bounds for how large young objects can be
        # (larger objects are allocated directly old).   XXX adjust
        self.nursery_size = newsize
        self.largest_young_fixedsize = self.get_young_fixedsize(newsize)
        self.largest_young_var_basesize = self.get_young_var_basesize(newsize)
        scale = 0
        while (self.min_nursery_size << (scale+1)) <= newsize:
            scale += 1
        self.nursery_scale = scale
        if DEBUG_PRINT:
            llop.debug_print(lltype.Void, "SSS  nursery_size =", newsize)
            llop.debug_print(lltype.Void, "SSS  largest_young_fixedsize =",
                             self.largest_young_fixedsize)
            llop.debug_print(lltype.Void, "SSS  largest_young_var_basesize =",
                             self.largest_young_var_basesize)
            llop.debug_print(lltype.Void, "SSS  nursery_scale =", scale)
        # we get the following invariant:
        assert self.nursery_size >= (self.min_nursery_size << scale)

        # Force a full collect to remove the current nursery whose size
        # no longer matches the bounds that we just computed.  This must
        # be done after changing the bounds, because it might re-create
        # a new nursery (e.g. if it invokes finalizers).
        self.semispace_collect()

 def f(x, y):
     persistent_a1 = A()
     persistent_a2 = A()
     i = 0
     while i < x:
         i += 1
         a = A()
     persistent_a3 = A()
     persistent_a4 = A()
     llop.gc__collect(lltype.Void)
     llop.gc__collect(lltype.Void)
     b.bla = persistent_a1.id + persistent_a2.id + persistent_a3.id + persistent_a4.id
     # NB print would create a static root!
     llop.debug_print(lltype.Void, b.num_deleted_c)
     return b.num_deleted

def get_L2cache_darwin():
    """Try to estimate the best nursery size at run-time, depending
    on the machine we are running on.
    """
    debug_start("gc-hardware")
    L2cache = get_darwin_sysctl_signed("hw.l2cachesize")
    L3cache = get_darwin_sysctl_signed("hw.l3cachesize")
    debug_print("L2cache =", L2cache)
    debug_print("L3cache =", L3cache)
    debug_stop("gc-hardware")

    mangled = L2cache + L3cache

    if mangled > 0:
        return mangled
    else:
        # Print a top-level warning even in non-debug builds
        llop.debug_print(lltype.Void,
            "Warning: cannot find your CPU L2 cache size with sysctl()")
        return -1

 def finished_full_collect(self):
     ll_assert(not self.rawmalloced_objects_to_trace.non_empty(),
               "rawmalloced_objects_to_trace should be empty at end")
     if self.config.gcconfig.debugprint:
         llop.debug_print(lltype.Void,
                          "| [hybrid] made nonmoving:         ",
                          self._nonmoving_copy_size, "bytes in",
                          self._nonmoving_copy_count, "objs")
     # sweep the nonmarked rawmalloced objects
     if self.is_collecting_gen3():
         self.sweep_rawmalloced_objects(generation=3)
     self.sweep_rawmalloced_objects(generation=2)
     self.sweep_rawmalloced_objects(generation=-2)
     # As we just collected, it's fine to raw_malloc'ate up to space_size
     # bytes again before we should force another collect.
     self.large_objects_collect_trigger = self.space_size
     if self.is_collecting_gen3():
         self.count_semispaceonly_collects = 0
     if self.config.gcconfig.debugprint:
         self._initial_trigger = self.large_objects_collect_trigger

 def debug_collect_finish(self, start_time):
     if self.config.gcconfig.debugprint:
         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
         llop.debug_print(lltype.Void,
                          "| number of collections so far       ", 
                          cc)
         llop.debug_print(lltype.Void,
                          "| total collections per second:      ",
                          cc / total_program_time)
         llop.debug_print(lltype.Void,
                          "| total time in markcompact-collect: ",
                          ct, "seconds")
         llop.debug_print(lltype.Void,
                          "| percentage collection<->total time:",
                          ct * 100.0 / total_program_time, "%")
         llop.debug_print(lltype.Void,
                          "`----------------------------------------------")

 def collect_nursery(self):
     if self.nursery_size > self.top_of_space - self.free:
         # the semispace is running out, do a full collect
         self.obtain_free_space(self.nursery_size)
         ll_assert(self.nursery_size <= self.top_of_space - self.free,
                      "obtain_free_space failed to do its job")
     if self.nursery:
         if self.config.gcconfig.debugprint:
             llop.debug_print(lltype.Void, "--- minor collect ---")
             llop.debug_print(lltype.Void, "nursery:",
                              self.nursery, "to", self.nursery_top)
         # a nursery-only collection
         scan = beginning = self.free
         self.collect_oldrefs_to_nursery()
         self.collect_roots_in_nursery()
         scan = self.scan_objects_just_copied_out_of_nursery(scan)
         # at this point, all static and old objects have got their
         # GCFLAG_NO_YOUNG_PTRS set again by trace_and_drag_out_of_nursery
         if self.young_objects_with_weakrefs.non_empty():
             self.invalidate_young_weakrefs()
         if self.young_objects_with_id.length() > 0:
             self.update_young_objects_with_id()
         # mark the nursery as free and fill it with zeroes again
         llarena.arena_reset(self.nursery, self.nursery_size, 2)
         if self.config.gcconfig.debugprint:
             llop.debug_print(lltype.Void,
                              "survived (fraction of the size):",
                              float(scan - beginning) / self.nursery_size)
         #self.debug_check_consistency()   # -- quite expensive
     else:
         # no nursery - this occurs after a full collect, triggered either
         # just above or by some previous non-nursery-based allocation.
         # Grab a piece of the current space for the nursery.
         self.nursery = self.free
         self.nursery_top = self.nursery + self.nursery_size
         self.free = self.nursery_top
     self.nursery_free = self.nursery
     return self.nursery_free

 def _teardown(self):
     llop.debug_print(lltype.Void, "Teardown")
     llarena.arena_free(self.fromspace)
     llarena.arena_free(self.tospace)

 def externfn(node):
     llop.debug_print(lltype.Void, node)
     return node.value * 2

 def externfn(node):
     llop.debug_print(lltype.Void, compute_unique_id(node),
                      node.value, node.extra)
     return node.value * 2

    def sweep_rawmalloced_objects(self, generation):
        # free all the rawmalloced objects of the specified generation
        # that have not been marked
        if generation == 2:
            objects = self.gen2_rawmalloced_objects
            # generation 2 sweep: if A points to an object object B that
            # moves from gen2 to gen3, it's possible that A no longer points
            # to any gen2 object.  In this case, A remains a bit too long in
            # last_generation_root_objects, but this will be fixed by the
            # next collect_last_generation_roots().
        elif generation == 3:
            objects = self.gen3_rawmalloced_objects
            # generation 3 sweep: remove from last_generation_root_objects
            # all the objects that we are about to free
            gen3roots = self.last_generation_root_objects
            newgen3roots = self.AddressStack()
            while gen3roots.non_empty():
                obj = gen3roots.pop()
                if not (self.header(obj).tid & GCFLAG_UNVISITED):
                    newgen3roots.append(obj)
            gen3roots.delete()
            self.last_generation_root_objects = newgen3roots
        else:
            # mostly a hack: the generation number -2 is the part of the
            # generation 2 that lives in gen2_resizable_objects
            ll_assert(generation == -2, "bogus 'generation'")
            objects = self.gen2_resizable_objects

        surviving_objects = self.AddressStack()
        # Help the flow space
        alive_count = alive_size = dead_count = dead_size = 0
        while objects.non_empty():
            obj = objects.pop()
            tid = self.header(obj).tid
            if tid & GCFLAG_UNVISITED:
                if self.config.gcconfig.debugprint:
                    dead_count+=1
                    dead_size+=raw_malloc_usage(self.get_size(obj))
                addr = obj - self.gcheaderbuilder.size_gc_header
                llmemory.raw_free(addr)
            else:
                if self.config.gcconfig.debugprint:
                    alive_count+=1
                    alive_size+=raw_malloc_usage(self.get_size(obj))
                if generation == 3:
                    surviving_objects.append(obj)
                elif generation == 2:
                    ll_assert((tid & GCFLAG_AGE_MASK) < GCFLAG_AGE_MAX,
                              "wrong age for generation 2 object")
                    tid += GCFLAG_AGE_ONE
                    if (tid & GCFLAG_AGE_MASK) == GCFLAG_AGE_MAX:
                        # the object becomes part of generation 3
                        self.gen3_rawmalloced_objects.append(obj)
                        # GCFLAG_NO_HEAP_PTRS not set yet, conservatively
                        self.last_generation_root_objects.append(obj)
                    else:
                        # the object stays in generation 2
                        tid |= GCFLAG_UNVISITED
                        surviving_objects.append(obj)
                    self.header(obj).tid = tid
                elif generation == -2:
                    # the object stays in generation -2
                    tid |= GCFLAG_UNVISITED
                    surviving_objects.append(obj)
                    self.header(obj).tid = tid
        objects.delete()
        if generation == 2:
            self.gen2_rawmalloced_objects = surviving_objects
        elif generation == 3:
            self.gen3_rawmalloced_objects = surviving_objects
        elif generation == -2:
            self.gen2_resizable_objects = surviving_objects
        if self.config.gcconfig.debugprint:
            llop.debug_print(lltype.Void,
                             "| [hyb] gen", generation,
                             "nonmoving now alive: ",
                             alive_size, "bytes in",
                             alive_count, "objs")
            llop.debug_print(lltype.Void,
                             "| [hyb] gen", generation,
                             "nonmoving freed:     ",
                             dead_size, "bytes in",
                             dead_count, "objs")

 def write_free_statistics(self, typeid, result):
     llop.debug_print(lltype.Void, "free", typeid, " ", result)