benchtests/bench-strncmp.c

   1 /* Measure strncmp functions.
   2    Copyright (C) 2013-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 #ifdef WIDE
  21 # define TEST_NAME "wcsncmp"
  22 #else
  23 # define TEST_NAME "strncmp"
  24 #endif
  25 #include "bench-string.h"
  26 #include "json-lib.h"
  27
  28 #ifdef WIDE
  29 # define STRDUP wcsdup
  30 #else
  31 # define STRDUP strdup
  32
  33 int
  34 generic_strncmp (const char *s1, const char *s2, size_t n);
  35
  36 IMPL (generic_strncmp, 0)
  37
  38 #endif
  39
  40 typedef int (*proto_t) (const CHAR *, const CHAR *, size_t);
  41
  42 IMPL (STRNCMP, 1)
  43
  44 static void
  45 do_one_test (json_ctx_t *json_ctx, impl_t *impl, const CHAR *s1, const CHAR
  46              *s2, size_t n, int exp_result)
  47 {
  48   size_t i, iters = INNER_LOOP_ITERS;
  49   timing_t start, stop, cur;
  50
  51   TIMING_NOW (start);
  52   for (i = 0; i < iters; ++i)
  53     {
  54       CALL (impl, s1, s2, n);
  55     }
  56   TIMING_NOW (stop);
  57
  58   TIMING_DIFF (cur, start, stop);
  59
  60   json_element_double (json_ctx, (double) cur / (double) iters);
  61 }
  62
  63 static void
  64 do_test_limit (json_ctx_t *json_ctx, size_t align1, size_t align2, size_t len,
  65                size_t n, int max_char, int exp_result)
  66 {
  67   size_t i, align_n;
  68   CHAR *s1, *s2;
  69
  70   align1 &= 15;
  71   align2 &= 15;
  72   align_n = (page_size - n * CHARBYTES) & 15;
  73
  74   json_element_object_begin (json_ctx);
  75   json_attr_uint (json_ctx, "strlen", (double) len);
  76   json_attr_uint (json_ctx, "len", (double) n);
  77   json_attr_uint (json_ctx, "align1", (double) align1);
  78   json_attr_uint (json_ctx, "align2", (double) align2);
  79   json_array_begin (json_ctx, "timings");
  80
  81   FOR_EACH_IMPL (impl, 0)
  82     {
  83       alloc_bufs ();
  84       s1 = (CHAR *) (buf1 + page_size - n * CHARBYTES);
  85       s2 = (CHAR *) (buf2 + page_size - n * CHARBYTES);
  86
  87       if (align1 < align_n)
  88         s1 = (CHAR *) ((char *) s1 - (align_n - align1));
  89
  90       if (align2 < align_n)
  91         s2 = (CHAR *) ((char *) s2 - (align_n - align2));
  92
  93       for (i = 0; i < n; i++)
  94         s1[i] = s2[i] = 1 + 23 * i % max_char;
  95
  96       if (len < n)
  97         {
  98           s1[len] = 0;
  99           s2[len] = 0;
 100           if (exp_result < 0)
 101             s2[len] = 32;
 102           else if (exp_result > 0)
 103             s1[len] = 64;
 104         }
 105
 106       do_one_test (json_ctx, impl, s1, s2, n, exp_result);
 107     }
 108
 109   json_array_end (json_ctx);
 110   json_element_object_end (json_ctx);
 111 }
 112
 113 static void
 114 do_test (json_ctx_t *json_ctx, size_t align1, size_t align2, size_t len, size_t
 115          n, int max_char, int exp_result)
 116 {
 117   size_t i;
 118   CHAR *s1, *s2;
 119
 120   if (n == 0)
 121     return;
 122
 123   align1 &= getpagesize () - 1;
 124   if (align1 + (n + 1) * CHARBYTES >= page_size)
 125     return;
 126
 127   align2 &= getpagesize () - 1;
 128   if (align2 + (n + 1) * CHARBYTES >= page_size)
 129     return;
 130
 131   json_element_object_begin (json_ctx);
 132   json_attr_uint (json_ctx, "strlen", (double)len);
 133   json_attr_uint (json_ctx, "len", (double)n);
 134   json_attr_uint (json_ctx, "align1", (double)align1);
 135   json_attr_uint (json_ctx, "align2", (double)align2);
 136   json_array_begin (json_ctx, "timings");
 137
 138   FOR_EACH_IMPL (impl, 0)
 139   {
 140     alloc_bufs ();
 141     s1 = (CHAR *)(buf1 + align1);
 142     s2 = (CHAR *)(buf2 + align2);
 143
 144     for (i = 0; i < n; i++)
 145       s1[i] = s2[i] = 1 + (23 << ((CHARBYTES - 1) * 8)) * i % max_char;
 146
 147     s1[n] = 24 + exp_result;
 148     s2[n] = 23;
 149     s1[len] = 0;
 150     s2[len] = 0;
 151     if (exp_result < 0)
 152       s2[len] = 32;
 153     else if (exp_result > 0)
 154       s1[len] = 64;
 155     if (len >= n)
 156       s2[n - 1] -= exp_result;
 157
 158     do_one_test (json_ctx, impl, s1, s2, n, exp_result);
 159   }
 160
 161   json_array_end (json_ctx);
 162   json_element_object_end (json_ctx);
 163 }
 164
 165 static void
 166 do_one_test_page_boundary (json_ctx_t *json_ctx, CHAR *s1, CHAR *s2,
 167                            size_t align1, size_t align2, size_t len,
 168                            size_t n, int exp_result)
 169 {
 170   json_element_object_begin (json_ctx);
 171   json_attr_uint (json_ctx, "strlen", (double) len);
 172   json_attr_uint (json_ctx, "len", (double) n);
 173   json_attr_uint (json_ctx, "align1", (double) align1);
 174   json_attr_uint (json_ctx, "align2", (double) align2);
 175   json_array_begin (json_ctx, "timings");
 176   FOR_EACH_IMPL (impl, 0)
 177     do_one_test (json_ctx, impl, s1, s2, n, exp_result);
 178   json_array_end (json_ctx);
 179   json_element_object_end (json_ctx);
 180 }
 181
 182 static void
 183 do_test_page_boundary (json_ctx_t *json_ctx)
 184 {
 185   /* To trigger bug 25933, we need a size that is equal to the vector
 186      length times 4. In the case of AVX2 for Intel, we need 32 * 4.  We
 187      make this test generic and run it for all architectures as additional
 188      boundary testing for such related algorithms.  */
 189   size_t size = 32 * 4;
 190   size_t len;
 191   CHAR *s1 = (CHAR *) (buf1 + (BUF1PAGES - 1) * page_size);
 192   CHAR *s2 = (CHAR *) (buf2 + (BUF1PAGES - 1) * page_size);
 193   int exp_result;
 194
 195   memset (s1, 'a', page_size);
 196   memset (s2, 'a', page_size);
 197
 198   s1[(page_size / CHARBYTES) - 1] = (CHAR) 0;
 199
 200   /* Iterate over a size that is just below where we expect the bug to
 201      trigger up to the size we expect will trigger the bug e.g. [99-128].
 202      Likewise iterate the start of two strings between 30 and 31 bytes
 203      away from the boundary to simulate alignment changes.  */
 204   for (size_t s = 99; s <= size; s++)
 205     for (size_t s1a = 30; s1a < 32; s1a++)
 206       for (size_t s2a = 30; s2a < 32; s2a++)
 207         {
 208           size_t align1 = (page_size / CHARBYTES - s) - s1a;
 209           size_t align2 = (page_size / CHARBYTES - s) - s2a;
 210           CHAR *s1p = s1 + align1;
 211           CHAR *s2p = s2 + align2;
 212           len = (page_size / CHARBYTES) - 1 - align1;
 213           exp_result = STRNCMP (s1p, s2p, s);
 214           do_one_test_page_boundary (json_ctx, s1p, s2p, align1, align2,
 215                                      len, s, exp_result);
 216         }
 217 }
 218
 219 static void
 220 do_one_test_page (json_ctx_t *json_ctx, size_t offset1, size_t offset2,
 221                   CHAR *s2)
 222 {
 223   CHAR *s1;
 224   int exp_result;
 225
 226   if (offset1 * CHARBYTES  >= page_size
 227       || offset2 * CHARBYTES >= page_size)
 228     return;
 229
 230   s1 = (CHAR *) buf1;
 231   s1 += offset1;
 232   s2 += offset2;
 233
 234   size_t len = (page_size / CHARBYTES) - offset1;
 235
 236   exp_result= *s1;
 237
 238   json_element_object_begin (json_ctx);
 239   json_attr_uint (json_ctx, "strlen", (double) len);
 240   json_attr_uint (json_ctx, "len", (double) page_size);
 241   json_attr_uint (json_ctx, "align1", (double) offset1);
 242   json_attr_uint (json_ctx, "align2", (double) offset2);
 243   json_array_begin (json_ctx, "timings");
 244   {
 245     FOR_EACH_IMPL (impl, 0)
 246       do_one_test (json_ctx, impl, s1, s2, page_size, -exp_result);
 247   }
 248   json_array_end (json_ctx);
 249   json_element_object_end (json_ctx);
 250
 251   json_element_object_begin (json_ctx);
 252   json_attr_uint (json_ctx, "strlen", (double) len);
 253   json_attr_uint (json_ctx, "len", (double) page_size);
 254   json_attr_uint (json_ctx, "align1", (double) offset1);
 255   json_attr_uint (json_ctx, "align2", (double) offset2);
 256   json_array_begin (json_ctx, "timings");
 257   {
 258     FOR_EACH_IMPL (impl, 0)
 259       do_one_test (json_ctx, impl, s1, s2, page_size, exp_result);
 260   }
 261   json_array_end (json_ctx);
 262   json_element_object_end (json_ctx);
 263 }
 264
 265 static void
 266 do_test_page (json_ctx_t *json_ctx)
 267 {
 268   size_t i;
 269   CHAR *s1, *s2;
 270
 271   s1 = (CHAR *) buf1;
 272   /* Fill buf1 with 23. */
 273   for (i = 0; i < (page_size / CHARBYTES) - 1; i++)
 274     s1[i] = 23;
 275   s1[i] = 0;
 276
 277   /* Make a copy of buf1.  */
 278   s2 = STRDUP (s1);
 279
 280   /* Test should terminate within the page boundary.  */
 281   for (i = 0; i < (108 / CHARBYTES); ++i)
 282     do_one_test_page (json_ctx, ((page_size - 108) / CHARBYTES) + i,
 283                       ((page_size - 1460) / CHARBYTES), s2);
 284
 285   free (s2);
 286 }
 287
 288 int
 289 test_main (void)
 290 {
 291   json_ctx_t json_ctx;
 292   size_t i, j, len;
 293   size_t pg_sz = getpagesize ();
 294
 295   test_init ();
 296
 297   json_init (&json_ctx, 0, stdout);
 298
 299   json_document_begin (&json_ctx);
 300   json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
 301
 302   json_attr_object_begin (&json_ctx, "functions");
 303   json_attr_object_begin (&json_ctx, TEST_NAME);
 304   json_attr_string (&json_ctx, "bench-variant", "default");
 305
 306   json_array_begin (&json_ctx, "ifuncs");
 307   FOR_EACH_IMPL (impl, 0)
 308   json_element_string (&json_ctx, impl->name);
 309   json_array_end (&json_ctx);
 310
 311   json_array_begin (&json_ctx, "results");
 312
 313   for (i = 0; i < 16; ++i)
 314     {
 315       do_test (&json_ctx, 0, 0, 8, i, 127, 0);
 316       do_test (&json_ctx, 0, 0, 8, i, 127, -1);
 317       do_test (&json_ctx, 0, 0, 8, i, 127, 1);
 318       do_test (&json_ctx, i, i, 8, i, 127, 0);
 319       do_test (&json_ctx, i, i, 8, i, 127, 1);
 320       do_test (&json_ctx, i, i, 8, i, 127, -1);
 321       do_test (&json_ctx, i, 2 * i, 8, i, 127, 0);
 322       do_test (&json_ctx, 2 * i, i, 8, i, 127, 1);
 323       do_test (&json_ctx, i, 3 * i, 8, i, 127, -1);
 324       do_test (&json_ctx, 0, 0, 8, i, 255, 0);
 325       do_test (&json_ctx, 0, 0, 8, i, 255, -1);
 326       do_test (&json_ctx, 0, 0, 8, i, 255, 1);
 327       do_test (&json_ctx, i, i, 8, i, 255, 0);
 328       do_test (&json_ctx, i, i, 8, i, 255, 1);
 329       do_test (&json_ctx, i, i, 8, i, 255, -1);
 330       do_test (&json_ctx, i, 2 * i, 8, i, 255, 0);
 331       do_test (&json_ctx, 2 * i, i, 8, i, 255, 1);
 332       do_test (&json_ctx, i, 3 * i, 8, i, 255, -1);
 333     }
 334
 335   for (len = 0; len <= 128; len += 64)
 336     {
 337       for (i = 1; i <= 8192;)
 338         {
 339           /* No page crosses.  */
 340           do_test (&json_ctx, 0, 0, i, i + len, 127, 0);
 341           do_test (&json_ctx, i * CHARBYTES, 0, i, i + len, 127, 0);
 342           do_test (&json_ctx, 0, i * CHARBYTES, i, i + len, 127, 0);
 343
 344           /* False page crosses.  */
 345           do_test (&json_ctx, pg_sz / 2, pg_sz / 2 - CHARBYTES, i, i + len,
 346                    127, 0);
 347           do_test (&json_ctx, pg_sz / 2 - CHARBYTES, pg_sz / 2, i, i + len,
 348                    127, 0);
 349
 350           do_test (&json_ctx, pg_sz - (i * CHARBYTES), 0, i, i + len, 127,
 351                    0);
 352           do_test (&json_ctx, 0, pg_sz - (i * CHARBYTES), i, i + len, 127,
 353                    0);
 354
 355           /* Real page cross.  */
 356           for (j = 16; j < 128; j += 16)
 357             {
 358               do_test (&json_ctx, pg_sz - j, 0, i, i + len, 127, 0);
 359               do_test (&json_ctx, 0, pg_sz - j, i, i + len, 127, 0);
 360
 361               do_test (&json_ctx, pg_sz - j, pg_sz - j / 2, i, i + len,
 362                        127, 0);
 363               do_test (&json_ctx, pg_sz - j / 2, pg_sz - j, i, i + len,
 364                        127, 0);
 365             }
 366
 367           if (i < 32)
 368             {
 369               ++i;
 370             }
 371           else if (i < 160)
 372             {
 373               i += 8;
 374             }
 375           else if (i < 256)
 376             {
 377               i += 32;
 378             }
 379           else
 380             {
 381               i *= 2;
 382             }
 383         }
 384     }
 385
 386   for (i = 1; i < 8; ++i)
 387     {
 388       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 127, 0);
 389       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 127, 1);
 390       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 127, -1);
 391       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 255, 0);
 392       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 255, 1);
 393       do_test (&json_ctx, 0, 0, 8 << i, 16 << i, 255, -1);
 394       do_test (&json_ctx, 8 - i, 2 * i, 8 << i, 16 << i, 127, 0);
 395       do_test (&json_ctx, 8 - i, 2 * i, 8 << i, 16 << i, 127, 1);
 396       do_test (&json_ctx, 2 * i, i, 8 << i, 16 << i, 255, 0);
 397       do_test (&json_ctx, 2 * i, i, 8 << i, 16 << i, 255, 1);
 398     }
 399
 400   do_test_limit (&json_ctx, 4, 0, 21, 20, 127, 0);
 401   do_test_limit (&json_ctx, 0, 4, 21, 20, 127, 0);
 402   do_test_limit (&json_ctx, 8, 0, 25, 24, 127, 0);
 403   do_test_limit (&json_ctx, 0, 8, 25, 24, 127, 0);
 404
 405   for (i = 0; i < 8; ++i)
 406     {
 407       do_test_limit (&json_ctx, 0, 0, 17 - i, 16 - i, 127, 0);
 408       do_test_limit (&json_ctx, 0, 0, 17 - i, 16 - i, 255, 0);
 409       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 127, 0);
 410       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 127, 1);
 411       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 127, -1);
 412       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 255, 0);
 413       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 255, 1);
 414       do_test_limit (&json_ctx, 0, 0, 15 - i, 16 - i, 255, -1);
 415     }
 416
 417   do_test_page_boundary (&json_ctx);
 418   do_test_page (&json_ctx);
 419
 420   json_array_end (&json_ctx);
 421   json_attr_object_end (&json_ctx);
 422   json_attr_object_end (&json_ctx);
 423   json_document_end (&json_ctx);
 424
 425   return ret;
 426 }
 427
 428 #include <support/test-driver.c>
 429
 430 #ifndef WIDE
 431 # undef STRNCMP
 432 # define STRNCMP generic_strncmp
 433 # define libc_hidden_builtin_def(X)
 434 # include <string/strncmp.c>
 435 #endif