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