GNU bug report logs - #72802
31.0.50; Crash in (equal sub-char-table-a sub-char-table-b)

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 72802 in the body.
You can then email your comments to 72802 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 31.0.50; Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 13:13:34 +0000

Summary: Comparing sub char tables can lead to crashes in equal when
they are read with their read syntax; using high-level char table
manipulation routines and comparing char tables (not sub char tables
directly) is almost certain to result in rare crashes as well.

The code in internal_equal compares sub-char-tables incorrectly and
segfaults on my machine (little-endian 64-bit words, LSB tags, 3 ==
Lisp_Cons) when evaluating this code:

(setq a #^^[3 2597376 (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3)])

(setq b #^^[3 2597504 (3) (3) (3) (3) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (3) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2) (2)])

(equal a b)


This happened to me while working on pdumper code for the no-purespace
branch and trying to compare dumped sub char tables, but it can happen
when reading sub char tables using their read syntax, too.

I'm almost certain the bug can actually happen when manipulating char
tables using higher-level routines, and comparing char tables, not sub
char tables.

Comparing char tables definitely results in nonsensical (but identical)
arguments 'o1' and 'o2' being passed to 'internal_equal', and put into
the hash table 'ht' in internal_equal.

This is almost definitely a crashable bug, but a very rare one (it
relies on conservative stack marking marking our hash table and trying
to mark the invalid conses in it), without using the read syntax for sub
char tables.

On 32-bit machines, the crashes might be much more common.

The problem is this code:

	for (ptrdiff_t i = 0; i < size; i++)
	  {
	    Lisp_Object v1, v2;
	    v1 = AREF (o1, i);
	    v2 = AREF (o2, i);
	    if (!internal_equal (v1, v2, equal_kind, depth + 1, ht))
	      return false;
	  }

which assumes sub char tables are ordinary pseudovectors and can be
compared by comparing XVECTOR (o1)->contents to XVECTOR (o2)->contents.

However, sub char tables should be compared by comparing
XSUB_CHAR_TABLE (o1)->contents to XSUB_CHAR_TABLE (o2)->contents, after
checking that 'depth' and 'min_char' also match.

The memory layout of sub char tables is:

struct Lisp_Sub_Char_Table
  {
    /* HEADER.SIZE is the vector's size field, which also holds the
       pseudovector type information.  It holds the size, too.  */
    union vectorlike_header header;

    /* Depth of this sub char-table.  It should be 1, 2, or 3.  A sub
       char-table of depth 1 contains 16 elements, and each element
       covers 4096 (128*32) characters.  A sub char-table of depth 2
       contains 32 elements, and each element covers 128 characters.  A
       sub char-table of depth 3 contains 128 elements, and each element
       is for one character.  */
    int depth;

    /* Minimum character covered by the sub char-table.  */
    int min_char;

    /* Use set_sub_char_table_contents to set this.  */
    Lisp_Object contents[FLEXIBLE_ARRAY_MEMBER];
  } GCALIGNED_STRUCT;

So the first 64-bit word after the header has 'min_char' in the high
bits, 3 in the low bits, in the above example.  In my case, we end up
calling

internal_equal (o1=XIL(0x27a20000000003), o2=XIL(0x27a28000000003),
equal_kind=EQUAL_PLAIN, depth=1, ht=XIL(0)) at fns.c:2887

with the nonsensical Lisp words o1 = 0x27a20000000003 (depth = 3,
min_char = 0x27a200) and o2 = 0x27a28000000003 (depth = 3, min_char =
0x27a280); these are interpreted as Lisp conses and we attempt to
dereference them, which leads to the segfault.

Relevant section of the backtrace:

(gdb) bt full
#0  0x0000555555838ea7 in internal_equal (o1=XIL(0x27a20000000003), o2=XIL(0x27a28000000003), equal_kind=EQUAL_PLAIN, depth=1, ht=XIL(0)) at fns.c:2887
        li = {
          tortoise = XIL(0x27a20000000003),
          max = 2,
          n = 0,
          q = 2
        }
#1  0x00005555558393c8 in internal_equal (o1=XIL(0x555557718945), o2=XIL(0x55555677bda5), equal_kind=EQUAL_PLAIN, depth=0, ht=XIL(0)) at fns.c:2963
        v1 = XIL(0x27a20000000003)
        v2 = XIL(0x27a28000000003)
        i = 0
        size = 129
#2  0x0000555555838a01 in Fequal (o1=XIL(0x555557718945), o2=XIL(0x55555677bda5)) at fns.c:2783

(gdb) l
2958		for (ptrdiff_t i = 0; i < size; i++)
2959		  {
2960		    Lisp_Object v1, v2;
2961		    v1 = AREF (o1, i);
2962		    v2 = AREF (o2, i);
2963		    if (!internal_equal (v1, v2, equal_kind, depth + 1, ht))
2964		      return false;
2965		  }
2966		return true;
2967	      }
(gdb) p SUB_CHAR_TABLE_P (o1)
$38 = true
(gdb) p SUB_CHAR_TABLE_P (o2)
$39 = true
(gdb) p *XSUB_CHAR_TABLE (o1)
$40 = {
  header = {
    size = 4611686018981036161
  },
  depth = 3,
  min_char = 2597376,
  contents = 0x555557718950
}
(gdb) p *XSUB_CHAR_TABLE (o2)
$41 = {
  header = {
    size = 4611686018981036161
  },
  depth = 3,
  min_char = 2597504,
  contents = 0x55555677bdb0
}
(gdb) p AREF (o1, 0)
$42 = (struct Lisp_X *) 0x27a20000000003
(gdb) p AREF (o2, 0)
$43 = (struct Lisp_X *) 0x27a28000000003
(gdb) p *XVECTOR (o1)
$44 = {
  header = {
    size = 4611686018981036161
  },
  contents = 0x555557718948
}
(gdb) p *XVECTOR (o2)
$45 = {
  header = {
    size = 4611686018981036161
  },
  contents = 0x55555677bda8
}

Fix coming up once this has a bug number.

Message #8 received at 72802 <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: 72802 <at> debbugs.gnu.org
Subject: Re: 31.0.50; Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 14:11:17 +0000

Pip Cet <pipcet <at> protonmail.com> writes:
> The code in internal_equal compares sub-char-tables incorrectly

This patch should fix things for the release branch:


From df31249b3686c38e4816cfa2784c25443a61b749 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet <at> protonmail.com>
Subject: [PATCH] Fix crashes when comparing sub char tables (Bug#72802)

* src/fns.c (internal_equal): Handle sub char tables specially, like
'mark_char_table' does.
---
 src/fns.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/src/fns.c b/src/fns.c
index 57113a8c5ed..cb799a13a6e 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2948,14 +2948,28 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	/* Aside from them, only true vectors, char-tables, compiled
 	   functions, and fonts (font-spec, font-entity, font-object)
 	   are sensible to compare, so eliminate the others now.  */
+	ptrdiff_t i = 0;
 	if (size & PSEUDOVECTOR_FLAG)
 	  {
 	    if (((size & PVEC_TYPE_MASK) >> PSEUDOVECTOR_AREA_BITS)
 		< PVEC_CLOSURE)
 	      return false;
+
+	    /* Bug#72802.  See 'mark_char_table' in alloc.c.  */
+	    if (SUB_CHAR_TABLE_P (o1))
+	      {
+		i = SUB_CHAR_TABLE_OFFSET;
+		if (XSUB_CHAR_TABLE (o1)->depth !=
+		    XSUB_CHAR_TABLE (o2)->depth)
+		  return false;
+		if (XSUB_CHAR_TABLE (o1)->min_char !=
+		    XSUB_CHAR_TABLE (o2)->min_char)
+		  return false;
+	      }
+
 	    size &= PSEUDOVECTOR_SIZE_MASK;
 	  }
-	for (ptrdiff_t i = 0; i < size; i++)
+	for (; i < size; i++)
 	  {
 	    Lisp_Object v1, v2;
 	    v1 = AREF (o1, i);
-- 
2.45.2


Okay for emacs-30 (and/or master, though I'd prefer to fix it
differently on that branch)?

For the master branch, I think the right thing to do is to turn the
first two, non-Lisp members of Lisp_Sub_Char_Table ('depth' and
'min_char') into 'Lisp_Object's.  Then we can simplify the code and
compare sub char tables as we do ordinary vectors, at the cost of eight
bytes of extra storage per sub char table on machines with 64-bit
EMACS_INTs.

BTW, I'm surprised this code returns nil; I think that should be
documented.

(setq a (make-char-table nil))
(setq b (make-char-table nil))
(aset a 1 nil)
(dotimes (i (max-char))
  (unless (equal (aref a i) (aref b i))
    (error "i = %S" i)))
(equal a b)

Pip

Message #11 received at 72802 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 72802 <at> debbugs.gnu.org
Subject: Re: bug#72802: 31.0.50;
 Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 17:50:11 +0300

> Date: Sun, 25 Aug 2024 14:11:17 +0000
> From:  Pip Cet via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> 
> Pip Cet <pipcet <at> protonmail.com> writes:
> > The code in internal_equal compares sub-char-tables incorrectly
> 
> This patch should fix things for the release branch:

I don't see a reason to install this on the release branch now.  Not
even on master, I think, unless we see a bug related to it that is not
caused by a specially-concocted Lisp program or GDB command.

If this is required for the no-pure-space branch, I think you should
install this on that branch.  Then it will be merged together with the
branch.

If you see some urgent need to fix this ASAP on master, please tell
why you think so.

> +	    /* Bug#72802.  See 'mark_char_table' in alloc.c.  */
> +	    if (SUB_CHAR_TABLE_P (o1))
> +	      {
> +		i = SUB_CHAR_TABLE_OFFSET;
> +		if (XSUB_CHAR_TABLE (o1)->depth !=
> +		    XSUB_CHAR_TABLE (o2)->depth)
> +		  return false;
> +		if (XSUB_CHAR_TABLE (o1)->min_char !=
> +		    XSUB_CHAR_TABLE (o2)->min_char)
> +		  return false;
> +	      }

I looked at mark_char_table, trying to understand what the above
comments wants to say, and couldn't.  So I think the comment should
be improved, so that it would be more clear what it wants to say.

Also, please move the assignment of SUB_CHAR_TABLE_OFFSET to i to
after the two early 'return's.

> For the master branch, I think the right thing to do is to turn the
> first two, non-Lisp members of Lisp_Sub_Char_Table ('depth' and
> 'min_char') into 'Lisp_Object's.  Then we can simplify the code and
> compare sub char tables as we do ordinary vectors, at the cost of eight
> bytes of extra storage per sub char table on machines with 64-bit
> EMACS_INTs.

I'm not sure we want to pay this cost.  What bothers me is mainly the
run-time cost of extracting integers from Lisp objects.  char-table is
supposed to be very efficient, both memory-wise and CPU-wise, and I
think the performance here trumps simplicity.

> BTW, I'm surprised this code returns nil; I think that should be
> documented.
> 
> (setq a (make-char-table nil))
> (setq b (make-char-table nil))
> (aset a 1 nil)
> (dotimes (i (max-char))
>   (unless (equal (aref a i) (aref b i))
>     (error "i = %S" i)))
> (equal a b)

Why are you surprised?  Setting a single cell of a char-table changes
its structure, usually in quite a radical way.  'aref' does some very
special things for char-tables; the semantics of accessing an element
of a vector is only correct superficially, not in the details.

The internals of a char-table are not really documented in the ELisp
manual; the description there is mostly phenomenological, without any
details.  If you want to document the internals, I think the proper
place is to add a comment at the beginning of chartab.c with these
details (and there are a lot of details not really documented
anywhere, at least not explicitly), and then this nit should be part
of that.

Message #14 received at 72802 <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 72802 <at> debbugs.gnu.org
Subject: Re: bug#72802: 31.0.50;
 Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 15:15:14 +0000

"Eli Zaretskii" <eliz <at> gnu.org> writes:

>> Date: Sun, 25 Aug 2024 14:11:17 +0000
>> From:  Pip Cet via "Bug reports for GNU Emacs,
>>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
>>
>> Pip Cet <pipcet <at> protonmail.com> writes:
>> > The code in internal_equal compares sub-char-tables incorrectly
>>
>> This patch should fix things for the release branch:
>
> I don't see a reason to install this on the release branch now.

Your call.

> Not even on master, I think, unless we see a bug related to it that is not
> caused by a specially-concocted Lisp program or GDB command.

It's a clear bug, whether or not the Lisp programs that cause it are
"specially-concocted" (what's that supposed to mean, anyway?  We can't
just delay fixing what are clearly bugs until they pop up on random
users' machines!)

So I think it's important to fix this soon (not "now") on the master
branch.

> If this is required for the no-pure-space branch, I think you should
> install this on that branch.  Then it will be merged together with the
> branch.

It's not, it just popped up during work on that branch.

> If you see some urgent need to fix this ASAP on master, please tell
> why you think so.

Not "ASAP", and not "urgent", no.  We certainly can take the time to
address your comments and fix up things.

>> +	    /* Bug#72802.  See 'mark_char_table' in alloc.c.  */
>> +	    if (SUB_CHAR_TABLE_P (o1))
>> +	      {
>> +		i = SUB_CHAR_TABLE_OFFSET;
>> +		if (XSUB_CHAR_TABLE (o1)->depth !=
>> +		    XSUB_CHAR_TABLE (o2)->depth)
>> +		  return false;
>> +		if (XSUB_CHAR_TABLE (o1)->min_char !=
>> +		    XSUB_CHAR_TABLE (o2)->min_char)
>> +		  return false;
>> +	      }
>
> I looked at mark_char_table, trying to understand what the above
> comments wants to say, and couldn't.  So I think the comment should
> be improved, so that it would be more clear what it wants to say.

As you will have seen, then, we compare the same "vector" elements in
internal_equal as are marked in mark_char_table, but I agree the comment
(and the code) can be improved, and will try to do that.

> Also, please move the assignment of SUB_CHAR_TABLE_OFFSET to i to
> after the two early 'return's.

Gladly.

>> For the master branch, I think the right thing to do is to turn the
>> first two, non-Lisp members of Lisp_Sub_Char_Table ('depth' and
>> 'min_char') into 'Lisp_Object's.  Then we can simplify the code and
>> compare sub char tables as we do ordinary vectors, at the cost of eight
>> bytes of extra storage per sub char table on machines with 64-bit
>> EMACS_INTs.
>
> I'm not sure we want to pay this cost.  What bothers me is mainly the
> run-time cost of extracting integers from Lisp objects.

That might be noticeable on 32-bit machines with EMACS_WIDE_INT, I
suppose, or on very old machines where memory isn't so much slower than
register manipulation.

> char-table is
> supposed to be very efficient, both memory-wise and CPU-wise, and I
> think the performance here trumps simplicity.

How about using an "ordinary" pseudovector with its non-Lisp elements at
the end?

>> BTW, I'm surprised this code returns nil; I think that should be
>> documented.
>>
>> (setq a (make-char-table nil))
>> (setq b (make-char-table nil))
>> (aset a 1 nil)
>> (dotimes (i (max-char))
>>   (unless (equal (aref a i) (aref b i))
>>     (error "i = %S" i)))
>> (equal a b)
>
> Why are you surprised?  Setting a single cell of a char-table changes
> its structure, usually in quite a radical way.  'aref' does some very
> special things for char-tables; the semantics of accessing an element
> of a vector is only correct superficially, not in the details.

Indeed, and I expected (and still expect) 'equal' to ignore such
details.

> The internals of a char-table are not really documented in the ELisp
> manual; the description there is mostly phenomenological, without any
> details.

I don't think 'equal' behavior is part of those "internals", and it
certainly isn't a detail.  Given the great trouble we're going to to
make 'equal' work on char tables at all, I'm still surprised we didn't
actually make it work the way it does on vectors.

> If you want to document the internals, I think the proper

Not the internals, just how 'equal' works.

Pip

Message #17 received at 72802 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 72802 <at> debbugs.gnu.org
Subject: Re: bug#72802: 31.0.50;
 Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 18:39:57 +0300

> Date: Sun, 25 Aug 2024 15:15:14 +0000
> From: Pip Cet <pipcet <at> protonmail.com>
> Cc: 72802 <at> debbugs.gnu.org
> 
> > Not even on master, I think, unless we see a bug related to it that is not
> > caused by a specially-concocted Lisp program or GDB command.
> 
> It's a clear bug, whether or not the Lisp programs that cause it are
> "specially-concocted" (what's that supposed to mean, anyway?  We can't
> just delay fixing what are clearly bugs until they pop up on random
> users' machines!)

We certainly can, and do.

Is there any code out there that compares char-tables and is affected
by this?

> So I think it's important to fix this soon (not "now") on the master
> branch.

I disagree, at least for now, sorry.  char-tables have been stable for
decades, so any change there should ideally be part of some
significant enhancement that justifies the potential destabilization.
Elimination of pure space or some similar change fits the bill.

> > If this is required for the no-pure-space branch, I think you should
> > install this on that branch.  Then it will be merged together with the
> > branch.
> 
> It's not, it just popped up during work on that branch.

Popped up how?

In any case, there's nothing wrong with fixing that as part of a much
larger changeset, which gives us significant gains.

> > I'm not sure we want to pay this cost.  What bothers me is mainly the
> > run-time cost of extracting integers from Lisp objects.
> 
> That might be noticeable on 32-bit machines with EMACS_WIDE_INT, I
> suppose, or on very old machines where memory isn't so much slower than
> register manipulation.
> 
> > char-table is
> > supposed to be very efficient, both memory-wise and CPU-wise, and I
> > think the performance here trumps simplicity.
> 
> How about using an "ordinary" pseudovector with its non-Lisp elements at
> the end?

Not even that, I think.  Some of the char-table are accessed in the
inner-most loops of the display code, and were at the time optimized
especially for that purpose.  I'm not interested in making changes
there for minor simplifications.

> >> BTW, I'm surprised this code returns nil; I think that should be
> >> documented.
> >>
> >> (setq a (make-char-table nil))
> >> (setq b (make-char-table nil))
> >> (aset a 1 nil)
> >> (dotimes (i (max-char))
> >>   (unless (equal (aref a i) (aref b i))
> >>     (error "i = %S" i)))
> >> (equal a b)
> >
> > Why are you surprised?  Setting a single cell of a char-table changes
> > its structure, usually in quite a radical way.  'aref' does some very
> > special things for char-tables; the semantics of accessing an element
> > of a vector is only correct superficially, not in the details.
> 
> Indeed, and I expected (and still expect) 'equal' to ignore such
> details.

No, 'equal' compares components literally.

> > The internals of a char-table are not really documented in the ELisp
> > manual; the description there is mostly phenomenological, without any
> > details.
> 
> I don't think 'equal' behavior is part of those "internals"

Indeed, it isn't.  But if the internals are described in enough
detail, people will be able to understand why 'equal' returns nil in
your case.

> > If you want to document the internals, I think the proper
> 
> Not the internals, just how 'equal' works.

Why is it important?  The doc string of 'equal' already says

  Return t if two Lisp objects have similar structure and contents.

The two char-tables you are comparing have different structure, so
'equal' returns nil.  What else would you like to document there?

Message #20 received at 72802 <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 72802 <at> debbugs.gnu.org
Subject: Re: bug#72802: 31.0.50;
 Crash in (equal sub-char-table-a sub-char-table-b)
Date: Sun, 25 Aug 2024 16:01:11 +0000

"Eli Zaretskii" <eliz <at> gnu.org> writes:

>> So I think it's important to fix this soon (not "now") on the master
>> branch.
>
> I disagree, at least for now, sorry.

Feel free to close this, then.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.