[PATCH] ARM: fix unwinding for XIP kernels

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

The linker places the unwind tables in readonly sections. So when using
an XIP kernel these are located in ROM and cannot be modified.

For that reason don't convert the symbol addresses during boot (or
module loading) but only when interpreting them in search_index().
Moreover several consts are added to catch future writes and rename the
member "addr" of struct unwind_idx to "addr_offset" to better match the
new semantic.

This fixes unwinding on XIP which compared prel31 offsets to absolute
addresses because the initial conversion from prel31 to absolute failed.

Cc: Catalin Marinas <catalin.marinas@arm.com>
Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>
---
Hello,

this is broken since unwinding was introduce in v2.6.30-rc1.

Best regards
Uwe

 arch/arm/include/asm/unwind.h |   15 ++----------
 arch/arm/kernel/setup.c       |    2 -
 arch/arm/kernel/unwind.c      |   48 ++++++++++++----------------------------
 3 files changed, 18 insertions(+), 47 deletions(-)

diff --git a/arch/arm/include/asm/unwind.h b/arch/arm/include/asm/unwind.h
index a5edf42..2ae0e0a 100644
--- a/arch/arm/include/asm/unwind.h
+++ b/arch/arm/include/asm/unwind.h
@@ -30,14 +30,14 @@ enum unwind_reason_code {
 };
 
 struct unwind_idx {
-	unsigned long addr;
+	unsigned long addr_offset;
 	unsigned long insn;
 };
 
 struct unwind_table {
 	struct list_head list;
-	struct unwind_idx *start;
-	struct unwind_idx *stop;
+	const struct unwind_idx *start;
+	const struct unwind_idx *stop;
 	unsigned long begin_addr;
 	unsigned long end_addr;
 };
@@ -49,15 +49,6 @@ extern struct unwind_table *unwind_table_add(unsigned long start,
 extern void unwind_table_del(struct unwind_table *tab);
 extern void unwind_backtrace(struct pt_regs *regs, struct task_struct *tsk);
 
-#ifdef CONFIG_ARM_UNWIND
-extern int __init unwind_init(void);
-#else
-static inline int __init unwind_init(void)
-{
-	return 0;
-}
-#endif
-
 #endif	/* !__ASSEMBLY__ */
 
 #ifdef CONFIG_ARM_UNWIND
diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
index 7e7977a..cf9d71a 100644
--- a/arch/arm/kernel/setup.c
+++ b/arch/arm/kernel/setup.c
@@ -893,8 +893,6 @@ void __init setup_arch(char **cmdline_p)
 {
 	struct machine_desc *mdesc;
 
-	unwind_init();
-
 	setup_processor();
 	mdesc = setup_machine_fdt(__atags_pointer);
 	if (!mdesc)
diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
index e7e8365..ad3f06f 100644
--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -67,7 +67,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
 
 struct unwind_ctrl_block {
 	unsigned long vrs[16];		/* virtual register set */
-	unsigned long *insn;		/* pointer to the current instructions word */
+	const unsigned long *insn;	/* pointer to the current instructions word */
 	int entries;			/* number of entries left to interpret */
 	int byte;			/* current byte number in the instructions word */
 };
@@ -83,8 +83,8 @@ enum regs {
 	PC = 15
 };
 
-extern struct unwind_idx __start_unwind_idx[];
-extern struct unwind_idx __stop_unwind_idx[];
+extern const struct unwind_idx __start_unwind_idx[];
+extern const struct unwind_idx __stop_unwind_idx[];
 
 static DEFINE_SPINLOCK(unwind_lock);
 static LIST_HEAD(unwind_tables);
@@ -101,22 +101,22 @@ static LIST_HEAD(unwind_tables);
  * Binary search in the unwind index. The entries entries are
  * guaranteed to be sorted in ascending order by the linker.
  */
-static struct unwind_idx *search_index(unsigned long addr,
-				       struct unwind_idx *first,
-				       struct unwind_idx *last)
+static const struct unwind_idx *search_index(unsigned long addr,
+				       const struct unwind_idx *first,
+				       const struct unwind_idx *last)
 {
 	pr_debug("%s(%08lx, %p, %p)\n", __func__, addr, first, last);
 
-	if (addr < first->addr) {
+	if (addr < prel31_to_addr(&first->addr_offset)) {
 		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
 		return NULL;
-	} else if (addr >= last->addr)
+	} else if (addr >= prel31_to_addr(&last->addr_offset))
 		return last;
 
 	while (first < last - 1) {
-		struct unwind_idx *mid = first + ((last - first + 1) >> 1);
+		const struct unwind_idx *mid = first + ((last - first + 1) >> 1);
 
-		if (addr < mid->addr)
+		if (addr < prel31_to_addr(&mid->addr_offset))
 			last = mid;
 		else
 			first = mid;
@@ -125,9 +125,9 @@ static struct unwind_idx *search_index(unsigned long addr,
 	return first;
 }
 
-static struct unwind_idx *unwind_find_idx(unsigned long addr)
+static const struct unwind_idx *unwind_find_idx(unsigned long addr)
 {
-	struct unwind_idx *idx = NULL;
+	const struct unwind_idx *idx = NULL;
 	unsigned long flags;
 
 	pr_debug("%s(%08lx)\n", __func__, addr);
@@ -274,7 +274,7 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 int unwind_frame(struct stackframe *frame)
 {
 	unsigned long high, low;
-	struct unwind_idx *idx;
+	const struct unwind_idx *idx;
 	struct unwind_ctrl_block ctrl;
 
 	/* only go to a higher address on the stack */
@@ -399,7 +399,6 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
 				      unsigned long text_size)
 {
 	unsigned long flags;
-	struct unwind_idx *idx;
 	struct unwind_table *tab = kmalloc(sizeof(*tab), GFP_KERNEL);
 
 	pr_debug("%s(%08lx, %08lx, %08lx, %08lx)\n", __func__, start, size,
@@ -408,15 +407,11 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
 	if (!tab)
 		return tab;
 
-	tab->start = (struct unwind_idx *)start;
-	tab->stop = (struct unwind_idx *)(start + size);
+	tab->start = (const struct unwind_idx *)start;
+	tab->stop = (const struct unwind_idx *)(start + size);
 	tab->begin_addr = text_addr;
 	tab->end_addr = text_addr + text_size;
 
-	/* Convert the symbol addresses to absolute values */
-	for (idx = tab->start; idx < tab->stop; idx++)
-		idx->addr = prel31_to_addr(&idx->addr);
-
 	spin_lock_irqsave(&unwind_lock, flags);
 	list_add_tail(&tab->list, &unwind_tables);
 	spin_unlock_irqrestore(&unwind_lock, flags);
@@ -437,16 +432,3 @@ void unwind_table_del(struct unwind_table *tab)
 
 	kfree(tab);
 }
-
-int __init unwind_init(void)
-{
-	struct unwind_idx *idx;
-
-	/* Convert the symbol addresses to absolute values */
-	for (idx = __start_unwind_idx; idx < __stop_unwind_idx; idx++)
-		idx->addr = prel31_to_addr(&idx->addr);
-
-	pr_debug("unwind: ARM stack unwinding initialised\n");
-
-	return 0;
-}
-- 
1.7.7.1

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> The linker places the unwind tables in readonly sections. So when using
> an XIP kernel these are located in ROM and cannot be modified.
> 
> For that reason don't convert the symbol addresses during boot (or
> module loading) but only when interpreting them in search_index().
> Moreover several consts are added to catch future writes and rename the
> member "addr" of struct unwind_idx to "addr_offset" to better match the
> new semantic.
> 
> This fixes unwinding on XIP which compared prel31 offsets to absolute
> addresses because the initial conversion from prel31 to absolute failed.

My only worry - does this increase the index search by doing the prel31
conversion every time? It could affect tools like lockdep that need to
get the backtrace regularly at run-time.

-- 
Catalin

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > The linker places the unwind tables in readonly sections. So when using
> > an XIP kernel these are located in ROM and cannot be modified.
> > 
> > For that reason don't convert the symbol addresses during boot (or
> > module loading) but only when interpreting them in search_index().
> > Moreover several consts are added to catch future writes and rename the
> > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > new semantic.
> > 
> > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > addresses because the initial conversion from prel31 to absolute failed.
> 
> My only worry - does this increase the index search by doing the prel31
> conversion every time? It could affect tools like lockdep that need to
> get the backtrace regularly at run-time.
Yeah, I thought about the increased runtime, too and considered to only
fix it on CONFIG_XIP=y. Unfortunately as the addresses are relative to
their respective position in the idx section it's not trivial to just do
the inverse mapping on the address and compare that. But maybe it's
still cheaper to do it that way?

I will take a look and do some measurements when I have my more pressing
problems solved. For now I'm happy to have backtraces again.

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH] ARM: fix unwinding for XIP kernels

[Nicolas Pitre]

On Thu, 17 Nov 2011, Catalin Marinas wrote:

> On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > The linker places the unwind tables in readonly sections. So when using
> > an XIP kernel these are located in ROM and cannot be modified.
> > 
> > For that reason don't convert the symbol addresses during boot (or
> > module loading) but only when interpreting them in search_index().
> > Moreover several consts are added to catch future writes and rename the
> > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > new semantic.
> > 
> > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > addresses because the initial conversion from prel31 to absolute failed.
> 
> My only worry - does this increase the index search by doing the prel31
> conversion every time? It could affect tools like lockdep that need to
> get the backtrace regularly at run-time.

We're talking about two constant shifts and an add.  something that 
myght take around 2 cycles on ARM.  Hardly noticeable I would say, 
especially given that lockdep is already quite costly and hardly 
something you want to keep around in production anyway.

On the plus side, this fixes the XIP case, and allow for backtrace to be 
usable pretty early without any explicit initialization.

As far as I'm concerned (which isn't much as this is not my code):

Acked-by: Nicolas Pitre <nico@linaro.org>


Nicolas

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

On 18 November 2011 18:28, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Thu, 17 Nov 2011, Catalin Marinas wrote:
>
>> On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
>> > The linker places the unwind tables in readonly sections. So when using
>> > an XIP kernel these are located in ROM and cannot be modified.
>> >
>> > For that reason don't convert the symbol addresses during boot (or
>> > module loading) but only when interpreting them in search_index().
>> > Moreover several consts are added to catch future writes and rename the
>> > member "addr" of struct unwind_idx to "addr_offset" to better match the
>> > new semantic.
>> >
>> > This fixes unwinding on XIP which compared prel31 offsets to absolute
>> > addresses because the initial conversion from prel31 to absolute failed.
>>
>> My only worry - does this increase the index search by doing the prel31
>> conversion every time? It could affect tools like lockdep that need to
>> get the backtrace regularly at run-time.
>
> We're talking about two constant shifts and an add. ?something that
> myght take around 2 cycles on ARM. ?Hardly noticeable I would say,
> especially given that lockdep is already quite costly and hardly
> something you want to keep around in production anyway.

