[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.

diff --git a/src/mc/mc_dwarf.cpp b/src/mc/mc_dwarf.cpp
index a1ae2d8..c9b409a 100644 (file)
--- a/src/mc/mc_dwarf.cpp
+++ b/src/mc/mc_dwarf.cpp
@@ -6,6 +6,7 @@
 
 #include <cinttypes>
 
 
 #include <cinttypes>
 

+#include <algorithm>

 #include <memory>
 
 #include <stdlib.h>
 #include <memory>
 
 #include <stdlib.h>


@@ -1007,8 +1008,8 @@ void MC_dwarf_get_variables(mc_object_info_t info)
 
 // ***** Functions index
 
 
 // ***** 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;
 {
   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)
 {
 
 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;
 
   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.low_pc = e.second.low_pc;

-    entry.high_pc = e.second.high_pc;

     entry.function = &e.second;
     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:
 
   // 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)
 }
 
 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 f982306..11817a2 100644 (file)
--- 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->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
 }
 
 /** Find the DWARF offset for this ELF object


@@ -113,22 +107,35 @@ void *ObjectInformation::base_address() const
   return result;
 }
 
   return result;
 }
 

+/* Find a function by instruction pointer */

 mc_frame_t ObjectInformation::find_function(const void *ip) const
 {
 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 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);
   while (j >= i) {
     int k = i + ((j - i) / 2);

-    if (ip < base[k].low_pc) {
+    if (ip < base[k].low_pc)

       j = k - 1;
       j = k - 1;

-    } else if (ip >= base[k].high_pc) {
+    else if (k <= j && ip >= base[k + 1].low_pc)

       i = k + 1;
       i = k + 1;

-    } else {
+    else if (ip < base[k].function->high_pc)

       return base[k].function;
       return base[k].function;

-    }
+    else
+      return nullptr;

   }
   return nullptr;
 }
   }
   return nullptr;
 }

diff --git a/src/mc/mc_object_info.h b/src/mc/mc_object_info.h
index b195d47..5e431ec 100644 (file)
--- 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;
 
   size_t start_scope;
   mc_object_info_t object_info;

-

 };
 
 class Frame {
 };
 
 class Frame {


@@ -132,10 +131,18 @@ public:
   mc_object_info_t object_info;
 };
 
   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();
 class ObjectInformation {
 public:
   ObjectInformation();

-  ~ObjectInformation();

   ObjectInformation(ObjectInformation const&) = delete;
   ObjectInformation& operator=(ObjectInformation const&) = delete;
 
   ObjectInformation(ObjectInformation const&) = delete;
   ObjectInformation& operator=(ObjectInformation const&) = delete;
 


@@ -155,10 +162,12 @@ public:
   std::unordered_map<std::uint64_t, simgrid::mc::Type> types;
   std::unordered_map<std::string, simgrid::mc::Type*> full_types_by_name;
 
   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
   {
 
   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);
 
   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
 #endif