1 /* ztest.c -- Test for libbacktrace inflate code.
2 Copyright (C) 2017-2018 Free Software Foundation, Inc.
3 Written by Ian Lance Taylor, Google.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
8
9 (1) Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 (2) Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in
14 the documentation and/or other materials provided with the
15 distribution.
16
17 (3) The name of the author may not be used to
18 endorse or promote products derived from this software without
19 specific prior written permission.
20
21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 POSSIBILITY OF SUCH DAMAGE. */
32
33 #include "config.h"
34
35 #include <errno.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <time.h>
40 #include <sys/types.h>
41 #include <sys/stat.h>
42
43 #ifdef HAVE_ZLIB
44 #include <zlib.h>
45 #endif
46
47 #include "backtrace.h"
48 #include "backtrace-supported.h"
49
50 #include "internal.h"
51 #include "testlib.h"
52
53 #ifndef HAVE_CLOCK_GETTIME
54
55 typedef int xclockid_t;
56
57 static int
xclock_gettime(xclockid_t id ATTRIBUTE_UNUSED,struct timespec * ts ATTRIBUTE_UNUSED)58 xclock_gettime (xclockid_t id ATTRIBUTE_UNUSED,
59 struct timespec *ts ATTRIBUTE_UNUSED)
60 {
61 errno = EINVAL;
62 return -1;
63 }
64
65 #define clockid_t xclockid_t
66 #define clock_gettime xclock_gettime
67 #undef CLOCK_REALTIME
68 #define CLOCK_REALTIME 0
69
70 #endif /* !defined(HAVE_CLOCK_GETTIME) */
71
72 #ifdef CLOCK_PROCESS_CPUTIME_ID
73 #define ZLIB_CLOCK_GETTIME_ARG CLOCK_PROCESS_CPUTIME_ID
74 #else
75 #define ZLIB_CLOCK_GETTIME_ARG CLOCK_REALTIME
76 #endif
77
78 /* Some tests for the local zlib inflation code. */
79
80 struct zlib_test
81 {
82 const char *name;
83 const char *uncompressed;
84 size_t uncompressed_len;
85 const char *compressed;
86 size_t compressed_len;
87 };
88
89 /* Error callback. */
90
91 static void
error_callback_compress(void * vdata,const char * msg,int errnum)92 error_callback_compress (void *vdata, const char *msg, int errnum)
93 {
94 fprintf (stderr, "%s", msg);
95 if (errnum > 0)
96 fprintf (stderr, ": %s", strerror (errnum));
97 fprintf (stderr, "\n");
98 exit (EXIT_FAILURE);
99 }
100
101 static const struct zlib_test tests[] =
102 {
103 {
104 "empty",
105 "",
106 0,
107 "\x78\x9c\x03\x00\x00\x00\x00\x01",
108 8,
109 },
110 {
111 "hello",
112 "hello, world\n",
113 0,
114 ("\x78\x9c\xca\x48\xcd\xc9\xc9\xd7\x51\x28\xcf"
115 "\x2f\xca\x49\xe1\x02\x04\x00\x00\xff\xff\x21\xe7\x04\x93"),
116 25,
117 },
118 {
119 "goodbye",
120 "goodbye, world",
121 0,
122 ("\x78\x9c\x4b\xcf\xcf\x4f\x49\xaa"
123 "\x4c\xd5\x51\x28\xcf\x2f\xca\x49"
124 "\x01\x00\x28\xa5\x05\x5e"),
125 22,
126 },
127 {
128 "ranges",
129 ("\xcc\x11\x00\x00\x00\x00\x00\x00\xd5\x13\x00\x00\x00\x00\x00\x00"
130 "\x1c\x14\x00\x00\x00\x00\x00\x00\x72\x14\x00\x00\x00\x00\x00\x00"
131 "\x9d\x14\x00\x00\x00\x00\x00\x00\xd5\x14\x00\x00\x00\x00\x00\x00"
132 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
133 "\xfb\x12\x00\x00\x00\x00\x00\x00\x09\x13\x00\x00\x00\x00\x00\x00"
134 "\x0c\x13\x00\x00\x00\x00\x00\x00\xcb\x13\x00\x00\x00\x00\x00\x00"
135 "\x29\x14\x00\x00\x00\x00\x00\x00\x4e\x14\x00\x00\x00\x00\x00\x00"
136 "\x9d\x14\x00\x00\x00\x00\x00\x00\xd5\x14\x00\x00\x00\x00\x00\x00"
137 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
138 "\xfb\x12\x00\x00\x00\x00\x00\x00\x09\x13\x00\x00\x00\x00\x00\x00"
139 "\x67\x13\x00\x00\x00\x00\x00\x00\xcb\x13\x00\x00\x00\x00\x00\x00"
140 "\x9d\x14\x00\x00\x00\x00\x00\x00\xd5\x14\x00\x00\x00\x00\x00\x00"
141 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
142 "\x5f\x0b\x00\x00\x00\x00\x00\x00\x6c\x0b\x00\x00\x00\x00\x00\x00"
143 "\x7d\x0b\x00\x00\x00\x00\x00\x00\x7e\x0c\x00\x00\x00\x00\x00\x00"
144 "\x38\x0f\x00\x00\x00\x00\x00\x00\x5c\x0f\x00\x00\x00\x00\x00\x00"
145 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
146 "\x83\x0c\x00\x00\x00\x00\x00\x00\xfa\x0c\x00\x00\x00\x00\x00\x00"
147 "\xfd\x0d\x00\x00\x00\x00\x00\x00\xef\x0e\x00\x00\x00\x00\x00\x00"
148 "\x14\x0f\x00\x00\x00\x00\x00\x00\x38\x0f\x00\x00\x00\x00\x00\x00"
149 "\x9f\x0f\x00\x00\x00\x00\x00\x00\xac\x0f\x00\x00\x00\x00\x00\x00"
150 "\xdb\x0f\x00\x00\x00\x00\x00\x00\xff\x0f\x00\x00\x00\x00\x00\x00"
151 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
152 "\xfd\x0d\x00\x00\x00\x00\x00\x00\xd8\x0e\x00\x00\x00\x00\x00\x00"
153 "\x9f\x0f\x00\x00\x00\x00\x00\x00\xac\x0f\x00\x00\x00\x00\x00\x00"
154 "\xdb\x0f\x00\x00\x00\x00\x00\x00\xff\x0f\x00\x00\x00\x00\x00\x00"
155 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
156 "\xfa\x0c\x00\x00\x00\x00\x00\x00\xea\x0d\x00\x00\x00\x00\x00\x00"
157 "\xef\x0e\x00\x00\x00\x00\x00\x00\x14\x0f\x00\x00\x00\x00\x00\x00"
158 "\x5c\x0f\x00\x00\x00\x00\x00\x00\x9f\x0f\x00\x00\x00\x00\x00\x00"
159 "\xac\x0f\x00\x00\x00\x00\x00\x00\xdb\x0f\x00\x00\x00\x00\x00\x00"
160 "\xff\x0f\x00\x00\x00\x00\x00\x00\x2c\x10\x00\x00\x00\x00\x00\x00"
161 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
162 "\x60\x11\x00\x00\x00\x00\x00\x00\xd1\x16\x00\x00\x00\x00\x00\x00"
163 "\x40\x0b\x00\x00\x00\x00\x00\x00\x2c\x10\x00\x00\x00\x00\x00\x00"
164 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
165 "\x7a\x00\x00\x00\x00\x00\x00\x00\xb6\x00\x00\x00\x00\x00\x00\x00"
166 "\x9f\x01\x00\x00\x00\x00\x00\x00\xa7\x01\x00\x00\x00\x00\x00\x00"
167 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
168 "\x7a\x00\x00\x00\x00\x00\x00\x00\xa9\x00\x00\x00\x00\x00\x00\x00"
169 "\x9f\x01\x00\x00\x00\x00\x00\x00\xa7\x01\x00\x00\x00\x00\x00\x00"
170 "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"),
171 672,
172 ("\x78\x9c\x3b\x23\xc8\x00\x06\x57\x85\x21\xb4\x8c\x08\x84\x2e\x82"
173 "\xd2\x73\xa1\xf4\x55\x28\x8d\x0e\x7e\x0b\x41\x68\x4e\xa8\x7e\x1e"
174 "\x28\x7d\x1a\x4a\x6b\x42\xf5\xf9\x91\x69\x5e\x3a\x9a\x79\x84\xf4"
175 "\xc7\x73\x43\xe8\x1c\x28\x5d\x0b\xa5\xeb\x78\x20\xb4\x05\x3f\x84"
176 "\x8e\xe1\xc7\xae\xbf\x19\xaa\xee\x17\x94\xfe\xcb\x0b\xa1\xdf\xf3"
177 "\x41\x68\x11\x7e\x54\x73\xe6\x43\xe9\x35\x50\xfa\x36\x94\xfe\x8f"
178 "\xc3\x7c\x98\x79\x37\xf8\xc8\xd3\x0f\x73\xd7\x2b\x1c\xee\x8a\x21"
179 "\xd2\x5d\x3a\x02\xd8\xcd\x4f\x80\xa6\x87\x8b\x62\x10\xda\x81\x1b"
180 "\xbf\xfa\x2a\x28\xbd\x0d\x4a\xcf\x67\x84\xd0\xcb\x19\xf1\xab\x5f"
181 "\x49\xa4\x7a\x00\x48\x97\x29\xd4"),
182 152,
183 }
184 };
185
186 /* Test the hand coded samples. */
187
188 static void
test_samples(struct backtrace_state * state)189 test_samples (struct backtrace_state *state)
190 {
191 size_t i;
192
193 for (i = 0; i < sizeof tests / sizeof tests[0]; ++i)
194 {
195 char *p;
196 size_t v;
197 size_t j;
198 unsigned char *uncompressed;
199 size_t uncompressed_len;
200
201 p = malloc (12 + tests[i].compressed_len);
202 memcpy (p, "ZLIB", 4);
203 v = tests[i].uncompressed_len;
204 if (v == 0)
205 v = strlen (tests[i].uncompressed);
206 for (j = 0; j < 8; ++j)
207 p[j + 4] = (v >> ((7 - j) * 8)) & 0xff;
208 memcpy (p + 12, tests[i].compressed, tests[i].compressed_len);
209 uncompressed = NULL;
210 uncompressed_len = 0;
211 if (!backtrace_uncompress_zdebug (state, (unsigned char *) p,
212 tests[i].compressed_len + 12,
213 error_callback_compress, NULL,
214 &uncompressed, &uncompressed_len))
215 {
216 fprintf (stderr, "test %s: uncompress failed\n", tests[i].name);
217 ++failures;
218 }
219 else
220 {
221 if (uncompressed_len != v)
222 {
223 fprintf (stderr,
224 "test %s: got uncompressed length %zu, want %zu\n",
225 tests[i].name, uncompressed_len, v);
226 ++failures;
227 }
228 else if (memcmp (tests[i].uncompressed, uncompressed, v) != 0)
229 {
230 size_t j;
231
232 fprintf (stderr, "test %s: uncompressed data mismatch\n",
233 tests[i].name);
234 for (j = 0; j < v; ++j)
235 if (tests[i].uncompressed[j] != uncompressed[j])
236 fprintf (stderr, " %zu: got %#x want %#x\n", j,
237 uncompressed[j], tests[i].uncompressed[j]);
238 ++failures;
239 }
240 else
241 printf ("PASS: inflate %s\n", tests[i].name);
242
243 backtrace_free (state, uncompressed, uncompressed_len,
244 error_callback_compress, NULL);
245 }
246 }
247 }
248
249 #ifdef HAVE_ZLIB
250
251 /* Given a set of TRIALS timings, discard the lowest and highest
252 values and return the mean average of the rest. */
253
254 static size_t
average_time(const size_t * times,size_t trials)255 average_time (const size_t *times, size_t trials)
256 {
257 size_t imax;
258 size_t max;
259 size_t imin;
260 size_t min;
261 size_t i;
262 size_t sum;
263
264 imin = 0;
265 imax = 0;
266 min = times[0];
267 max = times[0];
268 for (i = 1; i < trials; ++i)
269 {
270 if (times[i] < min)
271 {
272 imin = i;
273 min = times[i];
274 }
275 if (times[i] > max)
276 {
277 imax = i;
278 max = times[i];
279 }
280 }
281
282 sum = 0;
283 for (i = 0; i < trials; ++i)
284 {
285 if (i != imax && i != imin)
286 sum += times[i];
287 }
288 return sum / (trials - 2);
289 }
290
291 #endif
292
293 /* Test a larger text, if available. */
294
295 static void
test_large(struct backtrace_state * state)296 test_large (struct backtrace_state *state)
297 {
298 #ifdef HAVE_ZLIB
299 unsigned char *orig_buf;
300 size_t orig_bufsize;
301 size_t i;
302 char *compressed_buf;
303 size_t compressed_bufsize;
304 unsigned long compress_sizearg;
305 unsigned char *uncompressed_buf;
306 size_t uncompressed_bufsize;
307 int r;
308 clockid_t cid;
309 struct timespec ts1;
310 struct timespec ts2;
311 size_t ctime;
312 size_t ztime;
313 const size_t trials = 16;
314 size_t ctimes[16];
315 size_t ztimes[16];
316 static const char * const names[] = {
317 "Mark.Twain-Tom.Sawyer.txt",
318 "../libgo/go/compress/testdata/Mark.Twain-Tom.Sawyer.txt"
319 };
320
321 orig_buf = NULL;
322 orig_bufsize = 0;
323 uncompressed_buf = NULL;
324 compressed_buf = NULL;
325
326 for (i = 0; i < sizeof names / sizeof names[0]; ++i)
327 {
328 size_t len;
329 char *namebuf;
330 FILE *e;
331 struct stat st;
332 char *rbuf;
333 size_t got;
334
335 len = strlen (SRCDIR) + strlen (names[i]) + 2;
336 namebuf = malloc (len);
337 if (namebuf == NULL)
338 {
339 perror ("malloc");
340 goto fail;
341 }
342 snprintf (namebuf, len, "%s/%s", SRCDIR, names[i]);
343 e = fopen (namebuf, "r");
344 free (namebuf);
345 if (e == NULL)
346 continue;
347 if (fstat (fileno (e), &st) < 0)
348 {
349 perror ("fstat");
350 fclose (e);
351 continue;
352 }
353 rbuf = malloc (st.st_size);
354 if (rbuf == NULL)
355 {
356 perror ("malloc");
357 goto fail;
358 }
359 got = fread (rbuf, 1, st.st_size, e);
360 fclose (e);
361 if (got > 0)
362 {
363 orig_buf = rbuf;
364 orig_bufsize = got;
365 break;
366 }
367 free (rbuf);
368 }
369
370 if (orig_buf == NULL)
371 {
372 /* We couldn't find an input file. */
373 printf ("UNSUPPORTED: inflate large\n");
374 return;
375 }
376
377 compressed_bufsize = compressBound (orig_bufsize) + 12;
378 compressed_buf = malloc (compressed_bufsize);
379 if (compressed_buf == NULL)
380 {
381 perror ("malloc");
382 goto fail;
383 }
384
385 compress_sizearg = compressed_bufsize - 12;
386 r = compress (compressed_buf + 12, &compress_sizearg,
387 orig_buf, orig_bufsize);
388 if (r != Z_OK)
389 {
390 fprintf (stderr, "zlib compress failed: %d\n", r);
391 goto fail;
392 }
393
394 compressed_bufsize = compress_sizearg + 12;
395
396 /* Prepare the header that our library expects. */
397 memcpy (compressed_buf, "ZLIB", 4);
398 for (i = 0; i < 8; ++i)
399 compressed_buf[i + 4] = (orig_bufsize >> ((7 - i) * 8)) & 0xff;
400
401 uncompressed_buf = malloc (orig_bufsize);
402 if (uncompressed_buf == NULL)
403 {
404 perror ("malloc");
405 goto fail;
406 }
407 uncompressed_bufsize = orig_bufsize;
408
409 if (!backtrace_uncompress_zdebug (state, compressed_buf, compressed_bufsize,
410 error_callback_compress, NULL,
411 &uncompressed_buf, &uncompressed_bufsize))
412 {
413 fprintf (stderr, "inflate large: backtrace_uncompress_zdebug failed\n");
414 goto fail;
415 }
416
417 if (uncompressed_bufsize != orig_bufsize)
418 {
419 fprintf (stderr,
420 "inflate large: got uncompressed length %zu, want %zu\n",
421 uncompressed_bufsize, orig_bufsize);
422 goto fail;
423 }
424
425 if (memcmp (uncompressed_buf, orig_buf, uncompressed_bufsize) != 0)
426 {
427 fprintf (stderr, "inflate large: uncompressed data mismatch\n");
428 goto fail;
429 }
430
431 printf ("PASS: inflate large\n");
432
433 for (i = 0; i < trials; ++i)
434 {
435 unsigned long uncompress_sizearg;
436
437 cid = ZLIB_CLOCK_GETTIME_ARG;
438 if (clock_gettime (cid, &ts1) < 0)
439 {
440 if (errno == EINVAL)
441 return;
442 perror ("clock_gettime");
443 return;
444 }
445
446 if (!backtrace_uncompress_zdebug (state, compressed_buf,
447 compressed_bufsize,
448 error_callback_compress, NULL,
449 &uncompressed_buf,
450 &uncompressed_bufsize))
451 {
452 fprintf (stderr,
453 ("inflate large: "
454 "benchmark backtrace_uncompress_zdebug failed\n"));
455 return;
456 }
457
458 if (clock_gettime (cid, &ts2) < 0)
459 {
460 perror ("clock_gettime");
461 return;
462 }
463
464 ctime = (ts2.tv_sec - ts1.tv_sec) * 1000000000;
465 ctime += ts2.tv_nsec - ts1.tv_nsec;
466 ctimes[i] = ctime;
467
468 if (clock_gettime (cid, &ts1) < 0)
469 {
470 perror("clock_gettime");
471 return;
472 }
473
474 uncompress_sizearg = uncompressed_bufsize;
475 r = uncompress (uncompressed_buf, &uncompress_sizearg,
476 compressed_buf + 12, compressed_bufsize - 12);
477
478 if (clock_gettime (cid, &ts2) < 0)
479 {
480 perror ("clock_gettime");
481 return;
482 }
483
484 if (r != Z_OK)
485 {
486 fprintf (stderr,
487 "inflate large: benchmark zlib uncompress failed: %d\n",
488 r);
489 return;
490 }
491
492 ztime = (ts2.tv_sec - ts1.tv_sec) * 1000000000;
493 ztime += ts2.tv_nsec - ts1.tv_nsec;
494 ztimes[i] = ztime;
495 }
496
497 /* Toss the highest and lowest times and average the rest. */
498 ctime = average_time (ctimes, trials);
499 ztime = average_time (ztimes, trials);
500
501 printf ("backtrace: %zu ns\n", ctime);
502 printf ("zlib : %zu ns\n", ztime);
503 printf ("ratio : %g\n", (double) ztime / (double) ctime);
504
505 return;
506
507 fail:
508 printf ("FAIL: inflate large\n");
509 ++failures;
510
511 if (orig_buf != NULL)
512 free (orig_buf);
513 if (compressed_buf != NULL)
514 free (compressed_buf);
515 if (uncompressed_buf != NULL)
516 free (uncompressed_buf);
517
518 #else /* !HAVE_ZLIB */
519
520 printf ("UNSUPPORTED: inflate large\n");
521
522 #endif /* !HAVE_ZLIB */
523 }
524
525 int
main(int argc ATTRIBUTE_UNUSED,char ** argv)526 main (int argc ATTRIBUTE_UNUSED, char **argv)
527 {
528 struct backtrace_state *state;
529
530 state = backtrace_create_state (argv[0], BACKTRACE_SUPPORTS_THREADS,
531 error_callback_create, NULL);
532
533 test_samples (state);
534 test_large (state);
535
536 exit (failures != 0 ? EXIT_FAILURE : EXIT_SUCCESS);
537 }
538