Subtle bug in intervals code

Subtle bug in intervals code

[Dmitry Antipov]

Commit 109118 (by me) introduces the following change in src/intervals.c, function delete_interval:

@@ -1262,8 +1198,7 @@
    register INTERVAL parent;
    ptrdiff_t amt = LENGTH (i);

-  if (amt > 0)			/* Only used on zero-length intervals now.  */
-    abort ();
+  eassert (amt == 0);		/* Only used on zero-length intervals now.  */

    if (ROOT_INTERVAL_P (i))
      {

Now this eassert traps at interval with negative length. I'm not familiar with
this subsystem enough to find (possible) bug quickly, so any help is appreciated.
The backtrace is:

#0  0x0000003fe1836567 in kill () at ../sysdeps/unix/syscall-template.S:82
#1  0x000000000054f58c in fatal_error_signal (sig=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/emacs.c:362
#2  fatal_error_signal (sig=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/emacs.c:332
#3  <signal handler called>
#4  0x0000003fe1836567 in kill () at ../sysdeps/unix/syscall-template.S:82
#5  0x000000000054ec05 in abort () at /home/dima/work/stuff/emacs/trunk/src/emacs.c:390
#6  0x00000000005c0b0a in die (msg=<optimized out>, file=<optimized out>, line=<optimized out>)
     at /home/dima/work/stuff/emacs/trunk/src/alloc.c:6753
#7  0x0000000000643ecb in delete_interval (i=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/intervals.c:1201
#8  0x00000000006452cc in merge_interval_left (i=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/intervals.c:1479
#9  0x000000000064c93a in set_text_properties (start=..., end=..., properties=..., object=..., coherent_change_p=...)
     at /home/dima/work/stuff/emacs/trunk/src/textprop.c:1306
#10 0x000000000064cb10 in Fset_text_properties (start=<optimized out>, end=<optimized out>, properties=<optimized out>,
     object=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/textprop.c:1244
#11 0x00000000005e0379 in eval_sub (form=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/eval.c:2176
#12 0x00000000005e0af5 in Fprogn (args=...) at /home/dima/work/stuff/emacs/trunk/src/eval.c:362
[...skipped a lot...]

Dmitry

Re: Subtle bug in intervals code

[Andreas Schwab]

Dmitry Antipov <dmantipov@yandex.ru> writes:

> Commit 109118 (by me) introduces the following change in src/intervals.c, function delete_interval:
>
> @@ -1262,8 +1198,7 @@
>    register INTERVAL parent;
>    ptrdiff_t amt = LENGTH (i);
>
> -  if (amt > 0)			/* Only used on zero-length intervals now.  */
> -    abort ();
> +  eassert (amt == 0);		/* Only used on zero-length intervals now.  */
>
>    if (ROOT_INTERVAL_P (i))
>      {
>
> Now this eassert traps at interval with negative length. I'm not familiar with
> this subsystem enough to find (possible) bug quickly, so any help is appreciated.

I think this will fix it.  The total length of an interval doesn't
change when it is absorbed by its children.

diff --git a/src/intervals.c b/src/intervals.c
index 5b8d44e..cd1254b 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -1391,10 +1391,6 @@ merge_interval_right (register INTERVAL i)
   register ptrdiff_t absorb = LENGTH (i);
   register INTERVAL successor;
 
-  /* Zero out this interval.  */
-  i->total_length -= absorb;
-  CHECK_TOTAL_LENGTH (i);
-
   /* Find the succeeding interval.  */
   if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
 				      as we descend.  */
@@ -1413,6 +1409,10 @@ merge_interval_right (register INTERVAL i)
       return successor;
     }
 
+  /* Zero out this interval.  */
+  i->total_length -= absorb;
+  CHECK_TOTAL_LENGTH (i);
+
   successor = i;
   while (! NULL_PARENT (successor))	   /* It's above us.  Subtract as
 					      we ascend.  */
@@ -1447,10 +1447,6 @@ merge_interval_left (register INTERVAL i)
   register ptrdiff_t absorb = LENGTH (i);
   register INTERVAL predecessor;
 
-  /* Zero out this interval.  */
-  i->total_length -= absorb;
-  CHECK_TOTAL_LENGTH (i);
-
   /* Find the preceding interval.  */
   if (! NULL_LEFT_CHILD (i))	/* It's below us. Go down,
 				   adding ABSORB as we go.  */
@@ -1469,9 +1465,13 @@ merge_interval_left (register INTERVAL i)
       return predecessor;
     }
 
