From febfafcf7f0e4d1cbe878e7dfffd9c9b78036aed Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Tue, 5 Dec 2017 17:34:00 +0200 Subject: Add support for first-access value typification during non-load phases --- build2/types.hxx | 35 +++++++++++++++++++++++++++++++++++ build2/variable.cxx | 49 ++++++++++++++++++++++++------------------------- build2/variable.hxx | 32 +++++++++++++++++++++++++++----- build2/variable.ixx | 43 ++++++++++++++++++++++++++----------------- build2/variable.txx | 6 +++--- 5 files changed, 115 insertions(+), 50 deletions(-) diff --git a/build2/types.hxx b/build2/types.hxx index cf95a9d..2f07029 100644 --- a/build2/types.hxx +++ b/build2/types.hxx @@ -98,6 +98,41 @@ namespace build2 using atomic_count = atomic; // Matches scheduler::atomic_count. + // Like std::atomic except implicit conversion and assignment use relaxed + // memory ordering. + // + template + struct relaxed_atomic: atomic + { + using atomic::atomic; // Delegate. + relaxed_atomic (const relaxed_atomic& a) noexcept + : atomic (a.load (memory_order_relaxed)) {} + + operator T () const noexcept {return this->load (memory_order_relaxed);} + + T operator= (T v) noexcept { + this->store (v, memory_order_relaxed); return v;} + T operator= (const relaxed_atomic& a) noexcept { + return *this = a.load (memory_order_relaxed);} + }; + + template + struct relaxed_atomic: atomic + { + using atomic::atomic; // Delegate. + relaxed_atomic (const relaxed_atomic& a) noexcept + : atomic (a.load (memory_order_relaxed)) {} + + operator T* () const noexcept {return this->load (memory_order_relaxed);} + T& operator* () const noexcept {return *this->load (memory_order_relaxed);} + T* operator-> () const noexcept {return this->load (memory_order_relaxed);} + + T* operator= (T* v) noexcept { + this->store (v, memory_order_relaxed); return v;} + T* operator= (const relaxed_atomic& a) noexcept { + return *this = a.load (memory_order_relaxed);} + }; + using std::mutex; using mlock = std::unique_lock; diff --git a/build2/variable.cxx b/build2/variable.cxx index 6eb2377..ed9527e 100644 --- a/build2/variable.cxx +++ b/build2/variable.cxx @@ -334,6 +334,19 @@ namespace build2 } void + typify_atomic (value& v, const value_type& t, const variable* var) + { + // Typification is kind of like caching so we reuse that mutex shard. + // + shared_mutex& m ( + variable_cache_mutex_shard[ + hash () (&v) % variable_cache_mutex_shard_size]); + + ulock l (m); + typify (v, t, var); // v.type is rechecked by typify(), stored under lock. + } + + void untypify (value& v) { if (v.type == nullptr) @@ -1228,29 +1241,16 @@ namespace build2 // variable_map // - void variable_map:: - typify (value_data& v, const variable& var) const - { - // We assume typification is not modification so no version increment. - // - build2::typify (v, *var.type, &var); - } - auto variable_map:: find (const variable& var, bool typed) const -> const value_data* { auto i (m_.find (var)); const value_data* r (i != m_.end () ? &i->second : nullptr); - // First access after being assigned a type? + // Check if this is the first access after being assigned a type. // - if (r != nullptr && typed && var.type != nullptr && r->type != var.type) - { - // All values shall be typed during load. - // - assert (!global_ || phase == run_phase::load); - typify (const_cast (*r), var); - } + if (r != nullptr && typed && var.type != nullptr) + typify (*r, var); return r; } @@ -1276,9 +1276,11 @@ namespace build2 if (!p.second) { - // First access after being assigned a type? + // Check if this is the first access after being assigned a type. // - if (typed && var.type != nullptr && r.type != var.type) + // Note: we still need atomic in case this is not a global state. + // + if (typed && var.type != nullptr) typify (r, var); } @@ -1351,13 +1353,10 @@ namespace build2 if (const variable_map::value_data* v = vm.find (var, false)) { - if (v->extra == 0 && var.type != nullptr && v->type != var.type) - { - // All values shall be typed during load. - // - assert (!global_ || phase == run_phase::load); - vm.typify (const_cast (*v), var); - } + // Check if this is the first access after being assigned a type. + // + if (v->extra == 0 && var.type != nullptr) + vm.typify (*v, var); return lookup (*v, vm); } diff --git a/build2/variable.hxx b/build2/variable.hxx index aa00eb8..bba2208 100644 --- a/build2/variable.hxx +++ b/build2/variable.hxx @@ -20,6 +20,17 @@ namespace build2 { + // Some general variable infrastructure rules: + // + // 1. A variable can only be entered or typified during the load phase. + // + // 2. Any entity (module) that caches a variable value must make sure the + // variable has already been typified. + // + // 3. Any entity (module) that assigns a target-specific variable value + // during a phase other than load must make sure the variable has already + // been typified. + class value; struct variable; struct lookup; @@ -139,7 +150,16 @@ namespace build2 class value { public: - const value_type* type; // NULL means this value is not (yet) typed. + // NULL means this value is not (yet) typed. + // + // Atomic access is used to implement on-first-access typification of + // values store in variable_map. Direct access as well as other functions + // that operate on values directly all use non-atomic access. + // + relaxed_atomic type; + + // True if there is no value. + // bool null; // Extra data that is associated with the value that can be used to store @@ -310,8 +330,9 @@ namespace build2 // for diagnostics. // template - void typify (value&, const variable*); - void typify (value&, const value_type&, const variable*); + void typify (value&, const variable*); + void typify (value&, const value_type&, const variable*); + void typify_atomic (value&, const value_type&, const variable*); // Remove value type from the value reversing it to names. This is similar // to reverse() below except that it modifies the value itself. @@ -1205,7 +1226,7 @@ namespace build2 friend class variable_type_map; void - typify (value_data&, const variable&) const; + typify (const value_data&, const variable&) const; private: bool global_; @@ -1223,7 +1244,8 @@ namespace build2 // // Note that since the cache can be modified on any lookup (including during // the execute phase), it is protected by its own mutex shard (allocated in - // main()). + // main()). This shard is also used for value typification (which is kind of + // like caching) during concurrent execution phases. // extern size_t variable_cache_mutex_shard_size; extern unique_ptr variable_cache_mutex_shard; diff --git a/build2/variable.ixx b/build2/variable.ixx index d7c4326..0a235e5 100644 --- a/build2/variable.ixx +++ b/build2/variable.ixx @@ -232,7 +232,7 @@ namespace build2 inline void typify (value& v, const variable* var) { - value_type& t (value_traits::value_type); + const value_type& t (value_traits::value_type); if (v.type != &t) typify (v, t, var); @@ -689,6 +689,25 @@ namespace build2 return i != map_.end () ? &i->second : nullptr; } + // variable_map + // + inline void variable_map:: + typify (const value_data& v, const variable& var) const + { + // We assume typification is not modification so no version increment. + // + if (phase == run_phase::load) + { + if (v.type != var.type) + build2::typify (const_cast (v), *var.type, &var); + } + else + { + if (v.type.load (memory_order_acquire) != var.type) + build2::typify_atomic (const_cast (v), *var.type, &var); + } + } + // variable_map::iterator_adapter // template @@ -699,15 +718,10 @@ namespace build2 const variable& var (r.first); const value_data& val (r.second); - // First access after being assigned a type? + // Check if this is the first access after being assigned a type. // - if (var.type != nullptr && val.type != var.type) - { - // All values shall be typed during load. - // - assert (!m_->global_ || phase == run_phase::load); - m_->typify (const_cast (val), var); - } + if (var.type != nullptr) + m_->typify (val, var); return r; } @@ -720,15 +734,10 @@ namespace build2 const variable& var (p->first); const value_data& val (p->second); - // First access after being assigned a type? + // Check if this is the first access after being assigned a type. // - if (var.type != nullptr && val.type != var.type) - { - // All values shall be typed during load. - // - assert (!m_->global_ || phase == run_phase::load); - m_->typify (const_cast (val), var); - } + if (var.type != nullptr) + m_->typify (val, var); return p; } diff --git a/build2/variable.txx b/build2/variable.txx index aebbe1a..e374f22 100644 --- a/build2/variable.txx +++ b/build2/variable.txx @@ -601,9 +601,9 @@ namespace build2 // Cache hit. // - if (i != m_.end () && - i->second.version == ver && - i->second.stem_vars == svars && + if (i != m_.end () && + i->second.version == ver && + i->second.stem_vars == svars && i->second.stem_version == sver && (var.type == nullptr || i->second.value.type == var.type)) return pair (i->second.value, move (ul)); -- cgit v1.1