aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2017-02-13 09:48:12 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2017-02-13 12:42:42 +0200
commit737877e62467b924eea0a43eab68258b0c13db78 (patch)
tree3fe2f539a21ce0407cdaa908a9af56b4cf8087e0
parent38290dacd8faab166774d757a1e09807e57e9ba5 (diff)
Add MT-safe variable_cache, use for variable overrides
-rw-r--r--build2/b.cxx6
-rw-r--r--build2/context4
-rw-r--r--build2/context.cxx4
-rw-r--r--build2/scope12
-rw-r--r--build2/scope.cxx95
-rw-r--r--build2/types7
-rw-r--r--build2/variable50
-rw-r--r--build2/variable.cxx3
-rw-r--r--build2/variable.txx69
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));
+ }
}