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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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
