GNU bug report logs - #18361
New 'sort' implementation can crash Emacs

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 18361 in the body.
You can then email your comments to 18361 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: Paul Eggert <eggert <at> cs.ucla.edu>
To: bug-emacs <bug-gnu-emacs <at> gnu.org>, 
 Dmitry Antipov <dmantipov <at> yandex.ru>
Subject: New 'sort' implementation can crash Emacs
Date: Fri, 29 Aug 2014 14:24:53 -0700

The new implementation of 'sort' in the trunk invokes qsort (or 
qsort_r), but these functions have undefined behavior if the comparison 
function is ill-behaved.  Since the comparison predicate is 
user-defined, this means a bad user-supplied comparison function could 
crash Emacs.

One possible fix would be to build on the proposed patch in Bug#18360, 
except to change Emacs to always define its own qsort_r substitute, one 
that is known to produce some permutation of the input without crashing 
even if the comparison function is ill-behaved.

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

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 02:47:01 +0400

On 08/30/2014 01:24 AM, Paul Eggert wrote:

> The new implementation of 'sort' in the trunk invokes qsort (or qsort_r),
> but these functions have undefined behavior if the comparison function is
> ill-behaved.  Since the comparison predicate is user-defined, this means
> a bad user-supplied comparison function could crash Emacs.

I don't see how is that possible if we operate on a correctly initialized
vector and sort_vector_predicate is a valid function accepting 2 arguments.
Can you provide an example?  Is that just a poor property of the particular
qsort(_r) implementation?

Dmitry

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Fri, 29 Aug 2014 16:07:09 -0700

Dmitry Antipov wrote:
> Can you provide an example?

Sure, a comparison function that returns a new random value every time 
you call it.  Such a function is most likely not well formed, that is, 
it most likely does not define a total order.

> Is that just a poor property of the particular qsort(_r) implementation?

Yes and no.  qsort is allowed to have undefined behavior (what you're 
calling a "poor property") if given a comparison function that is not a 
total order; see 
<http://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html> 
DESCRIPTION paragraph 4.  Perhaps some qsort implementations have well 
defined behavior in this case (and so don't have the "poor property"), 
but there are performance reasons for qsort to have the "poor property" 
and in my experience most implementations have it.  GNU qsort and 
qsort_r, for example, have the "poor property".

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

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 09:07:46 +0400

On 08/30/2014 03:07 AM, Paul Eggert wrote:

> Sure, a comparison function that returns a new random value every
> time you call it.  Such a function is most likely not well formed
> that is, it most likely does not define a total order.

If an undefined behavior doesn't cause crash, I don't see a problem
if this is well-documented (probably in lispref).

I gave this function a solid run on GNU/Linux (glibc 2.18) and FreeBSD
10.0, and was unable to crash:

(defun sort-run ()
  (interactive)
  (let* ((max 1000000)
         (size 1000)
         (p (make-progress-reporter "Sorted: " 0 max)))
    (dotimes (loops max)
      (let ((v (make-vector size 0)))
        (dotimes (i size) (aset v i (% (random) (* size 2))))
        (sort v (lambda (x y) (random)))
        (progress-reporter-update p loops)))
    (progress-reporter-done p)))

I don't have any reasons to not trust in your experience, but I'm
really curious to look at the real example crashing qsort(_r) due
to ill-formed comparison function.

Dmitry

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Fri, 29 Aug 2014 22:22:48 -0700

Dmitry Antipov wrote:
>
> If an undefined behavior doesn't cause crash,

Unfortunately undefined behavior in qsort can cause a crash (or an 
infinite loop, etc., etc.).  It's platform-dependent, and on many 
platforms the problem happens only in unusual cases, so I'm not 
surprised your tests didn't find it.  But it definitely can happen. 
See, for example,

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42157

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51297

These crash reports are for Solaris qsort, but today I found similar 
issues in the latest glibc qsort by code inspection (e.g., the path 
qsort takes when memory is low).  These issues are not qsort bugs, since 
the qsort spec requires a total-order comparison function.  It's a bug 
in the Emacs trunk.

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

From: Dmitry Antipov <dmantipov <at> yandex.ru>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 10:55:17 +0400

On 08/30/2014 09:22 AM, Paul Eggert wrote:

> See, for example,
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42157
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51297

Very nice.  But couldn't we detect an improper comparison
function at runtime?  For example:

=== modified file 'src/fns.c'
--- src/fns.c   2014-08-29 19:18:06 +0000
+++ src/fns.c   2014-08-30 06:52:20 +0000
@@ -1933,6 +1933,8 @@
      preserve original order.  Pretty ugly but works.  */
   more = NILP (call2 (sort_vector_predicate, vp, vq));
   less = NILP (call2 (sort_vector_predicate, vq, vp));
+  if (!more && !less)
+    error ("Not an anti-symmetrical predicate in sort");
   return ((more && !less) ? 1
          : ((!more && less) ? -1
             : XSAVE_INTEGER (op, 0) - XSAVE_INTEGER (oq, 0)));

Dmitry

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 06:44:54 -0700

Dmitry Antipov wrote:

> couldn't we detect an improper comparison
> function at runtime?

Not easily, because it doesn't suffice to check whether the function is 
antisymmetrical at each comparison (a local property).  One must check 
whether the function defines a total order (a global property).  One way 
to do such a check is to sort the array, and then compare all pairs to 
verify that the function is indeed a total order.  But of course that 
begs the question of sorting the array, plus it's an O(N**2) check, so 
it's not practical.

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: 18361 <at> debbugs.gnu.org
Cc: Dmitry Antipov <dmantipov <at> yandex.ru>
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 16:05:03 -0700

I installed what I hope is a fix for this bug as trunk bzr 117784; 
please give it a look.

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: dmantipov <at> yandex.ru, 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sun, 31 Aug 2014 05:50:53 +0300

> Date: Sat, 30 Aug 2014 16:05:03 -0700
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Cc: Dmitry Antipov <dmantipov <at> yandex.ru>
> 
> I installed what I hope is a fix for this bug as trunk bzr 117784; 
> please give it a look.

Thanks.

There's something I don't understand in that changeset: why are we
importing the qsort_r module from gnulib, but then don't use anywhere?
What am I missing?

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: dmantipov <at> yandex.ru, 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 21:46:35 -0700

Eli Zaretskii wrote:
> why are we importing the qsort_r module from gnulib

We're not.  Emacs is merely importing gnulib's stdlib module, which now 
has placeholders (unused by Emacs) for qsort_r, just as it has 
placeholders for all GNU functions it might define.

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: dmantipov <at> yandex.ru, 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sun, 31 Aug 2014 18:20:18 +0300

> Date: Sat, 30 Aug 2014 21:46:35 -0700
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> CC: 18361 <at> debbugs.gnu.org, dmantipov <at> yandex.ru
> 
> Eli Zaretskii wrote:
> > why are we importing the qsort_r module from gnulib
> 
> We're not.  Emacs is merely importing gnulib's stdlib module, which now 
> has placeholders (unused by Emacs) for qsort_r, just as it has 
> placeholders for all GNU functions it might define.

OK, thanks.  I guess what fooled me was this part of the commit
message:

  Sync from gnulib, incorporating:
  2014-08-29 qsort_r: new module, for GNU-style qsort_r

Previous Next

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