strstr broken for some inputs on pre-SSE4 machines

Created attachment 5035
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).

Additional analysis from <email address hidden>:

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
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
fix strstr and memmem

Please add a testcase and post to <email address hidden>.

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.