From 4df79aaf86a9b6dfbccc3c51946024a30ba43726 Mon Sep 17 00:00:00 2001 From: Josh Stone Date: Tue, 30 Mar 2010 14:54:39 -0700 Subject: [PATCH] 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. --- dwflpp.cxx | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++ dwflpp.h | 11 ++++++++-- tapsets.cxx | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 126 insertions(+), 3 deletions(-) diff --git a/dwflpp.cxx b/dwflpp.cxx index c0def4320..0b25f4d5e 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); @@ -795,6 +796,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 ce4b70f40..386a440ca 100644 --- a/dwflpp.h +++ b/dwflpp.h @@ -63,6 +63,9 @@ typedef std::pair (function -> die) typedef unordered_map mod_cu_function_cache_t; +// module -> (function -> die) +typedef unordered_map mod_function_cache_t; + // inline function die -> instance die[] typedef unordered_map*> 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& 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 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 8a78e04cd..7b04f7943 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 used_cus; // by cu->addr + vector 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::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) { -- 2.43.5