xref: /illumos-gate/usr/src/cmd/sgs/gprof/common/dfn.c (revision 7879e8a6)
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 <stdio.h>
29 #include "gprof.h"
30 
31 #define	DFN_DEPTH	100
32 
33 struct dfnstruct {
34 	nltype	*nlentryp;
35 	int	cycletop;
36 };
37 
38 typedef struct dfnstruct	dfntype;
39 
40 dfntype	*dfn_stack = NULL;
41 int	dfn_depth = 0;
42 int	dfn_sz = 0;
43 
44 int	dfn_counter = DFN_NAN;
45 
46 /*
47  *	given this parent, depth first number its children.
48  */
49 void
dfn(nltype * parentp)50 dfn(nltype *parentp)
51 {
52 	arctype	*arcp;
53 
54 #ifdef DEBUG
55 	if (debug & DFNDEBUG) {
56 		(void) printf("[dfn] dfn(");
57 		printname(parentp);
58 		(void) printf(")\n");
59 	}
60 #endif /* DEBUG */
61 
62 	if (!dfn_stack) {
63 		dfn_sz = DFN_DEPTH;
64 		dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype));
65 		if (!dfn_stack) {
66 			(void) fprintf(stderr,
67 			    "fatal: can't malloc %d objects\n", dfn_sz);
68 			exit(1);
69 		}
70 	}
71 
72 	/*
73 	 *	if we're already numbered, no need to look any furthur.
74 	 */
75 	if (dfn_numbered(parentp))
76 		return;
77 
78 	/*
79 	 *	if we're already busy, must be a cycle
80 	 */
81 	if (dfn_busy(parentp)) {
82 		dfn_findcycle(parentp);
83 		return;
84 	}
85 
86 	/*
87 	 *	visit yourself before your children
88 	 */
89 	dfn_pre_visit(parentp);
90 
91 	/*
92 	 *	visit children
93 	 */
94 	for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist)
95 		dfn(arcp->arc_childp);
96 
97 	/*
98 	 *	visit yourself after your children
99 	 */
100 	dfn_post_visit(parentp);
101 }
102 
103 /*
104  *	push a parent onto the stack and mark it busy
105  */
106 void
dfn_pre_visit(nltype * parentp)107 dfn_pre_visit(nltype *parentp)
108 {
109 
110 	if (!dfn_stack) {
111 		dfn_sz = DFN_DEPTH;
112 		dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype));
113 		if (!dfn_stack) {
114 			(void) printf("fatal: can't malloc %d objects\n",
115 			    dfn_sz);
116 			exit(1);
117 		}
118 	}
119 
120 	dfn_depth += 1;
121 
122 	if (dfn_depth >= dfn_sz) {
123 		dfn_sz += DFN_DEPTH;
124 		dfn_stack = (dfntype *) realloc(dfn_stack,
125 		    dfn_sz * sizeof (dfntype));
126 
127 		if (!dfn_stack) {
128 			(void) fprintf(stderr,
129 			    "fatal: can't realloc %d objects\n", dfn_sz);
130 			exit(1);
131 		}
132 	}
133 
134 	dfn_stack[dfn_depth].nlentryp = parentp;
135 	dfn_stack[dfn_depth].cycletop = dfn_depth;
136 	parentp->toporder = DFN_BUSY;
137 
138 #ifdef DEBUG
139 	if (debug & DFNDEBUG) {
140 		(void) printf("[dfn_pre_visit]\t\t%d:", dfn_depth);
141 		printname(parentp);
142 		(void) printf("\n");
143 	}
144 #endif /* DEBUG */
145 }
146 
147 /*
148  *	are we already numbered?
149  */
150 bool
dfn_numbered(nltype * childp)151 dfn_numbered(nltype *childp)
152 {
153 	return (childp->toporder != DFN_NAN && childp->toporder != DFN_BUSY);
154 }
155 
156 /*
157  *	are we already busy?
158  */
159 bool
dfn_busy(nltype * childp)160 dfn_busy(nltype *childp)
161 {
162 	if (childp->toporder == DFN_NAN)
163 		return (FALSE);
164 
165 	return (TRUE);
166 }
167 
168 void
dfn_findcycle(nltype * childp)169 dfn_findcycle(nltype *childp)
170 {
171 	int	cycletop;
172 	nltype	*cycleheadp = NULL;
173 	nltype	*tailp;
174 	int	index;
175 
176 	for (cycletop = dfn_depth; cycletop > 0; cycletop -= 1) {
177 		cycleheadp = dfn_stack[cycletop].nlentryp;
178 		if (childp == cycleheadp)
179 			break;
180 
181 		if (childp->cyclehead != childp &&
182 		    childp->cyclehead == cycleheadp)
183 			break;
184 	}
185 
186 	if (cycletop <= 0) {
187 		/*
188 		 * don't report non existent functions
189 		 */
190 		if (childp->value) {
191 			(void) fprintf(stderr,
192 			    "[dfn_findcycle] couldn't find head "
193 			    "of cycle for %s\n", childp->name);
194 			return;
195 		}
196 	}
197 
198 #ifdef DEBUG
199 	if (debug & DFNDEBUG) {
200 		(void) printf("[dfn_findcycle] dfn_depth %d cycletop %d ",
201 		    dfn_depth, cycletop);
202 		printname(cycleheadp);
203 		(void) printf("\n");
204 	}
205 #endif /* DEBUG */
206 
207 	if (cycletop == dfn_depth) {
208 		/*
209 		 *	this is previous function, e.g. this calls itself
210 		 *	sort of boring
211 		 */
212 		dfn_self_cycle(childp);
213 	} else {
214 		/*
215 		 *	glom intervening functions that aren't already
216 		 *	glommed into this cycle.
217 		 *	things have been glommed when their cyclehead field
218 		 *	points to the head of the cycle they are glommed into.
219 		 */
220 		for (tailp = cycleheadp; tailp->cnext; tailp = tailp->cnext) {
221 			/* void: chase down to tail of things already glommed */
222 #ifdef DEBUG
223 			if (debug & DFNDEBUG) {
224 				(void) printf("[dfn_findcycle] tail ");
225 				printname(tailp);
226 				(void) printf("\n");
227 			}
228 #endif /* DEBUG */
229 		}
230 
231 		/*
232 		 *	if what we think is the top of the cycle
233 		 *	has a cyclehead field, then it's not really the
234 		 *	head of the cycle, which is really what we want
235 		 */
236 		if (cycleheadp->cyclehead != cycleheadp) {
237 			cycleheadp = cycleheadp->cyclehead;
238 #ifdef DEBUG
239 			if (debug & DFNDEBUG) {
240 				(void) printf("[dfn_findcycle] new cyclehead ");
241 				printname(cycleheadp);
242 				(void) printf("\n");
243 			}
244 #endif /* DEBUG */
245 		}
246 
247 		for (index = cycletop + 1; index <= dfn_depth; index += 1) {
248 
249 			childp = dfn_stack[index].nlentryp;
250 			if (childp->cyclehead == childp) {
251 				/*
252 				 *	not yet glommed anywhere, glom it
253 				 *	and fix any children it has glommed
254 				 */
255 				tailp->cnext = childp;
256 				childp->cyclehead = cycleheadp;
257 #ifdef DEBUG
258 				if (debug & DFNDEBUG) {
259 					(void) printf(
260 					    "[dfn_findcycle] glomming ");
261 					printname(childp);
262 					(void) printf(" onto ");
263 					printname(cycleheadp);
264 					(void) printf("\n");
265 				}
266 #endif /* DEBUG */
267 				for (tailp = childp; tailp->cnext;
268 				    tailp = tailp->cnext) {
269 					tailp->cnext->cyclehead = cycleheadp;
270 #ifdef DEBUG
271 					if (debug & DFNDEBUG) {
272 						(void) printf("[dfn_findcycle]"
273 						    " and its tail ");
274 						printname(tailp->cnext);
275 						(void) printf(" onto ");
276 						printname(cycleheadp);
277 						(void) printf("\n");
278 					}
279 #endif /* DEBUG */
280 				}
281 			} else if (childp->cyclehead != cycleheadp) {
282 				(void) fprintf(stderr, "[dfn_busy] glommed,"
283 				    " but not to cyclehead\n");
284 			}
285 		}
286 	}
287 }
288 
289 /*
290  *	deal with self-cycles
291  *	for lint: ARGSUSED
292  */
293 /* ARGSUSED */
294 void
dfn_self_cycle(nltype * parentp)295 dfn_self_cycle(nltype *parentp)
296 {
297 	/*
298 	 *	since we are taking out self-cycles elsewhere
299 	 *	no need for the special case, here.
300 	 */
301 #ifdef DEBUG
302 	if (debug & DFNDEBUG) {
303 		(void) printf("[dfn_self_cycle] ");
304 		printname(parentp);
305 		(void) printf("\n");
306 	}
307 #endif /* DEBUG */
308 }
309 
310 /*
311  *	visit a node after all its children
312  *	[MISSING: an explanation]
313  *	and pop it off the stack
314  */
315 void
dfn_post_visit(nltype * parentp)316 dfn_post_visit(nltype *parentp)
317 {
318 	nltype	*memberp;
319 
320 #ifdef DEBUG
321 	if (debug & DFNDEBUG) {
322 		(void) printf("[dfn_post_visit]\t%d: ", dfn_depth);
323 		printname(parentp);
324 		(void) printf("\n");
325 	}
326 #endif /* DEBUG */
327 	/*
328 	 *	number functions and things in their cycles
329 	 *	unless the function is itself part of a cycle
330 	 */
331 	if (parentp->cyclehead == parentp) {
332 		dfn_counter += 1;
333 
334 		for (memberp = parentp; memberp; memberp = memberp->cnext) {
335 
336 			memberp->toporder = dfn_counter;
337 #ifdef DEBUG
338 			if (debug & DFNDEBUG) {
339 				(void) printf("[dfn_post_visit]\t\tmember ");
340 				printname(memberp);
341 				(void) printf(" -> toporder = %d\n",
342 				    dfn_counter);
343 			}
344 #endif /* DEBUG */
345 		}
346 #ifdef DEBUG
347 	} else {
348 		if (debug & DFNDEBUG)
349 			(void) printf(
350 			    "[dfn_post_visit]\t\tis part of a cycle\n");
351 #endif /* DEBUG */
352 	}
353 	dfn_depth -= 1;
354 }
355