Add header cache to cc::compile_rule::enter_header()

6 files changed, 202 insertions, 35 deletions

diff --git a/libbuild2/c/init.cxx b/libbuild2/c/init.cxx
index f39114c..4c051b0 100644
--- a/libbuild2/c/init.cxx
+++ b/libbuild2/c/init.cxx
@@ -391,7 +391,7 @@ namespace build2
         inc
       };
 
-      auto& m (extra.set_module (new module (move (d))));
+      auto& m (extra.set_module (new module (move (d), rs)));
       m.init (rs, loc, extra.hints, *cm.x_info);
 
       return true;
diff --git a/libbuild2/cc/compile-rule.cxx b/libbuild2/cc/compile-rule.cxx
index a5e5417..002c889 100644
--- a/libbuild2/cc/compile-rule.cxx
+++ b/libbuild2/cc/compile-rule.cxx
@@ -248,12 +248,34 @@ namespace build2
     };
 
     compile_rule::
-    compile_rule (data&& d)
+    compile_rule (data&& d, const scope& rs)
         : common (move (d)),
           rule_id (string (x) += ".compile 6")
     {
       static_assert (sizeof (match_data) <= target::data_size,
                      "insufficient space");
+
+      // Locate the header cache (see enter_header() for details).
+      //
+      {
+        string mn (string (x) + ".config");
+
+        header_cache_ = rs.find_module<config_module> (mn); // Must be there.
+
+        const scope* ws (rs.weak_scope ());
+        if (ws != &rs)
+        {
+          const scope* s (&rs);
+          do
+          {
+            s = s->parent_scope ()->root_scope ();
+
+            if (const auto* m = s->find_module<config_module> (mn))
+              header_cache_ = m;
+
+          } while (s != ws);
+        }
+      }
     }
 
     template <typename T>
@@ -2044,7 +2066,7 @@ namespace build2
               pair<const file*, bool> er (
                 enter_header (
                   a, bs, t, li,
-                  f, false /* cache */, false /* normalized */,
+                  move (f), false /* cache */, false /* normalized */,
                   pfx_map, so_map));
 
               ht = er.first;
@@ -2062,7 +2084,7 @@ namespace build2
               // diagnostics won't really add anything to the compiler's. So
               // let's only print it at -V or higher.
               //
