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

[Paul Eggert]

Thanks, Chen, that was much nicer than what I was writing.
I did some minor cleanups, mostly to do with catching an
unlikely integer overflow that would have made 'sort' crash badly,
and pushed the following set of patches.

>From 780831a8602d9cdc22e7dcf44804e9c7183dd944 Mon Sep 17 00:00:00 2001
From: Chen Guo <address@hidden>
Date: Mon, 6 Dec 2010 00:15:42 -0800
Subject: [PATCH 1/4] sort: use mutexes, not spinlocks (avoid busy loop on 
blocked output)

Running a command like this on a multi-core system
  sort < big-file | less
would peg all processors at near 100% utilization.
* src/sort.c: (struct merge_node) Change member lock to mutex.
All uses changed.
* tests/Makefile.am (XFAIL_TESTS): Remove definition, now that
this test passes once again.  I.e., the sort-spinlock-abuse test
no longer fails.
* NEWS (Bug reports): Mention this.
Reported by DJ Lucas in http://debbugs.gnu.org/7489.
---
 NEWS              |    5 +++++
 src/sort.c        |   14 +++++++-------
 tests/Makefile.am |    3 ---
 3 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/NEWS b/NEWS
index c3110a3..9f55cbb 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,11 @@ GNU coreutils NEWS                                    -*- 
outline -*-
   sort -u with at least two threads could attempt to read through a
   corrupted pointer. [bug introduced in coreutils-8.6]
 
+  sort with at least two threads and with blocked output would busy-loop
+  (spinlock) all threads, often using 100% of available CPU cycles to
+  do no work.  I.e., "sort < big-file | less" could waste a lot of power.
+  [bug introduced in coreutils-8.6]
+
 ** New features
 
   split accepts the --number option to generate a specific number of files.
diff --git a/src/sort.c b/src/sort.c
index a4c2cbf..9cfc814 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -241,7 +241,7 @@ struct merge_node
   struct merge_node *parent;    /* Parent node. */
   unsigned int level;           /* Level in merge tree. */
   bool queued;                  /* Node is already in heap. */
-  pthread_spinlock_t lock;      /* Lock for node operations. */
+  pthread_mutex_t lock;         /* Lock for node operations. */
 };
 
 /* Priority queue of merge nodes. */
@@ -3157,7 +3157,7 @@ compare_nodes (void const *a, void const *b)
 static inline void
 lock_node (struct merge_node *node)
 {
-  pthread_spin_lock (&node->lock);
+  pthread_mutex_lock (&node->lock);
 }
 
 /* Unlock a merge tree NODE. */
@@ -3165,7 +3165,7 @@ lock_node (struct merge_node *node)
 static inline void
 unlock_node (struct merge_node *node)
 {
-  pthread_spin_unlock (&node->lock);
+  pthread_mutex_unlock (&node->lock);
 }
 
 /* Destroy merge QUEUE. */
@@ -3479,7 +3479,7 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
   node.parent = parent;
   node.level = parent->level + 1;
   node.queued = false;
-  pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
+  pthread_mutex_init (&node.lock, NULL);
 
   /* Calculate thread arguments. */
   unsigned long int lo_threads = nthreads / 2;
@@ -3515,7 +3515,7 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
       merge_loop (queue, total_lines, tfp, temp_output);
     }
 
-  pthread_spin_destroy (&node.lock);
+  pthread_mutex_destroy (&node.lock);
 }
 
 /* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3799,12 +3799,12 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
               node.parent = NULL;
               node.level = MERGE_END;
               node.queued = false;
-              pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
+              pthread_mutex_init (&node.lock, NULL);
 
               sortlines (line, line, nthreads, buf.nlines, &node, true,
                          &queue, tfp, temp_output);
               queue_destroy (&queue);
-              pthread_spin_destroy (&node.lock);
+              pthread_mutex_destroy (&node.lock);
             }
           else
             write_unique (line - 1, tfp, temp_output);
diff --git a/tests/Makefile.am b/tests/Makefile.am
index d52f677..b573061 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -656,7 +656,4 @@ pr_data =                                   \
   pr/ttb3-FF                                   \
   pr/w72l24f-ll
 
-XFAIL_TESTS =                                  \
-  misc/sort-spinlock-abuse
-
 include $(srcdir)/check.mk
-- 
1.7.2


>From bcf9043b1f3983d099672047b36ad0a371af169d Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 10 Dec 2010 20:52:04 -0800
Subject: [PATCH 2/4] sort: comment fix

* src/sort.c: Comment fix re spin locks.
---
 src/sort.c |    7 +------
 1 files changed, 1 insertions(+), 6 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 9cfc814..36e3b19 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3149,10 +3149,7 @@ compare_nodes (void const *a, void const *b)
   return nodea->level < nodeb->level;
 }
 
-/* Lock a merge tree NODE.
-   Spin locks were seen to perform better than mutexes when the number
-   of threads is limited to the number of processors, assuming 'sort'
-   never waits when writing to stdout.  */
+/* Lock a merge tree NODE.  */
 
 static inline void
 lock_node (struct merge_node *node)
