Differential D10551
libc glob: Avoid pathological exponential behavior Authored by cem on Apr 30 2017, 7:20 PM. Tags None Referenced Files
Subscribers None
Details Adapt glob's match() routine to use a greedy algorithm that avoids While here, add a testcase for the byzantine input. Prompted by: https://research.swtch.com/glob Tests included. They pass with the changed match() routine.
Diff Detail
Event TimelineComment Actions 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. Comment Actions I prefer to copy NetBSD implementing the same thing, it appears they have additional safeguard against "name" goes too far: Comment Actions 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. Comment Actions + if (nameNext != nameStart
+ && (nameEnd == NULL || nameNext <= nameEnd)) {
+ pat = patNext;
+ name = nameNext;
+ continue;
+ }Comment Actions 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. |