benchtests/bench-strcmp.c

   1 /* Measure strcmp and wcscmp functions.
   2    Copyright (C) 2013-2023 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 "wcscmp"
  22 #else
  23 # define TEST_NAME "strcmp"
  24 #endif
  25 #include "bench-string.h"
  26 #include "json-lib.h"
  27
  28 #ifdef WIDE
  29 # define CHARBYTESLOG 2
  30 # define MIDCHAR 0x7fffffff
  31 # define LARGECHAR 0xfffffffe
  32 #else
  33 # define CHARBYTESLOG 0
  34 # define MIDCHAR 0x7f
  35 # define LARGECHAR 0xfe
  36
  37 int
  38 generic_strcmp (const char *s1, const char *s2);
  39
  40 IMPL (generic_strcmp, 0)
  41
  42 #endif
  43
  44 typedef int (*proto_t) (const CHAR *, const CHAR *);
  45
  46 IMPL (STRCMP, 1)
  47
  48 static void
  49 do_one_test (json_ctx_t *json_ctx, impl_t *impl,
  50              const CHAR *s1, const CHAR *s2,
  51              int exp_result)
  52 {
  53   size_t i, iters = INNER_LOOP_ITERS8 / 2;
  54   timing_t start, stop, cur;
  55
  56   TIMING_NOW (start);
  57   for (i = 0; i < iters; ++i)
  58     {
  59       CALL (impl, s1, s2);
  60     }
  61   TIMING_NOW (stop);
  62
  63   TIMING_DIFF (cur, start, stop);
  64
  65   json_element_double (json_ctx, (double) cur / (double) iters);
  66 }
  67
  68 static void
  69 do_test (json_ctx_t *json_ctx, size_t align1, size_t align2, size_t len,
  70          int max_char, int exp_result, int at_end)
  71 {
  72   size_t i;
  73
  74   CHAR *s1, *s2;
  75
  76   if (len == 0)
  77     return;
  78
  79   align1 &= ~(CHARBYTES - 1);
  80   align2 &= ~(CHARBYTES - 1);
  81
  82   align1 &= (getpagesize () - 1);
  83   if (align1 + (len + 1) * CHARBYTES >= page_size)
  84     return;
  85
  86   align2 &= (getpagesize () - 1);
  87   if (align2 + (len + 1) * CHARBYTES >= page_size)
  88     return;
  89
  90   /* Put them close to the end of page.  */
  91   if (at_end)
  92     {
  93       i = align1 + CHARBYTES * (len + 2);
  94       align1 = ((page_size - i) / 16 * 16) + align1;
  95       i = align2 + CHARBYTES * (len + 2);
  96       align2 = ((page_size - i) / 16 * 16) + align2;
  97     }
  98
  99   s1 = (CHAR *)(buf1 + align1);
 100   s2 = (CHAR *)(buf2 + align2);
 101
 102   for (i = 0; i < len; i++)
 103     s1[i] = s2[i] = 1 + (23 << ((CHARBYTES - 1) * 8)) * i % max_char;
 104
 105   s1[len] = s2[len] = 0;
 106   s1[len + 1] = 23;
 107   s2[len + 1] = 24 + exp_result;
 108   s2[len - 1] -= exp_result;
 109
 110   json_element_object_begin (json_ctx);
 111   json_attr_uint (json_ctx, "length", (double)len);
 112   json_attr_uint (json_ctx, "align1", (double)align1);
 113   json_attr_uint (json_ctx, "align2", (double)align2);
 114   json_array_begin (json_ctx, "timings");
 115
 116   FOR_EACH_IMPL (impl, 0)
 117     do_one_test (json_ctx, impl, s1, s2, exp_result);
 118
 119   json_array_end (json_ctx);
 120   json_element_object_end (json_ctx);
 121 }
 122
 123 static void
 124 do_one_test_page_boundary (json_ctx_t *json_ctx, CHAR *s1, CHAR *s2,
 125                            size_t align1, size_t align2, size_t len,
 126                            int exp_result)
 127 {
 128   json_element_object_begin (json_ctx);
 129   json_attr_uint (json_ctx, "length", (double) len);
 130   json_attr_uint (json_ctx, "align1", (double) align1);
 131   json_attr_uint (json_ctx, "align2", (double) align2);
 132   json_array_begin (json_ctx, "timings");
 133   FOR_EACH_IMPL (impl, 0)
 134     do_one_test (json_ctx, impl, s1, s2, exp_result);
 135   json_array_end (json_ctx);
 136   json_element_object_end (json_ctx);
 137 }
 138
 139 static void
 140 do_test_page_boundary (json_ctx_t *json_ctx)
 141 {
 142   /* To trigger bug 25933, we need a size that is equal to the vector
 143      length times 4. In the case of AVX2 for Intel, we need 32 * 4.  We
 144      make this test generic and run it for all architectures as additional
 145      boundary testing for such related algorithms.  */
 146   size_t size = 32 * 4;
 147   size_t len;
 148   CHAR *s1 = (CHAR *) (buf1 + (BUF1PAGES - 1) * page_size);
 149   CHAR *s2 = (CHAR *) (buf2 + (BUF1PAGES - 1) * page_size);
 150   int exp_result;
 151
 152   memset (s1, 'a', page_size);
 153   memset (s2, 'a', page_size);
 154
 155   s1[(page_size / CHARBYTES) - 1] = (CHAR) 0;
 156   s2[(page_size / CHARBYTES) - 1] = (CHAR) 0;
 157
 158   /* Iterate over a size that is just below where we expect the bug to
 159      trigger up to the size we expect will trigger the bug e.g. [99-128].
 160      Likewise iterate the start of two strings between 30 and 31 bytes
 161      away from the boundary to simulate alignment changes.  */
 162   for (size_t s = 99; s <= size; s++)
 163     for (size_t s1a = 30; s1a < 32; s1a++)
 164       for (size_t s2a = 30; s2a < 32; s2a++)
 165         {
 166           size_t align1 = (page_size / CHARBYTES - s) - s1a;
 167           size_t align2 = (page_size / CHARBYTES - s) - s2a;
 168           CHAR *s1p = s1 + align1;
 169           CHAR *s2p = s2 + align2;
 170           len = (page_size / CHARBYTES) - 1 - align1;
 171           exp_result = STRCMP (s1p, s2p);
 172           do_one_test_page_boundary (json_ctx, s1p, s2p, align1, align2,
 173                                      len, exp_result);
 174         }
 175 }
 176
 177 int
 178 test_main (void)
 179 {
 180   json_ctx_t json_ctx;
 181   size_t i, j, k;
 182   size_t pg_sz = getpagesize ();
 183
 184   test_init ();
 185
 186   json_init (&json_ctx, 0, stdout);
 187
 188   json_document_begin (&json_ctx);
 189   json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
 190
 191   json_attr_object_begin (&json_ctx, "functions");
 192   json_attr_object_begin (&json_ctx, TEST_NAME);
 193   json_attr_string (&json_ctx, "bench-variant", "default");
 194
 195   json_array_begin (&json_ctx, "ifuncs");
 196   FOR_EACH_IMPL (impl, 0)
 197     json_element_string (&json_ctx, impl->name);
 198   json_array_end (&json_ctx);
 199
 200   json_array_begin (&json_ctx, "results");
 201   for (k = 0; k < 2; ++k)
 202     {
 203       for (i = 1; i < 32; ++i)
 204         {
 205           do_test (&json_ctx, CHARBYTES * i, CHARBYTES * i, i, MIDCHAR, 0, k);
 206           do_test (&json_ctx, CHARBYTES * i, CHARBYTES * i, i, MIDCHAR, 1, k);
 207           do_test (&json_ctx, CHARBYTES * i, CHARBYTES * i, i, MIDCHAR, -1, k);
 208         }
 209
 210       for (i = 1; i <= 8192;)
 211         {
 212           /* No page crosses.  */
 213           do_test (&json_ctx, 0, 0, i, MIDCHAR, 0, k);
 214           do_test (&json_ctx, i * CHARBYTES, 0, i, MIDCHAR, 0, k);
 215           do_test (&json_ctx, 0, i * CHARBYTES, i, MIDCHAR, 0, k);
 216
 217           /* False page crosses.  */
 218           do_test (&json_ctx, pg_sz / 2, pg_sz / 2 - CHARBYTES, i, MIDCHAR, 0,
 219                    k);
 220           do_test (&json_ctx, pg_sz / 2 - CHARBYTES, pg_sz / 2, i, MIDCHAR, 0,
 221                    k);
 222
 223           do_test (&json_ctx, pg_sz - (i * CHARBYTES), 0, i, MIDCHAR, 0, k);
 224           do_test (&json_ctx, 0, pg_sz - (i * CHARBYTES), i, MIDCHAR, 0, k);
 225
 226           /* Real page cross.  */
 227           for (j = 16; j < 128; j += 16)
 228             {
 229               do_test (&json_ctx, pg_sz - j, 0, i, MIDCHAR, 0, k);
 230               do_test (&json_ctx, 0, pg_sz - j, i, MIDCHAR, 0, k);
 231
 232               do_test (&json_ctx, pg_sz - j, pg_sz - j / 2, i, MIDCHAR, 0, k);
 233               do_test (&json_ctx, pg_sz - j / 2, pg_sz - j, i, MIDCHAR, 0, k);
 234             }
 235
 236           if (i < 32)
 237             {
 238               ++i;
 239             }
 240           else if (i < 160)
 241             {
 242               i += 8;
 243             }
 244           else if (i < 512)
 245             {
 246               i += 32;
 247             }
 248           else
 249             {
 250               i *= 2;
 251             }
 252         }
 253
 254       for (i = 1; i < 10 + CHARBYTESLOG; ++i)
 255         {
 256           do_test (&json_ctx, 0, 0, 2 << i, MIDCHAR, 0, k);
 257           do_test (&json_ctx, 0, 0, 2 << i, LARGECHAR, 0, k);
 258           do_test (&json_ctx, 0, 0, 2 << i, MIDCHAR, 1, k);
 259           do_test (&json_ctx, 0, 0, 2 << i, LARGECHAR, 1, k);
 260           do_test (&json_ctx, 0, 0, 2 << i, MIDCHAR, -1, k);
 261           do_test (&json_ctx, 0, 0, 2 << i, LARGECHAR, -1, k);
 262           do_test (&json_ctx, 0, CHARBYTES * i, 2 << i, MIDCHAR, 1, k);
 263           do_test (&json_ctx, CHARBYTES * i, CHARBYTES * (i + 1), 2 << i,
 264                    LARGECHAR, 1, k);
 265         }
 266
 267       for (i = 1; i < 8; ++i)
 268         {
 269           do_test (&json_ctx, CHARBYTES * i, 2 * CHARBYTES * i, 8 << i,
 270                    MIDCHAR, 0, k);
 271           do_test (&json_ctx, 2 * CHARBYTES * i, CHARBYTES * i, 8 << i,
 272                    LARGECHAR, 0, k);
 273           do_test (&json_ctx, CHARBYTES * i, 2 * CHARBYTES * i, 8 << i,
 274                    MIDCHAR, 1, k);
 275           do_test (&json_ctx, 2 * CHARBYTES * i, CHARBYTES * i, 8 << i,
 276                    LARGECHAR, 1, k);
 277           do_test (&json_ctx, CHARBYTES * i, 2 * CHARBYTES * i, 8 << i,
 278                    MIDCHAR, -1, k);
 279           do_test (&json_ctx, 2 * CHARBYTES * i, CHARBYTES * i, 8 << i,
 280                    LARGECHAR, -1, k);
 281         }
 282     }
 283   do_test_page_boundary (&json_ctx);
 284
 285   json_array_end (&json_ctx);
 286   json_attr_object_end (&json_ctx);
 287   json_attr_object_end (&json_ctx);
 288   json_document_end (&json_ctx);
 289
 290   return ret;
 291 }
 292
 293 #include <support/test-driver.c>
 294
 295 #ifndef WIDE
 296 # undef STRCMP
 297 # define STRCMP generic_strcmp
 298 # include <string/strcmp.c>
 299 #endif