Logo AND Algorithmique Numérique Distribuée

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