Use a wider cache for simple function lookups

When we have many individual function lookups, like the nearly 1000 with
syscall.*, each one will iterate every CU in the module (M) and then do a
cache lookup in N entries.  That's a thousand MlogN lookups.

We can instead keep the functions in a module-wide map, and then the
complexity is just a thousand logMN lookups.

Before:
  $ ./run-stap -l 'syscall.**' --vp 01 >/dev/null
  Pass 2: analyzed script: 793 probe(s), 11 function(s), 20 embed(s),
  0 global(s) using 245872virt/147304res/78272shr kb,
  in 1390usr/60sys/1448real ms.

After:
  $ ./run-stap -l 'syscall.**' --vp 01 >/dev/null
  Pass 2: analyzed script: 793 probe(s), 11 function(s), 20 embed(s),
  0 global(s) using 246228virt/147616res/78276shr kb,
  in 720usr/60sys/782real ms.

* dwflpp.cxx (dwflpp::iterate_single_function): Do a simple function
  lookup based on a module-wide cache.
  (dwflpp::mod_function_caching_callback): Helper for above.
* tapsets.cxx (dwarf_query::query_module_functions): Query a single
  function from the module-wide cache.
  (dwarf_query::query_module_dwarf): Use above for simple cases.

3 files changed, 126 insertions, 3 deletions

diff --git a/dwflpp.cxx b/dwflpp.cxx
index c0def432..0b25f4d5 100644
--- a/dwflpp.cxx
+++ b/dwflpp.cxx
@@ -99,6 +99,7 @@ dwflpp::~dwflpp()
 {
   delete_map(module_cu_cache);
   delete_map(cu_function_cache);
+  delete_map(mod_function_cache);
   delete_map(cu_inl_function_cache);
   delete_map(global_alias_cache);
   delete_map(cu_die_parent_cache);
@@ -796,6 +797,14 @@ dwflpp::cu_function_caching_callback (Dwarf_Die* func, void *arg)
 
 
 int
+dwflpp::mod_function_caching_callback (Dwarf_Die* cu, void *arg)
+{
+  dwarf_getfuncs (cu, cu_function_caching_callback, arg, 0);
+  return DWARF_CB_OK;
+}
+
+
+int
 dwflpp::iterate_over_functions (int (* callback)(Dwarf_Die * func, base_query * q),
                                 base_query * q, const string& function)
 {
@@ -855,6 +864,57 @@ dwflpp::iterate_over_functions (int (* callback)(Dwarf_Die * func, base_query *
 }
 
 
+int
+dwflpp::iterate_single_function (int (* callback)(Dwarf_Die * func, base_query * q),
+                                 base_query * q, const string& function)
+{
+  int rc = DWARF_CB_OK;
+  assert (module);
+
+  get_module_dwarf(false);
+  if (!module_dwarf)
+    return rc;
+
+  cu_function_cache_t *v = mod_function_cache[module_dwarf];
+  if (v == 0)
+    {
+      v = new cu_function_cache_t;
+      mod_function_cache[module_dwarf] = v;
+      iterate_over_cus (mod_function_caching_callback, v);
+      if (sess.verbose > 4)
+        clog << "module function cache " << module_name
+             << " size " << v->size() << endl;
+    }
+
+  cu_function_cache_t::iterator it;
+  cu_function_cache_range_t range = v->equal_range(function);
+  if (range.first != range.second)
+    {
+      for (it = range.first; it != range.second; ++it)
+        {
+          Dwarf_Die cu_mem;
+          Dwarf_Die& die = it->second;
+          if (sess.verbose > 4)
+            clog << "module function cache " << module_name
+              << " hit " << function << endl;
+
+          // since we're iterating out of cu-context, we need each focus
+          focus_on_cu(dwarf_diecu(&die, &cu_mem, NULL, NULL));
+
+          rc = (*callback)(& die, q);
+          if (rc != DWARF_CB_OK) break;
+        }
+    }
+
+  // undo the focus_on_cu
+  this->cu = NULL;
+  this->function_name.clear();
+  this->function = NULL;
+
+  return rc;
+}
+
+
 /* This basically only goes one level down from the compile unit so it
  * only picks up top level stuff (i.e. nothing in a lower scope) */
 int
diff --git a/dwflpp.h b/dwflpp.h
index ce4b70f4..386a440c 100644
--- a/dwflpp.h
+++ b/dwflpp.h
@@ -63,6 +63,9 @@ typedef std::pair<cu_function_cache_t::iterator,
 // cu die -> (function -> die)
 typedef unordered_map<void*, cu_function_cache_t*> mod_cu_function_cache_t;
 
+// module -> (function -> die)
+typedef unordered_map<Dwarf*, cu_function_cache_t*> mod_function_cache_t;
+
 // inline function die -> instance die[]
 typedef unordered_map<void*, std::vector<Dwarf_Die>*> cu_inl_function_cache_t;
 
@@ -215,11 +218,12 @@ struct dwflpp
   Dwarf_Die *declaration_resolve(const char *name);
   Dwarf_Die *declaration_resolve_other_cus(const char *name);
 
-  mod_cu_function_cache_t cu_function_cache;
-
   int iterate_over_functions (int (* callback)(Dwarf_Die * func, base_query * q),
                               base_query * q, const std::string& function);
 
+  int iterate_single_function (int (* callback)(Dwarf_Die * func, base_query * q),
+                               base_query * q, const std::string& function);
+
   void iterate_over_srcfile_lines (char const * srcfile,
                                    int lines[2],
                                    bool need_single_match,
@@ -296,6 +300,8 @@ private:
   void setup_user(const std::vector<std::string>& modules, bool debuginfo_needed = true);
 
   module_cu_cache_t module_cu_cache;
+  mod_cu_function_cache_t cu_function_cache;
+  mod_function_cache_t mod_function_cache;
 
   std::set<void*> cu_inl_function_cache_done; // CUs that are already cached
   cu_inl_function_cache_t cu_inl_function_cache;
@@ -322,6 +328,7 @@ private:
                                    int (* callback)(Dwarf_Die *, void *),
                                    void * data);
 
+  static int mod_function_caching_callback (Dwarf_Die* func, void *arg);
   static int cu_function_caching_callback (Dwarf_Die* func, void *arg);
 
   bool has_single_line_record (dwarf_query * q, char const * srcfile, int lineno);
diff --git a/tapsets.cxx b/tapsets.cxx
index 8a78e04c..7b04f794 100644
--- a/tapsets.cxx
+++ b/tapsets.cxx
@@ -641,6 +641,8 @@ struct dwarf_query : public base_query
   func_info_map_t filtered_functions;
   bool choose_next_line;
   Dwarf_Addr entrypc_for_next_line;
+
+  void query_module_functions ();
 };
 
 
@@ -786,7 +788,13 @@ dwarf_query::query_module_dwarf()
       // specifier, we have to scan over all the CUs looking for
       // the function(s) in question
       assert(has_function_str || has_statement_str);
-      dw.iterate_over_cus(&query_cu, this);
+
+      // For simple cases, no wildcard and no source:line, we can do a very
+      // quick function lookup in a module-wide cache.
+      if (spec_type == function_alone && !dw.name_has_wildcard(function))
+        query_module_functions();
+      else
+        dw.iterate_over_cus(&query_cu, this);
     }
 }
 
