Add MT-safe variable_cache, use for variable overrides

9 files changed, 181 insertions, 69 deletions

diff --git a/build2/b.cxx b/build2/b.cxx
index 14258b3..01d9378 100644
--- a/build2/b.cxx
+++ b/build2/b.cxx
@@ -273,7 +273,7 @@ main (int argc, char* argv[])
 
     keep_going = !ops.serial_stop ();
 
-    // Start up the scheduler.
+    // Start up the scheduler and allocate lock shards.
     //
     size_t jobs (0);
 
@@ -296,6 +296,10 @@ main (int argc, char* argv[])
 
     sched.startup (jobs);
 
+    variable_cache_mutex_shard_size = sched.shard_size ();
+    variable_cache_mutex_shard.reset (
+      new shared_mutex[variable_cache_mutex_shard_size]);
+
     // Trace some overall environment information.
     //
     if (verb >= 5)
diff --git a/build2/context b/build2/context
index 3c731a5..79f04a2 100644
--- a/build2/context
+++ b/build2/context
@@ -253,10 +253,6 @@ namespace build2
   //
   extern atomic_count dependency_count;
 
-  // Variable override value cache.
-  //
-  extern variable_override_cache var_override_cache;
-
   // Reset the build state. In particular, this removes all the targets,
   // scopes, and variables.
   //
diff --git a/build2/context.cxx b/build2/context.cxx
index cbb2656..8b4fd52 100644
--- a/build2/context.cxx
+++ b/build2/context.cxx
@@ -60,8 +60,6 @@ namespace build2
 
   atomic_count dependency_count;
 
-  variable_override_cache var_override_cache;
-
   variable_overrides
   reset (const strings& cmd_vars)
   {
@@ -77,8 +75,6 @@ namespace build2
 
     variable_overrides vos;
 
-    var_override_cache.clear ();
-
     targets.clear ();
     sm.clear ();
     vp.clear ();
diff --git a/build2/scope b/build2/scope
index 64aaf24..2b86200 100644
--- a/build2/scope
+++ b/build2/scope
@@ -177,6 +177,18 @@ namespace build2
     //
     variable_type_map target_vars;
 
+    // Variable override cache (project root and global scope only).
+    //
+    // The key is the variable plus the innermost (scope-wise) variable map to
+    // which this override applies. See find_override() for details.
+    //
+    // Note: since it can be modified on any lookup (including during the
+    // execute phase), the cache is protected by its own mutex shard.
+    //
+    mutable
+    variable_cache<pair<const variable*, const variable_map*>>
+    override_cache;
+
     // Meta/operations supported by this project (set on the root
     // scope only).
     //
diff --git a/build2/scope.cxx b/build2/scope.cxx
index 6f21636..d7e9d8e 100644
--- a/build2/scope.cxx
+++ b/build2/scope.cxx
@@ -329,19 +329,7 @@ namespace build2
     if (inner_proj == nullptr)
       inner_proj = global_scope;
 
-    // Implementing proper caching is tricky so for now we are going to re-
-    // calculate the value every time. Later, the plan is to use value
-    // versioning (incremented on every update) to detect stem value changes.
-    // We also need to watch out for the change of the stem itself in addition
-    // to its value (think of a new variable set since last lookup which is
-    // now a new stem). Thus stem_vars in variable_override_value.
-    //
-    // @@ MT
-    //
-    variable_override_value& cache (
-      var_override_cache[make_pair (inner_vars, &var)]);
-
-    // Now find our "stem", that is the value to which we will be appending
+    // Now find our "stem", that is, the value to which we will be appending
     // suffixes and prepending prefixes. This is either the original or the
     // __override, provided it applies. We may also not have either.
     //
@@ -404,41 +392,51 @@ namespace build2
         break;
     }
 
-    // If there is a stem, set it as the initial value of the cache.
-    // Otherwise, start with a NULL value.
-    //
-    // Note: very similar logic as in the target type/pattern specific cache
-    // population code above.
+    // Check the cache.
     //
+    pair<value&, ulock> cache (
+      inner_proj->override_cache.insert (
+        make_pair (&var, inner_vars), stem));
 
-    // Un-typify the cache. This can be necessary, for example, if we are
-    // changing from one value-typed stem to another.
+    value& cv (cache.first);
+    bool cl (cache.second.owns_lock ());
+
+    // If cache miss/invalidation, update the value.
     //