Just doing some maths - the prel31 conversion takes 2 instructions on
ARMv7 (sbfx, add). The search_index() loop is executed for
log(nr-symbols) iterations. On a vmlinux I have around with ~15000
function symbols, it means 14 iterations, so we get ~28 more cycles
per stack frame. For an average backtrace of 8 function calls, it adds
~200 cycles per backtrace.

For lockdep, that's indeed unnoticeable but there are some other tools
that need tracing. If no-one complains about this increase, I'm ok
with the patch (I know in the past people complained that unwinding is
much slower than frame pointers).

-- 
Catalin

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > The linker places the unwind tables in readonly sections. So when using
> > an XIP kernel these are located in ROM and cannot be modified.
> > 
> > For that reason don't convert the symbol addresses during boot (or
> > module loading) but only when interpreting them in search_index().
> > Moreover several consts are added to catch future writes and rename the
> > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > new semantic.
> > 
> > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > addresses because the initial conversion from prel31 to absolute failed.
> 
> My only worry - does this increase the index search by doing the prel31
> conversion every time? It could affect tools like lockdep that need to
> get the backtrace regularly at run-time.
I did a first test now using 

	static int __init unwind_test(void)
	{
	      unsigned long flags;
	      u64 start, end;
	      register unsigned long current_sp asm ("sp");
	      int i;

	      struct stackframe init_frame;

	      init_frame.fp = (unsigned long)__builtin_frame_address(0);
	      init_frame.sp = current_sp;
	      init_frame.lr = (unsigned long)__builtin_return_address(0);
	      init_frame.pc = (unsigned long)unwind_test;

	      local_irq_save(flags);
	      start = timestamp();
	      for (i = 0; i < 100; ++i) {
		      struct stackframe frame = init_frame;
		      while (!unwind_frame(&frame));
	      }
	      end = timestamp();
	      local_irq_restore(flags);

	      pr_info("%s: ************************ unwind test took %llu\n",
			      __func__, (unsigned long long)(end - start));
	      return 0;
	}
	late_initcall(unwind_test);

where timestamp reads and returns the value of a cpu counter on an mx35
machine.

The increase in runtime of my patch is@approx 7% for the above test
case.

I will try later to optimise a bit more as I wrote earlier in this
thread.

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

On Sun, Nov 20, 2011 at 12:28:09PM +0100, Uwe Kleine-K?nig wrote:
> On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > The linker places the unwind tables in readonly sections. So when using
> > > an XIP kernel these are located in ROM and cannot be modified.
> > > 
> > > For that reason don't convert the symbol addresses during boot (or
> > > module loading) but only when interpreting them in search_index().
> > > Moreover several consts are added to catch future writes and rename the
> > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > new semantic.
> > > 
> > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > addresses because the initial conversion from prel31 to absolute failed.
> > 
> > My only worry - does this increase the index search by doing the prel31
> > conversion every time? It could affect tools like lockdep that need to
> > get the backtrace regularly at run-time.
> I did a first test now using 
> 
> 	static int __init unwind_test(void)
> 	{
> 	      unsigned long flags;
> 	      u64 start, end;
> 	      register unsigned long current_sp asm ("sp");
> 	      int i;
> 
> 	      struct stackframe init_frame;
> 
> 	      init_frame.fp = (unsigned long)__builtin_frame_address(0);
> 	      init_frame.sp = current_sp;
> 	      init_frame.lr = (unsigned long)__builtin_return_address(0);
> 	      init_frame.pc = (unsigned long)unwind_test;
> 
> 	      local_irq_save(flags);
> 	      start = timestamp();
> 	      for (i = 0; i < 100; ++i) {
> 		      struct stackframe frame = init_frame;
> 		      while (!unwind_frame(&frame));
> 	      }
> 	      end = timestamp();
> 	      local_irq_restore(flags);
> 
> 	      pr_info("%s: ************************ unwind test took %llu\n",
> 			      __func__, (unsigned long long)(end - start));
> 	      return 0;
> 	}
> 	late_initcall(unwind_test);
> 
> where timestamp reads and returns the value of a cpu counter on an mx35
> machine.
> 
> The increase in runtime of my patch is at approx 7% for the above test
> case.
> 
> I will try later to optimise a bit more as I wrote earlier in this
> thread.
OK, did that now, and it's a tad faster than the original implementation
with an optimisation[1] using my test case. Don't know why though. Maybe
because I moved the test for the first entry to after the loop and the
cache helps me there?

I'll send a patch in reply to this mail that applies on top of my
previous patch. It would be great to get someone proof reading it.

Best regards
Uwe

[1] I optimised as follows:

