perf tools: Enhance the thread stack to output call/return data

Enhance the thread stack to output detailed information about paired
calls and returns.

The enhanced processing consumes sample information via
thread_stack__process() and outputs information about paired calls /
returns via a call-back.

While the call-back makes it possible for the facility to be used by
arbitrary tools, a subsequent patch will provide the information to
Python scripting via the db-export interface.

An important part of the call/return information is the
call path which provides a structure that defines a context
sensitive call graph.

Note that there are now two ways to use the thread stack.

For simply providing a call stack (like you would get from the perf
record -g option) the interface consists of thread_stack__event() and
thread_stack__sample().

Whereas the enhanced interface consists of call_return_processor__new()
and thread_stack__process().

Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: David Ahern <dsahern@gmail.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Namhyung Kim <namhyung@gmail.com>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Stephane Eranian <eranian@google.com>
Link: http://lkml.kernel.org/r/1414678188-14946-5-git-send-email-adrian.hunter@intel.com
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>

2 files changed, 659 insertions, 5 deletions

diff --git a/tools/perf/util/thread-stack.c b/tools/perf/util/thread-stack.c
index 85b60d2e738f..9ed59a452d1f 100644
--- a/tools/perf/util/thread-stack.c
+++ b/tools/perf/util/thread-stack.c
@@ -13,23 +13,96 @@
  *
  */
 
+#include <linux/rbtree.h>
+#include <linux/list.h>
 #include "thread.h"
 #include "event.h"
+#include "machine.h"
 #include "util.h"
 #include "debug.h"
+#include "symbol.h"
+#include "comm.h"
 #include "thread-stack.h"
 
-#define STACK_GROWTH 4096
+#define CALL_PATH_BLOCK_SHIFT 8
+#define CALL_PATH_BLOCK_SIZE (1 << CALL_PATH_BLOCK_SHIFT)
+#define CALL_PATH_BLOCK_MASK (CALL_PATH_BLOCK_SIZE - 1)
 
+struct call_path_block {
+        struct call_path cp[CALL_PATH_BLOCK_SIZE];
+        struct list_head node;
+};
+
+/**
+ * struct call_path_root - root of all call paths.
+ * @call_path: root call path
+ * @blocks: list of blocks to store call paths
+ * @next: next free space
+ * @sz: number of spaces
+ */
+struct call_path_root {
+        struct call_path call_path;
+        struct list_head blocks;
+        size_t next;
+        size_t sz;
+};
+
+/**
+ * struct call_return_processor - provides a call-back to consume call-return
+ *                                information.
+ * @cpr: call path root
+ * @process: call-back that accepts call/return information
+ * @data: anonymous data for call-back
+ */
+struct call_return_processor {
+        struct call_path_root *cpr;
+        int (*process)(struct call_return *cr, void *data);
+        void *data;
+};
+
+#define STACK_GROWTH 2048
+
+/**
+ * struct thread_stack_entry - thread stack entry.
+ * @ret_addr: return address
+ * @timestamp: timestamp (if known)
+ * @ref: external reference (e.g. db_id of sample)
+ * @branch_count: the branch count when the entry was created
+ * @cp: call path
+ * @no_call: a 'call' was not seen
+ */
 struct thread_stack_entry {
         u64 ret_addr;
+        u64 timestamp;
+        u64 ref;
+        u64 branch_count;
+        struct call_path *cp;
+        bool no_call;
 };
 
+/**
+ * struct thread_stack - thread stack constructed from 'call' and 'return'
+ *                       branch samples.
+ * @stack: array that holds the stack
+ * @cnt: number of entries in the stack
+ * @sz: current maximum stack size
+ * @trace_nr: current trace number
+ * @branch_count: running branch count
+ * @kernel_start: kernel start address
+ * @last_time: last timestamp
+ * @crp: call/return processor
+ * @comm: current comm
+ */
 struct thread_stack {
         struct thread_stack_entry *stack;
         size_t cnt;
         size_t sz;
         u64 trace_nr;
+        u64 branch_count;
+        u64 kernel_start;
+        u64 last_time;
+        struct call_return_processor *crp;
+        struct comm *comm;
 };
 
 static int thread_stack__grow(struct thread_stack *ts)
@@ -50,7 +123,8 @@ static int thread_stack__grow(struct thread_stack *ts)
         return 0;
 }
 
-static struct thread_stack *thread_stack__new(void)
+static struct thread_stack *thread_stack__new(struct thread *thread,
+                                              struct call_return_processor *crp)
 {
         struct thread_stack *ts;
 
@@ -63,6 +137,12 @@ static struct thread_stack *thread_stack__new(void)
                 return NULL;
         }
 
+        if (thread->mg && thread->mg->machine)
+                ts->kernel_start = machine__kernel_start(thread->mg->machine);
+        else
+                ts->kernel_start = 1ULL << 63;
+        ts->crp = crp;
+
         return ts;
 }
 
@@ -104,6 +184,64 @@ static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr)
         }
 }
 
+static bool thread_stack__in_kernel(struct thread_stack *ts)
+{
+        if (!ts->cnt)
+                return false;
+
+        return ts->stack[ts->cnt - 1].cp->in_kernel;
+}
+
+static int thread_stack__call_return(struct thread *thread,
+                                     struct thread_stack *ts, size_t idx,
+                                     u64 timestamp, u64 ref, bool no_return)
+{
+        struct call_return_processor *crp = ts->crp;
+        struct thread_stack_entry *tse;
+        struct call_return cr = {
+                .thread = thread,
+                .comm = ts->comm,
+                .db_id = 0,
+        };
+
+        tse = &ts->stack[idx];
+        cr.cp = tse->cp;
+        cr.call_time = tse->timestamp;
+        cr.return_time = timestamp;
+        cr.branch_count = ts->branch_count - tse->branch_count;
+        cr.call_ref = tse->ref;
+        cr.return_ref = ref;
+        if (tse->no_call)
+                cr.flags |= CALL_RETURN_NO_CALL;
+        if (no_return)
+                cr.flags |= CALL_RETURN_NO_RETURN;
+
+        return crp->process(&cr, crp->data);
+}
+
+static int thread_stack__flush(struct thread *thread, struct thread_stack *ts)
+{
+        struct call_return_processor *crp = ts->crp;
+        int err;
+
+        if (!crp) {
+                ts->cnt = 0;
+                return 0;
+        }
+
+        while (ts->cnt) {
+                err = thread_stack__call_return(thread, ts, --ts->cnt,
+                                                ts->last_time, 0, true);
+                if (err) {
+