Package: coreutils;
Reported by: Jim Meyering <jim <at> meyering.net>
Date: Thu, 9 Dec 2010 12:11:01 UTC
Severity: normal
Tags: fixed
Done: Assaf Gordon <assafgordon <at> gmail.com>
Bug is archived. No further changes may be made.
View this message in rfc822 format
From: Paul Eggert <eggert <at> cs.ucla.edu> To: Chen Guo <chen.guo.0625 <at> gmail.com> Cc: coreutils <at> gnu.org, bug-coreutils <at> gnu.org, Jim Meyering <jim <at> meyering.net>, DJ Lucas <dj <at> linuxfromscratch.org> Subject: bug#7597: multi-threaded sort can segfault (unrelated to the sort -u segfault) Date: Sat, 11 Dec 2010 00:35:20 -0800
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 <chenguo4 <at> ucla.edu>
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 <eggert <at> cs.ucla.edu>
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 <chenguo4 <at> ucla.edu>
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 <eggert <at> cs.ucla.edu>
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
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.