From 773cbe7c3a92faef15e6533eed36910a32dd1df1 Mon Sep 17 00:00:00 2001 From: Gabriel Corona Date: Tue, 21 Jul 2015 12:09:19 +0200 Subject: [PATCH] [mc] Make ObjectInformation::function_index a std::vector and while we're at it remove high_pc from the FunctionIndexEntry which is not so useful. --- src/mc/mc_dwarf.cpp | 27 +++++++++++++-------------- src/mc/mc_object_info.cpp | 35 +++++++++++++++++++++-------------- src/mc/mc_object_info.h | 27 +++++++++++++++------------ 3 files changed, 49 insertions(+), 40 deletions(-) diff --git a/src/mc/mc_dwarf.cpp b/src/mc/mc_dwarf.cpp index a1ae2d8ee4..c9b409a6be 100644 --- a/src/mc/mc_dwarf.cpp +++ b/src/mc/mc_dwarf.cpp @@ -6,6 +6,7 @@ #include +#include #include #include @@ -1007,8 +1008,8 @@ void MC_dwarf_get_variables(mc_object_info_t info) // ***** Functions index -static int MC_compare_frame_index_items(mc_function_index_item_t a, - mc_function_index_item_t b) +static int MC_compare_frame_index_items(simgrid::mc::FunctionIndexEntry* a, + simgrid::mc::FunctionIndexEntry* b) { if (a->low_pc < b->low_pc) return -1; @@ -1020,28 +1021,26 @@ static int MC_compare_frame_index_items(mc_function_index_item_t a, static void MC_make_functions_index(mc_object_info_t info) { - xbt_dynar_t index = xbt_dynar_new(sizeof(s_mc_function_index_item_t), NULL); + info->functions_index.clear(); for (auto& e : info->subprograms) { if (e.second.low_pc == nullptr) continue; - s_mc_function_index_item_t entry; + simgrid::mc::FunctionIndexEntry entry; entry.low_pc = e.second.low_pc; - entry.high_pc = e.second.high_pc; entry.function = &e.second; - xbt_dynar_push(index, &entry); + info->functions_index.push_back(entry); } - mc_function_index_item_t base = - (mc_function_index_item_t) xbt_dynar_get_ptr(index, 0); + info->functions_index.shrink_to_fit(); // Sort the array by low_pc: - qsort(base, - xbt_dynar_length(index), - sizeof(s_mc_function_index_item_t), - (int (*)(const void *, const void *)) MC_compare_frame_index_items); - - info->functions_index = index; + std::sort(info->functions_index.begin(), info->functions_index.end(), + [](simgrid::mc::FunctionIndexEntry& a, + simgrid::mc::FunctionIndexEntry& b) + { + return a.low_pc < b.low_pc; + }); } static void MC_post_process_variables(mc_object_info_t info) diff --git a/src/mc/mc_object_info.cpp b/src/mc/mc_object_info.cpp index f982306806..11817a2c03 100644 --- a/src/mc/mc_object_info.cpp +++ b/src/mc/mc_object_info.cpp @@ -78,12 +78,6 @@ ObjectInformation::ObjectInformation() this->end_rw = nullptr; this->start_ro = nullptr; this->end_ro = nullptr; - this->functions_index = nullptr; -} - -ObjectInformation::~ObjectInformation() -{ - xbt_dynar_free(&this->functions_index); } /** Find the DWARF offset for this ELF object @@ -113,22 +107,35 @@ void *ObjectInformation::base_address() const return result; } +/* Find a function by instruction pointer */ mc_frame_t ObjectInformation::find_function(const void *ip) const { - xbt_dynar_t dynar = this->functions_index; - mc_function_index_item_t base = - (mc_function_index_item_t) xbt_dynar_get_ptr(dynar, 0); + /* This is implemented by binary search on a sorted array. + * + * We do quite a lot ot those so we want this to be cache efficient. + * We pack the only information we need in the index entries in order + * to successfully do the binary search. We do not need the high_pc + * during the binary search (only at the end) so it is not included + * in the index entry. We could use parallel arrays as well. + * + * We cannot really use the std:: alogrithm for this. + * We could use std::binary_search by including the high_pc inside + * the FunctionIndexEntry. + */ + const simgrid::mc::FunctionIndexEntry* base = + this->functions_index.data(); int i = 0; - int j = xbt_dynar_length(dynar) - 1; + int j = this->functions_index.size() - 1; while (j >= i) { int k = i + ((j - i) / 2); - if (ip < base[k].low_pc) { + if (ip < base[k].low_pc) j = k - 1; - } else if (ip >= base[k].high_pc) { + else if (k <= j && ip >= base[k + 1].low_pc) i = k + 1; - } else { + else if (ip < base[k].function->high_pc) return base[k].function; - } + else + return nullptr; } return nullptr; } diff --git a/src/mc/mc_object_info.h b/src/mc/mc_object_info.h index b195d47750..5e431eca31 100644 --- a/src/mc/mc_object_info.h +++ b/src/mc/mc_object_info.h @@ -113,7 +113,6 @@ public: size_t start_scope; mc_object_info_t object_info; - }; class Frame { @@ -132,10 +131,18 @@ public: mc_object_info_t object_info; }; +/** An entry in the functions index + * + * See the code of ObjectInformation::find_function. + */ +struct FunctionIndexEntry { + void* low_pc; + mc_frame_t function; +}; + class ObjectInformation { public: ObjectInformation(); - ~ObjectInformation(); ObjectInformation(ObjectInformation const&) = delete; ObjectInformation& operator=(ObjectInformation const&) = delete; @@ -155,10 +162,12 @@ public: std::unordered_map types; std::unordered_map full_types_by_name; - // Here we sort the minimal information for an efficient (and cache-efficient) - // lookup of a function given an instruction pointer. - // The entries are sorted by low_pc and a binary search can be used to look them up. - xbt_dynar_t functions_index; + /** Index of functions by IP + * + * The entries are sorted by low_pc and a binary search can be used to look + * them up. Should we used a binary tree instead? + */ + std::vector functions_index; bool executable() const { @@ -195,10 +204,4 @@ XBT_INTERNAL void* mc_member_resolve( const void* base, mc_type_t type, mc_type_t member, mc_address_space_t snapshot, int process_index); - -struct s_mc_function_index_item { - void* low_pc, *high_pc; - mc_frame_t function; -}; - #endif -- 2.20.1