#include <cinttypes>
+#include <algorithm>
#include <memory>
#include <stdlib.h>
// ***** 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;
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)
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
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;
}
size_t start_scope;
mc_object_info_t object_info;
-
};
class Frame {
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;
std::unordered_map<std::uint64_t, simgrid::mc::Type> types;
std::unordered_map<std::string, simgrid::mc::Type*> 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<FunctionIndexEntry> functions_index;
bool executable() const
{
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