GNU bug report logs - #9780
sort -u throws out non-duplicates

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 9780 in the body.
You can then email your comments to 9780 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: Bernhard Rosenkraenzer <bero <at> bero.eu>
To: <bug-coreutils <at> gnu.org>
Subject: sort -u throws out non-duplicates
Date: Tue, 18 Oct 2011 01:59:12 +0100

[bero <at> matterhorn tmp]$ wget http://bero.eu/java-source-list
[...]
[bero <at> matterhorn tmp]$ tr ' ' '\n' <java-source-list |sort |grep 
X509Certificate
libcore/luni/src/main/java/java/security/cert/X509Certificate.java
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java

This is correct...

[bero <at> matterhorn tmp]$ tr ' ' '\n' <java-source-list |sort -u |grep 
X509Certificate
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java

Note the missing .../java/java/security/cert/X509Certificate.java

[bero <at> matterhorn tmp]$ tr ' ' '\n' <java-source-list |sort |uniq |grep 
X509Certificate
libcore/luni/src/main/java/java/security/cert/X509Certificate.java
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java

This is correct


The problem occurs (at least) with sort from coreutils 8.12, 8.13 and 
8.14.

ttyl
bero

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

From: Bernhard Rosenkraenzer <bero <at> bero.eu>
To: <bug-coreutils <at> gnu.org>
Subject: Re: sort -u throws out non-duplicates
Date: Tue, 18 Oct 2011 02:02:57 +0100

On Tue, 18 Oct 2011 01:59:12 +0100, Bernhard Rosenkraenzer wrote:
> Note the missing .../java/java/security/cert/X509Certificate.java
>
> The problem occurs (at least) with sort from coreutils 8.12, 8.13 and 
> 8.14.

This is locale related... Seems to happen in any non-C locale.

[bero <at> matterhorn ~]$ tr ' ' '\n' <java-source-list |LANG=C sort -u 
|grep X509Certificate
libcore/luni/src/main/java/java/security/cert/X509Certificate.java
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
[bero <at> matterhorn ~]$ tr ' ' '\n' <java-source-list |LANG=en_US sort -u 
|grep X509Certificate
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
[bero <at> matterhorn ~]$ tr ' ' '\n' <java-source-list |LANG=de_CH sort -u 
|grep X509Certificate
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
[bero <at> matterhorn ~]$ tr ' ' '\n' <java-source-list |LANG=fr_FR sort -u 
|grep X509Certificate
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java

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

From: Eric Blake <eblake <at> redhat.com>
To: Bernhard Rosenkraenzer <bero <at> bero.eu>
Cc: 9780 <at> debbugs.gnu.org
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Mon, 17 Oct 2011 20:22:52 -0600

tag 9780 moreinfo
thanks

On 10/17/2011 06:59 PM, Bernhard Rosenkraenzer wrote:
> [bero <at> matterhorn tmp]$ wget http://bero.eu/java-source-list
> [...]
> [bero <at> matterhorn tmp]$ tr ' ' '\n' <java-source-list |sort |grep
> X509Certificate
> libcore/luni/src/main/java/java/security/cert/X509Certificate.java
> libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
>
> This is correct...
>
> [bero <at> matterhorn tmp]$ tr ' ' '\n' <java-source-list |sort -u |grep
> X509Certificate
> libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
>
> Note the missing .../java/java/security/cert/X509Certificate.java

Thanks for the report.  Unfortunately, you did not provide enough 
information to reproduce this - for example, what platform are you 
running on?  Can you narrow it down to a single file of say 5 or so 
lines?  Can you reproduce the problem with shorter input lines?

My guess, although I need more info to confirm it, is that this is not a 
bug, but rather that java-source-list contains some lines that differ in 
case and/or punctuation but happen to collate identically.  If so, then 
sort -u is picking the lower-case version as the unique line, at which 
point your grep for the case-sensitive X509Certificate is obviously failing.

The fact that you already proved that LC_ALL=C changes the behavior 
lends credence to my supposition, since C is byte-sensitive, but most 
other languages collate case-insensitively.  See also the FAQ:

https://www.gnu.org/software/coreutils/faq/#Sort-does-not-sort-in-normal-order_0021

> The problem occurs (at least) with sort from coreutils 8.12, 8.13 and 8.14.

Use 'sort --debug' to help decipher sort's behavior.  Here's my 
demonstration that I cannot reproduce it using coreutils.git with just 
two input lines:

$ printf 
'libcore/luni/src/main/java/java/security/cert/X509Certificate.java\nlibcore/luni/src/main/java/javax/security/cert/X509Certificate.java\n' 
| sort -u --debug
sort: using `en_US.UTF-8' sorting rules
libcore/luni/src/main/java/java/security/cert/X509Certificate.java
__________________________________________________________________
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
___________________________________________________________________

So there's definitely something else in java-source-list that we aren't 
seeing that is (probably correctly) affecting your output.

-- 
Eric Blake   eblake <at> redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

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

From: Bernhard Rosenkraenzer <bero <at> bero.eu>
To: Eric Blake <eblake <at> redhat.com>
Cc: 9780 <at> debbugs.gnu.org
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Tue, 18 Oct 2011 09:48:00 +0100

On Mon, 17 Oct 2011 20:22:52 -0600, Eric Blake wrote:
> On 10/17/2011 06:59 PM, Bernhard Rosenkraenzer wrote:
> Thanks for the report.  Unfortunately, you did not provide enough
> information to reproduce this - for example, what platform are you
> running on?

Fairly current Linux -- kernel 3.1-rc9, eglibc 2.14.1

>  Can you narrow it down to a single file of say 5 or so
> lines?  Can you reproduce the problem with shorter input lines?

Yes:
[bero <at> matterhorn ~]$ echo 
'libcore/luni/src/main/java/java/security/cert/X509CRLSelector.java 
libcore/luni/src/main/java/java/security/cert/X509CertSelector.java 
libcore/luni/src/main/java/java/security/cert/X509Certificate.java 
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java' |tr 
' ' '\n' |sort -u --debug
sort: using `en_US' sorting rules
libcore/luni/src/main/java/java/security/cert/X509CertSelector.java
___________________________________________________________________
libcore/luni/src/main/java/java/security/cert/X509CRLSelector.java
__________________________________________________________________
libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
___________________________________________________________________


It starts working correctly if any of the entries are removed, yet none 
of those should match as a duplicate as far as I can see.

> My guess, although I need more info to confirm it, is that this is
> not a bug, but rather that java-source-list contains some lines that
> differ in case and/or punctuation but happen to collate identically.
> If so, then sort -u is picking the lower-case version as the unique
> line, at which point your grep for the case-sensitive X509Certificate
> is obviously failing.

