Version 5 (modified by bacek, 12 years ago) |
---|
Rought idea of GC rework
- Decouple GC from Memory Allocation (Remove all this Pool/Arena/Whatever)
- Made GC track GCable.
(Without going through Pools to find if we need more memory/iterating headers/etc)
- Implement sweep-free GC. (And it will be much easy because GC track GCable already)
- Break API to make Parrot_gc_mark_PMC_alive to accept PMC**. (And probably rename it into gc_visit_pmc)
- Implement Compacting GC.
- Implement Generational GC on top of Compacting.
- "Optional" rename VTABLE_mark to VTABLE_gc_visit 'cause I want to reuse it in Compacting phase.
- Or try to reuse VTABLE_visit
Allocator API + PoolAllocator implementation. M&S/Incremental M&S/TriColour M&S/IncrementalTriColourM&S implementations.
# Current PObj. class PObj { has $flags; }; class PMC is PObj { method mark($gc) { ... } }; class RPA is PMC { has @pmcs; method mark($gc) { $gc.mark_alive($_) for self.pmcs; } }; # GC don't care how this work. It just have to work _fast_. class Allocator { has $object_size; method allocate() { ... }; method free($obj) { ... }; method Bool is_owned($obj) { ... }; }; class PoolAllocator { # 4KB page # We reuse storage to store index of next free object. # For detailed design see Alexandresku's SmallObjectAllocator # In the nutshell: # Initial content of $current_index, @objects is # 0 => [1, 2, 3, -1] # first alloc: # 1 => [*, 2, 3, -1] # second alloc: # 2 => [*, *, 3, -1] # free first object # 0 => [2, *, 3, -1] class Page { # fixed size header. my int $current_index; my int $object_size; my Page* $next_free_page; # Number of objects is (4096-sizeof(header))/$object_size; my @objects; method BUILD() { self.current_index := 0; # Initialize "linked list" for 0..+self.objects-1 -> $i { self.objects[$i] = $i+1; } # Terminate list self.objects[*-1] := -1; } method allocate() { # Use @objects as "linked list" my $res = (void*)self.objects[self.current_index]; self.current_index = (int)*$res; $res; } method free($obj) { # Get index of freed object my $index := ptr_diff($obj - @objects)/self.object_size; # Store current_index in it. self.objects[$index] = self.current_index; self.current_index = $index; } method is_full() { self.current_index < 0 }; }; # Pool data # Sorted array of pages to use binary search for finding pointer. has @pages of Page; # Linked list to pages with free storage. has $current_page; has $object_size; method BUILD() { self.current_page = Page->new(self.object_size); self.pages.push(self.current_page); } method allocate() { # Invariant: current page always have space. my $res = self.current_page.allocate(); # Allocate new page if it's filled if self.current_page.is_full { # Try to reuse old page my $page = self.current_page.next_free_page; if $page { self.current_page.next_free_page := NULL; self.current_page = $page; } else { # We have to allocate new one. $page = Page->new(self.object_size); self.current_page = $page; # Use binary search to put $page into proper position. my $pos = lower_bound(self.pages, $page); self.pages.splice($pos+1, 0, 0, $page); } } } method free($obj) { my $page = self.find_page($obj); assert($page); # If page was full than put it on free list. my $put_in_free_list := !$page.is_full; $page.free($obj); if $put_in_free_list { $page.next_free_page = self.current_page; self.current_page = $page; } } # Find page which holds $obj. method find_page($obj) { my $pos := lower_bound(self.pages, $obj); if ptr_diff(self.pages[$pos], $obj) < 4096 { return self.pages[$pos]; } return NULL; } # Pool owns $obj if there is Page for it. method bool is_owned($obj) { self.find_page($obj) != NULL; } }; class GC { has $allocator; has $allocated_since_last_gc; has $allocations_between_gc; has @objects; method BUILD() { self.allocator = Allocator.new(sizeof(PObj)); }; method get_object() { if self.need_gc() { self.do_gc(); }; my $obj := self.allocator.allocate(); @objects.push($obj); return $obj; } method need_gc() { ++self.allocated_since_last_gc >= self.allocations_between_gc; } # Current GC schema. method do_gc() { # Mark phase self.mark_alive($_) for self.trace_roots(); self.sweep(); } method is_pmc($void) { self.allocator.is_owned($void); } method trace_roots() { my @roots; for $system_areas -> $ptr { @roots.push($ptr) is self.is_pmc($void); } @roots; } method sweep() { # sweep phase for @objects -> $obj { if $obj.is_alive { $obj.is_alive := Bool::False; } else { self.allocator.free($obj); } } self.allocated_since_last_gc := 0; } method mark_alive($obj) { return if $obj.is_alive; $obj.is_alive := Bool::True; $obj.mark(self); } }; class IncrementalGC is GC { # Grey objects. has @working_set; has $do_marking; # Override need_gc method need_gc() { return Bool::False if self.do_marking; return self.SUPER.need_gc(); } method get_object() { self.mark_a_little_bit() if self.do_marking; self.SUPER.get_object(); } method do_gc() { # "Mark" phase self.do_marking := Bool::True; self.working_set := self.trace_roots(); } method mark_a_little_bit() { my $count := 0; for self.working_set -> $obj { return if $count++ > 10; self.real_mark($obj); } self.do_marking := Bool::False; self.sweep(); } # Override GC.mark_alive method mark_alive($obj) { self.working_set.push($obj); } # Just redispatch to GC.mark_alive method real_mark($obj) { self.SUPER.mark_alive($obj); } } # is non-recursive GC class TriColourGC is GC { # Black (inherited from GC) # We need separate @live_list if we want to do it incremental # has @objects; # Grey has @grey_objects; # White during GC has @dead_objects; method do_gc() { self.dead_objects = self.objects; self.objects = (); self.grey_objects = self.trace_roots(); # mark_alive will push into self.grey_objects self.mark_real($_) for self.grey_objects; # Sweep for self.dead_objects -> $dead { $dead.destroy(); self.allocator.free($dead); } } method mark_alive($obj) { self.grey_objects.push($obj); self.dead_objects.remove($obj); } method mark_real($obj) { self.objects.push($obj); self.SUPER.mark_alive($obj); } }; # Non-recursive, tri-colour, incremental mark and sweep. class IncrementalTriColourGC is GC { has @live_objects; # Black has @grey_objects; # Guess? has @dead_objects; # White has $do_marking; # We are in mark phase. has $do_sweeping; # We are in sweep phase. method need_gc() { return Bool::False if self.do_marking || self.do_sweeping; return self.SUPER.need_gc(); } method get_object() { self.mark_a_little_bit() if self.do_marking; self.sweep_a_little_bit() if self.do_sweeping; self.SUPER.get_object(); } method do_gc() { # Prepare mark phase self.do_marking = Bool::True; self.do_sweeping = Bool::False; self.dead_objects = self.objects; self.objects = (); self.grey_objects = self.trace_roots(); } method mark_a_little_bit() { my $count = 0; while(my $obj = self.grey_objects.pop) { self.mark_real($obj); return if $count++ > 10; } # Switch to incremental sweep. self.do_marking = Bool::False; self.do_sweeping = Bool::True; } method sweep_a_little_bit() { my $count = 0; while(my $dead = self.dead_objects.pop) { $dead.destroy(); self.allocator.free($dead); return if $count++ > 10; } # self.objects can be updated at this point of time. # Add live_objects to objects to use on next GC round. self.objects.push(self.live_objects); # .grey_objects .dead_objects are empty now. # Back to normal life self.do_sweeping = Bool::False; } method mark_alive($obj) { self.dead_objects.remove($obj); self.grey_objects.push($obj); } method mark_real($obj) { self.live_objects.push($obj); self.SUPER.mark_alive($obj); } }; # vim: ft=perl6