1 /* Copyright (c) 2014-2015. 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. */
11 #include "mc_private.h"
12 #include "mc/datatypes.h"
14 #include "mc_hash.hpp"
16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_hash, mc, "Logging specific to mc_hash");
22 #define MC_HASH_INIT ((simgrid::mc::hash_type)5381)
25 static void hash_update(hash_type& hash, T const& value)
27 hash = (hash << 5) + hash + (std::uint64_t) value;
33 typedef struct s_mc_hashing_state {
34 // Set of pointers/addresses already processed (avoid loops):
35 mc_address_set_t handled_addresses;
38 void mc_hash_state_init(mc_hashing_state * state);
39 void mc_hash_state_destroy(mc_hashing_state * state);
41 void mc_hash_state_init(mc_hashing_state * state)
43 state->handled_addresses = mc_address_set_new();
46 void mc_hash_state_destroy(mc_hashing_state * state)
48 mc_address_set_free(&state->handled_addresses);
51 // TODO, detect and avoid loops
53 static bool mc_ignored(const void *address, size_t size)
55 mc_heap_ignore_region_t region;
56 unsigned int cursor = 0;
57 const void *end = (char *) address + size;
58 xbt_dynar_foreach(mc_heap_comparison_ignore, cursor, region) {
59 void *istart = region->address;
60 void *iend = (char *) region->address + region->size;
62 if (address >= istart && address < iend && end >= istart && end < iend)
69 static void mc_hash_binary(hash_type * hash, const void *s, size_t len)
71 const char *p = (const char*) s;
72 for (size_t i = 0; i != len; ++i) {
73 hash_update(*hash, p[i]);
77 /** \brief Compute a hash for a given value of a given type
79 * We try to be very conservative (do not hash too ambiguous things).
81 * \param address address of the variable
82 * \param type type of the variable
84 static void mc_hash_value(hash_type * hash, mc_hashing_state * state,
85 simgrid::mc::ObjectInformation* info, const void *address,
86 simgrid::mc::Type* type)
88 simgrid::mc::Process* process = &mc_model_checker->process();
93 // Not relevant, do nothing:
94 case DW_TAG_unspecified_type:
97 // Simple case, hash this has binary:
98 case DW_TAG_base_type:
99 case DW_TAG_enumeration_type:
101 if (mc_ignored(address, 1))
103 mc_hash_binary(hash, address, type->byte_size);
107 case DW_TAG_array_type:
109 if (mc_ignored(address, type->byte_size))
112 long element_count = type->element_count;
113 simgrid::mc::Type* subtype = type->subtype;
114 if (subtype == NULL) {
115 XBT_DEBUG("Hash array without subtype");
119 for (i = 0; i != element_count; ++i) {
120 XBT_DEBUG("Hash array element %i", i);
121 void *subaddress = ((char *) address) + i * subtype->byte_size;
122 mc_hash_value(hash, state, info, subaddress, subtype);
129 case DW_TAG_volatile_type:
130 case DW_TAG_const_type:
131 case DW_TAG_restrict_type:
133 type = type->subtype;
140 case DW_TAG_structure_type:
141 case DW_TAG_class_type:
143 if (mc_ignored(address, type->byte_size))
146 unsigned int cursor = 0;
147 simgrid::mc::Type* member;
148 xbt_dynar_foreach(type->members, cursor, member) {
149 XBT_DEBUG("Hash struct member %s", member->name);
150 if (type->subtype == NULL)
152 void *member_variable = mc_member_resolve(address, type, member, NULL);
153 mc_hash_value(hash, state, info, member_variable, type->subtype);
158 // Pointer, we hash a single value but it might be an array.
159 case DW_TAG_pointer_type:
160 case DW_TAG_reference_type:
161 case DW_TAG_rvalue_reference_type:
163 if (mc_ignored(address, 1))
166 void *pointed = *(void **) address;
167 if (pointed == NULL) {
168 XBT_DEBUG("Hashed pinter is NULL");
172 if (mc_address_test(state->handled_addresses, pointed)) {
173 XBT_DEBUG("Hashed pointed data %p already hashed", pointed);
176 mc_address_add(state->handled_addresses, pointed);
178 // Anything outside the R/W segments and the heap is not hashed:
179 bool valid_pointer = (pointed >= (void *) binary_info->start_rw
180 && pointed <= (void *) binary_info->end_rw)
181 || (pointed >= (void *) libsimgrid_info->start_rw
182 && pointed <= (void *) libsimgrid_info->end_rw)
183 || (pointed >= process->heap_address
184 && pointed < (void *) ((const char *) process->heap_address + STD_HEAP_SIZE));
185 if (!valid_pointer) {
186 XBT_DEBUG("Hashed pointed data %p is in an ignored range", pointed);
190 if (type->subtype == NULL) {
191 XBT_DEBUG("Missing type for %p (type=%s)",
192 pointed, type->type_id.c_str());
197 type = type->subtype;
202 case DW_TAG_union_type:
203 case DW_TAG_subroutine_type:
209 static void mc_hash_object_globals(hash_type * hash, mc_hashing_state * state,
210 simgrid::mc::ObjectInformation* info)
212 unsigned int cursor = 0;
213 simgrid::mc::Variable* variable;
214 xbt_dynar_foreach(info->global_variables, cursor, variable) {
215 XBT_DEBUG("Hash global variable %s", variable->name);
217 if (variable->type_id == NULL) {
222 simgrid::mc::Type* type = variable->type;
228 const char *address = variable->address;
229 bool valid_pointer = (address >= binary_info->start_rw
230 && address <= binary_info->end_rw)
231 || (address >= libsimgrid_info->start_rw
232 && address <= libsimgrid_info->end_rw)
233 || (address >= (const char *) process->heap_address
234 && address < (const char *) process->heap_address + STD_HEAP_SIZE);
238 mc_hash_value(hash, state, info, variable->address, type);
242 static void mc_hash_stack_frame(mc_hash_t * hash,
243 simgrid::mc::ObjectInformation* info,
244 unw_cursor_t * unw_cursor, simgrid::mc::Frame* frame,
245 char *frame_pointer, mc_hashing_state * state)
250 unsigned int cursor = 0;
251 simgrid::mc::Variable* variable;
252 xbt_dynar_foreach(frame->variables, cursor, variable) {
254 if (variable->type_id == NULL) {
255 XBT_DEBUG("Hash local variable %s without type", variable->name);
258 if (variable->locations.size == 0) {
259 XBT_DEBUG("Hash local variable %s without location", variable->name);
263 XBT_DEBUG("Hash local variable %s", variable->name);
265 void *variable_address =
266 (void *) mc_dwarf_resolve_locations(&variable->locations,
267 variable->object_info, unw_cursor,
268 frame_pointer, NULL);
270 simgrid::mc::Type* type = variable->type;
272 XBT_DEBUG("Hash local variable %s without loctypeation", variable->name);
276 mc_hash_value(hash, state, info, variable_address, type);
279 // TODO, handle nested scopes
282 static void mc_hash_stack(mc_hash_t * hash, mc_snapshot_stack_t stack,
283 mc_hashing_state * state)
287 mc_stack_frame_t stack_frame;
289 for(s_mc_stack_frame_t const& stack_frame : stack->stack_frames) {
291 hash_update(*hash, stack_frame.ip);
293 simgrid::mc::ObjectInformation* info;
294 if (stack_frame.ip >= (unw_word_t) libsimgrid_info->start_exec
295 && stack_frame.ip < (unw_word_t) libsimgrid_info->end_exec)
296 info = libsimgrid_info;
297 else if (stack_frame.ip >= (unw_word_t) binary_info->start_exec
298 && stack_frame.ip < (unw_word_t) binary_info->end_exec)
303 mc_hash_stack_frame(hash, info, &(stack_frame.unw_cursor),
304 stack_frame.frame, (void *) stack_frame.frame_base,
310 static void mc_hash_stacks(mc_hash_t * hash, mc_hashing_state * state,
313 unsigned int cursor = 0;
314 mc_snapshot_stack_t current_stack;
316 hash_update(*hash, xbt_dynar_length(stacks_areas));
319 xbt_dynar_foreach(stacks, cursor, current_stack) {
320 XBT_DEBUG("Stack %i", i);
321 mc_hash_stack(hash, current_stack, state);
327 static hash_type hash(std::vector<s_mc_snapshot_stack_t> const& stacks)
330 mc_hashing_state state;
331 mc_hash_state_init(&state);
334 hash_type hash = MC_HASH_INIT;
336 hash_update(hash, xbt_swag_size(simix_global->process_list));
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);
348 hash_type hash(Snapshot const& snapshot)
350 XBT_DEBUG("START hash %i", snapshot.num_state);
351 hash_type res = simgrid::mc::hash(snapshot.stacks);
352 XBT_DEBUG("END hash %i", snapshot.num_state);