+  /* Zero out this interval.  */
+  i->total_length -= absorb;
+  CHECK_TOTAL_LENGTH (i);
+
   predecessor = i;
   while (! NULL_PARENT (predecessor))	/* It's above us.  Go up,
-				   subtracting ABSORB.  */
+					   subtracting ABSORB.  */
     {
       if (AM_RIGHT_CHILD (predecessor))
 	{

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Subtle bug in intervals code

[Paul Eggert]

Thanks, that patch looks good.  It fixes common crashes in my development
version which were getting to be annoying, so I installed it in your
name as trunk bzr 109153.

Re: Subtle bug in intervals code

[Stefan Monnier]

> I think this will fix it.  The total length of an interval doesn't
> change when it is absorbed by its children.

I can't wrap my head around this code, so if this is the right fix,
thank you very much.


        Stefan

Re: Subtle bug in intervals code

[Eli Zaretskii]

> Date: Wed, 18 Jul 2012 15:48:08 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> Commit 109118 (by me) introduces the following change in src/intervals.c, function delete_interval:
> 
> @@ -1262,8 +1198,7 @@
>     register INTERVAL parent;
>     ptrdiff_t amt = LENGTH (i);
> 
> -  if (amt > 0)			/* Only used on zero-length intervals now.  */
> -    abort ();
> +  eassert (amt == 0);		/* Only used on zero-length intervals now.  */
> 
>     if (ROOT_INTERVAL_P (i))
>       {
> 
> Now this eassert traps at interval with negative length. I'm not familiar with
> this subsystem enough to find (possible) bug quickly, so any help is appreciated.
> The backtrace is:
> 
> #0  0x0000003fe1836567 in kill () at ../sysdeps/unix/syscall-template.S:82
> #1  0x000000000054f58c in fatal_error_signal (sig=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/emacs.c:362
> #2  fatal_error_signal (sig=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/emacs.c:332
> #3  <signal handler called>
> #4  0x0000003fe1836567 in kill () at ../sysdeps/unix/syscall-template.S:82
> #5  0x000000000054ec05 in abort () at /home/dima/work/stuff/emacs/trunk/src/emacs.c:390
> #6  0x00000000005c0b0a in die (msg=<optimized out>, file=<optimized out>, line=<optimized out>)
>      at /home/dima/work/stuff/emacs/trunk/src/alloc.c:6753
> #7  0x0000000000643ecb in delete_interval (i=<optimized out>) at /home/dima/work/stuff/emacs/trunk/src/intervals.c:1201

Been there, done that:

  http://lists.gnu.org/archive/html/emacs-devel/2010-09/msg01138.html

My last message, here:

  http://lists.gnu.org/archive/html/emacs-devel/2010-09/msg01207.html

got no responses.  So the mystery is still a mystery (at least to me),
but one thing is certain: you must modify the assertion to

  eassert (amt <= 0);

Re: Subtle bug in intervals code

[Eli Zaretskii]

> Date: Wed, 18 Jul 2012 15:48:08 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> Commit 109118 (by me) introduces the following change in src/intervals.c, function delete_interval:
> 
> @@ -1262,8 +1198,7 @@
>     register INTERVAL parent;
>     ptrdiff_t amt = LENGTH (i);
> 
> -  if (amt > 0)			/* Only used on zero-length intervals now.  */
> -    abort ();
> +  eassert (amt == 0);		/* Only used on zero-length intervals now.  */
> 
>     if (ROOT_INTERVAL_P (i))
>       {
> 
> Now this eassert traps at interval with negative length. I'm not familiar with
> this subsystem enough to find (possible) bug quickly, so any help is appreciated.

Do you have an easy test case that triggers this?  The only ones
posted are to bootstrap, which is not my idea of an easy test case...

Re: Subtle bug in intervals code

[Paul Eggert]

On 07/18/2012 11:33 AM, Eli Zaretskii wrote:
> Do you have an easy test case that triggers this?

My test involves creating bool vectors of various sizes.
Usually it works, sometimes the intervals.c assert fails.
There doesn't seem to be a pattern; no single test case
always works.

That is, in *scratch* I do this:

(make-bool-vector 1000000 nil)
(make-bool-vector 1000000 nil)
(make-bool-vector 10000 nil)
(make-bool-vector 100000 nil)
(make-bool-vector 10000000 nil)

and evaluate each one in turn.  I do some more if the first
few don't dump core.  It fairly reliably dumps core eventually.

This is Fedora 15 x86-64, compiled with GCC 4.7.1,
with -g -O0 -DENABLE_CHECKING.  I ran emacs -Q
under X.

Re: Subtle bug in intervals code

[Eli Zaretskii]

> Date: Wed, 18 Jul 2012 12:27:47 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: Dmitry Antipov <dmantipov@yandex.ru>, emacs-devel@gnu.org
> 
> That is, in *scratch* I do this:
> 
> (make-bool-vector 1000000 nil)
> (make-bool-vector 1000000 nil)
> (make-bool-vector 10000 nil)
> (make-bool-vector 100000 nil)
> (make-bool-vector 10000000 nil)
> 
> and evaluate each one in turn.  I do some more if the first
> few don't dump core.  It fairly reliably dumps core eventually.

Thanks, but I couldn't crash Emacs here this way.

Btw, why would make-bool-vector exercise intervals?  The crash is
triggered by rearranging text properties, AFAICS.

Re: Subtle bug in intervals code

[Paul Eggert]

On 07/18/2012 12:44 PM, Eli Zaretskii wrote:
> why would make-bool-vector exercise intervals?

I don't think it does, directly.  I imagine intervals
are exercised due to my editing the *scratch* buffer,
typing C-j, etc.