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