src/mc/mc_hash.c

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