create a real call graph that can have cycles in --graphviz

[honggyukim]

uftrace graph actually doesn't show a call graph, but just a call tree output. For example, t-fibonacci example's output is as follows.

$ gcc -pg -o t-fibonacci tests/s-fibonacci.c

$ uftrace record t-fibonacci

$ uftrace graph
# Function Call Graph for 't-fibonacci' (session: 7701e718f823010e)
========== FUNCTION CALL GRAPH ==========
# TOTAL TIME   FUNCTION
   20.354 us : (1) t-fibonacci
    2.199 us :  +-(1) __monstartup
             :  |
    1.129 us :  +-(1) __cxa_atexit
             :  |
   17.026 us :  +-(1) main
   16.499 us :    (1) fib
   15.859 us :    (2) fib
   14.887 us :    (4) fib
   12.782 us :    (8) fib
    8.362 us :    (14) fib
    2.976 us :    (10) fib
    0.390 us :    (2) fib

As the output shows there are multiple nodes for fib function. It's because there are multiple backtrace or call paths of each fib node.

The --graphviz output also uses the same logic when building a graph, precisely a tree. So its output doesn't show the multiple nodes for the same function, but it draws multiple edges for the same calls.

The --graphviz output of t-fibonacci is as follows.

$ gcc -pg -o t-fibonacci tests/s-fibonacci.c
$ uftrace record t-fibonacci
$ uftrace dump --graphviz
      ...
digraph G {
    "t-fibonacci"
    "t-fibonacci" -> "__monstartup" [xlabel = "1"]
    "t-fibonacci" -> "__cxa_atexit" [xlabel = "1"]
    "t-fibonacci" -> "main" [xlabel = "1"]
    "main" -> "fib" [xlabel = "1"]
    "fib" -> "fib" [xlabel = "2"]
    "fib" -> "fib" [xlabel = "4"]
    "fib" -> "fib" [xlabel = "8"]
    "fib" -> "fib" [xlabel = "14"]
    "fib" -> "fib" [xlabel = "10"]
    "fib" -> "fib" [xlabel = "2"]
}

Its image shows too many edges from fib to fib as follows.

But it would be much better to make it as follows.

digraph G {
    "t-fibonacci"
    "t-fibonacci" -> "__monstartup" [xlabel = "1"]
    "t-fibonacci" -> "__cxa_atexit" [xlabel = "1"]
    "t-fibonacci" -> "main" [xlabel = "1"]
    "main" -> "fib" [xlabel = "1"]
    "fib" -> "fib" [xlabel = "40"]
}

This modified dot produces much clear image as follows.

[daeroro]

I want to try this one!

[honggyukim]

@daeroro Thanks. But it'd be much easier to do #1499 first.

[daeroro]

@honggyukim Thank you. I'll try #1499 first.

[hjongkim]

I'll try this.

[honggyukim]

Thanks. Please keep in mind that this can be applied to mermaid result as well so we need to have a common routine that combines the related edges.

[hjongkim]

Thanks for the advice. I'll also consider the impact on mermaid functionality.

[deepseafishy]

Hi, I have been looking into this issue for the past few days and I think I know the root of the problem, but I don't really know how to fix this. As mentioned intially, there are multiple fib nodes since there are multiple call paths. Seems like tracking such multiple call paths are done by add_graph_entry() through changing the pointer for the tg->node:

out:
    node->nr_calls++;
    tg->node = node;

and by add_graph_exit(), again changing the pointer for the tg->node:

out:
    node->time += fstack->total_time;
    node->child_time += fstack->child_time;

    if (exit_cb)
        exit_cb(tg, cb_arg);

    tg->node = node->parent;

If I am not wrong, tg->node is therefore decided by how many UFTRACE_ENTRY and UFTRACE_EXIT are encountered in the dump file. So I thought about changing this logic to not have a different fib node for every different call path, but then it would not make a proper graph in the first place. My thoughts are either:

1. have a separate variable in the node like bool recursive to denote that it is a node of recursive calls, and skip any of the prints regarding recursive calls during print_graph_to_graphviz(),
2. or reduce the edges after creating the graph by iterating through the whole.

@gichoel told me that the latter would create significant overhead if the initial graph is extremely large in size. Maybe the former idea could work, but I wanted some feedback if there are any better ideas.

[namhyung]

I think the first approach would work if you can count the number of recursive calls correctly.