-              if (ht == nullptr)
+              if (ht == nullptr) // f is still valid.
               {
                 assert (!exists); // Sanity check.
 
@@ -2110,6 +2132,8 @@ namespace build2
               // messy, let's keep both (it would have been nicer to print
               // ours after the compiler's but that isn't easy).
               //
+              // Note: if ht is NULL, f is still valid.
+              //
               r = "ERROR unable to update header '";
               r += (ht != nullptr ? ht->path () : f).string ();
               r += '\'';
@@ -2573,7 +2597,7 @@ namespace build2
               pair<const file*, bool> r (
                 enter_header (
                   a, bs, t, li,
-                  f, false /* cache */, false /* normalized */,
+                  move (f), false /* cache */, false /* normalized */,
                   pfx_map, so_map));
 
               if (!r.second) // Shouldn't be remapped.
@@ -2601,7 +2625,7 @@ namespace build2
               pair<const file*, bool> er (
                 enter_header (
                   a, bs, t, li,
-                  f, false /* cache */, false /* normalized */,
+                  move (f), false /* cache */, false /* normalized */,
                   pfx_map, so_map));
 
               ht = er.first;
@@ -2620,7 +2644,7 @@ namespace build2
               // diagnostics won't really add anything to the compiler's. So
               // let's only print it at -V or higher.
               //
-              if (ht == nullptr)
+              if (ht == nullptr) // f is still valid.
               {
                 assert (!exists); // Sanity check.
 
@@ -2667,6 +2691,8 @@ namespace build2
               // messy, let's keep both (it would have been nicer to print
               // ours after the compiler's but that isn't easy).
               //
+              // Note: if ht is NULL, f is still valid.
+              //
               rs = !exists
                 ? string ("INCLUDE")
                 : ("ERROR unable to update header '" +
@@ -2790,17 +2816,115 @@ namespace build2
     }
 #endif
 
+    //atomic_count cache_hit {0};
+    //atomic_count cache_mis {0};
+    //atomic_count cache_cls {0};
+
+    // The fp path is only moved from on success.
+    //
     // Note: this used to be a lambda inside extract_headers() so refer to the
     // body of that function for the overall picture.
     //
     pair<const file*, bool> compile_rule::
     enter_header (action a, const scope& bs, file& t, linfo li,
-                  path& fp, bool cache, bool norm,
+                  path&& fp, bool cache, bool norm,
                   optional<prefix_map>& pfx_map,
                   const srcout_map& so_map) const
     {
       tracer trace (x, "compile_rule::enter_header");
 
+      // It's reasonable to expect the same header to be included by multiple
+      // translation units, which means we will be re-doing this work over and
+      // over again. And it's not exactly cheap, taking up to 50% of an
+      // up-to-date check time on some projects. So we are going to cache the
+      // header path to target mapping.
+      //
+      // While we pass quite a bit of specific "context" (target, base scope)
+      // to enter_file(), here is the analysis why the result will not depend
+      // on this context for the non-absent header (fp is absolute):
+      //
+      // 1. Let's start with the base scope (bs). Firstly, the base scope
+      //    passed to map_extension() is the scope of the header (i.e., it is
+      //    the scope of fp.directory()). Other than that, the target base
+      //    scope is only passed to build_prefix_map() which is only called
+      //    for the absent header (linfo is also only used here).
+      //
+      // 2. Next is the target (t). It is passed to build_prefix_map() but
+      //    that doesn't matter for the same reason as in (1). Other than
+      //    that, it is only passed to build2::search() which in turn passes
+      //    it to target type-specific prerequisite search callback (see
+      //    target_type::search) if one is not NULL. The target type in
+      //    question here is one of the headers and we know all of them use
+      //    the standard file_search() which ignores the passed target.
+      //
+      // 3. Finally, so_map could be used for an absolute fp. While we could
+      //    simply not cache the result if it was used (second half of the
+      //    result pair is true), there doesn't seem to be any harm in caching
+      //    the remapped path->target mapping. In fact, if to think about it,
+      //    there is no harm in caching the generated file mapping since it
+      //    will be immediately generated and any subsequent inclusions we
+      //    will "see" with an absolute path, which we can resolve from the
+      //    cache.
+      //
+      // To put it another way, all we need to do is make sure that if we were
+      // to not return an existing cache entry, the call to enter_file() would
+      // have returned exactly the same path/target.
+      //
+      // @@ Could it be that the header is re-mapped in one config but not the
+      //    other (e.g., when we do both in src and in out builds and we pick
+      //    the generated header in src)? If so, that would lead to a
+      //    divergence. I.e., we would cache the no-remap case first and then
+      //    return it even though the re-map is necessary? Why can't we just
+      //    check for re-mapping ourselves? A: the remapping logic in
+      //    enter_file() is not exactly trivial.
+      //
+      //    But on the other hand, I think we can assume that different
+      //    configurations will end up with different caches. In other words,
+      //    we can assume that for the same "cc amalgamation" we use only a
+      //    single "version" of a header. Seems reasonable.
+      //
+      // Note also that while it would have been nice to have a unified cc
+      // cache, the map_extension() call is passed x_inc which is module-
+      // specific. In other words, we may end up mapping the same header to
+      // two different targets depending on whether it is included from, say,
+      // C or C++ translation unit. We could have used a unified cache for
+      // headers that were mapped using the fallback target type, which would
+      // cover the installed headers. Maybe, one day (it's also possible that
+      // separate caches reduce contention).
+      //
+      // Another related question is where we want to keep the cache: project,
+      // strong amalgamation, or weak amalgamation (like module sidebuilds).
+      // Some experimentation showed that weak has the best performance (which
+      // suggest that a unified cache will probably be a win).
+      //
+      // Note also that we don't need to clear this cache since we never clear
+      // the targets set. In other words, the only time targets are
+      // invalidated is when we destroy the build context, which also destroys
+      // the cache.
+      //
+      const config_module& hc (*header_cache_);
+
+      // First check the cache.
+      //
+      if (fp.absolute ())
+      {
+        if (!norm)
+        {
+          normalize_external (fp, "header");
+          norm = true;
+        }
+
+        slock l (hc.header_map_mutex);
+        auto i (hc.header_map.find (fp));
+        if (i != hc.header_map.end ())
+        {
+          //cache_hit.fetch_add (1, memory_order_relaxed);
+          return make_pair (i->second, false);
+        }
+
+        //cache_mis.fetch_add (1, memory_order_relaxed);
+      }
+
       struct data
       {
         linfo li;
@@ -2810,24 +2934,44 @@ namespace build2
       // If it is outside any project, or the project doesn't have such an
       // extension, assume it is a plain old C header.
       //
-      return enter_file (
-        trace, "header",
-        a, bs, t,
-        fp, cache, norm,
-        [this] (const scope& bs, const string& n, const string& e)
+      auto r (enter_file (
+                trace, "header",
+                a, bs, t,
+                fp, cache, norm,
+                [this] (const scope& bs, const string& n, const string& e)
+                {
+                  return map_extension (bs, n, e, x_inc);
+                },
+                h::static_type,
+                [this, &d] (action a, const scope& bs, const target& t)
+                  -> const prefix_map&
+                {
+                  if (!d.pfx_map)
+                    d.pfx_map = build_prefix_map (bs, a, t, d.li);
+
+                  return *d.pfx_map;
+                },
+                so_map));
+
+      // Cache.
+      //
+      if (r.first != nullptr)
+      {
+        const file* f;
         {
-          return map_extension (bs, n, e, x_inc);
-        },
-        h::static_type,
-        [this, &d] (action a, const scope& bs, const target& t)
-          -> const prefix_map&
+          ulock l (hc.header_map_mutex);
+          auto p (hc.header_map.emplace (move (fp), r.first));
+          f = p.second ? nullptr : p.first->second;
+        }
+
+        if (f != nullptr)
         {
-          if (!d.pfx_map)
-            d.pfx_map = build_prefix_map (bs, a, t, d.li);
+          //cache_cls.fetch_add (1, memory_order_relaxed);
+          assert (r.first == f);
+        }
+      }
 
-          return *d.pfx_map;
-        },
-        so_map);
+      return r;
     }
 
     // Note: this used to be a lambda inside extract_headers() so refer to the
@@ -3588,7 +3732,7 @@ namespace build2
 
         if (const file* ht = enter_header (
               a, bs, t, li,
-              hp, cache, cache /* normalized */,
+              move (hp), cache, cache /* normalized */,
               pfx_map, so_map).first)
         {
           // If we are reading the cache, then it is possible the file has
@@ -3603,7 +3747,7 @@ namespace build2
             // Verify/add it to the dependency database.
             //
             if (!cache)
-              dd.expect (ht->path ()); // @@ Use hp (or verify match)?
+              dd.expect (ht->path ());
 
             skip_count++;
             return *u;
@@ -3617,7 +3761,7 @@ namespace build2
             return fail (*ht);
         }
         else
-          return fail (hp);
+          return fail (hp); // hp is still valid.
       };
 
       // As above but for a header unit. Note that currently it is only used