@@ -4567,8 +4564,6 @@ main (int argc, char **argv)
     }
   else
     {
-      /* If NTHREADS > number of cores on the machine, spinlocking
-         could be wasteful.  */
       unsigned long int np2 = num_processors (NPROC_CURRENT_OVERRIDABLE);
       if (!nthreads || nthreads > np2)
         nthreads = np2;
-- 
1.7.2


>From a1f8177972fb3f864847dc45237ad7d4d6a7f395 Mon Sep 17 00:00:00 2001
From: Chen Guo <address@hidden>
Date: Fri, 10 Dec 2010 13:13:36 -0800
Subject: [PATCH 3/4] sort: preallocate merge tree nodes to heap.

* src/sort.c: (merge_tree_init) New function. Allocates memory for
merge tree nodes.
(merge_tree_destory) New function.
(init_node) New function.
(sortlines) Refactor node creation code to init_node. Remove now
superfluous arguments. All callers changed.
(sort) Initialize/destory merge tree. Refactor root node creation
to merge_tree_init.
---
 src/sort.c |  170 +++++++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 111 insertions(+), 59 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 36e3b19..b724f3d 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -239,6 +239,8 @@ struct merge_node
   size_t nlo;                   /* Total Lines remaining from LO. */
   size_t nhi;                   /* Total lines remaining from HI. */
   struct merge_node *parent;    /* Parent node. */
+  struct merge_node *lo_child;  /* LO child node. */
+  struct merge_node *hi_child;  /* HI child node. */
   unsigned int level;           /* Level in merge tree. */
   bool queued;                  /* Node is already in heap. */
   pthread_mutex_t lock;         /* Lock for node operations. */
@@ -3137,6 +3139,83 @@ sequential_sort (struct line *restrict lines, size_t 
nlines,
     }
 }
 
+struct merge_node * init_node (struct merge_node *, struct merge_node *,
+                               struct line *restrict, unsigned long int,
+                               size_t, bool);
+
+
+/* Initialize the merge tree. */
+static struct merge_node *
+merge_tree_init (unsigned long int nthreads, size_t nlines,
+                 struct line *restrict dest)
+{
+  struct merge_node *merge_tree = xmalloc (2 * nthreads * sizeof *merge_tree);
+
+  struct merge_node *root_node = merge_tree;
+  root_node->lo = root_node->hi = root_node->end_lo = root_node->end_hi = NULL;
+  root_node->dest = NULL;
+  root_node->nlo = root_node->nhi = nlines;
+  root_node->parent = NULL;
+  root_node->level = MERGE_END;
+  root_node->queued = false;
+  pthread_mutex_init (&root_node->lock, NULL);
+
+  init_node (root_node, root_node + 1, dest, nthreads, nlines, false);
+  return merge_tree;
+}
+
+/* Destroy the merge tree. */
+static void
+merge_tree_destroy (struct merge_node *merge_tree)
+{
+  free (merge_tree);
+}
+
+/* Initialize a merge tree node. */
+
+struct merge_node *
+init_node (struct merge_node *parent, struct merge_node *node_pool,
+           struct line *restrict dest, unsigned long int nthreads,
+           size_t total_lines, bool lo_child)
+{
+  size_t nlines = (lo_child)? parent->nlo : parent->nhi;
+  size_t nlo = nlines / 2;
+  size_t nhi = nlines - nlo;
+  struct line *lo = dest - total_lines;
+  struct line *hi = lo - nlo;
+  struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
+
+  struct merge_node *node = node_pool++;
+  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);
+
+  if (nthreads > 1)
+    {
+      unsigned long int lo_threads = nthreads / 2;
+      unsigned long int hi_threads = nthreads - lo_threads;
+      node->lo_child = node_pool;
+      node_pool = init_node (node, node_pool, lo, lo_threads,
+                             total_lines, true);
+      node->hi_child = node_pool;
+      node_pool = init_node (node, node_pool, hi, hi_threads,
+                             total_lines, false);
+    }
+  else
+    {
+      node->lo_child = NULL;
+      node->hi_child = NULL;
+    }
+  return node_pool;
+}
+
+
 /* Compare two merge nodes A and B for priority.  */
 
 static int
