GNU bug report logs -
#7489
[coreutils] over aggressive threads in sort
Previous Next
Reported by: DJ Lucas <dj <at> linuxfromscratch.org>
Date: Fri, 26 Nov 2010 19:40:02 UTC
Severity: normal
Tags: fixed
Done: Assaf Gordon <assafgordon <at> gmail.com>
Bug is archived. No further changes may be made.
To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 7489 in the body.
You can then email your comments to 7489 AT debbugs.gnu.org in the normal way.
Toggle the display of automated, internal messages from the tracker.
Report forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Fri, 26 Nov 2010 19:40:02 GMT)
Full text and
rfc822 format available.
Acknowledgement sent
to
DJ Lucas <dj <at> linuxfromscratch.org>:
New bug report received and forwarded. Copy sent to
bug-coreutils <at> gnu.org.
(Fri, 26 Nov 2010 19:40:03 GMT)
Full text and
rfc822 format available.
Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):
Sent too bug-coreutils too (no bug id currently AFAICT).
Bug only affects multi-byte locales. Take the following samples:
bash-4.1# zcat cracklib-words-20080507.gz | sort -u --debug > file &&
echo $?
sort: using `en_US.UTF-8' sorting rules
Segmentation fault
bash-4.1# echo $?
139
bash-4.1#
bash-4.1# zcat cracklib-words-20080507.gz | sort -u --parallel=1
--debug > file && echo $?
sort: using `en_US.UTF-8' sorting rules
0
bash-4.1#
bash-4.1# zcat cracklib-words-20080507.gz | LANG=C sort -u --debug >
file && echo $?
sort: using simple byte comparison
0
bash-4.1#
bash-4.1# gzip -d cracklib-words-20080507.gz
bash-4.1# sort -u --debug cracklib-words-20080507 > file && echo $?
sort: using `en_US.UTF-8' sorting rules
0
bash-4.1#
In the interim, for a quick and dirty hack, I've added an LC_COLLATE
comparison and set nthreads to 1 in multibyte locales.
Probably well known, but the test file that I used is available from:
http://downloads.sourceforge.net/cracklib/cracklib-words-20080507.gz
-- DJ Lucas
--
This message has been scanned for viruses and
dangerous content, and is believed to be clean.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Fri, 26 Nov 2010 23:19:01 GMT)
Full text and
rfc822 format available.
Message #8 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Thanks for the bug report. Unfortunately,
I cannot reproduce the problem with coreutils 8.7, either on
RHEL 5.5 x86-64 or on Ubuntu 10.10 x86.
Which version of coreutils are you running? And on what
platform? How did you build it?
Can you reproduce it with --parallel=2? If not, which value
of --parallel is needed?
If this is coreutils 8.7, can you get a core dump and a GDB
backtrace?
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 27 Nov 2010 02:49:01 GMT)
Full text and
rfc822 format available.
Message #11 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 26/11/10 18:01, DJ Lucas wrote:
> Sent too bug-coreutils too (no bug id currently AFAICT).
>
> Bug only affects multi-byte locales. Take the following samples:
>
>
>
> bash-4.1# zcat cracklib-words-20080507.gz | sort -u --debug > file &&
> echo $?
> sort: using `en_US.UTF-8' sorting rules
> Segmentation fault
> bash-4.1# echo $?
> 139
> bash-4.1#
>
>
> bash-4.1# zcat cracklib-words-20080507.gz | sort -u --parallel=1
> --debug > file && echo $?
> sort: using `en_US.UTF-8' sorting rules
> 0
> bash-4.1#
>
>
> bash-4.1# zcat cracklib-words-20080507.gz | LANG=C sort -u --debug >
> file && echo $?
> sort: using simple byte comparison
> 0
> bash-4.1#
>
>
> bash-4.1# gzip -d cracklib-words-20080507.gz
> bash-4.1# sort -u --debug cracklib-words-20080507 > file && echo $?
> sort: using `en_US.UTF-8' sorting rules
> 0
> bash-4.1#
>
>
> In the interim, for a quick and dirty hack, I've added an LC_COLLATE
> comparison and set nthreads to 1 in multibyte locales.
>
> Probably well known, but the test file that I used is available from:
> http://downloads.sourceforge.net/cracklib/cracklib-words-20080507.gz
>
> -- DJ Lucas
>
100% reproducible on a 32 bit F12 box (first I tried)
# zcat cracklib-words-20080507.gz | ./coreutils-8.7/src/sort -u --parallel=1 > /dev/null
# zcat cracklib-words-20080507.gz | ./coreutils-8.7/src/sort -u --parallel=2 > /dev/null
Segmentation fault (core dumped)
#0 0x00c4aecf in __strlen_ia32 () from /lib/libc.so.6
#1 0x00c4ecf1 in strcoll_l () from /lib/libc.so.6
#2 0x00c4a8b1 in strcoll () from /lib/libc.so.6
#3 0x0805682d in strcoll_loop (s1=<value optimized out>, s1size=<value optimized out>, s2=<value optimized out>, s2size=1852142453) at memcoll.c:39
#4 memcoll0 (s1=<value optimized out>, s1size=<value optimized out>, s2=<value optimized out>, s2size=1852142453) at memcoll.c:110
#5 0x08054263 in xmemcoll0 (s1=0xb5457008 "lauters", s1size=8, s2=0x6f626f79 <Address 0x6f626f79 out of bounds>, s2size=1852142453) at xmemcoll.c:71
#6 0x0804e091 in compare (a=0xb68cb558, b=0xb5c3e9b8) at sort.c:2653
#7 0x0804f320 in write_unique (line=0xb68cb558, tfp=0x9f2ebe0, temp_output=0x9f2e9c0 "/tmp/sortqd5BvL") at sort.c:3233
#8 0x0804f5b0 in mergelines_node (node=0xbfd06c0c, total_lines=822189, tfp=0x9f2ebe0, temp_output=0x9f2e9c0 "/tmp/sortqd5BvL") at sort.c:3279
#9 0x0804f8e4 in merge_loop (queue=0xbfd06ca4, total_lines=822189, tfp=0x9f2ebe0, temp_output=0x9f2e9c0 "/tmp/sortqd5BvL") at sort.c:3367
#10 0x0804fc52 in sortlines (lines=0xb7557038, dest=0xb68cb568, nthreads=1, total_lines=822189, parent=0xbfd06c0c, lo_child=true, merge_queue=0xbfd06ca4, tfp=0x9f2ebe0, temp_output=0x9f2e9c0 "/tmp/sortqd5BvL")
at sort.c:3481
#11 0x0804f9a4 in sortlines_thread (data=0xbfd06be4) at sort.c:3404
#12 0x00d58ab5 in start_thread () from /lib/libpthread.so.0
#13 0x00caef1e in clone () from /lib/libc.so.6
(gdb) quit
Looks like ASCII data passed on the stack for pointer and size (oboy, nesu)
Hmm, seems like multiple threads are racing to update the
static "saved" variable in write_unique() ?
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 27 Nov 2010 02:55:02 GMT)
Full text and
rfc822 format available.
Message #14 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/26/2010 05:24 PM, Paul Eggert wrote:
> Thanks for the bug report. Unfortunately,
> I cannot reproduce the problem with coreutils 8.7, either on
> RHEL 5.5 x86-64 or on Ubuntu 10.10 x86.
>
> Which version of coreutils are you running?
8.7. Haven't tested on 8.6 or 8.5. 8.4 worked correctly, but that was
expected since I can get around it if not running in multiple threads.
> And on what
> platform?
LFS 32bit on Athlon II 250 (64bit dual core CPU/hardware). gcc-4.5.1,
glibc-2.12.1, binutils-2.20.1.
> How did you build it?
Basic CMMI --prefix=/usr. Built both with and without i18n RH patch and
Linux only uname patches.
>
> Can you reproduce it with --parallel=2? If not, which value
> of --parallel is needed?
Yes, it is reproducible with --parallel=2. Seems this is a difficult
one to track down. So far we've only confirmed that it happens in
multibyte locales, with 32bit build on 64bit multi-core hardware, and
only from stdin. Works fine if the file is passed as an argument to
sort. Haven't confirmed 64bit build had multibyte yet, but the error did
not occur on the report from that user. Setting LANG/LC_ALL to C or
POSIX works around it, as well as --parallel=1. I've added a quick and
really ugly workaround in the interim so that I can continue and get
some work done (using getenv("LC_COLLATE"), and testing only against !=
POSIX and != C, setting nthreads=1). Confirmed that the correct encoding
is displayed with --debug with the workaround in place.
If you have a similar setup laying around (32bit installation on 64bit
multi-core hardware), try
cat bigfile.txt | LANG=en_US.UTF-8 sort -u (or similar)
>
> If this is coreutils 8.7, can you get a core dump and a GDB
> backtrace?
>
Sure, give me a bit, but looks like Pádraig Brady beat me to it.
-- DJ Lucas
--
This message has been scanned for viruses and
dangerous content, and is believed to be clean.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 27 Nov 2010 03:29:02 GMT)
Full text and
rfc822 format available.
Message #17 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 27/11/10 03:00, DJ Lucas wrote:
>
> Setting LANG/LC_ALL to C or
> POSIX works around it, as well as --parallel=1. I've added a quick and
> really ugly workaround in the interim so that I can continue and get
> some work done (using getenv("LC_COLLATE"), and testing only against !=
> POSIX and != C, setting nthreads=1). Confirmed that the correct encoding
> is displayed with --debug with the workaround in place.
Best workaround I think is to leave the code alone,
and set OMP_NUM_THREADS=1 in your env
as otherwise you may get invalid results
in any locale.
cheers,
Pádraig.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 27 Nov 2010 08:24:02 GMT)
Full text and
rfc822 format available.
Message #20 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/26/2010 06:52 PM, Pádraig Brady wrote:
> Hmm, seems like multiple threads are racing to update the
> static "saved" variable in write_unique() ?
I don't think it's as simple as that. write_unique
is generating output, and when it is run it is supposed
to have exclusive access to the output file, which means
it also has exclusive access to the "saved" variable.
I suspect the problem is that the line structure is
messed up when you have multiple threads and sufficiently
large input, in that when one merge node is done and
the next one is run, the "saved" variable (which points
to storage managed by the earlier node) is pointing to
storage that is no longer valid. I haven't had time to
look into the details, though.
Chen, do you have some insight into this? Here's the thread:
http://lists.gnu.org/archive/html/bug-coreutils/2010-11/msg00209.html
I have now reproduced the bug on RHEL 5.5 x86-64, using
coreutils 8.7 built with "configure CC='cc -m32'". The bug
is also present in the savannah git master.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 27 Nov 2010 09:34:02 GMT)
Full text and
rfc822 format available.
Message #23 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Following up on my previous email, it appears to me that
the following line in mergelines_node is weird:
node->dest -= lo_orig - node->lo + hi_orig - node->hi;
Surely there should be a "*" in front of that line?
(This does not fix the bug; perhaps it is a different bug?)
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sun, 28 Nov 2010 00:53:02 GMT)
Full text and
rfc822 format available.
Message #26 received at 7489 <at> debbugs.gnu.org (full text, mbox):
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);
}
}
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sun, 28 Nov 2010 01:31:01 GMT)
Full text and
rfc822 format available.
Message #29 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 28/11/10 00:57, 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);
> }
> }
>
>
It passes a fleeting test between kids and sleep...
$ zcat cracklib-words-20080507.gz | ./coreutils-8.7/src/sort -u > /dev/null
Segmentation fault (core dumped)
$ zcat cracklib-words-20080507.gz | ./coreutils-8.7/src/sort -u | wc -l
0
$ zcat cracklib-words-20080507.gz | ./coreutils-8.7/src/sort-paul -u | wc -l
1671704
cheers,
Pádraig.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sun, 28 Nov 2010 02:14:02 GMT)
Full text and
rfc822 format available.
Message #32 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/27/2010 06:57 PM, 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.
>
lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$ cat
/lfs-source-archive/cracklib-words-20080507 | sort -u > /dev/null; echo $?
0
lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$
Appears to work as expected. Thanks for jumping on this so quickly.
-- DJ Lucas
--
This message has been scanned for viruses and
dangerous content, and is believed to be clean.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 07:10:03 GMT)
Full text and
rfc822 format available.
Message #35 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/27/2010 08:18 PM, DJ Lucas wrote:
>
> lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$ cat
> /lfs-source-archive/cracklib-words-20080507 | sort -u > /dev/null; echo $?
> 0
> lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$
>
> Appears to work as expected. Thanks for jumping on this so quickly.
>
Okay, so that fixes the segfault for both the original example from the
RedHat bug, and the example I submitted. However, CPU is still showing
100% utilization in the original test (from RedHat bz), and the test
that, I believe (not sure of the quoting), was submitted by PÃdraig
Brady still fails. I don't have a link to the original (maybe private
message), but it is quoted here:
http://lists.gnu.org/archive/html/coreutils/2010-11/msg00124.html. I ran
only the quoted test. Unrelated bug? (again, not entirely sure of the
context)
lfs [ lfs-source-archive ]$ seq 100000 > in
lfs [ lfs-source-archive ]$ mkfifo fifo
lfs [ lfs-source-archive ]$ (for i in $(seq 12); do read line; echo $i;
sleep .1; done
> cat > /dev/null) < fifo &
[1] 16123
lfs [ lfs-source-archive ]$ (ulimit -t 1; sort in > fifo \
> || echo killed via $(env kill -l $(expr $? - 128)))
1
2
3
4
5
6
7
8
9
killed via KILL
lfs [ lfs-source-archive ]$ 10
11
12
^C
[1]+ Done ( for i in $(seq 12);
do
read line; echo $i; sleep .1;
done; cat > /dev/null ) < fifo
-- DJ Lucas
--
This message has been scanned for viruses and
dangerous content, and is believed to be clean.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 11:26:02 GMT)
Full text and
rfc822 format available.
Message #38 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 29/11/10 07:14, DJ Lucas wrote:
> On 11/27/2010 08:18 PM, DJ Lucas wrote:
>
>>
>> lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$ cat
>> /lfs-source-archive/cracklib-words-20080507 | sort -u > /dev/null; echo $?
>> 0
>> lfs [ /lfs-source-archive/coreutils-8.7-new/src ]$
>>
>> Appears to work as expected. Thanks for jumping on this so quickly.
>>
>
> Okay, so that fixes the segfault for both the original example from the
> RedHat bug, and the example I submitted. However, CPU is still showing
> 100% utilization in the original test (from RedHat bz), and the test
> that, I believe (not sure of the quoting), was submitted by PÃdraig
> Brady still fails. I don't have a link to the original (maybe private
> message), but it is quoted here:
> http://lists.gnu.org/archive/html/coreutils/2010-11/msg00124.html. I ran
> only the quoted test. Unrelated bug? (again, not entirely sure of the
> context)
There was a suggested workaround for test here:
https://bugzilla.redhat.com/show_bug.cgi?id=655096#c5
I've no time to try that at present though.
sorry,
Pádraig.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 19:11:02 GMT)
Full text and
rfc822 format available.
Message #41 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/28/10 23:14, DJ Lucas wrote:
> http://lists.gnu.org/archive/html/coreutils/2010-11/msg00124.html
Ah, sorry, I didn't understand that message and thought Pádraig
had handled it. On an 8-core RHEL 5.5 x86-64 host I reproduced
the problem with the stated test case:
(for i in $(seq 12); do read line; echo $i; sleep .1; done
cat > /dev/null) < fifo &
(ulimit -t 1; ./sort in > fifo \
|| echo killed via $(env kill -l $(expr $? - 128)))
If I understand this other bug correctly, the problem is that one thread
is using a spin lock to wait for another thread, which in turn is waiting
to write to the pipe. Surely the simplest fix is to drop spin locks
entirely and use mutexes instead. Perhaps a better fix would be to
use mutexes at the top level (where threads can write to a file and
therefore can wait) and to use spin locks at lower levels (where
threads are merely storing into memory and thus can't wait).
Chen, do you have any advice on this as well? I can look into
either fix but am mildly inclined to take the simpler (albeit slower)
approach, at least at first. Here's that thread again:
http://lists.gnu.org/archive/html/bug-coreutils/2010-11/msg00209.html
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 20:04:02 GMT)
Full text and
rfc822 format available.
Message #44 received at 7489 <at> debbugs.gnu.org (full text, mbox):
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 <meyering <at> redhat.com>
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
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 20:09:03 GMT)
Full text and
rfc822 format available.
Message #47 received at 7489 <at> debbugs.gnu.org (full text, mbox):
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.
I haven't tried to trigger that one yet.
Have you?
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 29 Nov 2010 22:42:02 GMT)
Full text and
rfc822 format available.
Message #50 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/29/10 12:14, Jim Meyering wrote:
> I haven't tried to trigger that one yet.
> Have you?
No, sorry, haven't had time. My current guess, by the way,
is that it's not a bug that can be triggered: it's merely
useless code that is harmless and can safely be removed.
(This is a guess that I also came up with in my sleep, so
take it for what it's worth. :-)
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 00:29:02 GMT)
Full text and
rfc822 format available.
Message #53 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Hi all,
On Mon, Nov 29, 2010 at 11:16 AM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
> entirely and use mutexes instead. Perhaps a better fix would be to
> use mutexes at the top level (where threads can write to a file and
> therefore can wait) and to use spin locks at lower levels (where
> threads are merely storing into memory and thus can't wait).
>
> Chen, do you have any advice on this as well? I can look into
> either fix but am mildly inclined to take the simpler (albeit slower)
> approach, at least at first. Here's that thread again:
>
> http://lists.gnu.org/archive/html/bug-coreutils/2010-11/msg00209.html
I haven't looked at the code in a couple of months, so I wont have a
definite answer
until tonight, but off the top of my head I'm not sure mixing
spinlocks and mutexes
will work, since they exist orthogonally. That is, a thread can lock
the mutex of a
structure, but the spin lock of the structure is still free to be
acquired. The only way
to ensure the struct is locked down is to lock both the mutex and the spinlock,
in which case, what's the point?
The only way this would work is if, when a struct is locked via mutex the only
threads trying to acquire the struct are trying to do so via mutex,
and no threads
are looking to lock via spinlock. I'll take a look when I get home
tonight to see
if this condition always holds.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 00:35:02 GMT)
Full text and
rfc822 format available.
Message #56 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/29/10 16:34, Chen Guo wrote:
> The only way this would work is if, when a struct is locked via mutex the only
> threads trying to acquire the struct are trying to do so via mutex,
> and no threads
> are looking to lock via spinlock.
Yes, that's definitely the idea. Under either of my
proposals, a particular object would be protected either
by a spinlock, or by a mutex, but never by both; and the
decision as to whether to use a spinlock or a mutex would
be made by object-creation time at the latest.
Thanks for looking into it.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 04:28:02 GMT)
Full text and
rfc822 format available.
Message #59 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Hi guys,
Is something up with Savannah? I just tried a git clone and got
connection time out; I cant even reach git.sv.gnu.org via ping.
I'll try again at work tomorrow.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 07:33:03 GMT)
Full text and
rfc822 format available.
Message #62 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/29/2010 08:32 PM, Chen Guo wrote:
> Hi guys,
> Is something up with Savannah? I just tried a git clone and got
> connection time out; I cant even reach git.sv.gnu.org via ping.
There was a breakin, which led to leaking of encrypted account
passwords, some of them discovered via a brute-force attack.
It's pretty bad. They're reinstalling and restoring the data
from a November 24 backup. No firm ETA yet. Expect an
official announcement soon.
You can find the current status at <http://savannah.gnu.org/>.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 21:36:02 GMT)
Full text and
rfc822 format available.
Message #65 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Jim Meyering wrote:
> 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.
...
Hi Paul,
I'm getting ready to push something like the following
(I'll add a NEWS entry first, though)
Is there anything you'd like to add?
From 46589f6be5ce6cd7ff474059a33f47b57094ff21 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Tue, 30 Nov 2010 22:30:12 +0100
Subject: [PATCH] sort -u: fix a thread-race pointer corruption bug
* src/sort.c (write_unique): Save the entire "struct line", not
just a pointer to one. Otherwise, with a multi-thread run,
sometimes, with some inputs, fillbuf would would win a race
and clobber a "saved->text" pointer in one thread just before
it was dereferenced in a comparison in another thread.
---
src/sort.c | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
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);
}
}
--
1.7.3.2.846.gf4b062
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Nov 2010 22:17:02 GMT)
Full text and
rfc822 format available.
Message #68 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/30/10 13:41, Jim Meyering wrote:
> Is there anything you'd like to add?
No, thanks, that looks good. I have some other patches
to clean things up in this area, but they can wait.
I hate to tease, so here is a draft of the cleanup patches.
Most of this stuff is cleanup, but the first line of the change
does fix a bug with very large sorts: when level > 14 on a
typical 64-bit host, there is an unwanted integer overflow
and 'sort' will divide by zero. Admittedly this bug is
unlikely (doesn't this mean you need thousands of threads?).
Anyway, perhaps Chen can review them (I don't have time
to test them right now).
Plus we have to fix the other bug. I wrote these cleanup patches
while trying to understand the code well enough to fix the other bug.
diff --git a/src/sort.c b/src/sort.c
index 1aa1eb4..708cc3c 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -107,7 +107,7 @@ struct rlimit { size_t rlim_cur; };
/* Maximum number of lines to merge every time a NODE is taken from
the MERGE_QUEUE. Node is at LEVEL in the binary merge tree,
and is responsible for merging TOTAL lines. */
-#define MAX_MERGE(total, level) ((total) / ((2 << level) * (2 << level)) + 1)
+#define MAX_MERGE(total, level) (((total) >> (((level) << 1) + 2)) + 1)
/* Heuristic value for the number of lines for which it is worth
creating a subthread, during an internal merge sort, on a machine
@@ -237,10 +237,10 @@ struct merge_node
struct line **dest; /* Pointer to destination of merge. */
size_t nlo; /* Total Lines remaining from LO. */
size_t nhi; /* Total lines remaining from HI. */
- size_t level; /* Level in merge tree. */
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_spinlock_t lock; /* Lock for node operations. */
};
/* Priority queue of merge nodes. */
@@ -3156,7 +3156,7 @@ compare_nodes (void const *a, void const *b)
static inline void
lock_node (struct merge_node *node)
{
- pthread_spin_lock (node->lock);
+ pthread_spin_lock (&node->lock);
}
/* Unlock a merge tree NODE. */
@@ -3164,7 +3164,7 @@ lock_node (struct merge_node *node)
static inline void
unlock_node (struct merge_node *node)
{
- pthread_spin_unlock (node->lock);
+ pthread_spin_unlock (&node->lock);
}
/* Destroy merge QUEUE. */
@@ -3240,69 +3240,38 @@ write_unique (struct line const *line, FILE *tfp, char const *temp_output)
/* Merge the lines currently available to a NODE in the binary
merge tree, up to a maximum specified by MAX_MERGE. */
-static size_t
+static void
mergelines_node (struct merge_node *restrict node, size_t total_lines,
FILE *tfp, char const *temp_output)
{
- struct line *lo_orig = node->lo;
- struct line *hi_orig = node->hi;
+ bool merge_to_dest = (MERGE_ROOT < node->level);
+ struct line const *lo_orig = node->lo;
+ struct line const *hi_orig = node->hi;
+ struct line *dest = *node->dest;
size_t to_merge = MAX_MERGE (total_lines, node->level);
- size_t merged_lo;
- size_t merged_hi;
- if (node->level > MERGE_ROOT)
+ while (to_merge--)
{
- /* Merge to destination buffer. */
- struct line *dest = *node->dest;
- while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
- if (compare (node->lo - 1, node->hi - 1) <= 0)
- *--dest = *--node->lo;
- else
- *--dest = *--node->hi;
-
- merged_lo = lo_orig - node->lo;
- merged_hi = hi_orig - node->hi;
-
- if (node->nhi == merged_hi)
- while (node->lo != node->end_lo && to_merge--)
- *--dest = *--node->lo;
- else if (node->nlo == merged_lo)
- while (node->hi != node->end_hi && to_merge--)
- *--dest = *--node->hi;
- }
- else
- {
- /* Merge directly to output. */
- while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
+ bool lo_exhausted = (node->lo == node->end_lo);
+ bool hi_exhausted = (node->hi == node->end_hi);
+ int cmp = lo_exhausted - hi_exhausted;
+ if (! cmp)
{
- if (compare (node->lo - 1, node->hi - 1) <= 0)
- write_unique (--node->lo, tfp, temp_output);
- else
- write_unique (--node->hi, tfp, temp_output);
+ if (lo_exhausted)
+ break;
+ cmp = compare (node->lo - 1, node->hi - 1);
}
- merged_lo = lo_orig - node->lo;
- merged_hi = hi_orig - node->hi;
-
- if (node->nhi == merged_hi)
- {
- while (node->lo != node->end_lo && to_merge--)
- write_unique (--node->lo, tfp, temp_output);
- }
- else if (node->nlo == merged_lo)
- {
- while (node->hi != node->end_hi && to_merge--)
- write_unique (--node->hi, tfp, temp_output);
- }
- node->dest -= lo_orig - node->lo + hi_orig - node->hi;
+ struct line const *lesser = (cmp <= 0 ? --node->lo : --node->hi);
+ if (merge_to_dest)
+ *--dest = *lesser;
+ else
+ write_unique (lesser, tfp, temp_output);
}
- /* Update NODE. */
- merged_lo = lo_orig - node->lo;
- merged_hi = hi_orig - node->hi;
- node->nlo -= merged_lo;
- node->nhi -= merged_hi;
- return merged_lo + merged_hi;
+ *node->dest = dest;
+ node->nlo -= lo_orig - node->lo;
+ node->nhi -= hi_orig - node->hi;
}
/* Insert NODE into QUEUE if it passes insertion checks. */
@@ -3328,13 +3297,11 @@ check_insert (struct merge_node *node, struct merge_node_queue *queue)
/* Update parent merge tree NODE. */
static void
-update_parent (struct merge_node *node, size_t merged,
- struct merge_node_queue *queue)
+update_parent (struct merge_node *node, struct merge_node_queue *queue)
{
if (node->level > MERGE_ROOT)
{
lock_node (node->parent);
- *node->dest -= merged;
check_insert (node->parent, queue);
unlock_node (node->parent);
}
@@ -3364,10 +3331,9 @@ merge_loop (struct merge_node_queue *queue,
queue_insert (queue, node);
break;
}
- size_t merged_lines = mergelines_node (node, total_lines, tfp,
- temp_output);
+ mergelines_node (node, total_lines, tfp, temp_output);
check_insert (node, queue);
- update_parent (node, merged_lines, queue);
+ update_parent (node, queue);
unlock_node (node);
}
@@ -3442,10 +3408,9 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
struct line *lo = dest - total_lines;
struct line *hi = lo - nlo;
struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
- pthread_spinlock_t lock;
- pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
struct merge_node node = {lo, hi, lo, hi, parent_end, nlo, nhi,
- parent->level + 1, parent, false, &lock};
+ parent, parent->level + 1, false, };
+ pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
/* Calculate thread arguments. */
unsigned long int lo_threads = nthreads / 2;
@@ -3481,7 +3446,7 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
merge_loop (merge_queue, total_lines, tfp, temp_output);
}
- pthread_spin_destroy (&lock);
+ pthread_spin_destroy (&node.lock);
}
/* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3758,16 +3723,15 @@ sort (char * const *files, size_t nfiles, char const *output_file,
struct merge_node_queue merge_queue;
queue_init (&merge_queue, 2 * nthreads);
- pthread_spinlock_t lock;
- pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
struct merge_node node =
{NULL, NULL, NULL, NULL, NULL, buf.nlines,
- buf.nlines, MERGE_END, NULL, false, &lock};
+ buf.nlines, NULL, MERGE_END, false, };
+ pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
sortlines (line, line, nthreads, buf.nlines, &node, true,
&merge_queue, tfp, temp_output);
queue_destroy (&merge_queue);
- pthread_spin_destroy (&lock);
+ pthread_spin_destroy (&node.lock);
}
else
write_unique (line - 1, tfp, temp_output);
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Wed, 01 Dec 2010 00:15:02 GMT)
Full text and
rfc822 format available.
Message #71 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On Tue, Nov 30, 2010 at 2:22 PM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
Hi Professor Eggert,
> Anyway, perhaps Chen can review them (I don't have time
> to test them right now).
I'll look at it as soon as Savannah's back up; I never actually pulled
from coreutils after the original patch was submitted. Professor
Eggert, could you detail how you can trigger the divide-by-zero bug?
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Wed, 01 Dec 2010 06:11:01 GMT)
Full text and
rfc822 format available.
Message #74 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/30/2010 04:19 PM, Chen Guo wrote:
> could you detail how you can trigger the divide-by-zero bug?
Invoke MAX_MERGE(total, level) with level == 15.
2 << level yields 65536, and 65536 * 65536 overflows to zero.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Wed, 01 Dec 2010 07:32:02 GMT)
Full text and
rfc822 format available.
Message #77 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Paul Eggert wrote:
> On 11/29/2010 08:32 PM, Chen Guo wrote:
>> Hi guys,
>> Is something up with Savannah? I just tried a git clone and got
>> connection time out; I cant even reach git.sv.gnu.org via ping.
>
> There was a breakin, which led to leaking of encrypted account
> passwords, some of them discovered via a brute-force attack.
Note that it was web passwords.
> It's pretty bad. They're reinstalling and restoring the data
> from a November 24 backup. No firm ETA yet. Expect an
> official announcement soon.
>
> You can find the current status at <http://savannah.gnu.org/>.
Here's the chronology:
http://www.fsf.org/blogs/sysadmin/savannah-and-www.gnu.org-downtime
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Thu, 02 Dec 2010 05:52:02 GMT)
Full text and
rfc822 format available.
Message #80 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/30/2010 10:16 PM, Paul Eggert wrote:
> Invoke MAX_MERGE(total, level) with level == 15.
> 2 << level yields 65536, and 65536 * 65536 overflows to zero.
I managed to reproduce this bug on a (faked) host with
32768 processors, using a command like this:
seq 1000000000 | sort --parallel=32768 -S 10G
The result was a floating point exception (actually, a division
by zero) and 'sort' crashed.
However, the bug is timing dependent and is very hard to
reproduce. I tried many more times to reproduce it, and
they all failed.
This proved to my satisfaction that it is a real bug, though,
so I pushed the following patch.
From 1561c2b228d93a049e527824e14ad4fe8c256b52 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Wed, 1 Dec 2010 21:50:00 -0800
Subject: [PATCH] sort: fix bug on 64-bit hosts with at least 32768 processors
* src/sort.c (MAX_MERGE): Avoid integer overflow when on a machine
with (say) 32-bit int and 64-bit size_t and when level == 15.
Without this fix, on such a machine with 32768 or more processors,
the level computation could overflow on large input, and this
would result in division by zero.
---
src/sort.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 1aa1eb4..5c368cd 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -107,7 +107,7 @@ struct rlimit { size_t rlim_cur; };
/* Maximum number of lines to merge every time a NODE is taken from
the MERGE_QUEUE. Node is at LEVEL in the binary merge tree,
and is responsible for merging TOTAL lines. */
-#define MAX_MERGE(total, level) ((total) / ((2 << level) * (2 << level)) + 1)
+#define MAX_MERGE(total, level) (((total) >> (2 * ((level) + 1))) + 1)
/* Heuristic value for the number of lines for which it is worth
creating a subthread, during an internal merge sort, on a machine
--
1.7.2
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Thu, 02 Dec 2010 10:18:01 GMT)
Full text and
rfc822 format available.
Message #83 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Hi Professor Eggert,
On Mon, Nov 29, 2010 at 11:16 AM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
> (for i in $(seq 12); do read line; echo $i; sleep .1; done
> cat > /dev/null) < fifo &
> (ulimit -t 1; ./sort in > fifo \
> || echo killed via $(env kill -l $(expr $? - 128)))
I ran this 10 times or so on an i7 and couldn't trigger anything. Is
seq 12 supposed to vary depending on the number of cores?
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Thu, 02 Dec 2010 17:44:01 GMT)
Full text and
rfc822 format available.
Message #86 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 12/02/10 02:22, Chen Guo wrote:
> On Mon, Nov 29, 2010 at 11:16 AM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
>> (for i in $(seq 12); do read line; echo $i; sleep .1; done
>> cat > /dev/null) < fifo &
>> (ulimit -t 1; ./sort in > fifo \
>> || echo killed via $(env kill -l $(expr $? - 128)))
>
> I ran this 10 times or so on an i7 and couldn't trigger anything. Is
> seq 12 supposed to vary depending on the number of cores?
I imagine it does. It's timing-dependent; I can't always reproduce
it on my test host (Intel Xeon E5620 2.4 GHz).
I just now realized that the above doesn't say what "in" is; it's
the output of "seq 100000".
Also, it may help to use an explicit --parallel=2 or whatever.
What happens if you do the following with the latest git version
(savannah's back up, by the way)?
cd tests && make check TESTS=misc/sort-spinlock-abuse
This gets an XFAIL fairly reliably on my test host.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Thu, 02 Dec 2010 21:38:02 GMT)
Full text and
rfc822 format available.
Message #89 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Chen Guo wrote:
> Hi Professor Eggert,
> On Mon, Nov 29, 2010 at 11:16 AM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
>> (for i in $(seq 12); do read line; echo $i; sleep .1; done
>> cat > /dev/null) < fifo &
>> (ulimit -t 1; ./sort in > fifo \
>> || echo killed via $(env kill -l $(expr $? - 128)))
>
> I ran this 10 times or so on an i7 and couldn't trigger anything. Is
> seq 12 supposed to vary depending on the number of cores?
Hi Chen,
Here's a stand-alone command-line test using the sort in your PATH:
rm -f in fifo
seq 100000 > in
mkfifo fifo
(for i in $(seq 12); do read line; echo $i; sleep .1; done
cat > /dev/null) < fifo &
(ulimit -t 1; sort in > fifo \
|| echo killed via $(env kill -l $(expr $? - 128)))
The 12 x 0.1-second sleeps are to ensure that the busy-waiting
sort will accumulate more than 1.0 seconds of CPU time, and thus
surpass the CPU time limit imposed by "ulimit -t 1".
With more processes, then you may use a number smaller than 12.
Running on a 6-core i7, I see the "killed via XCPU" message
anywhere between the "1" and "4" output lines. E.g.,
1
2
killed via XCPU
$ 3 :
4
5
6
7
8
9
10
11
12
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Fri, 03 Dec 2010 20:14:02 GMT)
Full text and
rfc822 format available.
Message #92 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Thanks Jim, that helped a lot.
I'll try out Professor Eggert's suggestion, of switching to mutexes
only at the top level merge. Of the following approaches, which would
you guys consider better practice?
1) void pointer, cast as either mutex or spinlock in lock function
2) union of mutex and spinlock, chosen in lock function
The idea is basically, in the lock function if we see the node is
MERGE_LEVEL_ROOT we'd lock the mutex either via cast or union member,
and likewise for other merge levels for spinlock.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Fri, 03 Dec 2010 21:06:02 GMT)
Full text and
rfc822 format available.
Message #95 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 12/03/10 12:18, Chen Guo wrote:
> I'll try out Professor Eggert's suggestion, of switching to mutexes
> only at the top level merge.
I'm having second thoughts about that. Yes, that'll prevent the
top-level merge (which is generating the actual output) from chewing
up CPU time. But it already has that property, since it's outputting
to stdout. And if second-level merges use mutexes, then the third-level
merges will spin. We'll have to use mutexes at all levels, unless
I'm missing something.
How about this idea instead. Keep using spin locks everywhere, but
have the top-level merge output to memory, as the lower merges already
do. The main thread can wait for the top level merge to finish and
then generate output. That way, none of the merges will have to wait
on an output pipe (or a slow output file).
Either option (either switch to mutexes everywhere, or have the top-level
merge go to memory) should work. Perhaps we should try both and benchmark
them.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sat, 04 Dec 2010 08:38:02 GMT)
Full text and
rfc822 format available.
Message #98 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 11/29/2010 02:46 PM, Paul Eggert wrote:
> My current guess, by the way,
> is that it's not a bug that can be triggered: it's merely
> useless code that is harmless and can safely be removed.
I removed it as part of the following series of cleanup
patches. These are intended merely to refactor the code
and simplify it a bit, to make it easier to fix the CPU
spinlock bug. Please feel free to undo anything that
looks at all questionable.
While we're on that subject, I assume that
if we want to fix it by doing the last pass in memory rather
than to stdout, we need to allocate a bit more memory at
the start, basically N * (1 + log2(N)) cells instead of
N (log2(N)) cells. This is enough to hold the extra pass
of output. If this isn't right, Chen, please let me know.
From 6c2452cd9f58c30e2e451c57d49384a2df785e3e Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 14:27:02 -0800
Subject: [PATCH 1/7] sort: Clarify comments
* src/sort.c: Improve comments a bit.
---
src/sort.c | 81 +++++++++++++++++++++++++++++++++++++++++++----------------
1 files changed, 59 insertions(+), 22 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 5c368cd..3d89a32 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -105,7 +105,7 @@ struct rlimit { size_t rlim_cur; };
#endif
/* Maximum number of lines to merge every time a NODE is taken from
- the MERGE_QUEUE. Node is at LEVEL in the binary merge tree,
+ the merge queue. Node is at LEVEL in the binary merge tree,
and is responsible for merging TOTAL lines. */
#define MAX_MERGE(total, level) (((total) >> (2 * ((level) + 1))) + 1)
@@ -196,6 +196,7 @@ struct buffer
bool eof; /* An EOF has been read. */
};
+/* Sort key. */
struct keyfield
{
size_t sword; /* Zero-origin 'word' to start at. */
@@ -3072,7 +3073,9 @@ mergelines (struct line *restrict t, size_t nlines,
}
/* Sort the array LINES with NLINES members, using TEMP for temporary space.
- NLINES must be at least 2.
+ Do this all within one thread. NLINES must be at least 2.
+ If TO_TEMP, put the sorted output into TEMP, and TEMP is as large as LINES.
+ Otherwise the sort is in-place and TEMP is half-sized.
The input and output arrays are in reverse order, and LINES and
TEMP point just past the end of their respective arrays.
@@ -3134,9 +3137,7 @@ sequential_sort (struct line *restrict lines, size_t nlines,
}
}
-/* Compare two NODEs for priority. The NODE with the higher (numerically
- lower) level has priority. If tie, the NODE with the most remaining
- lines has priority. */
+/* Compare two merge nodes A and B for priority. */
static int
compare_nodes (void const *a, void const *b)
@@ -3149,9 +3150,9 @@ compare_nodes (void const *a, void const *b)
}
/* Lock a merge tree NODE.
- Note spin locks were seen to perform better than mutexes
- as long as the number of threads is limited to the
- number of processors. */
+ 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. */
static inline void
lock_node (struct merge_node *node)
@@ -3190,8 +3191,8 @@ queue_init (struct merge_node_queue *queue, size_t reserve)
pthread_cond_init (&queue->cond, NULL);
}
-/* Insert NODE into priority QUEUE. Assume caller either holds lock on NODE
- or does not need to lock NODE. */
+/* Insert NODE into QUEUE. The caller either holds a lock on NODE, or
+ does not need to lock NODE. */
static void
queue_insert (struct merge_node_queue *queue, struct merge_node *node)
@@ -3203,7 +3204,7 @@ queue_insert (struct merge_node_queue *queue, struct merge_node *node)
pthread_cond_signal (&queue->cond);
}
-/* Pop NODE off priority QUEUE. Guarantee a non-null, spinlocked NODE. */
+/* Pop the top node off the priority QUEUE, lock the node, return it. */
static struct merge_node *
queue_pop (struct merge_node_queue *queue)
@@ -3218,10 +3219,12 @@ queue_pop (struct merge_node_queue *queue)
return node;
}
-/* If UNQIUE is set, checks to make sure line isn't a duplicate before
- outputting. If UNIQUE is not set, output the passed in line. Note that
- this function does not actually save the line, nor any key information,
- thus is only appropriate for internal sort. */
+/* Output LINE to TFP, unless -u is specified and the line compares
+ equal to the previous line. TEMP_OUTPUT is the name of TFP, or
+ is null if TFP is standard output.
+
+ This function does not save the line for comparison later, so it is
+ appropriate only for internal sort. */
static void
write_unique (struct line const *line, FILE *tfp, char const *temp_output)
@@ -3238,7 +3241,11 @@ write_unique (struct line const *line, FILE *tfp, char const *temp_output)
}
/* Merge the lines currently available to a NODE in the binary
- merge tree, up to a maximum specified by MAX_MERGE. */
+ merge tree. Merge a number of lines appropriate for this merge
+ level, assuming TOTAL_LINES is the total number of lines.
+
+ If merging at the top level, send output to TFP. TEMP_OUTPUT is
+ the name of TFP, or is null if TFP is standard output. */
static size_t
mergelines_node (struct merge_node *restrict node, size_t total_lines,
@@ -3305,7 +3312,9 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
return merged_lo + merged_hi;
}
-/* Insert NODE into QUEUE if it passes insertion checks. */
+/* Insert NODE into QUEUE if it is not already queued, and if one of
+ NODE's children has available lines and the other either has
+ available lines or has exhausted its lines. */
static void
check_insert (struct merge_node *node, struct merge_node_queue *queue)
@@ -3325,7 +3334,7 @@ check_insert (struct merge_node *node, struct merge_node_queue *queue)
}
}
-/* Update parent merge tree NODE. */
+/* Insert NODE's parent into QUEUE if the parent can now be worked on. */
static void
update_parent (struct merge_node *node, size_t merged,
@@ -3346,8 +3355,11 @@ update_parent (struct merge_node *node, size_t merged,
}
}
-/* Repeatedly pop QUEUE for a NODE with lines to merge, and merge at least
- some of those lines, until the MERGE_END node is popped. */
+/* Repeatedly pop QUEUE for a node with lines to merge, and merge at least
+ some of those lines, until the MERGE_END node is popped.
+ TOTAL_LINES is the total number of lines. If merging at the top
+ level, send output to TFP. TEMP_OUTPUT is the name of TFP, or is
+ null if TFP is standard output. */
static void
merge_loop (struct merge_node_queue *queue,
@@ -3384,13 +3396,33 @@ static void sortlines (struct line *restrict, struct line *restrict,
struct thread_args
{
+ /* Source, i.e., the array of lines to sort. This points just past
+ 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;
+
+ /* True if this node is sorting the lower half of the parent's work. */
bool lo_child;
+
+ /* The priority queue controlling available work for the entire
+ internal sort. */
struct merge_node_queue *const merge_queue;
+
+ /* If at the top level, the file to output to, and the file's name.
+ If the file is standard output, the file's name is null. */
FILE *tfp;
char const *output_temp;
};
@@ -3407,7 +3439,10 @@ sortlines_thread (void *data)
return NULL;
}
-/* There are three phases to the algorithm: node creation, sequential sort,
+/* Sort lines, possibly in parallel. The arguments are as in struct
+ thread_args above.
+
+ The algorithm has three phases: node creation, sequential sort,
and binary merge.
During node creation, sortlines recursively visits each node in the
@@ -3683,7 +3718,7 @@ merge (struct sortfile *files, size_t ntemps, size_t nfiles,
}
}
-/* Sort NFILES FILES onto OUTPUT_FILE. */
+/* Sort NFILES FILES onto OUTPUT_FILE. Use at most NTHREADS threads. */
static void
sort (char * const *files, size_t nfiles, char const *output_file,
@@ -3967,6 +4002,8 @@ set_ordering (char const *s, struct keyfield *key, enum blanktype blanktype)
return (char *) s;
}
+/* Initialize KEY. */
+
static struct keyfield *
key_init (struct keyfield *key)
{
--
1.7.2
From 5e87272634c4f5459808ec5d5c15d1710a2a5bbe Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 14:39:23 -0800
Subject: [PATCH 2/7] sort: tune struct_merge_node slightly
* src/sort.c (struct merge_node): 'lock' is now the actual lock,
not a pointer to the lock; there's no need for indirection here.
Make 'level' unsigned int instead of size_t, since it is a
bit-shift count; also, move it next to a bool so that it's more
likely to take less space. All uses changed.
(sortlines, sort): Spell out initialization instead of using an
initializer. This makes the initializer a bit easier to understand,
and avoids unnecessary stores into the spin lock.
---
src/sort.c | 40 +++++++++++++++++++++++++---------------
1 files changed, 25 insertions(+), 15 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 3d89a32..141af52 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -238,10 +238,10 @@ struct merge_node
struct line **dest; /* Pointer to destination of merge. */
size_t nlo; /* Total Lines remaining from LO. */
size_t nhi; /* Total lines remaining from HI. */
- size_t level; /* Level in merge tree. */
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_spinlock_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_spin_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_spin_unlock (&node->lock);
}
/* Destroy merge QUEUE. */
@@ -3477,10 +3477,17 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
struct line *lo = dest - total_lines;
struct line *hi = lo - nlo;
struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
- pthread_spinlock_t lock;
- pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
- struct merge_node node = {lo, hi, lo, hi, parent_end, nlo, nhi,
- parent->level + 1, parent, false, &lock};
+
+ 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_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
/* Calculate thread arguments. */
unsigned long int lo_threads = nthreads / 2;
@@ -3516,7 +3523,7 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
merge_loop (merge_queue, total_lines, tfp, temp_output);
}
- pthread_spin_destroy (&lock);
+ pthread_spin_destroy (&node.lock);
}
/* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3793,16 +3800,19 @@ sort (char * const *files, size_t nfiles, char const *output_file,
struct merge_node_queue merge_queue;
queue_init (&merge_queue, 2 * nthreads);
- pthread_spinlock_t lock;
- pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
- struct merge_node node =
- {NULL, NULL, NULL, NULL, NULL, buf.nlines,
- buf.nlines, MERGE_END, NULL, false, &lock};
+ 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_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
sortlines (line, line, nthreads, buf.nlines, &node, true,
&merge_queue, tfp, temp_output);
queue_destroy (&merge_queue);
- pthread_spin_destroy (&lock);
+ pthread_spin_destroy (&node.lock);
}
else
write_unique (line - 1, tfp, temp_output);
--
1.7.2
From a7beff9385827f47b97e089cfe15f2761c9a1efd Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 15:01:21 -0800
Subject: [PATCH 3/7] sort: put queue arg first
* src/sort.c (queue_check_insert, queue_check_insert_parent): Make
the queue arg first, for consistency with other functions such as
queue_insert that put the queue arg first. Rename from
check_insert and update_parent, respectively. All callers
changed.
---
src/sort.c | 16 ++++++++--------
1 files changed, 8 insertions(+), 8 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 141af52..af4b20c 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3312,12 +3312,12 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
return merged_lo + merged_hi;
}
-/* Insert NODE into QUEUE if it is not already queued, and if one of
+/* Into QUEUE, insert NODE if it is not already queued, and if one of
NODE's children has available lines and the other either has
available lines or has exhausted its lines. */
static void
-check_insert (struct merge_node *node, struct merge_node_queue *queue)
+queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
{
size_t lo_avail = node->lo - node->end_lo;
size_t hi_avail = node->hi - node->end_hi;
@@ -3334,17 +3334,17 @@ check_insert (struct merge_node *node, struct merge_node_queue *queue)
}
}
-/* Insert NODE's parent into QUEUE if the parent can now be worked on. */
+/* Into QUEUE, insert NODE's parent if the parent can now be worked on. */
static void
-update_parent (struct merge_node *node, size_t merged,
- struct merge_node_queue *queue)
+queue_check_insert_parent (struct merge_node_queue *queue,
+ struct merge_node *node, size_t merged)
{
if (node->level > MERGE_ROOT)
{
lock_node (node->parent);
*node->dest -= merged;
- check_insert (node->parent, queue);
+ queue_check_insert (queue, node->parent);
unlock_node (node->parent);
}
else if (node->nlo + node->nhi == 0)
@@ -3378,8 +3378,8 @@ merge_loop (struct merge_node_queue *queue,
}
size_t merged_lines = mergelines_node (node, total_lines, tfp,
temp_output);
- check_insert (node, queue);
- update_parent (node, merged_lines, queue);
+ queue_check_insert (queue, node);
+ queue_check_insert_parent (queue, node, merged_lines);
unlock_node (node);
}
--
1.7.2
From 66d448d0757c3ad3cd11f20142aeeefbdcdd354e Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 15:04:31 -0800
Subject: [PATCH 4/7] sort: simplify write_unique
* src/sort.c (write_unique): Simplify slightly so that there is
just one call to write_line, not two.
---
src/sort.c | 9 +++++----
1 files changed, 5 insertions(+), 4 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index af4b20c..1faf171 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3231,13 +3231,14 @@ write_unique (struct line const *line, FILE *tfp, char const *temp_output)
{
static struct line saved;
- if (!unique)
- write_line (line, tfp, temp_output);
- else if (!saved.text || compare (line, &saved))
+ if (unique)
{
+ if (saved.text && ! compare (line, &saved))
+ return;
saved = *line;
- write_line (line, tfp, temp_output);
}
+
+ write_line (line, tfp, temp_output);
}
/* Merge the lines currently available to a NODE in the binary
--
1.7.2
From 809431a68369189a3bc4be2388fdb0f20922c4e0 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 15:11:46 -0800
Subject: [PATCH 5/7] sort: fix problems with merge node dest pointer
* src/sort.c (mergelines_node): Return void, not size_t. All
callers changed. Change *node->dest here, not in caller.
Do not change node->dest: it's not needed and could cause problems
on (mostly theoretical) hosts that do not allow adding integers to
null pointers.
(queue_check_insert_parent): Omit MERGED parameter; no longer needed.
All callers changed.
---
src/sort.c | 13 +++++--------
1 files changed, 5 insertions(+), 8 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 1faf171..f7296d6 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3248,7 +3248,7 @@ write_unique (struct line const *line, FILE *tfp, char const *temp_output)
If merging at the top level, send output to TFP. TEMP_OUTPUT is
the name of TFP, or is null if TFP is standard output. */
-static size_t
+static void
mergelines_node (struct merge_node *restrict node, size_t total_lines,
FILE *tfp, char const *temp_output)
{
@@ -3277,6 +3277,7 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
else if (node->nlo == merged_lo)
while (node->hi != node->end_hi && to_merge--)
*--dest = *--node->hi;
+ *node->dest = dest;
}
else
{
@@ -3302,7 +3303,6 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
while (node->hi != node->end_hi && to_merge--)
write_unique (--node->hi, tfp, temp_output);
}
- node->dest -= lo_orig - node->lo + hi_orig - node->hi;
}
/* Update NODE. */
@@ -3310,7 +3310,6 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
merged_hi = hi_orig - node->hi;
node->nlo -= merged_lo;
node->nhi -= merged_hi;
- return merged_lo + merged_hi;
}
/* Into QUEUE, insert NODE if it is not already queued, and if one of
@@ -3339,12 +3338,11 @@ queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
static void
queue_check_insert_parent (struct merge_node_queue *queue,
- struct merge_node *node, size_t merged)
+ struct merge_node *node)
{
if (node->level > MERGE_ROOT)
{
lock_node (node->parent);
- *node->dest -= merged;
queue_check_insert (queue, node->parent);
unlock_node (node->parent);
}
@@ -3377,10 +3375,9 @@ merge_loop (struct merge_node_queue *queue,
queue_insert (queue, node);
break;
}
- size_t merged_lines = mergelines_node (node, total_lines, tfp,
- temp_output);
+ mergelines_node (node, total_lines, tfp, temp_output);
queue_check_insert (queue, node);
- queue_check_insert_parent (queue, node, merged_lines);
+ queue_check_insert_parent (queue, node);
unlock_node (node);
}
--
1.7.2
From 68bdf2752625e74a4783b441f69e79a7bd65ab5c Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 15:23:43 -0800
Subject: [PATCH 6/7] sort: clarify queue_check_insert
* src/sort.c (queue_check_insert): Clarify body a bit, and remove
no-longer-needed comment.
---
src/sort.c | 16 +++++-----------
1 files changed, 5 insertions(+), 11 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index f7296d6..3ed7c5b 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3319,18 +3319,12 @@ mergelines_node (struct merge_node *restrict node, size_t total_lines,
static void
queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
{
- size_t lo_avail = node->lo - node->end_lo;
- size_t hi_avail = node->hi - node->end_hi;
-
- /* Conditions for insertion:
- 1. NODE is not already in heap.
- 2. NODE has available lines from both it's children, OR one child has
- available lines, but the other has exhausted all its lines. */
- if ((!node->queued)
- && ((lo_avail && (hi_avail || !(node->nhi)))
- || (hi_avail && !(node->nlo))))
+ if (! node->queued)
{
- queue_insert (queue, node);
+ bool lo_avail = (node->lo - node->end_lo) != 0;
+ bool hi_avail = (node->hi - node->end_hi) != 0;
+ if (lo_avail ? hi_avail || ! node->nhi : hi_avail && ! node->nlo)
+ queue_insert (queue, node);
}
}
--
1.7.2
From 49c7f475ddcba334d76ef364d65882802c26163e Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Fri, 3 Dec 2010 15:39:50 -0800
Subject: [PATCH 7/7] sort: merge_queue -> queue
* src/sort.c (struct thread_args, sortlines_thread, sortlines, sort):
Rename "merge_queue" to "queue", for consistency with other functions
that just use the name "queue" for these things.
---
src/sort.c | 22 +++++++++++-----------
1 files changed, 11 insertions(+), 11 deletions(-)
diff --git a/src/sort.c b/src/sort.c
index 3ed7c5b..a4c2cbf 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3411,7 +3411,7 @@ struct thread_args
/* The priority queue controlling available work for the entire
internal sort. */
- struct merge_node_queue *const merge_queue;
+ struct merge_node_queue *const queue;
/* If at the top level, the file to output to, and the file's name.
If the file is standard output, the file's name is null. */
@@ -3426,7 +3426,7 @@ 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->merge_queue,
+ args->parent, args->lo_child, args->queue,
args->tfp, args->output_temp);
return NULL;
}
@@ -3459,7 +3459,7 @@ 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 *merge_queue,
+ struct merge_node_queue *queue,
FILE *tfp, char const *temp_output)
{
/* Create merge tree NODE. */
@@ -3486,13 +3486,13 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
unsigned long int hi_threads = nthreads - lo_threads;
pthread_t thread;
struct thread_args args = {lines, lo, lo_threads, total_lines, &node,
- true, merge_queue, tfp, temp_output};
+ 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,
- merge_queue, tfp, temp_output);
+ queue, tfp, temp_output);
pthread_join (thread, NULL);
}
else
@@ -3511,8 +3511,8 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
node.end_lo = lines - nlo;
node.end_hi = lines - nlo - nhi;
- queue_insert (merge_queue, &node);
- merge_loop (merge_queue, total_lines, tfp, temp_output);
+ queue_insert (queue, &node);
+ merge_loop (queue, total_lines, tfp, temp_output);
}
pthread_spin_destroy (&node.lock);
@@ -3789,8 +3789,8 @@ sort (char * const *files, size_t nfiles, char const *output_file,
}
if (1 < buf.nlines)
{
- struct merge_node_queue merge_queue;
- queue_init (&merge_queue, 2 * nthreads);
+ 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;
@@ -3802,8 +3802,8 @@ sort (char * const *files, size_t nfiles, char const *output_file,
pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
sortlines (line, line, nthreads, buf.nlines, &node, true,
- &merge_queue, tfp, temp_output);
- queue_destroy (&merge_queue);
+ &queue, tfp, temp_output);
+ queue_destroy (&queue);
pthread_spin_destroy (&node.lock);
}
else
--
1.7.2
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Sun, 05 Dec 2010 15:32:03 GMT)
Full text and
rfc822 format available.
Message #101 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Paul Eggert wrote:
> On 11/29/2010 02:46 PM, Paul Eggert wrote:
>> My current guess, by the way,
>> is that it's not a bug that can be triggered: it's merely
>> useless code that is harmless and can safely be removed.
>
> I removed it as part of the following series of cleanup
> patches. These are intended merely to refactor the code
> and simplify it a bit, to make it easier to fix the CPU
> spinlock bug. Please feel free to undo anything that
> looks at all questionable.
Hi Paul,
Thanks for all the clean-up.
I have no idea if the following is as a result of your changes,
since the segfault failure has been hard to reproduce.
It is from the sort-compress test, and has happened so far
only twice during "make -j9 check" on a quad-core F14 system:
Core was generated by `sort --compress-program=./dzip -S 1k in'.
Program terminated with signal 11, Segmentation fault.
#0 queue_check_insert (queue=0x7fffdbdc5620, node=0x5) at sort.c:3322
3322 if (! node->queued)
(gdb) p node
$1 = (struct merge_node *) 0x5
(gdb) bt
#0 queue_check_insert (queue=0x7fffdbdc5620, node=0x5) at sort.c:3322
#1 0x00000000004055a9 in queue_check_insert_parent (
lines=<value optimized out>, dest=<value optimized out>,
nthreads=140173261458952, total_lines=10, parent=<value optimized out>,
lo_child=<value optimized out>, queue=0x7fffdbdc5620, tfp=0x1c2fb90,
temp_output=0x1c2f72c "./sortpns55x") at sort.c:3340
#2 merge_loop (lines=<value optimized out>, dest=<value optimized out>,
nthreads=140173261458952, total_lines=10, parent=<value optimized out>,
lo_child=<value optimized out>, queue=0x7fffdbdc5620, tfp=0x1c2fb90,
temp_output=0x1c2f72c "./sortpns55x") at sort.c:3374
#3 sortlines (lines=<value optimized out>, dest=<value optimized out>,
nthreads=140173261458952, total_lines=10, parent=<value optimized out>,
lo_child=<value optimized out>, queue=0x7fffdbdc5620, tfp=0x1c2fb90,
temp_output=0x1c2f72c "./sortpns55x") at sort.c:3515
#4 0x00000000004059cb in sortlines_thread (data=<value optimized out>)
at sort.c:3428
#5 0x0000003f49806d5b in start_thread () from /lib64/libpthread-2.12.90.so
#6 0x0000003f48ce4aad in clone () from /lib64/libc-2.12.90.so
However, there is another failure that makes me suspicious:
(also based on sort-compress):
seq -w 200000 > exp && tac exp > in
PATH=.:$PATH ./sort --compress-program=dzip -S 1k in > out
That gets stuck in waitpid (from sort.c's reap), waiting for a
dzip invocation that appears will never terminate. This is also
on that same 4-core system, and is relatively easy to reproduce,
so it should be easy to identify the offending change, but I'm
out of time, now.
The hang is also reproducible with just 2000 input lines,
but then it doesn't arise as consistently.
I'll note in passing that the spinlock CPU utilization problem
is particularly noticeable when using --compress-program= because
there is a lot more waiting.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 06 Dec 2010 05:11:02 GMT)
Full text and
rfc822 format available.
Message #104 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Hi Professor Eggert,
On Fri, Dec 3, 2010 at 1:10 PM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
> On 12/03/10 12:18, Chen Guo wrote:
> Either option (either switch to mutexes everywhere, or have the top-level
> merge go to memory) should work. Perhaps we should try both and benchmark
> them.
Test machine is 4 core i7. The numbers I'm giving are averaged
over 20 runs, given in seconds, and are of the form elapsed / user +
system.
spinlock:
1 thread: 3.354 / 3.349
2 threads: 1.960 / 3.812
4 threads: 1.366 / 5.085
mutex:
1 thread: 3.354 / 3.350
2 threads: 2.062 / 3.628
4 threads: 1.497 / 4.172
spin/ output after
1 thread: 3.519 / 3.517
2 threads: 2.098 / 3.996
4 threads: 1.488 / 5.347
It seems if we have to choose between mutex and output post-sort,
mutex is the way to go. Mutex is faster in the single threaded case,
while in multithreaded the elapsed time is negligibly different, the
user time is much greater. With spinlocks only, the greater system
time was justified (though some might disagree) by the lower elapsed
time. With spinlock outputting post-sort, there is no more
justification for the higher user time.
Before saying anything else, I should note that for mutexes, on 4
threads 20% of the time there's a segfault on a seemingly innocuous
line in queue_insert ():
node->queued = true
GDB shows that pointers all look normal, and I could not trigger this
over 10 runs with valgrind (it seems valgrind is singlethreaded). If
we do decide to go back to mutexes, I'll look into this issue more.
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 06 Dec 2010 06:56:02 GMT)
Full text and
rfc822 format available.
Message #107 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 12/05/2010 09:16 PM, Chen Guo wrote:
> Before saying anything else, I should note that for mutexes, on 4
> threads 20% of the time there's a segfault on a seemingly innocuous
> line in queue_insert ():
> node->queued = true
It does sound like mutexes are the way to go, and that this bug
needs to be fixed. I assume that this is the call to queue_insert
from queue_check_insert_parent? What's the backtrace? (And
what patch are you using, to get mutexes?)
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Mon, 06 Dec 2010 08:20:03 GMT)
Full text and
rfc822 format available.
Message #110 received at 7489 <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
Hi Professor Eggert,
On Sun, Dec 5, 2010 at 11:01 PM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
> On 12/05/2010 09:16 PM, Chen Guo wrote:
>> Before saying anything else, I should note that for mutexes, on 4
>> threads 20% of the time there's a segfault on a seemingly innocuous
>> line in queue_insert ():
>> node->queued = true
>
> It does sound like mutexes are the way to go, and that this bug
> needs to be fixed. I assume that this is the call to queue_insert
> from queue_check_insert_parent? What's the backtrace? (And
> what patch are you using, to get mutexes?)
>
I've attached the patch (inlined at the bottom). Here's the GDB
crash, with backtrace. I also printed node->queued in GDB, so it's
evident that its accessible.
(gdb) run --parallel 2 rec_1M > /dev/null
Starting program: /data/chen/Coding/Coreutils/test/sort-mutex
--parallel 2 rec_1M > /dev/null
[Thread debugging using libthread_db enabled]
[New Thread 0x7fffcbb95710 (LWP 19850)]
Program received signal SIGSEGV, Segmentation fault.
queue_insert (queue=0x7fffffffe0c0, node=0x7ffff7ddc560) at sort.c:3202
3202 node->queued = true;
(gdb) bt
#0 queue_insert (queue=0x7fffffffe0c0, node=0x7ffff7ddc560) at sort.c:3202
#1 0x0000000000405844 in queue_check_insert_parent (lines=<value
optimized out>, dest=<value optimized out>, nthreads=<value optimized
out>, total_lines=<value optimized out>, parent=<value optimized out>,
lo_child=<value optimized out>, queue=0x7fffffffe0c0,
tfp=0x7ffff7bb9780, temp_output=0x0) at sort.c:3340
#2 merge_loop (lines=<value optimized out>, dest=<value optimized
out>, nthreads=<value optimized out>, total_lines=<value optimized
out>, parent=<value optimized out>, lo_child=<value optimized out>,
queue=0x7fffffffe0c0,
tfp=0x7ffff7bb9780, temp_output=0x0) at sort.c:3374
#3 sortlines (lines=<value optimized out>, dest=<value optimized
out>, nthreads=<value optimized out>, total_lines=<value optimized
out>, parent=<value optimized out>, lo_child=<value optimized out>,
queue=0x7fffffffe0c0,
tfp=0x7ffff7bb9780, temp_output=0x0) at sort.c:3515
#4 0x0000000000405c2b in sortlines (lines=0x7ffff7344030, dest=<value
optimized out>, nthreads=<value optimized out>, total_lines=<value
optimized out>, parent=<value optimized out>, lo_child=<value
optimized out>,
queue=0x7fffffffe0c0, tfp=0x7ffff7bb9780, temp_output=0x0) at sort.c:3494
#5 0x00000000004095e8 in sort (argc=<value optimized out>,
argv=<value optimized out>) at sort.c:3804
#6 main (argc=<value optimized out>, argv=<value optimized out>) at sort.c:4576
(gdb) print node
$1 = (struct merge_node *) 0x7ffff7ddc560
(gdb) print node->queued
$2 = false
And here's the patch:
From 5a1d0b8f1a4c6d7cd99da7376f8c03f8a4cc2be9 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] sort: change spinlocks to mutexes.
* src/sort.c: (struct merge_node) Change member lock to mutex. All
uses changed.
---
src/sort.c | 14 +++++++-------
1 files changed, 7 insertions(+), 7 deletions(-)
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);
--
1.7.1
[mutex.patch (text/x-patch, attachment)]
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 07 Dec 2010 02:18:02 GMT)
Full text and
rfc822 format available.
Message #113 received at 7489 <at> debbugs.gnu.org (full text, mbox):
On 12/05/10 03:21, Jim Meyering wrote:
> seq -w 200000 > exp && tac exp > in
> PATH=.:$PATH ./sort --compress-program=dzip -S 1k in > out
>
> That gets stuck in waitpid (from sort.c's reap), waiting for a
> dzip invocation that appears will never terminate. This is also
> on that same 4-core system, and is relatively easy to reproduce,
> so it should be easy to identify the offending change, but I'm
> out of time, now.
>
I've verified this bug. It occurs regardless of whether the
December 3 changes are applied, so it looks like it was an
earlier change. I've also verified that it occurs with
--parallel=1 so it seems unlikely it would be thread-related.
What happens is that 'sort' creates a pipe to a compressor
but then never closes the pipe. When it waits for the compressor
to finish there is an obvious deadlock.
I'll see if I can track it down, but my guess it's somewhere
in the compressor/decompressor code. It's doing some lazy
evaluation and I wouldn't be surprised if that goes haywire
in some cases.
I'd guess there's also a bug in the thread code too,
having to do with your core dump (and Chen's; could be
two bugs).
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 07 Dec 2010 10:02:01 GMT)
Full text and
rfc822 format available.
Message #116 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Chen Guo wrote:
...
> I've attached the patch (inlined at the bottom). Here's the GDB
> crash, with backtrace. I also printed node->queued in GDB, so it's
> evident that its accessible.
>
> (gdb) run --parallel 2 rec_1M > /dev/null
> Starting program: /data/chen/Coding/Coreutils/test/sort-mutex
> --parallel 2 rec_1M > /dev/null
> [Thread debugging using libthread_db enabled]
> [New Thread 0x7fffcbb95710 (LWP 19850)]
>
> Program received signal SIGSEGV, Segmentation fault.
> queue_insert (queue=0x7fffffffe0c0, node=0x7ffff7ddc560) at sort.c:3202
> 3202 node->queued = true;
> (gdb) bt
...
> (gdb) print node
> $1 = (struct merge_node *) 0x7ffff7ddc560
> (gdb) print node->queued
> $2 = false
Could it be that you're looking at one thread,
while the segfault happened in another?
In my core dump, the offending "node" pointer had a value of 5.
...
> And here's the patch:
>
> Subject: [PATCH] sort: change spinlocks to mutexes.
>
> * src/sort.c: (struct merge_node) Change member lock to mutex. All
> uses changed.
Hi Chen,
Thanks for the patch.
Since this fixes a bug, I've added a NEWS entry.
Also, since with your patch, the sort-spinlock-abuse
test now passes, I've adjusted tests/Makefile.am to reflect that.
The segfault may be easier to reproduce with mutexes,
but I've seen the same one also with spinlocks (albeit rarely).
Here's the amended patch:
From 7a80bc63e1411f0a2ed7c4259e852de34591a65a 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] 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.3.2.92.g7e4eb
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 07 Dec 2010 11:20:03 GMT)
Full text and
rfc822 format available.
Message #119 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Chen Guo wrote:
> Hi Professor Eggert,
> On Sun, Dec 5, 2010 at 11:01 PM, Paul Eggert <eggert <at> cs.ucla.edu> wrote:
>> On 12/05/2010 09:16 PM, Chen Guo wrote:
>>> Before saying anything else, I should note that for mutexes, on 4
>>> threads 20% of the time there's a segfault on a seemingly innocuous
>>> line in queue_insert ():
>>> node->queued = true
>>
>> It does sound like mutexes are the way to go, and that this bug
>> needs to be fixed. I assume that this is the call to queue_insert
>> from queue_check_insert_parent? What's the backtrace? (And
>> what patch are you using, to get mutexes?)
>>
>
> I've attached the patch (inlined at the bottom). Here's the GDB
> crash, with backtrace. I also printed node->queued in GDB, so it's
> evident that its accessible.
>
> (gdb) run --parallel 2 rec_1M > /dev/null
> Starting program: /data/chen/Coding/Coreutils/test/sort-mutex
> --parallel 2 rec_1M > /dev/null
Hi Chen,
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
Information forwarded
to
owner <at> debbugs.gnu.org, bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 07 Dec 2010 20:57:03 GMT)
Full text and
rfc822 format available.
Message #122 received at 7489 <at> debbugs.gnu.org (full text, mbox):
Hi Jim,
On Tue, Dec 7, 2010 at 3:24 AM, Jim Meyering <jim <at> meyering.net> wrote:
> Hi Chen,
>
> 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.
Information forwarded
to
bug-coreutils <at> gnu.org:
bug#7489; Package
coreutils.
(Tue, 30 Oct 2018 07:48:02 GMT)
Full text and
rfc822 format available.
Message #125 received at 7489 <at> debbugs.gnu.org (full text, mbox):
(triaging old bugs)
Hello,
This long thread ( http://bugs.gnu.org/7489 )
deals with multiple parallel-sort bugs, resulting in many commits:
====
1d0a12037 Paul Eggert 2010-12-22 sort: minor performance tweak with
num_processors
41159f960 Pádraig Brady 2010-12-20 maint: fix a typo in sort --parallel
help message
0e181024c Pádraig Brady 2010-12-18 sort: use at most 8 threads by default
8e81a99c2 Paul Eggert 2010-12-16 sort: do not generate thousands of
subprocesses for 16-way merge
1b31ce698 Paul Eggert 2010-12-16 sort: fix hang with sort --compress
f3c584d1e Paul Eggert 2010-12-16 sort: don't dump core when merging
from input twice
14ad7a255 Paul Eggert 2010-12-14 sort: fix very-unlikely buffer
overrun when merging to input file
8f40ed634 Paul Eggert 2010-12-14 sort: document --compress reaper fixes
0da4d8430 Paul Eggert 2010-12-13 sort: fix some --compress reaper bugs
ad61335bf Jim Meyering 2010-12-11 sort: avoid segfault when using two
or more threads
9a9d69e9e Jim Meyering 2010-12-11 sort: syntax cleanup
27e997d0e Paul Eggert 2010-12-11 sort: integer overflow checks in
thread counts, etc.
c9db0ac6d Chen Guo 2010-12-10 sort: preallocate merge tree nodes
to heap.
d1f700355 Paul Eggert 2010-12-10 sort: comment fix
621876ff4 Chen Guo 2010-12-06 sort: use mutexes, not spinlocks
(avoid busy loop on blocked output)
a1629ba1e Jim Meyering 2010-12-05 tests: remove useless definition of
$SORT in sort-compress
cd00fa6ee Paul Eggert 2010-12-03 sort: merge_queue -> queue
fb282c7b3 Paul Eggert 2010-12-03 sort: clarify queue_check_insert
fb41e82c7 Paul Eggert 2010-12-03 sort: fix problems with merge node
dest pointer
f2d977aff Paul Eggert 2010-12-03 sort: simplify write_unique
6f4279421 Paul Eggert 2010-12-03 sort: put queue arg first
f35f4b339 Paul Eggert 2010-12-03 sort: tune struct_merge_node slightly
eb989f4b7 Paul Eggert 2010-12-03 sort: Clarify comments
0ec869e8b Paul Eggert 2010-12-01 sort: fix bug on 64-bit hosts with
at least 32768 processors
===
All the above were included in coreutils 8.8.
I assume the sort bugs are fixed, despite no 'final' message in the thread.
If there are no objections, I'll close this bug in couple of days.
-assaf
Added tag(s) fixed.
Request was from
Assaf Gordon <assafgordon <at> gmail.com>
to
control <at> debbugs.gnu.org.
(Tue, 06 Nov 2018 17:56:01 GMT)
Full text and
rfc822 format available.
bug closed, send any further explanations to
7489 <at> debbugs.gnu.org and DJ Lucas <dj <at> linuxfromscratch.org>
Request was from
Assaf Gordon <assafgordon <at> gmail.com>
to
control <at> debbugs.gnu.org.
(Tue, 06 Nov 2018 17:56:01 GMT)
Full text and
rfc822 format available.
bug archived.
Request was from
Debbugs Internal Request <help-debbugs <at> gnu.org>
to
internal_control <at> debbugs.gnu.org.
(Wed, 05 Dec 2018 12:24:06 GMT)
Full text and
rfc822 format available.
This bug report was last modified 5 years and 356 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.