Logo AND Algorithmique Numérique Distribuée

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