src/mc/mc_diff.c

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