/* * difftest.c -- differential harness: kernel fnmatch (sys/libkern/fnmatch.c, * compiled verbatim into this binary via fnmatch_k.c + shim.h) vs the host * libc fnmatch(3). * * build: cc -O2 -o difftest difftest.c fnmatch_k.c */ #include #include #include #include #include #include int _kfnmatch(const char *, const char *, int, int); static int kfn(const char *p, const char *s, int f) { return _kfnmatch(p, s, f, 0); } static long nfail = 0, ncase = 0; static long cls_backslash = 0, cls_other = 0; static void chk(const char *p, const char *s, int f, const char *tag) { int rk = kfn(p, s, f); int rl = fnmatch(p, s, f); ncase++; if ((rk == 0) != (rl == 0)) { nfail++; if (p[strlen(p) - 1] == '\\' && !(f & FNM_NOESCAPE)) cls_backslash++; else { cls_other++; if (cls_other <= 10) printf("DIVERGE-OTHER[%s] flags=%#x pattern=\"%s\" " "string=\"%s\": kernel=%d libc=%d\n", tag, f, p, s, rk, rl); } } } static double now_sec(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); return ts.tv_sec + ts.tv_nsec / 1e9; } static const char *alpha = "*?[]-\\!^ab/."; /* 12 symbols */ static const int flags_all[] = { 0, FNM_PATHNAME, FNM_PERIOD, FNM_PATHNAME | FNM_PERIOD, FNM_NOESCAPE, FNM_CASEFOLD, FNM_PATHNAME | FNM_PERIOD | FNM_NOESCAPE, FNM_LEADING_DIR, FNM_PATHNAME | FNM_LEADING_DIR | FNM_PERIOD }; #define NFLAGS 9 /* enumerate all strings over alpha[] of each length 1..maxlen into buf, calling cb for each; returns count */ static long enum_syms(int maxlen, void (*cb)(const char *, int)) { char buf[8]; long total = 0; int na = 12, len, i; long count, idx; for (len = 1; len <= maxlen; len++) { count = 1; for (i = 0; i < len; i++) count *= na; /* 12^len of this length */ for (idx = 0; idx < count; idx++) { long x = idx; for (i = len - 1; i >= 0; i--) { buf[i] = alpha[x % na]; x /= na; } buf[len] = 0; cb(buf, len); total++; } } return total; } static char cur_pat[8]; static void cb_str(const char *s, int len) { int f; for (f = 0; f < NFLAGS; f++) chk(cur_pat, s, flags_all[f], "corpus"); } static void cb_pat(const char *p, int len) { snprintf(cur_pat, sizeof(cur_pat), "%s", p); enum_syms(3, cb_str); } int main(void) { int i, j; char pat[128], str[128]; setlocale(LC_ALL, "C"); /* ---- 1. exhaustive small corpus: patterns len 1..3 x strings len 1..3 ---- */ { long total = enum_syms(3, cb_pat); /* 1884 patterns */ (void)total; /* random longer cases, mixed lengths up to 16 */ srand(12345); for (i = 0; i < 300000; i++) { int plen = 1 + rand() % 16; int slen = 1 + rand() % 16; for (j = 0; j < plen; j++) pat[j] = alpha[rand() % 12]; pat[plen] = 0; for (j = 0; j < slen; j++) str[j] = alpha[rand() % 12]; str[slen] = 0; chk(pat, str, flags_all[rand() % NFLAGS], "random"); } printf("[corpus] %ld cases, %ld divergences\n", ncase, nfail); } /* ---- 1b. dedicated bracket-expression sweep: "[" + 1..3 syms + "]" * (drives every pointer move in rangematch) ---- */ { char bp[8], bs[2]; const char *bal = "]-\\!^ab/.\x80\xff"; int nb = (int)strlen(bal); int cnt = 0; for (int a = 0; a < nb; a++) for (int b = 0; b < nb; b++) for (int c = 0; c < nb; c++) { snprintf(bp, sizeof(bp), "[%c%c%c]", bal[a], bal[b], bal[c]); for (int d = 0; d < nb; d++) { bs[0] = bal[d]; bs[1] = 0; chk(bp, bs, 0, "bracket"); chk(bp, bs, FNM_NOESCAPE, "bracket"); chk(bp, bs, FNM_PATHNAME, "bracket"); chk(bp, bs, FNM_CASEFOLD, "bracket"); cnt += 4; } } printf("[bracket] %d cases (running divergences: %ld)\n", cnt, nfail); } /* ---- 2. targeted: MAXNEST depth cap (string scaled to keep C(n,k) small) ---- */ { int diverge_at = -1; for (int nstars = 1; nstars <= 24; nstars++) { int o = 0; for (j = 0; j < nstars; j++) { pat[o++] = '*'; pat[o++] = 'a'; } pat[o] = 0; for (j = 0; j < nstars + 2; j++) str[j] = 'a'; str[nstars + 2] = 0; int rk = kfn(pat, str, 0); int rl = fnmatch(pat, str, 0); printf("[maxnest] stars=%2d kernel=%d libc=%d%s\n", nstars, rk, rl, ((rk == 0) != (rl == 0)) ? " <== DIVERGE" : ""); if (diverge_at < 0 && (rk == 0) != (rl == 0)) diverge_at = nstars; } printf("[maxnest] first divergence at %d stars\n", diverge_at); } /* ---- 3. targeted: signed-char bracket range endpoints ---- */ { struct { const char *p; const char *s; const char *why; } t[] = { { "[a-\xff]", "\x80", "0x80 within [0x61,0xff]" }, { "[a-\xff]", "\xfe", "0xfe within [0x61,0xff]" }, { "[\x80-\xff]", "\x90", "high-high range" }, { "[\x01-\x7f]", "\x80", "0x80 outside [1,0x7f]" }, }; for (i = 0; i < 4; i++) { int rk = kfn(t[i].p, t[i].s, 0); int rl = fnmatch(t[i].p, t[i].s, 0); printf("[signed] pattern-raw=\"%s\" string-raw=\"%s\" " "kernel=%d libc=%d (%s)\n", t[i].p, t[i].s, rk, rl, t[i].why); } } /* ---- 4. backtracking cost characterization (worst case = FAILING match) ---- * worst-case work for "*a"*k+"b" vs n a's ~ C(n,k) chains: * - in-kernel bound: if_xname <= 16 bytes => C(16,8)=12870 chains max * - long-string danger (no kernel consumer today): shown with n=20..28 */ { for (int nstars = 4; nstars <= 10; nstars += 2) { int o = 0; for (j = 0; j < nstars; j++) { pat[o++] = '*'; pat[o++] = 'a'; } pat[o++] = 'b'; /* never occurs: worst case */ pat[o] = 0; for (j = 0; j < 16; j++) str[j] = 'a'; str[16] = 0; double t0 = now_sec(); int r = kfn(pat, str, 0); double dt = now_sec() - t0; printf("[time-ifname-worst] stars=%2d n=16 kernel: %.6f s (ret %d)\n", nstars, dt, r); } for (int n = 20; n <= 28; n += 4) { int o = 0; for (j = 0; j < 10; j++) { pat[o++] = '*'; pat[o++] = 'a'; } pat[o++] = 'b'; pat[o] = 0; for (j = 0; j < n; j++) str[j] = 'a'; str[n] = 0; double t0 = now_sec(); int r = kfn(pat, str, 0); double dt = now_sec() - t0; t0 = now_sec(); int rl = fnmatch(pat, str, 0); double dtl = now_sec() - t0; printf("[time-long-worst] stars=10 n=%2d kernel: %.6f s (ret %d) " "libc: %.6f s (ret %d)\n", n, dt, r, dtl, rl); } } printf("TOTAL divergences: %ld / %ld cases " "(trailing-backslash class: %ld, other: %ld)\n", nfail, ncase, cls_backslash, cls_other); printf("TOTAL divergences: %ld / %ld cases\n", nfail, ncase); return 0; }