src/mc/mc_hash.cpp

   1 /* Copyright (c) 2014. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include <cinttypes>
   8
   9 #include <stdint.h>
  10 #include <stdbool.h>
  11
  12 #include "mc_private.h"
  13 #include "mc/datatypes.h"
  14 #include <mc/mc.h>
  15 #include "mc_hash.hpp"
  16
  17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_hash, mc, "Logging specific to mc_hash");
  18
  19 namespace simgrid {
  20 namespace mc {
  21
  22 // This is djb2:
  23 #define MC_HASH_INIT ((simgrid::mc::hash_type)5381)
  24
  25 template<class T>
  26 static void hash_update(hash_type& hash, T const& value)
  27 {
  28   hash = (hash << 5) + hash + (uint64_t) value;
  29 }
  30
  31 // ***** Hash state
  32
  33 #if 0
  34 typedef struct s_mc_hashing_state {
  35   // Set of pointers/addresses already processed (avoid loops):
  36   mc_address_set_t handled_addresses;
  37 } mc_hashing_state;
  38
  39 void mc_hash_state_init(mc_hashing_state * state);
  40 void mc_hash_state_destroy(mc_hashing_state * state);
  41
  42 void mc_hash_state_init(mc_hashing_state * state)
  43 {
  44   state->handled_addresses = mc_address_set_new();
  45 }
  46
  47 void mc_hash_state_destroy(mc_hashing_state * state)
  48 {
  49   mc_address_set_free(&state->handled_addresses);
  50 }
  51
  52 // TODO, detect and avoid loops
  53
  54 static bool mc_ignored(const void *address, size_t size)
  55 {
  56   mc_heap_ignore_region_t region;
  57   unsigned int cursor = 0;
  58   const void *end = (char *) address + size;
  59   xbt_dynar_foreach(mc_heap_comparison_ignore, cursor, region) {
  60     void *istart = region->address;
  61     void *iend = (char *) region->address + region->size;
  62
  63     if (address >= istart && address < iend && end >= istart && end < iend)
  64       return true;
  65   }
  66
  67   return false;
  68 }
  69
  70 static void mc_hash_binary(hash_type * hash, const void *s, size_t len)
  71 {
  72   const char *p = (const char*) s;
  73   for (size_t i = 0; i != len; ++i) {
  74     hash_update(*hash, p[i]);
  75   }
  76 }
  77
  78 /** \brief Compute a hash for a given value of a given type
  79  *
  80  *  We try to be very conservative (do not hash too ambiguous things).
  81  *
  82  *  \param address address of the variable
  83  *  \param type type of the variable
  84  * */
  85 static void mc_hash_value(hash_type * hash, mc_hashing_state * state,
  86                           simgrid::mc::ObjectInformation* info, const void *address,
  87                           simgrid::mc::Type* type)
  88 {
  89   simgrid::mc::Process* process = &mc_model_checker->process();
  90 top:
  91
  92   switch (type->type) {
  93
  94     // Not relevant, do nothing:
  95   case DW_TAG_unspecified_type:
  96     return;
  97
  98     // Simple case, hash this has binary:
  99   case DW_TAG_base_type:
 100   case DW_TAG_enumeration_type:
 101     {
 102       if (mc_ignored(address, 1))
 103         return;
 104       mc_hash_binary(hash, address, type->byte_size);
 105       return;
 106     }
 107
 108   case DW_TAG_array_type:
 109     {
 110       if (mc_ignored(address, type->byte_size))
 111         return;
 112
 113       long element_count = type->element_count;
 114       simgrid::mc::Type* subtype = type->subtype;
 115       if (subtype == NULL) {
 116         XBT_DEBUG("Hash array without subtype");
 117         return;
 118       }
 119       int i;
 120       for (i = 0; i != element_count; ++i) {
 121         XBT_DEBUG("Hash array element %i", i);
 122         void *subaddress = ((char *) address) + i * subtype->byte_size;
 123         mc_hash_value(hash, state, info, subaddress, subtype);
 124       }
 125       return;
 126     }
 127
 128     // Get the raw type:
 129   case DW_TAG_typedef:
 130   case DW_TAG_volatile_type:
 131   case DW_TAG_const_type:
 132   case DW_TAG_restrict_type:
 133     {
 134       type = type->subtype;
 135       if (type == NULL)
 136         return;
 137       else
 138         goto top;
 139     }
 140
 141   case DW_TAG_structure_type:
 142   case DW_TAG_class_type:
 143     {
 144       if (mc_ignored(address, type->byte_size))
 145         return;
 146
 147       unsigned int cursor = 0;
 148       simgrid::mc::Type* member;
 149       xbt_dynar_foreach(type->members, cursor, member) {
 150         XBT_DEBUG("Hash struct member %s", member->name);
 151         if (type->subtype == NULL)
 152           return;
 153         void *member_variable = mc_member_resolve(address, type, member, NULL);
 154         mc_hash_value(hash, state, info, member_variable, type->subtype);
 155       }
 156       return;
 157     }
 158
 159     // Pointer, we hash a single value but it might be an array.
 160   case DW_TAG_pointer_type:
 161   case DW_TAG_reference_type:
 162   case DW_TAG_rvalue_reference_type:
 163     {
 164       if (mc_ignored(address, 1))
 165         return;
 166
 167       void *pointed = *(void **) address;
 168       if (pointed == NULL) {
 169         XBT_DEBUG("Hashed pinter is NULL");
 170         return;
 171       }
 172       // Avoid loops:
 173       if (mc_address_test(state->handled_addresses, pointed)) {
 174         XBT_DEBUG("Hashed pointed data %p already hashed", pointed);
 175         return;
 176       }
 177       mc_address_add(state->handled_addresses, pointed);
 178
 179       // Anything outside the R/W segments and the heap is not hashed:
 180       bool valid_pointer = (pointed >= (void *) binary_info->start_rw
 181                             && pointed <= (void *) binary_info->end_rw)
 182           || (pointed >= (void *) libsimgrid_info->start_rw
 183               && pointed <= (void *) libsimgrid_info->end_rw)
 184           || (pointed >= process->heap_address
 185               && pointed < (void *) ((const char *) process->heap_address + STD_HEAP_SIZE));
 186       if (!valid_pointer) {
 187         XBT_DEBUG("Hashed pointed data %p is in an ignored range", pointed);
 188         return;
 189       }
 190
 191       if (type->subtype == NULL) {
 192         XBT_DEBUG("Missing type for %p (type=%s)",
 193           pointed, type->type_id.c_str());
 194         return;
 195       }
 196
 197       address = pointed;
 198       type = type->subtype;
 199       goto top;
 200     }
 201
 202     // Skip this:
 203   case DW_TAG_union_type:
 204   case DW_TAG_subroutine_type:
 205   default:
 206     return;
 207   }
 208 }
 209
 210 static void mc_hash_object_globals(hash_type * hash, mc_hashing_state * state,
 211                                    simgrid::mc::ObjectInformation* info)
 212 {
 213   unsigned int cursor = 0;
 214   simgrid::mc::Variable* variable;
 215   xbt_dynar_foreach(info->global_variables, cursor, variable) {
 216     XBT_DEBUG("Hash global variable %s", variable->name);
 217
 218     if (variable->type_id == NULL) {
 219       // Nothing
 220       continue;
 221     }
 222
 223     simgrid::mc::Type* type = variable->type;
 224     if (type == NULL) {
 225       // Nothing
 226       continue;
 227     }
 228
 229     const char *address = variable->address;
 230     bool valid_pointer = (address >= binary_info->start_rw
 231                           && address <= binary_info->end_rw)
 232         || (address >= libsimgrid_info->start_rw
 233             && address <= libsimgrid_info->end_rw)
 234         || (address >= (const char *) process->heap_address
 235             && address < (const char *) process->heap_address + STD_HEAP_SIZE);
 236     if (!valid_pointer)
 237       continue;
 238
 239     mc_hash_value(hash, state, info, variable->address, type);
 240   }
 241 }
 242
 243 static void mc_hash_stack_frame(mc_hash_t * hash,
 244                                 simgrid::mc::ObjectInformation* info,
 245                                 unw_cursor_t * unw_cursor, simgrid::mc::Frame* frame,
 246                                 char *frame_pointer, mc_hashing_state * state)
 247 {
 248
 249   // return; // TEMP
 250
 251   unsigned int cursor = 0;
 252   simgrid::mc::Variable* variable;
 253   xbt_dynar_foreach(frame->variables, cursor, variable) {
 254
 255     if (variable->type_id == NULL) {
 256       XBT_DEBUG("Hash local variable %s without type", variable->name);
 257       continue;
 258     }
 259     if (variable->locations.size == 0) {
 260       XBT_DEBUG("Hash local variable %s without location", variable->name);
 261       continue;
 262     }
 263
 264     XBT_DEBUG("Hash local variable %s", variable->name);
 265
 266     void *variable_address =
 267         (void *) mc_dwarf_resolve_locations(&variable->locations,
 268                                             variable->object_info, unw_cursor,
 269                                             frame_pointer, NULL);
 270
 271     simgrid::mc::Type* type = variable->type;
 272     if (type == NULL) {
 273       XBT_DEBUG("Hash local variable %s without loctypeation", variable->name);
 274       continue;
 275     }
 276
 277     mc_hash_value(hash, state, info, variable_address, type);
 278   }
 279
 280   // TODO, handle nested scopes
 281 }
 282
 283 static void mc_hash_stack(mc_hash_t * hash, mc_snapshot_stack_t stack,
 284                           mc_hashing_state * state)
 285 {
 286
 287   unsigned cursor = 0;
 288   mc_stack_frame_t stack_frame;
 289
 290   for(s_mc_stack_frame_t const& stack_frame : stack->stack_frames) {
 291
 292     hash_update(*hash, stack_frame.ip);
 293
 294     simgrid::mc::ObjectInformation* info;
 295     if (stack_frame.ip >= (unw_word_t) libsimgrid_info->start_exec
 296         && stack_frame.ip < (unw_word_t) libsimgrid_info->end_exec)
 297       info = libsimgrid_info;
 298     else if (stack_frame.ip >= (unw_word_t) binary_info->start_exec
 299              && stack_frame.ip < (unw_word_t) binary_info->end_exec)
 300       info = binary_info;
 301     else
 302       continue;
 303
 304     mc_hash_stack_frame(hash, info, &(stack_frame.unw_cursor),
 305                         stack_frame.frame, (void *) stack_frame.frame_base,
 306                         state);
 307
 308   }
 309 }
 310
 311 static void mc_hash_stacks(mc_hash_t * hash, mc_hashing_state * state,
 312                            xbt_dynar_t stacks)
 313 {
 314   unsigned int cursor = 0;
 315   mc_snapshot_stack_t current_stack;
 316
 317   hash_update(*hash, xbt_dynar_length(stacks_areas));
 318
 319   int i = 0;
 320   xbt_dynar_foreach(stacks, cursor, current_stack) {
 321     XBT_DEBUG("Stack %i", i);
 322     mc_hash_stack(hash, current_stack, state);
 323     ++i;
 324   }
 325 }
 326 #endif
 327
 328 static hash_type hash(std::vector<s_mc_snapshot_stack_t> const& stacks)
 329 {
 330 #if 0
 331   mc_hashing_state state;
 332   mc_hash_state_init(&state);
 333 #endif
 334
 335   hash_type hash = MC_HASH_INIT;
 336
 337   hash_update(hash, xbt_swag_size(simix_global->process_list));
 338 #if 0
 339   // mc_hash_object_globals(&hash, &state, binary_info);
 340   // mc_hash_object_globals(&hash, &state, libsimgrid_info);
 341   // mc_hash_stacks(&hash, &state, stacks);
 342   mc_hash_state_destroy(&state);
 343 #endif
 344
 345
 346   return hash;
 347 }
 348
 349 hash_type hash(Snapshot const& snapshot)
 350 {
 351   XBT_DEBUG("START hash %i", snapshot.num_state);
 352   hash_type res = simgrid::mc::hash(snapshot.stacks);
 353   XBT_DEBUG("END hash %i", snapshot.num_state);
 354   return res;
 355 }
 356
 357 }
 358 }