perf report: Add "Fractal" mode output - support callchains with relative overhead rate

The current callchain displays the overhead rates as absolute:
relative to the total overhead.

This patch provides relative overhead percentage, in which each
branch of the callchain tree is a independant instrumentated object.

This provides a 'fractal' view of the call-chain profile: each
sub-graph looks like a profile in itself - relative to its parent.

You can produce such output by using the "fractal" mode
that you can abbreviate via f, fr, fra, frac, etc...

./perf report -s sym -c fractal

Example:

     8.46%  [k] copy_user_generic_string
                |
                |--52.01%-- generic_file_aio_read
                |          do_sync_read
                |          vfs_read
                |          |
                |          |--97.20%-- sys_pread64
                |          |          system_call_fastpath
                |          |          pread64
                |          |
                |           --2.81%-- sys_read
                |                     system_call_fastpath
                |                     __read
                |
                |--39.85%-- generic_file_buffered_write
                |          __generic_file_aio_write_nolock
                |          generic_file_aio_write
                |          do_sync_write
                |          reiserfs_file_write
                |          vfs_write
                |          |
                |          |--97.05%-- sys_pwrite64
                |          |          system_call_fastpath
                |          |          __pwrite64
                |          |
                |           --2.95%-- sys_write
                |                     system_call_fastpath
                |                     __write_nocancel
[...]

Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Anton Blanchard <anton@samba.org>
Cc: Jens Axboe <jens.axboe@oracle.com>
Cc: Arnaldo Carvalho de Melo <acme@redhat.com>
LKML-Reference: <1246772361-9960-5-git-send-email-fweisbec@gmail.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

1 files changed, 69 insertions, 15 deletions

diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c
index 5d244afb7cdf..9d3c8141b8c1 100644
--- a/tools/perf/util/callchain.c
+++ b/tools/perf/util/callchain.c
@@ -32,13 +32,14 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
                 rnode = rb_entry(parent, struct callchain_node, rb_node);
 
                 switch (mode) {
-                case FLAT:
+                case CHAIN_FLAT:
                         if (rnode->hit < chain->hit)
                                 p = &(*p)->rb_left;
                         else
                                 p = &(*p)->rb_right;
                         break;
-                case GRAPH:
+                case CHAIN_GRAPH_ABS: /* Falldown */
+                case CHAIN_GRAPH_REL:
                         if (rnode->cumul_hit < chain->cumul_hit)
                                 p = &(*p)->rb_left;
                         else
@@ -53,43 +54,96 @@ rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
         rb_insert_color(&chain->rb_node, root);
 }
 
+static void
+__sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
+                  u64 min_hit)
+{
+        struct callchain_node *child;
+
+        chain_for_each_child(child, node)
+                __sort_chain_flat(rb_root, child, min_hit);
+
+        if (node->hit && node->hit >= min_hit)
+                rb_insert_callchain(rb_root, node, CHAIN_FLAT);
+}
+
 /*
  * Once we get every callchains from the stream, we can now
  * sort them by hit
  */
-void sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
-                     u64 min_hit)
+static void
+sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
+                u64 min_hit, struct callchain_param *param __used)
+{
+        __sort_chain_flat(rb_root, node, min_hit);
+}
+
+static void __sort_chain_graph_abs(struct callchain_node *node,
+                                   u64 min_hit)
 {
         struct callchain_node *child;
 
-        chain_for_each_child(child, node)
-                sort_chain_flat(rb_root, child, min_hit);
+        node->rb_root = RB_ROOT;
 
-        if (node->hit && node->hit >= min_hit)
-                rb_insert_callchain(rb_root, node, FLAT);
+        chain_for_each_child(child, node) {
+                __sort_chain_graph_abs(child, min_hit);
+                if (child->cumul_hit >= min_hit)
+                        rb_insert_callchain(&node->rb_root, child,
+                                            CHAIN_GRAPH_ABS);
+        }
+}
+
+static void
+sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_node *chain_root,
+                     u64 min_hit, struct callchain_param *param __used)
+{
+        __sort_chain_graph_abs(chain_root, min_hit);
+        rb_root->rb_node = chain_root->rb_root.rb_node;
 }
 
-static void __sort_chain_graph(struct callchain_node *node, u64 min_hit)
+static void __sort_chain_graph_rel(struct callchain_node *node,
+                                   double min_percent)
 {
         struct callchain_node *child;
+        u64 min_hit;
 
         node->rb_root = RB_ROOT;
+        min_hit = node->cumul_hit * min_percent / 100.0;
 
         chain_for_each_child(child, node) {
-                __sort_chain_graph(child, min_hit);
+                __sort_chain_graph_rel(child, min_percent);
                 if (child->cumul_hit >= min_hit)
-                        rb_insert_callchain(&node->rb_root, child, GRAPH);
+                        rb_insert_callchain(&node->rb_root, child,
+                                            CHAIN_GRAPH_REL);
         }
 }
 
-void
-sort_chain_graph(struct rb_root *rb_root, struct callchain_node *chain_root,
-                 u64 min_hit)
+static void
+sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_node *chain_root,
+                     u64 min_hit __used, struct callchain_param *param)
 {
-        __sort_chain_graph(chain_root, min_hit);
+        __sort_chain_graph_rel(chain_root, param->min_percent);
         rb_root->rb_node = chain_root->rb_root.rb_node;
 }
 
+int register_callchain_param(struct callchain_param *param)
+{
+        switch (param->mode) {
+        case CHAIN_GRAPH_ABS:
+                param->sort = sort_chain_graph_abs;
+                break;
+        case CHAIN_GRAPH_REL:
+                param->sort = sort_chain_graph_rel;
+                break;
+        case CHAIN_FLAT:
+                param->sort = sort_chain_flat;
+                break;
+        default:
+                return -1;
+        }
+        return 0;
+}
+
 /*
  * Create a child for a parent. If inherit_children, then the new child
  * will become the new parent of it's parent children