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