--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -110,14 +110,13 @@ static struct unwind_idx *search_index(unsigned long addr,
 	if (addr < first->addr) {
 		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
 		return NULL;
-	} else if (addr >= last->addr)
-		return last;
+	}
 
-	while (first < last - 1) {
+	while (first < last) {
 		struct unwind_idx *mid = first + ((last - first + 1) >> 1);
 
 		if (addr < mid->addr)
-			last = mid;
+			last = mid - 1;
 		else
 			first = mid;
 	}

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH RFC] ARM: unwind: optimize to not convert each table value but the address

[Uwe Kleine-König]

The offsets in the unwind index section are signed 31 bit numbers and
the structs are sorted by this offset. So it first has offsets between
0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
between 0x00000000 and 0x3fffffff. When seperating these two blocks the
numbers are sorted even when interpreting the offsets as unsigned longs.

So instead of converting each offset hit during bisection to an absolute
address, first determine which of the blocks needs to be searched and
then adapt the key to find for the offset while bisecting using a simple
unsigned long comparison.

In my tests this is faster than the original implementation modifying
the unwind index section by 4.5%.

Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>
---
 arch/arm/include/asm/unwind.h |    1 +
 arch/arm/kernel/unwind.c      |   89 ++++++++++++++++++++++++++++++++--------
 2 files changed, 72 insertions(+), 18 deletions(-)

diff --git a/arch/arm/include/asm/unwind.h b/arch/arm/include/asm/unwind.h
index 2ae0e0a..d1c3f3a 100644
--- a/arch/arm/include/asm/unwind.h
+++ b/arch/arm/include/asm/unwind.h
@@ -37,6 +37,7 @@ struct unwind_idx {
 struct unwind_table {
 	struct list_head list;
 	const struct unwind_idx *start;
+	const struct unwind_idx *origin;
 	const struct unwind_idx *stop;
 	unsigned long begin_addr;
 	unsigned long end_addr;
diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
index ad3f06f..eaf5bbd 100644
--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -84,6 +84,7 @@ enum regs {
 };
 
 extern const struct unwind_idx __start_unwind_idx[];
+static const struct unwind_idx *__origin_unwind_idx;
 extern const struct unwind_idx __stop_unwind_idx[];
 
 static DEFINE_SPINLOCK(unwind_lock);
@@ -98,31 +99,76 @@ static LIST_HEAD(unwind_tables);
 })
 
 /*
- * Binary search in the unwind index. The entries entries are
+ * Binary search in the unwind index. The entries are
  * guaranteed to be sorted in ascending order by the linker.
+ *
+ * start = first entry
+ * origin = first entry with positive offset (or end if there is no such entry)
+ * stop - 1 = last entry
  */
 static const struct unwind_idx *search_index(unsigned long addr,
-				       const struct unwind_idx *first,
-				       const struct unwind_idx *last)
+				       const struct unwind_idx *start,
+				       const struct unwind_idx *origin,
+				       const struct unwind_idx *stop)
 {
-	pr_debug("%s(%08lx, %p, %p)\n", __func__, addr, first, last);
+	unsigned long addr_prel31;
+
+	pr_debug("%s(%08lx, %p, %p, %p)\n", __func__, addr, start, origin, stop);
+
+	/*
+	 * only search in the section with the matching sign. This way the
+	 * prel31 numbers can be compared as unsigned longs.
+	 */
+	if (addr < (unsigned long)start)
+		/* negative offsets: [start; origin) */
+		stop = origin;
+	else
+		/* positive offsets: [origin; stop) */
+		start = origin;
+
+	/* prel31 for address relavive to start */
+	addr_prel31 = (addr - (unsigned long)start) & 0x7fffffff;
+
+	while (start < stop - 1) {
+		const struct unwind_idx *mid = start + ((stop - start) >> 1);
+
+		/*
+		 * As addr_prel31 is relative to start an offset is needed to
+		 * make it relative to mid.
+		 */
+		if (addr_prel31 - ((unsigned long)mid - (unsigned long)start) < mid->addr_offset)
+			stop = mid;
+		else {
+			/* keep addr_prel31 relative to start */
+			addr_prel31 -= ((unsigned long)mid - (unsigned long)start);
+			start = mid;
+		}
+	}
 
-	if (addr < prel31_to_addr(&first->addr_offset)) {
+	if (likely(start->addr_offset <= addr_prel31))
+		return start;
+	else {
 		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
 		return NULL;
-	} else if (addr >= prel31_to_addr(&last->addr_offset))
-		return last;
+	}
+}
 
-	while (first < last - 1) {
-		const struct unwind_idx *mid = first + ((last - first + 1) >> 1);
+static const struct unwind_idx *unwind_find_origin(const struct unwind_idx *start,
+		const struct unwind_idx *stop)
+{
+	pr_debug("%s(%p, %p)\n", __func__, start, stop);
+	while (start < stop - 1) {
+		const struct unwind_idx *mid = start + ((stop - start) >> 1);
 
-		if (addr < prel31_to_addr(&mid->addr_offset))
-			last = mid;
+		if (mid->addr_offset >= 0x40000000)
+			/* negative offset */
+			start = mid;
 		else
-			first = mid;
+			/* positive offset */
+			stop = mid;
 	}
-
-	return first;
+	pr_debug("%s -> %p\n", __func__, stop);
+	return stop;
 }
 
 static const struct unwind_idx *unwind_find_idx(unsigned long addr)
@@ -132,11 +178,16 @@ static const struct unwind_idx *unwind_find_idx(unsigned long addr)
 
 	pr_debug("%s(%08lx)\n", __func__, addr);
 
-	if (core_kernel_text(addr))
+	if (core_kernel_text(addr)) {
+		if (unlikely(!__origin_unwind_idx))
+			__origin_unwind_idx = unwind_find_origin(__start_unwind_idx,
+					__stop_unwind_idx);
+
 		/* main unwind table */
 		idx = search_index(addr, __start_unwind_idx,
-				   __stop_unwind_idx - 1);
-	else {
+				   __origin_unwind_idx,
+				   __stop_unwind_idx);
+	} else {
 		/* module unwind tables */
 		struct unwind_table *table;
 
@@ -145,7 +196,8 @@ static const struct unwind_idx *unwind_find_idx(unsigned long addr)
 			if (addr >= table->begin_addr &&
 			    addr < table->end_addr) {
 				idx = search_index(addr, table->start,
-						   table->stop - 1);
+						   table->origin,
+						   table->stop);
 				/* Move-to-front to exploit common traces */
 				list_move(&table->list, &unwind_tables);
 				break;
@@ -409,6 +461,7 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
 
 	tab->start = (const struct unwind_idx *)start;
 	tab->stop = (const struct unwind_idx *)(start + size);
+	tab->origin = unwind_find_origin(tab->start, tab->stop);
 	tab->begin_addr = text_addr;
 	tab->end_addr = text_addr + text_size;
 
-- 
1.7.7.2

[PATCH RFC] ARM: unwind: optimize to not convert each table value but the address

[Catalin Marinas]

On Sun, Nov 20, 2011 at 11:12:42PM +0000, Uwe Kleine-K?nig wrote:
> The offsets in the unwind index section are signed 31 bit numbers and
> the structs are sorted by this offset. So it first has offsets between
> 0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
> between 0x00000000 and 0x3fffffff. When seperating these two blocks the
> numbers are sorted even when interpreting the offsets as unsigned longs.
> 
> So instead of converting each offset hit during bisection to an absolute
> address, first determine which of the blocks needs to be searched and
> then adapt the key to find for the offset while bisecting using a simple
> unsigned long comparison.
> 
> In my tests this is faster than the original implementation modifying
> the unwind index section by 4.5%.

If you don't care about the 7% unwinding performance drop on XIP
kernels, we could just have a prel31_lt() macro (or whatever other name)
which is a standard '<' comparison on !XIP kernels and does the prel31
conversion with XIP. It's only two places in search_index() where it is
needed and the code would still be more readable than the changes in
this patch :).

If you still want such improvement, I'll do a proper review of the
patch.

Thanks.

-- 
Catalin

[PATCH RFC] ARM: unwind: optimize to not convert each table value but the address

[Uwe Kleine-König]

On Mon, Nov 21, 2011 at 04:34:00PM +0000, Catalin Marinas wrote:
> On Sun, Nov 20, 2011 at 11:12:42PM +0000, Uwe Kleine-K?nig wrote:
> > The offsets in the unwind index section are signed 31 bit numbers and
> > the structs are sorted by this offset. So it first has offsets between
> > 0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
> > between 0x00000000 and 0x3fffffff. When seperating these two blocks the
> > numbers are sorted even when interpreting the offsets as unsigned longs.
> > 
> > So instead of converting each offset hit during bisection to an absolute
> > address, first determine which of the blocks needs to be searched and
> > then adapt the key to find for the offset while bisecting using a simple
> > unsigned long comparison.
> > 
> > In my tests this is faster than the original implementation modifying
> > the unwind index section by 4.5%.
> 
> If you don't care about the 7% unwinding performance drop on XIP
> kernels, we could just have a prel31_lt() macro (or whatever other name)
> which is a standard '<' comparison on !XIP kernels and does the prel31
> conversion with XIP. It's only two places in search_index() where it is
> needed and the code would still be more readable than the changes in
> this patch :).
> 
> If you still want such improvement, I'll do a proper review of the
> patch.
I'd prefer to get my improvement in. It took me quite some time to work
it out and I'm proud to made it work. And I don't think it's that
complicated or unreadable. Do you think it is? It's a bit different than
your code so the patch might look complicated, but IMHO the result is
fine.

