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