DBE table ordering

DBE table ordering

[Mark Huang]

search_one_table() in arch/mips/kernel/traps.c does a binary search for the
erring instruction address in the DBE table. What guarantee is there that
the table is in order by instruction address? It looks like the code hasn't
changed in a long time and it has worked for me since at least 2.4.3.
However, a top of tree (2.5.1) kernel crashes on me as soon as a get_dbe()
fails, because the table is out of order at link time---possibly run time if
there's some code that I missed that is reordering the table at __init. Any
ideas?

Thanks in advance,

--Mark

Re: DBE table ordering

[Keith Owens]

On Wed, 17 Apr 2002 15:21:56 -0700, 
"Mark Huang" <mhuang@broadcom.com> wrote:
>search_one_table() in arch/mips/kernel/traps.c does a binary search for the
>erring instruction address in the DBE table. What guarantee is there that
>the table is in order by instruction address? It looks like the code hasn't
>changed in a long time and it has worked for me since at least 2.4.3.
>However, a top of tree (2.5.1) kernel crashes on me as soon as a get_dbe()
>fails, because the table is out of order at link time---possibly run time if
>there's some code that I missed that is reordering the table at __init. Any
>ideas?

The kernel relies on several tables being correctly ordered by the
linker, including the initialization vectors, so it is a fair bet that
the linker is correctly appended these tables as the kernel is built.
What is more likely is that one of the exception table entries was
created out of order.  Please send the following output to me, not the
list.

objdump -h vmlinux
objdump -s -j __ex_table vmlinux
nm -a vmlinux

Re: DBE table ordering

[Mark Huang]

