1/* Copyright (C) 2021 Free Software Foundation, Inc. 2 Contributed by Oracle. 3 4 This file is part of GNU Binutils. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, 51 Franklin Street - Fifth Floor, Boston, 19 MA 02110-1301, USA. */ 20 21#include "config.h" 22#include <stdio.h> 23#include <stdlib.h> 24 25#include "util.h" 26#include "DefaultMap.h" 27#include "CacheMap.h" 28 29#include "DbeSession.h" 30#include "Application.h" 31#include "CallStack.h" 32#include "Emsg.h" 33#include "Experiment.h" 34#include "Expression.h" 35#include "Function.h" 36#include "Histable.h" 37#include "IndexObject.h" 38#include "MetricList.h" 39#include "Module.h" 40#include "DbeView.h" 41#include "Metric.h" 42#include "PathTree.h" 43#include "LoadObject.h" 44#include "Sample.h" 45#include "StringBuilder.h" 46#include "Table.h" 47 48// Define counts, rate for error warnings for statistical profiles 49#define MIN_PROF_CNT 100 50#define MAX_PROF_RATE 1000. 51 52#define NUM_DESCENDANTS(nd) ((nd)->descendants ? (nd)->descendants->size() : 0) 53#define IS_LEAF(nd) ((nd)->descendants == NULL) 54 55#ifdef DEBUG 56#define DBG(__func) __func 57#else 58#define DBG(__func) 59#endif 60 61void 62PathTree::construct (DbeView *_dbev, int _indxtype, PathTreeType _pathTreeType) 63{ 64 dbev = _dbev; 65 indxtype = _indxtype; 66 pathTreeType = _pathTreeType; 67 status = 0; 68 nchunks = 0; 69 chunks = NULL; 70 nodes = 1; // don't use node 0 71 nslots = 0; 72 slots = NULL; 73 root_idx = 0; 74 root = NULL; 75 depth = 1; 76 dnodes = 0; 77 phaseIdx = -1; 78 nexps = 0; 79 total_obj = NULL; 80 indx_expr = NULL; 81 statsq = NULL; 82 warningq = NULL; 83 cancel_ok = 1; 84 ptree_internal = NULL; 85 ftree_internal = NULL; 86 ftree_needs_update = false; 87 depth_map = NULL; 88 init (); 89} 90 91PathTree::~PathTree () 92{ 93 fini (); 94 for (long i = 0; i < nchunks; i++) 95 delete[] chunks[i]; 96 delete[] chunks; 97} 98 99void 100PathTree::init () 101{ 102 fn_map = new DefaultMap<Function*, NodeIdx>; 103 stack_prop = PROP_NONE; 104 desc_htable_size = 511; 105 desc_htable_nelem = 0; 106 descHT = new hash_node_t*[desc_htable_size]; 107 for (int i = 0; i < desc_htable_size; i++) 108 descHT[i] = NULL; 109 pathMap = new CacheMap<uint64_t, NodeIdx>; 110 statsq = new Emsgqueue (NTXT ("statsq")); 111 warningq = new Emsgqueue (NTXT ("warningq")); 112 if (indxtype < 0) 113 { 114 Function *ftotal = dbeSession->get_Total_Function (); 115 if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE) 116 total_obj = ftotal; 117 else 118 total_obj = ftotal->find_dbeinstr (0, 0); 119 VMode view_mode = dbev->get_view_mode (); 120 if (view_mode == VMODE_MACHINE) 121 stack_prop = PROP_MSTACK; 122 else if (view_mode == VMODE_EXPERT) 123 stack_prop = PROP_XSTACK; 124 else if (view_mode == VMODE_USER) 125 { 126 stack_prop = PROP_USTACK; 127 if (dbeSession->is_omp_available () 128 && pathTreeType == PATHTREE_INTERNAL_OMP) 129 stack_prop = PROP_XSTACK; 130 } 131 } 132 else 133 { 134 total_obj = new IndexObject (indxtype, (uint64_t) - 2); 135 total_obj->set_name (dbe_strdup (NTXT ("<Total>"))); 136 char *idxname = dbeSession->getIndexSpaceName (indxtype); 137 if (streq (idxname, NTXT ("OMP_preg"))) 138 stack_prop = PROP_CPRID; 139 else if (streq (idxname, NTXT ("OMP_task"))) 140 stack_prop = PROP_TSKID; 141 else 142 indx_expr = dbeSession->getIndexSpaceExpr (indxtype); 143 } 144 root_idx = new_Node (0, total_obj, false); 145 root = NODE_IDX (root_idx); 146} 147 148void 149PathTree::fini () 150{ 151 // For each node free its descendants vector 152 // and reset the node list of its function 153 for (long i = 1; i < nodes; i++) 154 { 155 Node *node = NODE_IDX (i); 156 if (node->descendants) 157 delete node->descendants; 158 } 159 nodes = 1; // don't use node 0 160 161 for (int i = 0; i < nslots; i++) 162 { 163 int **tmp = slots[i].mvals; 164 for (long j = 0; j < nchunks; j++) 165 delete[] tmp[j]; 166 delete[] tmp; 167 } 168 delete[] slots; 169 slots = NULL; 170 nslots = 0; 171 delete fn_map; 172 fn_map = NULL; 173 delete pathMap; 174 pathMap = NULL; 175 destroy (depth_map); 176 depth_map = NULL; 177 if (indxtype >= 0) 178 delete total_obj; 179 180 for (int i = 0; i < desc_htable_size; i++) 181 { 182 hash_node_t *p = descHT[i]; 183 while (p) 184 { 185 hash_node_t *p1 = p; 186 p = p->next; 187 delete p1; 188 } 189 } 190 delete[] descHT; 191 delete statsq; 192 delete warningq; 193 depth = 1; 194 dnodes = 0; 195 phaseIdx = -1; 196 nexps = 0; 197 status = 0; 198} 199 200PtreePhaseStatus 201PathTree::reset () 202{ 203 if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE) 204 return NORMAL; // never process reset for ftree_internal. 205 206 if (dbeSession->is_omp_available () && dbev->get_view_mode () == VMODE_USER 207 && pathTreeType == PATHTREE_MAIN && ptree_internal == NULL) 208 ptree_internal = new PathTree (dbev, indxtype, PATHTREE_INTERNAL_OMP); 209 210 if (phaseIdx != dbev->getPhaseIdx ()) 211 { 212 fini (); 213 init (); 214 phaseIdx = dbev->getPhaseIdx (); 215 ftree_needs_update = true; 216 } 217 for (; nexps < dbeSession->nexps (); nexps++) 218 { 219 ftree_needs_update = true; 220 if (add_experiment (nexps) == CANCELED) 221 return CANCELED; 222 } 223 224 // LIBRARY_VISIBILITY 225 if (dbev->isNewViewMode ()) 226 dbev->resetNewViewMode (); 227 if (dbev->isShowHideChanged ()) 228 dbev->resetShowHideChanged (); 229 return NORMAL; 230} 231 232int 233PathTree::allocate_slot (int id, ValueTag vtype) 234{ 235 236 int i; 237 int slot_idx = find_slot (id); 238 if (slot_idx >= 0) 239 { 240 DBG (assert (slots[slot_idx].vtype == vtype)); 241 return slot_idx; 242 } 243 slot_idx = nslots++; 244 245 Slot *old_slots = slots; 246 slots = new Slot[nslots]; 247 for (i = 0; i < slot_idx; i++) 248 slots[i] = old_slots[i]; 249 delete[] old_slots; 250 251 slots[slot_idx].id = id; 252 slots[slot_idx].vtype = vtype; 253 int **ip = new int*[nchunks]; 254 for (i = 0; i < nchunks; i++) 255 ip[i] = NULL; 256 slots[slot_idx].mvals = ip; 257 258 return slot_idx; 259} 260 261void 262PathTree::allocate_slots (Slot *new_slots, int new_nslots) 263{ 264 // duplicates new_slots 265 266 // if previously had more slots than currently requested, delete the data from those slots. 267 for (int i = new_nslots; i < nslots; i++) 268 { 269 int **tmp = slots[i].mvals; 270 for (long j = 0; j < nchunks; j++) 271 delete tmp[j]; 272 delete tmp; 273 } 274 if (new_nslots == 0) 275 { 276 nslots = new_nslots; 277 delete[] slots; 278 slots = NULL; 279 return; 280 } 281 282 Slot *old_slots = slots; 283 slots = new Slot[new_nslots]; 284 for (int i = 0; i < new_nslots; i++) 285 { 286 slots[i] = new_slots[i]; // pick up id and vtype 287 if (i < nslots) 288 slots[i].mvals = old_slots[i].mvals; 289 else 290 { 291 if (nchunks == 0) 292 slots[i].mvals = NULL; 293 else 294 { 295 int **ip = new int*[nchunks]; 296 for (long j = 0; j < nchunks; j++) 297 ip[j] = NULL; 298 slots[i].mvals = ip; 299 } 300 } 301 } 302 nslots = new_nslots; 303 delete old_slots; 304} 305 306int 307PathTree::find_slot (int id) 308{ 309 for (int i = 0; i < nslots; i++) 310 if (slots[i].id == id) 311 return i; 312 return -1; 313} 314 315PathTree::NodeIdx 316PathTree::new_Node (NodeIdx anc, Histable *instr, bool leaf) 317{ 318 if (nodes >= nchunks * CHUNKSZ) 319 { 320 long idx = nchunks++; 321 322 // Reallocate Node chunk array 323 Node **old_chunks = chunks; 324 chunks = new Node*[nchunks]; 325 for (long k = 0; k < idx; k++) 326 chunks[k] = old_chunks[k]; 327 delete[] old_chunks; 328 329 // Reallocate metric value chunk arrays. 330 for (int i = 0; i < nslots; i++) 331 { 332 int **mvals = new int*[nchunks]; 333 for (long k = 0; k < idx; k++) 334 { 335 mvals[k] = slots[i].mvals[k]; 336 } 337 delete[] slots[i].mvals; 338 slots[i].mvals = mvals; 339 slots[i].mvals[idx] = NULL; 340 } 341 342 // Allocate new chunk for nodes. 343 // Note that we don't need to allocate new chunks 344 // for metric values at this point as we rely on 345 // lazy allocation. 346 // 347 allocate_chunk (chunks, idx); 348 } 349 NodeIdx node_idx = nodes++; 350 Node *node = NODE_IDX (node_idx); 351 node->ancestor = anc; 352 node->descendants = leaf ? (Vector<NodeIdx>*)NULL : new Vector<NodeIdx>(2); 353 node->instr = instr; 354 Function *func = (Function*) (instr->convertto (Histable::FUNCTION)); 355 node->funclist = fn_map->get (func); 356 fn_map->put (func, node_idx); 357 return node_idx; 358} 359 360PathTree::NodeIdx 361PathTree::find_path (Experiment *exp, DataView *dview, long recIdx) 362{ 363 if (indx_expr != NULL) 364 { 365 Expression::Context ctx (dbev, exp, dview, recIdx); 366 uint64_t idx = indx_expr->eval (&ctx); 367 Histable *cur_obj = dbeSession->createIndexObject (indxtype, idx); 368 cur_obj->set_name_from_context (&ctx); 369 NodeIdx dsc_idx = find_in_desc_htable (root_idx, cur_obj, true); 370 depth = 2; 371 return dsc_idx; 372 } 373 374 bool showAll = dbev->isShowAll (); 375 int t_stack_prop = stack_prop; 376 void *stackId = dview->getObjValue (t_stack_prop, recIdx); 377 NodeIdx node_idx; 378 if (stackId != NULL) 379 { 380 // pathMap does not work with NULL key 381 node_idx = pathMap->get ((uint64_t) stackId); 382 if (node_idx != 0) 383 return node_idx; 384 } 385 Vector<Histable*> *stack = (Vector<Histable*>*)CallStack::getStackPCs (stackId, !showAll); 386 int stack_size = stack->size (); 387 if (stack_size == 0) 388 return root_idx; 389 390 node_idx = root_idx; 391 int thisdepth = 1; 392 393 for (int i = stack_size - 1; i >= 0; i--) 394 { 395 bool leaf = (i == 0); 396 Histable *cur_addr = stack->fetch (i); 397 398 // bail out of loop if load object API-only is set 399 // and this is not the top frame 400 // This is now done in HSTACK if hide is set 401 402 Function *func = (Function*) cur_addr->convertto (Histable::FUNCTION); 403 if (func != NULL) 404 { 405 Module *mod = func->module; 406 LoadObject *lo = mod->loadobject; 407 int segx = lo->seg_idx; 408 if (showAll && dbev->get_lo_expand (segx) == LIBEX_API 409 && i != stack_size - 1) 410 leaf = true; 411 } 412 413 NodeIdx dsc_idx = find_desc_node (node_idx, cur_addr, leaf); 414 thisdepth++; 415 node_idx = dsc_idx; 416 417 // LIBEX_API processing might have set leaf to true 418 if (leaf) 419 break; 420 } 421 if (thisdepth > depth) 422 depth = thisdepth; 423 delete stack; 424 pathMap->put ((uint64_t) stackId, node_idx); 425 return node_idx; 426} 427 428static int 429desc_node_comp (const void *s1, const void *s2, const void *ptree) 430{ 431 PathTree::NodeIdx t1, t2; 432 t1 = *(PathTree::NodeIdx *)s1; 433 t2 = *(PathTree::NodeIdx *)s2; 434 PathTree* Ptree = (PathTree *) ptree; 435 PathTree::Node *n1 = Ptree->NODE_IDX (t1); 436 PathTree::Node *n2 = Ptree->NODE_IDX (t2); 437 Histable *d1 = n1->instr; 438 Histable *d2 = n2->instr; 439 if (d1->id < d2->id) 440 return -1; 441 else if (d1->id > d2->id) 442 return +1; 443 else 444 return 0; 445} 446 447PathTree::NodeIdx 448PathTree::find_in_desc_htable (NodeIdx node_idx, Histable *instr, bool leaf) 449{ 450 unsigned int hash_code = (unsigned int) instr->id % desc_htable_size; 451 Node *node = NODE_IDX (node_idx); 452 hash_node_t *p = NULL; 453 for (p = descHT[hash_code]; p; p = p->next) 454 { 455 Node *dsc = NODE_IDX (p->nd); 456 Histable *dinstr = dsc->instr; 457 if (dinstr->id == instr->id && leaf == IS_LEAF (dsc)) 458 return p->nd; 459 } 460 // Not found 461 NodeIdx dsc_idx = new_Node (node_idx, instr, leaf); 462 node->descendants->append (dsc_idx); 463 p = new hash_node_t (); 464 p->nd = dsc_idx; 465 p->next = descHT[hash_code]; 466 descHT[hash_code] = p; 467 desc_htable_nelem++; 468 469 // time to resize 470 if (desc_htable_nelem == desc_htable_size) 471 { 472 int old_htable_size = desc_htable_size; 473 desc_htable_size = old_htable_size * 2 + 1; 474 hash_node_t **old_htable = descHT; 475 descHT = new hash_node_t*[desc_htable_size]; 476 for (int i = 0; i < desc_htable_size; i++) 477 descHT[i] = NULL; 478 479 for (int i = 0; i < old_htable_size; i++) 480 if (old_htable[i] != NULL) 481 { 482 hash_node *old_p; 483 hash_node_t *hash_p = old_htable[i]; 484 while (hash_p != NULL) 485 { 486 hash_node_t *new_p = new hash_node_t (); 487 new_p->nd = hash_p->nd; 488 Node *dnode = NODE_IDX (hash_p->nd); 489 Histable *dnode_instr = dnode->instr; 490 hash_code = (unsigned int) dnode_instr->id % desc_htable_size; 491 new_p->next = descHT[hash_code]; 492 descHT[hash_code] = new_p; 493 old_p = hash_p; 494 hash_p = hash_p->next; 495 delete old_p; 496 } 497 } 498 delete[] old_htable; 499 } 500 return dsc_idx; 501} 502 503PathTree::NodeIdx 504PathTree::find_desc_node (NodeIdx node_idx, Histable *instr, bool leaf) 505{ 506 // Binary search. All nodes are ordered by Histable::id. 507 508 // We have a special case when two nodes with the same 509 // id value may co-exist: one representing a leaf node and 510 // another one representing a call site. 511 Node *node = NODE_IDX (node_idx); 512 int left = 0; 513 int right = NUM_DESCENDANTS (node) - 1; 514 while (left <= right) 515 { 516 int index = (left + right) / 2; 517 NodeIdx dsc_idx = node->descendants->fetch (index); 518 Node *dsc = NODE_IDX (dsc_idx); 519 Histable *dinstr = dsc->instr; 520 if (instr->id < dinstr->id) 521 right = index - 1; 522 else if (instr->id > dinstr->id) 523 left = index + 1; 524 else if (leaf == IS_LEAF (dsc)) 525 return dsc_idx; 526 else if (leaf) 527 right = index - 1; 528 else 529 left = index + 1; 530 } 531 532 // None was found. Create one. 533 NodeIdx dsc_idx = new_Node (node_idx, instr, leaf); 534 node->descendants->insert (left, dsc_idx); 535 return dsc_idx; 536} 537 538PtreePhaseStatus 539PathTree::process_packets (Experiment *exp, DataView *packets, int data_type) 540{ 541 Expression::Context ctx (dbev, exp); 542 char *progress_bar_msg = NULL; 543 int progress_bar_percent = -1; 544 545 Vector<BaseMetric*> *mlist = dbev->get_all_reg_metrics (); 546 Vector<BaseMetric*> mlist2; 547 StringBuilder stb; 548 for (int midx = 0, mlist_sz = mlist->size (); midx < mlist_sz; ++midx) 549 { 550 BaseMetric *mtr = mlist->fetch (midx); 551 if (mtr->get_packet_type () == data_type && 552 (mtr->get_expr () == NULL || mtr->get_expr ()->passes (&ctx))) 553 { 554 Hwcentry *hwc = mtr->get_hw_ctr (); 555 if (hwc) 556 { 557 stb.setLength (0); 558 // XXX this should be done at metric registration 559 Collection_params *col_params = exp->get_params (); 560 for (int i = 0; i < MAX_HWCOUNT; i++) 561 { 562 // We may have duplicate counters in col_params, 563 // check for all (see 5081284). 564 if (dbe_strcmp (hwc->name, col_params->hw_aux_name[i]) == 0) 565 { 566 if (stb.length () != 0) 567 stb.append (NTXT ("||")); 568 stb.append (NTXT ("HWCTAG==")); 569 stb.append (i); 570 } 571 } 572 if (stb.length () == 0) 573 continue; 574 stb.append (NTXT ("&& ((HWCINT & ")); 575 stb.append ((long long) HWCVAL_ERR_FLAG); 576 stb.append (NTXT (")==0)")); 577 char *s = stb.toString (); 578 mtr->set_cond_spec (s); 579 free (s); 580 } 581 ValueTag vtype = mtr->get_vtype (); 582 switch (vtype) 583 { 584 case VT_INT: 585 case VT_ULLONG: 586 case VT_LLONG: 587 break; // nothing to do 588 default: 589 vtype = VT_ULLONG; // ym: not sure when this would happen 590 break; 591 } 592 allocate_slot (mtr->get_id (), vtype); 593 mlist2.append (mtr); 594 } 595 } 596 597 Slot **mslots = new Slot*[mlist2.size ()]; 598 for (int midx = 0, mlist_sz = mlist2.size (); midx < mlist_sz; ++midx) 599 { 600 BaseMetric *mtr = mlist2.fetch (midx); 601 int id = mtr->get_id (); 602 int slot_ind = find_slot (id); 603 mslots[midx] = SLOT_IDX (slot_ind); 604 } 605 606 for (long i = 0, packets_sz = packets->getSize (); i < packets_sz; ++i) 607 { 608 if (dbeSession->is_interactive ()) 609 { 610 if (NULL == progress_bar_msg) 611 progress_bar_msg = dbe_sprintf (GTXT ("Processing Experiment: %s"), 612 get_basename (exp->get_expt_name ())); 613 int val = (int) (100 * i / packets_sz); 614 if (val > progress_bar_percent) 615 { 616 progress_bar_percent += 10; 617 if (theApplication->set_progress (val, progress_bar_msg) 618 && cancel_ok) 619 { 620 delete[] mslots; 621 return CANCELED; 622 } 623 } 624 } 625 626 NodeIdx path_idx = 0; 627 ctx.put (packets, i); 628 629 for (int midx = 0, mlist_sz = mlist2.size (); midx < mlist_sz; ++midx) 630 { 631 BaseMetric *mtr = mlist2.fetch (midx); 632 if (mtr->get_cond () != NULL && !mtr->get_cond ()->passes (&ctx)) 633 continue; 634 635 int64_t mval = mtr->get_val ()->eval (&ctx); 636 if (mval == 0) 637 continue; 638 if (path_idx == 0) 639 path_idx = find_path (exp, packets, i); 640 NodeIdx node_idx = path_idx; 641 Slot *mslot = mslots[midx]; 642 while (node_idx) 643 { 644 INCREMENT_METRIC (mslot, node_idx, mval); 645 node_idx = NODE_IDX (node_idx)->ancestor; 646 } 647 } 648 } 649 if (dbeSession->is_interactive ()) 650 free (progress_bar_msg); 651 delete[] mslots; 652 if (indx_expr != NULL) 653 root->descendants->sort ((CompareFunc) desc_node_comp, this); 654 return NORMAL; 655} 656 657DataView * 658PathTree::get_filtered_events (int exp_index, int data_type) 659{ 660 if (indx_expr != NULL) 661 { 662 IndexObjType_t *indexObj = dbeSession->getIndexSpace (indxtype); 663 if (indexObj->memObj && data_type != DATA_HWC) 664 return NULL; 665 } 666 return dbev->get_filtered_events (exp_index, data_type); 667} 668 669PtreePhaseStatus 670PathTree::add_experiment (int exp_index) 671{ 672 StringBuilder sb; 673 char *expt_name; 674 char *base_name; 675 Emsg *m; 676 Experiment *experiment = dbeSession->get_exp (exp_index); 677 if (experiment->broken != 0) 678 return NORMAL; 679 status = 0; 680 expt_name = experiment->get_expt_name (); 681 base_name = get_basename (expt_name); 682 683 hrtime_t starttime = gethrtime (); 684 hrtime_t startvtime = gethrvtime (); 685 686 // Experiment::getEndTime was initially implemented as 687 // returning exp->last_event. To preserve the semantics 688 // new Experiment::getLastEvent() is used here. 689 hrtime_t tot_time = experiment->getLastEvent () - experiment->getStartTime (); 690 691 if (!dbev->isShowAll () && (dbev->isShowHideChanged () 692 || dbev->isNewViewMode ())) 693 experiment->resetShowHideStack (); 694 695 // To report experiment index to the user, 696 // start numeration from 1, not 0 697 sb.sprintf (GTXT ("PathTree processing experiment %d (`%s'); duration %lld.%06lld"), 698 exp_index + 1, base_name, 699 tot_time / NANOSEC, (tot_time % NANOSEC / 1000)); 700 m = new Emsg (CMSG_COMMENT, sb); 701 statsq->append (m); 702 703 DataView *prof_packet = get_filtered_events (exp_index, DATA_CLOCK); 704 if (prof_packet && prof_packet->getSize () > 0) 705 { 706 if (process_packets (experiment, prof_packet, DATA_CLOCK) == CANCELED) 707 return CANCELED; 708 long clock_cnt = prof_packet->getSize (); 709 double clock_rate; 710 if (tot_time != 0) 711 clock_rate = (double) clock_cnt / (double) tot_time * (double) NANOSEC; 712 else 713 clock_rate = (double) 0.; 714 if (experiment->timelineavail) 715 sb.sprintf (GTXT (" Processed %ld clock-profile events (%3.2f/sec.)"), 716 clock_cnt, clock_rate); 717 else 718 sb.sprintf (GTXT (" Processed %ld clock-profile events"), clock_cnt); 719 m = new Emsg (CMSG_COMMENT, sb); 720 statsq->append (m); 721 722 // check for statistical validity 723 if ((experiment->timelineavail == true) 724 && !dbev->get_filter_active () && (clock_cnt < MIN_PROF_CNT)) 725 { 726 sb.sprintf (GTXT ("WARNING: too few clock-profile events (%ld) in experiment %d (`%s') for statistical validity"), 727 clock_cnt, exp_index + 1, base_name); 728 m = new Emsg (CMSG_COMMENT, sb); 729 statsq->append (m); 730 } 731 } 732 733 DataView *sync_packet = get_filtered_events (exp_index, DATA_SYNCH); 734 if (sync_packet && sync_packet->getSize () > 0) 735 { 736 if (process_packets (experiment, sync_packet, DATA_SYNCH) == CANCELED) 737 return CANCELED; 738 long sync_cnt = sync_packet->getSize (); 739 sb.sprintf (GTXT (" Processed %ld synctrace events"), sync_cnt); 740 m = new Emsg (CMSG_COMMENT, sb); 741 statsq->append (m); 742 } 743 744 DataView *iotrace_packet = get_filtered_events (exp_index, DATA_IOTRACE); 745 if (iotrace_packet && iotrace_packet->getSize () > 0) 746 { 747 if (process_packets (experiment, iotrace_packet, DATA_IOTRACE) == CANCELED) 748 return CANCELED; 749 long iotrace_cnt = iotrace_packet->getSize (); 750 sb.sprintf (GTXT (" Processed %ld IO trace events"), iotrace_cnt); 751 m = new Emsg (CMSG_COMMENT, sb); 752 statsq->append (m); 753 } 754 755 DataView *hwc_packet = get_filtered_events (exp_index, DATA_HWC); 756 if (hwc_packet && hwc_packet->getSize () > 0) 757 { 758 if (process_packets (experiment, hwc_packet, DATA_HWC) == CANCELED) 759 return CANCELED; 760 long hwc_cnt = hwc_packet->getSize (); 761 double hwc_rate = (double) hwc_cnt / (double) tot_time * (double) NANOSEC; 762 if (experiment->timelineavail) 763 sb.sprintf (GTXT (" Processed %ld hwc-profile events (%3.2f/sec.)"), 764 hwc_cnt, hwc_rate); 765 else 766 sb.sprintf (GTXT (" Processed %ld hwc-profile events"), hwc_cnt); 767 m = new Emsg (CMSG_COMMENT, sb); 768 statsq->append (m); 769 770 // check for statistical validity 771 if (experiment->timelineavail && !dbev->get_filter_active () && (hwc_cnt < MIN_PROF_CNT)) 772 { 773 sb.sprintf (GTXT ("WARNING: too few HW counter profile events (%ld) in experiment %d (`%s') for statistical validity"), 774 hwc_cnt, exp_index + 1, base_name); 775 m = new Emsg (CMSG_COMMENT, sb); 776 statsq->append (m); 777 } 778 } 779 780 DataView *heap_packet = get_filtered_events (exp_index, DATA_HEAP); 781 if (heap_packet && heap_packet->getSize () > 0) 782 { 783 if (process_packets (experiment, heap_packet, DATA_HEAP) == CANCELED) 784 return CANCELED; 785 long heap_cnt = heap_packet->getSize (); 786 sb.sprintf (GTXT (" Processed %ld heaptrace events"), heap_cnt); 787 m = new Emsg (CMSG_COMMENT, sb); 788 statsq->append (m); 789 } 790 791 DataView *race_packet = get_filtered_events (exp_index, DATA_RACE); 792 if (race_packet && race_packet->getSize () > 0) 793 { 794 if (process_packets (experiment, race_packet, DATA_RACE) == CANCELED) 795 return CANCELED; 796 long race_cnt = race_packet->getSize (); 797 sb.sprintf (GTXT (" Processed %ld race access events"), race_cnt); 798 m = new Emsg (CMSG_COMMENT, sb); 799 statsq->append (m); 800 } 801 802 DataView *deadlock_packet = get_filtered_events (exp_index, DATA_DLCK); 803 if (deadlock_packet && deadlock_packet->getSize () > 0) 804 { 805 if (process_packets (experiment, deadlock_packet, DATA_DLCK) == CANCELED) 806 return CANCELED; 807 long race_cnt = deadlock_packet->getSize (); 808 sb.sprintf (GTXT (" Processed %ld race access events"), race_cnt); 809 m = new Emsg (CMSG_COMMENT, sb); 810 statsq->append (m); 811 } 812 813 hrtime_t pathtime = gethrtime () - starttime; 814 hrtime_t pathvtime = gethrvtime () - startvtime; 815 sb.sprintf (GTXT ("PathTree time = %lld.%06lld CPU-time %lld.%06lld\n"), 816 pathtime / NANOSEC, (pathtime % NANOSEC) / 1000, 817 pathvtime / NANOSEC, (pathvtime % NANOSEC) / 1000); 818 m = new Emsg (CMSG_COMMENT, sb); 819 statsq->append (m); 820 return NORMAL; 821} 822 823Hist_data * 824PathTree::compute_metrics (MetricList *mlist, Histable::Type type, 825 Hist_data::Mode mode, Vector<Histable*> *objs, 826 Histable *context, Vector<Histable*> *sel_objs, 827 PtreeComputeOption computeOpt) 828{ 829 VMode view_mode = dbev->get_view_mode (); 830 831 // For displaying disassembly correctly in user mode with openmp 832 if (ptree_internal != NULL && 833 (view_mode == VMODE_EXPERT || 834 (view_mode == VMODE_USER && (type == Histable::INSTR 835 || (dbev->isOmpDisMode () 836 && type == Histable::FUNCTION 837 && mode == Hist_data::CALLEES 838 && computeOpt == COMPUTEOPT_OMP_CALLEE)) 839 ))) 840 return ptree_internal->compute_metrics (mlist, type, mode, objs, context, 841 sel_objs); 842 843 PtreePhaseStatus resetStatus = reset (); 844 845 hist_data = new Hist_data (mlist, type, mode); 846 int nmetrics = mlist->get_items ()->size (); 847 int sort_ind = -1; 848 Hist_data::HistItem *hi; 849 int index; 850 851 if (status != 0 || resetStatus == CANCELED) 852 return hist_data; 853 854 hist_data->set_status (Hist_data::SUCCESS); 855 if (dbeSession->is_interactive () && mode != Hist_data::CALLEES) 856 theApplication->set_progress (0, GTXT ("Constructing Metrics")); 857 858 xlate = new int[nmetrics]; 859 for (int mind = 0; mind < nmetrics; mind++) 860 { 861 Metric *mtr = mlist->get (mind); 862 xlate[mind] = find_slot (mtr->get_id ()); 863 } 864 865 // Compute dynamic metrics 866 obj_list = new Histable*[depth]; 867 if ((type == Histable::LINE || type == Histable::INSTR) 868 && mode == Hist_data::CALLERS) 869 node_list = new Node*[depth]; 870 percent = 0; 871 ndone = 0; 872 if (mode == Hist_data::MODL) 873 { 874 Histable *obj = objs && objs->size () > 0 ? objs->fetch (0) : NULL; 875 if (obj != NULL) 876 { 877 switch (obj->get_type ()) 878 { 879 case Histable::FUNCTION: 880 { 881 Vector<Function*> *funclist = new Vector<Function*>; 882 funclist->append ((Function*) obj); 883 get_metrics (funclist, context); 884 delete funclist; 885 break; 886 } 887 case Histable::MODULE: 888 { 889 Vector<Histable*> *comparableModules = obj->get_comparable_objs (); 890 if (comparableModules != NULL) 891 { 892 Vector<Function*> *functions = new Vector<Function*>; 893 for (int i = 0; i < comparableModules->size (); i++) 894 { 895 Module *mod = (Module*) comparableModules->fetch (i); 896 if (mod) 897 { 898 bool found = false; 899 for (int i1 = 0; i1 < i; i1++) 900 { 901 if (mod == comparableModules->fetch (i1)) 902 { 903 found = true; 904 break; 905 } 906 } 907 if (!found) 908 functions->addAll (mod->functions); 909 } 910 } 911 get_metrics (functions, context); 912 delete functions; 913 } 914 else 915 get_metrics (((Module*) obj)->functions, context); 916 break; 917 } 918 case Histable::SOURCEFILE: 919 get_metrics (((SourceFile *) obj)->get_functions (), context); 920 break; 921 default: 922 DBG (assert (0)); 923 } 924 } 925 } 926 else if (mode == Hist_data::CALLERS) 927 { 928 if (objs && objs->size () > 0) 929 get_clr_metrics (objs); 930 } 931 else if (mode == Hist_data::CALLEES) 932 { 933 if (objs && objs->size () > 0) 934 get_cle_metrics (objs); 935 else // Special case: get root 936 get_cle_metrics (NULL); 937 } 938 else if (mode == Hist_data::SELF) 939 { 940 if (objs->size () == 1) 941 { 942 Histable *obj = objs->fetch (0); 943 if (obj != NULL) 944 { 945 if (obj->get_type () == Histable::LINE) 946 { 947 Vector<Function*> *funclist = new Vector<Function*>; 948 for (DbeLine *dl = (DbeLine*) obj->convertto (Histable::LINE); 949 dl; dl = dl->dbeline_func_next) 950 if (dl->func) 951 funclist->append (dl->func); 952 953 get_self_metrics (obj, funclist, sel_objs); 954 delete funclist; 955 } 956 else if (obj->get_type () == Histable::FUNCTION 957 || obj->get_type () == Histable::INSTR) 958 { 959 // Use shortcut for functions and oth. 960 if (context) 961 { 962 Vector<Function*> *funclist = NULL; 963 if (context->get_type () == Histable::MODULE) 964 funclist = ((Module*) context)->functions->copy (); 965 else 966 { 967 funclist = new Vector<Function*>; 968 funclist->append ((Function*) context); 969 } 970 get_self_metrics (obj, funclist, sel_objs); 971 delete funclist; 972 } 973 else 974 get_self_metrics (objs); 975 } 976 else 977 get_self_metrics (objs); 978 } 979 } 980 else 981 get_self_metrics (objs); 982 } 983 else // Hist_data::ALL 984 get_metrics (root_idx, 0); 985 986 delete[] obj_list; 987 if ((type == Histable::LINE || type == Histable::INSTR) 988 && mode == Hist_data::CALLERS) 989 delete[] node_list; 990 991 // Postprocess; find total 992 for (long mind = 0, sz = mlist->get_items ()->size (); mind < sz; mind++) 993 { 994 Metric *mtr = mlist->get_items ()->get (mind); 995 Metric::SubType subtype = mtr->get_subtype (); 996 ValueTag vtype = mtr->get_vtype (); 997 hist_data->total->value[mind].tag = vtype; 998 999 switch (vtype) 1000 { 1001 // ignoring the following cases (why?) 1002 case VT_SHORT: 1003 case VT_FLOAT: 1004 case VT_HRTIME: 1005 case VT_LABEL: 1006 case VT_ADDRESS: 1007 case VT_OFFSET: 1008 break; 1009 1010 case VT_INT: 1011 // Calculate total as the sum of all values in hist_data for 1012 // ATTRIBUTED metrics only. For all others, use root node values. 1013 // 1014 if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES) 1015 && subtype == Metric::ATTRIBUTED) 1016 { 1017 hist_data->total->value[mind].i = 0; 1018 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1019 { 1020 hist_data->total->value[mind].i += hi->value[mind].i; 1021 } 1022 if (mode == Hist_data::CALLEES) 1023 hist_data->total->value[mind].i += hist_data->gprof_item->value[mind].i; 1024 } 1025 else if (xlate[mind] != -1) 1026 ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]], 1027 root_idx); 1028 break; 1029 1030 case VT_LLONG: 1031 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1032 { 1033 hi->value[mind].tag = vtype; 1034 } 1035 1036 if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES) 1037 && subtype == Metric::ATTRIBUTED) 1038 { 1039 hist_data->total->value[mind].ll = 0; 1040 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1041 { 1042 hist_data->total->value[mind].ll += hi->value[mind].ll; 1043 } 1044 if (mode == Hist_data::CALLEES) 1045 hist_data->total->value[mind].ll += hist_data->gprof_item->value[mind].ll; 1046 } 1047 else if (xlate[mind] != -1) 1048 ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]], root_idx); 1049 break; 1050 1051 case VT_ULLONG: 1052 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1053 { 1054 hi->value[mind].tag = vtype; 1055 } 1056 if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES) 1057 && subtype == Metric::ATTRIBUTED) 1058 { 1059 hist_data->total->value[mind].ull = 0; 1060 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1061 { 1062 hist_data->total->value[mind].ull += hi->value[mind].ull; 1063 } 1064 if (mode == Hist_data::CALLEES) 1065 hist_data->total->value[mind].ull += hist_data->gprof_item->value[mind].ull; 1066 } 1067 else if (xlate[mind] != -1) 1068 ASN_METRIC_VAL (hist_data->total->value[mind], slots[xlate[mind]], root_idx); 1069 break; 1070 1071 case VT_DOUBLE: 1072 double prec = mtr->get_precision (); 1073 ValueTag vt = (xlate[mind] != -1) ? slots[xlate[mind]].vtype : VT_INT; 1074 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1075 { 1076 double val = (vt == VT_LLONG ? hi->value[mind].ll : 1077 (vt == VT_ULLONG ? hi->value[mind].ull 1078 : hi->value[mind].i)); 1079 hi->value[mind].tag = vtype; 1080 hi->value[mind].d = val / prec; 1081 } 1082 1083 if ((mode == Hist_data::CALLERS || mode == Hist_data::CALLEES) 1084 && subtype == Metric::ATTRIBUTED) 1085 { 1086 hist_data->total->value[mind].d = 0.0; 1087 Vec_loop (Hist_data::HistItem*, hist_data->hist_items, index, hi) 1088 { 1089 hist_data->total->value[mind].d += hi->value[mind].d; 1090 } 1091 if (mode == Hist_data::CALLEES) 1092 hist_data->total->value[mind].d += 1093 (double) (vt == VT_LLONG ? hist_data->gprof_item->value[mind].ll : 1094 (vt == VT_ULLONG ? hist_data->gprof_item->value[mind].ull : 1095 hist_data->gprof_item->value[mind].i)) / prec; 1096 } 1097 else if (xlate[mind] != -1) 1098 { 1099 TValue& total = hist_data->total->value[mind]; 1100 ASN_METRIC_VAL (total, slots[xlate[mind]], root_idx); 1101 double val = (vt == VT_LLONG ? total.ll : 1102 (vt == VT_ULLONG ? total.ll : total.i)); 1103 total.d = val / prec; 1104 } 1105 break; 1106 } 1107 } 1108 delete[] xlate; 1109 1110 // Determine by which metric to sort if any 1111 bool rev_sort = mlist->get_sort_rev (); 1112 for (long mind = 0, sz = mlist->get_items ()->size (); mind < sz; mind++) 1113 { 1114 Metric *mtr = mlist->get_items ()->get (mind); 1115 if (mlist->get_sort_ref_index () == mind) 1116 sort_ind = mind; 1117 1118 switch (mtr->get_type ()) 1119 { 1120 case BaseMetric::SIZES: 1121 Vec_loop (Hist_data::HistItem *, hist_data->hist_items, index, hi) 1122 { 1123 Histable *h = mtr->get_comparable_obj (hi->obj); 1124 hi->value[mind].tag = VT_LLONG; 1125 hi->value[mind].ll = h ? h->get_size () : 0; 1126 } 1127 break; 1128 case BaseMetric::ADDRESS: 1129 Vec_loop (Hist_data::HistItem *, hist_data->hist_items, index, hi) 1130 { 1131 Histable *h = mtr->get_comparable_obj (hi->obj); 1132 hi->value[mind].tag = VT_ADDRESS; 1133 hi->value[mind].ll = h ? h->get_addr () : 0; 1134 } 1135 break; 1136 case BaseMetric::DERIVED: 1137 { 1138 Definition *def = mtr->get_definition (); 1139 long *map = def->get_map (); 1140 for (long i1 = 0, sz1 = hist_data->hist_items->size (); i1 < sz1; i1++) 1141 { 1142 /* Hist_data::HistItem * */hi = hist_data->hist_items->get (i1); 1143 hi->value[mind].tag = VT_DOUBLE; 1144 hi->value[mind].d = def->eval (map, hi->value); 1145 } 1146 hist_data->total->value[mind].tag = VT_DOUBLE; 1147 hist_data->total->value[mind].d = def->eval (map, hist_data->total->value); 1148 } 1149 break; 1150 default: 1151 break; 1152 } 1153 } 1154 1155 hist_data->sort (sort_ind, rev_sort); 1156 hist_data->compute_minmax (); 1157 if (dbeSession->is_interactive () && mode != Hist_data::CALLERS) 1158 theApplication->set_progress (0, GTXT ("")); 1159 1160#if DEBUG_FTREE 1161 if (ftree_hist_data) 1162 { 1163 bool matches = ftree_debug_match_hist_data (hist_data, ftree_hist_data); 1164 if (!matches) 1165 assert (false); 1166 delete hist_data; 1167 hist_data = ftree_hist_data; // return the debug version 1168 } 1169#endif 1170 return hist_data; 1171} 1172 1173#if DEBUG_FTREE 1174bool 1175PathTree::ftree_debug_match_hist_data (Hist_data *data /* ref */, 1176 Hist_data *data_tmp) 1177{ 1178 if (data->get_status () != Hist_data::SUCCESS) 1179 { 1180 DBG (assert (false)); 1181 return false; 1182 } 1183 if (data == NULL && data != data_tmp) 1184 { 1185 DBG (assert (false)); 1186 return false; 1187 } 1188 1189 MetricList *mlist; 1190 mlist = data->get_metric_list (); 1191 MetricList *mlist_tmp; 1192 mlist_tmp = data_tmp->get_metric_list (); 1193 if (mlist->size () != mlist_tmp->size ()) 1194 { 1195 DBG (assert (false)); 1196 return false; 1197 } 1198 1199 // Get table size: count visible metrics 1200 int nitems = data->size (); 1201 if (data->size () != data_tmp->size ()) 1202 { 1203 DBG (assert (false)); 1204 return false; 1205 } 1206 1207 for (int i = 0; i < nitems; ++i) 1208 { 1209 Hist_data::HistItem *item = data->fetch (i); 1210 Hist_data::HistItem *item_tmp = data_tmp->fetch (i); 1211 if (item->obj->id != item_tmp->obj->id) 1212 { 1213 DBG (assert (false)); 1214 return false; 1215 } 1216 } 1217 1218 for (long i = 0, sz = mlist->size (); i < sz; i++) 1219 { 1220 long met_ind = i; 1221 Metric *mitem = mlist->get (i); 1222 Metric *mitem_tmp = mlist_tmp->get (i); 1223 1224 if (mitem->get_id () != mitem_tmp->get_id ()) 1225 { 1226 DBG (assert (false)); 1227 return false; 1228 } 1229 if (mitem->get_visbits () != mitem_tmp->get_visbits ()) 1230 { 1231 DBG (assert (false)); 1232 return false; 1233 } 1234 if (mitem->get_vtype () != mitem_tmp->get_vtype ()) 1235 { 1236 DBG (assert (false)); 1237 return false; 1238 } 1239 1240 if (!mitem->is_visible () && !mitem->is_tvisible () 1241 && !mitem->is_pvisible ()) 1242 continue; 1243 // table->append(dbeGetTableDataOneColumn(data, i)); 1244 for (long row = 0, sz_row = data->size (); row < sz_row; row++) 1245 { 1246 Metric *m = mitem; 1247 TValue res; 1248 TValue res_tmp; 1249 TValue *v = data->get_value (&res, met_ind, row); 1250 TValue *v_tmp = data_tmp->get_value (&res_tmp, met_ind, row); 1251 if ((m->get_visbits () & VAL_RATIO) != 0) 1252 { 1253 if (v->tag != VT_LABEL) 1254 { 1255 if (v->to_double () != v_tmp->to_double ()) 1256 { 1257 DBG (assert (false)); 1258 return false; 1259 } 1260 } 1261 continue; 1262 } 1263 switch (m->get_vtype ()) 1264 { 1265 case VT_DOUBLE: 1266 { 1267 double diff = v->d - v_tmp->d; 1268 if (diff < 0) diff = -diff; 1269 if (diff > 0.0001) 1270 { 1271 DBG (assert (false)); 1272 return false; 1273 } 1274 else 1275 DBG (assert (true)); 1276 break; 1277 } 1278 case VT_INT: 1279 if (v->i != v_tmp->i) 1280 { 1281 DBG (assert (false)); 1282 return false; 1283 } 1284 break; 1285 case VT_ULLONG: 1286 case VT_LLONG: 1287 case VT_ADDRESS: 1288 if (v->ll != v_tmp->ll) 1289 { 1290 DBG (assert (false)); 1291 return false; 1292 } 1293 break; 1294 1295 case VT_LABEL: 1296 if (dbe_strcmp (v->l, v_tmp->l)) 1297 { 1298 DBG (assert (false)); 1299 return false; 1300 } 1301 break; 1302 default: 1303 DBG (assert (false)); 1304 return false; 1305 } 1306 } 1307 } 1308 return true; 1309} 1310#endif 1311 1312Histable * 1313PathTree::get_hist_func_obj (Node *node) 1314{ 1315 LoadObject *lo; 1316 Function *func; 1317 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1318 // LIBRARY VISIBILITY 1319 lo = func->module->loadobject; 1320 if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE) 1321 return lo->get_hide_function (); 1322 return get_compare_obj (func); 1323} 1324 1325Histable * 1326PathTree::get_hist_obj (Node *node, Histable* context) 1327{ 1328 LoadObject *lo; 1329 Function *func; 1330 switch (hist_data->type) 1331 { 1332 case Histable::INSTR: 1333 if (hist_data->mode == Hist_data::MODL) 1334 { 1335 if (node->instr->get_type () != Histable::INSTR) 1336 return NULL; 1337 } 1338 else 1339 { 1340 // LIBRARY VISIBILITY 1341 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1342 lo = func->module->loadobject; 1343 if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE) 1344 return lo->get_hide_function (); 1345 } 1346 return node->instr; 1347 1348 case Histable::LINE: 1349 if (hist_data->mode != Hist_data::MODL) 1350 { 1351 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1352 lo = func->module->loadobject; 1353 // LIBRARY VISIBILITY 1354 if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE) 1355 return lo->get_hide_function (); 1356 } 1357 // For openmp user mode - the stack is already made with dbelines, 1358 // no need to convert it 1359 if (node->instr->get_type () == Histable::LINE) 1360 return node->instr; 1361 return node->instr->convertto (Histable::LINE, context); 1362 1363 case Histable::FUNCTION: 1364 if (pathTreeType == PATHTREE_INTERNAL_FUNCTREE && node->ancestor != 0) 1365 func = (Function*) node->instr; 1366 else 1367 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1368 lo = func->module->loadobject; 1369 // LIBRARY VISIBILITY 1370 if (dbev->get_lo_expand (lo->seg_idx) == LIBEX_HIDE) 1371 return lo->get_hide_function (); 1372 return get_compare_obj (func); 1373 case Histable::MODULE: 1374 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1375 return func->module; 1376 case Histable::LOADOBJECT: 1377 func = (Function*) (node->instr->convertto (Histable::FUNCTION)); 1378 return func->module->loadobject; 1379 case Histable::INDEXOBJ: 1380 case Histable::MEMOBJ: 1381 return node->instr; 1382 default: 1383 DBG (assert (0)); 1384 } 1385 return NULL; 1386} 1387 1388Histable * 1389PathTree::get_compare_obj (Histable *obj) 1390{ 1391 if (obj && dbev->comparingExperiments ()) 1392 obj = dbev->get_compare_obj (obj); 1393 return obj; 1394} 1395 1396void 1397PathTree::get_metrics (NodeIdx node_idx, int dpth) 1398{ 1399 Node *node = NODE_IDX (node_idx); 1400 Histable *cur_obj = get_hist_obj (node); 1401 obj_list[dpth] = cur_obj; 1402 1403 // Check for recursion (inclusive metrics) 1404 int incl_ok = 1; 1405 for (int i = dpth - 1; i >= 0; i--) 1406 if (cur_obj == obj_list[i]) 1407 { 1408 incl_ok = 0; 1409 break; 1410 } 1411 1412 // Check for leaf nodes (exclusive metrics) 1413 int excl_ok = 0; 1414 if (IS_LEAF (node) || node == NODE_IDX (root_idx)) 1415 excl_ok = 1; 1416 1417 // We shouldn't eliminate empty subtrees here because 1418 // we create the list of hist items dynamically and want 1419 // one for each object in the tree. 1420 cur_obj = get_compare_obj (cur_obj); 1421 Hist_data::HistItem *hi = hist_data->append_hist_item (cur_obj); 1422 DBG (assert (hi != NULL)); 1423 1424 MetricList *mlist = hist_data->get_metric_list (); 1425 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 1426 { 1427 if (xlate[ind] == -1) 1428 continue; 1429 Metric *mtr = mlist->get (ind); 1430 Metric::SubType subtype = mtr->get_subtype (); 1431 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 1432 continue; 1433 1434 switch (subtype) 1435 { 1436 case Metric::INCLUSIVE: 1437 if (incl_ok && hi) 1438 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1439 break; 1440 case Metric::EXCLUSIVE: 1441 if (excl_ok && hi) 1442 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1443 break; 1444 // ignoring the following cases (why?) 1445 case Metric::STATIC: 1446 case Metric::ATTRIBUTED: 1447 break; 1448 case Metric::DATASPACE: 1449 if (hi) 1450 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1451 break; 1452 } 1453 } 1454 1455 if (dbeSession->is_interactive ()) 1456 { 1457 ndone++; 1458 int new_percent = 95 * ndone / nodes; 1459 if (new_percent > percent) 1460 { 1461 percent = new_percent; 1462 theApplication->set_progress (percent, NULL); 1463 } 1464 } 1465 1466 // Recursively process all descendants 1467 int index; 1468 int dsize = NUM_DESCENDANTS (node); 1469 for (index = 0; index < dsize; index++) 1470 get_metrics (node->descendants->fetch (index), dpth + 1); 1471} 1472 1473void 1474PathTree::get_clr_metrics (Vector<Histable*> *objs, NodeIdx node_idx, 1475 int pmatch, int dpth) 1476{ 1477 Node *node = NODE_IDX (node_idx); 1478 Histable *cur_obj; 1479 if (hist_data->type == Histable::LINE || hist_data->type == Histable::INSTR) 1480 { 1481 cur_obj = get_hist_func_obj (node); 1482 node_list[dpth] = node; 1483 } 1484 else 1485 cur_obj = get_hist_obj (node); 1486 obj_list[dpth] = cur_obj; 1487 1488 bool match = false; 1489 int nobj = objs->size (); 1490 if (dpth + 1 >= nobj) 1491 { 1492 match = true; 1493 for (int i = 0; i < nobj; ++i) 1494 { 1495 if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i]) 1496 { 1497 match = false; 1498 break; 1499 } 1500 } 1501 } 1502 1503 Hist_data::HistItem *hi = NULL; 1504 Hist_data::HistItem *hi_adj = NULL; 1505 if (match && dpth >= nobj) 1506 { 1507 if (hist_data->type == Histable::LINE 1508 || hist_data->type == Histable::INSTR) 1509 hi = hist_data->append_hist_item (get_hist_obj (node_list[dpth - nobj])); 1510 else 1511 hi = hist_data->append_hist_item (obj_list[dpth - nobj]); 1512 1513 if (pmatch >= 0 && pmatch >= nobj) 1514 { 1515 if (hist_data->type == Histable::LINE 1516 || hist_data->type == Histable::INSTR) 1517 hi_adj = hist_data->append_hist_item (get_hist_obj ( 1518 node_list[pmatch - nobj])); 1519 else 1520 hi_adj = hist_data->append_hist_item (obj_list[pmatch - nobj]); 1521 } 1522 } 1523 1524 if (hi != NULL) 1525 { 1526 MetricList *mlist = hist_data->get_metric_list (); 1527 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 1528 { 1529 if (xlate[ind] == -1) 1530 continue; 1531 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 1532 continue; 1533 Metric *mtr = mlist->get (ind); 1534 Metric::SubType subtype = mtr->get_subtype (); 1535 1536 switch (subtype) 1537 { 1538 case Metric::ATTRIBUTED: 1539 if (hi) 1540 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1541 if (hi_adj) 1542 SUB_METRIC_VAL (hi_adj->value[ind], slots[xlate[ind]], node_idx); 1543 break; 1544 case Metric::STATIC: 1545 case Metric::EXCLUSIVE: 1546 case Metric::INCLUSIVE: 1547 case Metric::DATASPACE: 1548 break; 1549 } 1550 } 1551 } 1552 1553 // Recursively process all descendants 1554 int dsize = NUM_DESCENDANTS (node); 1555 for (int index = 0; index < dsize; index++) 1556 get_clr_metrics (objs, node->descendants->fetch (index), 1557 match ? dpth : pmatch, dpth + 1); 1558} 1559 1560void 1561PathTree::get_clr_metrics (Vector<Histable*> *objs) 1562{ 1563 get_clr_metrics (objs, root_idx, -1, 0); 1564} 1565 1566void 1567PathTree::get_cle_metrics (Vector<Histable*> *objs, NodeIdx node_idx, int pcle, 1568 int pmatch, int dpth) 1569{ 1570 Node *node = NODE_IDX (node_idx); 1571 Histable *cur_obj = get_hist_obj (node); 1572 obj_list[dpth] = cur_obj; 1573 1574 bool match = false; 1575 int nobj = objs->size (); 1576 if (dpth + 1 >= nobj) 1577 { 1578 match = true; 1579 for (int i = 0; i < nobj; ++i) 1580 if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i]) 1581 { 1582 match = false; 1583 break; 1584 } 1585 } 1586 1587 Hist_data::HistItem *hi = NULL; 1588 Hist_data::HistItem *hi_adj = NULL; 1589 if (pmatch >= 0 && dpth == pmatch + 1) 1590 hi = hist_data->append_hist_item (cur_obj); 1591 if (match && IS_LEAF (node)) 1592 hi = hist_data->gprof_item; 1593 if (pcle >= 0) 1594 hi_adj = hist_data->append_hist_item (obj_list[pcle]); 1595 1596 if (hi != NULL) 1597 { 1598 MetricList *mlist = hist_data->get_metric_list (); 1599 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 1600 { 1601 if (xlate[ind] == -1) 1602 continue; 1603 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 1604 continue; 1605 Metric *mtr = mlist->get (ind); 1606 Metric::SubType subtype = mtr->get_subtype (); 1607 if (subtype == Metric::ATTRIBUTED) 1608 { 1609 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1610 if (hi_adj) 1611 SUB_METRIC_VAL (hi_adj->value[ind], slots[xlate[ind]], node_idx); 1612 } 1613 } 1614 } 1615 1616 // Recursively process all descendants 1617 int dsize = NUM_DESCENDANTS (node); 1618 for (int index = 0; index < dsize; index++) 1619 get_cle_metrics (objs, node->descendants->fetch (index), 1620 pmatch >= 0 && dpth == pmatch + 1 ? dpth : pcle, 1621 match ? dpth : pmatch, dpth + 1); 1622} 1623 1624void 1625PathTree::get_cle_metrics (Vector<Histable*> *objs, NodeIdx node_idx, int dpth) 1626{ 1627 Node *node = NODE_IDX (node_idx); 1628 Histable *cur_obj = get_hist_obj (node); 1629 Hist_data::HistItem *hi = NULL; 1630 if (NULL == objs) // Special case: get root 1631 hi = hist_data->append_hist_item (cur_obj); 1632 else 1633 { 1634 if (dpth == objs->size ()) 1635 hi = hist_data->append_hist_item (cur_obj); 1636 else if (cur_obj == objs->fetch (dpth)) 1637 { 1638 // Recursively process all descendants 1639 int dsize = NUM_DESCENDANTS (node); 1640 for (int index = 0; index < dsize; index++) 1641 get_cle_metrics (objs, node->descendants->fetch (index), dpth + 1); 1642 if (dpth == objs->size () - 1 && dsize == 0) 1643 hi = hist_data->gprof_item; 1644 } 1645 } 1646 1647 if (hi != NULL) 1648 { 1649 MetricList *mlist = hist_data->get_metric_list (); 1650 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 1651 { 1652 if (xlate[ind] == -1) 1653 continue; 1654 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 1655 continue; 1656 Metric *mtr = mlist->get (ind); 1657 Metric::SubType subtype = mtr->get_subtype (); 1658 if (subtype == Metric::ATTRIBUTED) 1659 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 1660 } 1661 } 1662} 1663 1664void 1665PathTree::ftree_reset () 1666{ 1667 if (pathTreeType == PATHTREE_MAIN && indxtype < 0) 1668 { 1669 reset (); 1670 if (ftree_needs_update) 1671 { 1672 if (ftree_internal == NULL) 1673 { 1674 ftree_internal = new PathTree (dbev, indxtype, 1675 PATHTREE_INTERNAL_FUNCTREE); 1676 if (ftree_internal == NULL) 1677 return; 1678 } 1679 ftree_internal->ftree_build (this); 1680 ftree_needs_update = false; 1681 } 1682 } 1683} 1684 1685void 1686PathTree::ftree_build (PathTree * mstr) 1687{ 1688 fini (); 1689 init (); 1690 allocate_slots (mstr->slots, mstr->nslots); 1691 ftree_build (mstr, mstr->root_idx, root_idx); 1692 depth = mstr->depth; 1693 depth_map_build (); 1694} 1695 1696#if DEBUG_FTREE // possibly TBR 1697void 1698PathTree::ftree_dump () 1699{ 1700 hrtime_t starttime, endtime; 1701 int nmetrics = 1; 1702 // int nmetrics = nslots; 1703 for (int kk = 0; kk < nmetrics; kk++) 1704 { 1705 int id = slots[kk].id; 1706 starttime = gethrtime (); 1707 long nodecnt = 0; 1708 for (int ii = 0; ii < depth; ii++) 1709 { 1710 Vector<Vector<void*>*> *tmp = (Vector<Vector<void*>*>*)get_ftree_level 1711 (id, ii); 1712 if (tmp == NULL) 1713 continue; 1714 long sz = tmp->get (0)->size (); 1715 nodecnt += sz; 1716#if 1 1717 // fprintf(stderr, "... finished (%ld nodes)\n", sz); 1718#else 1719 Vector<NodeIdx> *nodeIdxList = (Vector<NodeIdx> *)tmp->get (0); 1720 Vector<NodeIdx> *ancestorNodeIdxList = (Vector<NodeIdx> *)tmp->get (1); 1721 Vector<uint64_t> *idList = (Vector<uint64_t> *)tmp->get (2); 1722 Vector<uint64_t> *vals = (Vector<uint64_t> *)tmp->get (3); 1723 for (int jj = 0; jj < sz; jj++) 1724 fprintf (stderr, " ...%d:%d node=%ld, anc=%ld, id=%llu, val=%llu\n", 1725 sz, jj, nodeIdxList->get (jj), 1726 ancestorNodeIdxList->get (jj), 1727 idList->get (jj), vals->get (jj)); 1728#endif 1729 destroy (tmp); 1730 } 1731 endtime = gethrtime (); 1732 fprintf (stderr, "====================== %ld nodes time=%llu\n", 1733 nodecnt, (endtime - starttime) / 1000 / 1000); 1734 } 1735} 1736#endif 1737 1738// ftree: translate mstr Histable::INSTR to Histable::FUNCTION 1739void 1740PathTree::ftree_build (PathTree *mstr, NodeIdx mstr_node_idx, 1741 NodeIdx local_node_idx) 1742{ 1743 // requires: slots, nslots 1744 Node *mstr_node = mstr->NODE_IDX (mstr_node_idx); 1745 int dsize = NUM_DESCENDANTS (mstr_node); 1746 1747 // Add metrics 1748 for (int i = 0; i < nslots; i++) 1749 { 1750 if (i >= mstr->nslots) 1751 continue; //weird 1752 if (slots[i].vtype != mstr->slots[i].vtype) 1753 continue; //weird 1754 TValue val; 1755 val.ll = 0; 1756 mstr->ASN_METRIC_VAL (val, mstr->slots[i], mstr_node_idx); 1757 int64_t mval; 1758 switch (slots[i].vtype) 1759 { 1760 case VT_ULLONG: 1761 case VT_LLONG: 1762 mval = val.ll; 1763 break; 1764 case VT_INT: 1765 mval = val.i; 1766 break; 1767 default: 1768 mval = 0; 1769 break; 1770 } 1771 if (mval) 1772 { 1773 Slot * mslot = SLOT_IDX (i); 1774 if (mslot) 1775 INCREMENT_METRIC (mslot, local_node_idx, mval); 1776 } 1777 } 1778 1779 // Recursively process all descendants 1780 for (int index = 0; index < dsize; index++) 1781 { 1782 NodeIdx mstr_desc_node_idx = mstr_node->descendants->fetch (index); 1783 Node *mstr_desc_node = mstr->NODE_IDX (mstr_desc_node_idx); 1784 Function *func = (Function*) mstr_desc_node->instr->convertto (Histable::FUNCTION); 1785 int mstr_desc_dsize = NUM_DESCENDANTS (mstr_desc_node); 1786 bool leaf = (mstr_desc_dsize == 0); 1787 NodeIdx local_desc_node_idx = find_desc_node (local_node_idx, func, leaf); 1788 ftree_build (mstr, mstr_desc_node_idx, local_desc_node_idx); 1789 } 1790} 1791 1792void 1793PathTree::depth_map_build () 1794{ 1795 destroy (depth_map); 1796 depth_map = new Vector<Vector<NodeIdx>*>(depth); 1797 if (depth) 1798 { 1799 depth_map->put (depth - 1, 0); // fill vector with nulls 1800 depth_map_build (root_idx, 0); 1801 } 1802} 1803 1804void 1805PathTree::depth_map_build (NodeIdx node_idx, int dpth) 1806{ 1807 Node *node = NODE_IDX (node_idx); 1808 1809 Vector<NodeIdx> *node_idxs = depth_map->get (dpth); 1810 if (node_idxs == NULL) 1811 { 1812 node_idxs = new Vector<NodeIdx>(); 1813 depth_map->store (dpth, node_idxs); 1814 } 1815 node_idxs->append (node_idx); 1816 1817 // Recursively process all descendants 1818 int dsize = NUM_DESCENDANTS (node); 1819 for (int index = 0; index < dsize; index++) 1820 { 1821 NodeIdx desc_node_idx = node->descendants->fetch (index); 1822 depth_map_build (desc_node_idx, dpth + 1); 1823 } 1824} 1825 1826int 1827PathTree::get_ftree_depth () 1828{ // external use only 1829 ftree_reset (); 1830 if (!ftree_internal) 1831 return 0; 1832 return ftree_internal->get_depth (); 1833} 1834 1835Vector<Function*>* 1836PathTree::get_ftree_funcs () 1837{ // external use only 1838 ftree_reset (); 1839 if (!ftree_internal) 1840 return NULL; 1841 return ftree_internal->get_funcs (); 1842} 1843 1844Vector<Function*>* 1845PathTree::get_funcs () 1846{ 1847 // get unique functions 1848 if (fn_map == NULL) 1849 return NULL; 1850 return fn_map->keySet (); 1851} 1852 1853Vector<void*>* 1854PathTree::get_ftree_level (BaseMetric *bm, int dpth) 1855{ // external use only 1856 ftree_reset (); 1857 if (!ftree_internal) 1858 return NULL; 1859 return ftree_internal->get_level (bm, dpth); 1860} 1861 1862Vector<void*>* 1863PathTree::get_level (BaseMetric *bm, int dpth) 1864{ 1865 // Nodes at tree depth dpth 1866 if (dpth < 0 || dpth >= depth) 1867 return NULL; 1868 if (depth_map == NULL) 1869 return NULL; 1870 Vector<NodeIdx> *node_idxs = depth_map->get (dpth); 1871 return get_nodes (bm, node_idxs); 1872} 1873 1874Vector<void*>* 1875PathTree::get_ftree_node_children (BaseMetric *bm, NodeIdx node_idx) 1876{ // external use only 1877 ftree_reset (); 1878 if (!ftree_internal) 1879 return NULL; 1880 return ftree_internal->get_node_children (bm, node_idx); 1881} 1882 1883Vector<void*>* 1884PathTree::get_node_children (BaseMetric *bm, NodeIdx node_idx) 1885{ 1886 // Nodes that are children of node_idx 1887 if (depth_map == NULL) 1888 return NULL; 1889 if (node_idx == 0) // special case for root 1890 return get_nodes (bm, depth_map->get (0)); 1891 if (node_idx < 0 || node_idx >= nodes) 1892 return NULL; 1893 Node *node = NODE_IDX (node_idx); 1894 if (node == NULL) 1895 return NULL; 1896 Vector<NodeIdx> *node_idxs = node->descendants; 1897 return get_nodes (bm, node_idxs); 1898} 1899 1900Vector<void*>* 1901PathTree::get_nodes (BaseMetric *bm, Vector<NodeIdx> *node_idxs) 1902{ // used for ftree 1903 // capture info for node_idxs: 1904 // node's idx 1905 // node->ancestor idx 1906 // node->instr->id 1907 // mind metric value // in the future, could instead accept vector of mind 1908 if (node_idxs == NULL) 1909 return NULL; 1910 long sz = node_idxs->size (); 1911 if (sz <= 0) 1912 return NULL; 1913 1914 bool calculate_metric = false; 1915 ValueTag vtype; 1916 int slot_idx; 1917 double prec; 1918 if (bm != NULL) 1919 { 1920 int mind = bm->get_id (); 1921 slot_idx = find_slot (mind); // may be -1 (CPI and IPC) 1922 prec = bm->get_precision (); 1923 vtype = bm->get_vtype (); 1924 } 1925 else 1926 { 1927 slot_idx = -1; 1928 prec = 1.0; 1929 vtype = VT_INT; 1930 } 1931 1932 if (slot_idx >= 0) 1933 { 1934 switch (vtype) 1935 { 1936 case VT_ULLONG: 1937 case VT_LLONG: 1938 case VT_INT: 1939 if (slots[slot_idx].vtype == vtype) 1940 calculate_metric = true; 1941 else 1942 DBG (assert (false)); 1943 break; 1944 case VT_DOUBLE: 1945 calculate_metric = true; 1946 break; 1947 default: 1948 break; 1949 } 1950 } 1951 1952 Vector<void*> *results = new Vector<void*>(4); 1953 if (!calculate_metric) 1954 results->store (3, NULL); 1955 else 1956 { 1957 // Code below cribbed from Dbe.cc:dbeGetTableDataV2Data. 1958 // TBD: possibly create an intermediate HistData and instead call that routine 1959 switch (vtype) 1960 { 1961 case VT_ULLONG: 1962 case VT_LLONG: 1963 { 1964 Vector<long long> *vals = new Vector<long long>(sz); 1965 for (long i = 0; i < sz; i++) 1966 { 1967 NodeIdx node_idx = node_idxs->get (i); 1968 TValue val; 1969 val.ll = 0; 1970 ASN_METRIC_VAL (val, slots[slot_idx], node_idx); 1971 vals->append (val.ll); 1972 } 1973 results->store (3, vals); 1974 break; 1975 } 1976 case VT_DOUBLE: 1977 { 1978 Vector<double> *vals = new Vector<double>(sz); 1979 TValue val; 1980 val.tag = slots[slot_idx].vtype; // required for to_double(); 1981 for (long i = 0; i < sz; i++) 1982 { 1983 NodeIdx node_idx = node_idxs->get (i); 1984 val.ll = 0; 1985 ASN_METRIC_VAL (val, slots[slot_idx], node_idx); 1986 double dval = val.to_double (); 1987 dval /= prec; 1988 vals->append (dval); 1989 } 1990 results->store (3, vals); 1991 break; 1992 } 1993 case VT_INT: 1994 { 1995 Vector<int> *vals = new Vector<int>(sz); 1996 for (long i = 0; i < sz; i++) 1997 { 1998 NodeIdx node_idx = node_idxs->get (i); 1999 TValue val; 2000 val.i = 0; 2001 ASN_METRIC_VAL (val, slots[slot_idx], node_idx); 2002 vals->append (val.i); 2003 } 2004 results->store (3, vals); 2005 break; 2006 } 2007 default: 2008 results->store (3, NULL); 2009 break; 2010 } 2011 } 2012 2013 Vector<int> *nodeIdxList = new Vector<int>(sz); 2014 Vector<int> *ancestorNodeIdxList = new Vector<int>(sz); 2015 Vector<uint64_t> *idList = new Vector<uint64_t>(sz); 2016 for (long i = 0; i < sz; i++) 2017 { 2018 NodeIdx node_idx = node_idxs->get (i); 2019 Node *node = NODE_IDX (node_idx); 2020 NodeIdx ancestor_idx = node->ancestor; 2021 Histable *func = node->instr; 2022 nodeIdxList->append (node_idx); 2023 ancestorNodeIdxList->append (ancestor_idx); 2024 idList->append (func->id); 2025 } 2026 2027 results->store (0, nodeIdxList); 2028 results->store (1, ancestorNodeIdxList); 2029 results->store (2, idList); 2030 return results; 2031} 2032 2033void 2034PathTree::get_cle_metrics (Vector<Histable*> *objs) 2035{ 2036 if (NULL == objs || objs->fetch (0) == get_hist_obj (NODE_IDX (root_idx))) 2037 // Call Tree optimization 2038 get_cle_metrics (objs, root_idx, 0); 2039 else 2040 // General case 2041 get_cle_metrics (objs, root_idx, -1, -1, 0); 2042} 2043 2044void 2045PathTree::get_metrics (Vector<Function*> *functions, Histable *context) 2046{ 2047 Function *fitem; 2048 int excl_ok, incl_ok; 2049 NodeIdx node_idx; 2050 Node *node, *anc; 2051 int index; 2052 2053 Vec_loop (Function*, functions, index, fitem) 2054 { 2055 node_idx = fn_map->get (fitem); 2056 for (; node_idx; node_idx = node->funclist) 2057 { 2058 node = NODE_IDX (node_idx); 2059 Histable *h_obj = get_hist_obj (node, context); 2060 if (h_obj == NULL) 2061 continue; 2062 2063 // Check for recursion (inclusive metrics) 2064 incl_ok = 1; 2065 for (anc = NODE_IDX (node->ancestor); anc; 2066 anc = NODE_IDX (anc->ancestor)) 2067 { 2068 if (h_obj == get_hist_obj (anc, context)) 2069 { 2070 incl_ok = 0; 2071 break; 2072 } 2073 } 2074 2075 // Check for leaf nodes (exclusive metrics) 2076 excl_ok = 0; 2077 if (IS_LEAF (node)) 2078 excl_ok = 1; 2079 2080 h_obj = get_compare_obj (h_obj); 2081 Hist_data::HistItem *hi = hist_data->append_hist_item (h_obj); 2082 2083 if (!excl_ok) 2084 hist_data->get_callsite_mark ()->put (h_obj, 1); 2085 MetricList *mlist = hist_data->get_metric_list (); 2086 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 2087 { 2088 if (xlate[ind] == -1) 2089 continue; 2090 Metric *mtr = mlist->get (ind); 2091 Metric::SubType subtype = mtr->get_subtype (); 2092 if (subtype == Metric::INCLUSIVE && !incl_ok) 2093 continue; 2094 if (subtype == Metric::EXCLUSIVE && !excl_ok) 2095 continue; 2096 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 2097 continue; 2098 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 2099 } 2100 } 2101 } 2102} 2103 2104void 2105PathTree::get_self_metrics (Vector<Histable*> *objs, NodeIdx node_idx, 2106 bool seen, int dpth) 2107{ 2108 Node *node = NODE_IDX (node_idx); 2109 Histable *cur_obj = get_hist_obj (node); 2110 obj_list[dpth] = cur_obj; 2111 2112 bool match = false; 2113 int nobj = objs->size (); 2114 if (dpth + 1 >= nobj) 2115 { 2116 match = true; 2117 for (int i = 0; i < nobj; ++i) 2118 { 2119 if (objs->fetch (i) != obj_list[dpth - nobj + 1 + i]) 2120 { 2121 match = false; 2122 break; 2123 } 2124 } 2125 } 2126 2127 if (match) 2128 { 2129 Hist_data::HistItem *hi = hist_data->append_hist_item (cur_obj); 2130 int incl_ok = !seen; 2131 int excl_ok = 0; 2132 if (IS_LEAF (node) || node == NODE_IDX (root_idx)) 2133 excl_ok = 1; 2134 MetricList *mlist = hist_data->get_metric_list (); 2135 for (long ind = 0, sz = mlist->size (); ind < sz; ind++) 2136 { 2137 if (xlate[ind] == -1) 2138 continue; 2139 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 2140 continue; 2141 Metric *mtr = mlist->get (ind); 2142 Metric::SubType subtype = mtr->get_subtype (); 2143 switch (subtype) 2144 { 2145 case Metric::INCLUSIVE: 2146 if (incl_ok && hi) 2147 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 2148 break; 2149 case Metric::EXCLUSIVE: 2150 case Metric::ATTRIBUTED: 2151 if (excl_ok && hi) 2152 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 2153 break; 2154 case Metric::DATASPACE: 2155 if (hi) 2156 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 2157 break; 2158 // ignoring the following cases (why?) 2159 case Metric::STATIC: 2160 break; 2161 } 2162 } 2163 } 2164 2165 if (dbeSession->is_interactive ()) 2166 { 2167 ndone++; 2168 int new_percent = 95 * ndone / nodes; 2169 if (new_percent > percent) 2170 { 2171 percent = new_percent; 2172 theApplication->set_progress (percent, NULL); 2173 } 2174 } 2175 2176 // Recursively process all descendants 2177 int index; 2178 int dsize = NUM_DESCENDANTS (node); 2179 for (index = 0; index < dsize; index++) 2180 get_self_metrics (objs, node->descendants->fetch (index), 2181 seen || match, dpth + 1); 2182} 2183 2184void 2185PathTree::get_self_metrics (Vector<Histable*> *objs) 2186{ 2187 get_self_metrics (objs, root_idx, false, 0); 2188} 2189 2190void 2191PathTree::get_self_metrics (Histable *obj, Vector<Function*> *funclist, 2192 Vector<Histable*>* sel_objs) 2193{ 2194 int excl_ok, incl_ok; 2195 NodeIdx node_idx; 2196 Node *node, *anc; 2197 2198 if (obj == NULL) 2199 return; 2200 2201 SourceFile *src = NULL; 2202 if (obj && obj->get_type () == Histable::LINE) 2203 { 2204 DbeLine *dbeline = (DbeLine*) obj; 2205 src = dbeline->sourceFile; 2206 } 2207 2208 Hist_data::HistItem *hi = hist_data->append_hist_item (obj); 2209 for (int i = 0, sz = funclist ? funclist->size () : 0; i < sz; i++) 2210 { 2211 Function *fitem = (Function*) get_compare_obj (funclist->fetch (i)); 2212 node_idx = fn_map->get (fitem); 2213 for (; node_idx; node_idx = node->funclist) 2214 { 2215 node = NODE_IDX (node_idx); 2216 if (obj && obj->get_type () == Histable::LINE) 2217 { 2218 Histable *h = get_hist_obj (node, src); 2219 if (h == NULL) 2220 continue; 2221 if (h->convertto (Histable::LINE) != obj->convertto (Histable::LINE)) 2222 continue; 2223 } 2224 else if (get_hist_obj (node, src) != obj) 2225 continue; 2226 2227 // Check for recursion (inclusive metrics) 2228 incl_ok = 1; 2229 for (anc = NODE_IDX (node->ancestor); anc; 2230 anc = NODE_IDX (anc->ancestor)) 2231 { 2232 if (get_hist_obj (anc, src) == obj) 2233 { 2234 incl_ok = 0; 2235 break; 2236 } 2237 if (sel_objs != NULL) 2238 for (int k = 0; k < sel_objs->size (); k++) 2239 if (sel_objs->fetch (k) == get_hist_obj (anc, src)) 2240 { 2241 incl_ok = 0; 2242 break; 2243 } 2244 } 2245 2246 // Check for leaf nodes (exclusive metrics) 2247 excl_ok = 0; 2248 if (IS_LEAF (node) || node == NODE_IDX (root_idx)) 2249 excl_ok = 1; 2250 2251 MetricList *mlist = hist_data->get_metric_list (); 2252 for (long ind = 0, ind_sz = mlist->size (); ind < ind_sz; ind++) 2253 { 2254 if (xlate[ind] == -1) 2255 continue; 2256 Metric *mtr = mlist->get (ind); 2257 Metric::SubType subtype = mtr->get_subtype (); 2258 if (subtype == Metric::INCLUSIVE && !incl_ok) 2259 continue; 2260 if (subtype == Metric::EXCLUSIVE && !excl_ok) 2261 continue; 2262 if (subtype == Metric::ATTRIBUTED && !excl_ok) 2263 continue; 2264 if (IS_MVAL_ZERO (slots[xlate[ind]], node_idx)) 2265 continue; 2266 ADD_METRIC_VAL (hi->value[ind], slots[xlate[ind]], node_idx); 2267 } 2268 } 2269 } 2270} 2271 2272Vector<Histable*> * 2273PathTree::get_clr_instr (Histable * func) 2274{ 2275 Vector<Histable*> * instrs = NULL; 2276 if (func->get_type () != Histable::FUNCTION) 2277 return NULL; 2278 NodeIdx node_idx = fn_map->get ((Function*) func); 2279 Node *node = NODE_IDX (node_idx); 2280 if (node == NULL) 2281 return new Vector<Histable*>(); 2282 int instr_num = 0; 2283 for (; node; node = NODE_IDX (node->funclist)) 2284 instr_num++; 2285 instrs = new Vector<Histable*>(instr_num); 2286 node = NODE_IDX (node_idx); 2287 Histable *instr = NODE_IDX (node->ancestor)->instr; 2288 instr_num = 0; 2289 instrs->store (instr_num, instr); 2290 node = NODE_IDX (node->funclist); 2291 for (; node; node = NODE_IDX (node->funclist)) 2292 { 2293 instr = NODE_IDX (node->ancestor)->instr; 2294 instr_num++; 2295 instrs->store (instr_num, instr); 2296 } 2297 return instrs; 2298} 2299 2300Vector<void*> * 2301PathTree::get_cle_instr (Histable * func, Vector<Histable*>*&instrs) 2302{ 2303 if (func->get_type () != Histable::FUNCTION) 2304 return NULL; 2305 NodeIdx node_idx = fn_map->get ((Function*) func); 2306 Node *node = NODE_IDX (node_idx); 2307 if (node == NULL) 2308 { 2309 instrs = new Vector<Histable*>(); 2310 return new Vector<void*>(); 2311 } 2312 int instr_num = 0; 2313 for (; node; node = NODE_IDX (node->funclist)) 2314 instr_num++; 2315 instrs = new Vector<Histable*>(instr_num); 2316 Vector<void*> *callee_info = new Vector<void*>(instr_num); 2317 node = NODE_IDX (node_idx); 2318 Histable *instr = node->instr; 2319 instr_num = 0; 2320 instrs->store (instr_num, instr); 2321 int dec_num = 0; 2322 NodeIdx dec_idx = 0; 2323 if (NUM_DESCENDANTS (node) > 0) 2324 { 2325 Vector<Histable*> * callee_instrs = new Vector<Histable*>(node->descendants->size ()); 2326 Vec_loop (NodeIdx, node->descendants, dec_num, dec_idx) 2327 { 2328 Node * dec_node = NODE_IDX (dec_idx); 2329 //XXXX Note: there can be more than one instrs in one leaf function 2330 callee_instrs->store (dec_num, dec_node->instr); 2331 } 2332 callee_info->store (instr_num, callee_instrs); 2333 } 2334 else 2335 callee_info->store (instr_num, NULL); 2336 node = NODE_IDX (node->funclist); 2337 for (; node; node = NODE_IDX (node->funclist)) 2338 { 2339 instr = node->instr; 2340 instr_num++; 2341 instrs->store (instr_num, instr); 2342 if (NUM_DESCENDANTS (node) > 0) 2343 { 2344 Vector<Histable*> * callee_instrs = new Vector<Histable*>(node->descendants->size ()); 2345 Vec_loop (NodeIdx, node->descendants, dec_num, dec_idx) 2346 { 2347 Node * dec_node = NODE_IDX (dec_idx); 2348 //XXXX Note: there can be more than one instrs in one leaf function 2349 callee_instrs->store (dec_num, dec_node->instr); 2350 } 2351 callee_info->store (instr_num, callee_instrs); 2352 } 2353 else 2354 callee_info->store (instr_num, NULL); 2355 } 2356 return callee_info; 2357} 2358 2359// 2360// 2361// The following methods are used for debugging purpose only. 2362// 2363// 2364static int maxdepth; 2365static int maxwidth; 2366 2367void 2368PathTree::print (FILE *fd) 2369{ 2370 (void) reset (); 2371 fprintf (fd, NTXT ("n = %lld, dn = %lld, MD = %lld\n\n"), 2372 (long long) nodes, (long long) dnodes, (long long) depth); 2373 maxdepth = 0; 2374 maxwidth = 0; 2375 print (fd, root, 0); 2376 fprintf (fd, NTXT ("md = %lld, mw = %lld\n"), 2377 (long long) maxdepth, (long long) maxwidth); 2378} 2379 2380void 2381PathTree::print (FILE *fd, PathTree::Node *node, int lvl) 2382{ 2383 const char *t; 2384 char *n; 2385 if (lvl + 1 > maxdepth) 2386 maxdepth = lvl + 1; 2387 for (int i = 0; i < lvl; i++) 2388 fprintf (fd, NTXT ("-")); 2389 Histable *instr = node->instr; 2390 if (instr->get_type () == Histable::LINE) 2391 { 2392 t = "L"; 2393 n = ((DbeLine *) instr)->func->get_name (); 2394 } 2395 else if (instr->get_type () == Histable::INSTR) 2396 { 2397 t = "I"; 2398 n = ((DbeInstr *) instr)->func->get_name (); 2399 } 2400 else 2401 { 2402 t = "O"; 2403 n = instr->get_name (); 2404 } 2405 long long addr = (long long) instr->get_addr (); 2406 fprintf (fd, NTXT ("%s %s (0x%08llx) -- ndesc = %lld\n"), 2407 t, n, addr, (long long) (NUM_DESCENDANTS (node))); 2408 2409 // Recursively process all descendants 2410 int dsize = NUM_DESCENDANTS (node); 2411 if (dsize > maxwidth) 2412 maxwidth = dsize; 2413 for (int index = 0; index < dsize; index++) 2414 print (fd, NODE_IDX (node->descendants->fetch (index)), lvl + 1); 2415} 2416 2417void 2418PathTree::printn (FILE *fd) 2419{ 2420 int n = dbg_nodes (root); 2421 fprintf (fd, GTXT ("Number of nodes: %d, total size: %d\n"), n, (int) (n * sizeof (Node))); 2422} 2423 2424void 2425PathTree::dumpNodes (FILE *fd, Histable *obj) 2426{ 2427 const char *t; 2428 char *n; 2429 NodeIdx node_idx = fn_map->get ((Function*) obj); 2430 Node *node = NODE_IDX (node_idx); 2431 if (node == NULL) 2432 { 2433 fprintf (fd, GTXT ("No nodes associated with %s\n"), obj->get_name ()); 2434 return; 2435 } 2436 Histable *instr = node->instr; 2437 for (; node; node = NODE_IDX (node->funclist)) 2438 { 2439 instr = node->instr; 2440 if (instr->get_type () == Histable::LINE) 2441 { 2442 t = "L"; 2443 n = ((DbeLine *) instr)->func->get_name (); 2444 } 2445 else if (instr->get_type () == Histable::INSTR) 2446 { 2447 t = "I"; 2448 n = ((DbeInstr *) instr)->func->get_name (); 2449 } 2450 else 2451 { 2452 t = "O"; 2453 n = instr->get_name (); 2454 } 2455 long long addr = (long long) instr->get_addr (); 2456 if (addr <= 0xFFFFFFFFU) 2457 fprintf (fd, NTXT ("0x%08x -- %s %s\n"), (uint32_t) addr, t, n); 2458 else 2459 fprintf (fd, NTXT ("0x%016llX -- %s %s\n"), addr, t, n); 2460 } 2461} 2462 2463int 2464PathTree::dbg_nodes (PathTree::Node *node) 2465{ 2466 int res = 1; 2467 int dsize = NUM_DESCENDANTS (node); 2468 for (int index = 0; index < dsize; index++) 2469 res += dbg_nodes (NODE_IDX (node->descendants->fetch (index))); 2470 return res; 2471} 2472 2473static int mind_g; 2474 2475int 2476leak_alloc_comp (const void *s1, const void *s2) 2477{ 2478 // See Hist_data::sort_compare() for duplicate code 2479 int result = 0; 2480 CStack_data::CStack_item *t1, *t2; 2481 t1 = *(CStack_data::CStack_item **)s1; 2482 t2 = *(CStack_data::CStack_item **)s2; 2483 2484 switch (t1->value[mind_g].tag) 2485 { 2486 case VT_INT: 2487 if (t1->value[mind_g].i < t2->value[mind_g].i) 2488 result = -1; 2489 else if (t1->value[mind_g].i > t2->value[mind_g].i) 2490 result = 1; 2491 else 2492 result = 0; 2493 break; 2494 case VT_LLONG: 2495 if (t1->value[mind_g].ll < t2->value[mind_g].ll) 2496 result = -1; 2497 else if (t1->value[mind_g].ll > t2->value[mind_g].ll) 2498 result = 1; 2499 else 2500 result = 0; 2501 break; 2502 case VT_ULLONG: 2503 if (t1->value[mind_g].ull < t2->value[mind_g].ull) 2504 result = -1; 2505 else if (t1->value[mind_g].ull > t2->value[mind_g].ull) 2506 result = 1; 2507 else 2508 result = 0; 2509 break; 2510 // ignoring the following cases (why?) 2511 case VT_SHORT: 2512 case VT_FLOAT: 2513 case VT_DOUBLE: 2514 case VT_HRTIME: 2515 case VT_LABEL: 2516 case VT_ADDRESS: 2517 case VT_OFFSET: 2518 break; 2519 } 2520 // Sort in descending order 2521 return -result; 2522} 2523 2524CStack_data * 2525PathTree::get_cstack_data (MetricList *mlist) 2526{ 2527 (void) reset (); 2528 CStack_data *lam = new CStack_data (mlist); 2529 int nmetrics = mlist->get_items ()->size (); 2530 mind_g = -1; 2531 xlate = new int[nmetrics]; 2532 for (int mind = 0; mind < nmetrics; mind++) 2533 { 2534 xlate[mind] = -1; 2535 Metric *mtr = mlist->get_items ()->fetch (mind); 2536 if (mlist->get_sort_ref_index () == mind) 2537 mind_g = mind; 2538 xlate[mind] = find_slot (mtr->get_id ()); 2539 } 2540 2541 // now fill in the actual data 2542 obj_list = new Histable*[depth]; 2543 get_cstack_list (lam, root_idx, 0); 2544 delete[] obj_list; 2545 2546 if (mind_g >= 0) 2547 lam->cstack_items->sort (leak_alloc_comp); 2548 delete[] xlate; 2549 return lam; 2550} 2551 2552void 2553PathTree::get_cstack_list (CStack_data *lam, NodeIdx node_idx, int dpth) 2554{ 2555 2556 Node *node = NODE_IDX (node_idx); 2557 obj_list[dpth] = node->instr; 2558 2559 CStack_data::CStack_item *item = NULL; 2560 if (IS_LEAF (node)) 2561 item = lam->new_cstack_item (); 2562 int nmetrics = lam->metrics->get_items ()->size (); 2563 bool subtree_empty = true; 2564 2565 for (int mind = 0; mind < nmetrics; mind++) 2566 { 2567 if (xlate[mind] == -1) 2568 continue; 2569 if (IS_MVAL_ZERO (slots[xlate[mind]], node_idx)) 2570 continue; 2571 else 2572 subtree_empty = false; 2573 if (item) 2574 { 2575 ADD_METRIC_VAL (item->value[mind], slots[xlate[mind]], node_idx); 2576 ADD_METRIC_VAL (lam->total->value[mind], slots[xlate[mind]], node_idx); 2577 } 2578 } 2579 2580 if (subtree_empty) 2581 { 2582 delete item; 2583 return; 2584 } 2585 2586 if (item) 2587 { 2588 // Finish processing a leaf node 2589 item->stack = new Vector<DbeInstr*>(dpth); 2590 for (int i = 1; i <= dpth; i++) 2591 item->stack->append ((DbeInstr*) obj_list[i]); 2592 lam->cstack_items->append (item); 2593 } 2594 else 2595 { 2596 // Recursively process all descendants 2597 int dsize = NUM_DESCENDANTS (node); 2598 for (int index = 0; index < dsize; index++) 2599 get_cstack_list (lam, node->descendants->fetch (index), dpth + 1); 2600 } 2601} 2602 2603Emsg * 2604PathTree::fetch_stats () 2605{ 2606 if (statsq == NULL) 2607 return NULL; 2608 return statsq->fetch (); 2609} 2610 2611void 2612PathTree::delete_stats () 2613{ 2614 if (statsq != NULL) 2615 { 2616 delete statsq; 2617 statsq = new Emsgqueue (NTXT ("statsq")); 2618 } 2619} 2620 2621Emsg * 2622PathTree::fetch_warnings () 2623{ 2624 if (warningq == NULL) 2625 return NULL; 2626 return warningq->fetch (); 2627} 2628 2629void 2630PathTree::delete_warnings () 2631{ 2632 if (warningq != NULL) 2633 { 2634 delete warningq; 2635 warningq = new Emsgqueue (NTXT ("warningq")); 2636 } 2637} 2638