1 /* ztest.c -- Test for libbacktrace inflate code.
2    Copyright (C) 2017-2020 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 ATTRIBUTE_UNUSED,const char * msg,int errnum)92 error_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 
102 static 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 
189 static void
test_samples(struct backtrace_state * state)190 test_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 
255 static size_t
average_time(const size_t * times,size_t trials)256 average_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 
296 static void
test_large(struct backtrace_state * state)297 test_large (struct backtrace_state *state)
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 
529 int
main(int argc ATTRIBUTE_UNUSED,char ** argv)530 main (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