[src/trunk]: src/usr.bin/make usr.bin/make: make Str_Match faster for repeate...

[rillig <rillig%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/331ac6b9e8ae
branches:  trunk
changeset: 972927:331ac6b9e8ae
user:      rillig <rillig%NetBSD.org@localhost>
date:      Sat Jun 13 21:16:27 2020 +0000

description:
usr.bin/make: make Str_Match faster for repeated asterisks

Conceptually related to https://en.wikipedia.org/wiki/ReDoS.

diffstat:

 usr.bin/make/str.c                  |  8 +++++---
 usr.bin/make/unit-tests/modmatch.mk |  7 ++++++-
 2 files changed, 11 insertions(+), 4 deletions(-)

diffs (56 lines):

diff -r 77d5885552ab -r 331ac6b9e8ae usr.bin/make/str.c
--- a/usr.bin/make/str.c        Sat Jun 13 20:18:00 2020 +0000
+++ b/usr.bin/make/str.c        Sat Jun 13 21:16:27 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: str.c,v 1.45 2020/06/13 07:48:59 rillig Exp $  */
+/*     $NetBSD: str.c,v 1.46 2020/06/13 21:16:27 rillig Exp $  */
 
 /*-
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -69,14 +69,14 @@
  */
 
 #ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: str.c,v 1.45 2020/06/13 07:48:59 rillig Exp $";
+static char rcsid[] = "$NetBSD: str.c,v 1.46 2020/06/13 21:16:27 rillig Exp $";
 #else
 #include <sys/cdefs.h>
 #ifndef lint
 #if 0
 static char     sccsid[] = "@(#)str.c  5.8 (Berkeley) 6/1/90";
 #else
-__RCSID("$NetBSD: str.c,v 1.45 2020/06/13 07:48:59 rillig Exp $");
+__RCSID("$NetBSD: str.c,v 1.46 2020/06/13 21:16:27 rillig Exp $");
 #endif
 #endif                         /* not lint */
 #endif
@@ -355,6 +355,8 @@
                 */
                if (*pattern == '*') {
                        pattern++;
+                       while (*pattern == '*')
+                               pattern++;
                        if (*pattern == 0)
                                return 1;
                        while (*string != 0) {
diff -r 77d5885552ab -r 331ac6b9e8ae usr.bin/make/unit-tests/modmatch.mk
--- a/usr.bin/make/unit-tests/modmatch.mk       Sat Jun 13 20:18:00 2020 +0000
+++ b/usr.bin/make/unit-tests/modmatch.mk       Sat Jun 13 21:16:27 2020 +0000
@@ -15,7 +15,7 @@
 res = OK
 .endif
 
-all:   show-libs check-cclass
+all:   show-libs check-cclass slow
 
 show-libs:
        @for x in $X; do ${.MAKE} -f ${MAKEFILE} show LIB=$$x; done
@@ -32,3 +32,8 @@
        @echo Upper=${LIST:M[A-Z]*}
        @echo Lower=${LIST:M[^A-Z]*}
        @echo nose=${LIST:M[^s]*[ex]}
+
+# Before 2020-06-13, this expression took quite a long time in Str_Match,
+# calling itself 601080390 times for 16 asterisks.
+slow: .PHONY
+       @:;: ${:U****************:M****************b:Q}