Add per-library cache of exported names

runtime/vm/object.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/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 39 matching lines @@
     "Huge method cutoff in unoptimized code size (in bytes).");
 DEFINE_FLAG(int, huge_method_cutoff_in_tokens, 20000,
     "Huge method cutoff in tokens: Disables optimizations for huge methods.");
 DEFINE_FLAG(bool, overlap_type_arguments, true,
     "When possible, partially or fully overlap the type arguments of a type "
     "with the type arguments of its super type.");
 DEFINE_FLAG(bool, show_internal_names, false,
     "Show names of internal classes (e.g. \"OneByteString\") in error messages "
     "instead of showing the corresponding interface names (e.g. \"String\")");
 DEFINE_FLAG(bool, use_lib_cache, true, "Use library name cache");
+DEFINE_FLAG(bool, use_exp_cache, true, "Use library exported name cache");

[srdjan, 2016/04/18 22:40:49]

use_exported_name_cache sounds more readable than use_exp_cache.

[Ivan Posva, 2016/04/18 23:07:21]

In the future please add new flags to the flag_list.h. I am assuming this flag
is temporary while we test the impact of this feature, correct?

[hausner, 2016/04/18 23:51:58]

Yes, I consider the flag temporary.

[hausner, 2016/04/18 23:51:58]

More readable maybe, but I'm not sure it is more understandable. This option
should not be used by the general public. If you insist, I can make it
use_export_cache.

[srdjan, 2016/04/26 21:09:42]

The flag is temporary, your choice.

 DEFINE_FLAG(bool, ignore_patch_signature_mismatch, false,
             "Ignore patch file member signature mismatch.");
 
 DECLARE_FLAG(bool, show_invisible_frames);
 DECLARE_FLAG(bool, trace_deoptimization);
 DECLARE_FLAG(bool, trace_deoptimization_verbose);
 DECLARE_FLAG(bool, write_protect_code);
 DECLARE_FLAG(bool, support_externalizable_strings);
 
 
