Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
model-checker : detect valid block or fragment pointer as free function
[simgrid.git] / src / xbt / mmalloc / mm_diff.c
1 /* mm_diff - Memory snapshooting and comparison                             */
2
3 /* Copyright (c) 2008-2012. The SimGrid Team. All rights reserved.          */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 #include "xbt/ex_interface.h" /* internals of backtrace setup */
9 #include "xbt/str.h"
10 #include "mc/mc.h"
11
12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mm_diff, xbt,
13                                 "Logging specific to mm_diff in mmalloc");
14
15 extern char *xbt_binary_name;
16
17 void mmalloc_backtrace_display(xbt_mheap_t mdp, void *ptr){
18   size_t block = BLOCK(ptr);
19   int type;
20   xbt_ex_t e;
21
22   if ((char *) ptr < (char *) mdp->heapbase || block > mdp->heapsize) {
23     fprintf(stderr,"Ouch, this pointer is not mine. I cannot display its backtrace. I refuse it to death!!\n");
24     abort();
25   }
26
27   type = mdp->heapinfo[block].type;
28
29   if (type != 0) {
30     //fprintf(stderr,"Only full blocks are backtraced for now. Ignoring your request.\n");
31     return;
32   }
33   if (mdp->heapinfo[block].busy_block.bt_size == 0) {
34     fprintf(stderr,"No backtrace available for that block, sorry.\n");
35     return;
36   }
37
38   memcpy(&e.bt,&(mdp->heapinfo[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE);
39   e.used = mdp->heapinfo[block].busy_block.bt_size;
40
41   xbt_ex_setup_backtrace(&e);
42   if (e.used == 0) {
43     fprintf(stderr, "(backtrace not set)\n");
44   } else if (e.bt_strings == NULL) {
45     fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet");
46   } else {
47     int i;
48
49     fprintf(stderr, "Backtrace of where the block %p was malloced (%d frames):\n",ptr,e.used);
50     for (i = 0; i < e.used; i++)       /* no need to display "xbt_backtrace_display" */{
51       fprintf(stderr,"%d",i);fflush(NULL);
52       fprintf(stderr, "---> %s\n", e.bt_strings[i] + 4);
53     }
54   }
55 }
56
57
58 void mmalloc_backtrace_block_display(xbt_mheap_t mdp, size_t block){
59
60   int type;
61   xbt_ex_t e;
62
63   type = mdp->heapinfo[block].type;
64
65   if (type != 0) {
66     fprintf(stderr,"Only full blocks are backtraced for now. Ignoring your request.\n");
67     return;
68   }
69   if (mdp->heapinfo[block].busy_block.bt_size == 0) {
70     fprintf(stderr,"No backtrace available for that block, sorry.\n");
71     return;
72   }
73
74   memcpy(&e.bt,&(mdp->heapinfo[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE);
75   e.used = mdp->heapinfo[block].busy_block.bt_size;
76
77   xbt_ex_setup_backtrace(&e);
78   if (e.used == 0) {
79     fprintf(stderr, "(backtrace not set)\n");
80   } else if (e.bt_strings == NULL) {
81     fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet");
82   } else {
83     int i;
84
85     fprintf(stderr, "Backtrace of where the block %zu was malloced (%d frames):\n", block ,e.used);
86     for (i = 0; i < e.used; i++)       /* no need to display "xbt_backtrace_display" */{
87       fprintf(stderr,"%d",i);fflush(NULL);
88       fprintf(stderr, "---> %s\n", e.bt_strings[i] + 4);
89     }
90   }
91 }
92
93 void mmalloc_backtrace_fragment_display(xbt_mheap_t mdp, size_t block, size_t frag){
94
95   xbt_ex_t e;
96
97   memcpy(&e.bt,&(mdp->heapinfo[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE);
98   e.used = XBT_BACKTRACE_SIZE;
99
100   xbt_ex_setup_backtrace(&e);
101   if (e.used == 0) {
102     fprintf(stderr, "(backtrace not set)\n");
103   } else if (e.bt_strings == NULL) {
104     fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet");
105   } else {
106     int i;
107
108     fprintf(stderr, "Backtrace of where the fragment %zu in block %zu was malloced (%d frames):\n", frag, block ,e.used);
109     for (i = 0; i < e.used; i++)       /* no need to display "xbt_backtrace_display" */{
110       fprintf(stderr,"%d",i);fflush(NULL);
111       fprintf(stderr, "---> %s\n", e.bt_strings[i] + 4);
112     }
113   }
114 }
115
116 int mmalloc_compare_heap(xbt_mheap_t mdp1, xbt_mheap_t mdp2){
117
118   if(mdp1 == NULL && mdp2 == NULL){
119     fprintf(stderr, "Malloc descriptors null\n");
120     return 0;
121   }
122
123   int errors = mmalloc_compare_mdesc(mdp1, mdp2);
124
125   return (errors > 0);
126
127 }
128
129 int mmalloc_compare_mdesc(struct mdesc *mdp1, struct mdesc *mdp2){
130
131   int errors = 0;
132
133   if(mdp1->heaplimit != mdp2->heaplimit){
134     fprintf(stderr,"Different limit of valid info table indices\n");
135     return 1;
136   }
137
138   void* s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
139
140   void *heapbase1 = (char *)mdp1 + BLOCKSIZE;
141   void *heapbase2 = (char *)mdp2 + BLOCKSIZE;
142
143   void * breakval1 = (char *)mdp1 + ((char *)mdp1->breakval - (char *)s_heap);
144   void * breakval2 = (char *)mdp2 + ((char *)mdp2->breakval - (char *)s_heap);
145
146   size_t i, j;
147   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
148   size_t frag_size;
149
150   i = 1;
151
152   int k;
153   int distance = 0;
154   int total_distance = 0;
155
156   int pointer_align;
157   void *address_pointed1, *address_pointed2;
158
159   int block_pointed1, block_pointed2, frag_pointed1, frag_pointed2;
160   void *addr_block_pointed1, *addr_block_pointed2;
161
162   /* Check busy blocks*/
163
164   while(i < mdp1->heaplimit){
165
166     if(mdp1->heapinfo[i].type != mdp2->heapinfo[i].type){
167       fprintf(stderr,"Different type of block : %d - %d\n", mdp1->heapinfo[i].type, mdp2->heapinfo[i].type);
168       errors++;
169     }
170
171     /* Get address of block i in each heap */
172     addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
173     xbt_assert(addr_block1 < breakval1, "Block address out of heap memory used");
174
175     addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
176     xbt_assert(addr_block2 < breakval2, "Block address out of heap memory used");
177
178     if(mdp1->heapinfo[i].type == 0){ /* busy large block */
179
180       if(mdp1->heapinfo[i].busy_block.size != mdp2->heapinfo[i].busy_block.size){
181         fprintf(stderr,"Different size of a large cluster : %zu - %zu\n", mdp1->heapinfo[i].busy_block.size, mdp2->heapinfo[i].busy_block.size); 
182         fflush(NULL);
183         errors++;
184       }
185
186       if(mdp1->heapinfo[i].busy_block.busy_size != mdp2->heapinfo[i].busy_block.busy_size){
187         fprintf(stderr,"Different busy_size of a large cluster : %zu - %zu\n", mdp1->heapinfo[i].busy_block.busy_size, mdp2->heapinfo[i].busy_block.busy_size); 
188         fflush(NULL);
189         errors++;
190       }
191
192       /* Hamming distance on different blocks */
193       distance = 0;
194
195
196       for(k=0;k<mdp1->heapinfo[i].busy_block.busy_size;k++){
197
198         if(memcmp(((char *)addr_block1) + k, ((char *)addr_block2) + k, 1) != 0){
199
200           fprintf(stderr, "Different byte (offset=%d) (%p - %p) in block %zu\n", k, (char *)addr_block1 + k, (char *)addr_block2 + k, i); fflush(NULL);
201           
202           /* Check if pointer difference */
203           pointer_align = (k >> sizeof(void*)) * sizeof(void*);
204           address_pointed1 = *((void **)((char *)addr_block1 + pointer_align));
205           address_pointed2 = *((void **)((char *)addr_block2 + pointer_align));
206
207           fprintf(stderr, "Addresses pointed : %p - %p\n", address_pointed1, address_pointed2);
208           
209           block_pointed1 = ((char*)address_pointed1 - (char*)((struct mdesc*)s_heap)->heapbase) / BLOCKSIZE + 1;
210           block_pointed2 = ((char*)address_pointed2 - (char*)((struct mdesc*)s_heap)->heapbase) / BLOCKSIZE + 1;
211           
212           fprintf(stderr, "Blocks pointed : %d - %d\n", block_pointed1, block_pointed2);
213           
214           if((char *) address_pointed1 < (char*)((struct mdesc*)s_heap)->heapbase || block_pointed1 > mdp1->heapsize || block_pointed1 < 1 || (char *) address_pointed2 < (char*)((struct mdesc*)s_heap)->heapbase || block_pointed2 > mdp2->heapsize || block_pointed2 < 1) {
215             fprintf(stderr, "Unknown pointer ! \n");
216             fflush(NULL);
217             distance++;
218             continue;
219           }
220           
221           addr_block_pointed1 = ((void*) (((ADDR2UINT((size_t)block_pointed1)) - 1) * BLOCKSIZE + (char*)heapbase1));
222           addr_block_pointed2 = ((void*) (((ADDR2UINT((size_t)block_pointed2)) - 1) * BLOCKSIZE + (char*)heapbase2));
223           
224           if(mdp1->heapinfo[block_pointed1].type == mdp2->heapinfo[block_pointed2].type){
225             
226             if(mdp1->heapinfo[block_pointed1].type == 0){ // Large block
227               
228               if(mdp1->heapinfo[block_pointed1].busy_block.busy_size == mdp2->heapinfo[block_pointed2].busy_block.busy_size){
229                 
230                 if(memcmp(addr_block_pointed1, addr_block_pointed2, mdp1->heapinfo[block_pointed1].busy_block.busy_size) != 0){
231                   distance++;
232                 }else{
233                   fprintf(stderr, "False difference detected\n");
234                 }
235                 
236               }else{
237                 distance++;
238               }
239               
240             }else{ // Fragmented block
241               
242               frag_pointed1 = ((char *)address_pointed1 - (char *)((void*) (((ADDR2UINT((size_t)block_pointed1)) - 1) * BLOCKSIZE + (char*)((struct mdesc*)s_heap)->heapbase))) / pow( 2, mdp1->heapinfo[block_pointed1].type);
243               frag_pointed2 = ((char *)address_pointed2 - (char *)((void*) (((ADDR2UINT((size_t)block_pointed2)) - 1) * BLOCKSIZE + (char*)((struct mdesc*)s_heap)->heapbase))) / pow( 2, mdp1->heapinfo[block_pointed1].type);
244               
245               fprintf(stderr, "Fragments pointed : %d - %d\n", frag_pointed1, frag_pointed2);
246               
247               if((frag_pointed1 < 0) || (frag_pointed1 > (BLOCKSIZE / pow( 2, mdp1->heapinfo[block_pointed1].type))) || (frag_pointed2 < 0) || (frag_pointed2 > (BLOCKSIZE / pow( 2, mdp1->heapinfo[block_pointed1].type)))){
248                 fprintf(stderr, "Unknown pointer ! \n");
249                 fflush(NULL);
250                 distance++;
251                 continue;
252               } 
253
254               fprintf(stderr, "Size used in fragments pointed : %d - %d\n", mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1], mdp2->heapinfo[block_pointed2].busy_frag.frag_size[frag_pointed2]);  
255               
256               if(mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1] == mdp2->heapinfo[block_pointed2].busy_frag.frag_size[frag_pointed2]){
257                 
258                 if(memcmp(addr_block_pointed1, addr_block_pointed2, mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1]) != 0){
259                   distance++;
260                 }else{
261                   fprintf(stderr, "False difference detected\n");
262                 }
263                 
264               }else{
265                 distance ++;
266               }
267             }
268             
269           }else{
270             fprintf(stderr, "Pointers on blocks with different types \n");
271             distance++;
272           }
273         }
274      
275       }
276
277
278       if(distance>0){
279         fprintf(stderr,"\nDifferent data in large block %zu (size = %zu (in blocks), busy_size = %zu (in bytes))\n", i, mdp1->heapinfo[i].busy_block.size, mdp1->heapinfo[i].busy_block.busy_size);
280         fflush(NULL);
281         fprintf(stderr, "Hamming distance between blocks : %d\n", distance);
282         mmalloc_backtrace_block_display(mdp1, i);
283         mmalloc_backtrace_block_display(mdp2, i);
284         fprintf(stderr, "\n");
285         errors++;
286         total_distance += distance;
287       }
288
289       i++;
290
291     }else{
292
293       if(mdp1->heapinfo[i].type > 0){ /* busy fragmented block */
294
295         if(mdp1->heapinfo[i].type != mdp2->heapinfo[i].type){
296           fprintf(stderr,"Different size of fragments in fragmented block %zu : %d - %d\n", i, mdp1->heapinfo[i].type, mdp2->heapinfo[i].type); fflush(NULL);
297           errors++;
298         }
299
300         if(mdp1->heapinfo[i].busy_frag.nfree != mdp2->heapinfo[i].busy_frag.nfree){
301           fprintf(stderr,"Different free fragments in fragmented block %zu : %zu - %zu\n", i, mdp1->heapinfo[i].busy_frag.nfree, mdp2->heapinfo[i].busy_frag.nfree); fflush(NULL);
302           errors++;
303         }
304
305         if(mdp1->heapinfo[i].busy_frag.first != mdp2->heapinfo[i].busy_frag.first){
306           fprintf(stderr,"Different busy_size of a large cluster : %zu - %zu\n", mdp1->heapinfo[i].busy_block.busy_size, mdp2->heapinfo[i].busy_block.busy_size); fflush(NULL);
307           errors++;
308         }
309
310         frag_size = pow(2, mdp1->heapinfo[i].type);
311
312         for(j=0; j< (BLOCKSIZE/frag_size); j++){
313
314           if(mdp1->heapinfo[i].busy_frag.frag_size[j] != mdp2->heapinfo[i].busy_frag.frag_size[j]){
315             fprintf(stderr,"Different busy_size for fragment %zu in block %zu : %hu - %hu\n", j, i, mdp1->heapinfo[i].busy_frag.frag_size[j], mdp2->heapinfo[i].busy_frag.frag_size[j]); fflush(NULL);
316             errors++;
317           }
318
319           if(mdp1->heapinfo[i].busy_frag.frag_size[j] > 0){
320
321             addr_frag1 = (char *)addr_block1 + (j * frag_size);
322             xbt_assert(addr_frag1 < breakval1, "Fragment address out of heap memory used");
323
324             addr_frag2 = (char *)addr_block2 + (j * frag_size);
325             xbt_assert(addr_frag1 < breakval1, "Fragment address out of heap memory used");
326
327             /* Hamming distance on different blocks */
328             distance = 0;
329
330             for(k=0;k<mdp1->heapinfo[i].busy_frag.frag_size[j];k++){
331
332               if(memcmp(((char *)addr_frag1) + k, ((char *)addr_frag2) + k, 1) != 0){
333
334                 fprintf(stderr, "Different byte (offset=%d) (%p - %p) in fragment %zu in block %zu\n", k, (char *)addr_frag1 + k, (char *)addr_frag2 + k, j, i); fflush(NULL);
335
336                 pointer_align = (k / sizeof(void*)) * sizeof(void*);
337                 address_pointed1 = *((void **)((char *)addr_frag1 + pointer_align));
338                 address_pointed2 = *((void **)((char *)addr_frag2 + pointer_align));
339
340                 fprintf(stderr, "Addresses pointed : %p - %p\n", address_pointed1, address_pointed2);
341
342                 block_pointed1 = ((char*)address_pointed1 - (char*)((struct mdesc*)s_heap)->heapbase) / BLOCKSIZE + 1;
343                 block_pointed2 = ((char*)address_pointed2 - (char*)((struct mdesc*)s_heap)->heapbase) / BLOCKSIZE + 1;
344
345                 fprintf(stderr, "Blocks pointed : %d - %d\n", block_pointed1, block_pointed2);
346                 
347                 if((char *) address_pointed1 < (char*)((struct mdesc*)s_heap)->heapbase || block_pointed1 > mdp1->heapsize || block_pointed1 < 1 || (char *) address_pointed2 < (char*)((struct mdesc*)s_heap)->heapbase || block_pointed2 > mdp2->heapsize || block_pointed2 < 1) {
348                   fprintf(stderr, "Unknown pointer ! \n");
349                   fflush(NULL);
350                   distance++;
351                   continue;
352                 }
353
354                 addr_block_pointed1 = ((void*) (((ADDR2UINT((size_t)block_pointed1)) - 1) * BLOCKSIZE + (char*)heapbase1));
355                 addr_block_pointed2 = ((void*) (((ADDR2UINT((size_t)block_pointed2)) - 1) * BLOCKSIZE + (char*)heapbase2));
356                 
357                 if(mdp1->heapinfo[block_pointed1].type == mdp2->heapinfo[block_pointed2].type){
358                   
359                   if(mdp1->heapinfo[block_pointed1].type == 0){ // Large block
360                     
361                     if(mdp1->heapinfo[block_pointed1].busy_block.busy_size == mdp2->heapinfo[block_pointed2].busy_block.busy_size){
362                       
363                       if(memcmp(addr_block_pointed1, addr_block_pointed2, mdp1->heapinfo[block_pointed1].busy_block.busy_size) != 0){
364                         distance++;
365                       }else{
366                         fprintf(stderr, "False difference detected\n");
367                       }
368                       
369                     }else{
370                       distance++;
371                     }
372                     
373                   }else{ // Fragmented block
374
375                     frag_pointed1 = ((char *)address_pointed1 - (char *)((void*) (((ADDR2UINT((size_t)block_pointed1)) - 1) * BLOCKSIZE + (char*)((struct mdesc*)s_heap)->heapbase))) / pow( 2, mdp1->heapinfo[block_pointed1].type);
376                     frag_pointed2 = ((char *)address_pointed2 - (char *)((void*) (((ADDR2UINT((size_t)block_pointed2)) - 1) * BLOCKSIZE + (char*)((struct mdesc*)s_heap)->heapbase))) / pow( 2, mdp1->heapinfo[block_pointed1].type);
377
378                     fprintf(stderr, "Fragments pointed : %d - %d\n", frag_pointed1, frag_pointed2);
379                     
380                     if((frag_pointed1 < 0) || (frag_pointed1 > (BLOCKSIZE / pow( 2, mdp1->heapinfo[block_pointed1].type))) || (frag_pointed2 < 0) || (frag_pointed2 > (BLOCKSIZE / pow( 2, mdp1->heapinfo[block_pointed1].type)))){
381                        fprintf(stderr, "Unknown pointer ! \n");
382                        fflush(NULL);
383                        distance++;
384                        continue;
385                     } 
386
387                     fprintf(stderr, "Size used in fragments pointed : %d - %d\n", mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1], mdp2->heapinfo[block_pointed2].busy_frag.frag_size[frag_pointed2]); 
388                                         
389                     if(mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1] == mdp2->heapinfo[block_pointed2].busy_frag.frag_size[frag_pointed2]){
390                       
391                       if(memcmp(addr_block_pointed1, addr_block_pointed2, mdp1->heapinfo[block_pointed1].busy_frag.frag_size[frag_pointed1]) != 0){
392                         distance++;
393                       }else{
394                         fprintf(stderr, "False difference detected\n");
395                       }
396                       
397                     }else{
398                       distance ++;
399                     }
400                   }
401
402                 }else{
403                   fprintf(stderr, "Pointers on blocks with different types \n");
404                   distance++;
405                 }
406               }
407
408             }
409
410             if(distance > 0){
411               fprintf(stderr,"\nDifferent data in fragment %zu (size = %zu, size used = %hu) in block %zu \n", j, frag_size, mdp1->heapinfo[i].busy_frag.frag_size[j], i);
412               fprintf(stderr, "Hamming distance between fragments : %d\n", distance);
413               mmalloc_backtrace_fragment_display(mdp1, i, j);
414               mmalloc_backtrace_fragment_display(mdp2, i, j);
415               fprintf(stderr, "\n");
416               errors++;
417               total_distance += distance;
418
419             }
420
421           }
422         }
423
424         i++;
425
426       }else{ /* free block */
427
428         i++;
429
430       }
431
432     }
433
434   }
435
436
437   fprintf(stderr, "Hamming distance between heap regions : %d\n", total_distance);
438
439   return (errors);
440 }
441
442
443 /* void *get_end_addr_heap(void *heap){ */
444
445 /*   FILE *fp;                     /\* File pointer to process's proc maps file *\/ */
446 /*   char *line = NULL;            /\* Temporal storage for each line that is readed *\/ */
447 /*   ssize_t read;                 /\* Number of bytes readed *\/ */
448 /*   size_t n = 0;                 /\* Amount of bytes to read by getline *\/ */
449
450 /*   fp = fopen("/proc/self/maps", "r"); */
451
452 /*   if(fp == NULL) */
453 /*     perror("fopen failed"); */
454
455
456 /*   xbt_dynar_t lfields = NULL; */
457 /*   xbt_dynar_t start_end  = NULL; */
458 /*   void *start_addr; */
459 /*   void *end_addr; */
460
461 /*   while ((read = getline(&line, &n, fp)) != -1) { */
462
463 /*     xbt_str_trim(line, NULL); */
464 /*     xbt_str_strip_spaces(line); */
465 /*     lfields = xbt_str_split(line,NULL); */
466
467 /*     start_end = xbt_str_split(xbt_dynar_get_as(lfields, 0, char*), "-"); */
468 /*     start_addr = (void *) strtoul(xbt_dynar_get_as(start_end, 0, char*), NULL, 16); */
469 /*     end_addr = (void *) strtoul(xbt_dynar_get_as(start_end, 1, char*), NULL, 16); */
470
471 /*     if(start_addr == heap){ */
472 /*       free(line); */
473 /*       fclose(fp); */
474 /*       xbt_dynar_reset(lfields); */
475 /*       xbt_free(lfields); */
476 /*       xbt_dynar_reset(start_end); */
477 /*       xbt_free(start_end); */
478 /*       return end_addr; */
479 /*     } */
480
481 /*   } */
482
483 /*   xbt_dynar_reset(lfields); */
484 /*   xbt_free(lfields); */
485 /*   xbt_dynar_reset(start_end); */
486 /*   xbt_free(start_end); */
487 /*   free(line); */
488 /*   fclose(fp); */
489 /*   return NULL; */
490
491
492 /* } */
493
494
495 void mmalloc_display_info_heap(xbt_mheap_t h){
496
497 }
498
499
500