1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 23 /* 24 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 25 * Use is subject to license terms. 26 */ 27 28 #pragma ident "%Z%%M% %I% %E% SMI" 29 30 #include <stdlib.h> 31 #include "gprof.h" 32 33 /* 34 * add (or just increment) an arc 35 */ 36 void 37 addarc(nltype *parentp, nltype *childp, actype count) 38 { 39 arctype *arcp; 40 41 #ifdef DEBUG 42 if (debug & TALLYDEBUG) { 43 (void) printf("[addarc] %lld arcs from %s to %s\n", 44 count, parentp->name, childp->name); 45 } 46 #endif /* DEBUG */ 47 arcp = arclookup(parentp, childp); 48 if (arcp != 0) { 49 /* 50 * a hit: just increment the count. 51 */ 52 #ifdef DEBUG 53 if (!Dflag) { 54 if (debug & TALLYDEBUG) { 55 (void) printf("[tally] hit %lld += %lld\n", 56 arcp->arc_count, count); 57 } 58 } else { 59 if (debug & TALLYDEBUG) { 60 (void) printf("[tally] hit %lld -= %lld\n", 61 arcp->arc_count, count); 62 } 63 } 64 65 #endif /* DEBUG */ 66 if (!Dflag) 67 arcp->arc_count += count; 68 else { 69 arcp->arc_count -= count; 70 if (arcp->arc_count < 0) 71 arcp->arc_count = 0; 72 } 73 return; 74 } 75 arcp = (arctype *)calloc(1, sizeof (*arcp)); 76 arcp->arc_parentp = parentp; 77 arcp->arc_childp = childp; 78 arcp->arc_count = count; 79 /* 80 * prepend this child to the children of this parent 81 */ 82 arcp->arc_childlist = parentp->children; 83 parentp->children = arcp; 84 /* 85 * prepend this parent to the parents of this child 86 */ 87 arcp->arc_parentlist = childp->parents; 88 childp->parents = arcp; 89 } 90 91 /* 92 * the code below topologically sorts the graph (collapsing cycles), 93 * and propagates time bottom up and flags top down. 94 */ 95 96 /* 97 * the topologically sorted name list pointers 98 */ 99 nltype **topsortnlp; 100 101 static int 102 topcmp(const void *arg1, const void *arg2) 103 { 104 nltype **npp1 = (nltype **)arg1; 105 nltype **npp2 = (nltype **)arg2; 106 107 return ((*npp1)->toporder - (*npp2)->toporder); 108 } 109 110 static void 111 timepropagate(nltype *parentp) 112 { 113 arctype *arcp; 114 nltype *childp; 115 double share; 116 double propshare; 117 118 if (parentp->propfraction == 0.0) { 119 return; 120 } 121 /* 122 * gather time from children of this parent. 123 */ 124 for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) { 125 childp = arcp->arc_childp; 126 if (arcp->arc_count == 0) { 127 continue; 128 } 129 if (childp == parentp) { 130 continue; 131 } 132 if (childp->propfraction == 0.0) { 133 continue; 134 } 135 if (childp->cyclehead != childp) { 136 if (parentp->cycleno == childp->cycleno) { 137 continue; 138 } 139 if (parentp->toporder <= childp->toporder) { 140 (void) fprintf(stderr, 141 "[propagate] toporder botches\n"); 142 } 143 childp = childp->cyclehead; 144 } else { 145 if (parentp->toporder <= childp->toporder) { 146 (void) fprintf(stderr, 147 "[propagate] toporder botches\n"); 148 continue; 149 } 150 } 151 if (childp->ncall == 0) { 152 continue; 153 } 154 /* 155 * distribute time for this arc 156 */ 157 arcp->arc_time = childp->time 158 * (((double)arcp->arc_count) / 159 ((double)childp->ncall)); 160 arcp->arc_childtime = childp->childtime 161 * (((double)arcp->arc_count) / 162 ((double)childp->ncall)); 163 share = arcp->arc_time + arcp->arc_childtime; 164 parentp->childtime += share; 165 /* 166 * (1 - propfraction) gets lost along the way 167 */ 168 propshare = parentp->propfraction * share; 169 /* 170 * fix things for printing 171 */ 172 parentp->propchild += propshare; 173 arcp->arc_time *= parentp->propfraction; 174 arcp->arc_childtime *= parentp->propfraction; 175 /* 176 * add this share to the parent's cycle header, if any. 177 */ 178 if (parentp->cyclehead != parentp) { 179 parentp->cyclehead->childtime += share; 180 parentp->cyclehead->propchild += propshare; 181 } 182 #ifdef DEBUG 183 if (debug & PROPDEBUG) { 184 (void) printf("[dotime] child \t"); 185 printname(childp); 186 (void) printf(" with %f %f %lld/%lld\n", 187 childp->time, childp->childtime, 188 arcp->arc_count, childp->ncall); 189 (void) printf("[dotime] parent\t"); 190 printname(parentp); 191 (void) printf("\n[dotime] share %f\n", share); 192 } 193 #endif /* DEBUG */ 194 } 195 } 196 197 198 static void 199 cycletime(void) 200 { 201 int cycle; 202 nltype *cyclenlp; 203 nltype *childp; 204 205 for (cycle = 1; cycle <= ncycle; cycle += 1) { 206 cyclenlp = &cyclenl[cycle]; 207 for (childp = cyclenlp->cnext; childp; childp = childp->cnext) { 208 if (childp->propfraction == 0.0) { 209 /* 210 * all members have the same propfraction 211 * except those that were excluded with -E 212 */ 213 continue; 214 } 215 cyclenlp->time += childp->time; 216 } 217 cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time; 218 } 219 } 220 221 222 static void 223 dotime(void) 224 { 225 int index; 226 227 cycletime(); 228 for (index = 0; index < total_names; index += 1) { 229 timepropagate(topsortnlp[index]); 230 } 231 } 232 233 234 static void 235 cyclelink(void) 236 { 237 nltype *nlp; 238 nltype *cyclenlp; 239 int cycle; 240 nltype *memberp; 241 arctype *arcp; 242 mod_info_t *mi; 243 244 /* 245 * Count the number of cycles, and initialize the cycle lists 246 */ 247 ncycle = 0; 248 for (mi = &modules; mi; mi = mi->next) { 249 for (nlp = mi->nl; nlp < mi->npe; nlp++) { 250 /* 251 * this is how you find unattached cycles 252 */ 253 if (nlp->cyclehead == nlp && nlp->cnext != 0) { 254 ncycle += 1; 255 } 256 } 257 } 258 259 /* 260 * cyclenl is indexed by cycle number: 261 * i.e. it is origin 1, not origin 0. 262 */ 263 cyclenl = (nltype *) calloc(ncycle + 1, sizeof (nltype)); 264 if (cyclenl == 0) { 265 (void) fprintf(stderr, 266 "%s: No room for %d bytes of cycle headers\n", 267 whoami, (ncycle + 1) * sizeof (nltype)); 268 done(); 269 } 270 271 /* 272 * now link cycles to true cycleheads, 273 * number them, accumulate the data for the cycle 274 */ 275 cycle = 0; 276 for (mi = &modules; mi; mi = mi->next) { 277 for (nlp = mi->nl; nlp < mi->npe; nlp++) { 278 if (!(nlp->cyclehead == nlp && nlp->cnext != 0)) { 279 continue; 280 } 281 cycle += 1; 282 cyclenlp = &cyclenl[cycle]; 283 cyclenlp->name = 0; /* the name */ 284 cyclenlp->value = 0; /* pc entry point */ 285 cyclenlp->time = 0.0; /* ticks in routine */ 286 cyclenlp->childtime = 0.0; /* cumulative ticks */ 287 /* in children */ 288 cyclenlp->ncall = 0; /* how many times */ 289 /* called */ 290 cyclenlp->selfcalls = 0; /* how many calls */ 291 /* to self */ 292 cyclenlp->propfraction = 0.0; /* what % of time */ 293 /* propagates */ 294 cyclenlp->propself = 0.0; /* how much self time */ 295 /* propagates */ 296 cyclenlp->propchild = 0.0; /* how much of child */ 297 /* time propagates */ 298 cyclenlp->printflag = TRUE; /* should this be */ 299 /* printed? */ 300 cyclenlp->index = 0; /* index in the */ 301 /* graph list */ 302 cyclenlp->toporder = DFN_NAN; /* graph call chain */ 303 /* top-sort order */ 304 cyclenlp->cycleno = cycle; /* internal number */ 305 /* of cycle on */ 306 cyclenlp->cyclehead = cyclenlp; /* head of cycle ptr */ 307 cyclenlp->cnext = nlp; /* ptr to next member */ 308 /* of cycle */ 309 cyclenlp->parents = 0; /* caller arcs list */ 310 cyclenlp->children = 0; /* callee arcs list */ 311 #ifdef DEBUG 312 if (debug & CYCLEDEBUG) { 313 (void) printf("[cyclelink] "); 314 printname(nlp); 315 (void) printf(" is the head of cycle %d\n", 316 cycle); 317 } 318 #endif /* DEBUG */ 319 /* 320 * link members to cycle header 321 */ 322 for (memberp = nlp; memberp; memberp = memberp->cnext) { 323 memberp->cycleno = cycle; 324 memberp->cyclehead = cyclenlp; 325 } 326 /* 327 * count calls from outside the cycle 328 * and those among cycle members 329 */ 330 for (memberp = nlp; memberp; memberp = memberp->cnext) { 331 for (arcp = memberp->parents; arcp; 332 arcp = arcp->arc_parentlist) { 333 if (arcp->arc_parentp == memberp) 334 continue; 335 336 if (arcp->arc_parentp->cycleno == 337 cycle) { 338 cyclenlp->selfcalls += 339 arcp->arc_count; 340 } else 341 cyclenlp->ncall += arcp->arc_count; 342 } 343 } 344 } 345 } 346 } 347 348 349 /* 350 * check if any parent of this child 351 * (or outside parents of this cycle) 352 * have their print flags on and set the 353 * print flag of the child (cycle) appropriately. 354 * similarly, deal with propagation fractions from parents. 355 */ 356 static void 357 inheritflags(nltype *childp) 358 { 359 nltype *headp; 360 arctype *arcp; 361 nltype *parentp; 362 nltype *memp; 363 364 headp = childp->cyclehead; 365 if (childp == headp) { 366 /* 367 * just a regular child, check its parents 368 */ 369 childp->printflag = FALSE; 370 childp->propfraction = 0.0; 371 for (arcp = childp->parents; arcp; 372 arcp = arcp->arc_parentlist) { 373 parentp = arcp->arc_parentp; 374 if (childp == parentp) { 375 continue; 376 } 377 childp->printflag |= parentp->printflag; 378 /* 379 * if the child was never actually called 380 * (e.g. this arc is static (and all others 381 * are, too)) no time propagates along this arc. 382 */ 383 if (childp->ncall) { 384 childp->propfraction += parentp->propfraction 385 * (((double)arcp->arc_count) 386 / ((double)childp->ncall)); 387 } 388 } 389 } else { 390 /* 391 * its a member of a cycle, look at all parents from 392 * outside the cycle 393 */ 394 headp->printflag = FALSE; 395 headp->propfraction = 0.0; 396 for (memp = headp->cnext; memp; memp = memp->cnext) { 397 for (arcp = memp->parents; arcp; 398 arcp = arcp->arc_parentlist) { 399 if (arcp->arc_parentp->cyclehead == headp) { 400 continue; 401 } 402 parentp = arcp->arc_parentp; 403 headp->printflag |= parentp->printflag; 404 /* 405 * if the cycle was never actually called 406 * (e.g. this arc is static (and all 407 * others are, too)) no time propagates 408 * along this arc. 409 */ 410 if (headp->ncall) { 411 headp->propfraction += 412 parentp->propfraction 413 * (((double)arcp->arc_count) 414 / ((double)headp->ncall)); 415 } 416 } 417 } 418 for (memp = headp; memp; memp = memp->cnext) { 419 memp->printflag = headp->printflag; 420 memp->propfraction = headp->propfraction; 421 } 422 } 423 } 424 425 426 /* 427 * check here if *any* of its parents is printable 428 * then return true else return false 429 */ 430 static int 431 check_ancestors(nltype *siblingp) 432 { 433 arctype *parentsp; 434 if (!siblingp->parents) 435 return (1); 436 for (parentsp = siblingp->parents; parentsp; 437 parentsp = parentsp->arc_parentlist) { 438 if (parentsp->arc_parentp->printflag) 439 return (1); 440 } 441 return (0); 442 } 443 444 445 /* 446 * check if the parents it passes time are *all* on 447 * the Elist in which case we do not pass the time 448 */ 449 static int 450 check_parents(nltype *siblingp) 451 { 452 arctype *parentsp; 453 if (!siblingp->parents) 454 return (1); 455 for (parentsp = siblingp->parents; parentsp; 456 parentsp = parentsp->arc_parentlist) { 457 if (!onlist(Elist, parentsp->arc_parentp->name)) 458 return (1); 459 } 460 return (0); 461 } 462 463 464 /* 465 * in one top to bottom pass over the topologically sorted namelist 466 * propagate: 467 * printflag as the union of parents' printflags 468 * propfraction as the sum of fractional parents' propfractions 469 * and while we're here, sum time for functions. 470 */ 471 static void 472 doflags(void) 473 { 474 int index; 475 nltype *childp; 476 nltype *oldhead; 477 478 oldhead = 0; 479 for (index = total_names - 1; index >= 0; index -= 1) { 480 childp = topsortnlp[index]; 481 /* 482 * if we haven't done this function or cycle, 483 * inherit things from parent. 484 * this way, we are linear in the number of arcs 485 * since we do all members of a cycle (and the 486 * cycle itself) as we hit the first member 487 * of the cycle. 488 */ 489 if (childp->cyclehead != oldhead) { 490 oldhead = childp->cyclehead; 491 inheritflags(childp); 492 } 493 #ifdef DEBUG 494 if (debug & PROPDEBUG) { 495 (void) printf("[doflags] "); 496 printname(childp); 497 (void) printf( 498 " inherits printflag %d and propfraction %f\n", 499 childp->printflag, childp->propfraction); 500 } 501 #endif /* DEBUG */ 502 if (!childp->printflag) { 503 bool on_flist; 504 /* 505 * printflag is off 506 * it gets turned on by 507 * being on -f list, 508 * or there not being any -f list 509 * and not being on -e list. 510 */ 511 if (((on_flist = onlist(flist, childp->name)) != 0) || 512 (!fflag && !onlist(elist, childp->name))) { 513 if (on_flist || check_ancestors(childp)) 514 childp->printflag = TRUE; 515 } 516 } else { 517 /* 518 * this function has printing parents: 519 * maybe someone wants to shut it up 520 * by putting it on -e list. (but favor -f 521 * over -e) 522 */ 523 if ((!onlist(flist, childp->name)) && 524 onlist(elist, childp->name)) { 525 childp->printflag = FALSE; 526 } 527 } 528 if (childp->propfraction == 0.0) { 529 /* 530 * no parents to pass time to. 531 * collect time from children if 532 * its on -F list, 533 * or there isn't any -F list and its not 534 * on -E list. 535 */ 536 if (onlist(Flist, childp->name) || 537 (!Fflag && !onlist(Elist, childp->name))) { 538 childp->propfraction = 1.0; 539 } 540 } else { 541 /* 542 * it has parents to pass time to, 543 * but maybe someone wants to shut it up 544 * by putting it on -E list. (but favor -F 545 * over -E) 546 */ 547 if (!onlist(Flist, childp->name) && 548 onlist(Elist, childp->name)) { 549 if (check_parents(childp)) 550 childp->propfraction = 0.0; 551 } 552 } 553 childp->propself = childp->time * childp->propfraction; 554 printtime += childp->propself; 555 #ifdef DEBUG 556 if (debug & PROPDEBUG) { 557 (void) printf("[doflags] "); 558 printname(childp); 559 (void) printf(" ends up with printflag %d and " 560 "propfraction %f\n", 561 childp->printflag, childp->propfraction); 562 (void) printf("time %f propself %f printtime %f\n", 563 childp->time, childp->propself, printtime); 564 } 565 #endif /* DEBUG */ 566 } 567 } 568 569 570 nltype ** 571 doarcs(void) 572 { 573 nltype *parentp, **timesortnlp; 574 arctype *arcp; 575 long i, index; 576 577 extern mod_info_t modules; 578 mod_info_t *mi; 579 580 /* 581 * initialize various things: 582 * zero out child times. 583 * count self-recursive calls. 584 * indicate that nothing is on cycles. 585 */ 586 for (mi = &modules; mi; mi = mi->next) { 587 for (parentp = mi->nl; parentp < mi->npe; parentp++) { 588 parentp->childtime = 0.0; 589 arcp = arclookup(parentp, parentp); 590 if (arcp != 0) { 591 parentp->ncall -= arcp->arc_count; 592 parentp->selfcalls = arcp->arc_count; 593 } else { 594 parentp->selfcalls = 0; 595 } 596 parentp->propfraction = 0.0; 597 parentp->propself = 0.0; 598 parentp->propchild = 0.0; 599 parentp->printflag = FALSE; 600 parentp->toporder = DFN_NAN; 601 parentp->cycleno = 0; 602 parentp->cyclehead = parentp; 603 parentp->cnext = 0; 604 605 /* 606 * Inspecting text space is valid only for 607 * the program executable. 608 */ 609 if (cflag && (mi == &modules)) { 610 findcalls( 611 parentp, 612 parentp->value, 613 parentp->value + parentp->sz); 614 } 615 } 616 } 617 618 /* 619 * topologically order things 620 * if any node is unnumbered, 621 * number it and any of its descendents. 622 */ 623 for (mi = &modules; mi; mi = mi->next) { 624 for (parentp = mi->nl; parentp < mi->npe; parentp++) { 625 if (parentp->toporder == DFN_NAN) { 626 dfn(parentp); 627 } 628 } 629 } 630 631 /* 632 * link together nodes on the same cycle 633 */ 634 cyclelink(); 635 /* 636 * Sort the symbol tables in reverse topological order 637 */ 638 topsortnlp = (nltype **) calloc(total_names, sizeof (nltype *)); 639 if (topsortnlp == (nltype **) 0) { 640 (void) fprintf(stderr, 641 "[doarcs] ran out of memory for topo sorting\n"); 642 } 643 index = 0; 644 for (mi = &modules; mi; mi = mi->next) { 645 for (i = 0; i < mi->nname; i++) 646 topsortnlp[index++] = &(mi->nl[i]); 647 } 648 649 qsort(topsortnlp, total_names, sizeof (nltype *), topcmp); 650 #ifdef DEBUG 651 if (debug & DFNDEBUG) { 652 (void) printf("[doarcs] topological sort listing\n"); 653 for (index = 0; index < total_names; index += 1) { 654 (void) printf("[doarcs] "); 655 (void) printf("%d:", topsortnlp[ index ]->toporder); 656 printname(topsortnlp[ index ]); 657 (void) printf("\n"); 658 } 659 } 660 #endif /* DEBUG */ 661 /* 662 * starting from the topological top, 663 * propagate print flags to children. 664 * also, calculate propagation fractions. 665 * this happens before time propagation 666 * since time propagation uses the fractions. 667 */ 668 doflags(); 669 /* 670 * starting from the topological bottom, 671 * propogate children times up to parents. 672 */ 673 dotime(); 674 /* 675 * Now, sort by propself + propchild. 676 * sorting both the regular function names 677 * and cycle headers. 678 */ 679 timesortnlp = (nltype **) calloc(total_names + ncycle, 680 sizeof (nltype *)); 681 if (timesortnlp == (nltype **) 0) { 682 (void) fprintf(stderr, 683 "%s: ran out of memory for sorting\n", whoami); 684 } 685 686 index = 0; 687 for (mi = &modules; mi; mi = mi->next) { 688 for (i = 0; i < mi->nname; i++) 689 timesortnlp[index++] = &(mi->nl[i]); 690 } 691 692 for (index = 1; index <= ncycle; index++) 693 timesortnlp[total_names+index-1] = &cyclenl[index]; 694 695 qsort(timesortnlp, total_names + ncycle, sizeof (nltype *), totalcmp); 696 697 for (index = 0; index < total_names + ncycle; index++) 698 timesortnlp[index]->index = index + 1; 699 700 return (timesortnlp); 701 } 702