Subject: bug#61514: 30.0.50; sadistically long xml line hangs emacs

From: Gregory Heytings <[email-masked]>
Date: Mon, 20 Feb 2023 02:05:59 +0000

>> Lowering emacs_re_max_failures just makes the regexp engine fail 
>> earlier, because there is not enough room in the failure stack.  In a 
>> sense it is better to fail earlier, but to do that in all cases, we 
>> would have to lower emacs_re_max_failures say to 10000, which I guess 
>> wouldn't be good because the it would fail too much.
>
> BTW, this makes me wonder why emacs_re_max_failures is not accessible 
> from Elisp.  I think it would be very useful, if only for debugging 
> purposes. And perhaps let-binding it to a lower value around some 
> potentially (or actually) problematic regexps would be a good way to 
> prevent or fix bugs such as the current one.
>

Looking at the history of that variable, which is in fact a compile-time 
constant, I see that it was initially (May 1995) set to 200000.  A few 
months later (Nov 1995) it was set to 20000, and reduced again (apparently 
because of bug reports) to 8000 and to 4000 (both in Jun 1996).  Two 
months later it was again set to 20000 (Aug 1996), and a year later to 
40000 (Dec 1997).  It kept that value since then.  As these changes (and 
this bug report) demonstrate, it is not possible to give that variable a 
"one size fits all" value.

Here's a patch that makes it modifiable, and "fixes" (in the sense of 
failing with a "Stack overflow in regexp matcher" instead of inflooping) 
the current bug.

WDYT?
From 0a58969670637cb4f065ae619531f78a11ea9bdb Mon Sep 17 00:00:00 2001
From: Gregory Heytings <[email-masked]>
Date: Mon, 20 Feb 2023 01:47:28 +0000
Subject: [PATCH] Make the number of failure points in regexp searches
 modifiable

* src/search.c (syms_of_search) <regexp-max-failures>: New
variable, replacing the constant variable 'emacs_re_max_failures'.
Initialize it with the constant 'max_regexp_max_failure'.

* src/regex-emacs.h: Replace the external definition of
'emacs_re_max_failures' with the constant
'max_regexp_max_failure'.

* src/regex-emacs.c (GROW_FAIL_STACK): Use the new variable
instead of the constant.  Reset it to its maximum value if
necessary.

* src/emacs.c (main): Use the new constant
'max_regexp_max_failure'.

* lisp/nxml/xmltok.el (xmltok-scan-attributes): Bind
'regexp-max-failures' to a small value.  Fixes bug#61514.
---
 lisp/nxml/xmltok.el |  3 ++-
 src/emacs.c         |  4 ++--
 src/regex-emacs.c   | 23 ++++++++---------------
 src/regex-emacs.h   |  4 ++--
 src/search.c        |  4 ++++
 5 files changed, 18 insertions(+), 20 deletions(-)

