From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Jim Meyering Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 14:50:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 9612@debbugs.gnu.org X-Debbugs-Original-To: bug-coreutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.13171349952497 (code B ref -1); Tue, 27 Sep 2011 14:50:02 +0000 Received: (at submit) by debbugs.gnu.org; 27 Sep 2011 14:49:55 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8Yyp-0000eD-1B for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:55 -0400 Received: from eggs.gnu.org ([140.186.70.92]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8Yyl-0000e4-2I for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:53 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8Yxs-00072D-3B for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:01 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from lists.gnu.org ([140.186.70.17]:56636) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxs-000729-1a for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:48:56 -0400 Received: from eggs.gnu.org ([140.186.70.92]:40487) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxq-0005r0-Bp for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:55 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8Yxj-00070t-FJ for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:54 -0400 Received: from mx.meyering.net ([88.168.87.75]:50547) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxi-00070e-Ue for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:47 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 4B2D0600D1 for ; Tue, 27 Sep 2011 16:48:45 +0200 (CEST) From: Jim Meyering Date: Tue, 27 Sep 2011 16:48:45 +0200 Message-ID: <878vpa6nxu.fsf@rho.meyering.net> Lines: 324 MIME-Version: 1.0 Content-Type: text/plain X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 140.186.70.17 X-Spam-Score: -4.9 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -5.1 (-----) This was reported by Aaron Denney in http://bugs.debian.org/642557. Who would have thought that including a few NaNs in the input to sort would make it infloop. The original failure arose only when sort was reading from a pipe: yes -- -nan | head -156903 | sort -g > /dev/null But it's not always easy to reproduce. For example, on a uni-core Debian unstable amd64 system, the bug strikes every time with the distro-supplied binary, but not at all on a fedora rawhide-supplied binary in a multi-core VM. However, when I compile coreutils-8.13 myself on that same rawhide system, *that* sort fails every time. Setting up to debug was a little tricky. In order to invoke sort-reading-from-pipe from gdb, I had to use a fifo: mkfifo sort-test-pipe yes -- -nan | head -156903 | sort-test-pipe & Then, with gdb, you can do this: gdb sort run -g < sort-test-pipe Debugging it, I was surprised to see the infinite loop iterating through these "*"-marked lines, with nfiles == 2 and always resetting i = 0: (gdb) l 2893 Since this only reorders two items if one is strictly greater than 2894 the other, it is stable. */ 2895 for (i = 0; i < nfiles; ++i) 2896 ord[i] = i; * 2897 for (i = 1; i < nfiles; ++i) * 2898 if (0 < compare (cur[ord[i - 1]], cur[ord[i]])) * 2899 t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0; 2900 2901 /* Repeatedly output the smallest line until no input remains. */ 2902 while (nfiles) (gdb) p ord[i-1] $6 = 0 (gdb) p ord[i] $7 = 1 (gdb) p compare (cur[0], cur[1]) $8 = 64 (gdb) p compare (cur[1], cur[0]) $9 = 64 That shows cur[0] > cur[1], and then, on the very next line a contradiction, cur[1] > cur[0] But it's not the classic NaN problem at all. That would be too easy ;-) That code already handles NaNs (via the general_numcompare function), detecting the unusual case and comparing NaNs with memcmp. Here's most of the general_numcompare function: static int general_numcompare (char const *sa, char const *sb) { char *ea; char *eb; long_double a = strtold (sa, &ea); long_double b = strtold (sb, &eb); ... /* Sort numbers in the usual way, where -0 == +0. Put NaNs after conversion errors but before numbers; sort them by internal bit-pattern, for lack of a more portable alternative. */ return (a < b ? -1 : a > b ? 1 : a == b ? 0 : b == b ? -1 : a == a ? 1 : memcmp (&a, &b, sizeof a)); } What could cause such bogosity? Here's the quick answer: The statement "long double x = NAN;" (inside glibc's strtold) leaves many bits of "x" uninitialized. For most uses of a NaN, that doesn't matter, but here, since we're actually trying to order the different NaNs, it makes all of the difference. [ I'm about to file the glibc bug -- or maybe it's a bug in the definition of gcc's __builtin_nan. Haven't looked yet. ] What happens when we infloop is that the surrounding code always happens to ensure that differing bits are 0x40 in the left operand and 0x00 in the right operand to memcmp. Then you will see precisely the above behavior. One "fix" is to return 0 rather than bothering with the memcmp call above, thus treating all NaNs as equal, rather than attempting to order them based on their internal bit patterns. But that is undesirable since it would render sort's output indeterminate whenever it contains different types of NaN values. E.g., NaN, NaN(1), NaN(2), etc. all result in different bit patterns. For example, currently, this works as you'd expect on a system with a NaN(...)-aware strtold, like anything glibc-based: $ for i in $(seq 9); do echo "NaN($i)";done|sort -gr NaN(9) NaN(8) NaN(7) NaN(6) NaN(5) NaN(4) NaN(3) NaN(2) NaN(1) If we were to remove the memcmp, those would not be sorted. ---------------------------------------- A kludgey fix that serves to demonstrate the problem would be to replace the two strtold invocations with these: long_double a = 0; a = strtold (sa, &ea); long_double b = 0; b = strtold (sb, &eb); That does the job at least when compiling with gcc -ggdb3, but minimal optimization could well eliminate the dead stores. ---------------------------------------- The real solution is to change glibc's strtold so that its "long double" result contains no uninitialized bit. In the shorter term, I'd like a gnulib strtold module that works around the problem. However, gnulib's strtod.c simply ignores the digits in NaN(DDDDD), while glibc's implementation actually uses them. That should be easy to fix, right? Just merge in the glibc changes? But no, they rely on ieee754.h's "union ieee854_long_double", and that is not portable. So I have resorted to an even shorter-term work-around in the patch below. =-================================= Consequences: whenever qsort's comparison function "lies" (i.e., returns 1 for a < b, -1 for a > b, or 0 for a != b, qsort's behavior is undefined (i.e., it may well segfault). GNU sort(1) uses qsort only incidentally, to sort month names, and nowhere else, but now, you've seen that sort(1) had a similar problem when its comparison function is inconsistent. -------------------------------------------------- BTW, once I found the problem code, I realized I could provoke the infloop with two one-line inputs using sort's --merge option: echo nan > 1; sort -m -g 1 1 -------------------------------- Here's a little program to demonstrate the problem. Note how the results differ with compilation options: #include #include static char * fmt_nan (long double x) { unsigned int i; static char buf[33]; unsigned char const *p = (unsigned char const *) &x; for (i = 0; i < sizeof x; i++) sprintf (buf + 2*i, "%02x", *p++); return buf; } int main () { const char *q = "nan"; long double x = strtold (q, NULL); printf ("%s\n", fmt_nan (x)); x = 0; x = strtold (q, NULL); printf ("%s\n", fmt_nan (x)); return 0; } $ gcc -O0 -Wall -Wextra -W /t/strtold-bogosity.c && ./a.out 00000000000000c0ff7f400000000000 00000000000000c0ff7f000000000000 $ gcc -O1 -Wall -Wextra -W /t/strtold-bogosity.c && ./a.out 00000000000000c0ff7f000000000000 00000000000000c0ff7f000000000000 ------------------------------------------------------- And here's the patch I expect to apply for now: >From 17f70721d10f02543ae9e2d4e2c4b2babe0206a7 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Tue, 27 Sep 2011 16:32:35 +0200 Subject: [PATCH] sort: avoid a NaN-induced infloop These commands would fail to terminate: yes -- -nan | head -156903 | sort -g > /dev/null echo nan > F; sort -m -g F F That can happen with any strtold implementation that includes uninitialized data in its return value. The problem arises in the mergefps function when bubble-sorting the two or more lines, each from one of the input streams being merged: compare(a,b) returns 64, yet compare(b,a) also returns a positive value. With a broken comparison function like that, the bubble sort never terminates. Why do the long-double bit strings corresponding to two identical "nan" strings not compare equal? Because some parts of the result are uninitialized and thus depend on the state of the stack. For more details, see http://bugs.gnu.org/FIXME. * src/sort.c (nan_compare): New function. (general_numcompare): Use it rather than bare memcmp. Reported by Aaron Denney in http://bugs.debian.org/642557. * NEWS (Bug fixes): Mention it. * tests/misc/sort-NaN-infloop: New file. * tests/Makefile.am (TESTS): Add it. --- NEWS | 4 ++++ src/sort.c | 20 +++++++++++++++++++- tests/Makefile.am | 1 + tests/misc/sort-NaN-infloop | 28 ++++++++++++++++++++++++++++ 4 files changed, 52 insertions(+), 1 deletions(-) create mode 100755 tests/misc/sort-NaN-infloop diff --git a/NEWS b/NEWS index 140e6fa..f05a088 100644 --- a/NEWS +++ b/NEWS @@ -2,6 +2,10 @@ GNU coreutils NEWS -*- outline -*- * Noteworthy changes in release ?.? (????-??-??) [?] +** Bug fixes + + sort -g no longer infloops for certain inputs containing NaNs + ** Improvements md5sum --check now supports the -r format from the corresponding BSD tool. diff --git a/src/sort.c b/src/sort.c index 3d3119d..3e94a6e 100644 --- a/src/sort.c +++ b/src/sort.c @@ -1910,6 +1910,24 @@ numcompare (char const *a, char const *b) return strnumcmp (a, b, decimal_point, thousands_sep); } +/* Work around a problem whereby the long double value returned by glibc's + strtold ("NaN", ...) contains uninitialized bits: clear all bytes of + A and B before calling strtold. FIXME: remove this function once + gnulib guarantees that strtold's result is always well defined. */ +static int +nan_compare (char const *sa, char const *sb) +{ + long_double a; + memset (&a, 0, sizeof a); + a = strtold (sa, NULL); + + long_double b; + memset (&b, 0, sizeof b); + b = strtold (sb, NULL); + + return memcmp (&a, &b, sizeof a); +} + static int general_numcompare (char const *sa, char const *sb) { @@ -1935,7 +1953,7 @@ general_numcompare (char const *sa, char const *sb) : a == b ? 0 : b == b ? -1 : a == a ? 1 - : memcmp (&a, &b, sizeof a)); + : nan_compare (sa, sb)); } /* Return an integer in 1..12 of the month name MONTH. diff --git a/tests/Makefile.am b/tests/Makefile.am index eeb4cab..2cf409a 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -250,6 +250,7 @@ TESTS = \ misc/sort-unique \ misc/sort-unique-segv \ misc/sort-version \ + misc/sort-NaN-infloop \ split/filter \ split/suffix-length \ split/b-chunk \ diff --git a/tests/misc/sort-NaN-infloop b/tests/misc/sort-NaN-infloop new file mode 100755 index 0000000..ead871e --- /dev/null +++ b/tests/misc/sort-NaN-infloop @@ -0,0 +1,28 @@ +#!/bin/sh +# exercise the NaN-infloop bug in coreutils-8.13 + +# Copyright (C) 2011 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +. "${srcdir=.}/init.sh"; path_prepend_ ../src +print_ver_ sort + +echo nan > F || fail=1 +printf 'nan\nnan\n' > exp || fail=1 +timeout 10 sort -g -m F F > out || fail=1 + +compare out exp || fail=1 + +Exit $fail -- 1.7.7.rc0.362.g5a14 From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Andreas Schwab Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 17:15:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Jim Meyering Cc: 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.131714365715485 (code B ref 9612); Tue, 27 Sep 2011 17:15:01 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 17:14:17 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8bEW-00041h-Tz for submit@debbugs.gnu.org; Tue, 27 Sep 2011 13:14:17 -0400 Received: from mail-out.m-online.net ([212.18.0.9]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8bEU-00041Z-3A for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 13:14:15 -0400 Received: from frontend1.mail.m-online.net (unknown [192.168.8.180]) by mail-out.m-online.net (Postfix) with ESMTP id 7D6C41C0F563; Tue, 27 Sep 2011 19:13:22 +0200 (CEST) Received: from localhost (dynscan1.mnet-online.de [192.168.8.164]) by mail.m-online.net (Postfix) with ESMTP id 560011C001E8; Tue, 27 Sep 2011 19:13:22 +0200 (CEST) X-Virus-Scanned: amavisd-new at mnet-online.de Received: from mail.mnet-online.de ([192.168.8.180]) by localhost (dynscan1.mail.m-online.net [192.168.8.164]) (amavisd-new, port 10024) with ESMTP id 9KRvRL1cGTnW; Tue, 27 Sep 2011 19:13:21 +0200 (CEST) Received: from igel.home (ppp-88-217-107-205.dynamic.mnet-online.de [88.217.107.205]) by mail.mnet-online.de (Postfix) with ESMTP; Tue, 27 Sep 2011 19:13:21 +0200 (CEST) Received: by igel.home (Postfix, from userid 501) id 2C37ECA296; Tue, 27 Sep 2011 19:13:21 +0200 (CEST) From: Andreas Schwab References: <878vpa6nxu.fsf@rho.meyering.net> X-Yow: Hmmm.. a CRIPPLED ACCOUNTANT with a FALAFEL sandwich is HIT by a TROLLEY-CAR.. Date: Tue, 27 Sep 2011 19:13:20 +0200 In-Reply-To: <878vpa6nxu.fsf@rho.meyering.net> (Jim Meyering's message of "Tue, 27 Sep 2011 16:48:45 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.90 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -2.6 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) Jim Meyering writes: > The statement "long double x = NAN;" (inside glibc's strtold) leaves many > bits of "x" uninitialized. You are looking at padding bits, which have unspecified contents. 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." From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Jim Meyering Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 17:26:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Andreas Schwab Cc: 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.131714432116484 (code B ref 9612); Tue, 27 Sep 2011 17:26:03 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 17:25:21 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8bPD-0004Hj-VR for submit@debbugs.gnu.org; Tue, 27 Sep 2011 13:25:21 -0400 Received: from mx.meyering.net ([88.168.87.75]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8bPA-0004Ha-TN for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 13:25:18 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id B1CCF60097; Tue, 27 Sep 2011 19:24:25 +0200 (CEST) From: Jim Meyering In-Reply-To: (Andreas Schwab's message of "Tue, 27 Sep 2011 19:13:20 +0200") References: <878vpa6nxu.fsf@rho.meyering.net> Date: Tue, 27 Sep 2011 19:24:25 +0200 Message-ID: <87k48t525y.fsf@rho.meyering.net> Lines: 14 MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -3.2 (---) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.1 (---) Andreas Schwab wrote: > Jim Meyering writes: > >> The statement "long double x = NAN;" (inside glibc's strtold) leaves many >> bits of "x" uninitialized. > > You are looking at padding bits, which have unspecified contents. I realize that they are unspecified. That is why I did not claim that this is a POSIX violation. POSIX says little about what strtold must do for a "NaN" string. However, I am dismayed that with glibc's strtold the values of those bits is not deterministic. That makes sorting NaN values obtained from strtold unnecessarily hard. From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Andreas Schwab Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 20:09:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Jim Meyering Cc: 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.13171541294883 (code B ref 9612); Tue, 27 Sep 2011 20:09:01 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 20:08:49 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8dxQ-0001Gi-On for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:08:48 -0400 Received: from mail-out.m-online.net ([212.18.0.9]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8dxO-0001Ga-E0 for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 16:08:47 -0400 Received: from frontend1.mail.m-online.net (unknown [192.168.8.180]) by mail-out.m-online.net (Postfix) with ESMTP id 05AAE1C02F85; Tue, 27 Sep 2011 22:07:53 +0200 (CEST) Received: from localhost (dynscan1.mnet-online.de [192.168.8.164]) by mail.m-online.net (Postfix) with ESMTP id E752A1C0009B; Tue, 27 Sep 2011 22:07:53 +0200 (CEST) X-Virus-Scanned: amavisd-new at mnet-online.de Received: from mail.mnet-online.de ([192.168.8.180]) by localhost (dynscan1.mail.m-online.net [192.168.8.164]) (amavisd-new, port 10024) with ESMTP id kIRpOuBvxnPT; Tue, 27 Sep 2011 22:07:52 +0200 (CEST) Received: from igel.home (ppp-88-217-107-205.dynamic.mnet-online.de [88.217.107.205]) by mail.mnet-online.de (Postfix) with ESMTP; Tue, 27 Sep 2011 22:07:52 +0200 (CEST) Received: by igel.home (Postfix, from userid 501) id 6BF52CA296; Tue, 27 Sep 2011 22:07:52 +0200 (CEST) From: Andreas Schwab References: <878vpa6nxu.fsf@rho.meyering.net> <87k48t525y.fsf@rho.meyering.net> X-Yow: Did you GAIN WEIGHT in th' past 5 MINUTES or am I just DREAMING of two BROCCOLI FLORETS lying in an empty GAS TANK? Date: Tue, 27 Sep 2011 22:07:52 +0200 In-Reply-To: <87k48t525y.fsf@rho.meyering.net> (Jim Meyering's message of "Tue, 27 Sep 2011 19:24:25 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.90 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -2.6 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) Jim Meyering writes: > However, I am dismayed that with glibc's strtold the values of those bits > is not deterministic. Padding bits can change any time. 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." From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Paul Eggert Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 20:13:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Andreas Schwab Cc: Jim Meyering , 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.13171543495246 (code B ref 9612); Tue, 27 Sep 2011 20:13:01 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 20:12:29 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8e0y-0001MY-Jf for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:12:29 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8e0v-0001MQ-Fh for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 16:12:26 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id E090739E80F7; Tue, 27 Sep 2011 13:11:33 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5HmbWGFWES64; Tue, 27 Sep 2011 13:11:33 -0700 (PDT) Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 8B51A39E80F2; Tue, 27 Sep 2011 13:11:33 -0700 (PDT) Message-ID: <4E822DF5.3010502@cs.ucla.edu> Date: Tue, 27 Sep 2011 13:11:33 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.22) Gecko/20110906 Fedora/3.1.14-1.fc14 Thunderbird/3.1.14 MIME-Version: 1.0 References: <878vpa6nxu.fsf@rho.meyering.net> <87k48t525y.fsf@rho.meyering.net> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -3.1 (---) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.1 (---) On 09/27/11 13:07, Andreas Schwab wrote: > Padding bits can change any time. Is there any way to compare the non-padding parts of long doubles? There ought to be *some* way to get the fractional part of a NaN, no? For example, with glibc, is there some way to sprintf to a buffer and get the fraction out of the text in the buffer? From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Jim Meyering Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 20:34:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Paul Eggert Cc: Andreas Schwab , 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.13171556317161 (code B ref 9612); Tue, 27 Sep 2011 20:34:02 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 20:33:51 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8eLd-0001rR-U8 for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:33:50 -0400 Received: from mx.meyering.net ([88.168.87.75]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8eLa-0001rH-Ic for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 16:33:47 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 241D8600A1; Tue, 27 Sep 2011 22:32:54 +0200 (CEST) From: Jim Meyering In-Reply-To: <4E822DF5.3010502@cs.ucla.edu> (Paul Eggert's message of "Tue, 27 Sep 2011 13:11:33 -0700") References: <878vpa6nxu.fsf@rho.meyering.net> <87k48t525y.fsf@rho.meyering.net> <4E822DF5.3010502@cs.ucla.edu> Date: Tue, 27 Sep 2011 22:32:54 +0200 Message-ID: <8739fh4tft.fsf@rho.meyering.net> Lines: 57 MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -3.1 (---) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.1 (---) Paul Eggert wrote: > On 09/27/11 13:07, Andreas Schwab wrote: >> Padding bits can change any time. > > Is there any way to compare the non-padding parts of long doubles? > There ought to be *some* way to get the fractional part of a NaN, no? > For example, with glibc, is there some way to sprintf to a buffer > and get the fraction out of the text in the buffer? Good idea. Since the problem may be glibc-specific the work-around can be, too. /usr/include/ieee754.h defines this: union ieee854_long_double { long double d; /* This is the IEEE 854 double-extended-precision format. */ struct { #if __BYTE_ORDER == __BIG_ENDIAN unsigned int negative:1; unsigned int exponent:15; unsigned int empty:16; unsigned int mantissa0:32; unsigned int mantissa1:32; #endif #if __BYTE_ORDER == __LITTLE_ENDIAN # if __FLOAT_WORD_ORDER == __BIG_ENDIAN unsigned int exponent:15; unsigned int negative:1; unsigned int empty:16; unsigned int mantissa0:32; unsigned int mantissa1:32; # else unsigned int mantissa1:32; unsigned int mantissa0:32; unsigned int exponent:15; unsigned int negative:1; unsigned int empty:16; # endif #endif } ieee; ... I went ahead and committed my expedient patch, with adjusted URL in the log. I'm sure we'll get something better, though... BTW, this was introduced between 8.5 and 8.6, and I'll update NEWS with that. While I haven't found the specific commit, it's probably for this feature: * Noteworthy changes in release 8.6 (2010-10-15) [stable] sort -g now uses long doubles for greater range and precision. From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: John Reiser Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 20:54:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 9612@debbugs.gnu.org X-Debbugs-Original-To: bug-coreutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.131715682311875 (code B ref -1); Tue, 27 Sep 2011 20:54:02 +0000 Received: (at submit) by debbugs.gnu.org; 27 Sep 2011 20:53:43 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8ees-00035S-JH for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:53:43 -0400 Received: from eggs.gnu.org ([140.186.70.92]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8eeq-00035J-VS for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:53:41 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8ee1-0004i4-8c for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:52:50 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from lists.gnu.org ([140.186.70.17]:57231) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8ee1-0004i0-6e for submit@debbugs.gnu.org; Tue, 27 Sep 2011 16:52:49 -0400 Received: from eggs.gnu.org ([140.186.70.92]:50168) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8ee0-0001rk-5j for bug-coreutils@gnu.org; Tue, 27 Sep 2011 16:52:49 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8edz-0004ho-6O for bug-coreutils@gnu.org; Tue, 27 Sep 2011 16:52:48 -0400 Received: from bitwagon.com ([74.82.39.175]:58091) by eggs.gnu.org with smtp (Exim 4.71) (envelope-from ) id 1R8edy-0004hf-Ro for bug-coreutils@gnu.org; Tue, 27 Sep 2011 16:52:47 -0400 Received: from f14-64.local ([76.105.149.67]) by bitwagon.com for ; Tue, 27 Sep 2011 13:52:45 -0700 Message-ID: <4E82380E.5050004@bitwagon.com> Date: Tue, 27 Sep 2011 13:54:38 -0700 From: John Reiser Organization: - User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.22) Gecko/20110906 Fedora/3.1.14-1.fc14 Thunderbird/3.1.14 MIME-Version: 1.0 References: <878vpa6nxu.fsf@rho.meyering.net> <87k48t525y.fsf@rho.meyering.net> <4E822DF5.3010502@cs.ucla.edu> In-Reply-To: <4E822DF5.3010502@cs.ucla.edu> X-Enigmail-Version: 1.1.2 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 140.186.70.17 X-Spam-Score: -6.6 (------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -6.6 (------) > Is there any way to compare the non-padding parts of long doubles? > There ought to be *some* way to get the fractional part of a NaN, no? frexp() [man 3 frexp] would be the right idea, except that it fails explicitly for NaN. -- From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Andreas Schwab Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 27 Sep 2011 21:43:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Paul Eggert Cc: Jim Meyering , 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.131715972416169 (code B ref 9612); Tue, 27 Sep 2011 21:43:02 +0000 Received: (at 9612) by debbugs.gnu.org; 27 Sep 2011 21:42:04 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8fPf-0004Ck-Cr for submit@debbugs.gnu.org; Tue, 27 Sep 2011 17:42:03 -0400 Received: from mail-out.m-online.net ([212.18.0.10]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8fPd-0004CI-4O for 9612@debbugs.gnu.org; Tue, 27 Sep 2011 17:42:02 -0400 Received: from frontend1.mail.m-online.net (frontend1.mail.intern.m-online.net [192.168.8.180]) by mail-out.m-online.net (Postfix) with ESMTP id C8345186DED8; Tue, 27 Sep 2011 23:41:06 +0200 (CEST) Received: from localhost (dynscan1.mnet-online.de [192.168.8.164]) by mail.m-online.net (Postfix) with ESMTP id 0D39F1C000AC; Tue, 27 Sep 2011 23:41:07 +0200 (CEST) X-Virus-Scanned: amavisd-new at mnet-online.de Received: from mail.mnet-online.de ([192.168.8.180]) by localhost (dynscan1.mail.m-online.net [192.168.8.164]) (amavisd-new, port 10024) with ESMTP id ZeXJZUJBB0Hy; Tue, 27 Sep 2011 23:41:06 +0200 (CEST) Received: from igel.home (ppp-88-217-107-205.dynamic.mnet-online.de [88.217.107.205]) by mail.mnet-online.de (Postfix) with ESMTP; Tue, 27 Sep 2011 23:41:05 +0200 (CEST) Received: by igel.home (Postfix, from userid 501) id 5057DCA296; Tue, 27 Sep 2011 23:41:05 +0200 (CEST) From: Andreas Schwab References: <878vpa6nxu.fsf@rho.meyering.net> <87k48t525y.fsf@rho.meyering.net> <4E822DF5.3010502@cs.ucla.edu> X-Yow: I'm a GENIUS! I want to dispute sentence structure with SUSAN SONTAG!! Date: Tue, 27 Sep 2011 23:41:05 +0200 In-Reply-To: <4E822DF5.3010502@cs.ucla.edu> (Paul Eggert's message of "Tue, 27 Sep 2011 13:11:33 -0700") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.90 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -2.6 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) Paul Eggert writes: > On 09/27/11 13:07, Andreas Schwab wrote: >> Padding bits can change any time. > > Is there any way to compare the non-padding parts of long doubles? By ignoring the padding. > There ought to be *some* way to get the fractional part of a NaN, no? You need to inspect the bytes of the representation yourself. 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." From unknown Tue Jun 17 01:33:59 2025 X-Loop: help-debbugs@gnu.org Subject: bug#9612: sort: avoid a NaN-induced infloop Resent-From: Jim Meyering Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Sat, 01 Oct 2011 17:44:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 9612 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 9612@debbugs.gnu.org Received: via spool by 9612-submit@debbugs.gnu.org id=B9612.131749099114242 (code B ref 9612); Sat, 01 Oct 2011 17:44:02 +0000 Received: (at 9612) by debbugs.gnu.org; 1 Oct 2011 17:43:11 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1RA3ah-0003hf-32 for submit@debbugs.gnu.org; Sat, 01 Oct 2011 13:43:11 -0400 Received: from mx.meyering.net ([88.168.87.75]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1RA3ad-0003hV-VB for 9612@debbugs.gnu.org; Sat, 01 Oct 2011 13:43:09 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 9B1E46002D for <9612@debbugs.gnu.org>; Sat, 1 Oct 2011 19:41:53 +0200 (CEST) From: Jim Meyering In-Reply-To: <878vpa6nxu.fsf@rho.meyering.net> (Jim Meyering's message of "Tue, 27 Sep 2011 16:48:45 +0200") References: <878vpa6nxu.fsf@rho.meyering.net> Date: Sat, 01 Oct 2011 19:41:53 +0200 Message-ID: <874nzswqvy.fsf@rho.meyering.net> Lines: 17 MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -3.0 (---) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.9 (--) Jim Meyering wrote: > Who would have thought that including a few NaNs in the input to sort > would make it infloop. > > The original failure arose only when sort was reading from a pipe: > > yes -- -nan | head -156903 | sort -g > /dev/null > > But it's not always easy to reproduce. ... > [ I'm about to file the glibc bug ... I've done that: RFE: strtold: do not include uninitialized bytes when converting "NaN" http://sourceware.org/bugzilla/show_bug.cgi?id=13246 From unknown Tue Jun 17 01:33:59 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.427 (Entity 5.427) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Jim Meyering Subject: bug#9612: closed (Re: bug#9612: sort: avoid a NaN-induced infloop) Message-ID: References: <87k48iyxqe.fsf@rho.meyering.net> <878vpa6nxu.fsf@rho.meyering.net> X-Gnu-PR-Message: they-closed 9612 X-Gnu-PR-Package: coreutils Reply-To: 9612@debbugs.gnu.org Date: Thu, 06 Oct 2011 14:58:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1317913082-9935-1" This is a multi-part message in MIME format... ------------=_1317913082-9935-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #9612: sort: avoid a NaN-induced infloop which was filed against the coreutils package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 9612@debbugs.gnu.org. --=20 9612: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D9612 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1317913082-9935-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 9612-done) by debbugs.gnu.org; 6 Oct 2011 14:57:12 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1RBpNn-0002ZH-Es for submit@debbugs.gnu.org; Thu, 06 Oct 2011 10:57:12 -0400 Received: from mx.meyering.net ([88.168.87.75]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1RBpNk-0002Z9-Ma for 9612-done@debbugs.gnu.org; Thu, 06 Oct 2011 10:57:10 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 0F9BA601A6 for <9612-done@debbugs.gnu.org>; Thu, 6 Oct 2011 16:56:58 +0200 (CEST) From: Jim Meyering To: 9612-done@debbugs.gnu.org Subject: Re: bug#9612: sort: avoid a NaN-induced infloop In-Reply-To: <874nzswqvy.fsf@rho.meyering.net> (Jim Meyering's message of "Sat, 01 Oct 2011 19:41:53 +0200") References: <878vpa6nxu.fsf@rho.meyering.net> <874nzswqvy.fsf@rho.meyering.net> Date: Thu, 06 Oct 2011 16:56:57 +0200 Message-ID: <87k48iyxqe.fsf@rho.meyering.net> Lines: 25 MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 9612-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.0 (---) Jim Meyering wrote: > Jim Meyering wrote: >> Who would have thought that including a few NaNs in the input to sort >> would make it infloop. >> >> The original failure arose only when sort was reading from a pipe: >> >> yes -- -nan | head -156903 | sort -g > /dev/null >> >> But it's not always easy to reproduce. > ... >> [ I'm about to file the glibc bug > ... > > I've done that: > > RFE: strtold: do not include uninitialized bytes when converting "NaN" > http://sourceware.org/bugzilla/show_bug.cgi?id=13246 In the above BZ comments, Jakub Jelinek proposed something more robust, but I think it's not necessary. If we find an optimizer that thinks the added memset is useless, we'll discover it via the failing test, so I'd prefer not to add the volatile/union hack. I'm closing this. ------------=_1317913082-9935-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 27 Sep 2011 14:49:55 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8Yyp-0000eD-1B for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:55 -0400 Received: from eggs.gnu.org ([140.186.70.92]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1R8Yyl-0000e4-2I for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:53 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8Yxs-00072D-3B for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:49:01 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from lists.gnu.org ([140.186.70.17]:56636) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxs-000729-1a for submit@debbugs.gnu.org; Tue, 27 Sep 2011 10:48:56 -0400 Received: from eggs.gnu.org ([140.186.70.92]:40487) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxq-0005r0-Bp for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:55 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8Yxj-00070t-FJ for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:54 -0400 Received: from mx.meyering.net ([88.168.87.75]:50547) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8Yxi-00070e-Ue for bug-coreutils@gnu.org; Tue, 27 Sep 2011 10:48:47 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 4B2D0600D1 for ; Tue, 27 Sep 2011 16:48:45 +0200 (CEST) From: Jim Meyering To: bug-coreutils@gnu.org Subject: sort: avoid a NaN-induced infloop Date: Tue, 27 Sep 2011 16:48:45 +0200 Message-ID: <878vpa6nxu.fsf@rho.meyering.net> Lines: 324 MIME-Version: 1.0 Content-Type: text/plain X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 140.186.70.17 X-Spam-Score: -4.9 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -5.1 (-----) This was reported by Aaron Denney in http://bugs.debian.org/642557. Who would have thought that including a few NaNs in the input to sort would make it infloop. The original failure arose only when sort was reading from a pipe: yes -- -nan | head -156903 | sort -g > /dev/null But it's not always easy to reproduce. For example, on a uni-core Debian unstable amd64 system, the bug strikes every time with the distro-supplied binary, but not at all on a fedora rawhide-supplied binary in a multi-core VM. However, when I compile coreutils-8.13 myself on that same rawhide system, *that* sort fails every time. Setting up to debug was a little tricky. In order to invoke sort-reading-from-pipe from gdb, I had to use a fifo: mkfifo sort-test-pipe yes -- -nan | head -156903 | sort-test-pipe & Then, with gdb, you can do this: gdb sort run -g < sort-test-pipe Debugging it, I was surprised to see the infinite loop iterating through these "*"-marked lines, with nfiles == 2 and always resetting i = 0: (gdb) l 2893 Since this only reorders two items if one is strictly greater than 2894 the other, it is stable. */ 2895 for (i = 0; i < nfiles; ++i) 2896 ord[i] = i; * 2897 for (i = 1; i < nfiles; ++i) * 2898 if (0 < compare (cur[ord[i - 1]], cur[ord[i]])) * 2899 t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0; 2900 2901 /* Repeatedly output the smallest line until no input remains. */ 2902 while (nfiles) (gdb) p ord[i-1] $6 = 0 (gdb) p ord[i] $7 = 1 (gdb) p compare (cur[0], cur[1]) $8 = 64 (gdb) p compare (cur[1], cur[0]) $9 = 64 That shows cur[0] > cur[1], and then, on the very next line a contradiction, cur[1] > cur[0] But it's not the classic NaN problem at all. That would be too easy ;-) That code already handles NaNs (via the general_numcompare function), detecting the unusual case and comparing NaNs with memcmp. Here's most of the general_numcompare function: static int general_numcompare (char const *sa, char const *sb) { char *ea; char *eb; long_double a = strtold (sa, &ea); long_double b = strtold (sb, &eb); ... /* Sort numbers in the usual way, where -0 == +0. Put NaNs after conversion errors but before numbers; sort them by internal bit-pattern, for lack of a more portable alternative. */ return (a < b ? -1 : a > b ? 1 : a == b ? 0 : b == b ? -1 : a == a ? 1 : memcmp (&a, &b, sizeof a)); } What could cause such bogosity? Here's the quick answer: The statement "long double x = NAN;" (inside glibc's strtold) leaves many bits of "x" uninitialized. For most uses of a NaN, that doesn't matter, but here, since we're actually trying to order the different NaNs, it makes all of the difference. [ I'm about to file the glibc bug -- or maybe it's a bug in the definition of gcc's __builtin_nan. Haven't looked yet. ] What happens when we infloop is that the surrounding code always happens to ensure that differing bits are 0x40 in the left operand and 0x00 in the right operand to memcmp. Then you will see precisely the above behavior. One "fix" is to return 0 rather than bothering with the memcmp call above, thus treating all NaNs as equal, rather than attempting to order them based on their internal bit patterns. But that is undesirable since it would render sort's output indeterminate whenever it contains different types of NaN values. E.g., NaN, NaN(1), NaN(2), etc. all result in different bit patterns. For example, currently, this works as you'd expect on a system with a NaN(...)-aware strtold, like anything glibc-based: $ for i in $(seq 9); do echo "NaN($i)";done|sort -gr NaN(9) NaN(8) NaN(7) NaN(6) NaN(5) NaN(4) NaN(3) NaN(2) NaN(1) If we were to remove the memcmp, those would not be sorted. ---------------------------------------- A kludgey fix that serves to demonstrate the problem would be to replace the two strtold invocations with these: long_double a = 0; a = strtold (sa, &ea); long_double b = 0; b = strtold (sb, &eb); That does the job at least when compiling with gcc -ggdb3, but minimal optimization could well eliminate the dead stores. ---------------------------------------- The real solution is to change glibc's strtold so that its "long double" result contains no uninitialized bit. In the shorter term, I'd like a gnulib strtold module that works around the problem. However, gnulib's strtod.c simply ignores the digits in NaN(DDDDD), while glibc's implementation actually uses them. That should be easy to fix, right? Just merge in the glibc changes? But no, they rely on ieee754.h's "union ieee854_long_double", and that is not portable. So I have resorted to an even shorter-term work-around in the patch below. =-================================= Consequences: whenever qsort's comparison function "lies" (i.e., returns 1 for a < b, -1 for a > b, or 0 for a != b, qsort's behavior is undefined (i.e., it may well segfault). GNU sort(1) uses qsort only incidentally, to sort month names, and nowhere else, but now, you've seen that sort(1) had a similar problem when its comparison function is inconsistent. -------------------------------------------------- BTW, once I found the problem code, I realized I could provoke the infloop with two one-line inputs using sort's --merge option: echo nan > 1; sort -m -g 1 1 -------------------------------- Here's a little program to demonstrate the problem. Note how the results differ with compilation options: #include #include static char * fmt_nan (long double x) { unsigned int i; static char buf[33]; unsigned char const *p = (unsigned char const *) &x; for (i = 0; i < sizeof x; i++) sprintf (buf + 2*i, "%02x", *p++); return buf; } int main () { const char *q = "nan"; long double x = strtold (q, NULL); printf ("%s\n", fmt_nan (x)); x = 0; x = strtold (q, NULL); printf ("%s\n", fmt_nan (x)); return 0; } $ gcc -O0 -Wall -Wextra -W /t/strtold-bogosity.c && ./a.out 00000000000000c0ff7f400000000000 00000000000000c0ff7f000000000000 $ gcc -O1 -Wall -Wextra -W /t/strtold-bogosity.c && ./a.out 00000000000000c0ff7f000000000000 00000000000000c0ff7f000000000000 ------------------------------------------------------- And here's the patch I expect to apply for now: >From 17f70721d10f02543ae9e2d4e2c4b2babe0206a7 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Tue, 27 Sep 2011 16:32:35 +0200 Subject: [PATCH] sort: avoid a NaN-induced infloop These commands would fail to terminate: yes -- -nan | head -156903 | sort -g > /dev/null echo nan > F; sort -m -g F F That can happen with any strtold implementation that includes uninitialized data in its return value. The problem arises in the mergefps function when bubble-sorting the two or more lines, each from one of the input streams being merged: compare(a,b) returns 64, yet compare(b,a) also returns a positive value. With a broken comparison function like that, the bubble sort never terminates. Why do the long-double bit strings corresponding to two identical "nan" strings not compare equal? Because some parts of the result are uninitialized and thus depend on the state of the stack. For more details, see http://bugs.gnu.org/FIXME. * src/sort.c (nan_compare): New function. (general_numcompare): Use it rather than bare memcmp. Reported by Aaron Denney in http://bugs.debian.org/642557. * NEWS (Bug fixes): Mention it. * tests/misc/sort-NaN-infloop: New file. * tests/Makefile.am (TESTS): Add it. --- NEWS | 4 ++++ src/sort.c | 20 +++++++++++++++++++- tests/Makefile.am | 1 + tests/misc/sort-NaN-infloop | 28 ++++++++++++++++++++++++++++ 4 files changed, 52 insertions(+), 1 deletions(-) create mode 100755 tests/misc/sort-NaN-infloop diff --git a/NEWS b/NEWS index 140e6fa..f05a088 100644 --- a/NEWS +++ b/NEWS @@ -2,6 +2,10 @@ GNU coreutils NEWS -*- outline -*- * Noteworthy changes in release ?.? (????-??-??) [?] +** Bug fixes + + sort -g no longer infloops for certain inputs containing NaNs + ** Improvements md5sum --check now supports the -r format from the corresponding BSD tool. diff --git a/src/sort.c b/src/sort.c index 3d3119d..3e94a6e 100644 --- a/src/sort.c +++ b/src/sort.c @@ -1910,6 +1910,24 @@ numcompare (char const *a, char const *b) return strnumcmp (a, b, decimal_point, thousands_sep); } +/* Work around a problem whereby the long double value returned by glibc's + strtold ("NaN", ...) contains uninitialized bits: clear all bytes of + A and B before calling strtold. FIXME: remove this function once + gnulib guarantees that strtold's result is always well defined. */ +static int +nan_compare (char const *sa, char const *sb) +{ + long_double a; + memset (&a, 0, sizeof a); + a = strtold (sa, NULL); + + long_double b; + memset (&b, 0, sizeof b); + b = strtold (sb, NULL); + + return memcmp (&a, &b, sizeof a); +} + static int general_numcompare (char const *sa, char const *sb) { @@ -1935,7 +1953,7 @@ general_numcompare (char const *sa, char const *sb) : a == b ? 0 : b == b ? -1 : a == a ? 1 - : memcmp (&a, &b, sizeof a)); + : nan_compare (sa, sb)); } /* Return an integer in 1..12 of the month name MONTH. diff --git a/tests/Makefile.am b/tests/Makefile.am index eeb4cab..2cf409a 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -250,6 +250,7 @@ TESTS = \ misc/sort-unique \ misc/sort-unique-segv \ misc/sort-version \ + misc/sort-NaN-infloop \ split/filter \ split/suffix-length \ split/b-chunk \ diff --git a/tests/misc/sort-NaN-infloop b/tests/misc/sort-NaN-infloop new file mode 100755 index 0000000..ead871e --- /dev/null +++ b/tests/misc/sort-NaN-infloop @@ -0,0 +1,28 @@ +#!/bin/sh +# exercise the NaN-infloop bug in coreutils-8.13 + +# Copyright (C) 2011 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +. "${srcdir=.}/init.sh"; path_prepend_ ../src +print_ver_ sort + +echo nan > F || fail=1 +printf 'nan\nnan\n' > exp || fail=1 +timeout 10 sort -g -m F F > out || fail=1 + +compare out exp || fail=1 + +Exit $fail -- 1.7.7.rc0.362.g5a14 ------------=_1317913082-9935-1--