Subject: bug#7489: [coreutils] over aggressive threads in sort

From: Jim Meyering <[email-masked]>
Date: Mon, 29 Nov 2010 21:09:30 +0100

Paul Eggert wrote:
> Could you please try this little patch?  It should fix your
> problem.  I came up with this fix in my sleep (literally!
> I woke up this morning and the patch was in my head), but
> haven't had time to look at the code in this area to see
> if it's the best fix.
>
> Clearly there's at least one more bug as noted in my previous email
> <http://lists.gnu.org/archive/html/bug-coreutils/2010-11/msg00216.html>
> but I expect it's less likely to fire.
>
> diff --git a/src/sort.c b/src/sort.c
> index 7e25f6a..1aa1eb4 100644
> --- a/src/sort.c
> +++ b/src/sort.c
> @@ -3226,13 +3226,13 @@ queue_pop (struct merge_node_queue *queue)
>  static void
>  write_unique (struct line const *line, FILE *tfp, char const *temp_output)
>  {
> -  static struct line const *saved = NULL;
> +  static struct line saved;
>
>    if (!unique)
>      write_line (line, tfp, temp_output);
> -  else if (!saved || compare (line, saved))
> +  else if (!saved.text || compare (line, &saved))
>      {
> -      saved = line;
> +      saved = *line;
>        write_line (line, tfp, temp_output);
>      }
>  }

Nice.
That looks right to me.

FYI, what happens is the first fillbuf call gets a block
of lines, and "saved" ends up pointing at one of them.
The second fillbuf's fread races to overwrite a byte or two of the
saved->text pointer that is being dereferenced by the other thread.

The patch below adds a small test case to exercise it.
It demonstrates the failure in all but ~20 trials out of 1000 for me.
So far, I've reproduced this only on multi-core systems, with --parallel=2.

>From 3b8f453a325fbd094e2605347b1d8a05efab9b0d Mon Sep 17 00:00:00 2001
From: Jim Meyering <[email-masked]>
Date: Sun, 28 Nov 2010 12:59:38 +0100
Subject: [PATCH] tests: add test for parallel sort -u segfault bug

* tests/misc/sort-unique-segv: New file.
* tests/Makefile.am (TESTS): Add it.
---
 tests/Makefile.am           |    1 +
 tests/misc/sort-unique-segv |   55 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+), 0 deletions(-)
 create mode 100755 tests/misc/sort-unique-segv

diff --git a/tests/Makefile.am b/tests/Makefile.am
index b3be4df..d52f677 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -239,6 +239,7 @@ TESTS =						\
   misc/sort-rand				\
   misc/sort-spinlock-abuse			\
   misc/sort-unique				\
+  misc/sort-unique-segv				\
   misc/sort-version				\
   misc/split-a					\
   misc/split-bchunk				\
diff --git a/tests/misc/sort-unique-segv b/tests/misc/sort-unique-segv
new file mode 100755
index 0000000..0a1d4cb
--- /dev/null
+++ b/tests/misc/sort-unique-segv
@@ -0,0 +1,55 @@
+#!/bin/sh
+# parallel sort with --unique (-u) would segfault
+
+# Copyright (C) 2010 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
+
+test "$(nproc)" = 1 && skip_ "requires a multi-core system"
+
+cat <<\EOF > in || framework_failure_
+
+
+
+
+
+
+
+z
+zzzzzz
+zzzzzzz
+zzzzzzz
+zzzzzzz
+zzzzzzzzz
+zzzzzzzzzzz
+zzzzzzzzzzzz
+EOF
+
+cat <<\EOF > exp || fail=1
+
+z
+zzzzzz
+zzzzzzz
+zzzzzzzzz
+zzzzzzzzzzz
+zzzzzzzzzzzz
+EOF
+
+sort --parallel=2 -u -S 10b < in > out || fail=1
+compare out exp || fail=1
+
+Exit $fail
--
1.7.3.2.846.gf4b062