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 #include "xbt/mmalloc.h"
  12
  13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mm_diff, xbt,
  14                                 "Logging specific to mm_diff in mmalloc");
  15
  16 xbt_dynar_t mc_heap_comparison_ignore;
  17 xbt_dynar_t stacks_areas;
  18
  19 static void heap_area_pair_free(heap_area_pair_t pair);
  20 static void heap_area_pair_free_voidp(void *d);
  21 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
  22 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
  23 static heap_area_t new_heap_area(int block, int fragment);
  24
  25 static size_t heap_comparison_ignore_size(void *address);
  26 static void add_heap_equality(xbt_dynar_t equals, void *a1, void *a2);
  27 static void remove_heap_equality(xbt_dynar_t equals, int address, void *a);
  28
  29 static char* is_stack(void *address);
  30
  31 void mmalloc_backtrace_block_display(void* heapinfo, int block){
  32
  33   /* xbt_ex_t e; */
  34
  35   /* if (((malloc_info *)heapinfo)[block].busy_block.bt_size == 0) { */
  36   /*   fprintf(stderr, "No backtrace available for that block, sorry.\n"); */
  37   /*   return; */
  38   /* } */
  39
  40   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  41   /* e.used = ((malloc_info *)heapinfo)[block].busy_block.bt_size; */
  42
  43   /* xbt_ex_setup_backtrace(&e); */
  44   /* if (e.used == 0) { */
  45   /*   fprintf(stderr, "(backtrace not set)\n"); */
  46   /* } else if (e.bt_strings == NULL) { */
  47   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  48   /* } else { */
  49   /*   int i; */
  50
  51   /*   fprintf(stderr, "Backtrace of where the block %d was malloced (%d frames):\n", block ,e.used); */
  52   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  53   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  54   /*   } */
  55   /* } */
  56 }
  57
  58 void mmalloc_backtrace_fragment_display(void* heapinfo, int block, int frag){
  59
  60   /* xbt_ex_t e; */
  61
  62   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  63   /* e.used = XBT_BACKTRACE_SIZE; */
  64
  65   /* xbt_ex_setup_backtrace(&e); */
  66   /* if (e.used == 0) { */
  67   /*   fprintf(stderr, "(backtrace not set)\n"); */
  68   /* } else if (e.bt_strings == NULL) { */
  69   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  70   /* } else { */
  71   /*   int i; */
  72
  73   /*   fprintf(stderr, "Backtrace of where the fragment %d in block %d was malloced (%d frames):\n", frag, block ,e.used); */
  74   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  75   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  76   /*   } */
  77   /* } */
  78
  79 }
  80
  81 void mmalloc_backtrace_display(void *addr){
  82
  83   /* size_t block, frag_nb; */
  84   /* int type; */
  85
  86   /* xbt_mheap_t heap = __mmalloc_current_heap ?: (xbt_mheap_t) mmalloc_preinit(); */
  87
  88   /* block = (((char*) (addr) - (char*) heap -> heapbase) / BLOCKSIZE + 1); */
  89
  90   /* type = heap->heapinfo[block].type; */
  91
  92   /* switch(type){ */
  93   /* case -1 : /\* Free block *\/ */
  94   /*   fprintf(stderr, "Asked to display the backtrace of a block that is free. I'm puzzled\n"); */
  95   /*   xbt_abort(); */
  96   /*   break;  */
  97   /* case 0: /\* Large block *\/ */
  98   /*   mmalloc_backtrace_block_display(heap->heapinfo, block); */
  99   /*   break; */
 100   /* default: /\* Fragmented block *\/ */
 101   /*   frag_nb = RESIDUAL(addr, BLOCKSIZE) >> type; */
 102   /*   if(heap->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){ */
 103   /*     fprintf(stderr , "Asked to display the backtrace of a fragment that is free. I'm puzzled\n"); */
 104   /*     xbt_abort(); */
 105   /*   } */
 106   /*   mmalloc_backtrace_fragment_display(heap->heapinfo, block, frag_nb); */
 107   /*   break; */
 108   /* } */
 109 }
 110
 111
 112 void *s_heap = NULL, *heapbase1 = NULL, *heapbase2 = NULL;
 113 malloc_info *heapinfo1 = NULL, *heapinfo2 = NULL;
 114 size_t heaplimit = 0, heapsize1 = 0, heapsize2 = 0;
 115
 116 int ignore_done = 0;
 117
 118 void init_heap_information(xbt_mheap_t heap1, xbt_mheap_t heap2){
 119
 120   heaplimit = ((struct mdesc *)heap1)->heaplimit;
 121
 122   s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
 123
 124   heapbase1 = (char *)heap1 + BLOCKSIZE;
 125   heapbase2 = (char *)heap2 + BLOCKSIZE;
 126
 127   heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)s_heap)));
 128   heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)s_heap)));
 129
 130   heapsize1 = heap1->heapsize;
 131   heapsize2 = heap2->heapsize;
 132
 133 }
 134
 135 int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stack1, xbt_dynar_t *stack2, xbt_dynar_t equals){
 136
 137   if(heap1 == NULL && heap1 == NULL){
 138     XBT_DEBUG("Malloc descriptors null");
 139     return 0;
 140   }
 141
 142   if(heap1->heaplimit != heap2->heaplimit){
 143     XBT_DEBUG("Different limit of valid info table indices");
 144     return 1;
 145   }
 146
 147   /* Start comparison */
 148   size_t i1, i2, j1, j2, k;
 149   size_t current_block = -1;    /* avoid "maybe uninitialized" warning */
 150   size_t current_fragment;
 151   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 152   void *snap_addr_block1, *snap_addr_block2;
 153   char *stack_name;
 154   int nb_diff1 = 0, nb_diff2 = 0;
 155
 156   xbt_dynar_t previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
 157
 158   int equal, res_compare = 0;
 159
 160   /* Check busy blocks*/
 161
 162   i1 = 1;
 163
 164   while(i1 <= heaplimit){
 165
 166     current_block = i1;
 167
 168     if(heapinfo1[i1].type == -1){ /* Free block */
 169       i1++;
 170       continue;
 171     }
 172
 173     addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 174     snap_addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)heapbase1));
 175
 176     if(heapinfo1[i1].type == 0){  /* Large block */
 177
 178       if((xbt_dynar_length(*stack1) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block1)) != NULL)){
 179         stack_region_t stack = xbt_new0(s_stack_region_t, 1);
 180         stack->address = snap_addr_block1;
 181         stack->process_name = strdup(stack_name);
 182         stack->size = heapinfo1[i1].busy_block.busy_size;
 183         xbt_dynar_push(*stack1, &stack);
 184         res_compare = -1;
 185       }
 186
 187       if(heapinfo1[i1].busy_block.equal_to != NULL){
 188         i1++;
 189         continue;
 190       }
 191
 192       i2 = 1;
 193       equal = 0;
 194       res_compare = 0;
 195
 196       /* Try first to associate to same block in the other heap */
 197       if(heapinfo2[current_block].type == heapinfo1[current_block].type){
 198
 199         if(heapinfo2[current_block].busy_block.equal_to == NULL){
 200
 201           addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 202           snap_addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2));
 203
 204           if((xbt_dynar_length(*stack2) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block2)) != NULL)){
 205             stack_region_t stack = xbt_new0(s_stack_region_t, 1);
 206             stack->address = snap_addr_block2;
 207             stack->process_name = strdup(stack_name);
 208             stack->size = heapinfo2[current_block].busy_block.busy_size;
 209             xbt_dynar_push(*stack2, &stack);
 210             res_compare = -1;
 211           }
 212
 213           res_compare = compare_area(addr_block1, addr_block2, previous, equals);
 214
 215           if(res_compare == 0 || res_compare == -1){
 216             for(k=1; k < heapinfo2[current_block].busy_block.size; k++)
 217               heapinfo2[current_block+k].busy_block.equal_to = new_heap_area(i1, -1);
 218             for(k=1; k < heapinfo1[current_block].busy_block.size; k++)
 219               heapinfo1[current_block+k].busy_block.equal_to = new_heap_area(i1, -1);
 220             equal = 1;
 221             match_equals(previous, equals);
 222             i1 = i1 + heapinfo1[current_block].busy_block.size;
 223           }
 224
 225           xbt_dynar_reset(previous);
 226
 227         }
 228
 229       }
 230
 231       while(i2 <= heaplimit && !equal){
 232
 233         addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 234         snap_addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 235
 236         if((xbt_dynar_length(*stack2) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block2)) != NULL)){
 237           stack_region_t stack = xbt_new0(s_stack_region_t, 1);
 238           stack->address = snap_addr_block2;
 239           stack->process_name = strdup(stack_name);
 240           stack->size = heapinfo2[i2].busy_block.busy_size;
 241           xbt_dynar_push(*stack2, &stack);
 242           res_compare = -1;
 243         }
 244
 245         if(i2 == current_block){
 246           i2++;
 247           continue;
 248         }
 249
 250         if(heapinfo2[i2].type != 0){
 251           i2++;
 252           continue;
 253         }
 254
 255         if(heapinfo2[i2].busy_block.equal_to != NULL){
 256           i2++;
 257           continue;
 258         }
 259
 260         res_compare = compare_area(addr_block1, addr_block2, previous, equals);
 261
 262         if(res_compare == 0 || res_compare == -1){
 263           for(k=1; k < heapinfo2[i2].busy_block.size; k++)
 264             heapinfo2[i2+k].busy_block.equal_to = new_heap_area(i1, -1);
 265           for(k=1; k < heapinfo1[i1].busy_block.size; k++)
 266             heapinfo1[i1+k].busy_block.equal_to = new_heap_area(i2, -1);
 267           equal = 1;
 268           match_equals(previous, equals);
 269           i1 = i1 + heapinfo1[i1].busy_block.size;
 270         }
 271
 272         xbt_dynar_reset(previous);
 273
 274         i2++;
 275
 276       }
 277
 278       if(!equal){
 279         XBT_DEBUG("Block %zu not found (size_used = %zu)", i1, heapinfo1[i1].busy_block.busy_size);
 280         i1 = heaplimit + 1;
 281         nb_diff1++;
 282       }
 283
 284     }else{ /* Fragmented block */
 285
 286       for(j1=0; j1 < (size_t) (BLOCKSIZE >> heapinfo1[i1].type); j1++){
 287
 288         current_fragment = j1;
 289
 290         if(heapinfo1[i1].busy_frag.frag_size[j1] == -1) /* Free fragment */
 291           continue;
 292
 293         if(heapinfo1[i1].busy_frag.equal_to[j1] != NULL)
 294           continue;
 295
 296         addr_frag1 = (void*) ((char *)addr_block1 + (j1 << heapinfo1[i1].type));
 297
 298         i2 = 1;
 299         equal = 0;
 300
 301         /* Try first to associate to same fragment in the other heap */
 302         if(heapinfo2[current_block].type == heapinfo1[current_block].type){
 303
 304           if(heapinfo2[current_block].busy_frag.equal_to[current_fragment] == NULL){
 305
 306             addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 307             addr_frag2 = (void*) ((char *)addr_block2 + (current_fragment << ((xbt_mheap_t)s_heap)->heapinfo[current_block].type));
 308
 309             res_compare = compare_area(addr_frag1, addr_frag2, previous, equals);
 310
 311             if(res_compare == 0){
 312               equal = 1;
 313               match_equals(previous, equals);
 314             }
 315
 316             xbt_dynar_reset(previous);
 317
 318             }
 319         }
 320
 321         while(i2 <= heaplimit && !equal){
 322
 323
 324           if(heapinfo2[i2].type <= 0){
 325             i2++;
 326             continue;
 327           }
 328
 329           for(j2=0; j2 < (size_t) (BLOCKSIZE >> heapinfo2[i2].type); j2++){
 330
 331             if(heapinfo2[i2].type == heapinfo1[i1].type && i2 == current_block && j2 == current_fragment)
 332               continue;
 333
 334             if(heapinfo2[i2].busy_frag.equal_to[j2] != NULL)
 335               continue;
 336
 337             addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 338             addr_frag2 = (void*) ((char *)addr_block2 + (j2 << ((xbt_mheap_t)s_heap)->heapinfo[i2].type));
 339
 340             res_compare = compare_area(addr_frag1, addr_frag2, previous, equals);
 341
 342             if(res_compare == 0){
 343               equal = 1;
 344               match_equals(previous, equals);
 345               xbt_dynar_reset(previous);
 346               break;
 347             }
 348
 349             xbt_dynar_reset(previous);
 350
 351           }
 352
 353           i2++;
 354
 355         }
 356
 357         if(heapinfo1[i1].busy_frag.equal_to[j1] == NULL){
 358           XBT_DEBUG("Block %zu, fragment %zu not found (size_used = %d)", i1, j1, heapinfo1[i1].busy_frag.frag_size[j1]);
 359           i2 = heaplimit + 1;
 360           i1 = heaplimit + 1;
 361           nb_diff1++;
 362           break;
 363         }
 364
 365       }
 366
 367       i1++;
 368
 369     }
 370
 371   }
 372
 373   /* All blocks/fragments are equal to another block/fragment ? */
 374   size_t i = 1, j = 0;
 375
 376   while(i<=heaplimit){
 377     if(heapinfo1[i].type == 0){
 378       if(current_block == heaplimit){
 379         if(heapinfo1[i].busy_block.busy_size > 0){
 380           if(heapinfo1[i].busy_block.equal_to == NULL){
 381             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 382               addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
 383               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block1, heapinfo1[i].busy_block.busy_size);
 384               //mmalloc_backtrace_block_display((void*)heapinfo1, i);
 385             }
 386             nb_diff1++;
 387           }
 388         }
 389       }
 390       xbt_free(heapinfo1[i].busy_block.equal_to);
 391       heapinfo1[i].busy_block.equal_to = NULL;
 392     }
 393     if(heapinfo1[i].type > 0){
 394       addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
 395       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){
 396         if(current_block == heaplimit){
 397           if(heapinfo1[i].busy_frag.frag_size[j] > 0){
 398             if(heapinfo1[i].busy_frag.equal_to[j] == NULL){
 399               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 400                 addr_frag1 = (void*) ((char *)addr_block1 + (j << heapinfo1[i].type));
 401                 XBT_DEBUG("Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag1, heapinfo1[i].busy_frag.frag_size[j]);
 402                 //mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j);
 403               }
 404               nb_diff1++;
 405             }
 406           }
 407         }
 408         xbt_free(heapinfo1[i].busy_frag.equal_to[j]);
 409         heapinfo1[i].busy_frag.equal_to[j] = NULL;
 410       }
 411     }
 412     i++;
 413   }
 414
 415   i = 1;
 416
 417   while(i<=heaplimit){
 418     if(heapinfo2[i].type == 0){
 419       if(current_block == heaplimit){
 420         if(heapinfo2[i].busy_block.busy_size > 0){
 421           if(heapinfo2[i].busy_block.equal_to == NULL){
 422             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 423               addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
 424               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block2, heapinfo2[i].busy_block.busy_size);
 425               //mmalloc_backtrace_block_display((void*)heapinfo2, i);
 426             }
 427             nb_diff2++;
 428           }
 429         }
 430       }
 431       xbt_free(heapinfo2[i].busy_block.equal_to);
 432       heapinfo2[i].busy_block.equal_to = NULL;
 433     }
 434     if(heapinfo2[i].type > 0){
 435       addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
 436       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo2[i].type); j++){
 437         if(current_block == heaplimit){
 438           if(heapinfo2[i].busy_frag.frag_size[j] > 0){
 439             if(heapinfo2[i].busy_frag.equal_to[j] == NULL){
 440               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 441                 addr_frag2 = (void*) ((char *)addr_block2 + (j << heapinfo2[i].type));
 442                 XBT_DEBUG( "Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag2, heapinfo2[i].busy_frag.frag_size[j]);
 443                 //mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j);
 444               }
 445               nb_diff2++;
 446             }
 447           }
 448         }
 449         xbt_free(heapinfo2[i].busy_frag.equal_to[j]);
 450         heapinfo2[i].busy_frag.equal_to[j] = NULL;
 451       }
 452     }
 453     i++;
 454   }
 455
 456   xbt_dynar_free(&previous);
 457   ignore_done = 0;
 458   s_heap = NULL, heapbase1 = NULL, heapbase2 = NULL;
 459   heapinfo1 = NULL, heapinfo2 = NULL;
 460   heaplimit = 0, heapsize1 = 0, heapsize2 = 0;
 461
 462   return ((nb_diff1 > 0) || (nb_diff2 > 0));
 463 }
 464
 465 static heap_area_t new_heap_area(int block, int fragment){
 466   heap_area_t area = NULL;
 467   area = xbt_new0(s_heap_area_t, 1);
 468   area->block = block;
 469   area->fragment = fragment;
 470   return area;
 471 }
 472
 473
 474 static size_t heap_comparison_ignore_size(void *address){
 475
 476   unsigned int cursor = 0;
 477   int start = 0;
 478   int end = xbt_dynar_length(mc_heap_comparison_ignore) - 1;
 479   mc_heap_ignore_region_t region;
 480
 481   while(start <= end){
 482     cursor = (start + end) / 2;
 483     region = (mc_heap_ignore_region_t)xbt_dynar_get_as(mc_heap_comparison_ignore, cursor, mc_heap_ignore_region_t);
 484     if(region->address == address)
 485       return region->size;
 486     if(region->address < address)
 487       start = cursor + 1;
 488     if(region->address > address)
 489       end = cursor - 1;
 490   }
 491
 492   return 0;
 493 }
 494
 495
 496 int compare_area(void *area1, void* area2, xbt_dynar_t previous, xbt_dynar_t equals){
 497
 498   size_t i = 0, pointer_align = 0, ignore1 = 0, ignore2 = 0;
 499   void *address_pointed1, *address_pointed2;
 500   int res_compare;
 501   size_t block1, frag1, block2, frag2, size;
 502   int check_ignore = 0;
 503
 504   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 505   void *area1_to_compare, *area2_to_compare;
 506
 507   int match_pairs = 0;
 508
 509   if(previous == NULL){
 510     previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
 511     match_pairs = 1;
 512   }
 513
 514   block1 = ((char*)area1 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
 515   block2 = ((char*)area2 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
 516
 517   if(((char *)area1 < (char*)((xbt_mheap_t)s_heap)->heapbase)  || (block1 > heapsize1) || (block1 < 1) || ((char *)area2 < (char*)((xbt_mheap_t)s_heap)->heapbase) || (block2 > heapsize2) || (block2 < 1))
 518     return 1;
 519
 520   addr_block1 = ((void*) (((ADDR2UINT(block1)) - 1) * BLOCKSIZE + (char*)heapbase1));
 521   addr_block2 = ((void*) (((ADDR2UINT(block2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 522
 523   if(heapinfo1[block1].type == heapinfo2[block2].type){
 524
 525     if(heapinfo1[block1].type == -1){
 526       return 0;
 527     }else if(heapinfo1[block1].type == 0){
 528       if(heapinfo1[block1].busy_block.size != heapinfo2[block2].busy_block.size)
 529         return 1;
 530       if(heapinfo1[block1].busy_block.busy_size != heapinfo2[block2].busy_block.busy_size)
 531         return 1;
 532       if(!add_heap_area_pair(previous, block1, -1, block2, -1))
 533         return 0;
 534
 535       size = heapinfo1[block1].busy_block.busy_size;
 536       frag1 = -1;
 537       frag2 = -1;
 538
 539       area1_to_compare = addr_block1;
 540       area2_to_compare = addr_block2;
 541
 542       if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_block.ignore == 1)
 543         check_ignore = 1;
 544     }else{
 545       frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> heapinfo1[block1].type;
 546       frag2 = ((uintptr_t) (ADDR2UINT (area2) % (BLOCKSIZE))) >> heapinfo2[block2].type;
 547
 548       if(heapinfo1[block1].busy_frag.frag_size[frag1] != heapinfo2[block2].busy_frag.frag_size[frag2])
 549         return 1;
 550       if(!add_heap_area_pair(previous, block1, frag1, block2, frag2))
 551         return 0;
 552
 553       addr_frag1 = (void*) ((char *)addr_block1 + (frag1 << heapinfo1[block1].type));
 554       addr_frag2 = (void*) ((char *)addr_block2 + (frag2 << heapinfo2[block2].type));
 555
 556       area1_to_compare = addr_frag1;
 557       area2_to_compare = addr_frag2;
 558
 559       size = heapinfo1[block1].busy_frag.frag_size[frag1];
 560
 561       if(size == 0)
 562         return 0;
 563
 564       if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_frag.ignore[frag1] == 1)
 565         check_ignore = 1;
 566     }
 567   }else if((heapinfo1[block1].type > 0) && (heapinfo2[block2].type > 0)){
 568     frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> heapinfo1[block1].type;
 569     frag2 = ((uintptr_t) (ADDR2UINT (area2) % (BLOCKSIZE))) >> heapinfo2[block2].type;
 570
 571     if(heapinfo1[block1].busy_frag.frag_size[frag1] != heapinfo2[block2].busy_frag.frag_size[frag2])
 572       return 1;
 573     if(!add_heap_area_pair(previous, block1, frag1, block2, frag2))
 574       return 0;
 575
 576     addr_frag1 = (void*) ((char *)addr_block1 + (frag1 << heapinfo1[block1].type));
 577     addr_frag2 = (void*) ((char *)addr_block2 + (frag2 << heapinfo2[block2].type));
 578
 579     area1_to_compare = addr_frag1;
 580     area2_to_compare = addr_frag2;
 581
 582     size = heapinfo1[block1].busy_frag.frag_size[frag1];
 583
 584     if(size == 0)
 585       return 0;
 586
 587     if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_frag.ignore[frag1] == 1)
 588       check_ignore = 1;
 589   }else{
 590     return 1;
 591   }
 592
 593   while(i<size){
 594
 595     if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && check_ignore){
 596
 597       if((ignore1 = heap_comparison_ignore_size((char *)area1 + i)) > 0){
 598         if((ignore2 = heap_comparison_ignore_size((char *)area2 + i))  == ignore1){
 599           i = i + ignore2;
 600           ignore_done++;
 601           continue;
 602         }
 603       }
 604     }
 605
 606     if(memcmp(((char *)area1_to_compare) + i, ((char *)area2_to_compare) + i, 1) != 0){
 607
 608       /* Check pointer difference */
 609       pointer_align = (i / sizeof(void*)) * sizeof(void*);
 610       address_pointed1 = *((void **)((char *)area1_to_compare + pointer_align));
 611       address_pointed2 = *((void **)((char *)area2_to_compare + pointer_align));
 612
 613       res_compare = compare_area(address_pointed1, address_pointed2, previous, equals);
 614
 615       if(res_compare == 1)
 616         return 1;
 617
 618       i = pointer_align + sizeof(void *);
 619
 620     }else{
 621
 622       i++;
 623
 624     }
 625   }
 626
 627   if(match_pairs)
 628     match_equals(previous, equals);
 629
 630   return 0;
 631
 632
 633 }
 634
 635 static void heap_area_pair_free(heap_area_pair_t pair){
 636   if (pair){
 637     xbt_free(pair);
 638     pair = NULL;
 639   }
 640 }
 641
 642 static void heap_area_pair_free_voidp(void *d)
 643 {
 644   heap_area_pair_free((heap_area_pair_t) * (void **) d);
 645 }
 646
 647 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 648
 649   if(is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)){
 650     heap_area_pair_t pair = NULL;
 651     pair = xbt_new0(s_heap_area_pair_t, 1);
 652     pair->block1 = block1;
 653     pair->fragment1 = fragment1;
 654     pair->block2 = block2;
 655     pair->fragment2 = fragment2;
 656
 657     xbt_dynar_push(list, &pair);
 658
 659     return 1;
 660   }
 661
 662   return 0;
 663 }
 664
 665 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 666
 667   unsigned int cursor = 0;
 668   heap_area_pair_t current_pair;
 669
 670   xbt_dynar_foreach(list, cursor, current_pair){
 671     if(current_pair->block1 == block1 && current_pair->block2 == block2 && current_pair->fragment1 == fragment1 && current_pair->fragment2 == fragment2)
 672       return 0;
 673   }
 674
 675   return 1;
 676 }
 677
 678 void match_equals(xbt_dynar_t list, xbt_dynar_t equals){
 679
 680   unsigned int cursor = 0;
 681   heap_area_pair_t current_pair;
 682   heap_area_t previous_area;
 683
 684   void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2;
 685
 686   xbt_dynar_foreach(list, cursor, current_pair){
 687
 688     if(current_pair->fragment1 != -1){
 689
 690       real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 691       real_addr_frag1 = (void*) ((char *)real_addr_block1 + (current_pair->fragment1 << heapinfo1[current_pair->block1].type));
 692       real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 693       real_addr_frag2 = (void*) ((char *)real_addr_block2 + (current_pair->fragment2 << heapinfo2[current_pair->block2].type));
 694
 695       if(heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] != NULL){
 696         remove_heap_equality(equals, 1, real_addr_frag1);
 697         previous_area = heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1];
 698         xbt_free(heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment]);
 699         heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL;
 700         xbt_free(previous_area);
 701       }
 702       if(heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] != NULL){
 703         remove_heap_equality(equals, 2, real_addr_frag2);
 704         previous_area = heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2];
 705         xbt_free(heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment]);
 706         heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL;
 707         xbt_free(previous_area);
 708       }
 709
 710       if(real_addr_frag1 != real_addr_frag2)
 711         add_heap_equality(equals, real_addr_frag1, real_addr_frag2);
 712
 713       heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] = new_heap_area(current_pair->block2, current_pair->fragment2);
 714       heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] = new_heap_area(current_pair->block1, current_pair->fragment1);
 715
 716     }else{
 717
 718       real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 719       real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
 720
 721       if(heapinfo1[current_pair->block1].busy_block.equal_to != NULL){
 722         remove_heap_equality(equals, 1, real_addr_block1);
 723         previous_area = heapinfo1[current_pair->block1].busy_block.equal_to;
 724         xbt_free(heapinfo2[previous_area->block].busy_block.equal_to);
 725         heapinfo2[previous_area->block].busy_block.equal_to = NULL;
 726         xbt_free(previous_area);
 727       }
 728       if(heapinfo2[current_pair->block2].busy_block.equal_to != NULL){
 729         remove_heap_equality(equals, 2, real_addr_block2);
 730         previous_area = heapinfo2[current_pair->block2].busy_block.equal_to;
 731         xbt_free(heapinfo1[previous_area->block].busy_block.equal_to);
 732         heapinfo1[previous_area->block].busy_block.equal_to = NULL;
 733         xbt_free(previous_area);
 734       }
 735
 736       if(real_addr_block1 != real_addr_block2)
 737         add_heap_equality(equals, real_addr_block1, real_addr_block2);
 738
 739       heapinfo1[current_pair->block1].busy_block.equal_to = new_heap_area(current_pair->block2, current_pair->fragment2);
 740       heapinfo2[current_pair->block2].busy_block.equal_to = new_heap_area(current_pair->block1, current_pair->fragment1);
 741
 742     }
 743   }
 744
 745
 746 }
 747
 748 #ifndef max
 749 #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
 750 #endif
 751
 752 int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2){
 753
 754   if(heap1 == NULL && heap1 == NULL){
 755     XBT_DEBUG("Malloc descriptors null");
 756     return 0;
 757   }
 758
 759   if(heap1->heaplimit != heap2->heaplimit){
 760     XBT_DEBUG("Different limit of valid info table indices");
 761     return 1;
 762   }
 763
 764   /* Heap information */
 765   heaplimit = ((struct mdesc *)heap1)->heaplimit;
 766
 767   s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
 768
 769   heapbase1 = (char *)heap1 + BLOCKSIZE;
 770   heapbase2 = (char *)heap2 + BLOCKSIZE;
 771
 772   heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)s_heap)));
 773   heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)s_heap)));
 774
 775   heapsize1 = heap1->heapsize;
 776   heapsize2 = heap2->heapsize;
 777
 778   /* Start comparison */
 779   size_t i, j, k;
 780   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 781
 782   int distance = 0;
 783
 784   /* Check busy blocks*/
 785
 786   i = 1;
 787
 788   while(i <= heaplimit){
 789
 790     addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
 791     addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
 792
 793     if(heapinfo1[i].type != heapinfo2[i].type){
 794
 795       distance += BLOCKSIZE;
 796       XBT_DEBUG("Different type of blocks (%zu) : %d - %d -> distance = %d", i, heapinfo1[i].type, heapinfo2[i].type, distance);
 797       i++;
 798
 799     }else{
 800
 801       if(heapinfo1[i].type == -1){ /* Free block */
 802         i++;
 803         continue;
 804       }
 805
 806       if(heapinfo1[i].type == 0){ /* Large block */
 807
 808         if(heapinfo1[i].busy_block.size != heapinfo2[i].busy_block.size){
 809           distance += BLOCKSIZE * max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
 810           i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
 811           XBT_DEBUG("Different larger of cluster at block %zu : %zu - %zu -> distance = %d", i, heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size, distance);
 812           continue;
 813         }
 814
 815         /*if(heapinfo1[i].busy_block.busy_size != heapinfo2[i].busy_block.busy_size){
 816           distance += max(heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size);
 817           i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
 818           XBT_DEBUG("Different size used oin large cluster at block %zu : %zu - %zu -> distance = %d", i, heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size, distance);
 819           continue;
 820           }*/
 821
 822         k = 0;
 823
 824         //while(k < (heapinfo1[i].busy_block.busy_size)){
 825         while(k < heapinfo1[i].busy_block.size * BLOCKSIZE){
 826           if(memcmp((char *)addr_block1 + k, (char *)addr_block2 + k, 1) != 0){
 827             distance ++;
 828           }
 829           k++;
 830         }
 831
 832         i++;
 833
 834       }else { /* Fragmented block */
 835
 836         for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){
 837
 838           addr_frag1 = (void*) ((char *)addr_block1 + (j << heapinfo1[i].type));
 839           addr_frag2 = (void*) ((char *)addr_block2 + (j << heapinfo2[i].type));
 840
 841           if(heapinfo1[i].busy_frag.frag_size[j] == 0 && heapinfo2[i].busy_frag.frag_size[j] == 0){
 842             continue;
 843           }
 844
 845
 846           /*if(heapinfo1[i].busy_frag.frag_size[j] != heapinfo2[i].busy_frag.frag_size[j]){
 847             distance += max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j]);
 848             XBT_DEBUG("Different size used in fragment %zu in block %zu : %d - %d -> distance = %d", j, i, heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j], distance);
 849             continue;
 850             }*/
 851
 852           k=0;
 853
 854           //while(k < max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j])){
 855           while(k < (BLOCKSIZE / (BLOCKSIZE >> heapinfo1[i].type))){
 856             if(memcmp((char *)addr_frag1 + k, (char *)addr_frag2 + k, 1) != 0){
 857               distance ++;
 858             }
 859             k++;
 860           }
 861
 862         }
 863
 864         i++;
 865
 866       }
 867
 868     }
 869
 870   }
 871
 872   return distance;
 873
 874 }
 875
 876 static char* is_stack(void *address){
 877   unsigned int cursor = 0;
 878   stack_region_t stack;
 879
 880   xbt_dynar_foreach(stacks_areas, cursor, stack){
 881     if(address == stack->address)
 882       return stack->process_name;
 883   }
 884
 885   return NULL;
 886 }
 887
 888 static void add_heap_equality(xbt_dynar_t equals, void *a1, void *a2){
 889
 890   if(xbt_dynar_is_empty(equals)){
 891
 892     heap_equality_t he = xbt_new0(s_heap_equality_t, 1);
 893     he->address1 = a1;
 894     he->address2 = a2;
 895
 896     xbt_dynar_insert_at(equals, 0, &he);
 897
 898   }else{
 899
 900     unsigned int cursor = 0;
 901     int start = 0;
 902     int end = xbt_dynar_length(equals) - 1;
 903     heap_equality_t current_equality = NULL;
 904
 905     while(start <= end){
 906       cursor = (start + end) / 2;
 907       current_equality = (heap_equality_t)xbt_dynar_get_as(equals, cursor, heap_equality_t);
 908       if(current_equality->address1 == a1){
 909         if(current_equality->address2 == a2)
 910           return;
 911         if(current_equality->address2 < a2)
 912           start = cursor + 1;
 913         if(current_equality->address2 > a2)
 914           end = cursor - 1;
 915       }
 916       if(current_equality->address1 < a1)
 917         start = cursor + 1;
 918       if(current_equality->address1 > a1)
 919         end = cursor - 1;
 920     }
 921
 922     heap_equality_t he = xbt_new0(s_heap_equality_t, 1);
 923     he->address1 = a1;
 924     he->address2 = a2;
 925
 926     if(current_equality->address1 < a1)
 927       xbt_dynar_insert_at(equals, cursor + 1 , &he);
 928     else
 929        xbt_dynar_insert_at(equals, cursor, &he);
 930
 931   }
 932
 933 }
 934
 935 static void remove_heap_equality(xbt_dynar_t equals, int address, void *a){
 936
 937   unsigned int cursor = 0;
 938   heap_equality_t current_equality;
 939   int found = 0;
 940
 941   if(address == 1){
 942
 943     int start = 0;
 944     int end = xbt_dynar_length(equals) - 1;
 945
 946
 947     while(start <= end && found == 0){
 948       cursor = (start + end) / 2;
 949       current_equality = (heap_equality_t)xbt_dynar_get_as(equals, cursor, heap_equality_t);
 950       if(current_equality->address1 == a)
 951         found = 1;
 952       if(current_equality->address1 < a)
 953         start = cursor + 1;
 954       if(current_equality->address1 > a)
 955         end = cursor - 1;
 956     }
 957
 958     if(found == 1)
 959       xbt_dynar_remove_at(equals, cursor, NULL);
 960
 961   }else{
 962
 963     xbt_dynar_foreach(equals, cursor, current_equality){
 964       if(current_equality->address2 == a){
 965         found = 1;
 966         break;
 967       }
 968     }
 969
 970     if(found == 1)
 971       xbt_dynar_remove_at(equals, cursor, NULL);
 972
 973   }
 974
 975 }
 976
 977 int is_free_area(void *area, xbt_mheap_t heap){
 978
 979   void *sheap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
 980   malloc_info *heapinfo = (malloc_info *)((char *)heap + ((uintptr_t)((char *)heap->heapinfo - (char *)sheap)));
 981   size_t heapsize = heap->heapsize;
 982
 983   /* Get block number */
 984   size_t block = ((char*)area - (char*)((xbt_mheap_t)sheap)->heapbase) / BLOCKSIZE + 1;
 985   size_t fragment;
 986
 987   /* Check if valid block number */
 988   if((char *)area < (char*)((xbt_mheap_t)sheap)->heapbase || block > heapsize || block < 1)
 989     return 0;
 990
 991   if(heapinfo[block].type < 0)
 992     return 1;
 993
 994   if(heapinfo[block].type == 0)
 995     return 0;
 996
 997   if(heapinfo[block].type > 0){
 998     fragment = ((uintptr_t) (ADDR2UINT(area) % (BLOCKSIZE))) >> heapinfo[block].type;
 999     if(heapinfo[block].busy_frag.frag_size[fragment] == 0)
1000       return 1;
1001   }
1002
1003   return 0;
1004
1005
1006
1007 }