--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2008-01-05  Eric Blake  <ebb9@byu.net>
 
+	Avoid quadratic system memmem.
+	* m4/memmem.m4 (gl_FUNC_MEMMEM): Check for quadratic memmem.
+	Reported by Ralf Wildenhues.
+
 	Fix memmem test for mingw.
 	* modules/memmem-tests (configure.ac): Check for alarm.
 	* tests/test-memmem.c (main): Avoid alarm on platforms that lack

--- a/m4/memmem.m4
+++ b/m4/memmem.m4
@@ -1,5 +1,5 @@
-# memmem.m4 serial 6
-dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
+# memmem.m4 serial 7
+dnl Copyright (C) 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
 dnl with or without modifications, as long as this notice is preserved.
@@ -15,9 +15,28 @@
   if test $ac_cv_have_decl_memmem = no; then
     HAVE_DECL_MEMMEM=0
   else
-    AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works],
-      [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
-	  [return !memmem ("a", 1, NULL, 0);])],
+    AC_CACHE_CHECK([whether memmem works in linear time],
+      [gl_cv_func_memmem_works],
+      [AC_RUN_IFELSE([AC_LANG_PROGRAM([
+#include <string.h> /* for memmem */
+#include <stdlib.h> /* for malloc */
+#include <unistd.h> /* for alarm */
+], [[size_t m = 1000000;
+    char *haystack = (char *) malloc (2 * m + 1);
+    char *needle = (char *) malloc (m + 1);
+    void *result = 0;
+    /* Failure to compile this test due to missing alarm is okay,
+       since all such platforms (mingw) also lack memmem.  */
+    alarm (5);
+    if (haystack && needle)
+      {
+	memset (haystack, 'A', 2 * m);
+	haystack[2 * m] = 'B';
+	memset (needle, 'A', m);
+	needle[m] = 'B';
+	result = memmem (haystack, 2 * m + 1, needle, m + 1);
+      }
+    return !result || !memmem ("a", 1, 0, 0);]])],
 	[gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
 	[dnl pessimistically assume the worst, since even glibc 2.6.1
 	 dnl has quadratic complexity in its memmem