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