src/mc/mc_diff.cpp

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