If that makes your review easier, the main difference in the bisection
is that for you "last" is inclusive (at least with my optimisation) while
my "end" points behind the last entry that is considered.

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

On Sun, Nov 20, 2011 at 11:28:09AM +0000, Uwe Kleine-K?nig wrote:
> On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > The linker places the unwind tables in readonly sections. So when using
> > > an XIP kernel these are located in ROM and cannot be modified.
> > > 
> > > For that reason don't convert the symbol addresses during boot (or
> > > module loading) but only when interpreting them in search_index().
> > > Moreover several consts are added to catch future writes and rename the
> > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > new semantic.
> > > 
> > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > addresses because the initial conversion from prel31 to absolute failed.
> > 
> > My only worry - does this increase the index search by doing the prel31
> > conversion every time? It could affect tools like lockdep that need to
> > get the backtrace regularly at run-time.
> I did a first test now using 
> 
> 	static int __init unwind_test(void)

With your latest patch, have you tried dropping __init from this
function? Since the .init.text section goes after the unwind_idx tables,
all the prel31 offsets are positive and the number of init functions is
smaller than the run-time ones.

-- 
Catalin

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

Hello,

On Mon, Nov 21, 2011 at 06:35:45PM +0000, Catalin Marinas wrote:
> On Sun, Nov 20, 2011 at 11:28:09AM +0000, Uwe Kleine-K?nig wrote:
> > On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > > The linker places the unwind tables in readonly sections. So when using
> > > > an XIP kernel these are located in ROM and cannot be modified.
> > > > 
> > > > For that reason don't convert the symbol addresses during boot (or
> > > > module loading) but only when interpreting them in search_index().
> > > > Moreover several consts are added to catch future writes and rename the
> > > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > > new semantic.
> > > > 
> > > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > > addresses because the initial conversion from prel31 to absolute failed.
> > > 
> > > My only worry - does this increase the index search by doing the prel31
> > > conversion every time? It could affect tools like lockdep that need to
> > > get the backtrace regularly at run-time.
> > I did a first test now using 
> > 
> > 	static int __init unwind_test(void)
> 
> With your latest patch, have you tried dropping __init from this
> function? Since the .init.text section goes after the unwind_idx tables,
> all the prel31 offsets are positive and the number of init functions is
> smaller than the run-time ones.
Yeah, it works fine. In fact unwinding unwind_test yields:

	do_one_initcall+0x50/0x158
	kernel_init+0x78/0x120
	kernel_thread_exit+0x0/0x8

where kernel_thread_exit is not in .init.text, too.

I don't know why you asked? Did you see a bug? Or is it just to let me
do enough testing before you start reviewing my patches?

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

On Mon, Nov 28, 2011 at 09:22:17AM +0000, Uwe Kleine-K?nig wrote:
> Hello,
> 
> On Mon, Nov 21, 2011 at 06:35:45PM +0000, Catalin Marinas wrote:
> > On Sun, Nov 20, 2011 at 11:28:09AM +0000, Uwe Kleine-K?nig wrote:
> > > On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > > > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > > > The linker places the unwind tables in readonly sections. So when using
> > > > > an XIP kernel these are located in ROM and cannot be modified.
> > > > > 
> > > > > For that reason don't convert the symbol addresses during boot (or
> > > > > module loading) but only when interpreting them in search_index().
> > > > > Moreover several consts are added to catch future writes and rename the
> > > > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > > > new semantic.
> > > > > 
> > > > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > > > addresses because the initial conversion from prel31 to absolute failed.
> > > > 
> > > > My only worry - does this increase the index search by doing the prel31
> > > > conversion every time? It could affect tools like lockdep that need to
> > > > get the backtrace regularly at run-time.
> > > I did a first test now using 
> > > 
> > > 	static int __init unwind_test(void)
> > 
> > With your latest patch, have you tried dropping __init from this
> > function? Since the .init.text section goes after the unwind_idx tables,
> > all the prel31 offsets are positive and the number of init functions is
> > smaller than the run-time ones.
> Yeah, it works fine. In fact unwinding unwind_test yields:
> 
> 	do_one_initcall+0x50/0x158
> 	kernel_init+0x78/0x120
> 	kernel_thread_exit+0x0/0x8
> 
> where kernel_thread_exit is not in .init.text, too.
> 
> I don't know why you asked? Did you see a bug? Or is it just to let me
> do enough testing before you start reviewing my patches?

It's not a bug, just a wondering about the performance figures you got
with your latest patch. When you have __init to unwind_test, the
.init.text functions are placed by the linker after the unwinding table,
with having a positive prel31 address. All the non-init functions are
placed before the table with a negative prel31. With your latest patch,
you split the set of functions in two ranges - the non-init one with a
negative prel31 and the init functions with a positive prel31 and the
binary search only happens on one of these ranges. The problem is that
the init range is much smaller than the non-init one, so your benchmark
figures may not be realistic.

Could you run the simple benchmark on a non-init function?

Thanks.

-- 
Catalin

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