[-- Attachment #1: Type: text/plain, Size: 1177 bytes --]

>From the objdump output, it looks like the exception table is in order
at link time, but the DBE table is definitely out of order. What seems
to be throwing it off is the dummy call to get_dbe() in traps.c. After
sprinkling a few more calls to get_dbe() around the kernel and seeing
what happens during link, it looks like any call to get_dbe() inside an
__init section (or probably any explicitly located section) will throw
off the ordering of the table. 

I'd say just change the binary search to a linear one, or reorder the
table at __init time if O(log n) is that important. If there were 600
entries in the table, sure, but I don't really see the benefit of the
additional code to deal with only a handful, as in most cases.

> The kernel relies on several tables being correctly ordered by the
> linker, including the initialization vectors, so it is a fair bet that
> the linker is correctly appended these tables as the kernel is built.
> What is more likely is that one of the exception table entries was
> created out of order.  Please send the following output to me, not the
> list.
> 
> objdump -h vmlinux
> objdump -s -j __ex_table vmlinux
> nm -a vmlinux
> 


[-- Attachment #2: traps.c.diff --]
[-- Type: text/x-diff, Size: 813 bytes --]

Index: arch/mips/kernel/traps.c
===================================================================
RCS file: /cvs/linux/arch/mips/kernel/traps.c,v
retrieving revision 1.107
diff -u -r1.107 traps.c
--- arch/mips/kernel/traps.c	2002/02/26 23:29:05	1.107
+++ arch/mips/kernel/traps.c	2002/04/18 06:36:06
@@ -360,17 +360,12 @@
 		 unsigned long value)
 {
 	const struct exception_table_entry *mid;
-	long diff;
 
-	while (first < last) {
-		mid = (last - first) / 2 + first;
-		diff = mid->insn - value;
-		if (diff < 0)
-			first = mid + 1;
-		else
-			last = mid;
+	for (mid = first; mid <= last; mid++) {
+		if (mid->insn == value)
+			return mid->nextinsn;
 	}
-	return (first == last && first->insn == value) ? first->nextinsn : 0;
+	return 0;
 }
 
 extern spinlock_t modlist_lock;

Re: DBE table ordering

[Mark Huang]

[-- Attachment #1: Type: text/plain, Size: 1176 bytes --]

From the objdump output, it looks like the exception table is in order
at link time, but the DBE table is definitely out of order. What seems
to be throwing it off is the dummy call to get_dbe() in traps.c. After
sprinkling a few more calls to get_dbe() around the kernel and seeing
what happens during link, it looks like any call to get_dbe() inside an
__init section (or probably any explicitly located section) will throw
off the ordering of the table. 

I'd say just change the binary search to a linear one, or reorder the
table at __init time if O(log n) is that important. If there were 600
entries in the table, sure, but I don't really see the benefit of the
additional code to deal with only a handful, as in most cases.

> The kernel relies on several tables being correctly ordered by the
> linker, including the initialization vectors, so it is a fair bet that
> the linker is correctly appended these tables as the kernel is built.
> What is more likely is that one of the exception table entries was
> created out of order.  Please send the following output to me, not the
> list.
> 
> objdump -h vmlinux
> objdump -s -j __ex_table vmlinux
> nm -a vmlinux
> 


[-- Attachment #2: traps.c.diff --]
[-- Type: text/x-diff, Size: 813 bytes --]

Index: arch/mips/kernel/traps.c
===================================================================
RCS file: /cvs/linux/arch/mips/kernel/traps.c,v
retrieving revision 1.107
diff -u -r1.107 traps.c
--- arch/mips/kernel/traps.c	2002/02/26 23:29:05	1.107
+++ arch/mips/kernel/traps.c	2002/04/18 06:36:06
@@ -360,17 +360,12 @@
 		 unsigned long value)
 {
 	const struct exception_table_entry *mid;
-	long diff;
 
-	while (first < last) {
-		mid = (last - first) / 2 + first;
-		diff = mid->insn - value;
-		if (diff < 0)
-			first = mid + 1;
-		else
-			last = mid;
+	for (mid = first; mid <= last; mid++) {
+		if (mid->insn == value)
+			return mid->nextinsn;
 	}
-	return (first == last && first->insn == value) ? first->nextinsn : 0;
+	return 0;
 }
 
 extern spinlock_t modlist_lock;

Re: DBE table ordering

[Keith Owens]

On 17 Apr 2002 23:39:16 -0700, 
"Mark Huang" <mhuang@broadcom.com> wrote:
>From the objdump output, it looks like the exception table is in order
>at link time, but the DBE table is definitely out of order. What seems
>to be throwing it off is the dummy call to get_dbe() in traps.c. After
>sprinkling a few more calls to get_dbe() around the kernel and seeing
>what happens during link, it looks like any call to get_dbe() inside an
>__init section (or probably any explicitly located section) will throw
>off the ordering of the table. 

That is what I expected.  Various tables are built up from special
sections in each object.  The linker is correctly appending those
sections to the final table in vmlinux.  The use of multiple text
sections (init, exit, the rest) means that entries in a table for each
object are not necessarily in order, breaking the assumption that the
overall table is in order.

This is a more general problem than mips dbe, other kernel tables and
other architectures will have the same problem.  I will do a general
patch against 2.5.8 to sort these tables at init time, and backport the
general fix to 2.4.19 later.  In the meantime your patch will bypass
the problem for mips dbe.

Re: DBE table ordering

[Keith Owens]

On 17 Apr 2002 23:39:16 -0700, 
"Mark Huang" <mhuang@broadcom.com> wrote:
From the objdump output, it looks like the exception table is in order
>at link time, but the DBE table is definitely out of order. What seems
>to be throwing it off is the dummy call to get_dbe() in traps.c. After
>sprinkling a few more calls to get_dbe() around the kernel and seeing
>what happens during link, it looks like any call to get_dbe() inside an
>__init section (or probably any explicitly located section) will throw
>off the ordering of the table. 

That is what I expected.  Various tables are built up from special
sections in each object.  The linker is correctly appending those
sections to the final table in vmlinux.  The use of multiple text
sections (init, exit, the rest) means that entries in a table for each
object are not necessarily in order, breaking the assumption that the
overall table is in order.

This is a more general problem than mips dbe, other kernel tables and
other architectures will have the same problem.  I will do a general
patch against 2.5.8 to sort these tables at init time, and backport the
general fix to 2.4.19 later.  In the meantime your patch will bypass
the problem for mips dbe.

Re: DBE table ordering

[Gleb O. Raiko]

Keith,

Keith Owens wrote:
> 
> This is a more general problem than mips dbe, other kernel tables and
> other architectures will have the same problem.  I will do a general
> patch against 2.5.8 to sort these tables at init time, and backport the
> general fix to 2.4.19 later.  In the meantime your patch will bypass
> the problem for mips dbe.

Consider it as a feature. It was known from the time Ralf designed it. 

If you really hate this behaviour and want to change it, I guess just
linear serach is OK. Or just introduce set of get/put_dbe{b,w,l}
routines instead of macros and expect just one fault address (well, 6
addresses, if you care). I think, it's better than rearranging the table
on startup (your proposal) and searching in several dbe tables (was
introduced last year).

Another table (in fact, I know only the unaligned access table in
arch/mips*/unaligned.c) is immune, because call from an __init routine
from user space is somewhat tricky and, anyway, isn't allowed.

If you know other tables, I think it's better to find a solution on
individual basis. No needs for a common solution here. 

Regards,
Gleb.

Re: DBE table ordering

[Keith Owens]

On Thu, 18 Apr 2002 13:37:14 +0400, 
"Gleb O. Raiko" <raiko@niisi.msk.ru> wrote:
>If you really hate this behaviour and want to change it, I guess just
>linear serach is OK.

Performance matters for these tables.  It is worth doing one sort at
boot time to let the kernel run faster all the time.  For some tables
(ia64 unwind) the API mandates that the table be in ascending order.

I just sent a general sort routine to l-k for comments before I do the
rest of the work.

Re: DBE table ordering

[Gleb O. Raiko]

Keith Owens wrote:
> 
> On Thu, 18 Apr 2002 13:37:14 +0400,
> "Gleb O. Raiko" <raiko@niisi.msk.ru> wrote:
> >If you really hate this behaviour and want to change it, I guess just
> >linear serach is OK.
> 
> Performance matters for these tables.  It is worth doing one sort at
> boot time to let the kernel run faster all the time.  For some tables
> (ia64 unwind) the API mandates that the table be in ascending order.
> 

No, performance doesn't matter here. First, we are speaking about DBE
exception which slowdowns performance. Second, get/put_dbe are used for
peripherial accesses which are slow anyway. Third, do you really want to
speed up probe routines where those macros are used? I guess, not.

Then, how many addresses you have in your dbe_table, 1000 or 6 ? I guess
the latter. In the worst case, linear search requires 12 comparisons,
while binary search takes 6. 6 extra comparisons is nothing in the dbe
handler. If you have more than 6 addresses in the table, just replace
macros by routines and get exactly 6. And 6 comparisons, btw, there is
no need for loop, just 6 if-statements.

I dont't know about other tables and other arches. Perhaps, they need
sorting of some tables. But, definetely, sorting isn't required for mips
dbe/unaligned access tables.

Regards,
Gleb.

Re: DBE table ordering

[Maciej W. Rozycki]

On Thu, 18 Apr 2002, Gleb O. Raiko wrote:

> I dont't know about other tables and other arches. Perhaps, they need
> sorting of some tables. But, definetely, sorting isn't required for mips
> dbe/unaligned access tables.

 Still it can be done for consistency.  It won't hurt, will it?

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: macro@ds2.pg.gda.pl, PGP key available        +

Re: DBE table ordering

[Gleb O. Raiko]

Maciej,

"Maciej W. Rozycki" wrote:
> 
> On Thu, 18 Apr 2002, Gleb O. Raiko wrote:
> 
> > I dont't know about other tables and other arches. Perhaps, they need
> > sorting of some tables. But, definetely, sorting isn't required for mips
> > dbe/unaligned access tables.
> 
>  Still it can be done for consistency.  It won't hurt, will it?
> 

Sure, it won't hurt performance. Just looks stupid in this place.

Even if we'll add something like dbe_memcpy, which will require a lot of
addresses in the table in order ot get adequate performance, it'll be
still stupid. And answer your next question, dbe_memcpy is needed for
accesses to busses like VME where Bus{Abort,Error,Fail} are quite legal
and traditionally all of them are traslated to DBE.

Regards,
Gleb.

Re: DBE table ordering

[Maciej W. Rozycki]

On Fri, 19 Apr 2002, Gleb O. Raiko wrote:

> Sure, it won't hurt performance. Just looks stupid in this place.

 If it's done uniformly across all such tables it isn't stupid any longer. 
The reason is some independent code may depend on the consistency now or
in the future and creating unnecessary exceptions to rules makes
maintenance complicated and prone to hard to detect errors.

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: macro@ds2.pg.gda.pl, PGP key available        +