bug#18361: New 'sort' implementation can crash Emacs

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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.

bug#18361: New 'sort' implementation can crash Emacs

[Dmitry Antipov]

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

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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".

bug#18361: New 'sort' implementation can crash Emacs

[Dmitry Antipov]

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

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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.

bug#18361: New 'sort' implementation can crash Emacs

[Dmitry Antipov]

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

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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.

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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

bug#18361: New 'sort' implementation can crash Emacs

[Eli Zaretskii]

> Date: Sat, 30 Aug 2014 16:05:03 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> Cc: Dmitry Antipov <dmantipov@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?

bug#18361: New 'sort' implementation can crash Emacs

[Paul Eggert]

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.

bug#18361: New 'sort' implementation can crash Emacs

[Eli Zaretskii]

> Date: Sat, 30 Aug 2014 21:46:35 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: 18361@debbugs.gnu.org, dmantipov@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