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