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. */
10 #include "mc_private.h"
11 #include "mc/datatypes.h"
14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_hash, mc, "Logging specific to mc_hash");
17 typedef uint64_t mc_hash_t;
18 #define MC_HASH_INIT ((uint64_t)5381)
20 // #define MC_HASH(hash, value) hash = (((hash << 5) + hash) + (uint64_t) value)
21 #define MC_HASH(hash, value) \
22 { hash = (((hash << 5) + hash) + (uint64_t) value);\
23 XBT_DEBUG("%s:%i: %"PRIx64" -> %"PRIx64, __FILE__, __LINE__, (uint64_t) value, hash); }
27 typedef struct s_mc_hashing_state {
28 // Set of pointers/addresses already processed (avoid loops):
29 mc_address_set_t handled_addresses;
32 void mc_hash_state_init(mc_hashing_state * state);
33 void mc_hash_state_destroy(mc_hashing_state * state);
35 void mc_hash_state_init(mc_hashing_state * state)
37 state->handled_addresses = mc_address_set_new();
40 void mc_hash_state_destroy(mc_hashing_state * state)
42 mc_address_set_free(&state->handled_addresses);
45 // TODO, detect and avoid loops
47 static bool mc_ignored(const void *address, size_t size)
49 mc_heap_ignore_region_t region;
50 unsigned int cursor = 0;
51 const void *end = (char *) address + size;
52 xbt_dynar_foreach(mc_heap_comparison_ignore, cursor, region) {
53 void *istart = region->address;
54 void *iend = (char *) region->address + region->size;
56 if (address >= istart && address < iend && end >= istart && end < iend)
63 static void mc_hash_binary(mc_hash_t * hash, const void *s, size_t len)
65 const char *p = (const void *) s;
67 for (i = 0; i != len; ++i) {
73 /** \brief Compute a hash for a given value of a given type
75 * We try to be very conservative (do not hash too ambiguous things).
77 * \param address address of the variable
78 * \param type type of the variable
80 static void mc_hash_value(mc_hash_t * hash, mc_hashing_state * state,
81 mc_object_info_t info, const void *address,
88 // Not relevant, do nothing:
89 case DW_TAG_unspecified_type:
92 // Simple case, hash this has binary:
93 case DW_TAG_base_type:
94 case DW_TAG_enumeration_type:
96 if (mc_ignored(address, 1))
98 mc_hash_binary(hash, address, type->byte_size);
102 case DW_TAG_array_type:
104 if (mc_ignored(address, type->byte_size))
107 long element_count = type->element_count;
108 dw_type_t subtype = type->subtype;
109 if (subtype == NULL) {
110 XBT_DEBUG("Hash array without subtype");
114 for (i = 0; i != element_count; ++i) {
115 XBT_DEBUG("Hash array element %i", i);
116 void *subaddress = ((char *) address) + i * subtype->byte_size;
117 mc_hash_value(hash, state, info, subaddress, subtype);
124 case DW_TAG_volatile_type:
125 case DW_TAG_const_type:
126 case DW_TAG_restrict_type:
128 type = type->subtype;
135 case DW_TAG_structure_type:
136 case DW_TAG_class_type:
138 if (mc_ignored(address, type->byte_size))
141 unsigned int cursor = 0;
143 xbt_dynar_foreach(type->members, cursor, member) {
144 XBT_DEBUG("Hash struct member %s", member->name);
145 if (type->subtype == NULL)
147 void *member_variable = mc_member_resolve(address, type, member, NULL);
148 mc_hash_value(hash, state, info, member_variable, type->subtype);
153 // Pointer, we hash a single value but it might be an array.
154 case DW_TAG_pointer_type:
155 case DW_TAG_reference_type:
156 case DW_TAG_rvalue_reference_type:
158 if (mc_ignored(address, 1))
161 void *pointed = *(void **) address;
162 if (pointed == NULL) {
163 XBT_DEBUG("Hashed pinter is NULL");
167 if (mc_address_test(state->handled_addresses, pointed)) {
168 XBT_DEBUG("Hashed pointed data %p already hashed", pointed);
171 mc_address_add(state->handled_addresses, pointed);
173 // Anything outside the R/W segments and the heap is not hashed:
174 bool valid_pointer = (pointed >= (void *) mc_binary_info->start_rw
175 && pointed <= (void *) mc_binary_info->end_rw)
176 || (pointed >= (void *) mc_libsimgrid_info->start_rw
177 && pointed <= (void *) mc_libsimgrid_info->end_rw)
178 || (pointed >= std_heap
179 && pointed < (void *) ((const char *) std_heap + STD_HEAP_SIZE));
180 if (!valid_pointer) {
181 XBT_DEBUG("Hashed pointed data %p is in an ignored range", pointed);
185 if (type->subtype == NULL) {
186 XBT_DEBUG("Missing type for %p (type=%s)", pointed, type->dw_type_id);
191 type = type->subtype;
196 case DW_TAG_union_type:
197 case DW_TAG_subroutine_type:
203 static void mc_hash_object_globals(mc_hash_t * hash, mc_hashing_state * state,
204 mc_object_info_t info)
206 unsigned int cursor = 0;
207 dw_variable_t variable;
208 xbt_dynar_foreach(info->global_variables, cursor, variable) {
209 XBT_DEBUG("Hash global variable %s", variable->name);
211 if (variable->type_origin == NULL) {
216 dw_type_t type = variable->type;
222 const char *address = variable->address;
223 bool valid_pointer = (address >= mc_binary_info->start_rw
224 && address <= mc_binary_info->end_rw)
225 || (address >= mc_libsimgrid_info->start_rw
226 && address <= mc_libsimgrid_info->end_rw)
227 || (address >= (const char *) std_heap
228 && address < (const char *) std_heap + STD_HEAP_SIZE);
232 mc_hash_value(hash, state, info, variable->address, type);
236 static void mc_hash_stack_frame(mc_hash_t * hash,
237 mc_object_info_t info,
238 unw_cursor_t * unw_cursor, dw_frame_t frame,
239 char *frame_pointer, mc_hashing_state * state)
244 unsigned int cursor = 0;
245 dw_variable_t variable;
246 xbt_dynar_foreach(frame->variables, cursor, variable) {
248 if (variable->type_origin == NULL) {
249 XBT_DEBUG("Hash local variable %s without type", variable->name);
252 if (variable->locations.size == 0) {
253 XBT_DEBUG("Hash local variable %s without location", variable->name);
257 XBT_DEBUG("Hash local variable %s", variable->name);
259 void *variable_address =
260 (void *) mc_dwarf_resolve_locations(&variable->locations,
261 variable->object_info, unw_cursor,
262 frame_pointer, NULL);
264 dw_type_t type = variable->type;
266 XBT_DEBUG("Hash local variable %s without loctypeation", variable->name);
270 mc_hash_value(hash, state, info, variable_address, type);
273 // TODO, handle nested scopes
276 static void mc_hash_stack(mc_hash_t * hash, mc_snapshot_stack_t stack,
277 mc_hashing_state * state)
281 mc_stack_frame_t stack_frame;
283 xbt_dynar_foreach(stack->stack_frames, cursor, stack_frame) {
285 MC_HASH(*hash, stack_frame->ip);
287 mc_object_info_t info;
288 if (stack_frame->ip >= (unw_word_t) mc_libsimgrid_info->start_exec
289 && stack_frame->ip < (unw_word_t) mc_libsimgrid_info->end_exec)
290 info = mc_libsimgrid_info;
291 else if (stack_frame->ip >= (unw_word_t) mc_binary_info->start_exec
292 && stack_frame->ip < (unw_word_t) mc_binary_info->end_exec)
293 info = mc_binary_info;
297 mc_hash_stack_frame(hash, info, &(stack_frame->unw_cursor),
298 stack_frame->frame, (void *) stack_frame->frame_base,
304 static void mc_hash_stacks(mc_hash_t * hash, mc_hashing_state * state,
307 unsigned int cursor = 0;
308 mc_snapshot_stack_t current_stack;
310 MC_HASH(*hash, xbt_dynar_length(stacks_areas));
313 xbt_dynar_foreach(stacks, cursor, current_stack) {
314 XBT_DEBUG("Stack %i", i);
315 mc_hash_stack(hash, current_stack, state);
321 uint64_t mc_hash_processes_state(int num_state, xbt_dynar_t stacks)
323 XBT_DEBUG("START hash %i", num_state);
325 mc_hashing_state state;
326 mc_hash_state_init(&state);
328 mc_hash_t hash = MC_HASH_INIT;
330 MC_HASH(hash, xbt_swag_size(simix_global->process_list)); // process count
331 // mc_hash_object_globals(&hash, &state, mc_binary_info);
332 // mc_hash_object_globals(&hash, &state, mc_libsimgrid_info);
333 // mc_hash_stacks(&hash, &state, stacks);
335 mc_hash_state_destroy(&state);
337 XBT_DEBUG("END hash %i", num_state);