-    if (!stem.defined () || cache.value.type != stem->type)
+    if (cl)
     {
-      cache.value = nullptr;
-      cache.value.type = nullptr; // Un-typify.
-    }
+      // Note: very similar logic as in the target type/pattern specific cache
+      // population code above.
+      //
 
-    if (stem.defined ())
-    {
-      cache.value = *stem;
-      cache.stem_vars = stem.vars;
+      // Un-typify the cache. This can be necessary, for example, if we are
+      // changing from one value-typed stem to another.
+      //
+      if (!stem.defined () || cv.type != stem->type)
+      {
+        cv = nullptr;
+        cv.type = nullptr; // Un-typify.
+      }
+
+      if (stem.defined ())
+        cv = *stem;
+
+      // Typify the cache value. If the stem is the original, then the type
+      // would get propagated automatically. But the stem could also be the
+      // override, which is kept untyped. Or the stem might not be there at
+      // all while we still need to apply prefixes/suffixes in the type-aware
+      // way.
+      //
+      if (cv.type == nullptr && var.type != nullptr)
+        typify (cv, *var.type, &var);
     }
-    else
-      cache.stem_vars = nullptr; // No stem.
 
-    // Typify the cache value. If the stem is the original, then the type
-    // would get propagated automatically. But the stem could also be the
-    // override, which is kept untyped. Or the stem might not be there at all
-    // while we still need to apply prefixes/suffixes in the type-aware way.
+    // Now apply override prefixes and suffixes (if updating the cache). Also
+    // calculate the vars and depth of the result, which will be those of the
+    // stem or prefix/suffix that applies, whichever is the innermost.
     //
-    if (cache.value.type == nullptr && var.type != nullptr)
-      typify (cache.value, *var.type, &var);
-
-    // Now apply override prefixes and suffixes. Also calculate the vars and
-    // depth of the result, which will be those of the stem or prefix/suffix
-    // that applies, whichever is the innermost.
+    // Note: we could probably cache this information instead of recalculating
+    // it every time.
     //
     size_t depth (stem_depth);
     const variable_map* vars (stem.vars);
@@ -468,13 +466,16 @@ namespace build2
         //
         auto l (find (o, ".__prefix"));
 
-        if (l) // No sense to prepend/append if NULL.
+        if (cl)
         {
-          cache.value.prepend (names (cast<names> (l)), &var);
-        }
-        else if ((l = find (o, ".__suffix")))
-        {
-          cache.value.append (names (cast<names> (l)), &var);
+          if (l) // No sense to prepend/append if NULL.
+          {
+            cv.prepend (names (cast<names> (l)), &var);
+          }
+          else if ((l = find (o, ".__suffix")))
+          {
+            cv.append (names (cast<names> (l)), &var);
+          }
         }
 
         if (l.defined ())
@@ -502,7 +503,7 @@ namespace build2
     // Use the location of the innermost value that contributed as the
     // location of the result.
     //
-    return make_pair (lookup (&cache.value, vars), depth);
+    return make_pair (lookup (&cv, vars), depth);
   }
 
   value& scope::
diff --git a/build2/types b/build2/types
index 0e6012b..82ee889 100644
--- a/build2/types
+++ b/build2/types
@@ -15,7 +15,7 @@
 #include <cstdint>          // uint{8,16,32,64}_t, *_MIN, *_MAX
 #include <istream>
 #include <ostream>
-#include <functional>       // function, reference_wrapper
+#include <functional>       // hash, function, reference_wrapper
 #include <initializer_list>
 
 #include <mutex>
@@ -61,6 +61,8 @@ namespace build2
   using std::function;
   using std::reference_wrapper;
 
+  using std::hash;
+
   using std::initializer_list;
 
   using std::unique_ptr;
@@ -101,6 +103,9 @@ namespace build2
   using slock        = ulock;
 #endif
 
+  using std::defer_lock;
+  using std::adopt_lock;
+
   // Exceptions.
   //
   // While <exception> is included, there is no using for std::exception --
diff --git a/build2/variable b/build2/variable
index 6c579dd..35530ca 100644
--- a/build2/variable
+++ b/build2/variable
@@ -1219,11 +1219,7 @@ namespace build2
     lookup
     find (const target_type&, const string& tname, const variable&) const;
 
-    // In many places we assume that we can store a reference to the returned
-    // variable value (e.g., install::lookup_install()). As a result, in case
-    // of append/prepend where we calculate the value dynamically, we have to
-    // cache it (note, however, that if the value becomes stale, there is no
-    // guarantee the references remain valid).
+
     //
     // The key is the combination of the "original value identity" (as a
     // pointer to the value in one of the variable_pattern_map's) and the
