string/test-strstr.c

   1 /* Test and measure strstr functions.
   2    Copyright (C) 2010-2024 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #define TEST_MAIN
  20 #ifndef WIDE
  21 # define TEST_NAME "strstr"
  22 # define TEST_FUNC strstr
  23 #else
  24 # define TEST_NAME "wcsstr"
  25 # define TEST_FUNC wcsstr
  26 #endif
  27
  28 #ifndef WIDE
  29 # define CHAR char
  30 # define STRLEN strlen
  31 # define STRCPY strcpy
  32 # define MEMCPY memcpy
  33 # define MEMSET memset
  34 # define MEMPCPY mempcpy
  35 # define L(s) s
  36 #else
  37 # include <wchar.h>
  38 # define CHAR wchar_t
  39 # define STRLEN wcslen
  40 # define STRCPY wcscpy
  41 # define MEMCPY wmemcpy
  42 # define MEMSET wmemset
  43 # define MEMPCPY wmempcpy
  44 # define L(s) L ## s
  45 /* The test requires up to 8191 characters, so allocate at least 32Kb
  46    (considering 4kb page size).  */
  47 # define BUF1PAGES 4
  48 #endif
  49
  50 #include "test-string.h"
  51
  52 #ifndef WIDE
  53 # define STRSTR c_strstr
  54 # define libc_hidden_builtin_def(arg) /* nothing */
  55 # define __strnlen strnlen
  56 # include "strstr.c"
  57 # define C_IMPL STRSTR
  58 #else
  59 # undef weak_alias
  60 # define weak_alias(a, b)
  61 # define WCSSTR c_wcsstr
  62 # define __wmemcmp wmemcmp
  63 # define __wcsnlen wcsnlen
  64 # define __wcslen wcslen
  65 # include "wcsstr.c"
  66 # define C_IMPL WCSSTR
  67 #endif
  68
  69 /* Naive implementation to verify results.  */
  70 static CHAR *
  71 simple_strstr (const CHAR *s1, const CHAR *s2)
  72 {
  73   ssize_t s1len = STRLEN (s1);
  74   ssize_t s2len = STRLEN (s2);
  75
  76   if (s2len > s1len)
  77     return NULL;
  78
  79   for (ssize_t i = 0; i <= s1len - s2len; ++i)
  80     {
  81       size_t j;
  82       for (j = 0; j < s2len; ++j)
  83         if (s1[i + j] != s2[j])
  84           break;
  85       if (j == s2len)
  86         return (CHAR *) s1 + i;
  87     }
  88
  89   return NULL;
  90 }
  91
  92
  93 typedef CHAR *(*proto_t) (const CHAR *, const CHAR *);
  94
  95 IMPL (C_IMPL, 1)
  96 IMPL (TEST_FUNC, 1)
  97
  98 static int
  99 check_result (impl_t *impl, const CHAR *s1, const CHAR *s2,
 100               CHAR *exp_result)
 101 {
 102   CHAR *result = CALL (impl, s1, s2);
 103   if (result != exp_result)
 104     {
 105       error (0, 0, "Wrong result in function %s %p %p", impl->name,
 106              result, exp_result);
 107       ret = 1;
 108       return -1;
 109     }
 110
 111   return 0;
 112 }
 113
 114 static void
 115 do_one_test (impl_t *impl, const CHAR *s1, const CHAR *s2, CHAR *exp_result)
 116 {
 117   if (check_result (impl, s1, s2, exp_result) < 0)
 118     return;
 119 }
 120
 121
 122 static void
 123 do_test (size_t align1, size_t align2, size_t len1, size_t len2,
 124          int fail)
 125 {
 126   align1 = align1 * sizeof (CHAR);
 127   align2 = align2 * sizeof (CHAR);
 128
 129   CHAR *s1 = (CHAR *) (buf1 + align1);
 130   CHAR *s2 = (CHAR *) (buf2 + align2);
 131
 132   static const CHAR d[] = L("1234567890abcdef");
 133   const size_t dl = STRLEN (d);
 134   CHAR *ss2 = s2;
 135   for (size_t l = len2; l > 0; l = l > dl ? l - dl : 0)
 136     {
 137       size_t t = l > dl ? dl : l;
 138       ss2 = MEMPCPY (ss2, d, t);
 139     }
 140   s2[len2] = '\0';
 141
 142   if (fail)
 143     {
 144       CHAR *ss1 = s1;
 145       for (size_t l = len1; l > 0; l = l > dl ? l - dl : 0)
 146         {
 147           size_t t = l > dl ? dl : l;
 148           MEMCPY (ss1, d, t);
 149           ++ss1[len2 > 7 ? 7 : len2 - 1];
 150           ss1 += t;
 151         }
 152     }
 153   else
 154     {
 155       MEMSET (s1, '0', len1);
 156       MEMCPY (s1 + len1 - len2, s2, len2);
 157     }
 158   s1[len1] = '\0';
 159
 160   FOR_EACH_IMPL (impl, 0)
 161     do_one_test (impl, s1, s2, fail ? NULL : s1 + len1 - len2);
 162 }
 163
 164 static void
 165 check1 (void)
 166 {
 167   const CHAR s1[] =
 168     L("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_A7_20_EF_BF_BD");
 169   const CHAR s2[] = L("_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
 170   CHAR *exp_result;
 171
 172   exp_result = simple_strstr (s1, s2);
 173   FOR_EACH_IMPL (impl, 0)
 174     check_result (impl, s1, s2, exp_result);
 175 }
 176
 177 static void
 178 check2 (void)
 179 {
 180   const CHAR s1_stack[] = L(", enable_static, \0, enable_shared, ");
 181   const size_t s1_char_count = 18;
 182   const size_t s1_byte_len = 18 * sizeof (CHAR);
 183   const CHAR *s2_stack = &(s1_stack[s1_char_count]);
 184   const size_t s2_byte_len = 18 * sizeof (CHAR);
 185   CHAR *exp_result;
 186   const size_t page_size_real = getpagesize ();
 187
 188   /* Haystack at end of page.  The following page is protected.  */
 189   CHAR *s1_page_end = (void *) buf1 + page_size - s1_byte_len;
 190   STRCPY (s1_page_end, s1_stack);
 191
 192   /* Haystack which crosses a page boundary.
 193      Note: page_size is at least 2 * getpagesize.  See test_init.  */
 194   CHAR *s1_page_cross = (void *) buf1 + page_size_real - 8;
 195   STRCPY (s1_page_cross, s1_stack);
 196
 197   /* Needle at end of page.  The following page is protected.  */
 198   CHAR *s2_page_end = (void *) buf2 + page_size - s2_byte_len;
 199   STRCPY (s2_page_end, s2_stack);
 200
 201   /* Needle which crosses a page boundary.
 202      Note: page_size is at least 2 * getpagesize.  See test_init.  */
 203   CHAR *s2_page_cross = (void *) buf2 + page_size_real - 8;
 204   STRCPY (s2_page_cross, s2_stack);
 205
 206   exp_result = simple_strstr (s1_stack, s2_stack);
 207   FOR_EACH_IMPL (impl, 0)
 208     {
 209       check_result (impl, s1_stack, s2_stack, exp_result);
 210       check_result (impl, s1_stack, s2_page_end, exp_result);
 211       check_result (impl, s1_stack, s2_page_cross, exp_result);
 212
 213       check_result (impl, s1_page_end, s2_stack, exp_result);
 214       check_result (impl, s1_page_end, s2_page_end, exp_result);
 215       check_result (impl, s1_page_end, s2_page_cross, exp_result);
 216
 217       check_result (impl, s1_page_cross, s2_stack, exp_result);
 218       check_result (impl, s1_page_cross, s2_page_end, exp_result);
 219       check_result (impl, s1_page_cross, s2_page_cross, exp_result);
 220     }
 221 }
 222
 223 static void
 224 check3 (void)
 225 {
 226   /* Check that a long periodic needle does not cause false positives.  */
 227   {
 228     const CHAR input[] = L("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 229                             "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 230                             "_C3_A7_20_EF_BF_BD");
 231     const CHAR need[] = L("_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
 232     FOR_EACH_IMPL (impl, 0)
 233       check_result (impl, input, need, NULL);
 234   }
 235
 236   {
 237     const CHAR input[] = L("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 238                            "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 239                            "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
 240                            "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
 241     const CHAR need[] = L("_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD");
 242     FOR_EACH_IMPL (impl, 0)
 243       check_result (impl, input, need, (CHAR *) input + 115);
 244   }
 245 }
 246
 247
 248 #define N 1024
 249
 250 static void
 251 pr23637 (void)
 252 {
 253   CHAR *h = (CHAR*) buf1;
 254   CHAR *n = (CHAR*) buf2;
 255
 256   for (int i = 0; i < N; i++)
 257     {
 258       n[i] = 'x';
 259       h[i] = ' ';
 260       h[i + N] = 'x';
 261     }
 262
 263   n[N] = '\0';
 264   h[N * 2] = '\0';
 265
 266   /* Ensure we don't match at the first 'x'.  */
 267   h[0] = 'x';
 268
 269   CHAR *exp_result = simple_strstr (h, n);
 270   FOR_EACH_IMPL (impl, 0)
 271     check_result (impl, h, n, exp_result);
 272 }
 273
 274 static void
 275 pr23865 (void)
 276 {
 277   /* Check that a very long haystack is handled quickly if the needle is
 278      short and occurs near the beginning.  */
 279   {
 280     size_t m = 1000000;
 281     const CHAR *needle =
 282       L("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 283         "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
 284     CHAR *haystack = xmalloc ((m + 1) * sizeof (CHAR));
 285     MEMSET (haystack, L('A'), m);
 286     haystack[0] = L('B');
 287     haystack[m] = L('\0');
 288
 289     FOR_EACH_IMPL (impl, 0)
 290       check_result (impl, haystack, needle, haystack + 1);
 291
 292     free (haystack);
 293   }
 294
 295   /* Check that a very long needle is discarded quickly if the haystack is
 296      short.  */
 297   {
 298     size_t m = 1000000;
 299     const CHAR *haystack =
 300       L("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 301         "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB");
 302     CHAR *needle = xmalloc ((m + 1) * sizeof (CHAR));
 303     MEMSET (needle, L'A', m);
 304     needle[m] = L('\0');
 305
 306     FOR_EACH_IMPL (impl, 0)
 307       check_result (impl, haystack, needle, NULL);
 308
 309     free (needle);
 310   }
 311
 312   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 313   {
 314     size_t m = 1000000;
 315     CHAR *haystack = xmalloc ((2 * m + 2) * sizeof (CHAR));
 316     CHAR *needle = xmalloc ((m + 2) * sizeof (CHAR));
 317
 318     MEMSET (haystack, L('A'), 2 * m);
 319     haystack[2 * m] = L('B');
 320     haystack[2 * m + 1] = L('\0');
 321
 322     MEMSET (needle, L('A'), m);
 323     needle[m] = L('B');
 324     needle[m + 1] = L('\0');
 325
 326     FOR_EACH_IMPL (impl, 0)
 327       check_result (impl, haystack, needle, haystack + m);
 328
 329     free (needle);
 330     free (haystack);
 331   }
 332
 333   {
 334     /* Ensure that with a barely periodic "short" needle, STRSTR's
 335        search does not mistakenly skip just past the match point.  */
 336     const CHAR *haystack =
 337       L("\n"
 338        "with_build_libsubdir\n"
 339        "with_local_prefix\n"
 340        "with_gxx_include_dir\n"
 341        "with_cpp_install_dir\n"
 342        "enable_generated_files_in_srcdir\n"
 343        "with_gnu_ld\n"
 344        "with_ld\n"
 345        "with_demangler_in_ld\n"
 346        "with_gnu_as\n"
 347        "with_as\n"
 348        "enable_largefile\n"
 349        "enable_werror_always\n"
 350        "enable_checking\n"
 351        "enable_coverage\n"
 352        "enable_gather_detailed_mem_stats\n"
 353        "enable_build_with_cxx\n"
 354        "with_stabs\n"
 355        "enable_multilib\n"
 356        "enable___cxa_atexit\n"
 357        "enable_decimal_float\n"
 358        "enable_fixed_point\n"
 359        "enable_threads\n"
 360        "enable_tls\n"
 361        "enable_objc_gc\n"
 362        "with_dwarf2\n"
 363        "enable_shared\n"
 364        "with_build_sysroot\n"
 365        "with_sysroot\n"
 366        "with_specs\n"
 367        "with_pkgversion\n"
 368        "with_bugurl\n"
 369        "enable_languages\n"
 370        "with_multilib_list\n");
 371     const CHAR *needle =
 372       L("\n"
 373        "with_gnu_ld\n");
 374
 375     FOR_EACH_IMPL (impl, 0)
 376       check_result (impl, haystack, needle, (CHAR*) haystack + 114);
 377   }
 378
 379   {
 380     /* Same bug, shorter trigger.  */
 381     const CHAR *haystack = L("..wi.d.");
 382     const CHAR *needle = L(".d.");
 383     FOR_EACH_IMPL (impl, 0)
 384       check_result (impl, haystack, needle, (CHAR*) haystack + 4);
 385   }
 386
 387   /* Test case from Yves Bastide.
 388      <https://www.openwall.com/lists/musl/2014/04/18/2>  */
 389   {
 390     const CHAR *input = L("playing play play play always");
 391     const CHAR *needle = L("play play play");
 392     FOR_EACH_IMPL (impl, 0)
 393       check_result (impl, input, needle, (CHAR*) input + 8);
 394   }
 395
 396   /* Test long needles.  */
 397   {
 398     size_t m = 1024;
 399     CHAR *haystack = xmalloc ((2 * m + 1) * sizeof (CHAR));
 400     CHAR *needle = xmalloc ((m + 1) * sizeof (CHAR));
 401     haystack[0] = L('x');
 402     MEMSET (haystack + 1, L(' '), m - 1);
 403     MEMSET (haystack + m, L('x'), m);
 404     haystack[2 * m] = L('\0');
 405     MEMSET (needle, L('x'), m);
 406     needle[m] = L('\0');
 407
 408     FOR_EACH_IMPL (impl, 0)
 409       check_result (impl, haystack, needle, haystack + m);
 410
 411     free (needle);
 412     free (haystack);
 413   }
 414 }
 415
 416 static int
 417 test_main (void)
 418 {
 419   test_init ();
 420
 421   check1 ();
 422   check2 ();
 423   check3 ();
 424   pr23637 ();
 425   pr23865 ();
 426
 427   printf ("%23s", "");
 428   FOR_EACH_IMPL (impl, 0)
 429     printf ("\t%s", impl->name);
 430   putchar ('\n');
 431
 432   for (size_t klen = 2; klen < 32; ++klen)
 433     for (size_t hlen = 2 * klen; hlen < 16 * klen; hlen += klen)
 434       {
 435         do_test (0, 0, hlen, klen, 0);
 436         do_test (0, 0, hlen, klen, 1);
 437         do_test (0, 3, hlen, klen, 0);
 438         do_test (0, 3, hlen, klen, 1);
 439         do_test (0, 9, hlen, klen, 0);
 440         do_test (0, 9, hlen, klen, 1);
 441         do_test (0, 15, hlen, klen, 0);
 442         do_test (0, 15, hlen, klen, 1);
 443
 444         do_test (3, 0, hlen, klen, 0);
 445         do_test (3, 0, hlen, klen, 1);
 446         do_test (3, 3, hlen, klen, 0);
 447         do_test (3, 3, hlen, klen, 1);
 448         do_test (3, 9, hlen, klen, 0);
 449         do_test (3, 9, hlen, klen, 1);
 450         do_test (3, 15, hlen, klen, 0);
 451         do_test (3, 15, hlen, klen, 1);
 452
 453         do_test (9, 0, hlen, klen, 0);
 454         do_test (9, 0, hlen, klen, 1);
 455         do_test (9, 3, hlen, klen, 0);
 456         do_test (9, 3, hlen, klen, 1);
 457         do_test (9, 9, hlen, klen, 0);
 458         do_test (9, 9, hlen, klen, 1);
 459         do_test (9, 15, hlen, klen, 0);
 460         do_test (9, 15, hlen, klen, 1);
 461
 462         do_test (15, 0, hlen, klen, 0);
 463         do_test (15, 0, hlen, klen, 1);
 464         do_test (15, 3, hlen, klen, 0);
 465         do_test (15, 3, hlen, klen, 1);
 466         do_test (15, 9, hlen, klen, 0);
 467         do_test (15, 9, hlen, klen, 1);
 468         do_test (15, 15, hlen, klen, 0);
 469         do_test (15, 15, hlen, klen, 1);
 470
 471         do_test (15, 15, hlen + klen * 4, klen * 4, 0);
 472         do_test (15, 15, hlen + klen * 4, klen * 4, 1);
 473       }
 474
 475   do_test (0, 0, page_size - 1, 16, 0);
 476   do_test (0, 0, page_size - 1, 16, 1);
 477
 478   return ret;
 479 }
 480
 481 #include <support/test-driver.c>