1  /*
  2   * Copyright (c) 2017 Dell EMC Isilon
  3   * All rights reserved.
  4   *
  5   * Redistribution and use in source and binary forms, with or without
  6   * modification, are permitted provided that the following conditions
  7   * are met:
  8   * 1. Redistributions of source code must retain the above copyright
  9   *    notice, this list of conditions and the following disclaimer.
 10   * 2. Redistributions in binary form must reproduce the above copyright
 11   *    notice, this list of conditions and the following disclaimer in the
 12   *    documentation and/or other materials provided with the distribution.
 13   *
 14   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 15   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 16   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 17   * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 18   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 19   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 20   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 21   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 22   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 23   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 24   * SUCH DAMAGE.
 25   */
 26  
 27  #include <sys/cdefs.h>
 28  
 29  #include <sys/param.h>
 30  #include <errno.h>
 31  #include <fcntl.h>
 32  #include <glob.h>
 33  #include <stdio.h>
 34  #include <stdlib.h>
 35  #include <string.h>
 36  #include <time.h>
 37  #include <unistd.h>
 38  
 39  #include <darwintest.h>
 40  #include <darwintest_utils.h>
 41  
 42  /*
 43   * Derived from Russ Cox' pathological case test program used for the
 44   * https://research.swtch.com/glob article.
 45   */
 46  T_DECL(glob_pathological_test, "Russ Cox's pathological test program")
 47  {
 48  	struct timespec t, t2;
 49  	glob_t g;
 50  	const char *longname = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
 51  	    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
 52  	char pattern[1000], *p;
 53  	double dt;
 54  	unsigned i, j, k, mul = 10;
 55  	int fd, rc;
 56  
 57  	T_SETUPBEGIN;
 58  	rc = chdir(dt_tmpdir());
 59  	T_ASSERT_POSIX_ZERO(rc, NULL);
 60  	fd = open(longname, O_CREAT | O_RDWR, 0666);
 61  	T_ASSERT_POSIX_SUCCESS(fd, NULL);
 62  	T_SETUPEND;
 63  
 64  	/*
 65  	 * Test up to 100 a* groups.  Exponential implementations typically go
 66  	 * bang at i=7 or 8.
 67  	 */
 68  	for (i = 0; i < 100; i++) {
 69  		/*
 70  		 * Create a*...b pattern with i 'a*' groups.
 71  		 */
 72  		p = pattern;
 73  		for (k = 0; k < i; k++) {
 74  			*p++ = 'a';
 75  			*p++ = '*';
 76  		}
 77  		*p++ = 'b';
 78  		*p = '\0';
 79  
 80  		clock_gettime(CLOCK_MONOTONIC_RAW, &t);
 81  		for (j = 0; j < mul; j++) {
 82  			memset(&g, 0, sizeof g);
 83  			rc = glob(pattern, 0, 0, &g);
 84  			if (rc == GLOB_NOSPACE || rc == GLOB_ABORTED) {
 85  				T_ASSERT_EQ(rc, GLOB_NOMATCH,
 86  				    "an unexpected error occurred: "
 87  				    "rc=%d errno=%d", rc, errno);
 88  				/* NORETURN */
 89  			}
 90  
 91  			if (rc != GLOB_NOMATCH) {
 92  			    T_FAIL("A bogus match occurred: '%s' ~ '%s'", pattern, g.gl_pathv ? g.gl_pathv[0] : "(NULL)");
 93  			}
 94  			globfree(&g);
 95  		}
 96  		clock_gettime(CLOCK_MONOTONIC_RAW, &t2);
 97  
 98  		t2.tv_sec -= t.tv_sec;
 99  		t2.tv_nsec -= t.tv_nsec;
100  		dt = t2.tv_sec + (double)t2.tv_nsec/1e9;
101  		dt /= mul;
102  
103  		T_ASSERT_LE(dt, 1.0, "glob(3) completes in reasonable time (%d): %.9f sec/match", i,
104  		    dt);
105  
106  		if (dt >= 0.0001)
107  			mul = 1;
108  	}
109  }