@@ -1652,6 +1660,54 @@ query_cu (Dwarf_Die * cudie, void * arg)
 }
 
 
+void
+dwarf_query::query_module_functions ()
+{
+  try
+    {
+      filtered_srcfiles.clear();
+      filtered_functions.clear();
+      filtered_inlines.clear();
+
+      // Collect all module functions so we know which CUs are interesting
+      int rc = dw.iterate_single_function(query_dwarf_func, this, function);
+      if (rc != DWARF_CB_OK)
+        {
+          query_done = true;
+          return;
+        }
+
+      set<void*> used_cus; // by cu->addr
+      vector<Dwarf_Die> cus;
+      Dwarf_Die cu_mem;
+
+      for (func_info_map_t::iterator i = filtered_functions.begin();
+           i != filtered_functions.end(); ++i)
+        if (dwarf_diecu(&i->die, &cu_mem, NULL, NULL) &&
+            used_cus.insert(cu_mem.addr).second)
+          cus.push_back(cu_mem);
+
+      for (inline_instance_map_t::iterator i = filtered_inlines.begin();
+           i != filtered_inlines.end(); ++i)
+        if (dwarf_diecu(&i->die, &cu_mem, NULL, NULL) &&
+            used_cus.insert(cu_mem.addr).second)
+          cus.push_back(cu_mem);
+
+      // Reset the dupes since we didn't actually collect them the first time
+      alias_dupes.clear();
+      inline_dupes.clear();
+
+      // Run the query again on the individual CUs
+      for (vector<Dwarf_Die>::iterator i = cus.begin(); i != cus.end(); ++i)
+        query_cu(&*i, this);
+    }
+  catch (const semantic_error& e)
+    {
+      sess.print_error (e);
+    }
+}
+
+
 static void
 validate_module_elf (Dwfl_Module *mod, const char *name,  base_query *q)
 {