Logo AND Algorithmique Numérique Distribuée

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