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