1/* 2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23#undef DEBUG 24#include <string.h> 25#include <stdio.h> 26#include <libc.h> 27#include <limits.h> 28#include <sys/mman.h> 29#include "stuff/errors.h" 30#include "gprof.h" 31 32static uint64_t text_min = 0; 33static uint64_t text_max = 0; 34 35struct Edgestruct { 36 struct Edgestruct *next1; 37 struct Edgestruct *next2; 38 struct Edgestruct *prev1; 39 struct Edgestruct *prev2; 40 struct Edgestruct **pqp; 41 int v1; 42 int v2; 43 int w; 44}; 45typedef struct Edgestruct Edge; 46 47struct TreeNodestruct { 48 Edge *next1; 49 Edge *next2; 50 int parent; 51 int left; 52 int right; 53}; 54typedef struct TreeNodestruct TreeNode; 55 56#define NONE -1 57#define SEEN -2 58 59static FILE *gmon = NULL; 60static FILE *callf = NULL; 61static FILE *callo = NULL; 62static FILE *callt = NULL; 63#ifdef notdef 64static FILE *treefile = NULL; 65#endif 66 67static TreeNode *tree = NULL; 68static int n_nodes = 0; 69static Edge **pq = NULL; 70static int n_pq = 0; 71static char *whatsloaded = NULL; 72static Edge *free_edges = NULL; 73static Edge pqzero = { NULL, NULL, NULL, NULL, NULL, 0, 0, INT_MAX }; 74 75static void pqinsert( 76 Edge *edge); 77static Edge *pqremove( 78 void); 79static void pqdelete( 80 Edge *edge); 81static void upheap( 82 int k); 83static void downheap( 84 int k); 85 86static 87void 88do_what( 89void) 90{ 91 struct file *afile; 92 char *start, *stop, *dest, *whatsloadedp, ar_name[16], *namep; 93 94 for(afile = files; afile < &files[n_files]; afile++){ 95 if((namep = strrchr(afile->name, '/'))) 96 namep++; 97 else 98 namep = afile->name; 99 strncpy(ar_name, namep, 15); 100 ar_name[15] = '\0'; 101 whatsloadedp = whatsloaded; 102 while((start = stop = strstr(whatsloadedp, ar_name))){ 103 if((start == whatsloaded) || (*(start-1) == '(') || 104 (*(start-1) == '/')) { 105 while((*start != '\n') && (start >= whatsloaded)) 106 start--; 107 while((*stop != '\n') && (*stop != ')')) 108 stop++; 109 afile->what_name = dest = malloc(stop - start); 110 for(start++; start < stop; start++){ 111 *(dest++) = (*start == '(') ? ':' : *start; 112 } 113 *dest = '\0'; 114 break; 115 } 116 whatsloadedp = start + 1; 117 } 118 } 119} 120 121static 122char * 123find_file( 124uint64_t pc) 125{ 126 struct file *afile; 127 static int flag = 0; 128 129 for(afile = files; afile < &files[n_files]; afile++){ 130 if((pc >= afile->firstpc) && (pc < afile->lastpc)){ 131 return(afile->what_name); 132 } 133 } 134 if(flag == 0){ 135 fprintf(stderr, "In producing order files can't find module name " 136 "for functions (make sure all modules are compiled -g and " 137 "the program is not already ordered)\n"); 138 flag = 1; 139 } 140 return(NULL); 141} 142 143static 144int 145printp( 146nltype *node, 147FILE *f) 148{ 149 if(f == callt){ 150 if(zflag == FALSE && node->ncall == 0 && node->time == 0) 151 return(0); 152 else 153 return(1); 154 } 155 if(node->ncall == 0) /* call count 0 (not called) */ 156 return(0); 157 if(node->order == 0) /* not ordered (not called) */ 158 return(0); 159 if(node->value < text_min || node->value > text_max) 160 return(0); 161 return(1); 162/* 163 return(!( (node->ncall == 0) && 164 (node->selfcalls == 0) && 165 (node->propself == 0) && 166 (node->propchild == 0) && 167 (node->value >= text_min && node->value < text_max) ) ); 168 return ! ((node->ncall == 0) && 169 (node->selfcalls == 0) && 170 (node->propself == 0) && 171 (node->propchild == 0) 172 && (node->value >= text_min && node->value < text_max)); 173*/ 174} 175 176/* 177 void indent_node(int node, int level) 178 for (i = 0; i < level; i++) fprintf(treefile, " "); 179 fprintf(treefile, "%d %s\n", node, (node < npe - nl) ? nl[node].name : ""); 180 */ 181 182static 183void 184print_node( 185int node) 186{ 187 nltype *nlp; 188 char *file; 189 190 if((node == NONE) || (tree[node].parent == SEEN)) 191 return; 192 if(node < (npe - nl)){ 193 nlp = &nl[node]; 194 if(printp(nlp, NULL)){ 195 file = find_file(nlp->value); 196 fprintf(gmon, "%s:%s\n", file ? file : "", nlp->name); 197 } 198 } 199 tree[node].parent = SEEN; 200 print_node(tree[node].left); 201 print_node(tree[node].right); 202} 203 204static 205void 206print_nl( 207FILE *f) 208{ 209 nltype *nlp; 210 char *file; 211 212 for(nlp = npe-1; nlp >= nl; nlp--){ 213 if(printp(nlp, f)){ 214 file = find_file(nlp->value); 215 fprintf(f, "%s:%s\n", file ? file : "", nlp->name); 216 } 217 } 218} 219 220static 221void print_tree( 222void) 223{ 224 int i; 225 226 for(i = n_nodes-1; i >= 0; i--){ 227 if(tree[i].parent != SEEN) 228 print_node(i); 229 } 230} 231 232static 233Edge * 234find_edge( 235int v1, 236int v2, 237int w) 238{ 239 Edge *edge; 240 241 for(edge = tree[v1].next1; edge; edge = edge->next1){ 242 if(edge->v2 == v2){ 243 edge->w += w; 244 return(edge); 245 } 246 } 247 return(NULL); 248} 249 250static 251Edge * 252make_edge( 253int v1, 254int v2, 255int w) 256{ 257 Edge *edge; 258 259 if(free_edges){ 260 edge = free_edges; 261 free_edges = free_edges->next1; 262 } 263 else 264 edge = (Edge *)malloc(sizeof(Edge)); 265 edge->v1 = v1; 266 edge->v2 = v2; 267 edge->w = w; 268 269 edge->next1 = tree[v1].next1; 270 if(edge->next1) 271 edge->next1->prev1 = edge; 272 tree[v1].next1 = edge; 273 edge->prev1 = NULL; 274 275 edge->next2 = tree[v2].next2; 276 if(edge->next2) 277 edge->next2->prev2 = edge; 278 tree[v2].next2 = edge; 279 edge->prev2 = NULL; 280 281 edge->pqp = NULL; 282 return(edge); 283} 284 285static 286void 287free_edge( 288Edge *edge) 289{ 290 if(edge->prev1) 291 edge->prev1->next1 = edge->next1; 292 else 293 tree[edge->v1].next1 = edge->next1; 294 295 if(edge->next1) 296 edge->next1->prev1 = edge->prev1; 297 298 if(edge->prev2) 299 edge->prev2->next2 = edge->next2; 300 else 301 tree[edge->v2].next2 = edge->next2; 302 303 if(edge->next2) 304 edge->next2->prev2 = edge->prev2; 305 306 edge->next1 = free_edges; 307 free_edges = edge; 308} 309 310static 311int 312compare_file( 313struct file *x, 314struct file *y) 315{ 316 if(x->firstpc < y->firstpc) 317 return(-1); 318 else if(x->firstpc > y->firstpc) 319 return(1); 320 else 321 return(0); 322} 323 324static 325int 326compare_nl( 327nltype *x, 328nltype *y) 329{ 330 if(x->ncall < y->ncall) 331 return(-1); 332 else if(x->ncall > y->ncall) 333 return(1); 334 else 335 return(0); 336} 337 338static 339int 340compare_nl_order( 341nltype *x, 342nltype *y) 343{ 344 if(x->order > y->order) 345 return(-1); 346 else if(x->order < y->order) 347 return(1); 348 else 349 return(0); 350} 351 352static 353int 354timecmp( 355nltype *npp1, 356nltype *npp2) 357{ 358 double timediff; 359 int32_t calldiff; 360 361 timediff = npp2->time - npp1->time; 362 if(timediff > 0.0) 363 return(-1); 364 if(timediff < 0.0) 365 return(1); 366 calldiff = npp2->ncall - npp1->ncall; 367 if(calldiff > 0) 368 return(-1); 369 if(calldiff < 0) 370 return(1); 371 return(strcmp(npp2->name, npp1->name)); 372} 373 374static 375void 376enum_arcs( 377void(*proc)(arctype *arc, 378 arctype *backarc)) 379{ 380 nltype *nlp; 381 arctype *arcp, *backarc; 382 383 for(nlp = nl; nlp < npe; nlp++){ 384 for(arcp = nlp->children; arcp ; arcp = arcp->arc_childlist){ 385 for(backarc = arcp->arc_childp->children; 386 backarc; 387 backarc = backarc->arc_childlist){ 388 if(backarc->arc_childp == nlp){ 389 if(nlp < arcp->arc_childp) 390 proc(arcp, backarc); 391 goto skip; 392 } 393 } 394 proc(arcp, NULL); 395skip: 396 continue; 397 } 398 } 399} 400 401static int most_edges = 0; 402static 403void 404most_edges_proc( 405arctype *arc, 406arctype *backarc) 407{ 408 most_edges++; 409} 410 411static 412void 413enum_edges( 414int v, 415int(*proc_e1)(Edge *), 416int(*proc_e2)(Edge *)) 417{ 418 Edge *edge; 419 Edge *next1, *next2; 420 421 edge = tree[v].next1; 422 while(edge){ 423 next1 = edge->next1; 424 if(proc_e1(edge)) 425 free_edge(edge); 426 edge = next1; 427 } 428 edge = tree[v].next2; 429 while(edge){ 430 next2 = edge->next2; 431 if(proc_e2(edge)) 432 free_edge(edge); 433 edge = next2; 434 } 435} 436 437static 438int 439make_edge_e1( 440Edge *edge) 441{ 442 if(edge->pqp){ 443 pqdelete(edge); 444 make_edge(n_nodes, edge->v2, edge->w); 445 return(1); 446 } 447 else{ 448 return(0); 449 } 450} 451 452static 453int 454make_edge_e2( 455Edge *edge) 456{ 457 if(edge->pqp){ 458 pqdelete(edge); 459 make_edge(n_nodes, edge->v1, edge->w); 460 return(1); 461 } 462 else{ 463 return(0); 464 } 465} 466 467static 468int 469find_edge_e1( 470Edge *edge) 471{ 472 if(edge->pqp){ 473 pqdelete(edge); 474 if(!find_edge(n_nodes, edge->v2, edge->w)) 475 make_edge(n_nodes, edge->v2, edge->w); 476 return(1); 477 } 478 else{ 479 return(0); 480 } 481} 482 483static 484int 485find_edge_e2( 486Edge *edge) 487{ 488 if(edge->pqp){ 489 pqdelete(edge); 490 if(!find_edge(n_nodes, edge->v1, edge->w)) 491 make_edge(n_nodes, edge->v1, edge->w); 492 return(1); 493 } 494 else{ 495 return(0); 496 } 497} 498 499static 500int 501pqinsert_e1( 502Edge *edge) 503{ 504 if(!edge->pqp) 505 pqinsert(edge); 506 return(0); 507} 508 509static 510void 511main_loop( 512void) 513{ 514 Edge *edge; 515 516 while(n_pq > 0){ 517 edge = pqremove(); 518 519 /* collapse endpoints into combined node */ 520 tree[n_nodes].parent = NONE; 521 tree[n_nodes].left = edge->v1; 522 tree[n_nodes].right = edge->v2; 523 tree[edge->v1].parent = n_nodes; 524 tree[edge->v2].parent = n_nodes; 525 if(n_pq == 0) 526 break; 527 528 /* create edges for combined node */ 529 enum_edges(edge->v1, make_edge_e1, make_edge_e2); 530 enum_edges(edge->v2, find_edge_e1, find_edge_e2); 531 enum_edges(n_nodes, pqinsert_e1, NULL); 532 533 if((n_nodes++ % 50) == 0) 534 putc('.', stderr); 535 } 536 putc(';', stderr); 537 putc('\n', stderr); 538} 539 540static 541void 542pqinsert_proc( 543arctype *arc, 544arctype *backarc) 545{ 546 pqinsert(make_edge(arc->arc_parentp - nl, 547 arc->arc_childp - nl, 548 (backarc) ? (arc->arc_count + backarc->arc_count) : 549 (arc->arc_count))); 550} 551 552static 553void 554scatter( 555void) 556{ 557 int max_nodes; 558 TreeNode *tnode; 559 560 if(xflag == FALSE){ 561 max_nodes = 2 * (npe - nl); 562 tree = (TreeNode *)malloc(max_nodes * sizeof(TreeNode)); 563 n_nodes = npe - nl; 564 for(tnode = tree; tnode < &tree[max_nodes]; tnode++){ 565 tnode->next1 = tnode->next2 = NULL; 566 tnode->parent = tnode->left = tnode->right = NONE; 567 } 568 most_edges = 1; 569 enum_arcs(most_edges_proc); 570 pq = (Edge **)malloc(most_edges * sizeof(Edge *)); 571 n_pq = 0; 572 pq[0] = &pqzero; 573 574 enum_arcs(pqinsert_proc); /* create undirected graph */ 575 main_loop(); 576 print_tree(); 577 } 578 579 /* call frequency order file */ 580 qsort(nl, npe - nl, sizeof(nltype), 581 (int(*)(const void *, const void *))compare_nl); 582 print_nl(callf); 583 584 /* call order order file */ 585 qsort(nl, npe - nl, sizeof(nltype), 586 (int(*)(const void *, const void *))compare_nl_order); 587 print_nl(callo); 588 589 /* time order file */ 590 qsort(nl, npe - nl, sizeof(nltype), 591 (int (*)(const void *, const void *))timecmp); 592 print_nl(callt); 593} 594 595void 596printscatter( 597void) 598{ 599 int what_fd; 600 struct stat buf; 601 602 if(xflag == FALSE) 603 if((gmon = fopen("gmon.order", "w")) == NULL) 604 system_fatal("can't create file: gmon.order"); 605 if((callf = fopen("callf.order", "w")) == NULL) 606 system_fatal("can't create file: callf.order"); 607 if((callo = fopen("callo.order", "w")) == NULL) 608 system_fatal("can't create file: callo.order"); 609 if((callt = fopen("time.order", "w")) == NULL) 610 system_fatal("can't create file: time.order"); 611 /* 612 if((treefile = fopen("gmon.tree", "w")) == NULL) 613 system_fatal("can't create file: gmon.tree"); 614 */ 615 if((what_fd = open("whatsloaded", O_RDONLY)) >= 0){ 616 fstat(what_fd, &buf); 617 whatsloaded = mmap(0, buf.st_size, PROT_READ|PROT_WRITE, 618 MAP_FILE|MAP_PRIVATE, what_fd, 0); 619 do_what(); 620 } 621 get_text_min_max(&text_min, &text_max); 622 623 qsort(files, n_files, sizeof(struct file), 624 (int(*)(const void *, const void *))compare_file); 625 scatter(); 626 if(xflag == FALSE) 627 fclose(gmon); 628 fclose(callf); 629 fclose(callo); 630 fclose(callt); 631 if(what_fd >= 0) 632 close(what_fd); 633} 634 635#ifdef notdef 636static 637void 638ugh(void) 639{ 640} 641 642static 643voids 644print_pq( 645void) 646{ 647 int i; Edge *edge; 648 649 for(i = 1; i <= n_pq; i++){ 650 edge = pq[i]; 651 if(edge->pqp != &pq[i]) 652 ugh(); 653 fprintf(stderr, "%4d %4d %4d\n", i, edge->v1, edge->v2); 654 } 655} 656#endif 657 658static 659void 660upheap( 661int k) 662{ 663 Edge *v; 664 665 v = pq[k]; 666 while(pq[k/2]->w <= v->w){ 667 pq[k] = pq[k/2]; 668 pq[k]->pqp = &pq[k]; 669 k = k/2; 670 } 671 pq[k] = v; 672 pq[k]->pqp = &pq[k]; 673} 674 675static 676void 677downheap( 678int k) 679{ 680 Edge *v; 681 int j; 682 683 v = pq[k]; 684 while(k <= n_pq/2){ 685 j = 2 * k; 686 if(j < n_pq) 687 if(pq[j]->w < pq[j+1]->w) 688 j++; 689 if (v->w >= pq[j]->w) 690 break; 691 pq[k] = pq[j]; 692 pq[k]->pqp = &pq[k]; 693 k = j; 694 } 695 pq[k] = v; 696 pq[k]->pqp = &pq[k]; 697} 698 699static 700void 701pqinsert( 702Edge *v) 703{ 704#ifdef DEBUG 705 printf("pqinsert %d %x %d %d\n", 706 n_pq, (unsigned int)v, v->v1, v->v2); 707#endif 708 pq[++n_pq] = v; 709 upheap(n_pq); 710} 711 712static 713Edge * 714pqremove( 715void) 716{ 717 Edge *v = pq[1]; 718#ifdef DEBUG 719 printf("pqremove %d %x %d %d\n", 720 n_pq, (unsigned int)v, v->v1, v->v2); 721#endif 722 pq[1]->pqp = NULL; 723 pq[1] = pq[n_pq--]; 724 downheap(1); 725 return(v); 726} 727 728static 729void 730pqdelete( 731Edge *v) 732{ 733 Edge **peeq = v->pqp; 734#ifdef DEBUG 735 printf("pqdelete %d %x %d %d\n", 736 n_pq, (unsigned int)v, v->v1, v->v2); 737#endif 738 v->pqp = NULL; 739 if(n_pq == 0) 740 return; 741 *peeq = pq[n_pq--]; 742 upheap(peeq - pq); 743 downheap(peeq - pq); 744} 745