Copy-on-write class table for concurrent reading.

runtime/vm/class_table.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/class_table.h"
 #include "vm/flags.h"
 #include "vm/freelist.h"
+#include "vm/growable_array.h"
 #include "vm/heap.h"
 #include "vm/object.h"
 #include "vm/raw_object.h"
 #include "vm/visitor.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, print_class_table, false, "Print initial class table.");
 
 ClassTable::ClassTable()
     : top_(kNumPredefinedCids), capacity_(0), table_(NULL),
+      old_tables_(new MallocGrowableArray<RawClass**>()),

[Ivan Posva, 2015/01/20 22:46:45]

Wondering why you decided on MallocGrowableArray vs chaining through the first
entry?

[koda, 2015/01/21 14:36:09]

1. To avoid yet another ad hoc linked list implementation, of which we already
have many. MallocGrowableArray is reusable and did not add any new logic.

2. The entry for class id 0 being NULL rather than a random next-pointer helps
debugging. Alternatively, having the next pointer separately before class id 0
would complicate scaling+offset computation in generated code.

       class_heap_stats_table_(NULL),
       predefined_class_heap_stats_table_(NULL) {
   if (Dart::vm_isolate() == NULL) {
     capacity_ = initial_capacity_;
     table_ = reinterpret_cast<RawClass**>(
         calloc(capacity_, sizeof(RawClass*)));  // NOLINT
   } else {
     // Duplicate the class table from the VM isolate.
     ClassTable* vm_class_table = Dart::vm_isolate()->class_table();
     capacity_ = vm_class_table->capacity_;
@@ skipping 15 matching lines @@
         calloc(kNumPredefinedCids, sizeof(ClassHeapStats)));  // NOLINT
   for (intptr_t i = 0; i < kNumPredefinedCids; i++) {
     predefined_class_heap_stats_table_[i].Initialize();
   }
 }
 
 
 ClassTable::ClassTable(ClassTable* original)
     : top_(original->top_),
       capacity_(original->top_),
-      table_(reinterpret_cast<RawClass**>(
-          calloc(original->top_, sizeof(RawClass*)))),
+      table_(original->table_),
+      old_tables_(NULL),
       class_heap_stats_table_(NULL),
       predefined_class_heap_stats_table_(NULL) {
-  for (intptr_t i = 1; i < top_; i++) {
-    table_[i] = original->At(i);
+}
+
+
+ClassTable::~ClassTable() {
+  if (old_tables_ != NULL) {
+    FreeOldTables();
+    delete old_tables_;
+    free(table_);
+    free(predefined_class_heap_stats_table_);
+    free(class_heap_stats_table_);
+  } else {
+    // This instance was a shallow copy. It doesn't own any memory.
+    ASSERT(predefined_class_heap_stats_table_ == NULL);
+    ASSERT(class_heap_stats_table_ == NULL);
   }
 }
 
 
-ClassTable::~ClassTable() {
-  free(table_);
-  free(predefined_class_heap_stats_table_);
-  free(class_heap_stats_table_);
+void ClassTable::FreeOldTables() {
+  while (old_tables_->length() > 0) {
+    free(old_tables_->RemoveLast());
+  }
 }
 
 
 void ClassTable::Register(const Class& cls) {
   intptr_t index = cls.id();
   if (index != kIllegalCid) {
     ASSERT(index > 0);
     ASSERT(index < kNumPredefinedCids);
     ASSERT(table_[index] == 0);
     ASSERT(index < capacity_);
     table_[index] = cls.raw();
     // Add the vtable for this predefined class into the static vtable registry
     // if it has not been setup yet.
     cpp_vtable cls_vtable = cls.handle_vtable();
     cpp_vtable table_entry = Object::builtin_vtables_[index];
     ASSERT((table_entry == 0) || (table_entry == cls_vtable));
     if (table_entry == 0) {
       Object::builtin_vtables_[index] = cls_vtable;
     }
   } else {
     if (top_ == capacity_) {
       // Grow the capacity of the class table.
+      // TODO(koda): Add ClassTable::Grow to share code.
       intptr_t new_capacity = capacity_ + capacity_increment_;
       RawClass** new_table = reinterpret_cast<RawClass**>(
-          realloc(table_, new_capacity * sizeof(RawClass*)));  // NOLINT
+          malloc(new_capacity * sizeof(RawClass*)));  // NOLINT
+      memmove(new_table, table_, capacity_ * sizeof(RawClass*));
       ClassHeapStats* new_stats_table = reinterpret_cast<ClassHeapStats*>(
           realloc(class_heap_stats_table_,
                   new_capacity * sizeof(ClassHeapStats)));  // NOLINT
       for (intptr_t i = capacity_; i < new_capacity; i++) {
         new_table[i] = NULL;
         new_stats_table[i].Initialize();
       }
       capacity_ = new_capacity;
-      table_ = new_table;
+      old_tables_->Add(table_);
+      table_ = new_table;  // TODO(koda): This should use atomics.
       class_heap_stats_table_ = new_stats_table;
     }
     ASSERT(top_ < capacity_);
     if (!Class::is_valid_id(top_)) {
       FATAL1("Fatal error in ClassTable::Register: invalid index %" Pd "\n",
              top_);
     }
     cls.set_id(top_);
     table_[top_] = cls.raw();
     top_++;  // Increment next index.
   }
 }
 
 
 void ClassTable::RegisterAt(intptr_t index, const Class& cls) {
   ASSERT(index != kIllegalCid);
   ASSERT(index >= kNumPredefinedCids);
   if (index >= capacity_) {
     // Grow the capacity of the class table.
+    // TODO(koda): Add ClassTable::Grow to share code.
     intptr_t new_capacity = index + capacity_increment_;
     if (!Class::is_valid_id(index) || new_capacity < capacity_) {
       FATAL1("Fatal error in ClassTable::Register: invalid index %" Pd "\n",
              index);
     }
     RawClass** new_table = reinterpret_cast<RawClass**>(
-        realloc(table_, new_capacity * sizeof(RawClass*)));  // NOLINT
+        malloc(new_capacity * sizeof(RawClass*)));  // NOLINT
+    memmove(new_table, table_, capacity_ * sizeof(RawClass*));
     ClassHeapStats* new_stats_table = reinterpret_cast<ClassHeapStats*>(
         realloc(class_heap_stats_table_,
                 new_capacity * sizeof(ClassHeapStats)));  // NOLINT
     for (intptr_t i = capacity_; i < new_capacity; i++) {
       new_table[i] = NULL;
       new_stats_table[i].Initialize();
     }
     capacity_ = new_capacity;
-    table_ = new_table;
+    old_tables_->Add(table_);
+    table_ = new_table;  // TODO(koda): This should use atomics.
     class_heap_stats_table_ = new_stats_table;
     ASSERT(capacity_increment_ >= 1);
   }
   ASSERT(table_[index] == 0);
   cls.set_id(index);
   table_[index] = cls.raw();
   if (index >= top_) {
     top_ = index + 1;
   }
 }
@@ skipping 305 matching lines @@
 
 void ClassTable::UpdateLiveNew(intptr_t cid, intptr_t size) {
   ClassHeapStats* stats = PreliminaryStatsAt(cid);
   ASSERT(stats != NULL);
   ASSERT(size >= 0);
   stats->post_gc.AddNew(size);
 }
 
 
 }  // namespace dart