diff --git a/lisp/nxml/xmltok.el b/lisp/nxml/xmltok.el
index c36d225c7c9..32d6dfd39c1 100644
--- a/lisp/nxml/xmltok.el
+++ b/lisp/nxml/xmltok.el
@@ -731,7 +731,8 @@ xmltok-scan-after-comment-open
 
 (defun xmltok-scan-attributes ()
   (let ((recovering nil)
-	(atts-needing-normalization nil))
+	(atts-needing-normalization nil)
+	(regexp-max-failures 1000))
     (while (cond ((or (looking-at (xmltok-attribute regexp))
 		      ;; use non-greedy group
 		      (when (looking-at (concat "[^<>\n]+?"
diff --git a/src/emacs.c b/src/emacs.c
index 214e2e2a296..eb978c9de23 100644
--- a/src/emacs.c
+++ b/src/emacs.c
@@ -1499,7 +1499,7 @@ main (int argc, char **argv)
       rlim_t lim = rlim.rlim_cur;
 
       /* Approximate the amount regex-emacs.c needs per unit of
-	 emacs_re_max_failures, then add 33% to cover the size of the
+	 max_regexp_max_failures, then add 33% to cover the size of the
 	 smaller stacks that regex-emacs.c successively allocates and
 	 discards on its way to the maximum.  */
       int min_ratio = 20 * sizeof (char *);
@@ -1514,7 +1514,7 @@ main (int argc, char **argv)
 
       if (try_to_grow_stack)
 	{
-	  rlim_t newlim = emacs_re_max_failures * ratio + extra;
+	  rlim_t newlim = max_regexp_max_failures * ratio + extra;
 
 	  /* Round the new limit to a page boundary; this is needed
 	     for Darwin kernel 15.4.0 (see Bug#23622) and perhaps
diff --git a/src/regex-emacs.c b/src/regex-emacs.c
index 2dca0d16ad9..87d4d5cd434 100644
--- a/src/regex-emacs.c
+++ b/src/regex-emacs.c
@@ -868,17 +868,6 @@ print_double_string (re_char *where, re_char *string1, ptrdiff_t size1,
    space, so it is not a hard limit.  */
 #define INIT_FAILURE_ALLOC 20
 
-/* Roughly the maximum number of failure points on the stack.  Would be
-   exactly that if failure always used TYPICAL_FAILURE_SIZE items.
-   This is a variable only so users of regex can assign to it; we never
-   change it ourselves.  We always multiply it by TYPICAL_FAILURE_SIZE
-   before using it, so it should probably be a byte-count instead.  */
-/* Note that 4400 was enough to cause a crash on Alpha OSF/1,
-   whose default stack limit is 2mb.  In order for a larger
-   value to work reliably, you have to try to make it accord
-   with the process stack limit.  */
-ptrdiff_t emacs_re_max_failures = 40000;
-
 union fail_stack_elt
 {
   re_char *pointer;
@@ -912,7 +901,7 @@ #define INIT_FAIL_STACK()						\

 /* Double the size of FAIL_STACK, up to a limit
-   which allows approximately 'emacs_re_max_failures' items.
+   which allows approximately 'Vregexp_max_failures' items.
 
    Return 1 if succeeds, and 0 if either ran out of memory
    allocating space for it or it was already too large.
@@ -926,16 +915,20 @@ #define INIT_FAIL_STACK()						\
 #define FAIL_STACK_GROWTH_FACTOR 4
 
 #define GROW_FAIL_STACK(fail_stack)					\
-  (((fail_stack).size >= emacs_re_max_failures * TYPICAL_FAILURE_SIZE)        \
+  ((Vregexp_max_failures =						\
+    Vregexp_max_failures < 0						\
+    || Vregexp_max_failures > max_regexp_max_failures ?			\
+    max_regexp_max_failures : Vregexp_max_failures),			\
+   ((fail_stack).size >= Vregexp_max_failures * TYPICAL_FAILURE_SIZE)   \
    ? 0									\
    : ((fail_stack).stack						\
       = REGEX_REALLOCATE ((fail_stack).stack,				\
 	  (fail_stack).avail * sizeof (fail_stack_elt_t),		\
-          min (emacs_re_max_failures * TYPICAL_FAILURE_SIZE,                  \
+          min (Vregexp_max_failures * TYPICAL_FAILURE_SIZE,             \
                ((fail_stack).size * FAIL_STACK_GROWTH_FACTOR))          \
           * sizeof (fail_stack_elt_t)),                                 \
       ((fail_stack).size						\
-       = (min (emacs_re_max_failures * TYPICAL_FAILURE_SIZE,		\
+       = (min (Vregexp_max_failures * TYPICAL_FAILURE_SIZE,		\
 	       ((fail_stack).size * FAIL_STACK_GROWTH_FACTOR)))),	\
       1))
 
diff --git a/src/regex-emacs.h b/src/regex-emacs.h
index 1bc973363e9..16bd7da094b 100644
--- a/src/regex-emacs.h
+++ b/src/regex-emacs.h
@@ -49,8 +49,8 @@ #define EMACS_REGEX_H 1
    TODO: turn into an actual function parameter.  */
 extern Lisp_Object re_match_object;
 
-/* Roughly the maximum number of failure points on the stack.  */
-extern ptrdiff_t emacs_re_max_failures;
+/* Maximum value for Vregexp_max_failures.  */
+#define max_regexp_max_failures 40000
 
 /* Amount of memory that we can safely stack allocate.  */
 extern ptrdiff_t emacs_re_safe_alloca;
diff --git a/src/search.c b/src/search.c
index 0bb52c03eef..e3360eb3a86 100644
--- a/src/search.c
+++ b/src/search.c
@@ -3431,6 +3431,10 @@ syms_of_search (void)
 is to bind it with `let' around a small expression.  */);
   Vinhibit_changing_match_data = Qnil;
 
+  DEFVAR_INT ("regexp-max-failures", Vregexp_max_failures,
+	      doc: /* Maximum number of failures points in a regexp search.  */);
+  Vregexp_max_failures = max_regexp_max_failures;
+
   defsubr (&Slooking_at);
   defsubr (&Sposix_looking_at);
   defsubr (&Sstring_match);
-- 
2.39.0