"Fossies" - the Fresh Open Source Software Archive 
Member "FunctionCheck-3.2.0/src/fcdump/fc_graph.c" (26 May 2012, 15842 Bytes) of package /linux/privat/old/FunctionCheck-3.2.0.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 /*
2 * FunctionCheck profiler
3 * (C) Copyright 2000-2012 Yannick Perret
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19 /** fc_graph.c: **/
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include "fc_graph.h"
25
26 FC_Node **fc_list_of_nodes=NULL;
27 int fc_nb_list_of_nodes=0;
28
29 /* register a pointer to a node in the local list */
30 void fc_register_node(FC_Node *node)
31 {
32 if (fc_list_of_nodes == NULL)
33 {
34 fc_list_of_nodes = malloc(sizeof (FC_Node*));
35 }
36 else
37 {
38 fc_list_of_nodes = realloc(fc_list_of_nodes, sizeof (FC_Node*)*
39 (fc_nb_list_of_nodes + 1));
40 }
41 if (fc_list_of_nodes == NULL)
42 {
43 fc_message("cannot allocate %d bytes for local node list.", sizeof (FC_Node*)*
44 (fc_nb_list_of_nodes + 1));
45 fc_message("cycles detection will not be usable.");
46 fc_nb_list_of_nodes = 0;
47 return;
48 }
49 fc_list_of_nodes[fc_nb_list_of_nodes] = node;
50 fc_nb_list_of_nodes++;
51 }
52
53 /* create a new node for a given function */
54 FC_Node *fc_create_node(FC_Function *function)
55 {
56 FC_Node *tmp;
57
58 if (fc_malloc(tmp, 1) == NULL)
59 {
60 fc_message("not enough memory");
61 return NULL;
62 }
63 if (fc_malloc(tmp->nexts, 1) == NULL)
64 {
65 fc_message("not enough memory");
66 free(tmp);
67 return NULL;
68 }
69 if (fc_malloc(tmp->prevs, 1) == NULL)
70 {
71 fc_message("not enough memory");
72 free(tmp->nexts);
73 free(tmp);
74 return NULL;
75 }
76 if (fc_malloc(tmp->nnexts, 1) == NULL)
77 {
78 fc_message("not enough memory");
79 free(tmp->nexts);
80 free(tmp->prevs);
81 free(tmp);
82 return NULL;
83 }
84 if (fc_malloc(tmp->nprevs, 1) == NULL)
85 {
86 fc_message("not enough memory");
87 free(tmp->nexts);
88 free(tmp->prevs);
89 free(tmp->nnexts);
90 free(tmp);
91 return NULL;
92 }
93 tmp->nexts[0] = NULL;
94 tmp->prevs[0] = NULL;
95 tmp->nnexts[0] = 0;
96 tmp->nprevs[0] = 0;
97 tmp->function = function;
98 tmp->keep = 1;
99 tmp->treated = 0;
100 tmp->tag = 0;
101
102 return tmp;
103 }
104
105 /* delete a node */
106 FC_Node *fc_delete_node(FC_Node *node)
107 {
108 if (node == NULL)
109 return NULL;
110
111 if (node->nexts != NULL)
112 free(node->nexts);
113 if (node->prevs != NULL)
114 free(node->prevs);
115 if (node->nnexts != NULL)
116 free(node->nnexts);
117 if (node->nprevs != NULL)
118 free(node->nprevs);
119 free(node);
120
121 return NULL;
122 }
123
124 /* add a child to a node */
125 int fc_add_child(FC_Node *node, FC_Node *child, int number)
126 {
127 int nb = 0;
128
129 while (node->nexts[nb] != NULL)
130 {
131 nb++;
132 }
133 if ((node->nexts = realloc(node->nexts, (nb + 2) * sizeof (FC_Node*))) == NULL)
134 {
135 fc_message("not enough memory.");
136 return 0;
137 }
138 if ((node->nnexts = realloc(node->nnexts, (nb + 2) * sizeof (int))) == NULL)
139 {
140 fc_message("not enough memory.");
141 return 0;
142 }
143 node->nnexts[nb] = number;
144 node->nexts[nb] = child;
145 node->nexts[nb + 1] = NULL;
146
147 return 1;
148 }
149
150 /* add a parent to a node */
151 int fc_add_prev(FC_Node *node, FC_Node *prev, int number)
152 {
153 int nb = 0;
154
155 while (node->prevs[nb] != NULL)
156 nb++;
157 if ((node->prevs = realloc(node->prevs, (nb + 2) * sizeof (FC_Node*))) == NULL)
158 {
159 fc_message("not enough memory.");
160 return 0;
161 }
162 if ((node->nprevs = realloc(node->nprevs, (nb + 2) * sizeof (int))) == NULL)
163 {
164 fc_message("not enough memory.");
165 return 0;
166 }
167 node->nprevs[nb] = number;
168 node->prevs[nb] = prev;
169 node->prevs[nb + 1] = NULL;
170
171 return 1;
172 }
173
174 /* propagate given value (0/1) from the given node */
175 void fc_propagate_to_child(FC_Node*node, int val)
176 {
177 int i;
178
179 if (node->keep == val)
180 return; /* still done */
181
182 node->keep = val;
183 node->treated = 1;
184 i = 0;
185 while (node->nexts[i] != NULL)
186 {
187 fc_propagate_to_child(node->nexts[i], val);
188 i++;
189 }
190 }
191
192 /* retro-propagate given value (0/1) from the given node */
193 void fc_propagate_to_caller(FC_Node*node, int val)
194 {
195 int i;
196
197 if (node->keep == val)
198 return; /* still done */
199
200 node->keep = val;
201 node->treated = 1;
202 i = 0;
203 while (node->prevs[i] != NULL)
204 {
205 fc_propagate_to_caller(node->prevs[i], val);
206 i++;
207 }
208 }
209
210 /* propagate given value (0/1) from the given node */
211 void fc_propagate_to_child_p(FC_Node*node)
212 {
213 int i;
214
215 if (node->treated == 1)
216 return; /* still done */
217
218 node->keep = 1;
219 node->treated = 1;
220 i = 0;
221 while (node->nexts[i] != NULL)
222 {
223 fc_propagate_to_child_p(node->nexts[i]);
224 i++;
225 }
226 }
227
228 /* retro-propagate given value (0/1) from the given node */
229 void fc_propagate_to_caller_p(FC_Node*node)
230 {
231 int i;
232
233 if (node->treated == 1)
234 return; /* still done */
235
236 node->keep = 1;
237 node->treated = 1;
238 i = 0;
239 while (node->prevs[i] != NULL)
240 {
241 fc_propagate_to_caller_p(node->prevs[i]);
242 i++;
243 }
244 }
245
246 /* propagate tags to nodes */
247 void fc_tag_nodes(FC_Node *node, int tag)
248 {
249 int i;
250
251 /* stop if node still tagged */
252 if (node->tag != 0)
253 return;
254 /* tag the node */
255 node->tag = tag;
256 /* tag each child */
257 i = 0;
258 while (node->nexts[i] != NULL)
259 {
260 fc_tag_nodes(node->nexts[i], tag + 1);
261 i++;
262 }
263 }
264
265 /* for debug */
266 void fc_display_recurs(int option, FC_Node *node, unsigned int nc)
267 {
268 printf("%d: Simple recursion:\n", nc);
269 printf(" '%s' calls itself.\n", node->function->name.name);
270 printf(" Total time for this function: %f\n", node->function->total_time / 1000000.);
271 printf("\n");
272 }
273
274 void fc_display_cycle(int option, FC_Node *end, FC_Node *start, unsigned int nc)
275 {
276 printf("%d: Cycle:\n", nc);
277 printf(" cycle from '%s' to '%s'\n", start->function->name.name,
278 end->function->name.name);
279 printf(" Total time for this cycle: %f\n", start->function->total_time / 1000000.);
280 printf("\n");
281 }
282
283 /* check if a cycle is detected */
284 int fc_get_cycle_(FC_Node *node, FC_Node *init, FC_Node **last, int lng)
285 {
286 int i, ret;
287
288 /* loop found */
289 if ((node == init) && (lng != 0)) /* lng==0 => 1st call */
290 {
291 *last = NULL;
292 return lng;
293 }
294
295 if (node->tag > 0)
296 {/* indirect loop. stop now */
297 return 0;
298 }
299
300 /* tag this node to prevent loops */
301 node->tag = 1;
302
303 i = 0;
304 while (node->nexts[i] != NULL)
305 {
306 if ((ret = fc_get_cycle_(node->nexts[i], init, last, lng + 1)) > 0)
307 {
308 if (*last == NULL)
309 {
310 *last = node;
311 }
312 return ret;
313 }
314 i++;
315 }
316 /* no match */
317
318 return 0;
319 }
320
321 /* real call (for recursive reasons) */
322 int fc_get_cycle(FC_Node *node, FC_Node **last)
323 {
324 int i;
325
326 /* clear all tags */
327 for (i = 0; i < fc_nb_list_of_nodes; i++)
328 {
329 fc_list_of_nodes[i]->tag = 0;
330 }
331 return (fc_get_cycle_(node, node, last, 0));
332 }
333
334 /* compute list of cycles */
335 int fc_compute_cycles(int options)
336 {
337 int i;
338 unsigned int ncycle = 1; /* current cycle */
339 FC_Node **nodes, *last;
340 int nbinfo, ret;
341
342 if (fc_list_of_nodes == NULL)
343 return 0;
344
345 nodes = fc_list_of_nodes;
346 nbinfo = fc_nb_list_of_nodes;
347
348 /* try to detect every cycles */
349 for (i = 0; i < nbinfo; i++)
350 {
351 last = NULL;
352 ret = fc_get_cycle(nodes[i], &last);
353
354 if (ret == 1)
355 {
356 fc_display_recurs(options, nodes[i], ncycle);
357 ncycle++;
358 }
359 if (ret > 1)
360 {
361 fc_display_cycle(options, nodes[i], last, ncycle);
362 ncycle++;
363 }
364 }
365
366 return (ncycle - 1);
367 }
368
369 /* search a function. if do not exist, create a faked one */
370 FC_Function *fc_search_function(void *addr, int nb_fncs, FC_Function *fncs)
371 {
372 int i;
373 FC_Function *tmp;
374 char buf[512];
375
376 for (i = 0; i < nb_fncs; i++)
377 {
378 if (fncs[i].symbol == addr)
379 {
380 return (&(fncs[i]));
381 }
382 }
383 /* not found */
384 tmp = malloc(sizeof (FC_Function));
385 if (tmp == NULL)
386 {
387 fc_message("cannot allocate %d bytes for a faked function.", sizeof (FC_Function));
388 return NULL;
389 }
390
391 tmp->node = NULL;
392 tmp->symbol = addr;
393 sprintf(buf, "<%p>", addr);
394 tmp->name.name = strdup(buf);
395 return tmp;
396 }
397
398 /* propagate 'show function' to the children */
399 void fc_propagate_yes(FC_Node *node)
400 {
401 int i;
402
403 if (node == NULL)
404 return;
405
406 node->function->hide = 0;
407 node->treated = 1;
408
409 i = 0;
410 while (node->nexts[i] != NULL)
411 {
412 if (node->nexts[i]->treated == 0)
413 fc_propagate_yes(node->nexts[i]);
414 i++;
415 }
416 }
417
418 /* retro-propagate 'show function' to the children */
419 void fc_rpropagate_yes(FC_Node *node)
420 {
421 int i;
422
423 if (node == NULL)
424 return;
425
426 node->function->hide = 0;
427 node->treated = 1;
428
429 i = 0;
430 while (node->prevs[i] != NULL)
431 {
432 if (node->prevs[i]->treated == 0)
433 fc_propagate_yes(node->prevs[i]);
434 i++;
435 }
436 }
437
438 /* propagate 'hide function' to the children */
439 void fc_propagate_no(FC_Node *node)
440 {
441 int i;
442
443 if (node == NULL)
444 return;
445
446 node->function->hide = 1;
447 node->treated = 1;
448
449 i = 0;
450 while (node->nexts[i] != NULL)
451 {
452 if (node->nexts[i]->treated == 0)
453 fc_propagate_yes(node->nexts[i]);
454 i++;
455 }
456 }
457
458 /* retro-propagate 'hide function' to the children */
459 void fc_rpropagate_no(FC_Node *node)
460 {
461 int i;
462
463 if (node == NULL)
464 return;
465
466 node->function->hide = 1;
467 node->treated = 1;
468
469 i = 0;
470 while (node->prevs[i] != NULL)
471 {
472 if (node->prevs[i]->treated == 0)
473 fc_propagate_yes(node->prevs[i]);
474 i++;
475 }
476 }
477
478 /* perform all treatments to generate the call-graph */
479 int fc_graph_create(int *_nb_arcs, FC_Arc *arcs,
480 int nb_fncs, FC_Function *fncs,
481 FC_NSym *only, int nb_only,
482 FC_NSym *not, int nb_not,
483 int propagate, int rpropagate)
484 {
485 int nb_arcs;
486 int i, j;
487 int dec;
488 FC_Node *tmp;
489 FC_Function *func;
490
491 /* first remove duplicated entries in the arc table */
492 nb_arcs = *_nb_arcs;
493 fc_debug(" removing duplicated entries...");
494 for (i = 0; i < nb_arcs - 1; i++)
495 {
496 for (j = i + 1; j < nb_arcs; j++)
497 {
498 if ((arcs[i].from == arcs[j].from) &&
499 (arcs[i].to == arcs[j].to))
500 {
501 arcs[i].from = arcs[i].to = NULL;
502 /* sum the number of calls */
503 arcs[j].number += arcs[i].number;
504 break; /* no needs to test again */
505 }
506 }
507 }
508 dec = 0;
509 fc_debug(" removing duplicated entries (bis)...");
510 for (i = 0; i < nb_arcs; i++)
511 {
512 arcs[dec].from = arcs[i].from;
513 arcs[dec].to = arcs[i].to;
514 if (arcs[dec].from != NULL)
515 dec++;
516 }
517 nb_arcs = dec;
518 *_nb_arcs = dec;
519
520 /* for each arc we search the corresponding function */
521 fc_debug(" searching/creating arcs functions...");
522 for (i = 0; i < nb_arcs; i++)
523 {
524 arcs[i].ffrom = fc_search_function(arcs[i].from, nb_fncs, fncs);
525 arcs[i].fto = fc_search_function(arcs[i].to, nb_fncs, fncs);
526 if ((arcs[i].ffrom == NULL) || (arcs[i].fto == NULL))
527 {
528 fc_message("error while computing call graph. removing call-graph.");
529 return 0;
530 }
531 }
532
533 /* now create a node for each part of a arc */
534 fc_debug(" creating nodes for each arcs...");
535 for (i = 0; i < nb_arcs; i++)
536 {
537 if (arcs[i].ffrom->node == NULL)
538 {
539 tmp = fc_create_node(arcs[i].ffrom);
540 arcs[i].ffrom->node = (void*) tmp;
541 fc_register_node(tmp);
542 }
543 if (arcs[i].fto->node == NULL)
544 {
545 tmp = fc_create_node(arcs[i].fto);
546 arcs[i].fto->node = (void*) tmp;
547 fc_register_node(tmp);
548 }
549 }
550
551 /* now create the call graph links */
552 fc_debug(" linking nodes together...");
553 for (i = 0; i < nb_arcs; i++)
554 {
555 fc_add_child((FC_Node*) arcs[i].ffrom->node, (FC_Node*) arcs[i].fto->node, arcs[i].number);
556 fc_add_prev((FC_Node*) arcs[i].fto->node, (FC_Node*) arcs[i].ffrom->node, arcs[i].number);
557 }
558
559 /* now set/unset functions using -not/-only list */
560 fc_debug(" if any, propagating not/only...");
561 if ((nb_only != 0) && (nb_not == 0))
562 {
563 /* only use these functions */
564 /* first deselect all functions */
565 for (i = 0; i < nb_fncs; i++)
566 {
567 fncs[i].hide = 1;
568 ((FC_Node*) fncs[i].node)->treated = 0;
569 }
570 /* for each function in the list activate it */
571 for (i = 0; i < nb_only; i++)
572 {
573 if (only[i].addr != NULL)
574 {
575 func = fc_search_function(only[i].addr, nb_fncs, fncs);
576 func->hide = 0;
577 /* propagate/retro-propagate */
578 if (propagate)
579 {
580 fc_propagate_yes((FC_Node*) func->node);
581 }
582 if (rpropagate)
583 {
584 fc_rpropagate_yes((FC_Node*) func->node);
585 }
586 }
587 }
588 }
589 else
590 if ((nb_not != 0) && (nb_only == 0))
591 {
592 /* do not use these functions */
593 /* first select all functions */
594 for (i = 0; i < nb_fncs; i++)
595 {
596 fncs[i].hide = 0;
597 ((FC_Node*) fncs[i].node)->treated = 0;
598 }
599 /* for each function in the list desactivate it */
600 for (i = 0; i < nb_not; i++)
601 {
602 if (not[i].addr != NULL)
603 {
604 func = fc_search_function(not[i].addr, nb_fncs, fncs);
605 func->hide = 1;
606 /* add the propagate/retro-propagate */
607 if (propagate)
608 {
609 fc_propagate_no((FC_Node*) func->node);
610 }
611 if (rpropagate)
612 {
613 fc_rpropagate_no((FC_Node*) func->node);
614 }
615 }
616 }
617 }
618 else
619 if ((nb_not != 0) && (nb_only != 0))
620 {
621 /* special mode */
622 fc_message("combined -not/-only not implemented. Sorry.");
623 }
624
625 /* something else to compute ? */
626 fc_debug(" all done.");
627 return 1;
628 }
629
630 /* remove all nodes created */
631 int fc_graph_delete(int nb_arcs, FC_Arc *arcs,
632 int nb_fncs, FC_Function *fncs)
633 {
634 int i;
635
636 /* for each arc we search the node in the function */
637 for (i = 0; i < nb_arcs; i++)
638 {
639 if (arcs[i].ffrom->node != NULL)
640 {
641 arcs[i].ffrom->node = fc_delete_node(arcs[i].ffrom->node);
642 }
643 if (arcs[i].fto->node != NULL)
644 {
645 arcs[i].fto->node = fc_delete_node(arcs[i].fto->node);
646 }
647 }
648
649 /* remove the local list of nodes */
650 if (fc_list_of_nodes != NULL)
651 free(fc_list_of_nodes);
652
653 return 1;
654 }