@@ -3375,10 +3454,8 @@ merge_loop (struct merge_node_queue *queue,
 }
 
 
-static void sortlines (struct line *restrict, struct line *restrict,
-                       unsigned long int, size_t,
-                       struct merge_node *, bool,
-                       struct merge_node_queue *,
+static void sortlines (struct line *restrict, unsigned long int, size_t,
+                       struct merge_node *, bool, struct merge_node_queue *,
                        FILE *, char const *);
 
 /* Thread arguments for sortlines_thread. */
@@ -3389,19 +3466,15 @@ struct thread_args
      the end of the array.  */
   struct line *lines;
 
-  /* Destination, i.e., the array of lines to store result into.  This
-     also points just past the end of the array.  */
-  struct line *dest;
-
   /* Number of threads to use.  If 0 or 1, sort single-threaded.  */
   unsigned long int nthreads;
 
   /* Number of lines in LINES and DEST.  */
   size_t const total_lines;
 
-  /* Parent node; it will merge this node's output to the output
-     of this node's sibling.  */
-  struct merge_node *const parent;
+  /* Merge node. Lines from this node and this node's sibling will merged
+     to this node's parent. */
+  struct merge_node *const node;
 
   /* True if this node is sorting the lower half of the parent's work.  */
   bool lo_child;
@@ -3422,9 +3495,9 @@ static void *
 sortlines_thread (void *data)
 {
   struct thread_args const *args = data;
-  sortlines (args->lines, args->dest, args->nthreads, args->total_lines,
-             args->parent, args->lo_child, args->queue,
-             args->tfp, args->output_temp);
+  sortlines (args->lines, args->nthreads, args->total_lines,
+             args->node, args->lo_child, args->queue, args->tfp,
+             args->output_temp);
   return NULL;
 }
 
@@ -3453,49 +3526,32 @@ sortlines_thread (void *data)
    have been merged. */
 
 static void
-sortlines (struct line *restrict lines, struct line *restrict dest,
-           unsigned long int nthreads, size_t total_lines,
-           struct merge_node *parent, bool lo_child,
-           struct merge_node_queue *queue,
-           FILE *tfp, char const *temp_output)
+sortlines (struct line *restrict lines, unsigned long int nthreads,
+           size_t total_lines, struct merge_node *node, bool lo_child,
+           struct merge_node_queue *queue, FILE *tfp, char const *temp_output)
 {
-  /* Create merge tree NODE. */
-  size_t nlines = (lo_child)? parent->nlo : parent->nhi;
-  size_t nlo = nlines / 2;
-  size_t nhi = nlines - nlo;
-  struct line *lo = dest - total_lines;
-  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);
+  size_t nlines = node->nlo + node->nhi;
 
   /* 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,
-                             true, queue, tfp, temp_output};
+  struct thread_args args = {lines, lo_threads, total_lines,
+                             node->lo_child, 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,
-                 queue, tfp, temp_output);
+      sortlines (lines - node->nlo, hi_threads, total_lines,
+                 node->hi_child, false, queue, tfp, temp_output);
       pthread_join (thread, NULL);
     }
   else
     {
       /* Nthreads = 1, this is a leaf NODE, or pthread_create failed.
          Sort with 1 thread. */
+      size_t nlo = node->nlo;
+      size_t nhi = node->nhi;
       struct line *temp = lines - total_lines;
       if (1 < nhi)
         sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);
