src/mc/mc_diff.cpp

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