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