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