@@ -3634,10 +3778,10 @@ namespace build2
 
         const file* ht (
           enter_header (a, bs, t, li,
-                        hp, true /* cache */, false /* normalized */,
+                        move (hp), true /* cache */, false /* normalized */,
                         pfx_map, so_map).first);
 
-        if (ht == nullptr)
+        if (ht == nullptr) // hp is still valid.
         {
           diag_record dr;
           dr << error << "header " << hp << " not found and no rule to "
@@ -5738,6 +5882,9 @@ namespace build2
       // cc.config module and that is within our amalgmantion seems like a
       // good place.
       //
+      // @@ TODO: maybe we should cache this in compile_rule ctor like we
+      //          do for the header cache?
+      //
       const scope* as (&rs);
       {
         const scope* ws (as->weak_scope ());
@@ -5753,7 +5900,7 @@ namespace build2
             // This is also the module that registers the scope operation
             // callback that cleans up the subproject.
             //
-            if (cast_false<bool> ((*s)["cc.core.vars.loaded"]))
+            if (cast_false<bool> (s->vars["cc.core.vars.loaded"]))
               as = s;
 
           } while (s != ws);
diff --git a/libbuild2/cc/compile-rule.hxx b/libbuild2/cc/compile-rule.hxx
index 00965fc..16b33fa 100644
--- a/libbuild2/cc/compile-rule.hxx
+++ b/libbuild2/cc/compile-rule.hxx
@@ -22,6 +22,8 @@ namespace build2
 
   namespace cc
   {
+    class config_module;
+
     // The order is arranged so that their integral values indicate whether
     // one is a "stronger" than another.
     //
@@ -42,7 +44,7 @@ namespace build2
                                                dyndep_rule
     {
     public:
-      compile_rule (data&&);
+      compile_rule (data&&, const scope&);
 
       virtual bool
       match (action, target&) const override;
@@ -120,7 +122,7 @@ namespace build2
 
       pair<const file*, bool>
       enter_header (action, const scope&, file&, linfo,
-                    path&, bool, bool,
+                    path&&, bool, bool,
                     optional<prefix_map>&, const srcout_map&) const;
 
       optional<bool>
@@ -180,6 +182,7 @@ namespace build2
 
     private:
       const string rule_id;
+      const config_module* header_cache_;
     };
   }
 }