@@ -3503,16 +3559,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
@@ -3788,20 +3844,16 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
             {
               struct merge_node_queue queue;
               queue_init (&queue, 2 * nthreads);
+              struct merge_node *merge_tree =
+                merge_tree_init (nthreads, buf.nlines, line);
+              struct merge_node *end_node = merge_tree;
+              struct merge_node *root_node = merge_tree + 1;
 
-              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);
-
-              sortlines (line, line, nthreads, buf.nlines, &node, true,
-                         &queue, tfp, temp_output);
+              sortlines (line, nthreads, buf.nlines, root_node,
+                         true, &queue, tfp, temp_output);
               queue_destroy (&queue);
-              pthread_mutex_destroy (&node.lock);
+              pthread_mutex_destroy (&root_node->lock);
+              merge_tree_destroy (merge_tree);
             }
           else
             write_unique (line - 1, tfp, temp_output);
-- 
1.7.2


>From 8413953717970bc1cf33c52a5882489717304624 Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Sat, 11 Dec 2010 00:27:05 -0800
Subject: [PATCH 4/4] sort: integer overflow checks in thread counts, etc.

* src/sort.c (specify_nthreads, merge_tree_init, init_node):
(queue_init, sortlines, struct thread_args, sort, main):
Use size_t, not unsigned long int, for thread counts, since thread
counts are now used to compute sizes.
(specify_nthreads): Check for size_t overflow.
(merge_tree_init, sort): Shorten name of local variable, for
readability.
(merge_tree_init): Move constants next to each other in product,
so that the constant folding is easier to see.
(init_node): Now static.  Add 'restrict' only where it might
be helpful for compiler optimization.
(queue_init): 2nd arg is now nthreads, not "reserve", which is
a bit harder to follow.  All uses changed.
(struct thread_args): Rename lo_child to is_lo_child, so that
it's obvious to the reader when we're talking about this boolean
as opposed to the new lo_child member of the other structure.
All uses changed.
(sort): Remove unused local variable end_node.
(main): Don't allow large thread counts to cause undefined behavior
later, due to integer overflow.
---
 src/sort.c |  115 +++++++++++++++++++++++++++++++++--------------------------
 1 files changed, 64 insertions(+), 51 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index b724f3d..2c0f852 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -1379,15 +1379,17 @@ specify_sort_size (int oi, char c, char const *s)
 }
 
 /* Specify the number of threads to spawn during internal sort.  */
-static unsigned long int
+static size_t
 specify_nthreads (int oi, char c, char const *s)
 {
   unsigned long int nthreads;
   enum strtol_error e = xstrtoul (s, NULL, 10, &nthreads, "");
   if (e == LONGINT_OVERFLOW)
-    return ULONG_MAX;
+    return SIZE_MAX;
   if (e != LONGINT_OK)
     xstrtol_fatal (e, oi, c, long_options, s);
+  if (SIZE_MAX < nthreads)
+    nthreads = SIZE_MAX;
   if (nthreads == 0)
     error (SORT_FAILURE, 0, _("number in parallel must be nonzero"));
   return nthreads;
@@ -3139,28 +3141,28 @@ sequential_sort (struct line *restrict lines, size_t 
nlines,
     }
 }
 
-struct merge_node * init_node (struct merge_node *, struct merge_node *,
-                               struct line *restrict, unsigned long int,
-                               size_t, bool);
+static struct merge_node *init_node (struct merge_node *restrict,
+                                     struct merge_node *restrict,
+                                     struct line *, size_t, size_t, bool);
 
 
-/* Initialize the merge tree. */
+/* Create and return a merge tree for NTHREADS threads, sorting NLINES
+   lines, with destination DEST.  */
 static struct merge_node *
