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