fn.c revision 9ebd6e0c607fa30301b1325874eb8de871c21cc5
1/*--------------------------------------------------------------------*/ 2/*--- Callgrind ---*/ 3/*--- ct_fn.c ---*/ 4/*--------------------------------------------------------------------*/ 5 6/* 7 This file is part of Callgrind, a Valgrind tool for call tracing. 8 9 Copyright (C) 2002-2007, Josef Weidendorfer (Josef.Weidendorfer@gmx.de) 10 11 This program is free software; you can redistribute it and/or 12 modify it under the terms of the GNU General Public License as 13 published by the Free Software Foundation; either version 2 of the 14 License, or (at your option) any later version. 15 16 This program is distributed in the hope that it will be useful, but 17 WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 19 General Public License for more details. 20 21 You should have received a copy of the GNU General Public License 22 along with this program; if not, write to the Free Software 23 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 24 02111-1307, USA. 25 26 The GNU General Public License is contained in the file COPYING. 27*/ 28 29#include "global.h" 30 31#define N_INITIAL_FN_ARRAY_SIZE 10071 32 33static fn_array current_fn_active; 34 35static Addr runtime_resolve_addr = 0; 36static int runtime_resolve_length = 0; 37 38/* _ld_runtime_resolve, located in needs special handling: 39 * The jump at end into the resolved function should not be 40 * represented as a call (as usually done in callgrind with jumps), 41 * but as a return + call. Otherwise, the repeated existance of 42 * _ld_runtime_resolve in call chains will lead to huge cycles, 43 * making the profile almost worthless. 44 * 45 * If ld.so is stripped, the symbol will not appear. But as this 46 * function is handcrafted assembler, we search for it... 47 * 48 * Returns 0 if code not found, otherwise start address 49 */ 50static void search_runtime_resolve(obj_node* obj) 51{ 52 /* We do not check target address of <fixup>, therefore we have >1 ranges. 53 * We use a tuple sequence (offset,length) into the code array for this 54 */ 55 56#if defined(VGP_x86_linux) 57 /* Check ranges [0-11], [16-23] */ 58 static int code_offsets[] = { 0, 12, 16, 8, 24, 0 }; 59 static unsigned char code[] = { 60 /* 0*/ 0x50, 0x51, 0x52, 0x8b, 0x54, 0x24, 0x10, 0x8b, 61 /* 8*/ 0x44, 0x24, 0x0c, 0xe8, 0x70, 0x01, 0x00, 0x00, 62 /*16*/ 0x5a, 0x59, 0x87, 0x04, 0x24, 0xc2, 0x08, 0x00 }; 63#else 64#if defined(VGP_ppc32_linux) 65 static int code_offsets[] = {0, 65, 68, 64, 132, 0 }; 66 static unsigned char code[] = { 67 /* 0*/ 0x94, 0x21, 0xff, 0xc0, 0x90, 0x01, 0x00, 0x0c, 68 /* 8*/ 0x90, 0x61, 0x00, 0x10, 0x90, 0x81, 0x00, 0x14, 69 /*16*/ 0x7d, 0x83, 0x63, 0x78, 0x90, 0xa1, 0x00, 0x18, 70 /*24*/ 0x7d, 0x64, 0x5b, 0x78, 0x90, 0xc1, 0x00, 0x1c, 71 /*32*/ 0x7c, 0x08, 0x02, 0xa6, 0x90, 0xe1, 0x00, 0x20, 72 /*40*/ 0x90, 0x01, 0x00, 0x30, 0x91, 0x01, 0x00, 0x24, 73 /*48*/ 0x7c, 0x00, 0x00, 0x26, 0x91, 0x21, 0x00, 0x28, 74 /*56*/ 0x91, 0x41, 0x00, 0x2c, 0x90, 0x01, 0x00, 0x08, 75 /*64*/ 0x48, 0x00, 0x02, 0x91, 0x7c, 0x69, 0x03, 0xa6, /* at 64: bl aff0 <fixup> */ 76 /*72*/ 0x80, 0x01, 0x00, 0x30, 0x81, 0x41, 0x00, 0x2c, 77 /*80*/ 0x81, 0x21, 0x00, 0x28, 0x7c, 0x08, 0x03, 0xa6, 78 /*88*/ 0x81, 0x01, 0x00, 0x24, 0x80, 0x01, 0x00, 0x08, 79 /*96*/ 0x80, 0xe1, 0x00, 0x20, 0x80, 0xc1, 0x00, 0x1c, 80 /*104*/0x7c, 0x0f, 0xf1, 0x20, 0x80, 0xa1, 0x00, 0x18, 81 /*112*/0x80, 0x81, 0x00, 0x14, 0x80, 0x61, 0x00, 0x10, 82 /*120*/0x80, 0x01, 0x00, 0x0c, 0x38, 0x21, 0x00, 0x40, 83 /*128*/0x4e, 0x80, 0x04, 0x20 }; 84#else 85#if defined(VGP_amd64_linux) 86 /* x86_64 */ 87 static int code_offsets[] = {0, 62, 66, 44, 110, 0 }; 88 static unsigned char code[] = { 89 /* 0*/ 0x48, 0x83, 0xec, 0x38, 0x48, 0x89, 0x04, 0x24, 90 /* 8*/ 0x48, 0x89, 0x4c, 0x24, 0x08, 0x48, 0x89, 0x54, 0x24, 0x10, 91 /*18*/ 0x48, 0x89, 0x74, 0x24, 0x18, 0x48, 0x89, 0x7c, 0x24, 0x20, 92 /*28*/ 0x4c, 0x89, 0x44, 0x24, 0x28, 0x4c, 0x89, 0x4c, 0x24, 0x30, 93 /*38*/ 0x48, 0x8b, 0x74, 0x24, 0x40, 0x49, 0x89, 0xf3, 94 /*46*/ 0x4c, 0x01, 0xde, 0x4c, 0x01, 0xde, 0x48, 0xc1, 0xe6, 0x03, 95 /*56*/ 0x48, 0x8b, 0x7c, 0x24, 0x38, 0xe8, 0xee, 0x01, 0x00, 0x00, 96 /*66*/ 0x49, 0x89, 0xc3, 0x4c, 0x8b, 0x4c, 0x24, 0x30, 97 /*74*/ 0x4c, 0x8b, 0x44, 0x24, 0x28, 0x48, 0x8b, 0x7c, 0x24, 0x20, 98 /*84*/ 0x48, 0x8b, 0x74, 0x24, 0x18, 0x48, 0x8b, 0x54, 0x24, 0x10, 99 /*94*/ 0x48, 0x8b, 0x4c, 0x24, 0x08, 0x48, 0x8b, 0x04, 0x24, 100 /*103*/0x48, 0x83, 0xc4, 0x48, 0x41, 0xff, 0xe3 }; 101#else 102 /* Unknown platform, no check is done */ 103 static int code_offsets[] = {0, 0 }; 104 static unsigned char code[] = { 0 }; 105#endif 106#endif 107#endif 108 109 int *range = &(code_offsets[0]), *r = 0; 110 Bool found = False; 111 Addr addr, end; 112 113 /* Only search in libraries with a given name pattern */ 114 if ((VG_(strncmp)(obj->name, "/lib/ld", 7) != 0) && 115 (VG_(strncmp)(obj->name, "/lib64/ld", 9) != 0)) return; 116 117 CLG_DEBUG(1, "search_rs: Checking %d bytes of [%x %x %x...]\n", 118 range[1], code[0], code[1], code[2]); 119 120 end = obj->start + obj->size - range[1]; 121 addr = obj->start; 122 123 if (range[1] == 0) return; 124 125 while(addr < end) { 126 if (VG_(memcmp)( (void*)addr, code, range[1]) == 0) { 127 128 r = range + 2; 129 found = True; 130 while(r[1]) { 131 CLG_DEBUG(1, " [%p] Found! Checking %d bytes of [%x %x %x...]\n", 132 addr, r[1], code[r[0]], code[r[0]+1], code[r[0]+2]); 133 134 if (VG_(memcmp)( (void*)(addr+r[0]), code+r[0], r[1]) != 0) { 135 found = False; 136 break; 137 } 138 r += 2; 139 } 140 if (found) break; 141 } 142 addr++; 143 } 144 145 if (!found || (r==0)) return; 146 147 if (VG_(clo_verbosity) > 1) 148 VG_(message)(Vg_DebugMsg, "Code check found runtime_resolve: %s +%p=%p, length %d", 149 obj->name + obj->last_slash_pos, 150 addr - obj->start, addr, r[0]); 151 152 runtime_resolve_addr = addr; 153 runtime_resolve_length = r[0]; 154} 155 156/*------------------------------------------------------------*/ 157/*--- Object/File/Function hash entry operations ---*/ 158/*------------------------------------------------------------*/ 159 160/* Object hash table, fixed */ 161static obj_node* obj_table[N_OBJ_ENTRIES]; 162 163void CLG_(init_obj_table)() 164{ 165 Int i; 166 for (i = 0; i < N_OBJ_ENTRIES; i++) 167 obj_table[i] = 0; 168} 169 170#define HASH_CONSTANT 256 171 172static UInt str_hash(const Char *s, UInt table_size) 173{ 174 int hash_value = 0; 175 for ( ; *s; s++) 176 hash_value = (HASH_CONSTANT * hash_value + *s) % table_size; 177 return hash_value; 178} 179 180 181static Char* anonymous_obj = "???"; 182 183static __inline__ 184obj_node* new_obj_node(SegInfo* si, obj_node* next) 185{ 186 Int i; 187 obj_node* new; 188 189 new = (obj_node*) CLG_MALLOC(sizeof(obj_node)); 190 new->name = si ? VG_(strdup)( VG_(seginfo_filename)(si) ) 191 : anonymous_obj; 192 for (i = 0; i < N_FILE_ENTRIES; i++) { 193 new->files[i] = NULL; 194 } 195 CLG_(stat).distinct_objs ++; 196 new->number = CLG_(stat).distinct_objs; 197 new->start = si ? VG_(seginfo_start)(si) : 0; 198 new->size = si ? VG_(seginfo_size)(si) : 0; 199 new->offset = si ? VG_(seginfo_sym_offset)(si) : 0; 200 new->next = next; 201 202 // not only used for debug output (see static.c) 203 new->last_slash_pos = 0; 204 i = 0; 205 while(new->name[i]) { 206 if (new->name[i]=='/') new->last_slash_pos = i+1; 207 i++; 208 } 209 210 if (runtime_resolve_addr == 0) search_runtime_resolve(new); 211 212 return new; 213} 214 215obj_node* CLG_(get_obj_node)(SegInfo* si) 216{ 217 obj_node* curr_obj_node; 218 UInt objname_hash; 219 const UChar* obj_name; 220 221 obj_name = si ? (Char*) VG_(seginfo_filename)(si) : anonymous_obj; 222 223 /* lookup in obj hash */ 224 objname_hash = str_hash(obj_name, N_OBJ_ENTRIES); 225 curr_obj_node = obj_table[objname_hash]; 226 while (NULL != curr_obj_node && 227 VG_(strcmp)(obj_name, curr_obj_node->name) != 0) { 228 curr_obj_node = curr_obj_node->next; 229 } 230 if (NULL == curr_obj_node) { 231 obj_table[objname_hash] = curr_obj_node = 232 new_obj_node(si, obj_table[objname_hash]); 233 } 234 235 return curr_obj_node; 236} 237 238 239static __inline__ 240file_node* new_file_node(Char filename[FILENAME_LEN], 241 obj_node* obj, file_node* next) 242{ 243 Int i; 244 file_node* new = (file_node*) CLG_MALLOC(sizeof(file_node)); 245 new->name = VG_(strdup)(filename); 246 for (i = 0; i < N_FN_ENTRIES; i++) { 247 new->fns[i] = NULL; 248 } 249 CLG_(stat).distinct_files++; 250 new->number = CLG_(stat).distinct_files; 251 new->obj = obj; 252 new->next = next; 253 return new; 254} 255 256 257file_node* CLG_(get_file_node)(obj_node* curr_obj_node, 258 Char filename[FILENAME_LEN]) 259{ 260 file_node* curr_file_node; 261 UInt filename_hash; 262 263 /* lookup in file hash */ 264 filename_hash = str_hash(filename, N_FILE_ENTRIES); 265 curr_file_node = curr_obj_node->files[filename_hash]; 266 while (NULL != curr_file_node && 267 VG_(strcmp)(filename, curr_file_node->name) != 0) { 268 curr_file_node = curr_file_node->next; 269 } 270 if (NULL == curr_file_node) { 271 curr_obj_node->files[filename_hash] = curr_file_node = 272 new_file_node(filename, curr_obj_node, 273 curr_obj_node->files[filename_hash]); 274 } 275 276 return curr_file_node; 277} 278 279/* forward decl. */ 280static void resize_fn_array(void); 281 282static __inline__ 283fn_node* new_fn_node(Char fnname[FILENAME_LEN], 284 file_node* file, fn_node* next) 285{ 286 fn_node* new = (fn_node*) CLG_MALLOC(sizeof(fn_node)); 287 new->name = VG_(strdup)(fnname); 288 289 CLG_(stat).distinct_fns++; 290 new->number = CLG_(stat).distinct_fns; 291 new->last_cxt = 0; 292 new->pure_cxt = 0; 293 new->file = file; 294 new->next = next; 295 296 new->dump_before = False; 297 new->dump_after = False; 298 new->zero_before = False; 299 new->toggle_collect = False; 300 new->skip = False; 301 new->pop_on_jump = CLG_(clo).pop_on_jump; 302 new->is_malloc = False; 303 new->is_realloc = False; 304 new->is_free = False; 305 306 new->group = 0; 307 new->separate_callers = CLG_(clo).separate_callers; 308 new->separate_recursions = CLG_(clo).separate_recursions; 309 310#if CLG_ENABLE_DEBUG 311 new->verbosity = -1; 312#endif 313 314 if (CLG_(stat).distinct_fns >= current_fn_active.size) 315 resize_fn_array(); 316 317 return new; 318} 319 320 321/* Get a function node in hash2 with known file node. 322 * hash nodes are created if needed 323 */ 324static 325fn_node* get_fn_node_infile(file_node* curr_file_node, 326 Char fnname[FN_NAME_LEN]) 327{ 328 fn_node* curr_fn_node; 329 UInt fnname_hash; 330 331 CLG_ASSERT(curr_file_node != 0); 332 333 /* lookup in function hash */ 334 fnname_hash = str_hash(fnname, N_FN_ENTRIES); 335 curr_fn_node = curr_file_node->fns[fnname_hash]; 336 while (NULL != curr_fn_node && 337 VG_(strcmp)(fnname, curr_fn_node->name) != 0) { 338 curr_fn_node = curr_fn_node->next; 339 } 340 if (NULL == curr_fn_node) { 341 curr_file_node->fns[fnname_hash] = curr_fn_node = 342 new_fn_node(fnname, curr_file_node, 343 curr_file_node->fns[fnname_hash]); 344 } 345 346 return curr_fn_node; 347} 348 349 350/* Get a function node in a Segment. 351 * Hash nodes are created if needed. 352 */ 353static __inline__ 354fn_node* get_fn_node_inseg(SegInfo* si, 355 Char filename[FILENAME_LEN], 356 Char fnname[FN_NAME_LEN]) 357{ 358 obj_node *obj = CLG_(get_obj_node)(si); 359 file_node *file = CLG_(get_file_node)(obj, filename); 360 fn_node *fn = get_fn_node_infile(file, fnname); 361 362 return fn; 363} 364 365 366Bool CLG_(get_debug_info)(Addr instr_addr, 367 Char filename[FILENAME_LEN], 368 Char fn_name[FN_NAME_LEN], UInt* line_num, 369 SegInfo** pSegInfo) 370{ 371 Bool found1, found2, result = True; 372 UInt line; 373 374 CLG_DEBUG(6, " + get_debug_info(%p)\n", instr_addr); 375 376 if (pSegInfo) { 377 *pSegInfo = VG_(find_seginfo)(instr_addr); 378 379 // for generated code in anonymous space, pSegInfo is 0 380 } 381 382 found1 = VG_(get_filename_linenum)(instr_addr, 383 filename, FILENAME_LEN, 384 NULL, 0, NULL, // FIXME: add dirnames! 385 &line); 386 found2 = VG_(get_fnname)(instr_addr, 387 fn_name, FN_NAME_LEN); 388 389 if (!found1 && !found2) { 390 CLG_(stat).no_debug_BBs++; 391 VG_(strcpy)(filename, "???"); 392 VG_(strcpy)(fn_name, "???"); 393 if (line_num) *line_num=0; 394 result = False; 395 396 } else if ( found1 && found2) { 397 CLG_(stat).full_debug_BBs++; 398 if (line_num) *line_num=line; 399 400 } else if ( found1 && !found2) { 401 CLG_(stat).file_line_debug_BBs++; 402 VG_(strcpy)(fn_name, "???"); 403 if (line_num) *line_num=line; 404 405 } else /*(!found1 && found2)*/ { 406 CLG_(stat).fn_name_debug_BBs++; 407 VG_(strcpy)(filename, "???"); 408 if (line_num) *line_num=0; 409 } 410 411 CLG_DEBUG(6, " - get_debug_info(%p): seg '%s', fn %s\n", 412 instr_addr, 413 !pSegInfo ? (const UChar*)"-" : 414 (*pSegInfo) ? VG_(seginfo_filename)(*pSegInfo) : 415 (const UChar*)"(None)", 416 fn_name); 417 418 return result; 419} 420 421/* for _libc_freeres_wrapper => _exit renaming */ 422static BB* exit_bb = 0; 423 424 425/* 426 * Attach function struct to a BB from debug info. 427 */ 428fn_node* CLG_(get_fn_node)(BB* bb) 429{ 430 Char filename[FILENAME_LEN], fnname[FN_NAME_LEN]; 431 SegInfo* si; 432 UInt line_num; 433 fn_node* fn; 434 435 /* fn from debug info is idempotent for a BB */ 436 if (bb->fn) return bb->fn; 437 438 CLG_DEBUG(3,"+ get_fn_node(BB %p)\n", bb_addr(bb)); 439 440 /* get function/file name, line number and object of 441 * the BB according to debug information 442 */ 443 CLG_(get_debug_info)(bb_addr(bb), 444 filename, fnname, &line_num, &si); 445 446 if (0 == VG_(strcmp)(fnname, "???")) { 447 int p; 448 449 /* Use address as found in library */ 450 if (sizeof(Addr) == 4) 451 p = VG_(sprintf)(fnname, "%08p", bb->offset); 452 else 453 // 64bit address 454 p = VG_(sprintf)(fnname, "%016p", bb->offset); 455 456 VG_(sprintf)(fnname+p, "%s", 457 (bb->sect_kind == Vg_SectData) ? " [Data]" : 458 (bb->sect_kind == Vg_SectBSS) ? " [BSS]" : 459 (bb->sect_kind == Vg_SectGOT) ? " [GOT]" : 460 (bb->sect_kind == Vg_SectPLT) ? " [PLT]" : ""); 461 } 462 else { 463 if (VG_(get_fnname_if_entry)(bb_addr(bb), fnname, FN_NAME_LEN)) 464 bb->is_entry = 1; 465 } 466 467 /* HACK for correct _exit: 468 * _exit is redirected to VG_(__libc_freeres_wrapper) by valgrind, 469 * so we rename it back again :-) 470 */ 471 if (0 == VG_(strcmp)(fnname, "vgPlain___libc_freeres_wrapper") 472 && exit_bb) { 473 CLG_(get_debug_info)(bb_addr(exit_bb), 474 filename, fnname, &line_num, &si); 475 476 CLG_DEBUG(1, "__libc_freeres_wrapper renamed to _exit\n"); 477 } 478 if (0 == VG_(strcmp)(fnname, "_exit") && !exit_bb) 479 exit_bb = bb; 480 481 if (runtime_resolve_addr && 482 (bb_addr(bb) >= runtime_resolve_addr) && 483 (bb_addr(bb) < runtime_resolve_addr + runtime_resolve_length)) { 484 /* BB in runtime_resolve found by code check; use this name */ 485 VG_(sprintf)(fnname, "_dl_runtime_resolve"); 486 } 487 488 /* get fn_node struct for this function */ 489 fn = get_fn_node_inseg( si, filename, fnname); 490 491 /* if this is the 1st time the function is seen, 492 * some attributes are set */ 493 if (fn->pure_cxt == 0) { 494 495 /* Every function gets a "pure" context, i.e. a context with stack 496 * depth 1 only with this function. This is for compression of mangled 497 * names 498 */ 499 fn_node* pure[2]; 500 pure[0] = 0; 501 pure[1] = fn; 502 fn->pure_cxt = CLG_(get_cxt)(pure+1); 503 504 if (bb->sect_kind == Vg_SectPLT) 505 fn->skip = CLG_(clo).skip_plt; 506 507 if (VG_(strcmp)(fn->name, "_dl_runtime_resolve")==0) { 508 fn->pop_on_jump = True; 509 510 if (VG_(clo_verbosity) > 1) 511 VG_(message)(Vg_DebugMsg, "Symbol match: found runtime_resolve: %s +%p=%p", 512 bb->obj->name + bb->obj->last_slash_pos, 513 bb->offset, bb_addr(bb)); 514 } 515 516 fn->is_malloc = (VG_(strcmp)(fn->name, "malloc")==0); 517 fn->is_realloc = (VG_(strcmp)(fn->name, "realloc")==0); 518 fn->is_free = (VG_(strcmp)(fn->name, "free")==0); 519 520 /* apply config options from function name patterns 521 * given on command line */ 522 CLG_(update_fn_config)(fn); 523 } 524 525 526 bb->fn = fn; 527 bb->line = line_num; 528 529 CLG_DEBUG(3,"- get_fn_node(BB %p): %s (in %s:%u)\n", 530 bb_addr(bb), fnname, filename, line_num); 531 532 return fn; 533} 534 535 536/*------------------------------------------------------------*/ 537/*--- Active function array operations ---*/ 538/*------------------------------------------------------------*/ 539 540/* The active function array is a thread-specific array 541 * of UInts, mapping function numbers to the active count of 542 * functions. 543 * The active count is the number of times a function appears 544 * in the current call stack, and is used when costs for recursion 545 * levels should be separated. 546 */ 547 548UInt* CLG_(get_fn_entry)(Int n) 549{ 550 CLG_ASSERT(n < current_fn_active.size); 551 return current_fn_active.array + n; 552} 553 554void CLG_(init_fn_array)(fn_array* a) 555{ 556 Int i; 557 558 CLG_ASSERT(a != 0); 559 560 a->size = N_INITIAL_FN_ARRAY_SIZE; 561 if (a->size <= CLG_(stat).distinct_fns) 562 a->size = CLG_(stat).distinct_fns+1; 563 564 a->array = (UInt*) CLG_MALLOC(a->size * sizeof(UInt)); 565 for(i=0;i<a->size;i++) 566 a->array[i] = 0; 567} 568 569void CLG_(copy_current_fn_array)(fn_array* dst) 570{ 571 CLG_ASSERT(dst != 0); 572 573 dst->size = current_fn_active.size; 574 dst->array = current_fn_active.array; 575} 576 577fn_array* CLG_(get_current_fn_array)() 578{ 579 return ¤t_fn_active; 580} 581 582void CLG_(set_current_fn_array)(fn_array* a) 583{ 584 CLG_ASSERT(a != 0); 585 586 current_fn_active.size = a->size; 587 current_fn_active.array = a->array; 588 if (current_fn_active.size <= CLG_(stat).distinct_fns) 589 resize_fn_array(); 590} 591 592/* ensure that active_array is big enough: 593 * <distinct_fns> is the highest index, so <fn_active_array_size> 594 * has to be bigger than that. 595 */ 596static void resize_fn_array(void) 597{ 598 UInt* new; 599 Int i, newsize; 600 601 newsize = current_fn_active.size; 602 while (newsize <= CLG_(stat).distinct_fns) newsize *=2; 603 604 CLG_DEBUG(0, "Resize fn_active_array: %d => %d\n", 605 current_fn_active.size, newsize); 606 607 new = (UInt*) CLG_MALLOC(newsize * sizeof(UInt)); 608 for(i=0;i<current_fn_active.size;i++) 609 new[i] = current_fn_active.array[i]; 610 while(i<newsize) 611 new[i++] = 0; 612 613 VG_(free)(current_fn_active.array); 614 current_fn_active.size = newsize; 615 current_fn_active.array = new; 616 CLG_(stat).fn_array_resizes++; 617} 618 619 620