Module Name: src
Committed By: rillig
Date: Sat Jun 13 21:16:27 UTC 2020
Modified Files:
src/usr.bin/make: str.c
src/usr.bin/make/unit-tests: modmatch.mk
Log Message:
usr.bin/make: make Str_Match faster for repeated asterisks
Conceptually related to https://en.wikipedia.org/wiki/ReDoS.
To generate a diff of this commit:
cvs rdiff -u -r1.45 -r1.46 src/usr.bin/make/str.c
cvs rdiff -u -r1.3 -r1.4 src/usr.bin/make/unit-tests/modmatch.mk
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/str.c
diff -u src/usr.bin/make/str.c:1.45 src/usr.bin/make/str.c:1.46
--- src/usr.bin/make/str.c:1.45 Sat Jun 13 07:48:59 2020
+++ src/usr.bin/make/str.c Sat Jun 13 21:16:27 2020
@@ -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 @@ Str_Match(const char *string, const char
*/
if (*pattern == '*') {
pattern++;
+ while (*pattern == '*')
+ pattern++;
if (*pattern == 0)
return 1;
while (*string != 0) {
Index: src/usr.bin/make/unit-tests/modmatch.mk
diff -u src/usr.bin/make/unit-tests/modmatch.mk:1.3 src/usr.bin/make/unit-tests/modmatch.mk:1.4
--- src/usr.bin/make/unit-tests/modmatch.mk:1.3 Fri Apr 21 22:15:44 2017
+++ src/usr.bin/make/unit-tests/modmatch.mk Sat Jun 13 21:16:27 2020
@@ -15,7 +15,7 @@ res = no
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 @@ check-cclass:
@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}
