src/mc/mc_diff.cpp

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