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