@@ skipping 9546 matching lines @@
 #endif
   return present;
 }
 
 
 // Add a name to the resolved name cache. This name resolves to the
 // given object in this library scope. obj may be null, which means
 // the name does not resolve to anything in this library scope.
 void Library::AddToResolvedNamesCache(const String& name,
                                       const Object& obj) const {
-  ASSERT(!Compiler::IsBackgroundCompilation());
-  if (!FLAG_use_lib_cache) {
+  if (!FLAG_use_lib_cache || Compiler::IsBackgroundCompilation()) {

[srdjan, 2016/04/18 22:40:48]

Why are we starting to call AddToResolvedNamesCache from BackgroundCompiler?

[hausner, 2016/04/18 23:51:58]

No change here, but I think it is possible that the BG compiler ends up calling
this function, which is a latent race condition.

     return;
   }
   ResolvedNamesMap cache(resolved_names());
   cache.UpdateOrInsert(name, obj);
   StorePointer(&raw_ptr()->resolved_names_, cache.Release().raw());
 }
 
 
+bool Library::LookupExportedNamesCache(const String& name,
+                                       Object* obj) const {
+  ASSERT(FLAG_use_exp_cache);
+  if (exported_names() == Array::null()) {
+    return false;
+  }
+  ResolvedNamesMap cache(exported_names());
+  bool present = false;
+  *obj = cache.GetOrNull(name, &present);
+  // Mutator compiler thread may add entries and therefore
+  // change 'resolved_names()' while running a background compilation;

[srdjan, 2016/04/18 22:40:49]

s/resolved_names/exported_names/

[hausner, 2016/04/18 23:51:58]

Done.

+  // do not ASSERT that 'exported_names()' has not changed.
+  cache.Release();

[srdjan, 2016/04/18 22:40:49]

You may want to the same as in LookupResolvedNamesCache (changed recently):

#if defined(DEBUG)
  if (Thread::Current()->IsMutatorThread()) {
    ASSERT(cache.Release().raw() == exported_names());
  } else {
    // Release must be called in debug mode.
    cache.Release();
  }
#endif

[hausner, 2016/04/18 23:51:58]

Done.

+  return present;
+}
+
+void Library::AddToExportedNamesCache(const String& name,
+                                      const Object& obj) const {
+  ASSERT(!Compiler::IsBackgroundCompilation());
+  if (!FLAG_use_exp_cache || Compiler::IsBackgroundCompilation()) {

[srdjan, 2016/04/18 22:40:48]

Why tests for background compilation when asserting it can't be?

[hausner, 2016/04/18 23:51:58]

Ok, assertion removed.

+    return;
+  }
+  if (exported_names() == Array::null()) {
+    AllocateExportedNamesCache();
+  }
+  ResolvedNamesMap cache(exported_names());
+  cache.UpdateOrInsert(name, obj);
+  StorePointer(&raw_ptr()->exported_names_, cache.Release().raw());
+}
+
+
 void Library::InvalidateResolvedName(const String& name) const {

[srdjan, 2016/04/18 22:40:49]

You may want to:

Thread* thread = Thread::Current();
Zone* zone = ..
Isolate* isolate = ...

then pass zone to handles and replace call to Isolate::Current() with isolate.

[srdjan, 2016/04/18 22:40:49]

ASSERT(FLAG_use_exp_cache)

[hausner, 2016/04/18 23:51:58]

the flags for resolved name cache and exported names cache are independent. We
can get here even if the export cache is not used.

[hausner, 2016/04/18 23:51:58]

Done.

   Object& entry = Object::Handle();
   if (LookupResolvedNamesCache(name, &entry)) {
     // TODO(koda): Support deleted sentinel in snapshots and remove only 'name'.
     InvalidateResolvedNamesCache();
   }
+  GrowableObjectArray& libs = GrowableObjectArray::Handle(

[Ivan Posva, 2016/04/18 23:07:21]

Please add a comment how we can get into a state where this removal is needed
and why we need to invalidate all re-export caches.

[hausner, 2016/04/18 23:51:58]

Done.

+      Isolate::Current()->object_store()->libraries());
+  Library& lib = Library::Handle();
+  intptr_t num_libs = libs.Length();
+  for (intptr_t i = 0; i < num_libs; i++) {
+    lib ^= libs.At(i);
+    if (LookupExportedNamesCache(name, &entry)) {
+      InitExportedNamesCache();
+    }
+  }
 }
 
 
 void Library::InvalidateResolvedNamesCache() const {
   const intptr_t kInvalidatedCacheSize = 16;
   InitResolvedNamesCache(kInvalidatedCacheSize);
 }
 
 
+// Invalidate all exported names caches in the isolate.
+void Library::InvalidateExportedNamesCaches() {
+  GrowableObjectArray& libs = GrowableObjectArray::Handle(
+      Isolate::Current()->object_store()->libraries());
+  Library& lib = Library::Handle();
+  intptr_t num_libs = libs.Length();
+  for (intptr_t i = 0; i < num_libs; i++) {
+    lib ^= libs.At(i);
+    lib.InitExportedNamesCache();
+  }
+}
+
+
 void Library::GrowDictionary(const Array& dict, intptr_t dict_size) const {
   // TODO(iposva): Avoid exponential growth.
   intptr_t new_dict_size = dict_size * 2;
   const Array& new_dict =
       Array::Handle(Array::New(new_dict_size + 1, Heap::kOld));
   // Rehash all elements from the original dictionary
   // to the newly allocated array.
   Object& entry = Class::Handle();
   String& entry_name = String::Handle();
   Object& new_entry = Object::Handle();
@@ skipping 55 matching lines @@
   // Invalidate the cache of loaded scripts.
   if (loaded_scripts() != Array::null()) {
     StorePointer(&raw_ptr()->loaded_scripts_, Array::null());
   }
 }
 
 
 // Lookup a name in the library's re-export namespace.
 // This lookup can occur from two different threads: background compiler and
 // mutator thread.
-RawObject* Library::LookupReExport(const String& name) const {
-  if (HasExports()) {
-    const bool is_background_compiler = Compiler::IsBackgroundCompilation();
-    Array& exports = Array::Handle();
-    if (is_background_compiler) {
-      exports = this->exports2();
-      // Break potential export cycle while looking up name.
-      StorePointer(&raw_ptr()->exports2_, Object::empty_array().raw());
-    } else {
-      exports = this->exports();
-      // Break potential export cycle while looking up name.
-      StorePointer(&raw_ptr()->exports_, Object::empty_array().raw());
-    }
-    Namespace& ns = Namespace::Handle();
-    Object& obj = Object::Handle();
-    for (int i = 0; i < exports.Length(); i++) {
-      ns ^= exports.At(i);
-      obj = ns.Lookup(name);
-      if (!obj.IsNull()) {
-        // The Lookup call above may return a setter x= when we are looking
-        // for the name x. Make sure we only return when a matching name
-        // is found.
-        String& obj_name = String::Handle(obj.DictionaryName());
-        if (Field::IsSetterName(obj_name) == Field::IsSetterName(name)) {
-          break;
-        }
+RawObject* Library::LookupReExport(const String& name,
+                                   ZoneGrowableArray<intptr_t>* trail) const {
+  if (!HasExports()) {
+    return Object::null();
+  }
+
+  if (trail == NULL) {
+    trail = new ZoneGrowableArray<intptr_t>();
+  }
+  Object& obj = Object::Handle();
+  if (FLAG_use_exp_cache && LookupExportedNamesCache(name, &obj)) {
+    return obj.raw();
+  }
+
+  const intptr_t lib_id = this->index();
+  ASSERT(lib_id >= 0);  // We use -1 to indicate that a cycle was found.
+  trail->Add(lib_id);
+  const Array& exports = Array::Handle(this->exports());
+  Namespace& ns = Namespace::Handle();
+  for (int i = 0; i < exports.Length(); i++) {
+    ns ^= exports.At(i);
+    obj = ns.Lookup(name, trail);
+    if (!obj.IsNull()) {
+      // The Lookup call above may return a setter x= when we are looking
+      // for the name x. Make sure we only return when a matching name
+      // is found.
+      String& obj_name = String::Handle(obj.DictionaryName());
+      if (Field::IsSetterName(obj_name) == Field::IsSetterName(name)) {
+        break;
       }
     }
-    if (is_background_compiler) {
-      StorePointer(&raw_ptr()->exports2_, exports.raw());
-    } else {
-      StorePointer(&raw_ptr()->exports_, exports.raw());
-    }
-    return obj.raw();
   }
-  return Object::null();
+  bool in_cycle = (trail->RemoveLast() < 0);
+  if (FLAG_use_exp_cache &&
+      !in_cycle &&
+      !Compiler::IsBackgroundCompilation()) {
+    AddToExportedNamesCache(name, obj);
+  }
+  return obj.raw();
 }
 
 
 RawObject* Library::LookupEntry(const String& name, intptr_t *index) const {
   Thread* thread = Thread::Current();
   REUSABLE_ARRAY_HANDLESCOPE(thread);
   REUSABLE_OBJECT_HANDLESCOPE(thread);
   REUSABLE_STRING_HANDLESCOPE(thread);
   Array& dict = thread->ArrayHandle();
   dict ^= dictionary();
@@ skipping 65 matching lines @@
       dict.SetAt(new_index, entry);
       dict.SetAt(index, Object::null_object());
     }
   }
 
   // Update used count.
   intptr_t used_elements = Smi::Value(Smi::RawCast(dict.At(dict_size))) - 1;
   dict.SetAt(dict_size, Smi::Handle(zone, Smi::New(used_elements)));
 
   InvalidateResolvedNamesCache();
+  InvalidateExportedNamesCaches();
 
   return true;
 }
 
 
 void Library::AddClass(const Class& cls) const {
   ASSERT(!Compiler::IsBackgroundCompilation());
   const String& class_name = String::Handle(cls.Name());
   AddObject(cls, class_name);
   // Link class to this library.
@@ skipping 346 matching lines @@
       }
     }
   }
   return false;
 }
 
 
 void Library::DropDependencies() const {
   StorePointer(&raw_ptr()->imports_, Array::null());
   StorePointer(&raw_ptr()->exports_, Array::null());
-  StorePointer(&raw_ptr()->exports2_, Array::null());
 }
 
 
 void Library::AddImport(const Namespace& ns) const {
   Array& imports = Array::Handle(this->imports());
   intptr_t capacity = imports.Length();
   if (num_imports() == capacity) {
     capacity = capacity + kImportsCapacityIncrement;
     imports = Array::Grow(imports, capacity);
     StorePointer(&raw_ptr()->imports_, imports.raw());
@@ skipping 12 matching lines @@
 
 
 // We add one namespace at a time to the exports array and don't
 // pre-allocate any unused capacity. The assumption is that
 // re-exports are quite rare.
 void Library::AddExport(const Namespace& ns) const {
   Array &exports = Array::Handle(this->exports());
   intptr_t num_exports = exports.Length();
   exports = Array::Grow(exports, num_exports + 1);
   StorePointer(&raw_ptr()->exports_, exports.raw());
-  StorePointer(&raw_ptr()->exports2_, exports.raw());
   exports.SetAt(num_exports, ns);
 }
 
 
 static RawArray* NewDictionary(intptr_t initial_size) {
   const Array& dict = Array::Handle(Array::New(initial_size + 1, Heap::kOld));
   // The last element of the dictionary specifies the number of in use slots.
   dict.SetAt(initial_size, Smi::Handle(Smi::New(0)));
   return dict.raw();
 }
 
 
 void Library::InitResolvedNamesCache(intptr_t size,
                                      SnapshotReader* reader) const {
   ASSERT(Thread::Current()->IsMutatorThread());
   if (reader == NULL) {
     StorePointer(&raw_ptr()->resolved_names_,
                  HashTables::New<ResolvedNamesMap>(size));
   } else {
     intptr_t len = ResolvedNamesMap::ArrayLengthForNumOccupied(size);
     *reader->ArrayHandle() ^= reader->NewArray(len);
     StorePointer(&raw_ptr()->resolved_names_,
                  HashTables::New<ResolvedNamesMap>(*reader->ArrayHandle()));
   }
 }
 
 
+void Library::AllocateExportedNamesCache() const {
+  StorePointer(&raw_ptr()->exported_names_,
+               HashTables::New<ResolvedNamesMap>(16));
+}
+
+
+void Library::InitExportedNamesCache() const {
+  if (exported_names() != Array::null()) {
+    StorePointer(&raw_ptr()->exported_names_,
+                 HashTables::New<ResolvedNamesMap>(16));
+  }
+}
+
+
 void Library::InitClassDictionary() const {
   // TODO(iposva): Find reasonable initial size.
   const int kInitialElementCount = 16;
   StorePointer(&raw_ptr()->dictionary_, NewDictionary(kInitialElementCount));
 }
 
 
 void Library::InitImportList() const {
   const Array& imports =
       Array::Handle(Array::New(kInitialImportsCapacity, Heap::kOld));
@@ skipping 14 matching lines @@
 RawLibrary* Library::NewLibraryHelper(const String& url,
                                       bool import_core_lib) {
   Thread* thread = Thread::Current();
   Zone* zone = thread->zone();
   ASSERT(thread->IsMutatorThread());
   const Library& result = Library::Handle(zone, Library::New());
   result.StorePointer(&result.raw_ptr()->name_, Symbols::Empty().raw());
   result.StorePointer(&result.raw_ptr()->url_, url.raw());
   result.StorePointer(&result.raw_ptr()->resolved_names_,
                       Object::empty_array().raw());
+  result.StorePointer(&result.raw_ptr()->exported_names_,
+                      Array::null());
   result.StorePointer(&result.raw_ptr()->dictionary_,
                       Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->metadata_,
                       GrowableObjectArray::New(4, Heap::kOld));
   result.StorePointer(&result.raw_ptr()->toplevel_class_, Class::null());
   result.StorePointer(&result.raw_ptr()->patch_classes_,
                       GrowableObjectArray::New(Object::empty_array(),
                                                Heap::kOld));
   result.StorePointer(&result.raw_ptr()->imports_, Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->exports_, Object::empty_array().raw());
-  result.StorePointer(&result.raw_ptr()->exports2_,
-      Object::empty_array().raw());
   result.StorePointer(&result.raw_ptr()->loaded_scripts_, Array::null());
   result.StorePointer(&result.raw_ptr()->load_error_, Instance::null());
   result.set_native_entry_resolver(NULL);
   result.set_native_entry_symbol_resolver(NULL);
   result.set_is_in_fullsnapshot(false);
   result.StoreNonPointer(&result.raw_ptr()->corelib_imported_, true);
   result.set_debuggable(false);
   result.set_is_dart_scheme(url.StartsWith(Symbols::DartScheme()));
   result.StoreNonPointer(&result.raw_ptr()->load_state_,
                          RawLibrary::kAllocated);
@@ skipping 701 matching lines @@
     // contained in the list, so it is hidden.
     return true;
   }
   // The name is not filtered out.
   return false;
 }
 
 
 // Look up object with given name in library and filter out hidden
 // names. Also look up getters and setters.
-RawObject* Namespace::Lookup(const String& name) const {
+RawObject* Namespace::Lookup(const String& name,
+                             ZoneGrowableArray<intptr_t>* trail) const {
   Zone* zone = Thread::Current()->zone();
   const Library& lib = Library::Handle(zone, library());
+
+  if (trail != NULL) {
+    // Look for cycle in reexport graph.
+    for (int i = 0; i < trail->length(); i++) {
+      if (trail->At(i) == lib.index()) {
+        for (int j = i+1; j < trail->length(); j++) {
+          (*trail)[j] = -1;
+        }
+        return Object::null();
+      }
+    }
+  }
+
   intptr_t ignore = 0;
-
   // Lookup the name in the library's symbols.
   Object& obj = Object::Handle(zone, lib.LookupEntry(name, &ignore));
   if (!Field::IsGetterName(name) &&
       !Field::IsSetterName(name) &&
       (obj.IsNull() || obj.IsLibraryPrefix())) {
     String& accessor_name = String::Handle(zone);
     accessor_name ^= Field::LookupGetterSymbol(name);
     if (!accessor_name.IsNull()) {
       obj = lib.LookupEntry(accessor_name, &ignore);
     }
     if (obj.IsNull()) {
       accessor_name ^= Field::LookupSetterSymbol(name);
       if (!accessor_name.IsNull()) {
         obj = lib.LookupEntry(accessor_name, &ignore);
       }
     }
   }
 
   // Library prefixes are not exported.
   if (obj.IsNull() || obj.IsLibraryPrefix()) {
     // Lookup in the re-exported symbols.
-    obj = lib.LookupReExport(name);
+    obj = lib.LookupReExport(name, trail);
     if (obj.IsNull() && !Field::IsSetterName(name)) {
       // LookupReExport() only returns objects that match the given name.
       // If there is no field/func/getter, try finding a setter.
       const String& setter_name =
           String::Handle(zone, Field::LookupSetterSymbol(name));
       if (!setter_name.IsNull()) {
-        obj = lib.LookupReExport(setter_name);
+        obj = lib.LookupReExport(setter_name, trail);
       }
     }
   }
   if (obj.IsNull() || HidesName(name) || obj.IsLibraryPrefix()) {
     return Object::null();
   }
   return obj.raw();
 }
 
 
@@ skipping 10968 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart