Bug 12092 - strstr broken for some inputs on pre-SSE4 machines
Summary: strstr broken for some inputs on pre-SSE4 machines
Alias: None
Product: glibc
Classification: Unclassified
Component: libc (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Ulrich Drepper
Depends on:
Reported: 2010-10-05 05:56 UTC by Paul Pluzhnikov
Modified: 2014-06-30 07:54 UTC (History)
5 users (show)

See Also:
Last reconfirmed:

what appears to be minimal test case (404 bytes, text/plain)
2010-10-05 05:56 UTC, Paul Pluzhnikov
slightly simplified test case (302 bytes, text/plain)
2010-10-05 17:36 UTC, Paul Pluzhnikov
fix strstr and memmem (630 bytes, patch)
2010-10-05 22:23 UTC, Eric Blake
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Paul Pluzhnikov 2010-10-05 05:56:48 UTC
Created attachment 5035 [details]
what appears to be minimal test case

Attached test case fails with glibc-2.11.1 and with current git trunk; passes with glibc-2.7.

The failure I see on SSE2 and SSE3 machines is:
BUG: 55 vs. 115

The bug does *not* show up on SSE4_2 machines (either 32 or 64-bit mode).
Comment 1 Paul Pluzhnikov 2010-10-05 17:08:33 UTC
Additional analysis from iant@google.com:

I'm not completely sure, but this is what I see so far.  The bug can only occur when the second argument to strstr (the needle) is periodic, which is to say that it consists entirely of some repeated string.  When that happens, the code can fail to match if the first argument to strstr (the haystack) contains two or more repetitions of the needle's periodic string, but not as many as the number of occurrences as are in the needle.  In that case strstr can sometimes return a pointer to the smaller number of repetitions, when it should properly return NULL or a later pointer.  Also, the needle has to be 32 bytes or more.
Comment 2 Paul Pluzhnikov 2010-10-05 17:36:31 UTC
Created attachment 5037 [details]
slightly simplified test case
Comment 3 Ian Lance Taylor 2010-10-05 18:17:44 UTC
I think the problem is the Boyer-Moore shift in two_way_long_needle in
str-two-way.h.  It does not correctly update MEMORY.  I think we need something

          if (memory && shift < period)
          /* Since needle is periodic, but the last period has
             a byte out of place, there can be no match until
             after the mismatch.  */
          shift = needle_len - period;
          memory = 0;
          else if (memory > shift)
        memory = memory - shift;
        memory = 0;
Comment 4 Eric Blake 2010-10-05 18:31:36 UTC
Yep, resetting 'memory' after a large shift is required; I'm testing your idea now, but think you have the right patch in mind.
Comment 5 Eric Blake 2010-10-05 22:10:16 UTC
Your test for (memory > shift) will never be reached.  Other than the assignment added by your proposed patch, memory is only ever assigned to be 0 or needle_len - period.  And for a periodic needle, shift is either needle_len or < period, by virtue of how the shift table is constructed.  Therefore, if memory is non-zero but shift >= period, then shift is necessarily > memory at that point.

Which means your code can be reduced to this simpler patch:

diff --git i/string/str-two-way.h w/string/str-two-way.h
index 502af47..76044b3 100644
--- i/string/str-two-way.h
+++ w/string/str-two-way.h
@@ -350,8 +350,8 @@ two_way_long_needle (const unsigned char *haystack,
 		     a byte out of place, there can be no match until
 		     after the mismatch.  */
 		  shift = needle_len - period;
-		  memory = 0;
+	      memory = 0;
 	      j += shift;
Comment 6 Eric Blake 2010-10-05 22:23:54 UTC
Created attachment 5039 [details]
fix strstr and memmem
Comment 7 Jakub Jelinek 2010-10-05 22:29:09 UTC
Please add a testcase and post to libc-alpha@sources.redhat.com.
Comment 8 Eric Blake 2010-10-06 15:43:59 UTC
Interestingly enough:

strstr() and strcasestr() are only broken pre-SSE4, but memmem() is broken even on SSE4 machines.

On the other hand, on SSE4 machines, strstr() and strcasestr() are quadratic in behavior; in other words, the use of an assembly implementation has actually caused a performance regression over the fix for 

$ cat foo.c
#define _GNU_SOURCE
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>

#define P ":012345678-"

static void quit (int sig) { exit (sig + 128); }
int main(int argc, char **argv)
  const char *hay = ";" ":013245678-" P P ":012345678." P ":012345678." P;
  const char *needle = P P P;

  size_t m = 1000000;
  char *largehay = malloc (2 * m + 2);
  char *largeneedle = malloc (m + 2);
  signal (SIGALRM, quit);
  alarm (5);
  if (!largehay || !largeneedle)
    return 2;
  memset (largehay, 'A', 2 * m);
  largehay[2 * m] = 'B';
  largehay[2 * m + 1] = 0;
  memset (largeneedle, 'A', m);
  largeneedle[m] = 'B';
  largeneedle[m + 1] = 0;
  switch (argc > 1 ? atoi (argv[1]) : 0)
      /* Demonstrate str-two-way.h bug. */
    case 1:
      return !!memmem (hay, strlen (hay), needle, strlen (needle));
    case 2:
      return !!strstr (hay, needle);
    case 3:
      return !!strcasestr (hay, needle);

      /* Demonstrate quadratic behavior. */
    case 4:
      return !memmem (largehay, strlen (largehay),
		      largeneedle, strlen (largeneedle));
    case 5:
      return !strstr (largehay, largeneedle);
    case 6:
      return !strcasestr (largehay, largeneedle);

      /* Usage error. */
      return 2;
$ for i in $(seq 6); do ./foo $i; echo $?; done
Comment 9 Ulrich Drepper 2010-10-06 17:50:05 UTC
Fixed in git.
Comment 10 Eric Blake 2010-10-06 17:58:36 UTC
(In reply to comment #9)
> Fixed in git.

The incorrect results of memmem() and of non-SSE4 strstr() are fixed.  However, the glibc 2.11 regression of reintroducing quadratic behavior for SSE4 strstr is not yet fixed.