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