bug#9780: sort -u throws out non-duplicates

[Jim Meyering]

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 <address@hidden>
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 <address@hidden>
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 <address@hidden>
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