On Mon, Nov 28, 2011 at 09:45:03AM +0000, Catalin Marinas wrote:
> On Mon, Nov 28, 2011 at 09:22:17AM +0000, Uwe Kleine-K?nig wrote:
> > Hello,
> > 
> > On Mon, Nov 21, 2011 at 06:35:45PM +0000, Catalin Marinas wrote:
> > > On Sun, Nov 20, 2011 at 11:28:09AM +0000, Uwe Kleine-K?nig wrote:
> > > > On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > > > > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > > > > The linker places the unwind tables in readonly sections. So when using
> > > > > > an XIP kernel these are located in ROM and cannot be modified.
> > > > > > 
> > > > > > For that reason don't convert the symbol addresses during boot (or
> > > > > > module loading) but only when interpreting them in search_index().
> > > > > > Moreover several consts are added to catch future writes and rename the
> > > > > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > > > > new semantic.
> > > > > > 
> > > > > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > > > > addresses because the initial conversion from prel31 to absolute failed.
> > > > > 
> > > > > My only worry - does this increase the index search by doing the prel31
> > > > > conversion every time? It could affect tools like lockdep that need to
> > > > > get the backtrace regularly at run-time.
> > > > I did a first test now using 
> > > > 
> > > > 	static int __init unwind_test(void)
> > > 
> > > With your latest patch, have you tried dropping __init from this
> > > function? Since the .init.text section goes after the unwind_idx tables,
> > > all the prel31 offsets are positive and the number of init functions is
> > > smaller than the run-time ones.
> > Yeah, it works fine. In fact unwinding unwind_test yields:
> > 
> > 	do_one_initcall+0x50/0x158
> > 	kernel_init+0x78/0x120
> > 	kernel_thread_exit+0x0/0x8
> > 
> > where kernel_thread_exit is not in .init.text, too.
> > 
> > I don't know why you asked? Did you see a bug? Or is it just to let me
> > do enough testing before you start reviewing my patches?
> 
> It's not a bug, just a wondering about the performance figures you got
> with your latest patch. When you have __init to unwind_test, the
> .init.text functions are placed by the linker after the unwinding table,
> with having a positive prel31 address. All the non-init functions are
> placed before the table with a negative prel31. With your latest patch,
> you split the set of functions in two ranges - the non-init one with a
> negative prel31 and the init functions with a positive prel31 and the
> binary search only happens on one of these ranges. The problem is that
> the init range is much smaller than the non-init one, so your benchmark
> figures may not be realistic.
> 
> Could you run the simple benchmark on a non-init function?
Without __init I get with the original implementation:

	34139, 34127, 34100

and with my patch I get

	33456, 33425, 33407

So the speedup here is smaller here, but still OK. Anyhow, I don't care
much about the speedup compared to the current implementation. I like my
patch because it's more correct as it doesn't need to modify the unwind
tables and is searched in a nice way that doesn't look to be less
effective by an order.

Best regards
Uwe

-- 
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

On Mon, Nov 28, 2011 at 10:02:19AM +0000, Uwe Kleine-K?nig wrote:
> On Mon, Nov 28, 2011 at 09:45:03AM +0000, Catalin Marinas wrote:
> > On Mon, Nov 28, 2011 at 09:22:17AM +0000, Uwe Kleine-K?nig wrote:
> > > Hello,
> > > 
> > > On Mon, Nov 21, 2011 at 06:35:45PM +0000, Catalin Marinas wrote:
> > > > On Sun, Nov 20, 2011 at 11:28:09AM +0000, Uwe Kleine-K?nig wrote:
> > > > > On Thu, Nov 17, 2011 at 02:17:06PM +0000, Catalin Marinas wrote:
> > > > > > On Thu, Nov 17, 2011 at 01:40:00PM +0000, Uwe Kleine-K?nig wrote:
> > > > > > > The linker places the unwind tables in readonly sections. So when using
> > > > > > > an XIP kernel these are located in ROM and cannot be modified.
> > > > > > > 
> > > > > > > For that reason don't convert the symbol addresses during boot (or
> > > > > > > module loading) but only when interpreting them in search_index().
> > > > > > > Moreover several consts are added to catch future writes and rename the
> > > > > > > member "addr" of struct unwind_idx to "addr_offset" to better match the
> > > > > > > new semantic.
> > > > > > > 
> > > > > > > This fixes unwinding on XIP which compared prel31 offsets to absolute
> > > > > > > addresses because the initial conversion from prel31 to absolute failed.
> > > > > > 
> > > > > > My only worry - does this increase the index search by doing the prel31
> > > > > > conversion every time? It could affect tools like lockdep that need to
> > > > > > get the backtrace regularly at run-time.
> > > > > I did a first test now using 
> > > > > 
> > > > > 	static int __init unwind_test(void)
> > > > 
> > > > With your latest patch, have you tried dropping __init from this
> > > > function? Since the .init.text section goes after the unwind_idx tables,
> > > > all the prel31 offsets are positive and the number of init functions is
> > > > smaller than the run-time ones.
> > > Yeah, it works fine. In fact unwinding unwind_test yields:
> > > 
> > > 	do_one_initcall+0x50/0x158
> > > 	kernel_init+0x78/0x120
> > > 	kernel_thread_exit+0x0/0x8
> > > 
> > > where kernel_thread_exit is not in .init.text, too.
> > > 
> > > I don't know why you asked? Did you see a bug? Or is it just to let me
> > > do enough testing before you start reviewing my patches?
> > 
> > It's not a bug, just a wondering about the performance figures you got
> > with your latest patch. When you have __init to unwind_test, the
> > .init.text functions are placed by the linker after the unwinding table,
> > with having a positive prel31 address. All the non-init functions are
> > placed before the table with a negative prel31. With your latest patch,
> > you split the set of functions in two ranges - the non-init one with a
> > negative prel31 and the init functions with a positive prel31 and the
> > binary search only happens on one of these ranges. The problem is that
> > the init range is much smaller than the non-init one, so your benchmark
> > figures may not be realistic.
> > 
> > Could you run the simple benchmark on a non-init function?
> Without __init I get with the original implementation:
> 
> 	34139, 34127, 34100
> 
> and with my patch I get
> 
> 	33456, 33425, 33407
> 
> So the speedup here is smaller here, but still OK.

OK, so as long as it is not much worse than before, I'm ok with this.
I'll do a proper review of the patch in the next day or so.

Thanks.

-- 
Catalin

[PATCH RFC] ARM: unwind: optimize to not convert each table value but the address

[Catalin Marinas]

On Sun, Nov 20, 2011 at 11:12:42PM +0000, Uwe Kleine-K?nig wrote:
> The offsets in the unwind index section are signed 31 bit numbers and
> the structs are sorted by this offset. So it first has offsets between
> 0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
> between 0x00000000 and 0x3fffffff. When seperating these two blocks the
> numbers are sorted even when interpreting the offsets as unsigned longs.
> 
> So instead of converting each offset hit during bisection to an absolute
> address, first determine which of the blocks needs to be searched and
> then adapt the key to find for the offset while bisecting using a simple
> unsigned long comparison.
> 
> In my tests this is faster than the original implementation modifying
> the unwind index section by 4.5%.
> 
> Cc: Catalin Marinas <catalin.marinas@arm.com>
> Cc: Nicolas Pitre <nico@fluxnic.net>
> Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>

The patch looks fine. Could you please post the final combined patch
(and also pipe it through checkpatch.pl as it seems to have some too
long line).

Thanks.

-- 
Catalin

[PATCH] ARM: fix unwinding for XIP kernels

[Uwe Kleine-König]

The linker places the unwind tables in readonly sections. So when using
an XIP kernel these are located in ROM and cannot be modified.
For that reason the current approach to convert the relative offsets in
the unwind index to absolute addresses early in the boot process doesn't
work with XIP.

The offsets in the unwind index section are signed 31 bit numbers and
the structs are sorted by this offset. So it first has offsets between
0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
between 0x00000000 and 0x3fffffff. When seperating these two blocks the
numbers are sorted even when interpreting the offsets as unsigned longs.

So determine the first non-negative entry once and track that using the
new origin pointer. The actual bisection can then use a plain unsigned
long comparison. The only thing that makes the new bisection more
complicated is that the offsets are relative to their position in the
index section, so the key to search needs to be adapted accordingly in
each step.

Moreover several consts are added to catch future writes and rename the
member "addr" of struct unwind_idx to "addr_offset" to better match the
new semantic. (This has the additional benefit of breaking eventual
users at compile time to make them aware of the change.)

In my tests the new algorithm was a tad faster than the original and has
the additional upside of not needing the initial conversion and so saves
some boot time and it's possible to unwind even earlier.

Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>
---
Hello,

the code is the same as the two previous patches combined, only some
whitespace changes.

There are a few checkpatch issues left, namely one line over 80 chars
(which was already there before and IMHO is ok) and two warnings about
externs in arch/arm/kernel/unwind.c (__start_unwind_idx and
__stop_unwind_idx) which are ok, too. These externs were there before
and only the unwinder should care about them.

