src/xbt/mmalloc/mm_diff.c

   1 /* mm_diff - Memory snapshooting and comparison                             */
   2
   3 /* Copyright (c) 2008-2012. The SimGrid Team. All rights reserved.          */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #include "xbt/ex_interface.h" /* internals of backtrace setup */
   9 #include "xbt/str.h"
  10 #include "mc/mc.h"
  11
  12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mm_diff, xbt,
  13                                 "Logging specific to mm_diff in mmalloc");
  14
  15 extern char *xbt_binary_name;
  16
  17 xbt_dynar_t mmalloc_ignore;
  18
  19 typedef struct s_heap_area_pair{
  20   int block1;
  21   int fragment1;
  22   int block2;
  23   int fragment2;
  24 }s_heap_area_pair_t, *heap_area_pair_t;
  25
  26 static void heap_area_pair_free(heap_area_pair_t pair);
  27 static void heap_area_pair_free_voidp(void *d);
  28 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
  29 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
  30
  31 static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previous);
  32 static void match_equals(xbt_dynar_t list);
  33
  34 static size_t heap_comparison_ignore(void *address);
  35
  36 void mmalloc_backtrace_block_display(void* heapinfo, int block){
  37
  38   xbt_ex_t e;
  39
  40   if (((malloc_info *)heapinfo)[block].busy_block.bt_size == 0) {
  41     XBT_DEBUG("No backtrace available for that block, sorry.");
  42     return;
  43   }
  44
  45   memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE);
  46   e.used = ((malloc_info *)heapinfo)[block].busy_block.bt_size;
  47
  48   xbt_ex_setup_backtrace(&e);
  49   if (e.used == 0) {
  50     XBT_DEBUG("(backtrace not set)");
  51   } else if (e.bt_strings == NULL) {
  52     XBT_DEBUG("(backtrace not ready to be computed. %s)",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet");
  53   } else {
  54     int i;
  55
  56     XBT_DEBUG("Backtrace of where the block %d was malloced (%d frames):", block ,e.used);
  57     for (i = 0; i < e.used; i++)       /* no need to display "xbt_backtrace_display" */{
  58       XBT_DEBUG("%d ---> %s",i, e.bt_strings[i] + 4);
  59     }
  60   }
  61
  62 }
  63
  64 void mmalloc_backtrace_fragment_display(void* heapinfo, int block, int frag){
  65
  66   xbt_ex_t e;
  67
  68   memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE);
  69   e.used = XBT_BACKTRACE_SIZE;
  70
  71   xbt_ex_setup_backtrace(&e);
  72   if (e.used == 0) {
  73     XBT_DEBUG("(backtrace not set)");
  74   } else if (e.bt_strings == NULL) {
  75     XBT_DEBUG("(backtrace not ready to be computed. %s)",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet");
  76   } else {
  77     int i;
  78
  79     XBT_DEBUG("Backtrace of where the fragment %d in block %d was malloced (%d frames):", frag, block ,e.used);
  80     for (i = 0; i < e.used; i++)       /* no need to display "xbt_backtrace_display" */{
  81       XBT_DEBUG("%d ---> %s",i, e.bt_strings[i] + 4);
  82     }
  83   }
  84
  85 }
  86
  87 void *s_heap, *heapbase1, *heapbase2;
  88 malloc_info *heapinfo1, *heapinfo2;
  89 size_t heaplimit, heapsize1, heapsize2;
  90
  91 int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2){
  92
  93   if(heap1 == NULL && heap1 == NULL){
  94     XBT_DEBUG("Malloc descriptors null");
  95     return 0;
  96   }
  97
  98   if(heap1->heaplimit != heap2->heaplimit){
  99     XBT_DEBUG("Different limit of valid info table indices");
 100     return 1;
 101   }
 102
 103   /* Heap information */
 104   heaplimit = ((struct mdesc *)heap1)->heaplimit;
 105
 106   s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
 107
 108   heapbase1 = (char *)heap1 + BLOCKSIZE;
 109   heapbase2 = (char *)heap2 + BLOCKSIZE;
 110
 111   heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)s_heap)));
 112   heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)s_heap)));
 113
 114   heapsize1 = heap1->heapsize;
 115   heapsize2 = heap2->heapsize;
 116
 117   /* Start comparison */
 118   size_t i1, i2, j1, j2, k;
 119   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 120   size_t frag_size1, frag_size2;
 121
 122   xbt_dynar_t previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
 123
 124   int equal;
 125
 126   /* Check busy blocks*/
 127
 128   i1 = 1;
 129
 130   while(i1 < heaplimit){
 131
 132     i2 = 1;
 133     equal = 0;
 134
 135     if(heapinfo1[i1].type == -1){ /* Free block */
 136       i1++;
 137       continue;
 138     }
 139
 140     addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)heapbase1));
 141
 142     if(heapinfo1[i1].type == 0){  /* Large block */
 143
 144       while(i2 <= heaplimit && !equal){
 145
 146         if(heapinfo2[i2].type != 0){
 147           i2++;
 148           continue;
 149         }
 150
 151         if(heapinfo2[i2].busy_block.equal_to == 1){
 152           i2++;
 153           continue;
 154         }
 155
 156         if(heapinfo1[i1].busy_block.size != heapinfo2[i2].busy_block.size){
 157           i2++;
 158           continue;
 159         }
 160
 161         if(heapinfo1[i1].busy_block.busy_size != heapinfo2[i2].busy_block.busy_size){
 162           i2++;
 163           continue;
 164         }
 165
 166         addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 167
 168         /* Comparison */
 169         add_heap_area_pair(previous, i1, -1, i2, -1);
 170         if(!compare_area(addr_block1, addr_block2, heapinfo1[i1].busy_block.busy_size, previous)){
 171           for(k=0; k < heapinfo2[i2].busy_block.size; k++)
 172             heapinfo2[i2+k].busy_block.equal_to = 1;
 173           for(k=0; k < heapinfo1[i1].busy_block.size; k++)
 174             heapinfo1[i1+k].busy_block.equal_to = 1;
 175           equal = 1;
 176           match_equals(previous);
 177         }
 178         xbt_dynar_reset(previous);
 179
 180         i2++;
 181
 182       }
 183
 184     }else{ /* Fragmented block */
 185
 186       frag_size1 = 1 << heapinfo1[i1].type;
 187
 188       for(j1=0; j1 < (size_t) (BLOCKSIZE >> heapinfo1[i1].type); j1++){
 189
 190         if(heapinfo1[i1].busy_frag.frag_size[j1] == 0) /* Free fragment */
 191           continue;
 192
 193         addr_frag1 = (void*) ((char *)addr_block1 + (j1 * frag_size1));
 194
 195         i2 = 1;
 196         equal = 0;
 197
 198         while(i2 <= heaplimit && !equal){
 199
 200           if(heapinfo2[i2].type <= 0){
 201             i2++;
 202             continue;
 203           }
 204
 205           frag_size2 = 1 << heapinfo2[i2].type;
 206
 207           for(j2=0; j2 < (size_t) (BLOCKSIZE >> heapinfo2[i2].type); j2++){
 208
 209             if(heapinfo2[i2].busy_frag.equal_to[j2] == 1){
 210               continue;
 211             }
 212
 213             if(heapinfo1[i1].busy_frag.frag_size[j1] != heapinfo2[i2].busy_frag.frag_size[j2]){ /* Different size_used */
 214               continue;
 215             }
 216
 217             addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 218             addr_frag2 = (void*) ((char *)addr_block2 + (j2 * frag_size2));
 219
 220             /* Comparison */
 221             add_heap_area_pair(previous, i1, j1, i2, j2);
 222             if(!compare_area(addr_frag1, addr_frag2, heapinfo1[i1].busy_frag.frag_size[j1], previous)){
 223               heapinfo2[i2].busy_frag.equal_to[j2] = 1;
 224               heapinfo1[i1].busy_frag.equal_to[j1] = 1;
 225               equal = 1;
 226               match_equals(previous);
 227               break;
 228             }
 229             xbt_dynar_reset(previous);
 230
 231           }
 232
 233           i2++;
 234
 235         }
 236
 237       }
 238
 239     }
 240
 241     i1++;
 242
 243   }
 244
 245   /* All blocks/fragments are equal to another block/fragment ? */
 246   size_t i = 1, j = 0;
 247   int nb_diff1 = 0, nb_diff2 = 0;
 248   size_t frag_size = 0;
 249
 250   while(i<heaplimit){
 251     if(heapinfo1[i].type == 0){
 252       if(heapinfo1[i].busy_block.busy_size > 0){
 253         if(heapinfo1[i].busy_block.equal_to == -1){
 254           if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 255             addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
 256             XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block1, heapinfo1[i].busy_block.busy_size);
 257             mmalloc_backtrace_block_display((void*)heapinfo1, i);
 258           }
 259           nb_diff1++;
 260         }
 261       }
 262     }
 263     if(heapinfo1[i].type > 0){
 264       frag_size = 1 << heapinfo1[i].type;
 265       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){
 266         if(heapinfo1[i].busy_frag.frag_size[j] > 0){
 267           if(heapinfo1[i].busy_frag.equal_to[j] == -1){
 268             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 269               addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
 270               addr_frag1 = (void*) ((char *)addr_block1 + (j * frag_size));
 271               XBT_DEBUG("Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag1, heapinfo1[i].busy_frag.frag_size[j]);
 272               mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j);
 273             }
 274             nb_diff1++;
 275           }
 276         }
 277       }
 278     }
 279
 280     i++;
 281   }
 282
 283   XBT_DEBUG("Different blocks or fragments in heap1 : %d\n", nb_diff1);
 284
 285   i = 1;
 286
 287   while(i<heaplimit){
 288     if(heapinfo2[i].type == 0){
 289       if(heapinfo2[i].busy_block.busy_size > 0){
 290         if(heapinfo2[i].busy_block.equal_to == -1){
 291           if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 292             addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
 293             XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block2, heapinfo2[i].busy_block.busy_size);
 294             mmalloc_backtrace_block_display((void*)heapinfo2, i);
 295           }
 296           nb_diff2++;
 297         }
 298       }
 299     }
 300     if(heapinfo2[i].type > 0){
 301       frag_size = 1 << heapinfo2[i].type;
 302       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo2[i].type); j++){
 303         if(heapinfo2[i].busy_frag.frag_size[j] > 0){
 304           if(heapinfo2[i].busy_frag.equal_to[j] == -1){
 305             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 306               addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
 307               addr_frag2 = (void*) ((char *)addr_block2 + (j * frag_size));
 308               XBT_DEBUG( "Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag2, heapinfo2[i].busy_frag.frag_size[j]);
 309               mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j);
 310             }
 311             nb_diff2++;
 312           }
 313         }
 314       }
 315     }
 316     i++;
 317   }
 318
 319   XBT_DEBUG("Different blocks or fragments in heap2 : %d\n", nb_diff2);
 320
 321
 322   /* Reset equal information */
 323   i = 1;
 324
 325   while(i<heaplimit){
 326     if(heapinfo1[i].type == 0){
 327       heapinfo1[i].busy_block.equal_to = -1;
 328     }
 329     if(heapinfo1[i].type > 0){
 330       for(j=0; j < MAX_FRAGMENT_PER_BLOCK; j++){
 331         heapinfo1[i].busy_frag.equal_to[j] = -1;
 332       }
 333     }
 334     i++;
 335   }
 336
 337   i = 1;
 338
 339   while(i<heaplimit){
 340     if(heapinfo2[i].type == 0){
 341       heapinfo2[i].busy_block.equal_to = -1;
 342     }
 343     if(heapinfo2[i].type > 0){
 344       for(j=0; j < MAX_FRAGMENT_PER_BLOCK; j++){
 345         heapinfo2[i].busy_frag.equal_to[j] = -1;
 346       }
 347     }
 348     i++;
 349   }
 350
 351   xbt_dynar_free(&previous);
 352
 353   return ((nb_diff1 > 0) || (nb_diff2 > 0));
 354
 355 }
 356
 357 static size_t heap_comparison_ignore(void *address){
 358   unsigned int cursor = 0;
 359   mc_ignore_region_t region;
 360   xbt_dynar_foreach(mmalloc_ignore, cursor, region){
 361     if(region->address == address)
 362       return region->size;
 363   }
 364   return 0;
 365 }
 366
 367
 368 static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previous){
 369
 370   size_t i = 0, pointer_align = 0, ignore1 = 0, ignore2 = 0;
 371   void *address_pointed1, *address_pointed2, *addr_block_pointed1, *addr_block_pointed2, *addr_frag_pointed1, *addr_frag_pointed2;
 372   size_t block_pointed1, block_pointed2, frag_pointed1, frag_pointed2;
 373   size_t frag_size, frag_size1, frag_size2;
 374   int res_compare;
 375   void *current_area1, *current_area2;
 376
 377   while(i<size){
 378
 379     current_area1 = (char*)((xbt_mheap_t)s_heap)->heapbase + ((((char *)area1) + i) - (char *)heapbase1);
 380     if((ignore1 = heap_comparison_ignore(current_area1)) > 0){
 381       current_area2 = (char*)((xbt_mheap_t)s_heap)->heapbase + ((((char *)area2) + i) - (char *)heapbase2);
 382       if((ignore2 = heap_comparison_ignore(current_area2))  == ignore1){
 383         i = i + ignore2;
 384         continue;
 385       }
 386     }
 387
 388     if(memcmp(((char *)area1) + i, ((char *)area2) + i, 1) != 0){
 389
 390       /* Check pointer difference */
 391       pointer_align = (i / sizeof(void*)) * sizeof(void*);
 392       address_pointed1 = *((void **)((char *)area1 + pointer_align));
 393       address_pointed2 = *((void **)((char *)area2 + pointer_align));
 394
 395       /* Get pointed blocks number */
 396       block_pointed1 = ((char*)address_pointed1 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
 397       block_pointed2 = ((char*)address_pointed2 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
 398
 399       /* Check if valid blocks number */
 400       if((char *)address_pointed1 < (char*)((xbt_mheap_t)s_heap)->heapbase || block_pointed1 > heapsize1 || block_pointed1 < 1 || (char *)address_pointed2 < (char*)((xbt_mheap_t)s_heap)->heapbase || block_pointed2 > heapsize2 || block_pointed2 < 1)
 401         return 1;
 402
 403       if(heapinfo1[block_pointed1].type == heapinfo2[block_pointed2].type){ /* Same type of block (large or fragmented) */
 404
 405         addr_block_pointed1 = ((void*) (((ADDR2UINT(block_pointed1)) - 1) * BLOCKSIZE + (char*)heapbase1));
 406         addr_block_pointed2 = ((void*) (((ADDR2UINT(block_pointed2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 407
 408         if(heapinfo1[block_pointed1].type == 0){ /* Large block */
 409
 410           if(heapinfo1[block_pointed1].busy_block.size != heapinfo2[block_pointed2].busy_block.size){
 411             return 1;
 412           }
 413
 414           if(heapinfo1[block_pointed1].busy_block.busy_size != heapinfo2[block_pointed2].busy_block.busy_size){
 415             return 1;
 416           }
 417
 418           if(add_heap_area_pair(previous, block_pointed1, -1, block_pointed2, -1)){
 419
 420             res_compare = compare_area(addr_block_pointed1, addr_block_pointed2, heapinfo1[block_pointed1].busy_block.busy_size, previous);
 421
 422             if(res_compare)
 423               return 1;
 424
 425           }
 426
 427         }else{ /* Fragmented block */
 428
 429            /* Get pointed fragments number */
 430           frag_pointed1 = ((uintptr_t) (ADDR2UINT (address_pointed1) % (BLOCKSIZE))) >> heapinfo1[block_pointed1].type;
 431           frag_pointed2 = ((uintptr_t) (ADDR2UINT (address_pointed2) % (BLOCKSIZE))) >> heapinfo2[block_pointed2].type;
 432
 433           if(heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1] != heapinfo2[block_pointed2].busy_frag.frag_size[frag_pointed2]) /* Different size_used */
 434             return 1;
 435
 436           frag_size = 1 << heapinfo1[block_pointed1].type;
 437
 438           addr_frag_pointed1 = (void*) ((char *)addr_block_pointed1 + (frag_pointed1 * frag_size));
 439           addr_frag_pointed2 = (void*) ((char *)addr_block_pointed2 + (frag_pointed2 * frag_size));
 440
 441           if(add_heap_area_pair(previous, block_pointed1, frag_pointed1, block_pointed2, frag_pointed2)){
 442
 443             res_compare = compare_area(addr_frag_pointed1, addr_frag_pointed2, heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1], previous);
 444
 445             if(res_compare)
 446               return 1;
 447
 448           }
 449
 450         }
 451
 452       }else{
 453
 454         if((heapinfo1[block_pointed1].type > 0) && (heapinfo2[block_pointed2].type > 0)){
 455
 456           addr_block_pointed1 = ((void*) (((ADDR2UINT(block_pointed1)) - 1) * BLOCKSIZE + (char*)heapbase1));
 457           addr_block_pointed2 = ((void*) (((ADDR2UINT(block_pointed2)) - 1) * BLOCKSIZE + (char*)heapbase2));
 458
 459           frag_pointed1 = ((uintptr_t) (ADDR2UINT (address_pointed1) % (BLOCKSIZE))) >> heapinfo1[block_pointed1].type;
 460           frag_pointed2 = ((uintptr_t) (ADDR2UINT (address_pointed2) % (BLOCKSIZE))) >> heapinfo2[block_pointed2].type;
 461
 462           if(heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1] != heapinfo2[block_pointed2].busy_frag.frag_size[frag_pointed2]) /* Different size_used */
 463             return 1;
 464
 465           frag_size1 = 1 << heapinfo1[block_pointed1].type;
 466           frag_size2 = 1 << heapinfo1[block_pointed2].type;
 467
 468           addr_frag_pointed1 = (void*) ((char *)addr_block_pointed1 + (frag_pointed1 * frag_size1));
 469           addr_frag_pointed2 = (void*) ((char *)addr_block_pointed2 + (frag_pointed2 * frag_size2));
 470
 471           if(add_heap_area_pair(previous, block_pointed1, frag_pointed1, block_pointed2, frag_pointed2)){
 472
 473             res_compare = compare_area(addr_frag_pointed1, addr_frag_pointed2, heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1], previous);
 474
 475             if(res_compare)
 476               return 1;
 477
 478           }
 479
 480         }else{
 481           return 1;
 482         }
 483
 484       }
 485
 486       i = pointer_align + sizeof(void *);
 487
 488     }else{
 489
 490       i++;
 491
 492     }
 493   }
 494
 495   return 0;
 496
 497
 498 }
 499
 500 static void heap_area_pair_free(heap_area_pair_t pair){
 501   if (pair){
 502     free(pair);
 503     pair = NULL;
 504   }
 505 }
 506
 507 static void heap_area_pair_free_voidp(void *d)
 508 {
 509   heap_area_pair_free((heap_area_pair_t) * (void **) d);
 510 }
 511
 512 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 513
 514   if(is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)){
 515     heap_area_pair_t pair = NULL;
 516     pair = xbt_new0(s_heap_area_pair_t, 1);
 517     pair->block1 = block1;
 518     pair->fragment1 = fragment1;
 519     pair->block2 = block2;
 520     pair->fragment2 = fragment2;
 521
 522     xbt_dynar_push(list, &pair);
 523
 524     return 1;
 525   }
 526
 527   return 0;
 528 }
 529
 530 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 531
 532   unsigned int cursor = 0;
 533   heap_area_pair_t current_pair;
 534
 535   xbt_dynar_foreach(list, cursor, current_pair){
 536     if(current_pair->block1 == block1 && current_pair->block2 == block2 && current_pair->fragment1 == fragment1 && current_pair->fragment2 == fragment2)
 537       return 0;
 538   }
 539
 540   return 1;
 541 }
 542
 543 static void match_equals(xbt_dynar_t list){
 544
 545   unsigned int cursor = 0;
 546   heap_area_pair_t current_pair;
 547
 548   xbt_dynar_foreach(list, cursor, current_pair){
 549     if(current_pair->fragment1 != -1){
 550       heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] = 1;
 551       heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] = 1;
 552     }else{
 553       heapinfo1[current_pair->block1].busy_block.equal_to = 1;
 554       heapinfo2[current_pair->block2].busy_block.equal_to = 1;
 555     }
 556   }
 557
 558 }
 559