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   // Simple case, hash this has binary:
  81   case DW_TAG_base_type:
  82   case DW_TAG_enumeration_type:
  83   {
  84     if(mc_ignored(address, 1))
  85       return;
  86     mc_hash_binary(hash, address, type->byte_size);
  87     return;
  88   }
  89
  90   case DW_TAG_array_type:
  91   {
  92     if(mc_ignored(address, type->byte_size))
  93       return;
  94
  95     long element_count = type->element_count;
  96     dw_type_t subtype = xbt_dict_get_or_null(info->types, type->dw_type_id);
  97     if(subtype==NULL) {
  98       XBT_DEBUG("Hash array without subtype");
  99       return;
 100     }
 101     int i;
 102     for(i=0; i!=element_count; ++i) {
 103       XBT_DEBUG("Hash array element %i", i);
 104       void* subaddress = ((char*)address)+i*subtype->byte_size;
 105       mc_hash_value(hash, state, info, subaddress, subtype);
 106     }
 107     return;
 108   }
 109
 110   // Get the raw type:
 111   case DW_TAG_typedef:
 112   case DW_TAG_volatile_type:
 113   case DW_TAG_const_type:
 114   case DW_TAG_restrict_type:
 115   {
 116     if(type->dw_type_id==NULL) {
 117       return;
 118     }
 119     type = xbt_dict_get_or_null(info->types, type->dw_type_id);
 120     if(type==NULL)
 121       return;
 122     else
 123       goto top;
 124   }
 125
 126   case DW_TAG_structure_type:
 127   case DW_TAG_class_type:
 128   {
 129     if(mc_ignored(address, type->byte_size))
 130       return;
 131
 132     unsigned int cursor = 0;
 133     dw_type_t member;
 134     xbt_dynar_foreach(type->members, cursor, member){
 135       XBT_DEBUG("Hash struct member %s", member->name);
 136       dw_type_t subtype = xbt_dict_get_or_null(info->types, member->dw_type_id);
 137       if(subtype==NULL)
 138         return;
 139        mc_hash_value(hash, state, info, ((char*)address) + member->offset, subtype);
 140     }
 141     return;
 142   }
 143
 144   // Pointer, we hash a single value but it might be an array.
 145   case DW_TAG_pointer_type:
 146   case DW_TAG_reference_type:
 147   case DW_TAG_rvalue_reference_type:
 148   {
 149     if(mc_ignored(address, 1))
 150       return;
 151
 152     void* pointed = *(void**)address;
 153     if(pointed==NULL) {
 154       XBT_DEBUG("Hashed pinter is NULL");
 155       return;
 156     }
 157
 158     // Avoid loops:
 159     if(mc_address_test(state->handled_addresses, pointed)) {
 160       XBT_DEBUG("Hashed pointed data %p already hashed", pointed);
 161       return;
 162     }
 163     mc_address_add(state->handled_addresses, pointed);
 164
 165     // Anything outside the R/W segments and the heap is not hashed:
 166     bool valid_pointer = (pointed >= (void*) mc_binary_info->start_rw && pointed <= (void*) mc_binary_info->end_rw)
 167         || (pointed >= (void*) mc_libsimgrid_info->start_rw && pointed <= (void*) mc_libsimgrid_info->end_rw)
 168         || (pointed >= std_heap && pointed < (void*) ((const char*)std_heap + STD_HEAP_SIZE));
 169     if(!valid_pointer) {
 170       XBT_DEBUG("Hashed pointed data %p is in an ignored range", pointed);
 171       return;
 172     }
 173
 174     dw_type_t subtype = type->dw_type_id == NULL ? NULL : xbt_dict_get_or_null(info->types, type->dw_type_id);
 175     if(subtype==NULL) {
 176       XBT_DEBUG("Missing type for %p (type=%s)", pointed, type->dw_type_id);
 177       return;
 178     }
 179
 180     address = pointed;
 181     type = subtype;
 182     goto top;
 183   }
 184
 185   // Skip this:
 186   case DW_TAG_union_type:
 187   case DW_TAG_subroutine_type:
 188   default:
 189     return;
 190   }
 191 }
 192
 193
 194 static void mc_hash_object_globals(mc_hash_t *hash, mc_hashing_state* state, mc_object_info_t info) {
 195   unsigned int cursor = 0;
 196   dw_variable_t variable;
 197   xbt_dynar_foreach(info->global_variables, cursor, variable) {
 198     XBT_DEBUG("Hash global variable %s", variable->name);
 199
 200     if(variable->type_origin == NULL) {
 201       // Nothing
 202       continue;
 203     }
 204
 205     dw_type_t type = xbt_dict_get_or_null(info->types, variable->type_origin);
 206     if(type==NULL) {
 207       // Nothing
 208       continue;
 209     }
 210
 211     const char* address = variable->address.address;
 212     bool valid_pointer = (address >= mc_binary_info->start_rw && address <= mc_binary_info->end_rw)
 213         || (address >= mc_libsimgrid_info->start_rw && address <= mc_libsimgrid_info->end_rw)
 214         || (address >= (const char*) std_heap && address < (const char *)std_heap + STD_HEAP_SIZE);
 215     if(!valid_pointer) continue;
 216
 217     mc_hash_value(hash, state, info, variable->address.address, type);
 218   }
 219 }
 220
 221 static void mc_hash_stack_frame(
 222   mc_hash_t *hash,
 223     mc_object_info_t info, unw_cursor_t* unw_cursor, dw_frame_t frame, char* frame_pointer, mc_hashing_state* state
 224     ) {
 225
 226   // return; // TEMP
 227
 228   unsigned int cursor = 0;
 229   dw_variable_t variable;
 230   xbt_dynar_foreach(frame->variables, cursor, variable){
 231
 232     if(variable->type_origin==NULL) {
 233       XBT_DEBUG("Hash local variable %s without type", variable->name);
 234       continue;
 235     }
 236     if(variable->address.location == NULL) {
 237       XBT_DEBUG("Hash local variable %s without location", variable->name);
 238       continue;
 239     }
 240
 241     XBT_DEBUG("Hash local variable %s", variable->name);
 242
 243     void* variable_address = (void*) MC_dwarf_resolve_location(unw_cursor, variable->address.location, frame_pointer);
 244
 245     dw_type_t type = xbt_dict_get_or_null(info->types, variable->type_origin);
 246     if(type==NULL) {
 247       XBT_DEBUG("Hash local variable %s without loctypeation", variable->name);
 248       continue;
 249     }
 250
 251     mc_hash_value(hash, state, info, variable_address, type);
 252   }
 253 }
 254
 255 /** \brief Find the frame base of a given frame
 256  *
 257  *  \param ip         Instruction pointer
 258  *  \param frame
 259  *  \param unw_cursor
 260  */
 261 void* mc_find_frame_base(unw_word_t ip, dw_frame_t frame, unw_cursor_t* unw_cursor) {
 262   switch(frame->frame_base->type) {
 263   case e_dw_loclist:
 264   {
 265     int loclist_cursor;
 266     for(loclist_cursor=0; loclist_cursor < xbt_dynar_length(frame->frame_base->location.loclist); loclist_cursor++){
 267       dw_location_entry_t entry = xbt_dynar_get_as(frame->frame_base->location.loclist, loclist_cursor, dw_location_entry_t);
 268       if((ip >= entry->lowpc) && (ip < entry->highpc)){
 269         return (void*) MC_dwarf_resolve_location(unw_cursor, entry->location, NULL);
 270       }
 271     }
 272     return NULL;
 273   }
 274   // Not handled:
 275   default:
 276     return NULL;
 277   }
 278 }
 279
 280 static void mc_hash_stack(mc_hash_t *hash, stack_region_t stack, mc_hashing_state* state) {
 281
 282   unw_cursor_t cursor;
 283   if(unw_init_local(&cursor, (unw_context_t *)stack->context)){
 284     xbt_die("unw_init_local failed");
 285   }
 286
 287   MC_HASH(*hash, (long)stack->address);
 288
 289   long count = 0;
 290
 291   int ret;
 292   for(ret=1; ret >= 0; ret = unw_step(&cursor)) {
 293
 294     // Find the frame name:
 295     unw_word_t off;
 296     char frame_name[256];
 297     if(unw_get_proc_name(&cursor, frame_name, sizeof (frame_name), &off)!=0) {
 298       continue;
 299     }
 300
 301     XBT_DEBUG("Frame #%i %s", (int) count, frame_name);
 302
 303     // Stop before context switch with maestro
 304     if(!strcmp(frame_name, "smx_ctx_sysv_wrapper")) {
 305       break;
 306     }
 307
 308     ++count;
 309
 310     unw_word_t ip, sp;
 311     if(unw_get_reg(&cursor, UNW_REG_IP, &ip))
 312       continue;
 313     if(unw_get_reg(&cursor, UNW_REG_SP, &sp))
 314       continue;
 315
 316     MC_HASH(*hash, ip);
 317
 318     // Find the object info:
 319     mc_object_info_t info;
 320     if((long)ip >= (long) mc_libsimgrid_info->start_exec && (long)ip < (long) mc_libsimgrid_info->end_exec)
 321       info = mc_libsimgrid_info;
 322     else if((long)ip >= (long) mc_binary_info->start_exec && (long)ip < (long) mc_binary_info->end_exec)
 323       info = mc_binary_info;
 324     else
 325       continue;
 326
 327     // Find the frame:
 328     dw_frame_t frame = xbt_dict_get_or_null(info->local_variables, frame_name);
 329     if(frame==NULL)
 330       continue;
 331
 332     long true_ip = (long)frame->low_pc + (long)off;
 333
 334     // Find the fame base:
 335     void* frame_base = mc_find_frame_base(true_ip, frame, &cursor);
 336     if(frame_base==NULL)
 337       continue;
 338
 339     mc_hash_stack_frame(hash, info, &cursor, frame, frame_base, state);
 340   }
 341
 342   MC_HASH(*hash, count);
 343 }
 344
 345 static void mc_hash_stacks(mc_hash_t *hash, mc_hashing_state* state) {
 346   unsigned int cursor = 0;
 347   stack_region_t current_stack;
 348
 349   MC_HASH(*hash, xbt_dynar_length(stacks_areas));
 350
 351   int i=0;
 352   xbt_dynar_foreach(stacks_areas, cursor, current_stack){
 353     XBT_DEBUG("Stack %i", i);
 354     mc_hash_stack(hash, current_stack, state);
 355     ++i;
 356   }
 357 }
 358
 359 uint64_t mc_hash_processes_state(int num_state) {
 360   XBT_DEBUG("START hash %i", num_state);
 361
 362   mc_hashing_state state;
 363   mc_hash_state_init(&state);
 364
 365   mc_hash_t hash = MC_HASH_INIT;
 366
 367   MC_HASH(hash, xbt_swag_size(simix_global->process_list)); // process count
 368   mc_hash_object_globals(&hash, &state, mc_binary_info);
 369   // mc_hash_object_globals(&hash, &state, mc_libsimgrid_info);
 370   mc_hash_stacks(&hash, &state);
 371
 372   mc_hash_state_destroy(&state);
 373
 374   XBT_DEBUG("END hash %i", num_state);
 375   return hash;
 376 }