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 (ctx: json_ctx, d: (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 (ctx: json_ctx); |
75 | json_attr_uint (ctx: json_ctx, name: "strlen" , d: (double) len); |
76 | json_attr_uint (ctx: json_ctx, name: "len" , d: (double) n); |
77 | json_attr_uint (ctx: json_ctx, name: "align1" , d: (double) align1); |
78 | json_attr_uint (ctx: json_ctx, name: "align2" , d: (double) align2); |
79 | json_array_begin (ctx: json_ctx, name: "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 (ctx: json_ctx); |
110 | json_element_object_end (ctx: 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 (ctx: json_ctx); |
132 | json_attr_uint (ctx: json_ctx, name: "strlen" , d: (double)len); |
133 | json_attr_uint (ctx: json_ctx, name: "len" , d: (double)n); |
134 | json_attr_uint (ctx: json_ctx, name: "align1" , d: (double)align1); |
135 | json_attr_uint (ctx: json_ctx, name: "align2" , d: (double)align2); |
136 | json_array_begin (ctx: json_ctx, name: "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 (ctx: json_ctx); |
162 | json_element_object_end (ctx: 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 (ctx: json_ctx); |
171 | json_attr_uint (ctx: json_ctx, name: "strlen" , d: (double) len); |
172 | json_attr_uint (ctx: json_ctx, name: "len" , d: (double) n); |
173 | json_attr_uint (ctx: json_ctx, name: "align1" , d: (double) align1); |
174 | json_attr_uint (ctx: json_ctx, name: "align2" , d: (double) align2); |
175 | json_array_begin (ctx: json_ctx, name: "timings" ); |
176 | FOR_EACH_IMPL (impl, 0) |
177 | do_one_test (json_ctx, impl, s1, s2, n, exp_result); |
178 | json_array_end (ctx: json_ctx); |
179 | json_element_object_end (ctx: 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, s1: s1p, s2: s2p, align1, align2, |
215 | len, n: 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 (ctx: json_ctx); |
239 | json_attr_uint (ctx: json_ctx, name: "strlen" , d: (double) len); |
240 | json_attr_uint (ctx: json_ctx, name: "len" , d: (double) page_size); |
241 | json_attr_uint (ctx: json_ctx, name: "align1" , d: (double) offset1); |
242 | json_attr_uint (ctx: json_ctx, name: "align2" , d: (double) offset2); |
243 | json_array_begin (ctx: json_ctx, name: "timings" ); |
244 | { |
245 | FOR_EACH_IMPL (impl, 0) |
246 | do_one_test (json_ctx, impl, s1, s2, n: page_size, exp_result: -exp_result); |
247 | } |
248 | json_array_end (ctx: json_ctx); |
249 | json_element_object_end (ctx: json_ctx); |
250 | |
251 | json_element_object_begin (ctx: json_ctx); |
252 | json_attr_uint (ctx: json_ctx, name: "strlen" , d: (double) len); |
253 | json_attr_uint (ctx: json_ctx, name: "len" , d: (double) page_size); |
254 | json_attr_uint (ctx: json_ctx, name: "align1" , d: (double) offset1); |
255 | json_attr_uint (ctx: json_ctx, name: "align2" , d: (double) offset2); |
256 | json_array_begin (ctx: json_ctx, name: "timings" ); |
257 | { |
258 | FOR_EACH_IMPL (impl, 0) |
259 | do_one_test (json_ctx, impl, s1, s2, n: page_size, exp_result); |
260 | } |
261 | json_array_end (ctx: json_ctx); |
262 | json_element_object_end (ctx: 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 (s: 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, offset1: ((page_size - 108) / CHARBYTES) + i, |
283 | offset2: ((page_size - 1460) / CHARBYTES), s2); |
284 | |
285 | free (ptr: 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 (ctx: &json_ctx, indent_level: 0, stdout); |
298 | |
299 | json_document_begin (ctx: &json_ctx); |
300 | json_attr_string (ctx: &json_ctx, name: "timing_type" , TIMING_TYPE); |
301 | |
302 | json_attr_object_begin (ctx: &json_ctx, name: "functions" ); |
303 | json_attr_object_begin (ctx: &json_ctx, TEST_NAME); |
304 | json_attr_string (ctx: &json_ctx, name: "bench-variant" , s: "default" ); |
305 | |
306 | json_array_begin (ctx: &json_ctx, name: "ifuncs" ); |
307 | FOR_EACH_IMPL (impl, 0) |
308 | json_element_string (ctx: &json_ctx, s: impl->name); |
309 | json_array_end (ctx: &json_ctx); |
310 | |
311 | json_array_begin (ctx: &json_ctx, name: "results" ); |
312 | |
313 | for (i = 0; i < 16; ++i) |
314 | { |
315 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 127, exp_result: 0); |
316 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 127, exp_result: -1); |
317 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 127, exp_result: 1); |
318 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 127, exp_result: 0); |
319 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 127, exp_result: 1); |
320 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 127, exp_result: -1); |
321 | do_test (json_ctx: &json_ctx, align1: i, align2: 2 * i, len: 8, n: i, max_char: 127, exp_result: 0); |
322 | do_test (json_ctx: &json_ctx, align1: 2 * i, align2: i, len: 8, n: i, max_char: 127, exp_result: 1); |
323 | do_test (json_ctx: &json_ctx, align1: i, align2: 3 * i, len: 8, n: i, max_char: 127, exp_result: -1); |
324 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 255, exp_result: 0); |
325 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 255, exp_result: -1); |
326 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8, n: i, max_char: 255, exp_result: 1); |
327 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 255, exp_result: 0); |
328 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 255, exp_result: 1); |
329 | do_test (json_ctx: &json_ctx, align1: i, align2: i, len: 8, n: i, max_char: 255, exp_result: -1); |
330 | do_test (json_ctx: &json_ctx, align1: i, align2: 2 * i, len: 8, n: i, max_char: 255, exp_result: 0); |
331 | do_test (json_ctx: &json_ctx, align1: 2 * i, align2: i, len: 8, n: i, max_char: 255, exp_result: 1); |
332 | do_test (json_ctx: &json_ctx, align1: i, align2: 3 * i, len: 8, n: i, max_char: 255, exp_result: -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: &json_ctx, align1: 0, align2: 0, len: i, n: i + len, max_char: 127, exp_result: 0); |
341 | do_test (json_ctx: &json_ctx, align1: i * CHARBYTES, align2: 0, len: i, n: i + len, max_char: 127, exp_result: 0); |
342 | do_test (json_ctx: &json_ctx, align1: 0, align2: i * CHARBYTES, len: i, n: i + len, max_char: 127, exp_result: 0); |
343 | |
344 | /* False page crosses. */ |
345 | do_test (json_ctx: &json_ctx, align1: pg_sz / 2, align2: pg_sz / 2 - CHARBYTES, len: i, n: i + len, |
346 | max_char: 127, exp_result: 0); |
347 | do_test (json_ctx: &json_ctx, align1: pg_sz / 2 - CHARBYTES, align2: pg_sz / 2, len: i, n: i + len, |
348 | max_char: 127, exp_result: 0); |
349 | |
350 | do_test (json_ctx: &json_ctx, align1: pg_sz - (i * CHARBYTES), align2: 0, len: i, n: i + len, max_char: 127, |
351 | exp_result: 0); |
352 | do_test (json_ctx: &json_ctx, align1: 0, align2: pg_sz - (i * CHARBYTES), len: i, n: i + len, max_char: 127, |
353 | exp_result: 0); |
354 | |
355 | /* Real page cross. */ |
356 | for (j = 16; j < 128; j += 16) |
357 | { |
358 | do_test (json_ctx: &json_ctx, align1: pg_sz - j, align2: 0, len: i, n: i + len, max_char: 127, exp_result: 0); |
359 | do_test (json_ctx: &json_ctx, align1: 0, align2: pg_sz - j, len: i, n: i + len, max_char: 127, exp_result: 0); |
360 | |
361 | do_test (json_ctx: &json_ctx, align1: pg_sz - j, align2: pg_sz - j / 2, len: i, n: i + len, |
362 | max_char: 127, exp_result: 0); |
363 | do_test (json_ctx: &json_ctx, align1: pg_sz - j / 2, align2: pg_sz - j, len: i, n: i + len, |
364 | max_char: 127, exp_result: 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: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 127, exp_result: 0); |
389 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 127, exp_result: 1); |
390 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 127, exp_result: -1); |
391 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 255, exp_result: 0); |
392 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 255, exp_result: 1); |
393 | do_test (json_ctx: &json_ctx, align1: 0, align2: 0, len: 8 << i, n: 16 << i, max_char: 255, exp_result: -1); |
394 | do_test (json_ctx: &json_ctx, align1: 8 - i, align2: 2 * i, len: 8 << i, n: 16 << i, max_char: 127, exp_result: 0); |
395 | do_test (json_ctx: &json_ctx, align1: 8 - i, align2: 2 * i, len: 8 << i, n: 16 << i, max_char: 127, exp_result: 1); |
396 | do_test (json_ctx: &json_ctx, align1: 2 * i, align2: i, len: 8 << i, n: 16 << i, max_char: 255, exp_result: 0); |
397 | do_test (json_ctx: &json_ctx, align1: 2 * i, align2: i, len: 8 << i, n: 16 << i, max_char: 255, exp_result: 1); |
398 | } |
399 | |
400 | do_test_limit (json_ctx: &json_ctx, align1: 4, align2: 0, len: 21, n: 20, max_char: 127, exp_result: 0); |
401 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 4, len: 21, n: 20, max_char: 127, exp_result: 0); |
402 | do_test_limit (json_ctx: &json_ctx, align1: 8, align2: 0, len: 25, n: 24, max_char: 127, exp_result: 0); |
403 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 8, len: 25, n: 24, max_char: 127, exp_result: 0); |
404 | |
405 | for (i = 0; i < 8; ++i) |
406 | { |
407 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 17 - i, n: 16 - i, max_char: 127, exp_result: 0); |
408 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 17 - i, n: 16 - i, max_char: 255, exp_result: 0); |
409 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 127, exp_result: 0); |
410 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 127, exp_result: 1); |
411 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 127, exp_result: -1); |
412 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 255, exp_result: 0); |
413 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 255, exp_result: 1); |
414 | do_test_limit (json_ctx: &json_ctx, align1: 0, align2: 0, len: 15 - i, n: 16 - i, max_char: 255, exp_result: -1); |
415 | } |
416 | |
417 | do_test_page_boundary (json_ctx: &json_ctx); |
418 | do_test_page (json_ctx: &json_ctx); |
419 | |
420 | json_array_end (ctx: &json_ctx); |
421 | json_attr_object_end (ctx: &json_ctx); |
422 | json_attr_object_end (ctx: &json_ctx); |
423 | json_document_end (ctx: &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 |
436 | |