Changes between Version 3 and Version 4 of GCMassacre

Show
Ignore:
Timestamp:
05/25/10 12:03:32 (5 years ago)
Author:
bacek
Comment:

Describe how PoolAllocator can work

Legend:

Unmodified
Added
Removed
Modified
  • GCMassacre

    v3 v4  
    2020{{{ 
    2121#!perl 
    22 # GC don't care how this work. Pools/Arenas/Blocks/whatever. 
    23 class Allocator { 
    24     has $object_size; 
    25  
    26     method allocate() { ... }; 
    27     method free(pointer $obj) { ... }; 
    28 }; 
    2922 
    3023# Current PObj. 
     
    3326}; 
    3427 
    35  
    3628class PMC is PObj { 
    3729    method mark($gc) { ... } 
     
    4335    method mark($gc) { 
    4436        $gc.mark_alive($_) for self.pmcs; 
     37    } 
     38}; 
     39 
     40# GC don't care how this work. It just have to work _fast_. 
     41class Allocator { 
     42    has $object_size; 
     43 
     44    method allocate() { ... }; 
     45    method free($obj) { ... }; 
     46 
     47    method Bool is_owned($obj) { ... }; 
     48}; 
     49 
     50class PoolAllocator { 
     51    # 4KB page 
     52    # We reuse storage to store index of next free object. 
     53    # For detailed design see Alexandresku's SmallObjectAllocator 
     54    # In the nutshell: 
     55    # Initial content of $current_index, @objects is 
     56    # 0 => [1, 2, 3, -1] 
     57    # first alloc: 
     58    # 1 => [*, 2, 3, -1] 
     59    # second alloc: 
     60    # 2 => [*, *, 3, -1] 
     61    # free first object 
     62    # 0 => [2, *, 3, -1] 
     63    class Page { 
     64        # fixed size header. 
     65        my int $current_index; 
     66        my int $object_size; 
     67        my Page* $next_free_page; 
     68 
     69        # Number of objects is (4096-sizeof(header))/$object_size; 
     70        my @objects; 
     71 
     72        method BUILD() { 
     73            self.current_index := 0; 
     74            # Initialize "linked list" 
     75            for 0..+self.objects-1 -> $i { 
     76                self.objects[$i] = $i+1; 
     77            } 
     78            # Terminate list 
     79            self.objects[*-1] := -1; 
     80        } 
     81 
     82        method allocate() { 
     83            # Use @objects as "linked list" 
     84            my $res       = (void*)self.objects[self.current_index]; 
     85            self.current_index = (int)*$res; 
     86            $res; 
     87        } 
     88 
     89        method free($obj) { 
     90            # Get index of freed object 
     91            my $index := ptr_diff($obj - @objects)/self.object_size; 
     92 
     93            # Store current_index in it. 
     94            self.objects[$index] = self.current_index; 
     95            self.current_index   = $index; 
     96        } 
     97 
     98        method is_full() { self.current_index < 0 }; 
     99    }; 
     100 
     101    # Pool data 
     102    # Sorted array of pages to use binary search for finding pointer. 
     103    has @pages of Page; 
     104    # Linked list to pages with free storage. 
     105    has $current_page; 
     106 
     107    has $object_size; 
     108 
     109    method BUILD() { 
     110        self.current_page = Page->new(self.object_size); 
     111        self.pages.push(self.current_page); 
     112    } 
     113 
     114    method allocate() { 
     115        # Invariant: current page always have space. 
     116        my $res = self.current_page.allocate(); 
     117 
     118        # Allocate new page if it's filled 
     119        if self.current_page.is_full { 
     120            # Try to reuse old page 
     121            my $page = self.current_page.next_free_page; 
     122            if $page { 
     123                self.current_page.next_free_page := NULL; 
     124                self.current_page = $page; 
     125            } 
     126            else { 
     127                # We have to allocate new one. 
     128                $page = Page->new(self.object_size); 
     129                self.current_page = $page; 
     130 
     131                # Use binary search to put $page into proper position. 
     132                my $pos = lower_bound(self.pages, $page); 
     133                self.pages.splice($pos+1, 0, 0, $page); 
     134            } 
     135        } 
     136    } 
     137 
     138    method free($obj) { 
     139        my $page = self.find_page($obj); 
     140        assert($page); 
     141        # If page was full than put it on free list. 
     142        my $put_in_free_list := !$page.is_full; 
     143 
     144        $page.free($obj); 
     145 
     146        if $put_in_free_list { 
     147            $page.next_free_page = self.current_page; 
     148            self.current_page    = $page; 
     149        } 
     150    } 
     151 
     152    # Find page which holds $obj. 
     153    method find_page($obj) { 
     154        my $pos := lower_bound(self.pages, $obj); 
     155        if ptr_diff(self.pages[$pos], $obj) < 4096 { 
     156            return self.pages[$pos]; 
     157        } 
     158        return NULL; 
     159    } 
     160 
     161    # Pool owns $obj if there is Page for it. 
     162    method bool is_owned($obj) { 
     163        self.find_page($obj) != NULL; 
    45164    } 
    46165}; 
     
    81200    } 
    82201 
    83     method trace_roots() { ... } 
     202    method is_pmc($void) { 
     203        self.allocator.is_owned($void); 
     204    } 
     205 
     206    method trace_roots() { 
     207        my @roots; 
     208        for $system_areas -> $ptr { 
     209            @roots.push($ptr) is self.is_pmc($void); 
     210        } 
     211        @roots; 
     212    } 
    84213 
    85214    method sweep() { 
     
    93222            } 
    94223        } 
     224 
    95225        self.allocated_since_last_gc := 0; 
    96226    } 
     
    104234}; 
    105235 
     236 
    106237class IncrementalGC is GC { 
     238    # Grey objects. 
    107239    has @working_set; 
    108240    has $do_marking; 
     
    121253    method do_gc() { 
    122254        # "Mark" phase 
    123         self.do_marking := Bool::True; 
     255        self.do_marking  := Bool::True; 
    124256        self.working_set := self.trace_roots(); 
    125257    } 
     
    159291 
    160292    method do_gc() { 
    161         self.dead_objects = self.objects; 
    162         self.objects = (); 
    163  
    164         self.grey_objects = self.trace_roots(); 
     293        self.dead_objects  = self.objects; 
     294        self.objects       = (); 
     295 
     296        self.grey_objects  = self.trace_roots(); 
    165297        # mark_alive will push into self.grey_objects 
    166298        self.mark_real($_) for self.grey_objects; 
     
    183315    } 
    184316}; 
    185  
    186317 
    187318# Non-recursive, tri-colour, incremental mark and sweep. 
     
    255386}; 
    256387 
    257  
    258  
    259  
    260388# vim: ft=perl6 
    261389 
    262  
    263390}}}