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