src/mc/mc_diff.c

   1 /* mc_diff - Memory snapshooting and comparison                             */
   2
   3 /* Copyright (c) 2008-2014. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/ex_interface.h"   /* internals of backtrace setup */
  10 #include "xbt/str.h"
  11 #include "mc/mc.h"
  12 #include "xbt/mmalloc.h"
  13 #include "mc/datatypes.h"
  14 #include "mc/mc_private.h"
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_diff, xbt,
  17                                 "Logging specific to mc_diff in mc");
  18
  19 xbt_dynar_t mc_heap_comparison_ignore;
  20 xbt_dynar_t stacks_areas;
  21 void *maestro_stack_start, *maestro_stack_end;
  22
  23
  24 /********************************* Backtrace ***********************************/
  25 /******************************************************************************/
  26
  27 static void mmalloc_backtrace_block_display(void *heapinfo, int block)
  28 {
  29
  30   /* xbt_ex_t e; */
  31
  32   /* if (((malloc_info *)heapinfo)[block].busy_block.bt_size == 0) { */
  33   /*   fprintf(stderr, "No backtrace available for that block, sorry.\n"); */
  34   /*   return; */
  35   /* } */
  36
  37   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  38   /* e.used = ((malloc_info *)heapinfo)[block].busy_block.bt_size; */
  39
  40   /* xbt_ex_setup_backtrace(&e); */
  41   /* if (e.used == 0) { */
  42   /*   fprintf(stderr, "(backtrace not set)\n"); */
  43   /* } else if (e.bt_strings == NULL) { */
  44   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  45   /* } else { */
  46   /*   int i; */
  47
  48   /*   fprintf(stderr, "Backtrace of where the block %d was malloced (%d frames):\n", block ,e.used); */
  49   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  50   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  51   /*   } */
  52   /* } */
  53 }
  54
  55 static void mmalloc_backtrace_fragment_display(void *heapinfo, int block,
  56                                                int frag)
  57 {
  58
  59   /* xbt_ex_t e; */
  60
  61   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  62   /* e.used = XBT_BACKTRACE_SIZE; */
  63
  64   /* xbt_ex_setup_backtrace(&e); */
  65   /* if (e.used == 0) { */
  66   /*   fprintf(stderr, "(backtrace not set)\n"); */
  67   /* } else if (e.bt_strings == NULL) { */
  68   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  69   /* } else { */
  70   /*   int i; */
  71
  72   /*   fprintf(stderr, "Backtrace of where the fragment %d in block %d was malloced (%d frames):\n", frag, block ,e.used); */
  73   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  74   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  75   /*   } */
  76   /* } */
  77
  78 }
  79
  80 static void mmalloc_backtrace_display(void *addr)
  81 {
  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 MMALLOC_TYPE_HEAPINFO :  */
  94   /* case MMALLOC_TYPE_FREE : /\* 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 static int compare_backtrace(int b1, int f1, int b2, int f2)
 114 {
 115   /*int i = 0;
 116      if(f1 != -1){
 117      for(i=0; i< XBT_BACKTRACE_SIZE; i++){
 118      if(heapinfo1[b1].busy_frag.bt[f1][i] != heapinfo2[b2].busy_frag.bt[f2][i]){
 119      //mmalloc_backtrace_fragment_display((void*)heapinfo1, b1, f1);
 120      //mmalloc_backtrace_fragment_display((void*)heapinfo2, b2, f2);
 121      return 1;
 122      }
 123      }
 124      }else{
 125      for(i=0; i< heapinfo1[b1].busy_block.bt_size; i++){
 126      if(heapinfo1[b1].busy_block.bt[i] != heapinfo2[b2].busy_block.bt[i]){
 127      //mmalloc_backtrace_block_display((void*)heapinfo1, b1);
 128      //mmalloc_backtrace_block_display((void*)heapinfo2, b2);
 129      return 1;
 130      }
 131      }
 132      } */
 133   return 0;
 134 }
 135
 136
 137 /*********************************** Heap comparison ***********************************/
 138 /***************************************************************************************/
 139
 140 typedef char *type_name;
 141
 142 struct s_mc_diff {
 143   /** \brief Base address of the real heap */
 144   void *s_heap;
 145   size_t heaplimit;
 146   // Number of blocks in the heaps:
 147   size_t heapsize1, heapsize2;
 148   xbt_dynar_t to_ignore1, to_ignore2;
 149   s_heap_area_t *equals_to1, *equals_to2;
 150   dw_type_t *types1, *types2;
 151   size_t available;
 152 };
 153
 154 #define equals_to1_(i,j) equals_to1[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 155 #define equals_to2_(i,j) equals_to2[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 156 #define types1_(i,j) types1[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 157 #define types2_(i,j) types2[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 158
 159 __thread struct s_mc_diff *mc_diff_info = NULL;
 160
 161 /*********************************** Free functions ************************************/
 162
 163 static void heap_area_pair_free(heap_area_pair_t pair)
 164 {
 165   xbt_free(pair);
 166   pair = NULL;
 167 }
 168
 169 static void heap_area_pair_free_voidp(void *d)
 170 {
 171   heap_area_pair_free((heap_area_pair_t) * (void **) d);
 172 }
 173
 174 static void heap_area_free(heap_area_t area)
 175 {
 176   xbt_free(area);
 177   area = NULL;
 178 }
 179
 180 /************************************************************************************/
 181
 182 static s_heap_area_t make_heap_area(int block, int fragment)
 183 {
 184   s_heap_area_t area;
 185   area.valid = 1;
 186   area.block = block;
 187   area.fragment = fragment;
 188   return area;
 189 }
 190
 191
 192 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
 193                                  int block2, int fragment2)
 194 {
 195
 196   unsigned int cursor = 0;
 197   heap_area_pair_t current_pair;
 198
 199   xbt_dynar_foreach(list, cursor, current_pair) {
 200     if (current_pair->block1 == block1 && current_pair->block2 == block2
 201         && current_pair->fragment1 == fragment1
 202         && current_pair->fragment2 == fragment2)
 203       return 0;
 204   }
 205
 206   return 1;
 207 }
 208
 209 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
 210                               int block2, int fragment2)
 211 {
 212
 213   if (is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)) {
 214     heap_area_pair_t pair = NULL;
 215     pair = xbt_new0(s_heap_area_pair_t, 1);
 216     pair->block1 = block1;
 217     pair->fragment1 = fragment1;
 218     pair->block2 = block2;
 219     pair->fragment2 = fragment2;
 220
 221     xbt_dynar_push(list, &pair);
 222
 223     return 1;
 224   }
 225
 226   return 0;
 227 }
 228
 229 static ssize_t heap_comparison_ignore_size(xbt_dynar_t ignore_list,
 230                                            void *address)
 231 {
 232
 233   unsigned int cursor = 0;
 234   int start = 0;
 235   int end = xbt_dynar_length(ignore_list) - 1;
 236   mc_heap_ignore_region_t region;
 237
 238   while (start <= end) {
 239     cursor = (start + end) / 2;
 240     region =
 241         (mc_heap_ignore_region_t) xbt_dynar_get_as(ignore_list, cursor,
 242                                                    mc_heap_ignore_region_t);
 243     if (region->address == address)
 244       return region->size;
 245     if (region->address < address)
 246       start = cursor + 1;
 247     if (region->address > address)
 248       end = cursor - 1;
 249   }
 250
 251   return -1;
 252 }
 253
 254 static int is_stack(void *address)
 255 {
 256   unsigned int cursor = 0;
 257   stack_region_t stack;
 258
 259   xbt_dynar_foreach(stacks_areas, cursor, stack) {
 260     if (address == stack->address)
 261       return 1;
 262   }
 263
 264   return 0;
 265 }
 266
 267 // TODO, this should depend on the snapshot?
 268 static int is_block_stack(int block)
 269 {
 270   unsigned int cursor = 0;
 271   stack_region_t stack;
 272
 273   xbt_dynar_foreach(stacks_areas, cursor, stack) {
 274     if (block == stack->block)
 275       return 1;
 276   }
 277
 278   return 0;
 279 }
 280
 281 static void match_equals(struct s_mc_diff *state, xbt_dynar_t list)
 282 {
 283
 284   unsigned int cursor = 0;
 285   heap_area_pair_t current_pair;
 286
 287   xbt_dynar_foreach(list, cursor, current_pair) {
 288
 289     if (current_pair->fragment1 != -1) {
 290
 291       state->equals_to1_(current_pair->block1, current_pair->fragment1) =
 292           make_heap_area(current_pair->block2, current_pair->fragment2);
 293       state->equals_to2_(current_pair->block2, current_pair->fragment2) =
 294           make_heap_area(current_pair->block1, current_pair->fragment1);
 295
 296     } else {
 297
 298       state->equals_to1_(current_pair->block1, 0) =
 299           make_heap_area(current_pair->block2, current_pair->fragment2);
 300       state->equals_to2_(current_pair->block2, 0) =
 301           make_heap_area(current_pair->block1, current_pair->fragment1);
 302
 303     }
 304
 305   }
 306 }
 307
 308 /** Check whether two blocks are known to be matching
 309  *
 310  *  @param state  State used
 311  *  @param b1     Block of state 1
 312  *  @param b2     Block of state 2
 313  *  @return       if the blocks are known to be matching
 314  */
 315 static int equal_blocks(struct s_mc_diff *state, int b1, int b2)
 316 {
 317
 318   if (state->equals_to1_(b1, 0).block == b2
 319       && state->equals_to2_(b2, 0).block == b1)
 320     return 1;
 321
 322   return 0;
 323 }
 324
 325 /** Check whether two fragments are known to be matching
 326  *
 327  *  @param state  State used
 328  *  @param b1     Block of state 1
 329  *  @param f1     Fragment of state 1
 330  *  @param b2     Block of state 2
 331  *  @param f2     Fragment of state 2
 332  *  @return       if the fragments are known to be matching
 333  */
 334 static int equal_fragments(struct s_mc_diff *state, int b1, int f1, int b2,
 335                            int f2)
 336 {
 337
 338   if (state->equals_to1_(b1, f1).block == b2
 339       && state->equals_to1_(b1, f1).fragment == f2
 340       && state->equals_to2_(b2, f2).block == b1
 341       && state->equals_to2_(b2, f2).fragment == f1)
 342     return 1;
 343
 344   return 0;
 345 }
 346
 347 int init_heap_information(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t i1,
 348                           xbt_dynar_t i2)
 349 {
 350   if (mc_diff_info == NULL) {
 351     mc_diff_info = xbt_new0(struct s_mc_diff, 1);
 352     mc_diff_info->equals_to1 = NULL;
 353     mc_diff_info->equals_to2 = NULL;
 354     mc_diff_info->types1 = NULL;
 355     mc_diff_info->types2 = NULL;
 356   }
 357   struct s_mc_diff *state = mc_diff_info;
 358
 359   if ((((struct mdesc *) heap1)->heaplimit !=
 360        ((struct mdesc *) heap2)->heaplimit)
 361       ||
 362       ((((struct mdesc *) heap1)->heapsize !=
 363         ((struct mdesc *) heap2)->heapsize)))
 364     return -1;
 365
 366   state->heaplimit = ((struct mdesc *) heap1)->heaplimit;
 367
 368   // Mamailloute in order to find the base address of the main heap:
 369   state->s_heap =
 370       (char *) mmalloc_get_current_heap() - STD_HEAP_SIZE - xbt_pagesize;
 371
 372   state->heapsize1 = heap1->heapsize;
 373   state->heapsize2 = heap2->heapsize;
 374
 375   state->to_ignore1 = i1;
 376   state->to_ignore2 = i2;
 377
 378   if (state->heaplimit > state->available) {
 379     state->equals_to1 =
 380         realloc(state->equals_to1,
 381                 state->heaplimit * MAX_FRAGMENT_PER_BLOCK *
 382                 sizeof(s_heap_area_t));
 383     state->types1 =
 384         realloc(state->types1,
 385                 state->heaplimit * MAX_FRAGMENT_PER_BLOCK *
 386                 sizeof(type_name *));
 387     state->equals_to2 =
 388         realloc(state->equals_to2,
 389                 state->heaplimit * MAX_FRAGMENT_PER_BLOCK *
 390                 sizeof(s_heap_area_t));
 391     state->types2 =
 392         realloc(state->types2,
 393                 state->heaplimit * MAX_FRAGMENT_PER_BLOCK *
 394                 sizeof(type_name *));
 395     state->available = state->heaplimit;
 396   }
 397
 398   memset(state->equals_to1, 0,
 399          state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 400   memset(state->equals_to2, 0,
 401          state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 402   memset(state->types1, 0,
 403          state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 404   memset(state->types2, 0,
 405          state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 406
 407   return 0;
 408
 409 }
 410
 411 void reset_heap_information()
 412 {
 413
 414 }
 415
 416 int mmalloc_compare_heap(mc_snapshot_t snapshot1, mc_snapshot_t snapshot2)
 417 {
 418
 419   struct s_mc_diff *state = mc_diff_info;
 420
 421   /* Start comparison */
 422   size_t i1, i2, j1, j2, k;
 423   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 424   int nb_diff1 = 0, nb_diff2 = 0;
 425
 426   int equal, res_compare = 0;
 427
 428   /* Check busy blocks */
 429
 430   i1 = 1;
 431
 432   malloc_info heapinfo_temp1, heapinfo_temp2;
 433   malloc_info heapinfo_temp2b;
 434
 435   mc_mem_region_t heap_region1 = snapshot1->regions[0];
 436   mc_mem_region_t heap_region2 = snapshot2->regions[0];
 437
 438   // This is in snapshot do not use them directly:
 439   malloc_info* heapinfos1 = mc_snapshot_read_pointer(&std_heap->heapinfo, snapshot1, MC_NO_PROCESS_INDEX);
 440   malloc_info* heapinfos2 = mc_snapshot_read_pointer(&std_heap->heapinfo, snapshot2, MC_NO_PROCESS_INDEX);
 441
 442   while (i1 <= state->heaplimit) {
 443
 444     malloc_info* heapinfo1 = mc_snapshot_read_region(&heapinfos1[i1], heap_region1, &heapinfo_temp1, sizeof(malloc_info));
 445     malloc_info* heapinfo2 = mc_snapshot_read_region(&heapinfos2[i1], heap_region2, &heapinfo_temp2, sizeof(malloc_info));
 446
 447     if (heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type == MMALLOC_TYPE_HEAPINFO) {      /* Free block */
 448       i1 ++;
 449       continue;
 450     }
 451
 452     if (heapinfo1->type < 0) {
 453       fprintf(stderr, "Unkown mmalloc block type.\n");
 454       abort();
 455     }
 456
 457     addr_block1 =
 458         ((void *) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE +
 459                    (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
 460
 461     if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED) {       /* Large block */
 462
 463       if (is_stack(addr_block1)) {
 464         for (k = 0; k < heapinfo1->busy_block.size; k++)
 465           state->equals_to1_(i1 + k, 0) = make_heap_area(i1, -1);
 466         for (k = 0; k < heapinfo2->busy_block.size; k++)
 467           state->equals_to2_(i1 + k, 0) = make_heap_area(i1, -1);
 468         i1 += heapinfo1->busy_block.size;
 469         continue;
 470       }
 471
 472       if (state->equals_to1_(i1, 0).valid) {
 473         i1++;
 474         continue;
 475       }
 476
 477       i2 = 1;
 478       equal = 0;
 479       res_compare = 0;
 480
 481       /* Try first to associate to same block in the other heap */
 482       if (heapinfo2->type == heapinfo1->type) {
 483
 484         if (state->equals_to2_(i1, 0).valid == 0) {
 485
 486           addr_block2 =
 487               ((void *) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE +
 488                          (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
 489
 490           res_compare =
 491               compare_heap_area(MC_NO_PROCESS_INDEX, addr_block1, addr_block2, snapshot1, snapshot2,
 492                                 NULL, NULL, 0);
 493
 494           if (res_compare != 1) {
 495             for (k = 1; k < heapinfo2->busy_block.size; k++)
 496               state->equals_to2_(i1 + k, 0) = make_heap_area(i1, -1);
 497             for (k = 1; k < heapinfo1->busy_block.size; k++)
 498               state->equals_to1_(i1 + k, 0) = make_heap_area(i1, -1);
 499             equal = 1;
 500             i1 += heapinfo1->busy_block.size;
 501           }
 502
 503         }
 504
 505       }
 506
 507       while (i2 <= state->heaplimit && !equal) {
 508
 509         addr_block2 =
 510             ((void *) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE +
 511                        (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
 512
 513         if (i2 == i1) {
 514           i2++;
 515           continue;
 516         }
 517
 518         malloc_info* heapinfo2b = mc_snapshot_read_region(&heapinfos2[i2], heap_region2, &heapinfo_temp2b, sizeof(malloc_info));
 519
 520         if (heapinfo2b->type != MMALLOC_TYPE_UNFRAGMENTED) {
 521           i2++;
 522           continue;
 523         }
 524
 525         if (state->equals_to2_(i2, 0).valid) {
 526           i2++;
 527           continue;
 528         }
 529
 530         res_compare =
 531             compare_heap_area(MC_NO_PROCESS_INDEX, addr_block1, addr_block2, snapshot1, snapshot2,
 532                               NULL, NULL, 0);
 533
 534         if (res_compare != 1) {
 535           for (k = 1; k < heapinfo2b->busy_block.size; k++)
 536             state->equals_to2_(i2 + k, 0) = make_heap_area(i1, -1);
 537           for (k = 1; k < heapinfo1->busy_block.size; k++)
 538             state->equals_to1_(i1 + k, 0) = make_heap_area(i2, -1);
 539           equal = 1;
 540           i1 += heapinfo1->busy_block.size;
 541         }
 542
 543         i2++;
 544
 545       }
 546
 547       if (!equal) {
 548         XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1,
 549                   heapinfo1->busy_block.busy_size, addr_block1);
 550         i1 = state->heaplimit + 1;
 551         nb_diff1++;
 552         //i1++;
 553       }
 554
 555     } else {                    /* Fragmented block */
 556
 557       for (j1 = 0; j1 < (size_t) (BLOCKSIZE >> heapinfo1->type); j1++) {
 558
 559         if (heapinfo1->busy_frag.frag_size[j1] == -1) /* Free fragment */
 560           continue;
 561
 562         if (state->equals_to1_(i1, j1).valid)
 563           continue;
 564
 565         addr_frag1 =
 566             (void *) ((char *) addr_block1 + (j1 << heapinfo1->type));
 567
 568         i2 = 1;
 569         equal = 0;
 570
 571         /* Try first to associate to same fragment in the other heap */
 572         if (heapinfo2->type == heapinfo1->type) {
 573
 574           if (state->equals_to2_(i1, j1).valid == 0) {
 575
 576             addr_block2 =
 577                 ((void *) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE +
 578                            (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
 579             addr_frag2 =
 580                 (void *) ((char *) addr_block2 +
 581                           (j1 << heapinfo2->type));
 582
 583             res_compare =
 584                 compare_heap_area(MC_NO_PROCESS_INDEX, addr_frag1, addr_frag2, snapshot1, snapshot2,
 585                                   NULL, NULL, 0);
 586
 587             if (res_compare != 1)
 588               equal = 1;
 589
 590           }
 591
 592         }
 593
 594         while (i2 <= state->heaplimit && !equal) {
 595
 596           malloc_info* heapinfo2b = mc_snapshot_read_region(&heapinfos2[i2], heap_region2, &heapinfo_temp2b, sizeof(malloc_info));
 597
 598           if (heapinfo2b->type == MMALLOC_TYPE_FREE || heapinfo2b->type == MMALLOC_TYPE_HEAPINFO) {
 599             i2 ++;
 600             continue;
 601           }
 602
 603           // We currently do not match fragments with unfragmented blocks (maybe we should).
 604           if (heapinfo2b->type == MMALLOC_TYPE_UNFRAGMENTED) {
 605             i2++;
 606             continue;
 607           }
 608
 609           if (heapinfo2b->type < 0) {
 610             fprintf(stderr, "Unkown mmalloc block type.\n");
 611             abort();
 612           }
 613
 614           for (j2 = 0; j2 < (size_t) (BLOCKSIZE >> heapinfo2b->type);
 615                j2++) {
 616
 617             if (i2 == i1 && j2 == j1)
 618               continue;
 619
 620             if (state->equals_to2_(i2, j2).valid)
 621               continue;
 622
 623             addr_block2 =
 624                 ((void *) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE +
 625                            (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
 626             addr_frag2 =
 627                 (void *) ((char *) addr_block2 +
 628                           (j2 << heapinfo2b->type));
 629
 630             res_compare =
 631                 compare_heap_area(MC_NO_PROCESS_INDEX, addr_frag1, addr_frag2, snapshot2, snapshot2,
 632                                   NULL, NULL, 0);
 633
 634             if (res_compare != 1) {
 635               equal = 1;
 636               break;
 637             }
 638
 639           }
 640
 641           i2++;
 642
 643         }
 644
 645         if (!equal) {
 646           XBT_DEBUG
 647               ("Block %zu, fragment %zu not found (size_used = %zd, address = %p)\n",
 648                i1, j1, heapinfo1->busy_frag.frag_size[j1],
 649                addr_frag1);
 650           i2 = state->heaplimit + 1;
 651           i1 = state->heaplimit + 1;
 652           nb_diff1++;
 653           break;
 654         }
 655
 656       }
 657
 658       i1++;
 659
 660     }
 661
 662   }
 663
 664   /* All blocks/fragments are equal to another block/fragment ? */
 665   size_t i = 1, j = 0;
 666
 667   for(i = 1; i <= state->heaplimit; i++) {
 668     malloc_info* heapinfo1 = mc_snapshot_read_region(&heapinfos1[i], heap_region1, &heapinfo_temp1, sizeof(malloc_info));
 669     if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED) {
 670       if (i1 == state->heaplimit) {
 671         if (heapinfo1->busy_block.busy_size > 0) {
 672           if (state->equals_to1_(i, 0).valid == 0) {
 673             if (XBT_LOG_ISENABLED(mc_diff, xbt_log_priority_debug)) {
 674               // TODO, add address
 675               XBT_DEBUG("Block %zu not found (size used = %zu)", i,
 676                         heapinfo1->busy_block.busy_size);
 677               //mmalloc_backtrace_block_display((void*)heapinfo1, i);
 678             }
 679             nb_diff1++;
 680           }
 681         }
 682       }
 683     }
 684     if (heapinfo1->type > 0) {
 685       for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo1->type); j++) {
 686         if (i1 == state->heaplimit) {
 687           if (heapinfo1->busy_frag.frag_size[j] > 0) {
 688             if (state->equals_to1_(i, j).valid == 0) {
 689               if (XBT_LOG_ISENABLED(mc_diff, xbt_log_priority_debug)) {
 690                 // TODO, print fragment address
 691                 XBT_DEBUG
 692                     ("Block %zu, Fragment %zu not found (size used = %zd)",
 693                      i, j,
 694                      heapinfo1->busy_frag.frag_size[j]);
 695                 //mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j);
 696               }
 697               nb_diff1++;
 698             }
 699           }
 700         }
 701       }
 702     }
 703   }
 704
 705   if (i1 == state->heaplimit)
 706     XBT_DEBUG("Number of blocks/fragments not found in heap1 : %d", nb_diff1);
 707
 708   for (i=1; i <= state->heaplimit; i++) {
 709     malloc_info* heapinfo2 = mc_snapshot_read_region(&heapinfos2[i], heap_region2, &heapinfo_temp2, sizeof(malloc_info));
 710     if (heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) {
 711       if (i1 == state->heaplimit) {
 712         if (heapinfo2->busy_block.busy_size > 0) {
 713           if (state->equals_to2_(i, 0).valid == 0) {
 714             if (XBT_LOG_ISENABLED(mc_diff, xbt_log_priority_debug)) {
 715               // TODO, print address of the block
 716               XBT_DEBUG("Block %zu not found (size used = %zu)", i,
 717                         heapinfo2->busy_block.busy_size);
 718               //mmalloc_backtrace_block_display((void*)heapinfo2, i);
 719             }
 720             nb_diff2++;
 721           }
 722         }
 723       }
 724     }
 725     if (heapinfo2->type > 0) {
 726       for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo2->type); j++) {
 727         if (i1 == state->heaplimit) {
 728           if (heapinfo2->busy_frag.frag_size[j] > 0) {
 729             if (state->equals_to2_(i, j).valid == 0) {
 730               if (XBT_LOG_ISENABLED(mc_diff, xbt_log_priority_debug)) {
 731                 // TODO, print address of the block
 732                 XBT_DEBUG
 733                     ("Block %zu, Fragment %zu not found (size used = %zd)",
 734                      i, j,
 735                      heapinfo2->busy_frag.frag_size[j]);
 736                 //mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j);
 737               }
 738               nb_diff2++;
 739             }
 740           }
 741         }
 742       }
 743     }
 744   }
 745
 746   if (i1 == state->heaplimit)
 747     XBT_DEBUG("Number of blocks/fragments not found in heap2 : %d", nb_diff2);
 748
 749   return ((nb_diff1 > 0) || (nb_diff2 > 0));
 750 }
 751
 752 /**
 753  *
 754  * @param state
 755  * @param real_area1     Process address for state 1
 756  * @param real_area2     Process address for state 2
 757  * @param snapshot1      Snapshot of state 1
 758  * @param snapshot2      Snapshot of state 2
 759  * @param previous
 760  * @param size
 761  * @param check_ignore
 762  */
 763 static int compare_heap_area_without_type(struct s_mc_diff *state, int process_index,
 764                                           void *real_area1, void *real_area2,
 765                                           mc_snapshot_t snapshot1,
 766                                           mc_snapshot_t snapshot2,
 767                                           xbt_dynar_t previous, int size,
 768                                           int check_ignore)
 769 {
 770
 771   int i = 0;
 772   void *addr_pointed1, *addr_pointed2;
 773   int pointer_align, res_compare;
 774   ssize_t ignore1, ignore2;
 775
 776   mc_mem_region_t heap_region1 = snapshot1->regions[0];
 777   mc_mem_region_t heap_region2 = snapshot2->regions[0];
 778
 779   while (i < size) {
 780
 781     if (check_ignore > 0) {
 782       if ((ignore1 =
 783            heap_comparison_ignore_size(state->to_ignore1,
 784                                        (char *) real_area1 + i)) != -1) {
 785         if ((ignore2 =
 786              heap_comparison_ignore_size(state->to_ignore2,
 787                                          (char *) real_area2 + i)) == ignore1) {
 788           if (ignore1 == 0) {
 789             check_ignore--;
 790             return 0;
 791           } else {
 792             i = i + ignore2;
 793             check_ignore--;
 794             continue;
 795           }
 796         }
 797       }
 798     }
 799
 800     if (mc_snapshot_region_memcmp(((char *) real_area1) + i, heap_region1, ((char *) real_area2) + i, heap_region2, 1) != 0) {
 801
 802       pointer_align = (i / sizeof(void *)) * sizeof(void *);
 803       addr_pointed1 = mc_snapshot_read_pointer((char *) real_area1 + pointer_align, snapshot1, process_index);
 804       addr_pointed2 = mc_snapshot_read_pointer((char *) real_area2 + pointer_align, snapshot2, process_index);
 805
 806       if (addr_pointed1 > maestro_stack_start
 807           && addr_pointed1 < maestro_stack_end
 808           && addr_pointed2 > maestro_stack_start
 809           && addr_pointed2 < maestro_stack_end) {
 810         i = pointer_align + sizeof(void *);
 811         continue;
 812       } else if (addr_pointed1 > state->s_heap
 813                  && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
 814                  && addr_pointed2 > state->s_heap
 815                  && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) {
 816         // Both addreses are in the heap:
 817         res_compare =
 818             compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
 819                               snapshot2, previous, NULL, 0);
 820         if (res_compare == 1) {
 821           return res_compare;
 822         }
 823         i = pointer_align + sizeof(void *);
 824         continue;
 825       } else {
 826         return 1;
 827       }
 828
 829     }
 830
 831     i++;
 832
 833   }
 834
 835   return 0;
 836
 837 }
 838
 839 /**
 840  *
 841  * @param state
 842  * @param real_area1     Process address for state 1
 843  * @param real_area2     Process address for state 2
 844  * @param snapshot1      Snapshot of state 1
 845  * @param snapshot2      Snapshot of state 2
 846  * @param previous
 847  * @param type_id
 848  * @param area_size      either a byte_size or an elements_count (?)
 849  * @param check_ignore
 850  * @param pointer_level
 851  * @return               0 (same), 1 (different), -1 (unknown)
 852  */
 853 static int compare_heap_area_with_type(struct s_mc_diff *state, int process_index,
 854                                        void *real_area1, void *real_area2,
 855                                        mc_snapshot_t snapshot1,
 856                                        mc_snapshot_t snapshot2,
 857                                        xbt_dynar_t previous, dw_type_t type,
 858                                        int area_size, int check_ignore,
 859                                        int pointer_level)
 860 {
 861 top:
 862   if (is_stack(real_area1) && is_stack(real_area2))
 863     return 0;
 864
 865   ssize_t ignore1, ignore2;
 866
 867   if ((check_ignore > 0)
 868       && ((ignore1 = heap_comparison_ignore_size(state->to_ignore1, real_area1))
 869           > 0)
 870       && ((ignore2 = heap_comparison_ignore_size(state->to_ignore2, real_area2))
 871           == ignore1)) {
 872     return 0;
 873   }
 874
 875   dw_type_t subtype, subsubtype;
 876   int res, elm_size, i;
 877   unsigned int cursor = 0;
 878   dw_type_t member;
 879   void *addr_pointed1, *addr_pointed2;;
 880
 881   mc_mem_region_t heap_region1 = snapshot1->regions[0];
 882   mc_mem_region_t heap_region2 = snapshot2->regions[0];
 883
 884   switch (type->type) {
 885   case DW_TAG_unspecified_type:
 886     return 1;
 887
 888   case DW_TAG_base_type:
 889     if (type->name != NULL && strcmp(type->name, "char") == 0) {        /* String, hence random (arbitrary ?) size */
 890       if (real_area1 == real_area2)
 891         return -1;
 892       else
 893         return (mc_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, area_size) != 0);
 894     } else {
 895       if (area_size != -1 && type->byte_size != area_size)
 896         return -1;
 897       else {
 898         return (mc_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0);
 899       }
 900     }
 901     break;
 902   case DW_TAG_enumeration_type:
 903     if (area_size != -1 && type->byte_size != area_size)
 904       return -1;
 905     else
 906       return (mc_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0);
 907     break;
 908   case DW_TAG_typedef:
 909   case DW_TAG_const_type:
 910   case DW_TAG_volatile_type:
 911     // Poor man's TCO:
 912     type = type->subtype;
 913     goto top;
 914     break;
 915   case DW_TAG_array_type:
 916     subtype = type->subtype;
 917     switch (subtype->type) {
 918     case DW_TAG_unspecified_type:
 919       return 1;
 920
 921     case DW_TAG_base_type:
 922     case DW_TAG_enumeration_type:
 923     case DW_TAG_pointer_type:
 924     case DW_TAG_reference_type:
 925     case DW_TAG_rvalue_reference_type:
 926     case DW_TAG_structure_type:
 927     case DW_TAG_class_type:
 928     case DW_TAG_union_type:
 929       if (subtype->full_type)
 930         subtype = subtype->full_type;
 931       elm_size = subtype->byte_size;
 932       break;
 933       // TODO, just remove the type indirection?
 934     case DW_TAG_const_type:
 935     case DW_TAG_typedef:
 936     case DW_TAG_volatile_type:
 937       subsubtype = subtype->subtype;
 938       if (subsubtype->full_type)
 939         subsubtype = subsubtype->full_type;
 940       elm_size = subsubtype->byte_size;
 941       break;
 942     default:
 943       return 0;
 944       break;
 945     }
 946     for (i = 0; i < type->element_count; i++) {
 947       // TODO, add support for variable stride (DW_AT_byte_stride)
 948       res =
 949           compare_heap_area_with_type(state, process_index,
 950                                       (char *) real_area1 + (i * elm_size),
 951                                       (char *) real_area2 + (i * elm_size),
 952                                       snapshot1, snapshot2, previous,
 953                                       type->subtype, subtype->byte_size,
 954                                       check_ignore, pointer_level);
 955       if (res == 1)
 956         return res;
 957     }
 958     break;
 959   case DW_TAG_reference_type:
 960   case DW_TAG_rvalue_reference_type:
 961   case DW_TAG_pointer_type:
 962     if (type->subtype && type->subtype->type == DW_TAG_subroutine_type) {
 963       addr_pointed1 = mc_snapshot_read_pointer(real_area1, snapshot1, process_index);
 964       addr_pointed2 = mc_snapshot_read_pointer(real_area2, snapshot2, process_index);
 965       return (addr_pointed1 != addr_pointed2);;
 966     } else {
 967       pointer_level++;
 968       if (pointer_level > 1) {  /* Array of pointers */
 969         for (i = 0; i < (area_size / sizeof(void *)); i++) {
 970           addr_pointed1 = mc_snapshot_read_pointer((char*) real_area1 + i * sizeof(void *), snapshot1, process_index);
 971           addr_pointed2 = mc_snapshot_read_pointer((char*) real_area2 + i * sizeof(void *), snapshot2, process_index);
 972           if (addr_pointed1 > state->s_heap
 973               && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
 974               && addr_pointed2 > state->s_heap
 975               && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))
 976             res =
 977                 compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
 978                                   snapshot2, previous, type->subtype,
 979                                   pointer_level);
 980           else
 981             res = (addr_pointed1 != addr_pointed2);
 982           if (res == 1)
 983             return res;
 984         }
 985       } else {
 986         addr_pointed1 = mc_snapshot_read_pointer(real_area1, snapshot1, process_index);
 987         addr_pointed2 = mc_snapshot_read_pointer(real_area2, snapshot2, process_index);
 988         if (addr_pointed1 > state->s_heap
 989             && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
 990             && addr_pointed2 > state->s_heap
 991             && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))
 992           return compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
 993                                    snapshot2, previous, type->subtype,
 994                                    pointer_level);
 995         else
 996           return (addr_pointed1 != addr_pointed2);
 997       }
 998     }
 999     break;
1000   case DW_TAG_structure_type:
1001   case DW_TAG_class_type:
1002     if (type->full_type)
1003       type = type->full_type;
1004     if (area_size != -1 && type->byte_size != area_size) {
1005       if (area_size > type->byte_size && area_size % type->byte_size == 0) {
1006         for (i = 0; i < (area_size / type->byte_size); i++) {
1007           res =
1008               compare_heap_area_with_type(state, process_index,
1009                                           (char *) real_area1 + i * type->byte_size,
1010                                           (char *) real_area2 + i * type->byte_size,
1011                                           snapshot1, snapshot2, previous, type, -1,
1012                                           check_ignore, 0);
1013           if (res == 1)
1014             return res;
1015         }
1016       } else {
1017         return -1;
1018       }
1019     } else {
1020       cursor = 0;
1021       xbt_dynar_foreach(type->members, cursor, member) {
1022         // TODO, optimize this? (for the offset case)
1023         char *real_member1 =
1024             mc_member_resolve(real_area1, type, member, snapshot1, process_index);
1025         char *real_member2 =
1026             mc_member_resolve(real_area2, type, member, snapshot2, process_index);
1027         res =
1028             compare_heap_area_with_type(state, process_index, real_member1, real_member2,
1029                                         snapshot1, snapshot2,
1030                                         previous, member->subtype, -1,
1031                                         check_ignore, 0);
1032         if (res == 1) {
1033           return res;
1034         }
1035       }
1036     }
1037     break;
1038   case DW_TAG_union_type:
1039     return compare_heap_area_without_type(state, process_index, real_area1, real_area2,
1040                                           snapshot1, snapshot2, previous,
1041                                           type->byte_size, check_ignore);
1042     break;
1043   default:
1044     break;
1045   }
1046
1047   return 0;
1048
1049 }
1050
1051 /** Infer the type of a part of the block from the type of the block
1052  *
1053  * TODO, handle DW_TAG_array_type as well as arrays of the object ((*p)[5], p[5])
1054  *
1055  * TODO, handle subfields ((*p).bar.foo, (*p)[5].bar…)
1056  *
1057  * @param  type_id            DWARF type ID of the root address
1058  * @param  area_size
1059  * @return                    DWARF type ID for given offset
1060  */
1061 static dw_type_t get_offset_type(void *real_base_address, dw_type_t type,
1062                                  int offset, int area_size,
1063                                  mc_snapshot_t snapshot, int process_index)
1064 {
1065
1066   // Beginning of the block, the infered variable type if the type of the block:
1067   if (offset == 0)
1068     return type;
1069
1070   switch (type->type) {
1071   case DW_TAG_structure_type:
1072   case DW_TAG_class_type:
1073     if (type->full_type)
1074       type = type->full_type;
1075
1076     if (area_size != -1 && type->byte_size != area_size) {
1077       if (area_size > type->byte_size && area_size % type->byte_size == 0)
1078         return type;
1079       else
1080         return NULL;
1081     } else {
1082       unsigned int cursor = 0;
1083       dw_type_t member;
1084       xbt_dynar_foreach(type->members, cursor, member) {
1085
1086         if (!member->location.size) {
1087           // We have the offset, use it directly (shortcut):
1088           if (member->offset == offset)
1089             return member->subtype;
1090         } else {
1091           char *real_member =
1092               mc_member_resolve(real_base_address, type, member, snapshot, process_index);
1093           if (real_member - (char *) real_base_address == offset)
1094             return member->subtype;
1095         }
1096
1097       }
1098       return NULL;
1099     }
1100     break;
1101   default:
1102     /* FIXME : other cases ? */
1103     return NULL;
1104     break;
1105   }
1106 }
1107
1108 /**
1109  *
1110  * @param area1          Process address for state 1
1111  * @param area2          Process address for state 2
1112  * @param snapshot1      Snapshot of state 1
1113  * @param snapshot2      Snapshot of state 2
1114  * @param previous       Pairs of blocks already compared on the current path (or NULL)
1115  * @param type_id        Type of variable
1116  * @param pointer_level
1117  * @return 0 (same), 1 (different), -1
1118  */
1119 int compare_heap_area(int process_index, void *area1, void *area2, mc_snapshot_t snapshot1,
1120                       mc_snapshot_t snapshot2, xbt_dynar_t previous,
1121                       dw_type_t type, int pointer_level)
1122 {
1123
1124   struct s_mc_diff *state = mc_diff_info;
1125
1126   int res_compare;
1127   ssize_t block1, frag1, block2, frag2;
1128   ssize_t size;
1129   int check_ignore = 0;
1130
1131   void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2;
1132   int type_size = -1;
1133   int offset1 = 0, offset2 = 0;
1134   int new_size1 = -1, new_size2 = -1;
1135   dw_type_t new_type1 = NULL, new_type2 = NULL;
1136
1137   int match_pairs = 0;
1138
1139   malloc_info* heapinfos1 = mc_snapshot_read_pointer(&std_heap->heapinfo, snapshot1, process_index);
1140   malloc_info* heapinfos2 = mc_snapshot_read_pointer(&std_heap->heapinfo, snapshot2, process_index);
1141
1142   malloc_info heapinfo_temp1, heapinfo_temp2;
1143
1144   if (previous == NULL) {
1145     previous =
1146         xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
1147     match_pairs = 1;
1148   }
1149   // Get block number:
1150   block1 =
1151       ((char *) area1 -
1152        (char *) ((xbt_mheap_t) state->s_heap)->heapbase) / BLOCKSIZE + 1;
1153   block2 =
1154       ((char *) area2 -
1155        (char *) ((xbt_mheap_t) state->s_heap)->heapbase) / BLOCKSIZE + 1;
1156
1157   // If either block is a stack block:
1158   if (is_block_stack((int) block1) && is_block_stack((int) block2)) {
1159     add_heap_area_pair(previous, block1, -1, block2, -1);
1160     if (match_pairs) {
1161       match_equals(state, previous);
1162       xbt_dynar_free(&previous);
1163     }
1164     return 0;
1165   }
1166   // If either block is not in the expected area of memory:
1167   if (((char *) area1 < (char *) ((xbt_mheap_t) state->s_heap)->heapbase)
1168       || (block1 > state->heapsize1) || (block1 < 1)
1169       || ((char *) area2 < (char *) ((xbt_mheap_t) state->s_heap)->heapbase)
1170       || (block2 > state->heapsize2) || (block2 < 1)) {
1171     if (match_pairs) {
1172       xbt_dynar_free(&previous);
1173     }
1174     return 1;
1175   }
1176
1177   // Process address of the block:
1178   real_addr_block1 =
1179       ((void *) (((ADDR2UINT(block1)) - 1) * BLOCKSIZE +
1180                  (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
1181   real_addr_block2 =
1182       ((void *) (((ADDR2UINT(block2)) - 1) * BLOCKSIZE +
1183                  (char *) ((xbt_mheap_t) state->s_heap)->heapbase));
1184
1185   if (type) {
1186
1187     if (type->full_type)
1188       type = type->full_type;
1189
1190     // This assume that for "boring" types (volatile ...) byte_size is absent:
1191     while (type->byte_size == 0 && type->subtype != NULL)
1192       type = type->subtype;
1193
1194     // Find type_size:
1195     if ((type->type == DW_TAG_pointer_type)
1196         || ((type->type == DW_TAG_base_type) && type->name != NULL
1197             && (!strcmp(type->name, "char"))))
1198       type_size = -1;
1199     else
1200       type_size = type->byte_size;
1201
1202   }
1203
1204   mc_mem_region_t heap_region1 = snapshot1->regions[0];
1205   mc_mem_region_t heap_region2 = snapshot2->regions[0];
1206
1207   malloc_info* heapinfo1 = mc_snapshot_read_region(&heapinfos1[block1], heap_region1, &heapinfo_temp1, sizeof(malloc_info));
1208   malloc_info* heapinfo2 = mc_snapshot_read_region(&heapinfos2[block2], heap_region2, &heapinfo_temp2, sizeof(malloc_info));
1209
1210   if ((heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type==MMALLOC_TYPE_HEAPINFO)
1211     && (heapinfo2->type == MMALLOC_TYPE_FREE || heapinfo2->type ==MMALLOC_TYPE_HEAPINFO)) {
1212
1213     /* Free block */
1214     if (match_pairs) {
1215       match_equals(state, previous);
1216       xbt_dynar_free(&previous);
1217     }
1218     return 0;
1219
1220   } else if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED
1221     && heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) {
1222     /* Complete block */
1223
1224     // TODO, lookup variable type from block type as done for fragmented blocks
1225
1226     offset1 = (char *) area1 - (char *) real_addr_block1;
1227     offset2 = (char *) area2 - (char *) real_addr_block2;
1228
1229     if (state->equals_to1_(block1, 0).valid
1230         && state->equals_to2_(block2, 0).valid) {
1231       if (equal_blocks(state, block1, block2)) {
1232         if (match_pairs) {
1233           match_equals(state, previous);
1234           xbt_dynar_free(&previous);
1235         }
1236         return 0;
1237       }
1238     }
1239
1240     if (type_size != -1) {
1241       if (type_size != heapinfo1->busy_block.busy_size
1242           && type_size != heapinfo2->busy_block.busy_size
1243           && (type->name == NULL || !strcmp(type->name, "struct s_smx_context"))) {
1244         if (match_pairs) {
1245           match_equals(state, previous);
1246           xbt_dynar_free(&previous);
1247         }
1248         return -1;
1249       }
1250     }
1251
1252     if (heapinfo1->busy_block.size !=
1253         heapinfo2->busy_block.size) {
1254       if (match_pairs) {
1255         xbt_dynar_free(&previous);
1256       }
1257       return 1;
1258     }
1259
1260     if (heapinfo1->busy_block.busy_size !=
1261         heapinfo2->busy_block.busy_size) {
1262       if (match_pairs) {
1263         xbt_dynar_free(&previous);
1264       }
1265       return 1;
1266     }
1267
1268     if (!add_heap_area_pair(previous, block1, -1, block2, -1)) {
1269       if (match_pairs) {
1270         match_equals(state, previous);
1271         xbt_dynar_free(&previous);
1272       }
1273       return 0;
1274     }
1275
1276     size = heapinfo1->busy_block.busy_size;
1277
1278     // Remember (basic) type inference.
1279     // The current data structure only allows us to do this for the whole block.
1280     if (type != NULL && area1 == real_addr_block1) {
1281       state->types1_(block1, 0) = type;
1282     }
1283     if (type != NULL && area2 == real_addr_block2) {
1284       state->types2_(block2, 0) = type;
1285     }
1286
1287     if (size <= 0) {
1288       if (match_pairs) {
1289         match_equals(state, previous);
1290         xbt_dynar_free(&previous);
1291       }
1292       return 0;
1293     }
1294
1295     frag1 = -1;
1296     frag2 = -1;
1297
1298     if ((heapinfo1->busy_block.ignore > 0)
1299         && (heapinfo2->busy_block.ignore ==
1300             heapinfo1->busy_block.ignore))
1301       check_ignore = heapinfo1->busy_block.ignore;
1302
1303   } else if ((heapinfo1->type > 0) && (heapinfo2->type > 0)) {      /* Fragmented block */
1304
1305     // Fragment number:
1306     frag1 =
1307         ((uintptr_t) (ADDR2UINT(area1) % (BLOCKSIZE))) >> heapinfo1->type;
1308     frag2 =
1309         ((uintptr_t) (ADDR2UINT(area2) % (BLOCKSIZE))) >> heapinfo2->type;
1310
1311     // Process address of the fragment:
1312     real_addr_frag1 =
1313         (void *) ((char *) real_addr_block1 +
1314                   (frag1 << heapinfo1->type));
1315     real_addr_frag2 =
1316         (void *) ((char *) real_addr_block2 +
1317                   (frag2 << heapinfo2->type));
1318
1319     // Check the size of the fragments against the size of the type:
1320     if (type_size != -1) {
1321       if (heapinfo1->busy_frag.frag_size[frag1] == -1
1322           || heapinfo2->busy_frag.frag_size[frag2] == -1) {
1323         if (match_pairs) {
1324           match_equals(state, previous);
1325           xbt_dynar_free(&previous);
1326         }
1327         return -1;
1328       }
1329       // ?
1330       if (type_size != heapinfo1->busy_frag.frag_size[frag1]
1331           || type_size != heapinfo2->busy_frag.frag_size[frag2]) {
1332         if (match_pairs) {
1333           match_equals(state, previous);
1334           xbt_dynar_free(&previous);
1335         }
1336         return -1;
1337       }
1338     }
1339
1340     // Check if the blocks are already matched together:
1341     if (state->equals_to1_(block1, frag1).valid
1342         && state->equals_to2_(block2, frag2).valid) {
1343       if (offset1==offset2 && equal_fragments(state, block1, frag1, block2, frag2)) {
1344         if (match_pairs) {
1345           match_equals(state, previous);
1346           xbt_dynar_free(&previous);
1347         }
1348         return 0;
1349       }
1350     }
1351     // Compare the size of both fragments:
1352     if (heapinfo1->busy_frag.frag_size[frag1] !=
1353         heapinfo2->busy_frag.frag_size[frag2]) {
1354       if (type_size == -1) {
1355         if (match_pairs) {
1356           match_equals(state, previous);
1357           xbt_dynar_free(&previous);
1358         }
1359         return -1;
1360       } else {
1361         if (match_pairs) {
1362           xbt_dynar_free(&previous);
1363         }
1364         return 1;
1365       }
1366     }
1367
1368     // Size of the fragment:
1369     size = heapinfo1->busy_frag.frag_size[frag1];
1370
1371     // Remember (basic) type inference.
1372     // The current data structure only allows us to do this for the whole fragment.
1373     if (type != NULL && area1 == real_addr_frag1) {
1374       state->types1_(block1, frag1) = type;
1375     }
1376     if (type != NULL && area2 == real_addr_frag2) {
1377       state->types2_(block2, frag2) = type;
1378     }
1379     // The type of the variable is already known:
1380     if (type) {
1381       new_type1 = type;
1382       new_type2 = type;
1383     }
1384     // Type inference from the block type.
1385     else if (state->types1_(block1, frag1) != NULL
1386              || state->types2_(block2, frag2) != NULL) {
1387
1388       offset1 = (char *) area1 - (char *) real_addr_frag1;
1389       offset2 = (char *) area2 - (char *) real_addr_frag2;
1390
1391       if (state->types1_(block1, frag1) != NULL
1392           && state->types2_(block2, frag2) != NULL) {
1393         new_type1 =
1394             get_offset_type(real_addr_frag1, state->types1_(block1, frag1),
1395                             offset1, size, snapshot1, process_index);
1396         new_type2 =
1397             get_offset_type(real_addr_frag2, state->types2_(block2, frag2),
1398                             offset1, size, snapshot2, process_index);
1399       } else if (state->types1_(block1, frag1) != NULL) {
1400         new_type1 =
1401             get_offset_type(real_addr_frag1, state->types1_(block1, frag1),
1402                             offset1, size, snapshot1, process_index);
1403         new_type2 =
1404             get_offset_type(real_addr_frag2, state->types1_(block1, frag1),
1405                             offset2, size, snapshot2, process_index);
1406       } else if (state->types2_(block2, frag2) != NULL) {
1407         new_type1 =
1408             get_offset_type(real_addr_frag1, state->types2_(block2, frag2),
1409                             offset1, size, snapshot1, process_index);
1410         new_type2 =
1411             get_offset_type(real_addr_frag2, state->types2_(block2, frag2),
1412                             offset2, size, snapshot2, process_index);
1413       } else {
1414         if (match_pairs) {
1415           match_equals(state, previous);
1416           xbt_dynar_free(&previous);
1417         }
1418         return -1;
1419       }
1420
1421       if (new_type1 != NULL && new_type2 != NULL && new_type1 != new_type2) {
1422
1423         type = new_type1;
1424         while (type->byte_size == 0 && type->subtype != NULL)
1425           type = type->subtype;
1426         new_size1 = type->byte_size;
1427
1428         type = new_type2;
1429         while (type->byte_size == 0 && type->subtype != NULL)
1430           type = type->subtype;
1431         new_size2 = type->byte_size;
1432
1433       } else {
1434         if (match_pairs) {
1435           match_equals(state, previous);
1436           xbt_dynar_free(&previous);
1437         }
1438         return -1;
1439       }
1440     }
1441
1442     if (new_size1 > 0 && new_size1 == new_size2) {
1443       type = new_type1;
1444       size = new_size1;
1445     }
1446
1447     if (offset1 == 0 && offset2 == 0) {
1448       if (!add_heap_area_pair(previous, block1, frag1, block2, frag2)) {
1449         if (match_pairs) {
1450           match_equals(state, previous);
1451           xbt_dynar_free(&previous);
1452         }
1453         return 0;
1454       }
1455     }
1456
1457     if (size <= 0) {
1458       if (match_pairs) {
1459         match_equals(state, previous);
1460         xbt_dynar_free(&previous);
1461       }
1462       return 0;
1463     }
1464
1465     if ((heapinfo1->busy_frag.ignore[frag1] > 0)
1466         && (heapinfo2->busy_frag.ignore[frag2] ==
1467             heapinfo1->busy_frag.ignore[frag1]))
1468       check_ignore = heapinfo1->busy_frag.ignore[frag1];
1469
1470   } else {
1471
1472     if (match_pairs) {
1473       xbt_dynar_free(&previous);
1474     }
1475     return 1;
1476
1477   }
1478
1479
1480   /* Start comparison */
1481   if (type) {
1482     res_compare =
1483         compare_heap_area_with_type(state, process_index, area1, area2, snapshot1, snapshot2,
1484                                     previous, type, size, check_ignore,
1485                                     pointer_level);
1486   } else {
1487     res_compare =
1488         compare_heap_area_without_type(state, process_index, area1, area2, snapshot1, snapshot2,
1489                                        previous, size, check_ignore);
1490   }
1491   if (res_compare == 1) {
1492     if (match_pairs)
1493       xbt_dynar_free(&previous);
1494     return res_compare;
1495   }
1496
1497   if (match_pairs) {
1498     match_equals(state, previous);
1499     xbt_dynar_free(&previous);
1500   }
1501
1502   return 0;
1503 }
1504
1505 /*********************************************** Miscellaneous ***************************************************/
1506 /****************************************************************************************************************/
1507
1508 // Not used and broken code:
1509 # if 0
1510
1511 // Not used:
1512 static int get_pointed_area_size(void *area, int heap)
1513 {
1514
1515   struct s_mc_diff *state = mc_diff_info;
1516
1517   int block, frag;
1518   malloc_info *heapinfo;
1519
1520   if (heap == 1)
1521     heapinfo = state->heapinfo1;
1522   else
1523     heapinfo = state->heapinfo2;
1524
1525   block =
1526       ((char *) area -
1527        (char *) ((xbt_mheap_t) state->s_heap)->heapbase) / BLOCKSIZE + 1;
1528
1529   if (((char *) area < (char *) ((xbt_mheap_t) state->s_heap)->heapbase)
1530       || (block > state->heapsize1) || (block < 1))
1531     return -1;
1532
1533   if (heapinfo[block].type == MMALLOC_TYPE_FREE || heapinfo[block].type == MMALLOC_TYPE_HEAPINFO) {     /* Free block */
1534     return -1;
1535   } else if (heapinfo[block].type == MMALLOC_TYPE_UNFRAGMENTED) {       /* Complete block */
1536     return (int) heapinfo[block].busy_block.busy_size;
1537   } else {
1538     frag =
1539         ((uintptr_t) (ADDR2UINT(area) % (BLOCKSIZE))) >> heapinfo[block].type;
1540     return (int) heapinfo[block].busy_frag.frag_size[frag];
1541   }
1542 }
1543
1544 // Not used:
1545 char *get_type_description(mc_object_info_t info, char *type_name)
1546 {
1547
1548   xbt_dict_cursor_t dict_cursor;
1549   char *type_origin;
1550   dw_type_t type;
1551
1552   xbt_dict_foreach(info->types, dict_cursor, type_origin, type) {
1553     if (type->name && (strcmp(type->name, type_name) == 0)
1554         && type->byte_size > 0) {
1555       xbt_dict_cursor_free(&dict_cursor);
1556       return type_origin;
1557     }
1558   }
1559
1560   xbt_dict_cursor_free(&dict_cursor);
1561   return NULL;
1562 }
1563
1564
1565 #ifndef max
1566 #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
1567 #endif
1568
1569 // Not used:
1570 int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2)
1571 {
1572
1573   struct s_mc_diff *state = mc_diff_info;
1574
1575   if (heap1 == NULL && heap1 == NULL) {
1576     XBT_DEBUG("Malloc descriptors null");
1577     return 0;
1578   }
1579
1580   if (heap1->heaplimit != heap2->heaplimit) {
1581     XBT_DEBUG("Different limit of valid info table indices");
1582     return 1;
1583   }
1584
1585   /* Heap information */
1586   state->heaplimit = ((struct mdesc *) heap1)->heaplimit;
1587
1588
1589   // Mamailloute in order to find the base address of the main heap:
1590   state->s_heap =
1591       (char *) mmalloc_get_current_heap() - STD_HEAP_SIZE - xbt_pagesize;
1592
1593   state->heapbase1 = (char *) heap1 + BLOCKSIZE;
1594   state->heapbase2 = (char *) heap2 + BLOCKSIZE;
1595
1596   state->heapinfo1 =
1597       (malloc_info *) ((char *) heap1 +
1598                        ((uintptr_t)
1599                         ((char *) heap1->heapinfo - (char *) state->s_heap)));
1600   state->heapinfo2 =
1601       (malloc_info *) ((char *) heap2 +
1602                        ((uintptr_t)
1603                         ((char *) heap2->heapinfo - (char *) state->s_heap)));
1604
1605   state->heapsize1 = heap1->heapsize;
1606   state->heapsize2 = heap2->heapsize;
1607
1608   /* Start comparison */
1609   size_t i, j, k;
1610   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
1611
1612   int distance = 0;
1613
1614   /* Check busy blocks */
1615
1616   i = 1;
1617
1618   while (i <= state->heaplimit) {
1619
1620     addr_block1 =
1621         ((void *) (((ADDR2UINT(i)) - 1) * BLOCKSIZE +
1622                    (char *) state->heapbase1));
1623     addr_block2 =
1624         ((void *) (((ADDR2UINT(i)) - 1) * BLOCKSIZE +
1625                    (char *) state->heapbase2));
1626
1627     if (state->heapinfo1[i].type != state->heapinfo2[i].type) {
1628
1629       distance += BLOCKSIZE;
1630       XBT_DEBUG("Different type of blocks (%zu) : %d - %d -> distance = %d", i,
1631                 state->heapinfo1[i].type, state->heapinfo2[i].type, distance);
1632       i++;
1633
1634     } else {
1635
1636       if (state->heapinfo1[i].type == MMALLOC_TYPE_FREE
1637         || state->heapinfo1[i].type == MMALLOC_TYPE_HAPINFO) {     /* Free block */
1638         i++;
1639         continue;
1640       }
1641
1642       if (state->heapinfo1[i].type == MMALLOC_TYPE_UNFRAGMENTED) {      /* Large block */
1643
1644         if (state->heapinfo1[i].busy_block.size !=
1645             state->heapinfo2[i].busy_block.size) {
1646           distance +=
1647               BLOCKSIZE * max(state->heapinfo1[i].busy_block.size,
1648                               state->heapinfo2[i].busy_block.size);
1649           i += max(state->heapinfo1[i].busy_block.size,
1650                    state->heapinfo2[i].busy_block.size);
1651           XBT_DEBUG
1652               ("Different larger of cluster at block %zu : %zu - %zu -> distance = %d",
1653                i, state->heapinfo1[i].busy_block.size,
1654                state->heapinfo2[i].busy_block.size, distance);
1655           continue;
1656         }
1657
1658         /*if(heapinfo1[i].busy_block.busy_size != heapinfo2[i].busy_block.busy_size){
1659            distance += max(heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size);
1660            i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
1661            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);
1662            continue;
1663            } */
1664
1665         k = 0;
1666
1667         //while(k < (heapinfo1[i].busy_block.busy_size)){
1668         while (k < state->heapinfo1[i].busy_block.size * BLOCKSIZE) {
1669           if (memcmp((char *) addr_block1 + k, (char *) addr_block2 + k, 1) !=
1670               0) {
1671             distance++;
1672           }
1673           k++;
1674         }
1675
1676         i++;
1677
1678       } else {                  /* Fragmented block */
1679
1680         for (j = 0; j < (size_t) (BLOCKSIZE >> state->heapinfo1[i].type); j++) {
1681
1682           addr_frag1 =
1683               (void *) ((char *) addr_block1 + (j << state->heapinfo1[i].type));
1684           addr_frag2 =
1685               (void *) ((char *) addr_block2 + (j << state->heapinfo2[i].type));
1686
1687           if (state->heapinfo1[i].busy_frag.frag_size[j] == 0
1688               && state->heapinfo2[i].busy_frag.frag_size[j] == 0) {
1689             continue;
1690           }
1691
1692
1693           /*if(heapinfo1[i].busy_frag.frag_size[j] != heapinfo2[i].busy_frag.frag_size[j]){
1694              distance += max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j]);
1695              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);
1696              continue;
1697              } */
1698
1699           k = 0;
1700
1701           //while(k < max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j])){
1702           while (k < (BLOCKSIZE / (BLOCKSIZE >> state->heapinfo1[i].type))) {
1703             if (memcmp((char *) addr_frag1 + k, (char *) addr_frag2 + k, 1) !=
1704                 0) {
1705               distance++;
1706             }
1707             k++;
1708           }
1709
1710         }
1711
1712         i++;
1713
1714       }
1715
1716     }
1717
1718   }
1719
1720   return distance;
1721
1722 }
1723 #endif