libc glob: Avoid pathological exponential behavior

[cem]

Summary

Adapt glob's match() routine to use a greedy algorithm that avoids
exponential runtime in byzantine inputs.

While here, add a testcase for the byzantine input.

Prompted by: https://research.swtch.com/glob
Authored by: Yves Orton <demerphq at gmail.com>
Obtained from: Perl (33252c318625f3c6c89b816ee88481940e3e6f95)

Test Plan

Tests included. They pass with the changed match() routine.

[cem]

Note: Most of diff to match() is additional indentation from the added while loop. It's probably most useful to look at a diff which ignores whitespace changes.

Also note that NetBSD made a similar change for the same reasons. The NetBSD version is oddly very divergent from style(9). Perl's looked cleaner, so this change is derived from that instead.

[cem]

I plan to commit this in a couple days, if I don't hear anything.

[ache]

I prefer to copy NetBSD implementing the same thing, it appears they have additional safeguard against "name" goes too far:
http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/gen/glob.c.diff?r1=1.36&r2=1.37&f=h&f=u

[cem]

In D10551#218887, @ache wrote:

I prefer to copy NetBSD implementing the same thing, it appears they have additional safeguard against "name" goes too far:
http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/gen/glob.c.diff?r1=1.36&r2=1.37&f=h&f=u

What safeguard are you referring to?

Note that name cannot iterate off the valid portion of the string; every step that increments name checks for EOS, as does the end of the outer loop.

[ache]

+		if (nameNext != nameStart
+		    && (nameEnd == NULL || nameNext <= nameEnd)) {
+			pat = patNext;
+			name = nameNext;
+			continue;
+		}

[cem]

In D10551#218889, @ache wrote:

+		if (nameNext != nameStart
+		    && (nameEnd == NULL || nameNext <= nameEnd)) {
+			pat = patNext;
+			name = nameNext;
+			continue;
+		}

nameEnd == NULL || nameNext <= nameEnd check is redundant. nameNext (or nextn) can be set to name + 1 IIF *name != EOS.

nameNext != nameStart check does not apply to our implementation, because nextn is never initialized to the beginning of name and can only be set to name + 1.

So these checks are useless for us.

[cem]

r317749