src/mc/mc_hash.cpp

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