diff --git a/libbuild2/cc/module.hxx b/libbuild2/cc/module.hxx
index a91d723..ee9349a 100644
--- a/libbuild2/cc/module.hxx
+++ b/libbuild2/cc/module.hxx
@@ -4,6 +4,8 @@
 #ifndef LIBBUILD2_CC_MODULE_HXX
 #define LIBBUILD2_CC_MODULE_HXX
 
+#include <unordered_map>
+
 #include <libbuild2/types.hxx>
 #include <libbuild2/utility.hxx>
 
@@ -78,6 +80,15 @@ namespace build2
 
       bool new_config = false; // See guess() and init() for details.
 
+      // Header cache (see compile_rule::enter_header()).
+      //
+      // We place it into the config module so that we have an option of
+      // sharing it for the entire weak amalgamation.
+      //
+    public:
+      mutable shared_mutex                          header_map_mutex;
+      mutable std::unordered_map<path, const file*> header_map;
+
     private:
       // Defined in gcc.cxx.
       //
@@ -105,10 +116,10 @@ namespace build2
     {
     public:
       explicit
-      module (data&& d)
+      module (data&& d, const scope& rs)
           : common (move (d)),
             link_rule (move (d)),
-            compile_rule (move (d)),
+            compile_rule (move (d), rs),
             install_rule (move (d), *this),
             libux_install_rule (move (d), *this) {}
 
diff --git a/libbuild2/cxx/init.cxx b/libbuild2/cxx/init.cxx
index 0ebb424..3a934db 100644
--- a/libbuild2/cxx/init.cxx
+++ b/libbuild2/cxx/init.cxx
@@ -868,7 +868,7 @@ namespace build2
         inc
       };
 
-      auto& m (extra.set_module (new module (move (d))));
+      auto& m (extra.set_module (new module (move (d), rs)));
       m.init (rs, loc, extra.hints, *cm.x_info);
 
       return true;
diff --git a/libbuild2/dyndep.cxx b/libbuild2/dyndep.cxx
index 727a28c..55b02ed 100644
--- a/libbuild2/dyndep.cxx
+++ b/libbuild2/dyndep.cxx
@@ -389,6 +389,9 @@ namespace build2
     const function<dyndep_rule::prefix_map_func>& get_pfx_map,
     const dyndep_rule::srcout_map& so_map)
   {
+    // NOTE: see enter_header() caching logic if changing anyting here with
+    //       regards to the target and base scope usage.
+
     // Find or maybe insert the target. The directory is only moved from if
     // insert is true. Note that it must be normalized.
     //
@@ -561,6 +564,9 @@ namespace build2
     // Note: we now always use absolute path to the translation unit so this
     // no longer applies. But let's keep it for posterity.
     //
+    // Also note that we now assume (see cc::compile_rule::enter_header()) a
+    // relative path signifies a generated header.
+    //
 #if 0
     if (f.relative () && rels.relative ())
     {
@@ -590,7 +596,7 @@ namespace build2
     const file* pt (nullptr);
     bool remapped (false);
 
-    // If still relative then it does not exist.
+    // If relative then it does not exist.
     //
     if (fp.relative ())
     {