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