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