On Mon, 17 Dec 2007 09:28:57 -0800 (PST)
Linus Torvalds <[EMAIL PROTECTED]> wrote:
>
>
> On Sat, 15 Dec 2007, Herbert Xu wrote:
> >
> > There ought to be a warning about this sort of thing.
>
> We could add it to sparse. The appended (untested) patch seems to say
> there's a lot of those signed divides-by-power-of-twos.
>
> However, the problem with such warnings is that it encourages people to do
> the simple fix that may be *wrong*. For example, you fixed it with patches
> like
>
> > - int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
> > + int rsvd = r->limit ? 0 : random_read_wakeup_thresh / 4u;
>
> which is really quite dangerous for several reasons:
>
> - it depends intimately on the type of the thing being divided (try it:
> it will do nothing at all if the thing you divide is larger than
> "unsigned int", since then the "4u" will be turned into a _signed_
> larger type by the C type expansion).
>
I was looking at lib/extable.c which does emit a signed divide on i386 but not
on x86_64:
mid = (last - first) / 2 + first;
So I tried to compiled this on x86_64 :
long *mid(long *a, long *b)
{
return ((a - b) / 2 + a);
}
It gave :
mid:
movq %rdi, %rdx
subq %rsi, %rdx
sarq $3, %rdx
movq %rdx, %rax
shrq $63, %rax
addq %rdx, %rax
sarq %rax
leaq (%rdi,%rax,8), %rax
ret
while
long *mid(long *a, long *b)
{
return ((a - b) / 2u + a);
}
gave :
mid:
movq %rdi, %rdx
subq %rsi, %rdx
sarq $3, %rdx
movq %rdx, %rax
shrq $63, %rax
addq %rdx, %rax
sarq %rax
leaq (%rdi,%rax,8), %rax
ret
and while :
long *mid(long *a, long *b)
{
return (((unsigned long)(a - b)) / 2 + a);
}
gave :
mid:
movq %rdi, %rax
subq %rsi, %rax
sarq %rax
andq $-8, %rax
addq %rdi, %rax
ret
But I found this cast ugly so I cooked this patch.
[PATCH] Avoid signed arithmetics in search_extable()
On i386 and gcc-4.2.{1|2}, search_extable() currently does integer divides (by
2 !!!), while
we can certainly use a right shift. This looks more a typical bsearch()
implementation.
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
diff --git a/lib/extable.c b/lib/extable.c
index 463f456..03a81bd 100644
--- a/lib/extable.c
+++ b/lib/extable.c
@@ -54,20 +54,20 @@ search_extable(const struct exception_table_entry *first,
const struct exception_table_entry *last,
unsigned long value)
{
- while (first <= last) {
- const struct exception_table_entry *mid;
+ unsigned long mid, low = 0, high = (last - first);
- mid = (last - first) / 2 + first;
+ while (low <= high) {
+ mid = (low + high) / 2;
/*
* careful, the distance between entries can be
- * larger than 2GB:
+ * larger than MAX_LONG:
*/
- if (mid->insn < value)
- first = mid + 1;
- else if (mid->insn > value)
- last = mid - 1;
+ if (first[mid].insn < value)
+ low = mid + 1;
+ else if (first[mid].insn > value)
+ high = mid - 1;
else
- return mid;
+ return first + mid;
}
return NULL;
}
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