-merge_tree_init (unsigned long int nthreads, size_t nlines,
-                 struct line *restrict dest)
+merge_tree_init (size_t nthreads, size_t nlines, struct line *dest)
 {
-  struct merge_node *merge_tree = xmalloc (2 * nthreads * sizeof *merge_tree);
-
-  struct merge_node *root_node = merge_tree;
-  root_node->lo = root_node->hi = root_node->end_lo = root_node->end_hi = NULL;
-  root_node->dest = NULL;
-  root_node->nlo = root_node->nhi = nlines;
-  root_node->parent = NULL;
-  root_node->level = MERGE_END;
-  root_node->queued = false;
-  pthread_mutex_init (&root_node->lock, NULL);
-
-  init_node (root_node, root_node + 1, dest, nthreads, nlines, false);
+  struct merge_node *merge_tree = xmalloc (2 * sizeof *merge_tree * nthreads);
+
+  struct merge_node *root = merge_tree;
+  root->lo = root->hi = root->end_lo = root->end_hi = NULL;
+  root->dest = NULL;
+  root->nlo = root->nhi = nlines;
+  root->parent = NULL;
+  root->level = MERGE_END;
+  root->queued = false;
+  pthread_mutex_init (&root->lock, NULL);
+
+  init_node (root, root + 1, dest, nthreads, nlines, false);
   return merge_tree;
 }
 
@@ -3171,19 +3173,25 @@ merge_tree_destroy (struct merge_node *merge_tree)
   free (merge_tree);
 }
 
-/* Initialize a merge tree node. */
+/* Initialize a merge tree node and its descendants.  The node's
+   parent is PARENT.  The node and its descendants are taken from the
+   array of nodes NODE_POOL.  Their destination starts at DEST; they
+   will consume NTHREADS threads.  The total number of sort lines is
+   TOTAL_LINES.  IS_LO_CHILD is true if the node is the low child of
+   its parent.  */
 