FWIW changing everything to lower case doesn't change anything
[bero <at> matterhorn ~]$ echo 
'libcore/luni/src/main/java/java/security/cert/x509crlselector.java 
libcore/luni/src/main/java/java/security/cert/x509certselector.java 
libcore/luni/src/main/java/java/security/cert/x509certificate.java 
libcore/luni/src/main/java/javax/security/cert/x509certificate.java' |tr 
' ' '\n' |sort -u --debug
sort: using `en_US' sorting rules
libcore/luni/src/main/java/java/security/cert/x509certselector.java
___________________________________________________________________
libcore/luni/src/main/java/java/security/cert/x509crlselector.java
__________________________________________________________________
libcore/luni/src/main/java/javax/security/cert/x509certificate.java
___________________________________________________________________


ttyl
bero

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

From: Jim Meyering <jim <at> meyering.net>
To: Bernhard Rosenkraenzer <bero <at> bero.eu>
Cc: 9780 <at> debbugs.gnu.org, Eric Blake <eblake <at> redhat.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Tue, 18 Oct 2011 11:29:29 +0200

Bernhard Rosenkraenzer wrote:

> On Mon, 17 Oct 2011 20:22:52 -0600, Eric Blake wrote:
>> On 10/17/2011 06:59 PM, Bernhard Rosenkraenzer wrote:
>> Thanks for the report.  Unfortunately, you did not provide enough
>> information to reproduce this - for example, what platform are you
>> running on?
>
> Fairly current Linux -- kernel 3.1-rc9, eglibc 2.14.1
>
>>  Can you narrow it down to a single file of say 5 or so
>> lines?  Can you reproduce the problem with shorter input lines?
>
> Yes:
> [bero <at> matterhorn ~]$ echo
> libcore/luni/src/main/java/java/security/cert/X509CRLSelector.java
> libcore/luni/src/main/java/java/security/cert/X509CertSelector.java
> libcore/luni/src/main/java/java/security/cert/X509Certificate.java
> libcore/luni/src/main/java/javax/security/cert/X509Certificate.java'
> |tr ' ' '\n' |sort -u --debug

So far, I've been unable to reproduce that on Fedora 16 or Debian unstable
both x86_64.  I.e., the following (equivalent to above, but with no long
lines) always prints the four input lines:

cert=libcore/luni/src/main/java/java/security/cert
echo \
 $cert/X509CRLSelector.java \
 $cert/X509CertSelector.java \
 $cert/X509Certificate.java \
 libcore/luni/src/main/java/javax/security/cert/X509Certificate.java \
 |tr ' ' '\n' |sort -u --debug

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

From: Pádraig Brady <P <at> draigBrady.com>
To: Bernhard Rosenkraenzer <bero <at> bero.eu>
Cc: 9780 <at> debbugs.gnu.org
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Tue, 18 Oct 2011 13:01:28 +0100

On 10/18/2011 09:48 AM, Bernhard Rosenkraenzer wrote:
> On Mon, 17 Oct 2011 20:22:52 -0600, Eric Blake wrote:
>> On 10/17/2011 06:59 PM, Bernhard Rosenkraenzer wrote:
>> Thanks for the report.  Unfortunately, you did not provide enough
>> information to reproduce this - for example, what platform are you
>> running on?
> 
> Fairly current Linux -- kernel 3.1-rc9, eglibc 2.14.1
> 
>>  Can you narrow it down to a single file of say 5 or so
>> lines?  Can you reproduce the problem with shorter input lines?
> 
> Yes:
> [bero <at> matterhorn ~]$ echo 'libcore/luni/src/main/java/java/security/cert/X509CRLSelector.java libcore/luni/src/main/java/java/security/cert/X509CertSelector.java libcore/luni/src/main/java/java/security/cert/X509Certificate.java libcore/luni/src/main/java/javax/security/cert/X509Certificate.java' |tr ' ' '\n' |sort -u --debug
> sort: using `en_US' sorting rules
> libcore/luni/src/main/java/java/security/cert/X509CertSelector.java
> ___________________________________________________________________
> libcore/luni/src/main/java/java/security/cert/X509CRLSelector.java
> __________________________________________________________________
> libcore/luni/src/main/java/javax/security/cert/X509Certificate.java
> ___________________________________________________________________
> 
> 
> It starts working correctly if any of the entries are removed, yet none of those should match as a duplicate as far as I can see.
> 
>> My guess, although I need more info to confirm it, is that this is
>> not a bug, but rather that java-source-list contains some lines that
>> differ in case and/or punctuation but happen to collate identically.
>> If so, then sort -u is picking the lower-case version as the unique
>> line, at which point your grep for the case-sensitive X509Certificate
>> is obviously failing.
> 
> FWIW changing everything to lower case doesn't change anything
> [bero <at> matterhorn ~]$ echo 'libcore/luni/src/main/java/java/security/cert/x509crlselector.java libcore/luni/src/main/java/java/security/cert/x509certselector.java libcore/luni/src/main/java/java/security/cert/x509certificate.java libcore/luni/src/main/java/javax/security/cert/x509certificate.java' |tr ' ' '\n' |sort -u --debug
> sort: using `en_US' sorting rules
> libcore/luni/src/main/java/java/security/cert/x509certselector.java
> ___________________________________________________________________
> libcore/luni/src/main/java/java/security/cert/x509crlselector.java
> __________________________________________________________________
> libcore/luni/src/main/java/javax/security/cert/x509certificate.java
> ___________________________________________________________________
> 
> 

I can't reproduce this.
There may be some issues currently with debian locale defs?

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=636286

cheers,
Pádraig.

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

From: Rasmus Borup Hansen <rbh <at> intomics.com>
To: 9780 <at> debbugs.gnu.org
Subject: sort -u throws out non-duplicates
Date: Tue, 14 Aug 2012 10:17:21 +0200

I came across this bug and have written a small shell script (below) that reproduces it on recent Linux distributions. It also reproduces the error using the latest coreutils compiled from sources.

Best regards,

Rasmus


#!/bin/sh

# Generate a file consisting only of 24 long sequences of lines with
# numbers from 0 to 23. This is actually a file that strongly
# resembles one we came upon during our work.

(
    for i in `seq 1 18624` ; do echo 18; done
    for i in `seq 1 69001` ; do echo 10; done
    for i in `seq 1 37950` ; do echo 20; done
    for i in `seq 1 124026` ; do echo 2; done
    for i in `seq 1 52202` ; do echo 15; done
    for i in `seq 1 3660` ; do echo 0; done
    for i in `seq 1 71627` ; do echo 5; done
    for i in `seq 1 69989` ; do echo 19; done
    for i in `seq 1 65192` ; do echo 9; done
    for i in `seq 1 51058` ; do echo 16; done
    for i in `seq 1 26810` ; do echo 13; done
    for i in `seq 1 56387` ; do echo 23; done
    for i in `seq 1 77273` ; do echo 7; done
    for i in `seq 1 159425` ; do echo 1; done
    for i in `seq 1 36851` ; do echo 22; done
    for i in `seq 1 102583` ; do echo 12; done
    for i in `seq 1 75429` ; do echo 17; done
    for i in `seq 1 82322` ; do echo 6; done
    for i in `seq 1 101135` ; do echo 3; done
    for i in `seq 1 63726` ; do echo 4; done
    for i in `seq 1 57302` ; do echo 14; done
    for i in `seq 1 57770` ; do echo 8; done
    for i in `seq 1 18032` ; do echo 21; done
    for i in `seq 1 101938` ; do echo 11; done
) > inputfile

# There should be 24 unique lines in inputfile no matter what the -S
# parameter to sort is.

for SIZE in `seq 128 140` ; do
    sort -S $SIZE -u inputfile | wc -l
done

# Ubuntu 12.04     OpenSuSE 11.4    SLES 10 SP1      Gentoo
# coreutils 8.12   coreutils 8.9    coreutils 5.93   coreutils 8.14
# 23               24               24               24
# 24               24               24               24
# 24               24               24               23
# 23               23               24               24
# 24               21               24               22
# 24               24               24               23
# 22               23               24               23
# 24               23               24               23
# 22               24               24               23
# 24               24               24               24
# 24               24               24               24
# 24               24               24               22
# 24               24               24               23

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Rasmus Borup Hansen <rbh <at> intomics.com>
Cc: 9780 <at> debbugs.gnu.org
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Tue, 14 Aug 2012 11:28:21 -0700

Thanks very much for that test case; I've confirmed the bug on
my platform with the latest 'sort'.  If nobody else gets to it
I will try to take a look at it when I find the time
(most likely in a week or so).

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Tue, 14 Aug 2012 23:09:11 +0200

Paul Eggert wrote:
> Thanks very much for that test case; I've confirmed the bug on
> my platform with the latest 'sort'.  If nobody else gets to it
> I will try to take a look at it when I find the time
> (most likely in a week or so).

Yes, thanks again!
That is a serious bug.
It has been around for a long time.

This small reproducer (on a 2-core i686 system)
  perl -e 'printf "33\n"x2 ."7\n"x31 ."1\n"' | src/sort -S1 -u
prints this:
  33
  7
but should print this:
  1
  33
  7

On a multi-core x86_64, I need slightly different input to trigger
the failure.  Note how this uses only 22 '7's and --parallel=1.

  $ perl -e 'printf "33\n"x2 ."7\n"x22 ."1\n"'|src/sort --para=1 -S1 -u
  33
  7

The problem starts with write_unique's static variable:

static void
write_unique (struct line const *line, FILE *tfp, char const *temp_output)
{
  static struct line saved;
  if (unique)
    {
      if (saved.text && ! compare (line, &saved))
        return;
      saved = *line;
    }
    ...

Note how that merely makes a shallow copy of "*line".
I.e., it merely copies line's 4 members, 3 of which are pointers.

  (gdb) p *line
  $1 = {
    text = 0x806221e "1",
    length = 2,
    keybeg = 0x62626262 <Address 0x62626262 out of bounds>,
    keylim = 0x62626262 <Address 0x62626262 out of bounds>

In that example, the two key* variables are not even initialized,
which is not a problem, since they're not used in this example.
The one that causes trouble is the .text pointer.
The line buffer storage into which it points ends
up being overwritten when new data is read in (via fread),
and so if you are unlucky, you'll get an accidental match
and mistakenly skip the sole (in reduced temp files) occurrence
of a line, resulting in incorrect output.

The solution may be to make a deep copy, and store it in
an extensible (probably never-freed) buffer.
However, that looks like it will be comparatively expensive,
since determining whether keybeg and keylim must
also be copied depends on many global options,
the same ones used by sort's compare function.

A slower-yet-correct "sort -u" is obviously preferable to
our currently faster-yet-buggy one.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Wed, 15 Aug 2012 19:47:33 +0200

Jim Meyering wrote:
> Paul Eggert wrote:
>> Thanks very much for that test case; I've confirmed the bug on
>> my platform with the latest 'sort'.  If nobody else gets to it
>> I will try to take a look at it when I find the time
>> (most likely in a week or so).
>
> Yes, thanks again!
> That is a serious bug.
> It has been around for a long time.
>
> This small reproducer (on a 2-core i686 system)
>   perl -e 'printf "33\n"x2 ."7\n"x31 ."1\n"' | src/sort -S1 -u
> prints this:
>   33
>   7
> but should print this:
>   1
>   33
>   7
>
> On a multi-core x86_64, I need slightly different input to trigger
> the failure.  Note how this uses only 22 '7's and --parallel=1.
>
>   $ perl -e 'printf "33\n"x2 ."7\n"x22 ."1\n"'|src/sort --para=1 -S1 -u
>   33
>   7
>
> The problem starts with write_unique's static variable:
>
> static void
> write_unique (struct line const *line, FILE *tfp, char const *temp_output)
> {
>   static struct line saved;
>   if (unique)
>     {
>       if (saved.text && ! compare (line, &saved))
>         return;
>       saved = *line;
>     }
>     ...
>
> Note how that merely makes a shallow copy of "*line".
> I.e., it merely copies line's 4 members, 3 of which are pointers.
>
>   (gdb) p *line
>   $1 = {
>     text = 0x806221e "1",
>     length = 2,
>     keybeg = 0x62626262 <Address 0x62626262 out of bounds>,
>     keylim = 0x62626262 <Address 0x62626262 out of bounds>
>
> In that example, the two key* variables are not even initialized,
> which is not a problem, since they're not used in this example.
> The one that causes trouble is the .text pointer.
> The line buffer storage into which it points ends
> up being overwritten when new data is read in (via fread),
> and so if you are unlucky, you'll get an accidental match
> and mistakenly skip the sole (in reduced temp files) occurrence
> of a line, resulting in incorrect output.
>
> The solution may be to make a deep copy, and store it in
> an extensible (probably never-freed) buffer.
> However, that looks like it will be comparatively expensive,
> since determining whether keybeg and keylim must
> also be copied depends on many global options,
> the same ones used by sort's compare function.
>
> A slower-yet-correct "sort -u" is obviously preferable to
> our currently faster-yet-buggy one.

I'm technically "off" today, so have had little time.
In case anyone is chomping at the bit, here's a preliminary patch:

Here's a smaller test case that appears to be host/nproc-independent:
It should print two lines: 1, then 7.
Without this patch, it prints only "7".

    (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u

Of course, it needs more/better comments, NEWS and
tests -- and not just the one above, but also one that
demonstrates the need for the key* adjustments below.

This solution doesn't incur much of a performance penalty
because it copies the line only rarely: just before an fread
call that might modify the currently-saved text.


From 24f9646e3b954b7c914c0f3139054dfce466d314 Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering <at> redhat.com>
Date: Wed, 15 Aug 2012 12:30:44 +0200
Subject: [PATCH] sort: fix bug with --unique

---
 src/sort.c | 37 ++++++++++++++++++++++++++++++++++---
 1 file changed, 34 insertions(+), 3 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index d362dc5..6b07c22 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -262,6 +262,9 @@ struct merge_node_queue
                                    when popping. */
 };

+/* Used to implement --unique (-u).  */
+static struct line saved_line;
+
 /* FIXME: None of these tables work with multibyte character sets.
    Also, there are many other bugs when handling multibyte characters.
    One way to fix this is to rewrite 'sort' to use wide characters
@@ -1702,6 +1705,14 @@ limfield (struct line const *line, struct keyfield const *key)
   return ptr;
 }

+/* Return true if LINE and the buffer BUF of length LEN overlap.  */
+static inline bool
+overlap (char const *buf, size_t len, struct line const *line)
+{
+  char const *line_end = line->text + line->length;
+  return !(line_end <= buf || buf + len <= line->text);
+}
+
 /* Fill BUF reading from FP, moving buf->left bytes from the end
    of buf->buf to the beginning first.  If EOF is reached and the
    file wasn't terminated by a newline, supply one.  Set up BUF's line
@@ -1742,6 +1753,27 @@ fillbuf (struct buffer *buf, FILE *fp, char const *file)
              rest of the input file consists entirely of newlines,
              except that the last byte is not a newline.  */
           size_t readsize = (avail - 1) / (line_bytes + 1);
+          if (unique && overlap (ptr, readsize, &saved_line))
+            {
+              /* Copy saved_line.text into a buffer where it won't be clobbered
+                 and if KEY is non-NULL, adjust saved_line.key* to match.  */
+              static char *safe_text;
+              static size_t safe_text_n_alloc;
+              if (safe_text_n_alloc < saved_line.length)
+                {
+                  safe_text_n_alloc = saved_line.length;
+                  safe_text = x2nrealloc (safe_text, &safe_text_n_alloc, 1);
+                }
+              memcpy (safe_text, saved_line.text, saved_line.length);
+              if (key)
+                {
+                  #define s saved_line
+                  s.keybeg = safe_text + (s.keybeg - s.text);
+                  s.keylim = safe_text + (s.keylim - s.text);
+                  #undef s
+                }
+              saved_line.text = safe_text;
+            }
           size_t bytes_read = fread (ptr, 1, readsize, fp);
           char *ptrlim = ptr + bytes_read;
           char *p;
@@ -3348,13 +3380,12 @@ queue_pop (struct merge_node_queue *queue)
 static void
 write_unique (struct line const *line, FILE *tfp, char const *temp_output)
 {
-  static struct line saved;

   if (unique)
     {
-      if (saved.text && ! compare (line, &saved))
+      if (saved_line.text && ! compare (line, &saved_line))
         return;
-      saved = *line;
+      saved_line = *line;
     }

   write_line (line, tfp, temp_output);
--
1.7.12.rc2.16.g034161a

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Thu, 16 Aug 2012 09:27:23 +0200

Jim Meyering wrote:
...
> Here's a smaller test case that appears to be host/nproc-independent:
> It should print two lines: 1, then 7.
> Without this patch, it prints only "7".
>
>     (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u
>
> Of course, it needs more/better comments, NEWS and
> tests -- and not just the one above, but also one that
> demonstrates the need for the key* adjustments below.

FYI, here's the required test:

  (yes 7|head -10; echo 1)|sed 's/^/1 /'|sort -k2,2 --p=1 -S32b -u

Without the if (key) { ... } part of my patch, it would fail.
I had to tweak the number of '7's (s/11/10) in the input to make
it trigger.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Thu, 16 Aug 2012 10:09:24 +0200

Jim Meyering wrote:

> Jim Meyering wrote:
> ...
>> Here's a smaller test case that appears to be host/nproc-independent:
>> It should print two lines: 1, then 7.
>> Without this patch, it prints only "7".
>>
>>     (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u
>>
>> Of course, it needs more/better comments, NEWS and
>> tests -- and not just the one above, but also one that
>> demonstrates the need for the key* adjustments below.
>
> FYI, here's the required test:
>
>   (yes 7|head -10; echo 1)|sed 's/^/1 /'|sort -k2,2 --p=1 -S32b -u
>
> Without the if (key) { ... } part of my patch, it would fail.
> I had to tweak the number of '7's (s/11/10) in the input to make
> it trigger.

Hmm... The above is arch-specific.
It triggers the bug on i686, but not on x86_64.

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

From: Bernhard Voelker <mail <at> bernhard-voelker.de>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Paul Eggert <eggert <at> cs.ucla.edu>,
	Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Thu, 16 Aug 2012 10:27:58 +0200

On 08/16/2012 10:09 AM, Jim Meyering wrote:
>> FYI, here's the required test:
>> >
>> >   (yes 7|head -10; echo 1)|sed 's/^/1 /'|sort -k2,2 --p=1 -S32b -u
>> >
>> > Without the if (key) { ... } part of my patch, it would fail.
>> > I had to tweak the number of '7's (s/11/10) in the input to make
>> > it trigger.
> Hmm... The above is arch-specific.
> It triggers the bug on i686, but not on x86_64.

This triggers the bug on my x86_64:

  $ ~/cu> (yes 7|head -n 100; echo 1)|sed 's/^/1 /'| src/sort -k2,2 --p=1 -S1k -u
  1 7

However, a little different line does not:

  $ ~/cu> (yes 7|head -n 10; echo 1)|sed 's/^/1 /'| src/sort -k2,2 --p=1 -S1k -u
  1 1
  1 7

  $ ~/cu> (yes 7|head -n 100; echo 1)|sed 's/^/1 /'| src/sort -k2,2 --p=1 -S1M -u
  1 1
  1 7

Have a ncie day,
Berny

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Thu, 16 Aug 2012 10:28:25 +0200

Jim Meyering wrote:
> Jim Meyering wrote:
>> Jim Meyering wrote:
>> ...
>>> Here's a smaller test case that appears to be host/nproc-independent:
>>> It should print two lines: 1, then 7.
>>> Without this patch, it prints only "7".
>>>
>>>     (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u
>>>
>>> Of course, it needs more/better comments, NEWS and
>>> tests -- and not just the one above, but also one that
>>> demonstrates the need for the key* adjustments below.
>>
>> FYI, here's the required test:
>>
>>   (yes 7|head -10; echo 1)|sed 's/^/1 /'|sort -k2,2 --p=1 -S32b -u
>>
>> Without the if (key) { ... } part of my patch, it would fail.
>> I had to tweak the number of '7's (s/11/10) in the input to make
>> it trigger.
>
> Hmm... The above is arch-specific.
> It triggers the bug on i686, but not on x86_64.

Here's an interesting one, this time x86_64-specific:

perl -e 'print "0\n"x5000 ."6\n"x6000 ."8\n"x3000 ."4\n"x8000 ."1\n"x2000' \
  | sed 's/^/a /'| sort -k2,2 -u --par=1 -S1k

It prints a single line:

  a 1

rather than the required five:

  a 0
  a 1
  a 4
  a 6
  a 8

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Thu, 16 Aug 2012 23:03:02 +0200

Jim Meyering wrote:
...
> In case anyone is chomping at the bit, here's a preliminary patch:
>
> Here's a smaller test case that appears to be host/nproc-independent:
> It should print two lines: 1, then 7.
> Without this patch, it prints only "7".
>
>     (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u
>
> Of course, it needs more/better comments, NEWS and
> tests -- and not just the one above, but also one that
> demonstrates the need for the key* adjustments below.
>
> This solution doesn't incur much of a performance penalty
> because it copies the line only rarely: just before an fread
> call that might modify the currently-saved text.
>
...
> Subject: [PATCH] sort: fix bug with --unique
>
> ---
>  src/sort.c | 37 ++++++++++++++++++++++++++++++++++---
>  1 file changed, 34 insertions(+), 3 deletions(-)

Here's a complete patch:

From 431102766cbf7c360ee6fa1f157ebcd7d8b9ca0e Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering <at> redhat.com>
Date: Wed, 15 Aug 2012 12:30:44 +0200
Subject: [PATCH] sort: sort --unique (-u) could cause data loss

sort -u could omit one or more lines of expected output.
This bug arose because sort recorded the most recently printed line via
reference, and if you were unlucky, the storage for that line would be
reused (overwritten) as additional input was read into memory.  If you
were doubly unlucky, the new value of the "saved" line would not only
match the very next line, but if that next line were also the first in
a series of identical, not-yet-printed lines, then the corrupted "saved"
line value would result in the omission of all matching lines.

* src/sort.c (saved_line): New static/global, renamed and moved from...
(write_unique): ...here.  Old name was "saved", which was too generic
for its new role as file-scoped global.
(fillbuf): With --unique, when we're about to read into a buffer that
overlaps the saved "preceding" line (saved_line), copy the line's .text
member to a realloc'd-as-needed temporary buffer and adjust the line's
key-defining members if they're set.
(overlap): New function.
* tests/misc/sort: New tests.
* NEWS (Bug fixes): Mention it.
* THANKS.in: Update.
Bug introduced via commit v8.5-89-g9face83.
Reported by Rasmus Borup Hansen in
http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/23173/focus=24647
---
 NEWS            |  5 +++++
 THANKS.in       |  1 +
 src/sort.c      | 44 ++++++++++++++++++++++++++++++++++++++++----
 tests/misc/sort |  9 +++++++++
 4 files changed, 55 insertions(+), 4 deletions(-)

diff --git a/NEWS b/NEWS
index 012a633..f39a76a 100644
--- a/NEWS
+++ b/NEWS
@@ -9,6 +9,11 @@ GNU coreutils NEWS                                    -*- outline -*-
   certain options like -a, -l, -t and -x.
   [This bug was present in "the beginning".]

+  sort -u could fail to output one or more result lines.
+  For example, this command would fail to print "1":
+  (yes 7 | head -11; echo 1) | sort --p=1 -S32b -u
+  [bug introduced in coreutils-8.6]
+
 ** New features

   rm now accepts the --dir (-d) option which makes it remove empty directories.
diff --git a/THANKS.in b/THANKS.in
index 5db443b..a736201 100644
--- a/THANKS.in
+++ b/THANKS.in
@@ -508,6 +508,7 @@ Primoz PETERLIN                     primozz.peterlin <at> gmail.com
 Rainer Orth                         ro <at> TechFak.Uni-Bielefeld.DE
 Ralf W. Stephan                     stephan <at> tmt.de
 Ralph Loader                        loader <at> maths.ox.ac.uk
+Rasmus Borup Hansen                 rbh <at> intomics.com
 Raul Miller                         moth <at> magenta.com
 Raúl Núñez de Arenas Coronado       raul <at> pleyades.net
 Richard A Downing                   richard.downing <at> bcs.org.uk
diff --git a/src/sort.c b/src/sort.c
index d362dc5..c2d2d49 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -262,6 +262,9 @@ struct merge_node_queue
                                    when popping. */
 };

+/* Used to implement --unique (-u).  */
+static struct line saved_line;
+
 /* FIXME: None of these tables work with multibyte character sets.
    Also, there are many other bugs when handling multibyte characters.
    One way to fix this is to rewrite 'sort' to use wide characters
@@ -1702,6 +1705,14 @@ limfield (struct line const *line, struct keyfield const *key)
   return ptr;
 }

+/* Return true if LINE and the buffer BUF of length LEN overlap.  */
+static inline bool
+overlap (char const *buf, size_t len, struct line const *line)
+{
+  char const *line_end = line->text + line->length;
+  return !(line_end <= buf || buf + len <= line->text);
+}
+
 /* Fill BUF reading from FP, moving buf->left bytes from the end
    of buf->buf to the beginning first.  If EOF is reached and the
    file wasn't terminated by a newline, supply one.  Set up BUF's line
@@ -1742,6 +1753,33 @@ fillbuf (struct buffer *buf, FILE *fp, char const *file)
              rest of the input file consists entirely of newlines,
              except that the last byte is not a newline.  */
           size_t readsize = (avail - 1) / (line_bytes + 1);
+
+          /* With --unique, when we're about to read into a buffer that
+             overlaps the saved "preceding" line (saved_line), copy the line's
+             .text member to a realloc'd-as-needed temporary buffer and adjust
+             the line's key-defining members if they're set.  */
+          if (unique && overlap (ptr, readsize, &saved_line))
+            {
+              /* Copy saved_line.text into a buffer where it won't be clobbered
+                 and if KEY is non-NULL, adjust saved_line.key* to match.  */
+              static char *safe_text;
+              static size_t safe_text_n_alloc;
+              if (safe_text_n_alloc < saved_line.length)
+                {
+                  safe_text_n_alloc = saved_line.length;
+                  safe_text = x2nrealloc (safe_text, &safe_text_n_alloc, 1);
+                }
+              memcpy (safe_text, saved_line.text, saved_line.length);
+              if (key)
+                {
+                  #define s saved_line
+                  s.keybeg = safe_text + (s.keybeg - s.text);
+                  s.keylim = safe_text + (s.keylim - s.text);
+                  #undef s
+                }
+              saved_line.text = safe_text;
+            }
+
           size_t bytes_read = fread (ptr, 1, readsize, fp);
           char *ptrlim = ptr + bytes_read;
           char *p;
@@ -3348,13 +3386,11 @@ queue_pop (struct merge_node_queue *queue)
 static void
 write_unique (struct line const *line, FILE *tfp, char const *temp_output)
 {
-  static struct line saved;
-
   if (unique)
     {
-      if (saved.text && ! compare (line, &saved))
+      if (saved_line.text && ! compare (line, &saved_line))
         return;
-      saved = *line;
+      saved_line = *line;
     }

   write_line (line, tfp, temp_output);
diff --git a/tests/misc/sort b/tests/misc/sort
index 5d15d75..050d2f8 100755
--- a/tests/misc/sort
+++ b/tests/misc/sort
@@ -227,6 +227,15 @@ my @Tests =
 ["15d", '-i -u', {IN=>"\1a\na\n"}, {OUT=>"\1a\n"}],
 ["15e", '-i -u', {IN=>"a\n\1\1\1\1\1a\1\1\1\1\n"}, {OUT=>"a\n"}],

+# This would fail (printing only the 7) for 8.6..8.18.
+["unique-1", '--p=1 -S32b -u', {IN=>"7\n"x11 . "1\n"}, {OUT=>"1\n7\n"}],
+# Demonstrate that 8.19's key-spec-adjusting code is required.
+# These are more finicky in that they are arch-dependent.
+["unique-key-i686", '-k2,2 --p=1 -S32b -u',
+  {IN=>"a 7\n"x10 . "b 1\n"}, {OUT=>"b 1\na 7\n"}],
+["unique-key-x86_64", '-k2,2 --p=1 -S1k -u',
+  {IN=>"a 7\n"x20 . "b 1\n"}, {OUT=>"b 1\na 7\n"}],
+
 # From Erick Branderhorst -- fixed around 1.19e
 ["16a", '-f',
  {IN=>"éminence\nüberhaupt\n's-Gravenhage\naëroclub\nAag\naagtappels\n"},
--
1.7.12.rc2

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 9780 <at> debbugs.gnu.org,
	Benno Schulenberg <bensberg <at> justemail.net>,
	Bruce Dubbs <bruce.dubbs <at> gmail.com>, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: sort -u data loss deserves new release ASAP [Re: bug#9780: sort -u...
Date: Fri, 17 Aug 2012 12:00:24 +0200

Jim Meyering wrote:
> Jim Meyering wrote:
> ...
>> In case anyone is chomping at the bit, here's a preliminary patch:
>>
>> Here's a smaller test case that appears to be host/nproc-independent:
>> It should print two lines: 1, then 7.
>> Without this patch, it prints only "7".
>>
>>     (yes 7|head -11; echo 1)|sort --parallel=1 -S32b -u
...
> Here's a complete patch:
>
>>From 431102766cbf7c360ee6fa1f157ebcd7d8b9ca0e Mon Sep 17 00:00:00 2001
> From: Jim Meyering <meyering <at> redhat.com>
> Date: Wed, 15 Aug 2012 12:30:44 +0200
> Subject: [PATCH] sort: sort --unique (-u) could cause data loss
>
> sort -u could omit one or more lines of expected output.
> This bug arose because sort recorded the most recently printed line via
> reference, and if you were unlucky, the storage for that line would be
> reused (overwritten) as additional input was read into memory.  If you
> were doubly unlucky, the new value of the "saved" line would not only
> match the very next line, but if that next line were also the first in
> a series of identical, not-yet-printed lines, then the corrupted "saved"
> line value would result in the omission of all matching lines.
>
> * src/sort.c (saved_line): New static/global, renamed and moved from...
> (write_unique): ...here.  Old name was "saved", which was too generic
> for its new role as file-scoped global.
> (fillbuf): With --unique, when we're about to read into a buffer that
> overlaps the saved "preceding" line (saved_line), copy the line's .text
> member to a realloc'd-as-needed temporary buffer and adjust the line's
> key-defining members if they're set.
> (overlap): New function.
> * tests/misc/sort: New tests.
> * NEWS (Bug fixes): Mention it.
> * THANKS.in: Update.
> Bug introduced via commit v8.5-89-g9face83.
> Reported by Rasmus Borup Hansen in
> http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/23173/focus=24647

That sort -u can cause data loss is a big deal.
I want to make a release with this fix as soon as possible.
Since I'm making this a mostly-bug-fix release, the du and md5 --tag
changes will have to wait for 8.20.
However, I'll be happy to apply documentation-correcting changes
if someone would post a complete, updated patch or two.

If Bruce and Paul find that changing gnulib's parse-datetime test
will avoid a failure on LFS, I'll pull in a gnulib update for that.

Any other bug-fix-like changes that people can suggest?

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

From: Bernhard Voelker <mail <at> bernhard-voelker.de>
To: Jim Meyering <jim <at> meyering.net>
Cc: Benno Schulenberg <bensberg <at> justemail.net>, 9780 <at> debbugs.gnu.org,
	Paul Eggert <eggert <at> cs.ucla.edu>, Bruce Dubbs <bruce.dubbs <at> gmail.com>,
	Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u data loss deserves new release ASAP [Re:
	bug#9780: sort -u...
Date: Fri, 17 Aug 2012 13:06:53 +0200

On 08/17/2012 12:00 PM, Jim Meyering wrote:
> I want to make a release with this fix as soon as possible.
> Since I'm making this a mostly-bug-fix release, the du and md5 --tag
> changes will have to wait for 8.20.
> However, I'll be happy to apply documentation-correcting changes
> if someone would post a complete, updated patch or two.
> 
> If Bruce and Paul find that changing gnulib's parse-datetime test
> will avoid a failure on LFS, I'll pull in a gnulib update for that.
> 
> Any other bug-fix-like changes that people can suggest?

Hi Jim,

the first part of Benno's patch is a trivial documentation fix:
  http://debbugs.gnu.org/12212
  [PATCH 1/2] dd: the word BLOCKS no longer occurs in the help text

It fixes the man-page of dd. I replied that the same is
necessary in coreutils.texi, but there's no commitable patch
yet.

Now I see that you already CC'ed Benno ...

Have a nice day,
Berny

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 12:19:35 -0700

On 08/16/2012 02:03 PM, Jim Meyering wrote:
> * src/sort.c (saved_line): New static/global, renamed and moved from...
> (write_unique): ...here.

I see a couple of problems with this patch.  Pedantically,
the behavior of 'overlap' is undefined on hosts that
use a segmented architecture, because '<=' is not reliable
on pointers into different buffers.  (I have the vague recollection
that some compilers even rely on this to generate faster code
on flat architectures....)  More importantly, suppose the
buffer is reallocated (because it grows)?  Won't 'overlap'
do the wrong thing after that?  And it'd be nice if we didn't
have to worry about making a copy of that line.

I'll see if I can come up with something that addresses these
objectinos.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 21:36:32 +0200

Paul Eggert wrote:
> On 08/16/2012 02:03 PM, Jim Meyering wrote:
>> * src/sort.c (saved_line): New static/global, renamed and moved from...
>> (write_unique): ...here.
>
> I see a couple of problems with this patch.  Pedantically,
> the behavior of 'overlap' is undefined on hosts that
> use a segmented architecture, because '<=' is not reliable
> on pointers into different buffers.  (I have the vague recollection
> that some compilers even rely on this to generate faster code
> on flat architectures....)

I pushed the change seconds before your message arrived.
But that's probably best.  If you can change it to do the job
reliably even on fringe systems, that would be welcome.

> More importantly, suppose the
> buffer is reallocated (because it grows)?  Won't 'overlap'
> do the wrong thing after that?

How?  The first time the safe_text buffer is allocated
it will have to be disjoint from the line.text buffer
and from the buffer into which we're about to fread.
Thereafter, regardless of reallocation, overlap should
always be false.

> And it'd be nice if we didn't
> have to worry about making a copy of that line.

It appears that the need to copy a line (overlap)
is very rare, in practice.  If you find a way to avoid it,
it seems like it would have to be small and simple to be
worthwhile.

> I'll see if I can come up with something that addresses these
> objectinos.

Thanks!
And thanks for the review.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Benno Schulenberg <bensberg <at> justemail.net>,
	Bruce Dubbs <bruce.dubbs <at> gmail.com>, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u data loss deserves new release ASAP [Re:
	bug#9780: sort -u...
Date: Fri, 17 Aug 2012 21:40:36 +0200

Jim Meyering wrote:
...
> That sort -u can cause data loss is a big deal.
> I want to make a release with this fix as soon as possible.
> Since I'm making this a mostly-bug-fix release, the du and md5 --tag
> changes will have to wait for 8.20.
> However, I'll be happy to apply documentation-correcting changes
> if someone would post a complete, updated patch or two.

On second thought, these changes would require translation
adjustments.  Thus, I will defer these until after 8.19.

> If Bruce and Paul find that changing gnulib's parse-datetime test
> will avoid a failure on LFS, I'll pull in a gnulib update for that.

Paul fixed it, so I'll update from gnulib shortly.

> Any other bug-fix-like changes that people can suggest?

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 12:41:41 -0700

On 08/17/2012 12:36 PM, Jim Meyering wrote:
> The first time the safe_text buffer is allocated
> it will have to be disjoint from the line.text buffer
> and from the buffer into which we're about to fread.
> Thereafter, regardless of reallocation, overlap should
> always be false.

I haven't thought it through entirely, but I was
worried about the case where there is a saved line
but no saved_text, the buffer is reallocated, and
then we test for overlap.  If the reallocated buffer
does not overlap the original buffer, the test for
overlap will fail even though the saved line needs
to be copied into a new saved_text buffer.

I'll stare at the code some more....

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 21:53:06 +0200

Paul Eggert wrote:

> On 08/17/2012 12:36 PM, Jim Meyering wrote:
>> The first time the safe_text buffer is allocated
>> it will have to be disjoint from the line.text buffer
>> and from the buffer into which we're about to fread.
>> Thereafter, regardless of reallocation, overlap should
>> always be false.
>
> I haven't thought it through entirely, but I was
> worried about the case where there is a saved line
> but no saved_text, the buffer is reallocated, and

That is precisely what happens when this "(unique && ..." condition
is true for the first time (presuming you mean s/saved_text/safe_text/)

          /* With --unique, when we're about to read into a buffer that
             overlaps the saved "preceding" line (saved_line), copy the line's
             .text member to a realloc'd-as-needed temporary buffer and adjust
             the line's key-defining members if they're set.  */
          if (unique && overlap (ptr, readsize, &saved_line))
            {
              /* Copy saved_line.text into a buffer where it won't be clobbered
                 and if KEY is non-NULL, adjust saved_line.key* to match.  */
              static char *safe_text;
              static size_t safe_text_n_alloc;
              if (safe_text_n_alloc < saved_line.length)
                {
                  safe_text_n_alloc = saved_line.length;
                  safe_text = x2nrealloc (safe_text, &safe_text_n_alloc, 1);
                }
              memcpy (safe_text, saved_line.text, saved_line.length);
              if (key)
                {
                  #define s saved_line
                  s.keybeg = safe_text + (s.keybeg - s.text);
                  s.keylim = safe_text + (s.keylim - s.text);
                  #undef s
                }
              saved_line.text = safe_text;
            }

safe_text is initially NULL and we enter that block
only when we're about to fread into a buffer that overlaps
the current saved_line.text buffer.

In that case, we allocate an initial safe_text buffer,
copy saved_line.text into it, and update saved_line.text
to point to the just-allocated/initialized buffer.
Any test of overlap that compares that just-allocated
(or realloc'd) buffer with the about-to-be-fread-into
buffer will return false.

> then we test for overlap.  If the reallocated buffer
> does not overlap the original buffer, the test for
> overlap will fail even though the saved line needs
> to be copied into a new saved_text buffer.
>
> I'll stare at the code some more....

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 13:01:48 -0700

On 08/17/2012 12:53 PM, Jim Meyering wrote:
> safe_text is initially NULL and we enter that block
> only when we're about to fread into a buffer that overlaps
> the current saved_line.text buffer.

Sorry, I wasn't clear enough.  I was worried about the
case when saved_line.text does not overlap the buffer
we're about to read into, because the buffer we're about
to read into has been realloc'ed.  The idea is that we
saved a line, then realloc'ed the buffer, and now we're
doing the overlap test.  There won't be an overlap (assuming
realloc gave us fresh space), but the saved line points
into freed memory.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 22:31:21 +0200

Paul Eggert wrote:
> On 08/17/2012 12:53 PM, Jim Meyering wrote:
>> safe_text is initially NULL and we enter that block
>> only when we're about to fread into a buffer that overlaps
>> the current saved_line.text buffer.
>
> Sorry, I wasn't clear enough.  I was worried about the
> case when saved_line.text does not overlap the buffer
> we're about to read into, because the buffer we're about
> to read into has been realloc'ed.  The idea is that we
> saved a line, then realloc'ed the buffer, and now we're
> doing the overlap test.  There won't be an overlap (assuming
> realloc gave us fresh space), but the saved line points
> into freed memory.

Ohhh.  Good catch.
That is a related, but independent bug.
It also afflicts the code from before today's change.

Here's the part of fillbuf that can realloc "buf->buf",
leaving saved_line.text pointing into freed memory:

          {
            /* The current input line is too long to fit in the buffer.
               Increase the buffer size and try again, keeping it properly
               aligned.  */
            size_t line_alloc = buf->alloc / sizeof (struct line);
            buf->buf = x2nrealloc (buf->buf, &line_alloc, sizeof (struct line));
            buf->alloc = line_alloc * sizeof (struct line);
          }
        }
    }

One way to work around that is to update saved_line.text,
if needed, right after that x2nrealloc call.

Understanding that scenario, it was easy to construct a case
that triggers a free memory read:

    $ perl -le 'print "a\n"."0"x900'|valgrind ./sort --p=1 -S32b -u>/dev/null
    ==5263== Memcheck, a memory error detector
    ==5263== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
    ==5263== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
    ==5263== Command: ./sort --p=1 -S32b -u
    ==5263==
    ==5263== Invalid read of size 1
    ==5263==    at 0x4A0AD1C: bcmp (mc_replace_strmem.c:889)
    ==5263==    by 0x408118: compare (sort.c:2736)
    ==5263==    by 0x408425: write_unique (sort.c:3391)
    ==5263==    by 0x40467A: main (sort.c:3959)
    ==5263==  Address 0x4c34270 is 0 bytes inside a block of size 576 free'd
    ==5263==    at 0x4A0892E: realloc (vg_replace_malloc.c:632)
    ==5263==    by 0x410130: xrealloc (xmalloc.c:63)
    ==5263==    by 0x406C04: fillbuf (sort.c:1857)
    ==5263==    by 0x40462C: main (sort.c:3916)
    ==5263==
    ==5263==
    ==5263== HEAP SUMMARY:
    ==5263==     in use at exit: 128 bytes in 1 blocks
    ==5263==   total heap usage: 23 allocs, 22 frees, 530,779 bytes allocated
    ==5263==
    ==5263== LEAK SUMMARY:
    ==5263==    definitely lost: 0 bytes in 0 blocks
    ==5263==    indirectly lost: 0 bytes in 0 blocks
    ==5263==      possibly lost: 0 bytes in 0 blocks
    ==5263==    still reachable: 128 bytes in 1 blocks
    ==5263==         suppressed: 0 bytes in 0 blocks
    ==5263== Rerun with --leak-check=full to see details of leaked memory
    ==5263==
    ==5263== For counts of detected and suppressed errors, rerun with: -v
    ==5263== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)

So we definitely have a *second* bug here.
Thanks!

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 13:34:55 -0700

OK, I scratched my head for a bit and came up with the following
further patch, which addresses the issues that I mentioned.

From ac405d343c379096c7ed51b481d5ed08ee18d6e0 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 17 Aug 2012 13:26:00 -0700
Subject: [PATCH] sort: simpler fix for sort -u data-loss bug

* src/sort.c (overlap): Remove.
(fillbuf): Do not try to copy saved lines, as that is too risky
in the presence of parallelism, reallocated buffers, etc.
(sort): Invalidate any saved line before sorting a new batch.
---
 src/sort.c |   36 +-----------------------------------
 1 files changed, 1 insertions(+), 35 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index c2d2d49..9dbfee1 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -1705,14 +1705,6 @@ limfield (struct line const *line, struct keyfield const *key)
   return ptr;
 }
 
-/* Return true if LINE and the buffer BUF of length LEN overlap.  */
-static inline bool
-overlap (char const *buf, size_t len, struct line const *line)
-{
-  char const *line_end = line->text + line->length;
-  return !(line_end <= buf || buf + len <= line->text);
-}
-
 /* Fill BUF reading from FP, moving buf->left bytes from the end
    of buf->buf to the beginning first.  If EOF is reached and the
    file wasn't terminated by a newline, supply one.  Set up BUF's line
@@ -1753,33 +1745,6 @@ fillbuf (struct buffer *buf, FILE *fp, char const *file)
              rest of the input file consists entirely of newlines,
              except that the last byte is not a newline.  */
           size_t readsize = (avail - 1) / (line_bytes + 1);
-
-          /* With --unique, when we're about to read into a buffer that
-             overlaps the saved "preceding" line (saved_line), copy the line's
-             .text member to a realloc'd-as-needed temporary buffer and adjust
-             the line's key-defining members if they're set.  */
-          if (unique && overlap (ptr, readsize, &saved_line))
-            {
-              /* Copy saved_line.text into a buffer where it won't be clobbered
-                 and if KEY is non-NULL, adjust saved_line.key* to match.  */
-              static char *safe_text;
-              static size_t safe_text_n_alloc;
-              if (safe_text_n_alloc < saved_line.length)
-                {
-                  safe_text_n_alloc = saved_line.length;
-                  safe_text = x2nrealloc (safe_text, &safe_text_n_alloc, 1);
-                }
-              memcpy (safe_text, saved_line.text, saved_line.length);
-              if (key)
-                {
-                  #define s saved_line
-                  s.keybeg = safe_text + (s.keybeg - s.text);
-                  s.keylim = safe_text + (s.keylim - s.text);
-                  #undef s
-                }
-              saved_line.text = safe_text;
-            }
-
           size_t bytes_read = fread (ptr, 1, readsize, fp);
           char *ptrlim = ptr + bytes_read;
           char *p;
@@ -3928,6 +3893,7 @@ sort (char *const *files, size_t nfiles, char const *output_file,
               break;
             }
 
+          saved_line.text = NULL;
           line = buffer_linelim (&buf);
           if (buf.eof && !nfiles && !ntemps && !buf.left)
             {
-- 
1.7.6.5

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 13:38:34 -0700

On 08/17/2012 01:31 PM, Jim Meyering wrote:
> So we definitely have a *second* bug here.

Yes, I noticed.  It definitely counts as a double-ouch.
I'm glad the bug report prompted us to read this code
more carefully.

My latest patch should fix both bugs.

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 23:09:15 +0200

Paul Eggert wrote:
> OK, I scratched my head for a bit and came up with the following
> further patch, which addresses the issues that I mentioned.
...
> Subject: [PATCH] sort: simpler fix for sort -u data-loss bug
>
> * src/sort.c (overlap): Remove.
> (fillbuf): Do not try to copy saved lines, as that is too risky
> in the presence of parallelism, reallocated buffers, etc.
> (sort): Invalidate any saved line before sorting a new batch.
> ---
>  src/sort.c |   36 +-----------------------------------

Very nice!  That fixes not just the original bug, but also the FMR,
and eliminates my entire patch.  The only cost is in writing at most
one more line per buffer.

I hate to look such a nice gift horse in the mouth, but it's getting
late here...  Would you mind adjusting that to add NEWS and mention that
you've fixed the second, free-memory-read bug, too?

And even add the test?
If you don't find time, I'll get to that over the weekend.

===============
Regarding your patch...

For the record, at first I thought an input that used one (long) line per
buffer would make --unique a no-op, but then I realized that in that case,
each buffers-worth (one line each) would be written to its own temporary
file, and the merge phase would handle the --unique semantics.

Thanks again!

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

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Sat, 18 Aug 2012 07:40:53 +0200

Paul Eggert wrote:
> OK, I scratched my head for a bit and came up with the following
> further patch, which addresses the issues that I mentioned.
>
> Subject: [PATCH] sort: simpler fix for sort -u data-loss bug
>
> * src/sort.c (overlap): Remove.
> (fillbuf): Do not try to copy saved lines, as that is too risky
> in the presence of parallelism, reallocated buffers, etc.
> (sort): Invalidate any saved line before sorting a new batch.

Hi Paul,

I've adjusted your commit log to look like this.
Is that ok with you?

commit eb6427938ffe009ca7d8bcb4fc768bb9bc6bd135
Author: Paul Eggert <eggert <at> cs.ucla.edu>
Date:   Fri Aug 17 13:26:00 2012 -0700

    sort: simpler fix for sort -u data-loss bug, and for a FMR bug

    This also fixes a free-memory-read (FMR) bug: when fillbuf's realloc
    of buf->buf frees the buffer into which saved_line.text points,
    the processing of that just-read longer line includes comparison
    against the saved line in freed memory.
    * src/sort.c (overlap): Remove.
    (fillbuf): Do not try to copy saved lines, as that is too risky
    in the presence of parallelism, reallocated buffers, etc.
    (sort): Invalidate any saved line before sorting a new batch.

I've also written these two commits:

      tests: wrap the valgrind-requiring assertion in a function
      tests: trigger the sort -u free-memory-read bug

 -----
 NEWS                             |    5 +++++
 tests/Makefile.am                |    1 +
 tests/init.cfg                   |    6 ++++++
 tests/misc/sort                  |    4 ++++
 tests/misc/sort-stale-thread-mem |    2 +-
 tests/misc/sort-u-FMR            |   29 +++++++++++++++++++++++++++++
 6 files changed, 46 insertions(+), 1 deletion(-)

From d46873d2eb35f4fa6e735c1e094613fb0ae0dadb Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering <at> redhat.com>
Date: Sat, 18 Aug 2012 07:25:28 +0200
Subject: [PATCH 1/2] tests: wrap the valgrind-requiring assertion in a
 function

* tests/init.cfg (require_valgrind_): New function...
* tests/misc/sort-stale-thread-mem: ...extracted from here.
---
 tests/init.cfg                   | 6 ++++++
 tests/misc/sort-stale-thread-mem | 2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/tests/init.cfg b/tests/init.cfg
index 4ff5ad4..f223f13 100644
--- a/tests/init.cfg
+++ b/tests/init.cfg
@@ -160,6 +160,12 @@ require_strace_()
   fi
 }

+# Skip the current test if valgrind doesn't work.
+require_valgrind_()
+{
+  valgrind --help >/dev/null || skip_ "requires valgrind"
+}
+
 require_setfacl_()
 {
   setfacl -m user::rwx . \
diff --git a/tests/misc/sort-stale-thread-mem b/tests/misc/sort-stale-thread-mem
index c19f62e..05cc9ba 100755
--- a/tests/misc/sort-stale-thread-mem
+++ b/tests/misc/sort-stale-thread-mem
@@ -22,8 +22,8 @@
 print_ver_ sort

 very_expensive_
+require_valgrind_

-valgrind --help >/dev/null || skip_ "requires valgrind"
 grep '^#define HAVE_PTHREAD_T 1' "$CONFIG_HEADER" > /dev/null ||
   skip_ 'requires pthreads'

--
1.7.12.rc2


From d33e68da52bd0457acdc861ab2effba4f45a71fc Mon Sep 17 00:00:00 2001
From: Jim Meyering <meyering <at> redhat.com>
Date: Sat, 18 Aug 2012 07:26:30 +0200
Subject: [PATCH 2/2] tests: trigger the sort -u free-memory-read bug

* tests/misc/sort-u-FMR: New file.
* tests/Makefile.am (TESTS): Add it.
* tests/misc/sort: Add the test here, too.
* NEWS (Bug fixes): Mention it.
---
 NEWS                  |  5 +++++
 tests/Makefile.am     |  1 +
 tests/misc/sort       |  4 ++++
 tests/misc/sort-u-FMR | 29 +++++++++++++++++++++++++++++
 4 files changed, 39 insertions(+)
 create mode 100755 tests/misc/sort-u-FMR

diff --git a/NEWS b/NEWS
index f39a76a..1737235 100644
--- a/NEWS
+++ b/NEWS
@@ -14,6 +14,11 @@ GNU coreutils NEWS                                    -*- outline -*-
   (yes 7 | head -11; echo 1) | sort --p=1 -S32b -u
   [bug introduced in coreutils-8.6]

+  sort -u could read freed memory.
+  For example, this evokes a read from freed memory:
+  perl -le 'print "a\n"."0"x900'|valgrind sort --p=1 -S32b -u>/dev/null
+  [bug introduced in coreutils-8.6]
+
 ** New features

   rm now accepts the --dir (-d) option which makes it remove empty directories.
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 09d2658..69078bd 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -260,6 +260,7 @@ TESTS =						\
   misc/sort-unique-segv				\
   misc/sort-version				\
   misc/sort-NaN-infloop				\
+  misc/sort-u-FMR				\
   split/filter					\
   split/suffix-auto-length			\
   split/suffix-length				\
diff --git a/tests/misc/sort b/tests/misc/sort
index 4e51161..894a59a 100755
--- a/tests/misc/sort
+++ b/tests/misc/sort
@@ -237,6 +237,10 @@ my @Tests =
   {IN=>"a 7\n"x10 . "b 1\n"}, {OUT=>"b 1\na 7\n"}],
 ["unique-key-x86_64", '-u -k2,2 --p=1 -S32b',
   {IN=>"a 7\n"x11 . "b 1\n"}, {OUT=>"b 1\na 7\n"}],
+# Before 8.19, this would trigger a free-memory read.
+["unique-free-mem-read", '-u --p=1 -S32b',
+  {IN=>"a\n"."b\n"x900},
+ {OUT=>"a\n"."b\n"x900}],

 # From Erick Branderhorst -- fixed around 1.19e
 ["16a", '-f',
diff --git a/tests/misc/sort-u-FMR b/tests/misc/sort-u-FMR
new file mode 100755
index 0000000..303b429
--- /dev/null
+++ b/tests/misc/sort-u-FMR
@@ -0,0 +1,29 @@
+#!/bin/sh
+# Before 8.19, this would trigger a free-memory read.
+
+# Copyright (C) 2012 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 <http://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+print_ver_ sort
+require_valgrind_
+
+{ echo 0; printf '%0900d\n' 1; } > in || framework_failure_
+
+valgrind --error-exitcode=1 sort --p=1 -S32b -u in > out || fail=1
+
+compare in out || fail=1
+
+Exit $fail
--
1.7.12.rc2

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 9780 <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Fri, 17 Aug 2012 22:47:33 -0700

On 08/17/2012 10:40 PM, Jim Meyering wrote:
> I've adjusted your commit log to look like this.
> Is that ok with you?

Sure, that all looks good.  Thanks for doing that.

Message #96 received at 9780-done <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 9780-done <at> debbugs.gnu.org, Rasmus Borup Hansen <rbh <at> intomics.com>
Subject: Re: bug#9780: sort -u throws out non-duplicates
Date: Mon, 20 Aug 2012 21:20:23 +0200

Paul Eggert wrote:
> On 08/17/2012 01:31 PM, Jim Meyering wrote:
>> So we definitely have a *second* bug here.
>
> Yes, I noticed.  It definitely counts as a double-ouch.
> I'm glad the bug report prompted us to read this code
> more carefully.
>
> My latest patch should fix both bugs.

Thanks again.
Closing this bug, finally.

Previous Next

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