Thanks to Catalin to take the time to review my work.

Best regards
Uwe

 arch/arm/include/asm/unwind.h |   16 +----
 arch/arm/kernel/setup.c       |    2 -
 arch/arm/kernel/unwind.c      |  129 ++++++++++++++++++++++++++--------------
 3 files changed, 88 insertions(+), 59 deletions(-)

diff --git a/arch/arm/include/asm/unwind.h b/arch/arm/include/asm/unwind.h
index a5edf42..d1c3f3a 100644
--- a/arch/arm/include/asm/unwind.h
+++ b/arch/arm/include/asm/unwind.h
@@ -30,14 +30,15 @@ enum unwind_reason_code {
 };
 
 struct unwind_idx {
-	unsigned long addr;
+	unsigned long addr_offset;
 	unsigned long insn;
 };
 
 struct unwind_table {
 	struct list_head list;
-	struct unwind_idx *start;
-	struct unwind_idx *stop;
+	const struct unwind_idx *start;
+	const struct unwind_idx *origin;
+	const struct unwind_idx *stop;
 	unsigned long begin_addr;
 	unsigned long end_addr;
 };
@@ -49,15 +50,6 @@ extern struct unwind_table *unwind_table_add(unsigned long start,
 extern void unwind_table_del(struct unwind_table *tab);
 extern void unwind_backtrace(struct pt_regs *regs, struct task_struct *tsk);
 
-#ifdef CONFIG_ARM_UNWIND
-extern int __init unwind_init(void);
-#else
-static inline int __init unwind_init(void)
-{
-	return 0;
-}
-#endif
-
 #endif	/* !__ASSEMBLY__ */
 
 #ifdef CONFIG_ARM_UNWIND
diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
index 7e7977a..cf9d71a 100644
--- a/arch/arm/kernel/setup.c
+++ b/arch/arm/kernel/setup.c
@@ -893,8 +893,6 @@ void __init setup_arch(char **cmdline_p)
 {
 	struct machine_desc *mdesc;
 
-	unwind_init();
-
 	setup_processor();
 	mdesc = setup_machine_fdt(__atags_pointer);
 	if (!mdesc)
diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
index e7e8365..3f03fe0 100644
--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -67,7 +67,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
 
 struct unwind_ctrl_block {
 	unsigned long vrs[16];		/* virtual register set */
-	unsigned long *insn;		/* pointer to the current instructions word */
+	const unsigned long *insn;	/* pointer to the current instructions word */
 	int entries;			/* number of entries left to interpret */
 	int byte;			/* current byte number in the instructions word */
 };
@@ -83,8 +83,9 @@ enum regs {
 	PC = 15
 };
 
-extern struct unwind_idx __start_unwind_idx[];
-extern struct unwind_idx __stop_unwind_idx[];
+extern const struct unwind_idx __start_unwind_idx[];
+static const struct unwind_idx *__origin_unwind_idx;
+extern const struct unwind_idx __stop_unwind_idx[];
 
 static DEFINE_SPINLOCK(unwind_lock);
 static LIST_HEAD(unwind_tables);
@@ -98,45 +99,99 @@ static LIST_HEAD(unwind_tables);
 })
 
 /*
- * Binary search in the unwind index. The entries entries are
+ * Binary search in the unwind index. The entries are
  * guaranteed to be sorted in ascending order by the linker.
+ *
+ * start = first entry
+ * origin = first entry with positive offset (or stop if there is no such entry)
+ * stop - 1 = last entry
  */
-static struct unwind_idx *search_index(unsigned long addr,
-				       struct unwind_idx *first,
-				       struct unwind_idx *last)
+static const struct unwind_idx *search_index(unsigned long addr,
+				       const struct unwind_idx *start,
+				       const struct unwind_idx *origin,
+				       const struct unwind_idx *stop)
 {
-	pr_debug("%s(%08lx, %p, %p)\n", __func__, addr, first, last);
+	unsigned long addr_prel31;
+
+	pr_debug("%s(%08lx, %p, %p, %p)\n",
+			__func__, addr, start, origin, stop);
+
+	/*
+	 * only search in the section with the matching sign. This way the
+	 * prel31 numbers can be compared as unsigned longs.
+	 */
+	if (addr < (unsigned long)start)
+		/* negative offsets: [start; origin) */
+		stop = origin;
+	else
+		/* positive offsets: [origin; stop) */
+		start = origin;
+
+	/* prel31 for address relavive to start */
+	addr_prel31 = (addr - (unsigned long)start) & 0x7fffffff;
 
-	if (addr < first->addr) {
+	while (start < stop - 1) {
+		const struct unwind_idx *mid = start + ((stop - start) >> 1);
+
+		/*
+		 * As addr_prel31 is relative to start an offset is needed to
+		 * make it relative to mid.
+		 */
+		if (addr_prel31 - ((unsigned long)mid - (unsigned long)start) <
+				mid->addr_offset)
+			stop = mid;
+		else {
+			/* keep addr_prel31 relative to start */
+			addr_prel31 -= ((unsigned long)mid -
+					(unsigned long)start);
+			start = mid;
+		}
+	}
+
+	if (likely(start->addr_offset <= addr_prel31))
+		return start;
+	else {
 		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
 		return NULL;
-	} else if (addr >= last->addr)
-		return last;
+	}
+}
 