-struct merge_node *
-init_node (struct merge_node *parent, struct merge_node *node_pool,
-           struct line *restrict dest, unsigned long int nthreads,
-           size_t total_lines, bool lo_child)
+static struct merge_node *
+init_node (struct merge_node *restrict parent,
+           struct merge_node *restrict node_pool,
+           struct line *dest, size_t nthreads,
+           size_t total_lines, bool is_lo_child)
 {
-  size_t nlines = (lo_child)? parent->nlo : parent->nhi;
+  size_t nlines = (is_lo_child ? parent->nlo : parent->nhi);
   size_t nlo = nlines / 2;
   size_t nhi = nlines - nlo;
   struct line *lo = dest - total_lines;
   struct line *hi = lo - nlo;
-  struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
+  struct line **parent_end = (is_lo_child ? &parent->end_lo : &parent->end_hi);
 
   struct merge_node *node = node_pool++;
   node->lo = node->end_lo = lo;
@@ -3198,8 +3206,8 @@ init_node (struct merge_node *parent, struct merge_node 
*node_pool,
 
   if (nthreads > 1)
     {
-      unsigned long int lo_threads = nthreads / 2;
-      unsigned long int hi_threads = nthreads - lo_threads;
+      size_t lo_threads = nthreads / 2;
+      size_t hi_threads = nthreads - lo_threads;
       node->lo_child = node_pool;
       node_pool = init_node (node, node_pool, lo, lo_threads,
                              total_lines, true);
@@ -3254,15 +3262,16 @@ queue_destroy (struct merge_node_queue *queue)
   pthread_mutex_destroy (&queue->mutex);
 }
 
-/* Initialize merge QUEUE, allocating space for a maximum of RESERVE nodes.
-   Though it's highly unlikely all nodes are in the heap at the same time,
-   RESERVE should accommodate all of them. Counting a NULL dummy head for the
-   heap, RESERVE should be 2 * NTHREADS. */
+/* Initialize merge QUEUE, allocating space suitable for a maximum of
+   NTHREADS threads.  */
 
 static void
-queue_init (struct merge_node_queue *queue, size_t reserve)
+queue_init (struct merge_node_queue *queue, size_t nthreads)
 {
-  queue->priority_queue = heap_alloc (compare_nodes, reserve);
+  /* Though it's highly unlikely all nodes are in the heap at the same
+     time, the heap should accommodate all of them.  Counting a NULL
+     dummy head for the heap, reserve 2 * NTHREADS nodes.  */
+  queue->priority_queue = heap_alloc (compare_nodes, 2 * nthreads);
   pthread_mutex_init (&queue->mutex, NULL);
   pthread_cond_init (&queue->cond, NULL);
 }
@@ -3454,7 +3463,7 @@ merge_loop (struct merge_node_queue *queue,
 }
 
 
-static void sortlines (struct line *restrict, unsigned long int, size_t,
+static void sortlines (struct line *restrict, size_t, size_t,
                        struct merge_node *, bool, struct merge_node_queue *,
                        FILE *, char const *);
 
@@ -3467,7 +3476,7 @@ struct thread_args
   struct line *lines;
 
   /* Number of threads to use.  If 0 or 1, sort single-threaded.  */
-  unsigned long int nthreads;
+  size_t nthreads;
 
   /* Number of lines in LINES and DEST.  */
   size_t const total_lines;
@@ -3477,7 +3486,7 @@ struct thread_args
   struct merge_node *const node;
 
   /* True if this node is sorting the lower half of the parent's work.  */
-  bool lo_child;
+  bool is_lo_child;
 
   /* The priority queue controlling available work for the entire
      internal sort.  */
@@ -3496,7 +3505,7 @@ sortlines_thread (void *data)
 {
   struct thread_args const *args = data;
   sortlines (args->lines, args->nthreads, args->total_lines,
-             args->node, args->lo_child, args->queue, args->tfp,
+             args->node, args->is_lo_child, args->queue, args->tfp,
              args->output_temp);
   return NULL;
 }
@@ -3526,15 +3535,15 @@ sortlines_thread (void *data)
    have been merged. */
 
 static void
-sortlines (struct line *restrict lines, unsigned long int nthreads,
-           size_t total_lines, struct merge_node *node, bool lo_child,
+sortlines (struct line *restrict lines, size_t nthreads,
+           size_t total_lines, struct merge_node *node, bool is_lo_child,
            struct merge_node_queue *queue, FILE *tfp, char const *temp_output)
 {
   size_t nlines = node->nlo + node->nhi;
 
   /* Calculate thread arguments. */
-  unsigned long int lo_threads = nthreads / 2;
-  unsigned long int hi_threads = nthreads - lo_threads;
+  size_t lo_threads = nthreads / 2;
+  size_t hi_threads = nthreads - lo_threads;
   pthread_t thread;
   struct thread_args args = {lines, lo_threads, total_lines,
                              node->lo_child, true, queue, tfp, temp_output};
@@ -3774,7 +3783,7 @@ merge (struct sortfile *files, size_t ntemps, size_t 
nfiles,
 
 static void
 sort (char * const *files, size_t nfiles, char const *output_file,
-      unsigned long int nthreads)
+      size_t nthreads)
 {
   struct buffer buf;
   size_t ntemps = 0;
@@ -3793,7 +3802,7 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
       if (nthreads > 1)
         {
           /* Get log P. */
-          unsigned long int tmp = 1;
+          size_t tmp = 1;
           size_t mult = 1;
           while (tmp < nthreads)
             {
@@ -3843,16 +3852,15 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
           if (1 < buf.nlines)
             {
               struct merge_node_queue queue;
-              queue_init (&queue, 2 * nthreads);
+              queue_init (&queue, nthreads);
               struct merge_node *merge_tree =
                 merge_tree_init (nthreads, buf.nlines, line);
-              struct merge_node *end_node = merge_tree;
-              struct merge_node *root_node = merge_tree + 1;
+              struct merge_node *root = merge_tree + 1;
 
-              sortlines (line, nthreads, buf.nlines, root_node,
+              sortlines (line, nthreads, buf.nlines, root,
                          true, &queue, tfp, temp_output);
               queue_destroy (&queue);
-              pthread_mutex_destroy (&root_node->lock);
+              pthread_mutex_destroy (&root->lock);
               merge_tree_destroy (merge_tree);
             }
           else
@@ -4076,7 +4084,7 @@ main (int argc, char **argv)
   bool mergeonly = false;
   char *random_source = NULL;
   bool need_random = false;
-  unsigned long int nthreads = 0;
+  size_t nthreads = 0;
   size_t nfiles = 0;
   bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
   bool obsolete_usage = (posix2_version () < 200112);
@@ -4620,6 +4628,11 @@ main (int argc, char **argv)
       if (!nthreads || nthreads > np2)
         nthreads = np2;
 
+      /* Avoid integer overflow later.  */
+      size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));
+      if (nthreads_max < nthreads)
+        nthreads = nthreads_max;
+
       sort (files, nfiles, outfile, nthreads);
     }
 
-- 
1.7.2