4 ms·

OP, what version(s) of the BSD libc did you test? What OS, which version of the OS. macOS only? NetBSD? FreeBSD? OpenBSD? If you tested on FreeBSD, please fil

OP, what version(s) of the BSD libc did you test? What OS, which version of the OS. macOS only? NetBSD? FreeBSD? OpenBSD? If you tested on FreeBSD, please file a bug at https://bugs.freebsd.org/bugzilla/enter_bug.cgi?product=Base%20System https://bugs.freebsd.org/bugzilla/enter_bug.cgi?product=Base... I'm not a project member but I'm a user of the system so it's in my interest that issues like this are resolved. Please let me know whether or not you file a bug so that if you do I don't duplicate bug reports and if you don't I can do some benchmarking myself.

rsc 9y ago
I copied the glob implementation from one of the BSDs - I believe FreeBSD - into a standalone C program and ran that program on the same Linux system as the rest of the tests. Here's the version that tests the system glob. If you run it on your FooBSD systems you can see whether it runs quickly or not. The program assumes that you've already done: rm -rf /tmp/glob mkdir /tmp/glob cd /tmp/glob touch $(perl -e 'print "a"x100') And here's the program: #include <stdio.h> #include <glob.h> #include <unistd.h> #include <string.h> #include <stdlib.h> #include <dirent.h> #include <time.h> int main(void) { glob_t g; char pattern[1000], *p; struct timespec t, t2; double dt; int i, j, k; chdir("/tmp/glob"); setlinebuf(stdout); int mul = 1000; for(i = 0; i < 100; i++) { p = pattern; for (k = 0; k < i; k++) { *p++ = 'a'; *p++ = '*'; } *p++ = 'b'; *p = '\0'; printf("# %d %s\n", i, pattern); clock_gettime(CLOCK_REALTIME, &t); for (j = 0; j < mul; j++) { memset(&g, 0, sizeof g); if(glob(pattern, 0, 0, &g) != GLOB_NOMATCH) { fprintf(stderr, "error: found matches\n"); exit(2); } globfree(&g); } clock_gettime(CLOCK_REALTIME, &t2); t2.tv_sec -= t.tv_sec; t2.tv_nsec -= t.tv_nsec; dt = t2.tv_sec + (double)t2.tv_nsec/1e9; printf("%d %.9f\n", i, dt/mul); fflush(stdout); if(dt/mul >= 0.0001) mul = 1; if(i >= 8 && dt/mul >= 10) break; } } I won't be filing any specific bugs myself. I mailed oss-security@ this morning, which should reach relevant BSD maintainers, but more bug filing can't hurt.
loeg 9y ago
It's still exponential on FreeBSD CURRENT (per rsc's test program in the sibling thread): # 0 b 0 0.000000661 # 1 a*b 1 0.000005204 # 2 a*a*b 2 0.000036157 # 3 a*a*a*b 3 0.001124974 # 4 a*a*a*a*b 4 0.046123932 # 5 a*a*a*a*a*b 5 0.577535034 # 6 a*a*a*a*a*a*b 6 8.666314375 # 7 a*a*a*a*a*a*a*b 7 119.796626615 (I didn't wait for 8.) Please file a bug.

rsc 9y ago

I copied the glob implementation from one of the BSDs - I believe FreeBSD - into a standalone C program and ran that program on the same Linux system as the rest of the tests. Here's the version that tests the system glob. If you run it on your FooBSD systems you can see whether it runs quickly or not. The program assumes that you've already done: rm -rf /tmp/glob mkdir /tmp/glob cd /tmp/glob touch $(perl -e 'print "a"x100') And here's the program: #include <stdio.h> #include <glob.h> #include <unistd.h> #include <string.h> #include <stdlib.h> #include <dirent.h> #include <time.h> int main(void) { glob_t g; char pattern[1000], *p; struct timespec t, t2; double dt; int i, j, k; chdir("/tmp/glob"); setlinebuf(stdout); int mul = 1000; for(i = 0; i < 100; i++) { p = pattern; for (k = 0; k < i; k++) { *p++ = 'a'; *p++ = '*'; } *p++ = 'b'; *p = '\0'; printf("# %d %s\n", i, pattern); clock_gettime(CLOCK_REALTIME, &t); for (j = 0; j < mul; j++) { memset(&g, 0, sizeof g); if(glob(pattern, 0, 0, &g) != GLOB_NOMATCH) { fprintf(stderr, "error: found matches\n"); exit(2); } globfree(&g); } clock_gettime(CLOCK_REALTIME, &t2); t2.tv_sec -= t.tv_sec; t2.tv_nsec -= t.tv_nsec; dt = t2.tv_sec + (double)t2.tv_nsec/1e9; printf("%d %.9f\n", i, dt/mul); fflush(stdout); if(dt/mul >= 0.0001) mul = 1; if(i >= 8 && dt/mul >= 10) break; } } I won't be filing any specific bugs myself. I mailed oss-security@ this morning, which should reach relevant BSD maintainers, but more bug filing can't hurt.

loeg 9y ago

It's still exponential on FreeBSD CURRENT (per rsc's test program in the sibling thread): # 0 b 0 0.000000661 # 1 a*b 1 0.000005204 # 2 a*a*b 2 0.000036157 # 3 a*a*a*b 3 0.001124974 # 4 a*a*a*a*b 4 0.046123932 # 5 a*a*a*a*a*b 5 0.577535034 # 6 a*a*a*a*a*a*b 6 8.666314375 # 7 a*a*a*a*a*a*a*b 7 119.796626615 (I didn't wait for 8.) Please file a bug.