@@ -1241,17 +1237,47 @@ namespace build2
     map_type map_;
   };
 
-  // Variable override cache.
+  // Value caching. Used for overrides as well as target type/pattern-specific
+  // append/prepend.
+  //
+  // In many places we assume that we can store a reference to the returned
+  // variable value (e.g., install::lookup_install()). As a result, in these
+  // cases where we calculate the value dynamically, we have to cache it
+  // (note, however, that if the value becomes stale, there is no guarantee
+  // the references remain valid).
   //
-  struct variable_override_value
+  template <typename K>
+  class variable_cache
   {
-    variable_map::value_data value;
-    const variable_map* stem_vars = nullptr; // NULL means there is no stem.
+  public:
+    // If the returned unique lock is locked, then the value has been
+    // invalidated.
+    //
+    pair<value&, ulock>
+    insert (K, const lookup& stem);
+
+  private:
+    struct entry_type
+    {
+      build2::value value;
+
+      // Location of the stem as well as the version on which this cache
+      // value is based. Used to track the location and value of the stem
+      // for cache invalidation. NULL/0 means there is no stem.
+      //
+      const variable_map* stem_vars = nullptr;
+      size_t              stem_version = 0;
+    };
+
+    using map_type = std::map<K, entry_type>;
+
+    map_type m_;
   };
 
-  using variable_override_cache = std::map<pair<const variable_map*,
-                                                const variable*>,
-                                           variable_override_value>;
+  // Allocated in main().
+  //
+  extern size_t variable_cache_mutex_shard_size;
+  extern unique_ptr<shared_mutex[]> variable_cache_mutex_shard;
 }
 
 #include <build2/variable.ixx>
diff --git a/build2/variable.cxx b/build2/variable.cxx
index 7e105e6..09790b4 100644
--- a/build2/variable.cxx
+++ b/build2/variable.cxx
@@ -1283,4 +1283,7 @@ namespace build2
 
     return lookup ();
   }
+
+  size_t variable_cache_mutex_shard_size;
+  unique_ptr<shared_mutex[]> variable_cache_mutex_shard;
 }
diff --git a/build2/variable.txx b/build2/variable.txx
index b993200..5b212f0 100644
--- a/build2/variable.txx
+++ b/build2/variable.txx
@@ -552,4 +552,73 @@ namespace build2
     &map_compare<K, V>,
     &default_empty<map<K, V>>
   };
+
+  // variable_cache
+  //
+  template <typename K>
+  pair<value&, ulock> variable_cache<K>::
+  insert (K k, const lookup& stem)
+  {
+    const variable_map* vars (stem.vars); // NULL if undefined.
+    size_t ver (
+      stem.defined ()
+      ? static_cast<const variable_map::value_data*> (stem.value)->version
+      : 0);
+
+    shared_mutex& m (
+      variable_cache_mutex_shard[
+        hash<variable_cache*> () (this) % variable_cache_mutex_shard_size]);
+
+    slock sl (m);
+    ulock ul (m, defer_lock);
+
+    auto i (m_.find (k));
+
+    // Cache hit.
+    //
+    if (i != m_.end ()              &&
+        i->second.stem_vars == vars &&
+        i->second.stem_version == ver)
+      return pair<value&, ulock> (i->second.value, move (ul));
+
+    // Relock for exclusive access. Note that it is entirely possible
+    // that between unlock and lock someone else has updated the entry.
+    //
+    sl.unlock ();
+    ul.lock ();
+
+    // Note that the cache entries are never removed so we can reuse the
+    // iterator.
+    //
+    pair<typename map_type::iterator, bool> p (i, i == m_.end ());
+
+    if (p.second)
+      p = m_.emplace (move (k), entry_type {value (nullptr), vars, ver});
+
+    entry_type& e (p.first->second);
+
+    // Cache miss.
+    //
+    if (p.second)
+      ;
+    //
+    // Cache invalidation.
+    //
+    else if (e.stem_vars != vars || e.stem_version != ver)
+    {
+      if (e.stem_vars != vars)
+        e.stem_vars = vars;
+      else
+        assert (e.stem_version <= ver);
+
+      e.stem_version = ver;
+    }
+    //
+    // Cache hit.
+    //
+    else
+      ul.unlock ();
+
+    return pair<value&, ulock> (e.value, move (ul));
+  }
 }