bug#34910: 27.0.50; Too much matching reentrancy

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

Run, in *scratch*, with emacs -Q:

(with-temp-buffer
  (dotimes (i 10000)
    (insert "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))
  (insert "b")
  (goto-char (point-min))
  (looking-at ".*b"))

Result: "Too much matching reentrancy" in the minibuffer. No traceback.
Expected: The usual "Stack overflow in regexp matcher" error and
traceback.

The culprit seems to be

commit 938d252d1c6c5e2027aa250c649deb024154f936
Author: Daniel Colascione <dancol@dancol.org>
Date:   Sat Jun 16 13:46:10 2018 -0700

    Make regex matching reentrant; update syntax during match



In GNU Emacs 27.0.50 (build 9, x86_64-pc-linux-gnu, GTK+ Version
3.24.1)
 of 2019-03-18 built on dhcppc1
Repository revision: 799eb257970b1f6aeb5833417b6dd943d6479977
Repository branch: master
Windowing system distributor 'Fedora Project', version 11.0.12004000
System Description: Fedora 29 (Workstation Edition)

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.

Configured using:
 'configure --prefix=/home/mattias/eminst'

Configured features:
XPM JPEG TIFF GIF PNG SOUND DBUS GSETTINGS GLIB NOTIFY INOTIFY
LIBSELINUX GNUTLS FREETYPE XFT ZLIB TOOLKIT_SCROLL_BARS GTK3 X11 XDBE
XIM THREADS PDUMPER GMP

Important settings:
  value of $LC_MONETARY: sv_SE.UTF-8
  value of $LC_NUMERIC: sv_SE.UTF-8
  value of $LC_TIME: sv_SE.UTF-8
  value of $LANG: sv_SE.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc puny seq byte-opt gv
bytecomp byte-compile cconv dired dired-loaddefs format-spec rfc822 mml
easymenu mml-sec password-cache epa derived epg epg-config gnus-util
rmail rmail-loaddefs time-date mm-decode mm-bodies mm-encode mail-parse
rfc2231 mailabbrev gmm-utils mailheader cl-loaddefs cl-lib sendmail
rfc2047 rfc2045 ietf-drums mm-util mail-prsvr mail-utils elec-pair
mule-util tooltip eldoc electric uniquify ediff-hook vc-hooks
lisp-float-type mwheel term/x-win x-win term/common-win x-dnd tool-bar
dnd fontset image regexp-opt fringe tabulated-list replace newcomment
text-mode elisp-mode lisp-mode prog-mode register page menu-bar
rfn-eshadow isearch timer select scroll-bar mouse jit-lock font-lock
syntax facemenu font-core term/tty-colors frame cl-generic cham
georgian
utf-8-lang misc-lang vietnamese tibetan thai tai-viet lao korean
japanese eucjp-ms cp51932 hebrew greek romanian slovak czech european
ethiopic indian cyrillic chinese composite charscript charprop
case-table epa-hook jka-cmpr-hook help simple abbrev obarray minibuffer
cl-preloaded nadvice loaddefs button faces cus-face macroexp files
text-properties overlay sha1 md5 base64 format env code-pages mule
custom widget hashtable-print-readable backquote threads dbusbind
inotify dynamic-setting system-font-setting font-render-setting
move-toolbar gtk x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 44594 10186)
 (symbols 48 5845 2)
 (strings 32 14860 1818)
 (string-bytes 1 490684)
 (vectors 16 9450)
 (vector-slots 8 116818 14096)
 (floats 8 17 58)
 (intervals 56 186 0)
 (buffers 992 11))

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Mon, 18 Mar 2019 22:34:07 +0100
> 
> Run, in *scratch*, with emacs -Q:
> 
> (with-temp-buffer
>   (dotimes (i 10000)
>     (insert "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))
>   (insert "b")
>   (goto-char (point-min))
>   (looking-at ".*b"))
> 
> Result: "Too much matching reentrancy" in the minibuffer. No traceback.
> Expected: The usual "Stack overflow in regexp matcher" error and
> traceback.

Are you complaining against a different error message, or against the
lack of backtrace?

If the former, please explain why you expected that particular
error, and no other.

Thanks.

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

19 mars 2019 kl. 09.05 skrev Eli Zaretskii <eliz@gnu.org>:
> 
>> Result: "Too much matching reentrancy" in the minibuffer. No traceback.
>> Expected: The usual "Stack overflow in regexp matcher" error and
>> traceback.
> 
> Are you complaining against a different error message, or against the
> lack of backtrace?

Both. In fact, a gdb-level stack trace indicates that the "too much reentrancy" error was signalled when trying to deal with the stack overflow error somehow. I didn't get further then, and thought that Daniel Colascione would know more, since bisecting found his particular change.

The should be no question that "stack overflow" + debugger is the correct and intended behaviour, should it?

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Tue, 19 Mar 2019 10:27:09 +0100
> Cc: dancol@dancol.org, 34910@debbugs.gnu.org
> 
> The should be no question that "stack overflow" + debugger is the correct and intended behaviour, should it?

I don't know yet.  I asked you to elaborate on the reasons for your
expectations, and I still hope you will humor me.  Because just
taking the problem's manifestations at face value, one could argue
that the precise error message is immaterial, as long as it points to
the right direction, and "stack overflow in regexp matcher" is as
obscure as the other message.  But maybe I'm missing something, which
is why I asked you to elaborate on your reasoning.

Thanks.

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 1229 bytes --]

tis 2019-03-19 klockan 12:01 +0200 skrev Eli Zaretskii:
> 
> I don't know yet.  I asked you to elaborate on the reasons for your
> expectations, and I still hope you will humor me.  Because just
> taking the problem's manifestations at face value, one could argue
> that the precise error message is immaterial, as long as it points to
> the right direction, and "stack overflow in regexp matcher" is as
> obscure as the other message.  But maybe I'm missing something, which
> is why I asked you to elaborate on your reasoning.

Sorry, I didn't mean to sound touchy! Being the bug reporter, I deserve
every probing question. I'm most grateful for your quick reply!

It turns out the regexp cache logic is broken: it always uses the last
(LRU) entry, and fails if that entry is busy. It should really use the
last free entry.

What happened was that a regexp failed because of stack overflow, which
caused lots of code to run and many regexps to be compiled, but the
original (failing) regexp was still marked busy in the cache.
Eventually, it had been pushed down to the last position in the cache,
where it caused the next request for a free cache entry to fail with
the reentrancy error.

This patch fixes it. Please review.


[-- Attachment #2: 0001-Fix-spurious-regexp-reentrancy-error.patch --]
[-- Type: text/x-patch, Size: 2034 bytes --]

From 6ec7c354513a058fb0b396150ed3a7c1655e2a18 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Tue, 19 Mar 2019 13:06:20 +0100
Subject: [PATCH] Fix spurious regexp reentrancy error

src/search.c (compile_pattern): Don't give up if the last regexp cache
entry is busy.  Instead, use the last (least recently used) non-busy
entry, and only report the reentrancy error if there is no free entry
at all (Bug#34910).
---
 src/search.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/src/search.c b/src/search.c
index a1e0b0976e..2c00e6e93f 100644
--- a/src/search.c
+++ b/src/search.c
@@ -223,11 +223,13 @@ static struct regexp_cache *
 compile_pattern (Lisp_Object pattern, struct re_registers *regp,
 		 Lisp_Object translate, bool posix, bool multibyte)
 {
-  struct regexp_cache *cp, **cpp;
+  struct regexp_cache *cp, **cpp, **lru_nonbusy;
 
-  for (cpp = &searchbuf_head; ; cpp = &cp->next)
+  for (cpp = &searchbuf_head, lru_nonbusy = NULL; ; cpp = &cp->next)
     {
       cp = *cpp;
+      if (!cp->busy)
+        lru_nonbusy = cpp;
       /* Entries are initialized to nil, and may be set to nil by
 	 compile_pattern_1 if the pattern isn't valid.  Don't apply
 	 string accessors in those cases.  However, compile_pattern_1
@@ -247,13 +249,14 @@ compile_pattern (Lisp_Object pattern, struct re_registers *regp,
 	  && cp->buf.charset_unibyte == charset_unibyte)
 	break;
 
-      /* If we're at the end of the cache, compile into the nil cell
-	 we found, or the last (least recently used) cell with a
-	 string value.  */
+      /* If we're at the end of the cache, compile into the last
+	 (least recently used) non-busy cell in the cache.  */
       if (cp->next == 0)
 	{
-          if (cp->busy)
+          if (!lru_nonbusy)
             error ("Too much matching reentrancy");
+          cpp = lru_nonbusy;
+          cp = *cpp;
 	compile_it:
           eassert (!cp->busy);
 	  compile_pattern_1 (cp, pattern, translate, posix);
-- 
2.20.1

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Cc: dancol@dancol.org, 34910@debbugs.gnu.org
> Date: Tue, 19 Mar 2019 13:25:13 +0100
> 
> What happened was that a regexp failed because of stack overflow, which
> caused lots of code to run and many regexps to be compiled, but the
> original (failing) regexp was still marked busy in the cache.
> Eventually, it had been pushed down to the last position in the cache,
> where it caused the next request for a free cache entry to fail with
> the reentrancy error.
> 
> This patch fixes it. Please review.

Thanks, this looked reasonable.  Let's wait for Daniel to comment.

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 316 bytes --]

Here is another improvement: there should be no reason to keep the
regexp busy during the overflow error processing, so release it first.

By the way, is there any reason why only calls to re_search_2 are made
with a busy-marked regexp buffer, not calls to re_search? Are the
latter guaranteed not to be reentrant?


[-- Attachment #2: 0001-Release-regexp-before-signalling-overflow-error.patch --]
[-- Type: text/x-patch, Size: 1474 bytes --]

From 3c7555bf0fc38db94d87923869cb48d57b12605a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Tue, 19 Mar 2019 13:47:13 +0100
Subject: [PATCH] Release regexp before signalling overflow error

src/search.c (looking_at_1, search_buffer_re): Unfreeze the regexp buffer
before signalling a matcher overflow, since the error processing may
require quite some regexp use as well (Bug#34910).
---
 src/search.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/src/search.c b/src/search.c
index 2c00e6e93f..b61f65a77c 100644
--- a/src/search.c
+++ b/src/search.c
@@ -344,7 +344,10 @@ looking_at_1 (Lisp_Object string, bool posix)
 		  ZV_BYTE - BEGV_BYTE);
 
   if (i == -2)
-    matcher_overflow ();
+    {
+      unbind_to (count, Qnil);
+      matcher_overflow ();
+    }
 
   val = (i >= 0 ? Qt : Qnil);
   if (preserve_match_data && i >= 0)
@@ -1223,6 +1226,7 @@ search_buffer_re (Lisp_Object string, ptrdiff_t pos, ptrdiff_t pos_byte,
                          pos_byte - BEGV_BYTE);
       if (val == -2)
         {
+          unbind_to (count, Qnil);
           matcher_overflow ();
         }
       if (val >= 0)
@@ -1268,6 +1272,7 @@ search_buffer_re (Lisp_Object string, ptrdiff_t pos, ptrdiff_t pos_byte,
                          lim_byte - BEGV_BYTE);
       if (val == -2)
         {
+          unbind_to (count, Qnil);
           matcher_overflow ();
         }
       if (val >= 0)
-- 
2.20.1

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Cc: dancol@dancol.org, 34910@debbugs.gnu.org
> Date: Tue, 19 Mar 2019 13:25:13 +0100
> 
> It turns out the regexp cache logic is broken: it always uses the last
> (LRU) entry, and fails if that entry is busy. It should really use the
> last free entry.
> 
> What happened was that a regexp failed because of stack overflow, which
> caused lots of code to run and many regexps to be compiled, but the
> original (failing) regexp was still marked busy in the cache.
> Eventually, it had been pushed down to the last position in the cache,
> where it caused the next request for a free cache entry to fail with
> the reentrancy error.
> 
> This patch fixes it. Please review.

Since there were no further comments, I think you should push this.

Thanks.

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Cc: dancol@dancol.org, 34910@debbugs.gnu.org
> Date: Tue, 19 Mar 2019 13:50:00 +0100
> 
> Here is another improvement: there should be no reason to keep the
> regexp busy during the overflow error processing, so release it first.

Looks OK to me.

> By the way, is there any reason why only calls to re_search_2 are made
> with a busy-marked regexp buffer, not calls to re_search? Are the
> latter guaranteed not to be reentrant?

Not sure.  Stefan, any thoughts?

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

30 mars 2019 kl. 10.30 skrev Eli Zaretskii <eliz@gnu.org>:
> 
>> Here is another improvement: there should be no reason to keep the
>> regexp busy during the overflow error processing, so release it first.
> 
> Looks OK to me.

Thank you, both pushed.

>> By the way, is there any reason why only calls to re_search_2 are made
>> with a busy-marked regexp buffer, not calls to re_search? Are the
>> latter guaranteed not to be reentrant?
> 
> Not sure.  Stefan, any thoughts?

Maybe Daniel only had reentrancy concerns about regexp matching on buffers, not on strings?

bug#34910: 27.0.50; Too much matching reentrancy

[Stefan Monnier]

>> By the way, is there any reason why only calls to re_search_2 are made
>> with a busy-marked regexp buffer, not calls to re_search? Are the
>> latter guaranteed not to be reentrant?
> Not sure.  Stefan, any thoughts?

It was probably just an oversight, because whether we're searching
within strings or within buffers the same problems appear with \{N\}
repetitions (where the counter is stored directly inside the
regexp-byte-code) and with on-the-fly strength-reduction (where we
replace some byte-code with cheaper ones (where applicable) on the first
pass through the regexp).


        Stefan

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

30 mars 2019 kl. 13.55 skrev Stefan Monnier <monnier@IRO.UMontreal.CA>:
> 
> It was probably just an oversight, because whether we're searching
> within strings or within buffers the same problems appear with \{N\}
> repetitions (where the counter is stored directly inside the
> regexp-byte-code) and with on-the-fly strength-reduction (where we
> replace some byte-code with cheaper ones (where applicable) on the first
> pass through the regexp).

Is the reentrancy just in preparation for future needs, or is it possible to re-enter the regexp code right now?

If the latter, we may just as well fix the string case here and now; otherwise, I'd like to close the bug.

bug#34910: 27.0.50; Too much matching reentrancy

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Sat, 30 Mar 2019 14:05:50 +0100
> Cc: Eli Zaretskii <eliz@gnu.org>, dancol@dancol.org, 34910@debbugs.gnu.org
> 
> 30 mars 2019 kl. 13.55 skrev Stefan Monnier <monnier@IRO.UMontreal.CA>:
> > 
> > It was probably just an oversight, because whether we're searching
> > within strings or within buffers the same problems appear with \{N\}
> > repetitions (where the counter is stored directly inside the
> > regexp-byte-code) and with on-the-fly strength-reduction (where we
> > replace some byte-code with cheaper ones (where applicable) on the first
> > pass through the regexp).
> 
> Is the reentrancy just in preparation for future needs, or is it possible to re-enter the regexp code right now?

I think the former, since reentrance could only happen if a Lisp
thread yields while inside a regexp function, which I think is not
possible, since we never call 'select' or any Lisp from there, do we?

bug#34910: 27.0.50; Too much matching reentrancy

[Daniel Colascione]

On 3/30/19 4:18 AM, Mattias Engdegård wrote:
> 30 mars 2019 kl. 10.30 skrev Eli Zaretskii <eliz@gnu.org>:
>>
>>> Here is another improvement: there should be no reason to keep the
>>> regexp busy during the overflow error processing, so release it first.
>>
>> Looks OK to me.
> 
> Thank you, both pushed.

Thanks!

> 
>>> By the way, is there any reason why only calls to re_search_2 are made
>>> with a busy-marked regexp buffer, not calls to re_search? Are the
>>> latter guaranteed not to be reentrant?
>>
>> Not sure.  Stefan, any thoughts?
> 
> Maybe Daniel only had reentrancy concerns about regexp matching on buffers, not on strings?

We do automatic syntax discovery on buffers, not strings.

bug#34910: 27.0.50; Too much matching reentrancy

[Stefan Monnier]

> Is the reentrancy just in preparation for future needs, or is it possible to
> re-enter the regexp code right now?

IIRC we do when the regexp matcher needs to call syntax-propertize.


        Stefan

bug#34910: 27.0.50; Too much matching reentrancy

[Daniel Colascione]

>> Is the reentrancy just in preparation for future needs, or is it
>> possible to
>> re-enter the regexp code right now?
>
> IIRC we do when the regexp matcher needs to call syntax-propertize.

Right. That was the original motivation for the patch.

bug#34910: 27.0.50; Too much matching reentrancy

[Mattias Engdegård]

30 mars 2019 kl. 18.10 skrev Daniel Colascione <dancol@dancol.org>:
> 
>>> Is the reentrancy just in preparation for future needs, or is it
>>> possible to
>>> re-enter the regexp code right now?
>> 
>> IIRC we do when the regexp matcher needs to call syntax-propertize.
> 
> Right. That was the original motivation for the patch.

Thank you for the explanation.
There is no shortage of work to be done in the regexp code but it looks like this bug can be closed.