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