-	while (first < last - 1) {
-		struct unwind_idx *mid = first + ((last - first + 1) >> 1);
+static const struct unwind_idx *unwind_find_origin(
+		const struct unwind_idx *start, const struct unwind_idx *stop)
+{
+	pr_debug("%s(%p, %p)\n", __func__, start, stop);
+	while (start < stop - 1) {
+		const struct unwind_idx *mid = start + ((stop - start) >> 1);
 
-		if (addr < mid->addr)
-			last = mid;
+		if (mid->addr_offset >= 0x40000000)
+			/* negative offset */
+			start = mid;
 		else
-			first = mid;
+			/* positive offset */
+			stop = mid;
 	}
-
-	return first;
+	pr_debug("%s -> %p\n", __func__, stop);
+	return stop;
 }
 
-static struct unwind_idx *unwind_find_idx(unsigned long addr)
+static const struct unwind_idx *unwind_find_idx(unsigned long addr)
 {
-	struct unwind_idx *idx = NULL;
+	const struct unwind_idx *idx = NULL;
 	unsigned long flags;
 
 	pr_debug("%s(%08lx)\n", __func__, addr);
 
-	if (core_kernel_text(addr))
+	if (core_kernel_text(addr)) {
+		if (unlikely(!__origin_unwind_idx))
+			__origin_unwind_idx =
+				unwind_find_origin(__start_unwind_idx,
+						__stop_unwind_idx);
+
 		/* main unwind table */
 		idx = search_index(addr, __start_unwind_idx,
-				   __stop_unwind_idx - 1);
-	else {
+				   __origin_unwind_idx,
+				   __stop_unwind_idx);
+	} else {
 		/* module unwind tables */
 		struct unwind_table *table;
 
@@ -145,7 +200,8 @@ static struct unwind_idx *unwind_find_idx(unsigned long addr)
 			if (addr >= table->begin_addr &&
 			    addr < table->end_addr) {
 				idx = search_index(addr, table->start,
-						   table->stop - 1);
+						   table->origin,
+						   table->stop);
 				/* Move-to-front to exploit common traces */
 				list_move(&table->list, &unwind_tables);
 				break;
@@ -274,7 +330,7 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 int unwind_frame(struct stackframe *frame)
 {
 	unsigned long high, low;
-	struct unwind_idx *idx;
+	const struct unwind_idx *idx;
 	struct unwind_ctrl_block ctrl;
 
 	/* only go to a higher address on the stack */
@@ -399,7 +455,6 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
 				      unsigned long text_size)
 {
 	unsigned long flags;
-	struct unwind_idx *idx;
 	struct unwind_table *tab = kmalloc(sizeof(*tab), GFP_KERNEL);
 
 	pr_debug("%s(%08lx, %08lx, %08lx, %08lx)\n", __func__, start, size,
@@ -408,15 +463,12 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
 	if (!tab)
 		return tab;
 
-	tab->start = (struct unwind_idx *)start;
-	tab->stop = (struct unwind_idx *)(start + size);
+	tab->start = (const struct unwind_idx *)start;
+	tab->stop = (const struct unwind_idx *)(start + size);
+	tab->origin = unwind_find_origin(tab->start, tab->stop);
 	tab->begin_addr = text_addr;
 	tab->end_addr = text_addr + text_size;
 
-	/* Convert the symbol addresses to absolute values */
-	for (idx = tab->start; idx < tab->stop; idx++)
-		idx->addr = prel31_to_addr(&idx->addr);
-
 	spin_lock_irqsave(&unwind_lock, flags);
 	list_add_tail(&tab->list, &unwind_tables);
 	spin_unlock_irqrestore(&unwind_lock, flags);
@@ -437,16 +489,3 @@ void unwind_table_del(struct unwind_table *tab)
 
 	kfree(tab);
 }
-
-int __init unwind_init(void)
-{
-	struct unwind_idx *idx;
-
-	/* Convert the symbol addresses to absolute values */
-	for (idx = __start_unwind_idx; idx < __stop_unwind_idx; idx++)
-		idx->addr = prel31_to_addr(&idx->addr);
-
-	pr_debug("unwind: ARM stack unwinding initialised\n");
-
-	return 0;
-}
-- 
1.7.7.2

[PATCH] ARM: fix unwinding for XIP kernels

[Nicolas Pitre]

On Wed, 30 Nov 2011, Uwe Kleine-K?nig wrote:

> The linker places the unwind tables in readonly sections. So when using
> an XIP kernel these are located in ROM and cannot be modified.
> For that reason the current approach to convert the relative offsets in
> the unwind index to absolute addresses early in the boot process doesn't
> work with XIP.
> 
> The offsets in the unwind index section are signed 31 bit numbers and
> the structs are sorted by this offset. So it first has offsets between
> 0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
> between 0x00000000 and 0x3fffffff. When seperating these two blocks the
> numbers are sorted even when interpreting the offsets as unsigned longs.
> 
> So determine the first non-negative entry once and track that using the
> new origin pointer. The actual bisection can then use a plain unsigned
> long comparison. The only thing that makes the new bisection more
> complicated is that the offsets are relative to their position in the
> index section, so the key to search needs to be adapted accordingly in
> each step.
> 
> Moreover several consts are added to catch future writes and rename the
> member "addr" of struct unwind_idx to "addr_offset" to better match the
> new semantic. (This has the additional benefit of breaking eventual
> users at compile time to make them aware of the change.)
> 
> In my tests the new algorithm was a tad faster than the original and has
> the additional upside of not needing the initial conversion and so saves
> some boot time and it's possible to unwind even earlier.
> 
> Cc: Catalin Marinas <catalin.marinas@arm.com>
> Cc: Nicolas Pitre <nico@fluxnic.net>

Acked-by: Nicolas Pitre <nico@linaro.org>

> Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>
> ---
> Hello,
> 
> the code is the same as the two previous patches combined, only some
> whitespace changes.
> 
> There are a few checkpatch issues left, namely one line over 80 chars
> (which was already there before and IMHO is ok) and two warnings about
> externs in arch/arm/kernel/unwind.c (__start_unwind_idx and
> __stop_unwind_idx) which are ok, too. These externs were there before
> and only the unwinder should care about them.
> 
> Thanks to Catalin to take the time to review my work.
> 
> Best regards
> Uwe
> 
>  arch/arm/include/asm/unwind.h |   16 +----
>  arch/arm/kernel/setup.c       |    2 -
>  arch/arm/kernel/unwind.c      |  129 ++++++++++++++++++++++++++--------------
>  3 files changed, 88 insertions(+), 59 deletions(-)
> 
> diff --git a/arch/arm/include/asm/unwind.h b/arch/arm/include/asm/unwind.h
> index a5edf42..d1c3f3a 100644
> --- a/arch/arm/include/asm/unwind.h
> +++ b/arch/arm/include/asm/unwind.h
> @@ -30,14 +30,15 @@ enum unwind_reason_code {
>  };
>  
>  struct unwind_idx {
> -	unsigned long addr;
> +	unsigned long addr_offset;
>  	unsigned long insn;
>  };
>  
>  struct unwind_table {
>  	struct list_head list;
> -	struct unwind_idx *start;
> -	struct unwind_idx *stop;
> +	const struct unwind_idx *start;
> +	const struct unwind_idx *origin;
> +	const struct unwind_idx *stop;
>  	unsigned long begin_addr;
>  	unsigned long end_addr;
>  };
> @@ -49,15 +50,6 @@ extern struct unwind_table *unwind_table_add(unsigned long start,
>  extern void unwind_table_del(struct unwind_table *tab);
>  extern void unwind_backtrace(struct pt_regs *regs, struct task_struct *tsk);
>  
> -#ifdef CONFIG_ARM_UNWIND
> -extern int __init unwind_init(void);
> -#else
> -static inline int __init unwind_init(void)
> -{
> -	return 0;
> -}
> -#endif
> -
>  #endif	/* !__ASSEMBLY__ */
>  
>  #ifdef CONFIG_ARM_UNWIND
> diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
> index 7e7977a..cf9d71a 100644
> --- a/arch/arm/kernel/setup.c
> +++ b/arch/arm/kernel/setup.c
> @@ -893,8 +893,6 @@ void __init setup_arch(char **cmdline_p)
>  {
>  	struct machine_desc *mdesc;
>  
> -	unwind_init();
> -
>  	setup_processor();
>  	mdesc = setup_machine_fdt(__atags_pointer);
>  	if (!mdesc)
> diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
> index e7e8365..3f03fe0 100644
> --- a/arch/arm/kernel/unwind.c
> +++ b/arch/arm/kernel/unwind.c
> @@ -67,7 +67,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
>  
>  struct unwind_ctrl_block {
>  	unsigned long vrs[16];		/* virtual register set */
> -	unsigned long *insn;		/* pointer to the current instructions word */
> +	const unsigned long *insn;	/* pointer to the current instructions word */
>  	int entries;			/* number of entries left to interpret */
>  	int byte;			/* current byte number in the instructions word */
>  };
> @@ -83,8 +83,9 @@ enum regs {
>  	PC = 15
>  };
>  
> -extern struct unwind_idx __start_unwind_idx[];
> -extern struct unwind_idx __stop_unwind_idx[];
> +extern const struct unwind_idx __start_unwind_idx[];
> +static const struct unwind_idx *__origin_unwind_idx;
> +extern const struct unwind_idx __stop_unwind_idx[];
>  
>  static DEFINE_SPINLOCK(unwind_lock);
>  static LIST_HEAD(unwind_tables);
> @@ -98,45 +99,99 @@ static LIST_HEAD(unwind_tables);
>  })
>  
>  /*
> - * Binary search in the unwind index. The entries entries are
> + * Binary search in the unwind index. The entries are
>   * guaranteed to be sorted in ascending order by the linker.
> + *
> + * start = first entry
> + * origin = first entry with positive offset (or stop if there is no such entry)
> + * stop - 1 = last entry
>   */
> -static struct unwind_idx *search_index(unsigned long addr,
> -				       struct unwind_idx *first,
> -				       struct unwind_idx *last)
> +static const struct unwind_idx *search_index(unsigned long addr,
> +				       const struct unwind_idx *start,
> +				       const struct unwind_idx *origin,
> +				       const struct unwind_idx *stop)
>  {
> -	pr_debug("%s(%08lx, %p, %p)\n", __func__, addr, first, last);
> +	unsigned long addr_prel31;
> +
> +	pr_debug("%s(%08lx, %p, %p, %p)\n",
> +			__func__, addr, start, origin, stop);
> +
> +	/*
> +	 * only search in the section with the matching sign. This way the
> +	 * prel31 numbers can be compared as unsigned longs.
> +	 */
> +	if (addr < (unsigned long)start)
> +		/* negative offsets: [start; origin) */
> +		stop = origin;
> +	else
> +		/* positive offsets: [origin; stop) */
> +		start = origin;
> +
> +	/* prel31 for address relavive to start */
> +	addr_prel31 = (addr - (unsigned long)start) & 0x7fffffff;
>  
> -	if (addr < first->addr) {
> +	while (start < stop - 1) {
> +		const struct unwind_idx *mid = start + ((stop - start) >> 1);
> +
> +		/*
> +		 * As addr_prel31 is relative to start an offset is needed to
> +		 * make it relative to mid.
> +		 */
> +		if (addr_prel31 - ((unsigned long)mid - (unsigned long)start) <
> +				mid->addr_offset)
> +			stop = mid;
> +		else {
> +			/* keep addr_prel31 relative to start */
> +			addr_prel31 -= ((unsigned long)mid -
> +					(unsigned long)start);
> +			start = mid;
> +		}
> +	}
> +
> +	if (likely(start->addr_offset <= addr_prel31))
> +		return start;
> +	else {
>  		pr_warning("unwind: Unknown symbol address %08lx\n", addr);
>  		return NULL;
> -	} else if (addr >= last->addr)
> -		return last;
> +	}
> +}
>  
> -	while (first < last - 1) {
> -		struct unwind_idx *mid = first + ((last - first + 1) >> 1);
> +static const struct unwind_idx *unwind_find_origin(
> +		const struct unwind_idx *start, const struct unwind_idx *stop)
> +{
> +	pr_debug("%s(%p, %p)\n", __func__, start, stop);
> +	while (start < stop - 1) {
> +		const struct unwind_idx *mid = start + ((stop - start) >> 1);
>  
> -		if (addr < mid->addr)
> -			last = mid;
> +		if (mid->addr_offset >= 0x40000000)
> +			/* negative offset */
> +			start = mid;
>  		else
> -			first = mid;
> +			/* positive offset */
> +			stop = mid;
>  	}
> -
> -	return first;
> +	pr_debug("%s -> %p\n", __func__, stop);
> +	return stop;
>  }
>  
> -static struct unwind_idx *unwind_find_idx(unsigned long addr)
> +static const struct unwind_idx *unwind_find_idx(unsigned long addr)
>  {
> -	struct unwind_idx *idx = NULL;
> +	const struct unwind_idx *idx = NULL;
>  	unsigned long flags;
>  
>  	pr_debug("%s(%08lx)\n", __func__, addr);
>  
> -	if (core_kernel_text(addr))
> +	if (core_kernel_text(addr)) {
> +		if (unlikely(!__origin_unwind_idx))
> +			__origin_unwind_idx =
> +				unwind_find_origin(__start_unwind_idx,
> +						__stop_unwind_idx);
> +
>  		/* main unwind table */
>  		idx = search_index(addr, __start_unwind_idx,
> -				   __stop_unwind_idx - 1);
> -	else {
> +				   __origin_unwind_idx,
> +				   __stop_unwind_idx);
> +	} else {
>  		/* module unwind tables */
>  		struct unwind_table *table;
>  
> @@ -145,7 +200,8 @@ static struct unwind_idx *unwind_find_idx(unsigned long addr)
>  			if (addr >= table->begin_addr &&
>  			    addr < table->end_addr) {
>  				idx = search_index(addr, table->start,
> -						   table->stop - 1);
> +						   table->origin,
> +						   table->stop);
>  				/* Move-to-front to exploit common traces */
>  				list_move(&table->list, &unwind_tables);
>  				break;
> @@ -274,7 +330,7 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
>  int unwind_frame(struct stackframe *frame)
>  {
>  	unsigned long high, low;
> -	struct unwind_idx *idx;
> +	const struct unwind_idx *idx;
>  	struct unwind_ctrl_block ctrl;
>  
>  	/* only go to a higher address on the stack */
> @@ -399,7 +455,6 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
>  				      unsigned long text_size)
>  {
>  	unsigned long flags;
> -	struct unwind_idx *idx;
>  	struct unwind_table *tab = kmalloc(sizeof(*tab), GFP_KERNEL);
>  
>  	pr_debug("%s(%08lx, %08lx, %08lx, %08lx)\n", __func__, start, size,
> @@ -408,15 +463,12 @@ struct unwind_table *unwind_table_add(unsigned long start, unsigned long size,
>  	if (!tab)
>  		return tab;
>  
> -	tab->start = (struct unwind_idx *)start;
> -	tab->stop = (struct unwind_idx *)(start + size);
> +	tab->start = (const struct unwind_idx *)start;
> +	tab->stop = (const struct unwind_idx *)(start + size);
> +	tab->origin = unwind_find_origin(tab->start, tab->stop);
>  	tab->begin_addr = text_addr;
>  	tab->end_addr = text_addr + text_size;
>  
> -	/* Convert the symbol addresses to absolute values */
> -	for (idx = tab->start; idx < tab->stop; idx++)
> -		idx->addr = prel31_to_addr(&idx->addr);
> -
>  	spin_lock_irqsave(&unwind_lock, flags);
>  	list_add_tail(&tab->list, &unwind_tables);
>  	spin_unlock_irqrestore(&unwind_lock, flags);
> @@ -437,16 +489,3 @@ void unwind_table_del(struct unwind_table *tab)
>  
>  	kfree(tab);
>  }
> -
> -int __init unwind_init(void)
> -{
> -	struct unwind_idx *idx;
> -
> -	/* Convert the symbol addresses to absolute values */
> -	for (idx = __start_unwind_idx; idx < __stop_unwind_idx; idx++)
> -		idx->addr = prel31_to_addr(&idx->addr);
> -
> -	pr_debug("unwind: ARM stack unwinding initialised\n");
> -
> -	return 0;
> -}
> -- 
> 1.7.7.2
> 

[PATCH] ARM: fix unwinding for XIP kernels

[Catalin Marinas]

2011/11/30 Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>:
> The linker places the unwind tables in readonly sections. So when using
> an XIP kernel these are located in ROM and cannot be modified.
> For that reason the current approach to convert the relative offsets in
> the unwind index to absolute addresses early in the boot process doesn't
> work with XIP.
>
> The offsets in the unwind index section are signed 31 bit numbers and
> the structs are sorted by this offset. So it first has offsets between
> 0x40000000 and 0x7fffffff (i.e. the negative offsets) and then offsets
> between 0x00000000 and 0x3fffffff. When seperating these two blocks the
> numbers are sorted even when interpreting the offsets as unsigned longs.
>
> So determine the first non-negative entry once and track that using the
> new origin pointer. The actual bisection can then use a plain unsigned
> long comparison. The only thing that makes the new bisection more
> complicated is that the offsets are relative to their position in the
> index section, so the key to search needs to be adapted accordingly in
> each step.
>
> Moreover several consts are added to catch future writes and rename the
> member "addr" of struct unwind_idx to "addr_offset" to better match the
> new semantic. (This has the additional benefit of breaking eventual
> users at compile time to make them aware of the change.)
>
> In my tests the new algorithm was a tad faster than the original and has
> the additional upside of not needing the initial conversion and so saves
> some boot time and it's possible to unwind even earlier.
>
> Cc: Catalin Marinas <catalin.marinas@arm.com>
> Cc: Nicolas Pitre <nico@fluxnic.net>
> Signed-off-by: Uwe Kleine-K?nig <u.kleine-koenig@pengutronix.de>

Acked-by: Catalin Marinas <catalin.marinas@arm.com>