1 /* Copyright (c) 2014. The SimGrid Team.
2 * All rights reserved. */
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. */
12 #include "mc_private.h"
13 #include "mc/datatypes.h"
15 #include "mc_hash.hpp"
17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_hash, mc, "Logging specific to mc_hash");
20 typedef uint64_t mc_hash_t;
21 #define MC_HASH_INIT ((uint64_t)5381)
23 // #define MC_HASH(hash, value) hash = (((hash << 5) + hash) + (uint64_t) value)
24 #define MC_HASH(hash, value) \
25 { hash = (((hash << 5) + hash) + (uint64_t) value);\
26 XBT_DEBUG("%s:%i: %" PRIx64 " -> %" PRIx64, __FILE__, __LINE__, (uint64_t) value, hash); }
31 typedef struct s_mc_hashing_state {
32 // Set of pointers/addresses already processed (avoid loops):
33 mc_address_set_t handled_addresses;
36 void mc_hash_state_init(mc_hashing_state * state);
37 void mc_hash_state_destroy(mc_hashing_state * state);
39 void mc_hash_state_init(mc_hashing_state * state)
41 state->handled_addresses = mc_address_set_new();
44 void mc_hash_state_destroy(mc_hashing_state * state)
46 mc_address_set_free(&state->handled_addresses);
49 // TODO, detect and avoid loops
51 static bool mc_ignored(const void *address, size_t size)
53 mc_heap_ignore_region_t region;
54 unsigned int cursor = 0;
55 const void *end = (char *) address + size;
56 xbt_dynar_foreach(mc_heap_comparison_ignore, cursor, region) {
57 void *istart = region->address;
58 void *iend = (char *) region->address + region->size;
60 if (address >= istart && address < iend && end >= istart && end < iend)
67 static void mc_hash_binary(mc_hash_t * hash, const void *s, size_t len)
69 const char *p = (const char*) s;
70 for (size_t i = 0; i != len; ++i) {
75 /** \brief Compute a hash for a given value of a given type
77 * We try to be very conservative (do not hash too ambiguous things).
79 * \param address address of the variable
80 * \param type type of the variable
82 static void mc_hash_value(mc_hash_t * hash, mc_hashing_state * state,
83 mc_object_info_t info, const void *address,
86 mc_process_t process = &mc_model_checker->process();
91 // Not relevant, do nothing:
92 case DW_TAG_unspecified_type:
95 // Simple case, hash this has binary:
96 case DW_TAG_base_type:
97 case DW_TAG_enumeration_type:
99 if (mc_ignored(address, 1))
101 mc_hash_binary(hash, address, type->byte_size);
105 case DW_TAG_array_type:
107 if (mc_ignored(address, type->byte_size))
110 long element_count = type->element_count;
111 dw_type_t subtype = type->subtype;
112 if (subtype == NULL) {
113 XBT_DEBUG("Hash array without subtype");
117 for (i = 0; i != element_count; ++i) {
118 XBT_DEBUG("Hash array element %i", i);
119 void *subaddress = ((char *) address) + i * subtype->byte_size;
120 mc_hash_value(hash, state, info, subaddress, subtype);
127 case DW_TAG_volatile_type:
128 case DW_TAG_const_type:
129 case DW_TAG_restrict_type:
131 type = type->subtype;
138 case DW_TAG_structure_type:
139 case DW_TAG_class_type:
141 if (mc_ignored(address, type->byte_size))
144 unsigned int cursor = 0;
146 xbt_dynar_foreach(type->members, cursor, member) {
147 XBT_DEBUG("Hash struct member %s", member->name);
148 if (type->subtype == NULL)
150 void *member_variable = mc_member_resolve(address, type, member, NULL);
151 mc_hash_value(hash, state, info, member_variable, type->subtype);
156 // Pointer, we hash a single value but it might be an array.
157 case DW_TAG_pointer_type:
158 case DW_TAG_reference_type:
159 case DW_TAG_rvalue_reference_type:
161 if (mc_ignored(address, 1))
164 void *pointed = *(void **) address;
165 if (pointed == NULL) {
166 XBT_DEBUG("Hashed pinter is NULL");
170 if (mc_address_test(state->handled_addresses, pointed)) {
171 XBT_DEBUG("Hashed pointed data %p already hashed", pointed);
174 mc_address_add(state->handled_addresses, pointed);
176 // Anything outside the R/W segments and the heap is not hashed:
177 bool valid_pointer = (pointed >= (void *) binary_info->start_rw
178 && pointed <= (void *) binary_info->end_rw)
179 || (pointed >= (void *) libsimgrid_info->start_rw
180 && pointed <= (void *) libsimgrid_info->end_rw)
181 || (pointed >= process->heap_address
182 && pointed < (void *) ((const char *) process->heap_address + STD_HEAP_SIZE));
183 if (!valid_pointer) {
184 XBT_DEBUG("Hashed pointed data %p is in an ignored range", pointed);
188 if (type->subtype == NULL) {
189 XBT_DEBUG("Missing type for %p (type=%s)", pointed, type->dw_type_id);
194 type = type->subtype;
199 case DW_TAG_union_type:
200 case DW_TAG_subroutine_type:
206 static void mc_hash_object_globals(mc_hash_t * hash, mc_hashing_state * state,
207 mc_object_info_t info)
209 unsigned int cursor = 0;
210 dw_variable_t variable;
211 xbt_dynar_foreach(info->global_variables, cursor, variable) {
212 XBT_DEBUG("Hash global variable %s", variable->name);
214 if (variable->type_origin == NULL) {
219 dw_type_t type = variable->type;
225 const char *address = variable->address;
226 bool valid_pointer = (address >= binary_info->start_rw
227 && address <= binary_info->end_rw)
228 || (address >= libsimgrid_info->start_rw
229 && address <= libsimgrid_info->end_rw)
230 || (address >= (const char *) process->heap_address
231 && address < (const char *) process->heap_address + STD_HEAP_SIZE);
235 mc_hash_value(hash, state, info, variable->address, type);
239 static void mc_hash_stack_frame(mc_hash_t * hash,
240 mc_object_info_t info,
241 unw_cursor_t * unw_cursor, dw_frame_t frame,
242 char *frame_pointer, mc_hashing_state * state)
247 unsigned int cursor = 0;
248 dw_variable_t variable;
249 xbt_dynar_foreach(frame->variables, cursor, variable) {
251 if (variable->type_origin == NULL) {
252 XBT_DEBUG("Hash local variable %s without type", variable->name);
255 if (variable->locations.size == 0) {
256 XBT_DEBUG("Hash local variable %s without location", variable->name);
260 XBT_DEBUG("Hash local variable %s", variable->name);
262 void *variable_address =
263 (void *) mc_dwarf_resolve_locations(&variable->locations,
264 variable->object_info, unw_cursor,
265 frame_pointer, NULL);
267 dw_type_t type = variable->type;
269 XBT_DEBUG("Hash local variable %s without loctypeation", variable->name);
273 mc_hash_value(hash, state, info, variable_address, type);
276 // TODO, handle nested scopes
279 static void mc_hash_stack(mc_hash_t * hash, mc_snapshot_stack_t stack,
280 mc_hashing_state * state)
284 mc_stack_frame_t stack_frame;
286 for(s_mc_stack_frame_t const& stack_frame : stack->stack_frames) {
288 MC_HASH(*hash, stack_frame.ip);
290 mc_object_info_t info;
291 if (stack_frame.ip >= (unw_word_t) libsimgrid_info->start_exec
292 && stack_frame.ip < (unw_word_t) libsimgrid_info->end_exec)
293 info = libsimgrid_info;
294 else if (stack_frame.ip >= (unw_word_t) binary_info->start_exec
295 && stack_frame.ip < (unw_word_t) binary_info->end_exec)
300 mc_hash_stack_frame(hash, info, &(stack_frame.unw_cursor),
301 stack_frame.frame, (void *) stack_frame.frame_base,
307 static void mc_hash_stacks(mc_hash_t * hash, mc_hashing_state * state,
310 unsigned int cursor = 0;
311 mc_snapshot_stack_t current_stack;
313 MC_HASH(*hash, xbt_dynar_length(stacks_areas));
316 xbt_dynar_foreach(stacks, cursor, current_stack) {
317 XBT_DEBUG("Stack %i", i);
318 mc_hash_stack(hash, current_stack, state);
324 uint64_t mc_hash_processes_state(int num_state, std::vector<s_mc_snapshot_stack_t> const& stacks)
326 XBT_DEBUG("START hash %i", num_state);
329 mc_hashing_state state;
330 mc_hash_state_init(&state);
333 mc_hash_t hash = MC_HASH_INIT;
335 MC_HASH(hash, xbt_swag_size(simix_global->process_list)); // process count
337 // mc_hash_object_globals(&hash, &state, binary_info);
338 // mc_hash_object_globals(&hash, &state, libsimgrid_info);
339 // mc_hash_stacks(&hash, &state, stacks);
340 mc_hash_state_destroy(&state);
343 XBT_DEBUG("END hash %i", num_state);