bug#7597: multi-threaded sort can segfault (unrelated to the sort -u segfault)

[Jim Meyering]

[I've retitled and Cc'd bug-coreutils so this gets its own bug number]

Chen Guo wrote:
> On Tue, Dec 7, 2010 at 3:24 AM, Jim Meyering <address@hidden> wrote:
>> Thanks.  What does your input file look like?
>> I've been unable to reproduce the failure using the output of
>> seq 1000000.  I've tried a few different -S ... options, in case
>> the amount of available memory is a factor:
>>
>>  seq 1000000 > in-1M
>>  for i in $(seq 1000); do \
>>    printf '%03d\r' $i; src/sort --parallel=2 -S 1M in-1M > /dev/null; done
>
> The input file I used was generated with gensort
> (http://www.ordinal.com/gensort.html)
> I used the -a 1000000 to generate a 1 million line ASCII file. Running
> sort 10 times on 2 or 4 threads almost always triggered at least 1
> segfault.

Thank you.
With that, I've solved at least part of the problem.
The segfault (and other strangeness we've witnessed)
arises because each "node" struct is stored on the stack,
and its address ends up being used by another thread after
the thread that owns the stack in question has been "joined".

My solution is to use the heap instead of the stack.
However, for today I'm out of time and I have not yet found a
way to free these newly-malloc'd "node" buffers.

To test this, I've done the following:

gensort -a 10000 > gensort-10k
for i in $(seq 2000); do printf '% 4d\n' $i; valgrind --quiet src/sort -S 100K \
  --parallel=2 gensort-10k > k; test $(wc -c < k) = 1000000 || break; done
for i in $(seq 2000); do printf '% 4d\n' $i; src/sort -S 100K \
  --parallel=2 gensort-10k > j; test $(wc -c < j) = 1000000 || break; done

Without the patch, the first would show errors for more than 50% of
the runs and the second would rarely get to i=100 without generating
a core file.  With the patch, both complete error-free (not counting
leaks).

I'll add tests and a NEWS item, eventually.

>From e3a0cb08ebcb7ad6638d022418488c1085838fc3 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Thu, 9 Dec 2010 12:12:53 +0100
Subject: [PATCH] sort: avoid segfault when using two or more threads

* src/sort.c (sortlines, sort): Store each "node" structure on
the heap, not on the stack.  Otherwise, a node from one thread's
stack could be used in another thread after the first thread had
expired (via pthread_join).
---
 src/sort.c |   56 ++++++++++++++++++++++++++++----------------------------
 1 files changed, 28 insertions(+), 28 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 742971e..9a7ecd4 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3471,28 +3471,28 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
   struct line *hi = lo - nlo;
   struct line **parent_end = lo_child ? &parent->end_lo : &parent->end_hi;

-  struct merge_node node;
-  node.lo = node.end_lo = lo;
-  node.hi = node.end_hi = hi;
-  node.dest = parent_end;
-  node.nlo = nlo;
-  node.nhi = nhi;
-  node.parent = parent;
-  node.level = parent->level + 1;
-  node.queued = false;
-  pthread_mutex_init (&node.lock, NULL);
+  struct merge_node *node = xmalloc (sizeof *node);
+  node->lo = node->end_lo = lo;
+  node->hi = node->end_hi = hi;
+  node->dest = parent_end;
+  node->nlo = nlo;
+  node->nhi = nhi;
+  node->parent = parent;
+  node->level = parent->level + 1;
+  node->queued = false;
+  pthread_mutex_init (&node->lock, NULL);

   /* Calculate thread arguments. */
   unsigned long int lo_threads = nthreads / 2;
   unsigned long int hi_threads = nthreads - lo_threads;
   pthread_t thread;
-  struct thread_args args = {lines, lo, lo_threads, total_lines, &node,
+  struct thread_args args = {lines, lo, lo_threads, total_lines, node,
                              true, queue, tfp, temp_output};

   if (nthreads > 1 && SUBTHREAD_LINES_HEURISTIC <= nlines
       && pthread_create (&thread, NULL, sortlines_thread, &args) == 0)
     {
-      sortlines (lines - nlo, hi, hi_threads, total_lines, &node, false,
+      sortlines (lines - nlo, hi, hi_threads, total_lines, node, false,
                  queue, tfp, temp_output);
       pthread_join (thread, NULL);
     }
@@ -3507,16 +3507,16 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
         sequential_sort (lines, nlo, temp, false);

       /* Update merge NODE. No need to lock yet. */
-      node.lo = lines;
-      node.hi = lines - nlo;
-      node.end_lo = lines - nlo;
-      node.end_hi = lines - nlo - nhi;
+      node->lo = lines;
+      node->hi = lines - nlo;
+      node->end_lo = lines - nlo;
+      node->end_hi = lines - nlo - nhi;

-      queue_insert (queue, &node);
+      queue_insert (queue, node);
       merge_loop (queue, total_lines, tfp, temp_output);
     }

-  pthread_mutex_destroy (&node.lock);
+  pthread_mutex_destroy (&node->lock);
 }

 /* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3793,19 +3793,19 @@ sort (char *const *files, size_t nfiles, char const 
*output_file,
               struct merge_node_queue queue;
               queue_init (&queue, 2 * nthreads);

-              struct merge_node node;
-              node.lo = node.hi = node.end_lo = node.end_hi = NULL;
-              node.dest = NULL;
-              node.nlo = node.nhi = buf.nlines;
-              node.parent = NULL;
-              node.level = MERGE_END;
-              node.queued = false;
-              pthread_mutex_init (&node.lock, NULL);
+              struct merge_node *node = xmalloc (sizeof *node);
+              node->lo = node->hi = node->end_lo = node->end_hi = NULL;
+              node->dest = NULL;
+              node->nlo = node->nhi = buf.nlines;
+              node->parent = NULL;
+              node->level = MERGE_END;
+              node->queued = false;
+              pthread_mutex_init (&node->lock, NULL);

-              sortlines (line, line, nthreads, buf.nlines, &node, true,
+              sortlines (line, line, nthreads, buf.nlines, node, true,
                          &queue, tfp, temp_output);
               queue_destroy (&queue);
-              pthread_mutex_destroy (&node.lock);
+              pthread_mutex_destroy (&node->lock);
             }
           else
             write_unique (line - 1, tfp, temp_output);
--
1.7.3.3