unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
* bug#18361: New 'sort' implementation can crash Emacs
@ 2014-08-29 21:24 Paul Eggert
  2014-08-29 22:47 ` Dmitry Antipov
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-29 21:24 UTC (permalink / raw)
  To: 18361, dmantipov

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.





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-29 21:24 bug#18361: New 'sort' implementation can crash Emacs Paul Eggert
@ 2014-08-29 22:47 ` Dmitry Antipov
  2014-08-29 23:07   ` Paul Eggert
  0 siblings, 1 reply; 11+ messages in thread
From: Dmitry Antipov @ 2014-08-29 22:47 UTC (permalink / raw)
  To: Paul Eggert; +Cc: 18361

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





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-29 22:47 ` Dmitry Antipov
@ 2014-08-29 23:07   ` Paul Eggert
  2014-08-30  5:07     ` Dmitry Antipov
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-29 23:07 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: 18361

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





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-29 23:07   ` Paul Eggert
@ 2014-08-30  5:07     ` Dmitry Antipov
  2014-08-30  5:22       ` Paul Eggert
  0 siblings, 1 reply; 11+ messages in thread
From: Dmitry Antipov @ 2014-08-30  5:07 UTC (permalink / raw)
  To: Paul Eggert; +Cc: 18361

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






^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-30  5:07     ` Dmitry Antipov
@ 2014-08-30  5:22       ` Paul Eggert
  2014-08-30  6:55         ` Dmitry Antipov
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-30  5:22 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: 18361

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.





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-30  5:22       ` Paul Eggert
@ 2014-08-30  6:55         ` Dmitry Antipov
  2014-08-30 13:44           ` Paul Eggert
  0 siblings, 1 reply; 11+ messages in thread
From: Dmitry Antipov @ 2014-08-30  6:55 UTC (permalink / raw)
  To: Paul Eggert; +Cc: 18361

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






^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-30  6:55         ` Dmitry Antipov
@ 2014-08-30 13:44           ` Paul Eggert
  2014-08-30 23:05             ` Paul Eggert
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-30 13:44 UTC (permalink / raw)
  To: Dmitry Antipov; +Cc: 18361

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.





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-30 13:44           ` Paul Eggert
@ 2014-08-30 23:05             ` Paul Eggert
  2014-08-31  2:50               ` Eli Zaretskii
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-30 23:05 UTC (permalink / raw)
  To: 18361; +Cc: Dmitry Antipov

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





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-30 23:05             ` Paul Eggert
@ 2014-08-31  2:50               ` Eli Zaretskii
  2014-08-31  4:46                 ` Paul Eggert
  0 siblings, 1 reply; 11+ messages in thread
From: Eli Zaretskii @ 2014-08-31  2:50 UTC (permalink / raw)
  To: Paul Eggert; +Cc: dmantipov, 18361

> 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?





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-31  2:50               ` Eli Zaretskii
@ 2014-08-31  4:46                 ` Paul Eggert
  2014-08-31 15:20                   ` Eli Zaretskii
  0 siblings, 1 reply; 11+ messages in thread
From: Paul Eggert @ 2014-08-31  4:46 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: dmantipov, 18361

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.





^ permalink raw reply	[flat|nested] 11+ messages in thread

* bug#18361: New 'sort' implementation can crash Emacs
  2014-08-31  4:46                 ` Paul Eggert
@ 2014-08-31 15:20                   ` Eli Zaretskii
  0 siblings, 0 replies; 11+ messages in thread
From: Eli Zaretskii @ 2014-08-31 15:20 UTC (permalink / raw)
  To: Paul Eggert; +Cc: dmantipov, 18361

> 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






^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2014-08-31 15:20 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-08-29 21:24 bug#18361: New 'sort' implementation can crash Emacs Paul Eggert
2014-08-29 22:47 ` Dmitry Antipov
2014-08-29 23:07   ` Paul Eggert
2014-08-30  5:07     ` Dmitry Antipov
2014-08-30  5:22       ` Paul Eggert
2014-08-30  6:55         ` Dmitry Antipov
2014-08-30 13:44           ` Paul Eggert
2014-08-30 23:05             ` Paul Eggert
2014-08-31  2:50               ` Eli Zaretskii
2014-08-31  4:46                 ` Paul Eggert
2014-08-31 15:20                   ` Eli Zaretskii

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).