[Bug 1027977] Re: strstr() function produces wrong results under valgrind callgrind
Bug Watch Updater
1027977 at bugs.launchpad.net
Wed Jul 25 11:13:18 UTC 2012
Launchpad has imported 13 comments from the remote bug at
https://bugs.kde.org/show_bug.cgi?id=303963.
If you reply to an imported comment from within Launchpad, your comment
will be sent to the remote bug automatically. Read more about
Launchpad's inter-bugtracker facilities at
https://help.launchpad.net/InterBugTracking.
------------------------------------------------------------------------
On 2012-07-23T14:56:22+00:00 Moritz Hassert wrote:
Created attachment 72705
minimal test case
$valgrind --version
valgrind-3.7.0
When an application that uses the strstr() function from the C standard library is profiled with valgrind --tool=callgrind, the strstr() function produces false results (at least) under the following conditions:
* the string s1 to search in and the string s2 to search for are exact duplicates, that is strcmp(s1,s2)==0. s1 and s2 don't need to be pointing to the same memory object.
* the string length (excluding terminating zero) is a multiple of 16
Expected result: strstr(s1,s2) returns s1, indicating a match at the first charactor of s1
What happens: strstr(s1,s2) returns NULL, indicating no matching substring was found.
See attached minimal testcase for an example. Reproduce under Ubuntu 12.04 with the following steps:
$gcc strstrtest.c -o strstrtest
$./ strstrtest # <-- should report no errors
$valgrind --tool=callgrind ./ strstrtest # <-- should report errors for lengths multiple of 16
- The Problem does not show up under valgrind-3.6.0.SVN-Debian from Ubuntu 10.04 Lucid Lynx
- The Problem does not show up under tool=memcheck.
Some more info:
OS: Ubuntu 12.04 Precise Pangolin
$uname -a
Linux mhassert 3.2.0-26-generic #41-Ubuntu SMP Thu Jun 14 17:49:24 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/2
------------------------------------------------------------------------
On 2012-07-23T15:47:13+00:00 Josef-weidendorfer wrote:
I actually can reproduce this, both with VG 3.7.0 and VG 3.8.0.SVN.
This looks scary.
The strange thing is that callgrind just runs the original code, and does not
do any tricky redirections similar to memcheck. Therefore this bug also
happens with the tools none and cachegrind (just checked). It at least
looks like something bad is going on translating strstr machine code
in VEX.
/usr/bin/valgrind --tool=none ./strstrtest
==21970== Nulgrind, the minimal Valgrind tool
==21970== Copyright (C) 2002-2011, and GNU GPL'd, by Nicholas Nethercote.
==21970== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==21970== Command: ./strstrtest
==21970==
TEST1: strstr failed
TEST2: length 16: failed
...
Changing to component "general".
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/4
------------------------------------------------------------------------
On 2012-07-23T16:03:27+00:00 Josef-weidendorfer wrote:
The bug obviously happens in __strstr_sse42 (on 64bit).
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/5
------------------------------------------------------------------------
On 2012-07-23T17:25:12+00:00 Josef-weidendorfer wrote:
I just compared the control flow inside __strstr_sse42 on a real machine
(using gdb) and within valgrind (just running callgrind with "--collect-jumps=yes").
It looks like the VEX emulation of "pcmpistri" (used with mode "equal ordered")
is buggy.
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/6
------------------------------------------------------------------------
On 2012-07-23T20:30:40+00:00 Jseward wrote:
(In reply to comment #3)
> It looks like the VEX emulation of "pcmpistri" (used with mode "equal
> ordered") is buggy.
Josef, I am not surprised to hear that (+ thanks for chasing it). Which pcmpistri case
is it (iow, which immediate byte) ?
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/7
------------------------------------------------------------------------
On 2012-07-23T20:47:43+00:00 Josef-weidendorfer wrote:
(In reply to comment #4)
> Josef, I am not surprised to hear that (+ thanks for chasing it). Which
> pcmpistri case
> is it (iow, which immediate byte) ?
It's imm8 = 0xc. I think I found the problem:
There is a discrepancy between real hardware and emulation if the needle
is an empty string, ie. starts with "\0". This happens on the last call
to pcmpistri in __strstr_sse42 when the needle length is a multiple of
16.
For all positions in the haystack, VEX stops search whenever the end of the needle is found. As it starts with assuming "no hit found", all search results will be false.
In contrast to that, according to table 4-3 in the SDM, the real pcmpistri
starts with the assumption "hit found".
Patch, which makes the test case of this bug report work
(needs also be changed for the _wide variant):
--- a/VEX/priv/guest_generic_x87.c
+++ b/VEX/priv/guest_generic_x87.c
@@ -891,7 +891,7 @@ Bool compute_PCMPxSTRx ( /*OUT*/V128* resV,
UInt ni, hi;
UChar* argL = (UChar*)argLV;
UChar* argR = (UChar*)argRV;
- UInt boolRes = 0;
+ UInt boolRes = 0xFFFF;
UInt validL = ~(zmaskL | -zmaskL); // not(left(zmaskL))
UInt validR = ~(zmaskR | -zmaskR); // not(left(zmaskR))
for (hi = 0; hi < 16; hi++) {
@@ -905,7 +905,7 @@ Bool compute_PCMPxSTRx ( /*OUT*/V128* resV,
if (i >= 16) break;
if (argL[i] != argR[ni]) { m = 0; break; }
}
- boolRes |= (m << hi);
+ if (m==0) boolRes &= ~(1 << hi);
}
Of course it would be nice to add some test cases.
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/8
------------------------------------------------------------------------
On 2012-07-24T09:18:43+00:00 Jseward wrote:
The diff below adds test cases.
Index: none/tests/amd64/pcmpstr64.c
===================================================================
--- none/tests/amd64/pcmpstr64.c (revision 12776)
+++ none/tests/amd64/pcmpstr64.c (working copy)
@@ -639,6 +639,11 @@
try_istri(wot,h,s, "1111111111111234", "1111111111111234");
try_istri(wot,h,s, "a111111111111111", "000000000000000a");
try_istri(wot,h,s, "b111111111111111", "000000000000000a");
+
+ try_istri(wot,h,s, "b111111111111111", "0000000000000000");
+ try_istri(wot,h,s, "0000000000000000", "0000000000000000");
+ try_istri(wot,h,s, "123456789abcdef1", "0000000000000000");
+ try_istri(wot,h,s, "0000000000000000", "123456789abcdef1");
}
Index: none/tests/amd64/pcmpstr64w.c
===================================================================
--- none/tests/amd64/pcmpstr64w.c (revision 12776)
+++ none/tests/amd64/pcmpstr64w.c (working copy)
@@ -638,6 +638,11 @@
try_istri(wot,h,s, "1111111111111234", "1111111111111234");
try_istri(wot,h,s, "0a11111111111111", "000000000000000a");
try_istri(wot,h,s, "0b11111111111111", "000000000000000a");
+
+ try_istri(wot,h,s, "b111111111111111", "0000000000000000");
+ try_istri(wot,h,s, "0000000000000000", "0000000000000000");
+ try_istri(wot,h,s, "123456789abcdef1", "0000000000000000");
+ try_istri(wot,h,s, "0000000000000000", "123456789abcdef1");
}
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/9
------------------------------------------------------------------------
On 2012-07-24T09:23:01+00:00 Jseward wrote:
(In reply to comment #5)
Josef, thanks for chasing this:
> Patch, which makes the test case of this bug report work
> (needs also be changed for the _wide variant):
That unfortunately causes other test cases to fail.
The test programs (none/tests/amd64/pcmpstr64{,w}.c) can be used to
test the C logic without using Valgrind, because they contain a copy
of same code that is in guest_generic_x87.c and they compare the
output against the real instruction. Hence you can do this:
gcc -Wall -g -O -o foo none/tests/amd64/pcmpstr64.c && ./foo | grep
"\!\!\!"
and it will show any lines where the C simulation is wrong. With
the test case additions in the previous comment, I get:
sewardj at phoenix:~/VgTRUNK/trunk$ gcc -Wall -g -O -o foo none/tests/amd64/pcmpstr64.c && ./foo | grep "\!\!\!"
istri 0C 00abcde100bcde11 00000000000abcde -> 00c00010 00c10006 !!!!
istri 0C 0000000000000000 123456789abcdef1 -> 00400010 08410000 !!!!
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/10
------------------------------------------------------------------------
On 2012-07-24T15:39:20+00:00 Josef-weidendorfer wrote:
Forget the previous patch.
Actually, it is enough to move the break condition checking the end of
the haystack to the end of the loop. This allows an empty needle to match
an empty haystack. Passes all tests, including the new ones from
comment 6.
--- a/priv/guest_generic_x87.c
+++ b/priv/guest_generic_x87.c
@@ -895,9 +895,6 @@ Bool compute_PCMPxSTRx ( /*OUT*/V128* resV,
UInt validL = ~(zmaskL | -zmaskL); // not(left(zmaskL))
UInt validR = ~(zmaskR | -zmaskR); // not(left(zmaskR))
for (hi = 0; hi < 16; hi++) {
- if ((validL & (1 << hi)) == 0)
- // run off the end of the haystack
- break;
UInt m = 1;
for (ni = 0; ni < 16; ni++) {
if ((validR & (1 << ni)) == 0) break;
@@ -906,6 +903,9 @@ Bool compute_PCMPxSTRx ( /*OUT*/V128* resV,
if (argL[i] != argR[ni]) { m = 0; break; }
}
boolRes |= (m << hi);
+ if ((validL & (1 << hi)) == 0)
+ // run off the end of the haystack
+ break;
}
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/11
------------------------------------------------------------------------
On 2012-07-24T16:23:53+00:00 Josef-weidendorfer wrote:
Created attachment 72727
Patch for VEX
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/12
------------------------------------------------------------------------
On 2012-07-24T16:24:39+00:00 Josef-weidendorfer wrote:
Created attachment 72728
Patch for VG (test case)
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/13
------------------------------------------------------------------------
On 2012-07-25T09:23:17+00:00 Jseward wrote:
> Created attachment 72727 [details]
> Patch for VEX
> Created attachment 72728 [details]
> Patch for VG (test case)
Looks fine, please commit!
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/14
------------------------------------------------------------------------
On 2012-07-25T09:51:20+00:00 Josef-weidendorfer wrote:
Fixed in VEX r2447
Reply at: https://bugs.launchpad.net/valgrind/+bug/1027977/comments/15
** Changed in: valgrind
Status: Unknown => Fix Released
** Changed in: valgrind
Importance: Unknown => Medium
--
You received this bug notification because you are a member of Ubuntu
Foundations Bugs, which is subscribed to valgrind in Ubuntu.
https://bugs.launchpad.net/bugs/1027977
Title:
strstr() function produces wrong results under valgrind callgrind
Status in Valgrind:
Fix Released
Status in “valgrind” package in Ubuntu:
New
Bug description:
$valgrind --version
valgrind-3.7.0
When an application that uses the strstr() function from the C standard library is profiled with valgrind --tool=callgrind, the strstr() function produces false results (at least) under the following conditions:
* the string s1 to search in and the string s2 to search for are exact duplicates, that is strcmp(s1,s2)==0. s1 and s2 don't need to be pointing to the same memory object.
* the string length (excluding terminating zero) is a multiple of 16
Expected result: strstr(s1,s2) returns s1, indicating a match at the first charactor of s1
What happens: strstr(s1,s2) returns NULL, indicating no matching substring was found.
See attached minimal testcase for an example. Reproduce under Ubuntu 12.04 with the following steps:
$gcc strstrtest.c -o strstrtest
$./ strstrtest # <-- should report no errors
$valgrind --tool=callgrind ./ strstrtest # <-- should report errors for lengths multiple of 16
- The Problem does not show up under valgrind-3.6.0.SVN-Debian from Ubuntu 10.04 Lucid Lynx
- The Problem does not show up under tool=memcheck.
Some more info:
OS: Ubuntu 12.04 Precise Pangolin
$uname -a
Linux mhassert 3.2.0-26-generic #41-Ubuntu SMP Thu Jun 14 17:49:24 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux
To manage notifications about this bug go to:
https://bugs.launchpad.net/valgrind/+bug/1027977/+subscriptions
More information about the foundations-bugs
mailing list