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