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