Bug 12092

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.

Created attachment 5037 [details]
slightly simplified test case

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
like


          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;
          else
        memory = 0;

Yep, resetting 'memory' after a large shift is required; I'm testing your idea now, but think you have the right patch in mind.

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;
 	      continue;
 	    }

Created attachment 5039 [details]
fix strstr and memmem

Please add a testcase and post to libc-alpha@sources.redhat.com.

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 
http://sourceware.org/bugzilla/show_bug.cgi?id=5514

$ 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. */
    default:
      return 2;
    }
}
$ for i in $(seq 6); do ./foo $i; echo $?; done
1
0
0
0
142
142

Fixed in git.

(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.