perf probe: Support --line option to show probable source-code lines

Add --line option to support showing probable source-code lines.

  perf probe --line SRC:LN[-LN|+NUM]
   or
  perf probe --line FUNC[:LN[-LN|+NUM]]

This option shows source-code with line number if the line can
be probed. Lines without line number (and blue color) means that
the line can not be probed, because debuginfo doesn't have the
information of those lines.

The argument specifies the range of lines, "source.c:100-120"
shows lines between 100th to l20th in source.c file. And
"func:10+20" shows 20 lines from 10th line of func function.

e.g.
 # ./perf probe --line kernel/sched.c:1080
 <kernel/sched.c:1080>
          *
          * called with rq->lock held and irqs disabled
          */
         static void hrtick_start(struct rq *rq, u64 delay)
         {
                struct hrtimer *timer = &rq->hrtick_timer;
   1086         ktime_t time = ktime_add_ns(timer->base->get_time(), delay);

                hrtimer_set_expires(timer, time);

   1090         if (rq == this_rq()) {
   1091                 hrtimer_restart(timer);
   1092         } else if (!rq->hrtick_csd_pending) {
   1093                 __smp_call_function_single(cpu_of(rq), &rq->hrtick_csd,
   1094                 rq->hrtick_csd_pending = 1;

If you specifying function name, this shows function-relative
line number.

 # ./perf probe --line schedule
 <schedule:0>
         asmlinkage void __sched schedule(void)
      1  {
                struct task_struct *prev, *next;
                unsigned long *switch_count;
                struct rq *rq;
                int cpu;

         need_resched:
                preempt_disable();
      9         cpu = smp_processor_id();
     10         rq = cpu_rq(cpu);
     11         rcu_sched_qs(cpu);
     12         prev = rq->curr;
     13         switch_count = &prev->nivcsw;

Signed-off-by: Masami Hiramatsu <mhiramat@redhat.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: systemtap <systemtap@sources.redhat.com>
Cc: DLE <dle-develop@lists.sourceforge.net>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Mike Galbraith <efault@gmx.de>
LKML-Reference: <20100106144534.27218.77939.stgit@dhcp-100-2-132.bos.redhat.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
diff --git a/tools/perf/util/probe-finder.c b/tools/perf/util/probe-finder.c
index 6402798..1b2124d 100644
--- a/tools/perf/util/probe-finder.c
+++ b/tools/perf/util/probe-finder.c
@@ -140,6 +140,31 @@
 	return found;
 }
 
+static int cu_get_filename(Dwarf_Die cu_die, Dwarf_Unsigned fno, char **buf)
+{
+	Dwarf_Signed cnt, i;
+	char **srcs;
+	int ret = 0;
+
+	if (!buf || !fno)
+		return -EINVAL;
+
+	ret = dwarf_srcfiles(cu_die, &srcs, &cnt, &__dw_error);
+	if (ret == DW_DLV_OK) {
+		if ((Dwarf_Unsigned)cnt > fno - 1) {
+			*buf = strdup(srcs[fno - 1]);
+			ret = 0;
+			pr_debug("found filename: %s\n", *buf);
+		} else
+			ret = -ENOENT;
+		for (i = 0; i < cnt; i++)
+			dwarf_dealloc(__dw_debug, srcs[i], DW_DLA_STRING);
+		dwarf_dealloc(__dw_debug, srcs, DW_DLA_LIST);
+	} else
+		ret = -EINVAL;
+	return ret;
+}
+
 /* Compare diename and tname */
 static int die_compare_name(Dwarf_Die dw_die, const char *tname)
 {
@@ -567,7 +592,7 @@
 }
 
 /* Find probe point from its line number */
-static void find_by_line(struct probe_finder *pf)
+static void find_probe_point_by_line(struct probe_finder *pf)
 {
 	Dwarf_Signed cnt, i, clm;
 	Dwarf_Line *lines;
@@ -626,7 +651,7 @@
 				pf->fno = die_get_decl_file(dlink->die);
 				pf->lno = die_get_decl_line(dlink->die)
 					 + pp->line;
-				find_by_line(pf);
+				find_probe_point_by_line(pf);
 				return 1;
 			}
 			if (die_inlined_subprogram(dlink->die)) {
@@ -673,7 +698,7 @@
 	return 0;
 }
 
-static void find_by_func(struct probe_finder *pf)
+static void find_probe_point_by_func(struct probe_finder *pf)
 {
 	search_die_from_children(pf->cu_die, probefunc_callback, pf);
 }
@@ -714,10 +739,10 @@
 			if (ret == DW_DLV_NO_ENTRY)
 				pf.cu_base = 0;
 			if (pp->function)
-				find_by_func(&pf);
+				find_probe_point_by_func(&pf);
 			else {
 				pf.lno = pp->line;
-				find_by_line(&pf);
+				find_probe_point_by_line(&pf);
 			}
 		}
 		dwarf_dealloc(__dw_debug, pf.cu_die, DW_DLA_DIE);
@@ -728,3 +753,159 @@
 	return pp->found;
 }
 
+
+static void line_range_add_line(struct line_range *lr, unsigned int line)
+{
+	struct line_node *ln;
+	struct list_head *p;
+
+	/* Reverse search, because new line will be the last one */
+	list_for_each_entry_reverse(ln, &lr->line_list, list) {
+		if (ln->line < line) {
+			p = &ln->list;
+			goto found;
+		} else if (ln->line == line)	/* Already exist */
+			return ;
+	}
+	/* List is empty, or the smallest entry */
+	p = &lr->line_list;
+found:
+	pr_debug("Debug: add a line %u\n", line);
+	ln = zalloc(sizeof(struct line_node));
+	DIE_IF(ln == NULL);
+	ln->line = line;
+	INIT_LIST_HEAD(&ln->list);
+	list_add(&ln->list, p);
+}
+
+/* Find line range from its line number */
+static void find_line_range_by_line(struct line_finder *lf)
+{
+	Dwarf_Signed cnt, i;
+	Dwarf_Line *lines;
+	Dwarf_Unsigned lineno = 0;
+	Dwarf_Unsigned fno;
+	Dwarf_Addr addr;
+	int ret;
+
+	ret = dwarf_srclines(lf->cu_die, &lines, &cnt, &__dw_error);
+	DIE_IF(ret != DW_DLV_OK);
+
+	for (i = 0; i < cnt; i++) {
+		ret = dwarf_line_srcfileno(lines[i], &fno, &__dw_error);
+		DIE_IF(ret != DW_DLV_OK);
+		if (fno != lf->fno)
+			continue;
+
+		ret = dwarf_lineno(lines[i], &lineno, &__dw_error);
+		DIE_IF(ret != DW_DLV_OK);
+		if (lf->lno_s > lineno || lf->lno_e < lineno)
+			continue;
+
+		/* Filter line in the function address range */
+		if (lf->addr_s && lf->addr_e) {
+			ret = dwarf_lineaddr(lines[i], &addr, &__dw_error);
+			DIE_IF(ret != DW_DLV_OK);
+			if (lf->addr_s > addr || lf->addr_e <= addr)
+				continue;
+		}
+		line_range_add_line(lf->lr, (unsigned int)lineno);
+	}
+	dwarf_srclines_dealloc(__dw_debug, lines, cnt);
+	if (!list_empty(&lf->lr->line_list))
+		lf->found = 1;
+}
+
+/* Search function from function name */
+static int linefunc_callback(struct die_link *dlink, void *data)
+{
+	struct line_finder *lf = (struct line_finder *)data;
+	struct line_range *lr = lf->lr;
+	Dwarf_Half tag;
+	int ret;
+
+	ret = dwarf_tag(dlink->die, &tag, &__dw_error);
+	DIE_IF(ret == DW_DLV_ERROR);
+	if (tag == DW_TAG_subprogram &&
+	    die_compare_name(dlink->die, lr->function) == 0) {
+		/* Get the address range of this function */
+		ret = dwarf_highpc(dlink->die, &lf->addr_e, &__dw_error);
+		if (ret == DW_DLV_OK)
+			ret = dwarf_lowpc(dlink->die, &lf->addr_s, &__dw_error);
+		DIE_IF(ret == DW_DLV_ERROR);
+		if (ret == DW_DLV_NO_ENTRY) {
+			lf->addr_s = 0;
+			lf->addr_e = 0;
+		}
+
+		lf->fno = die_get_decl_file(dlink->die);
+		lr->offset = die_get_decl_line(dlink->die);;
+		lf->lno_s = lr->offset + lr->start;
+		if (!lr->end)
+			lf->lno_e = (Dwarf_Unsigned)-1;
+		else
+			lf->lno_e = lr->offset + lr->end;
+		lr->start = lf->lno_s;
+		lr->end = lf->lno_e;
+		find_line_range_by_line(lf);
+		/* If we find a target function, this should be end. */
+		lf->found = 1;
+		return 1;
+	}
+	return 0;
+}
+
+static void find_line_range_by_func(struct line_finder *lf)
+{
+	search_die_from_children(lf->cu_die, linefunc_callback, lf);
+}
+
+int find_line_range(int fd, struct line_range *lr)
+{
+	Dwarf_Half addr_size = 0;
+	Dwarf_Unsigned next_cuh = 0;
+	int ret;
+	struct line_finder lf = {.lr = lr};
+
+	ret = dwarf_init(fd, DW_DLC_READ, 0, 0, &__dw_debug, &__dw_error);
+	if (ret != DW_DLV_OK)
+		return -ENOENT;
+
+	while (!lf.found) {
+		/* Search CU (Compilation Unit) */
+		ret = dwarf_next_cu_header(__dw_debug, NULL, NULL, NULL,
+			&addr_size, &next_cuh, &__dw_error);
+		DIE_IF(ret == DW_DLV_ERROR);
+		if (ret == DW_DLV_NO_ENTRY)
+			break;
+
+		/* Get the DIE(Debugging Information Entry) of this CU */
+		ret = dwarf_siblingof(__dw_debug, 0, &lf.cu_die, &__dw_error);
+		DIE_IF(ret != DW_DLV_OK);
+
+		/* Check if target file is included. */
+		if (lr->file)
+			lf.fno = cu_find_fileno(lf.cu_die, lr->file);
+
+		if (!lr->file || lf.fno) {
+			if (lr->function)
+				find_line_range_by_func(&lf);
+			else {
+				lf.lno_s = lr->start;
+				if (!lr->end)
+					lf.lno_e = (Dwarf_Unsigned)-1;
+				else
+					lf.lno_e = lr->end;
+				find_line_range_by_line(&lf);
+			}
+			/* Get the real file path */
+			if (lf.found)
+				cu_get_filename(lf.cu_die, lf.fno, &lr->path);
+		}
+		dwarf_dealloc(__dw_debug, lf.cu_die, DW_DLA_DIE);
+	}
+	ret = dwarf_finish(__dw_debug, &__dw_error);
+	DIE_IF(ret != DW_DLV_OK);
+	return lf.found;
+}
+