Changes between Version 3 and Version 4 of GCMassacre

Timestamp:

05/25/10 12:03:32 (12 years ago)

Author:

bacek

Comment:

Describe how PoolAllocator can work

GCMassacre

@@ -20 +20 @@
 {{{
 #!perl
-# GC don't care how this work. Pools/Arenas/Blocks/whatever.
-class Allocator {
-    has $object_size;
-
-    method allocate() { ... };
-    method free(pointer $obj) { ... };
-};
 
 # Current PObj.
@@ -33 +26 @@
 };
 
-
 class PMC is PObj {
     method mark($gc) { ... }
@@ -43 +35 @@
     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;
     }
 };
@@ -81 +200 @@
     }
 
-    method trace_roots() { ... }
+    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() {
@@ -93 +222 @@
             }
         }
+
         self.allocated_since_last_gc := 0;
     }
@@ -104 +234 @@
 };
 
+
 class IncrementalGC is GC {
+    # Grey objects.
     has @working_set;
     has $do_marking;
@@ -121 +253 @@
     method do_gc() {
         # "Mark" phase
-        self.do_marking := Bool::True;
+        self.do_marking  := Bool::True;
         self.working_set := self.trace_roots();
     }
@@ -159 +291 @@
 
     method do_gc() {
-        self.dead_objects = self.objects;
-        self.objects = ();
-
-        self.grey_objects = self.trace_roots();
+        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;
@@ -183 +315 @@
     }
 };
-
 
 # Non-recursive, tri-colour, incremental mark and sweep.
@@ -255 +386 @@
 };
 
-
-
-
 # vim: ft=perl6
 
-
 }}}