From: Junio C Hamano <hidden> Date: 2018-08-13 20:21:02
Johannes Sixt [off-list ref] writes:
The Windows CRT implements O_APPEND "manually": on write() calls, the
file pointer is set to EOF before the data is written. Clearly, this is
not atomic. And in fact, this is the root cause of failures observed in
t5552-skipping-fetch-negotiator.sh and t5503-tagfollow.sh, where
different processes write to the same trace file simultanously; it also
occurred in t5400-send-pack.sh, but there it was worked around in
71406ed4d6 ("t5400: avoid concurrent writes into a trace file",
2017-05-18).
Fortunately, Windows does support atomic O_APPEND semantics using the
file access mode FILE_APPEND_DATA. Provide an implementation that does.
This implementation is minimal in such a way that it only implements
the open modes that are actually used in the Git code base. Emulation
for other modes can be added as necessary later. To become aware of
the necessity early, the unusal error ENOSYS is reported if an
unsupported mode is encountered.
Diagnosed-by: Johannes Schindelin [off-list ref]
Helped-by: Jeff Hostetler [off-list ref]
Signed-off-by: Johannes Sixt <redacted>
---
compat/mingw.c | 41 +++++++++++++++++++++++++++++++++++++++--
1 file changed, 39 insertions(+), 2 deletions(-)
Nice.
I wonder how much more expensive using this implementation is
compared with the original "race susceptible" open(), when raciness
is known not to be an issue (e.g. there is higher level lock that
protects the appending).
If it turns out to be quite more costly, I do not think we'd mind
introducing a thin wrapper
#ifndef race_safe_append_open
#ifndef race_safe_append_open(fn) open(fn, O_WRONLY|O_APPEND|O_CREAT, 0666)
#endif
in git-compat-util.h after it includes "compat/mingw.h" and replace
the call to open(... O_APPEND ...) in trace.c::get_trace_fd() with a
call to that wrapper. That way, other codepaths that use O_APPEND
(namely, reflog and todo-list writers) can avoid the additional
cost, if any.
Some may find it beneficial from code readability POV because that
approach marks the codepath that needs to have non-racy fd more
explicitly.
I am assuming that in this case other users of O_APPEND are not
performance critical, so hopefully the following is only theoretical
and not necessary.
git-compat-util.h | 5 +++++
trace.c | 2 +-
2 files changed, 6 insertions(+), 1 deletion(-)
@@ -47,7 +47,7 @@ static int get_trace_fd(struct trace_key *key)elseif(strlen(trace)==1&&isdigit(*trace))key->fd=atoi(trace);elseif(is_absolute_path(trace)){-intfd=open(trace,O_WRONLY|O_APPEND|O_CREAT,0666);+intfd=race_safe_append_open(trace);if(fd==-1){warning("could not open '%s' for tracing: %s",trace,strerror(errno));
From: Johannes Sixt <hidden> Date: 2018-08-13 21:05:36
Am 13.08.2018 um 22:20 schrieb Junio C Hamano:
Johannes Sixt [off-list ref] writes:
quoted
The Windows CRT implements O_APPEND "manually": on write() calls, the
file pointer is set to EOF before the data is written. Clearly, this is
not atomic. And in fact, this is the root cause of failures observed in
t5552-skipping-fetch-negotiator.sh and t5503-tagfollow.sh, where
different processes write to the same trace file simultanously; it also
occurred in t5400-send-pack.sh, but there it was worked around in
71406ed4d6 ("t5400: avoid concurrent writes into a trace file",
2017-05-18).
Fortunately, Windows does support atomic O_APPEND semantics using the
file access mode FILE_APPEND_DATA. Provide an implementation that does.
This implementation is minimal in such a way that it only implements
the open modes that are actually used in the Git code base. Emulation
for other modes can be added as necessary later. To become aware of
the necessity early, the unusal error ENOSYS is reported if an
unsupported mode is encountered.
Diagnosed-by: Johannes Schindelin [off-list ref]
Helped-by: Jeff Hostetler [off-list ref]
Signed-off-by: Johannes Sixt <redacted>
---
compat/mingw.c | 41 +++++++++++++++++++++++++++++++++++++++--
1 file changed, 39 insertions(+), 2 deletions(-)
Nice.
I wonder how much more expensive using this implementation is
compared with the original "race susceptible" open(), when raciness
is known not to be an issue (e.g. there is higher level lock that
protects the appending).
Certainly, the former way that uses two syscalls
(SetFilePointer+WriteFile) is more costly than this new way with just
one syscall (WriteFile). Of course, I don't know how atomic append would
be implemented in the kernel, but I can't think of a reason why it
should be slow on Windows, but fast on POSIX.
(But I can't provide numbers to back up my gut feeling...)
(And I also assume that you are not worried about the performance of
open() itself.)
...[define race_safe_append_open]... and replace
the call to open(... O_APPEND ...) in trace.c::get_trace_fd() with a
call to that wrapper. That way, other codepaths that use O_APPEND
(namely, reflog and todo-list writers) can avoid the additional
cost, if any.
Some may find it beneficial from code readability POV because that
approach marks the codepath that needs to have non-racy fd more
explicitly.
O_APPEND is POSIX and means race-free append. If you mark some call
sites with O_APPEND, then that must be the ones that need race-free
append. Hence, you would have to go the other route: Mark those call
sites that do _not_ need race-free append with some custom
function/macro. (Or mark both with different helpers and avoid writing
down O_APPEND.)
-- Hannes
The Windows CRT implements O_APPEND "manually": on write() calls, the
file pointer is set to EOF before the data is written. Clearly, this is
not atomic. And in fact, this is the root cause of failures observed in
t5552-skipping-fetch-negotiator.sh and t5503-tagfollow.sh, where
different processes write to the same trace file simultanously; it also
occurred in t5400-send-pack.sh, but there it was worked around in
71406ed4d6 ("t5400: avoid concurrent writes into a trace file",
2017-05-18).
Fortunately, Windows does support atomic O_APPEND semantics using the
file access mode FILE_APPEND_DATA. Provide an implementation that does.
This implementation is minimal in such a way that it only implements
the open modes that are actually used in the Git code base. Emulation
for other modes can be added as necessary later. To become aware of
the necessity early, the unusal error ENOSYS is reported if an
unsupported mode is encountered.
Diagnosed-by: Johannes Schindelin [off-list ref]
Helped-by: Jeff Hostetler [off-list ref]
Signed-off-by: Johannes Sixt <redacted>
---
compat/mingw.c | 41 +++++++++++++++++++++++++++++++++++++++--
1 file changed, 39 insertions(+), 2 deletions(-)
Nice.
I wonder how much more expensive using this implementation is
compared with the original "race susceptible" open(), when raciness
is known not to be an issue (e.g. there is higher level lock that
protects the appending).
Certainly, the former way that uses two syscalls
(SetFilePointer+WriteFile) is more costly than this new way with just
one syscall (WriteFile). Of course, I don't know how atomic append
would be implemented in the kernel, but I can't think of a reason why
it should be slow on Windows, but fast on POSIX.
(But I can't provide numbers to back up my gut feeling...)
(And I also assume that you are not worried about the performance of
open() itself.)
quoted
...[define race_safe_append_open]... and replace
the call to open(... O_APPEND ...) in trace.c::get_trace_fd() with a
call to that wrapper. That way, other codepaths that use O_APPEND
(namely, reflog and todo-list writers) can avoid the additional
cost, if any.
Some may find it beneficial from code readability POV because that
approach marks the codepath that needs to have non-racy fd more
explicitly.
O_APPEND is POSIX and means race-free append. If you mark some call
sites with O_APPEND, then that must be the ones that need race-free
append. Hence, you would have to go the other route: Mark those call
sites that do _not_ need race-free append with some custom
function/macro. (Or mark both with different helpers and avoid writing
down O_APPEND.)
O_APPEND in POSIX is race-free only up to PIPE_MAX bytes written at a
time, which is e.g. 2^12 by default on linux, after that all bets are
off and the kernel is free to interleave different write calls.
I've written code (not for git.git) that implements such a
"write_non_racy" function in the past, and the first thing it needs to
do is to assert that the length of the buffer being written doesn't
exceed PIPE_MAX.
So there's still a use for a race_safe_append_open() wrapper function,
to O_APPEND and do the PIPE_MAX assertion. Otherwise you're calling a
"safe" function which isn't safe at all anymore.
I have no idea what the equivalent of that PIPE_MAX caveat is on
non-POSIX (e.g. Windows), but would be interested to find out.
From: Jeff King <hidden> Date: 2018-08-13 22:37:05
On Mon, Aug 13, 2018 at 11:22:10PM +0200, Ævar Arnfjörð Bjarmason wrote:
quoted
O_APPEND is POSIX and means race-free append. If you mark some call
sites with O_APPEND, then that must be the ones that need race-free
append. Hence, you would have to go the other route: Mark those call
sites that do _not_ need race-free append with some custom
function/macro. (Or mark both with different helpers and avoid writing
down O_APPEND.)
O_APPEND in POSIX is race-free only up to PIPE_MAX bytes written at a
time, which is e.g. 2^12 by default on linux, after that all bets are
off and the kernel is free to interleave different write calls.
This is a claim I've run across often, but I've never seen a good
citation for it.
Certainly atomic writes to _pipes_ are determined by PIPE_BUF (which
IIRC is not even a constant on Linux, but can be changed at run-time).
But is it relevant for regular-file writes?
Another gem I found while digging on this O_APPEND/FILE_APPEND_DATA
stuff the other day: somebody claimed that the max atomic-append size on
Linux is 4096 and 1024 on Windows. But their experimental script was
done in bash! So I suspect they were really just measuring the size of
stdio buffers.
Here's my attempt at a test setup. This C program forces two processes
to write simultaneously to the same file with O_APPEND:
-- >8 --
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>
static void doit(int size, const char *fn, char c)
{
int fd;
char *buf;
fd = open(fn, O_WRONLY|O_APPEND|O_CREAT, 0666);
if (fd < 0) {
perror("open");
return;
}
buf = malloc(size);
memset(buf, c, size);
while (1)
write(fd, buf, size);
}
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
if (fork())
doit(size, argv[2], '1');
else
doit(size, argv[2], '2');
return 0;
}
-- 8< --
and then this program checks that we saw atomic units of the correct
size:
-- >8 --
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
char *buf;
buf = malloc(size);
while (1) {
int i;
/* assume atomic reads, i.e., no signals */
int r = read(0, buf, size);
if (!r)
break;
for (i = 1; i < size; i++) {
if (buf[i] != buf[0]) {
fprintf(stderr, "overlap\n");
return 1;
}
}
}
return 0;
}
-- 8< --
And then you can do something like:
for size in 4097 8193 16385 32769 65537 131073 262145 524289 1048577; do
>out ;# clean up from last run
echo "Trying $size..."
timeout 5 ./write $size out
if ! ./check $size <out; then
echo "$size failed"
break
fi
done
On my Linux system, each of those seems to write several gigabytes
without overlapping. I did manage to hit some failing cases, but they
were never sheared writes, but rather cases where there was an
incomplete write at the end-of-file.
So obviously this is all a bit of a tangent. I'd be fine declaring that
trace output is generally small enough not to worry about this in the
first place. But those results show that it shouldn't matter even if
we're writing 1MB trace lines on Linux. I wouldn't be at all surprised
to see different results on other operating systems, though.
-Peff
On Mon, Aug 13, 2018 at 11:22:10PM +0200, Ævar Arnfjörð Bjarmason wrote:
quoted
quoted
O_APPEND is POSIX and means race-free append. If you mark some call
sites with O_APPEND, then that must be the ones that need race-free
append. Hence, you would have to go the other route: Mark those call
sites that do _not_ need race-free append with some custom
function/macro. (Or mark both with different helpers and avoid writing
down O_APPEND.)
O_APPEND in POSIX is race-free only up to PIPE_MAX bytes written at a
time, which is e.g. 2^12 by default on linux, after that all bets are
off and the kernel is free to interleave different write calls.
[I should have said PIPE_BUF, not PIPE_MAX]
This is a claim I've run across often, but I've never seen a good
citation for it.
To clarify I'm claiming that this is not a guarantee POSIX or linux
support. Not that in practice it doesn't work on some systems.
The relevant POSIX docs are here:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/write.html
Write requests of {PIPE_BUF} bytes or less shall not be interleaved
with data from other processes doing writes on the same pipe. Writes
of greater than {PIPE_BUF} bytes may have data interleaved, on
arbitrary boundaries, with writes by other processes, whether or not
the O_NONBLOCK flag of the file status flags is set.
And the Linux docs at http://man7.org/linux/man-pages/man7/pipe.7.html
say something similar:
Writes of more than PIPE_BUF bytes may be nonatomic: the kernel may
interleave the data with data written by other processes. POSIX.1
requires PIPE_BUF to be at least 512 bytes. (On Linux, PIPE_BUF is
4096 bytes.)
Certainly atomic writes to _pipes_ are determined by PIPE_BUF (which
IIRC is not even a constant on Linux, but can be changed at run-time).
But is it relevant for regular-file writes?
I believe it's hardcoded at PIPE_BUF which is defined as PAGE_SIZE on
linux. I think you may be thinking of /proc/sys/fs/pipe-max-pages which
is the number of pages that a pipe will take before filling up, but I
may be wrong.
Another gem I found while digging on this O_APPEND/FILE_APPEND_DATA
stuff the other day: somebody claimed that the max atomic-append size on
Linux is 4096 and 1024 on Windows. But their experimental script was
done in bash! So I suspect they were really just measuring the size of
stdio buffers.
Yes, and some tests for this are wrong because they use e.g. "print" in
some higher-level language which'll always split stuff into writes of
1024 or something.
Here's my attempt at a test setup. This C program forces two processes
to write simultaneously to the same file with O_APPEND:
-- >8 --
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>
static void doit(int size, const char *fn, char c)
{
int fd;
char *buf;
fd = open(fn, O_WRONLY|O_APPEND|O_CREAT, 0666);
if (fd < 0) {
perror("open");
return;
}
buf = malloc(size);
memset(buf, c, size);
while (1)
write(fd, buf, size);
}
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
if (fork())
doit(size, argv[2], '1');
else
doit(size, argv[2], '2');
return 0;
}
-- 8< --
and then this program checks that we saw atomic units of the correct
size:
-- >8 --
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
char *buf;
buf = malloc(size);
while (1) {
int i;
/* assume atomic reads, i.e., no signals */
int r = read(0, buf, size);
if (!r)
break;
for (i = 1; i < size; i++) {
if (buf[i] != buf[0]) {
fprintf(stderr, "overlap\n");
return 1;
}
}
}
return 0;
}
-- 8< --
And then you can do something like:
for size in 4097 8193 16385 32769 65537 131073 262145 524289 1048577; do
>out ;# clean up from last run
echo "Trying $size..."
timeout 5 ./write $size out
if ! ./check $size <out; then
echo "$size failed"
break
fi
done
On my Linux system, each of those seems to write several gigabytes
without overlapping. I did manage to hit some failing cases, but they
were never sheared writes, but rather cases where there was an
incomplete write at the end-of-file.
Yeah I can't make that fail experimentally either, except in the case
you mentioned. I also checked on a NetBSD & OpenBSD and OpenBSD box I
have access to, same thing.
So obviously this is all a bit of a tangent. I'd be fine declaring that
trace output is generally small enough not to worry about this in the
first place. But those results show that it shouldn't matter even if
we're writing 1MB trace lines on Linux. I wouldn't be at all surprised
to see different results on other operating systems, though.
I don't know how this works internally in the kernel, but I'd be very
careful to make that assertion. Most likely this in practice depends on
what FS you're using, its mount options, whether fsync() is involved,
I/O pressure etc.
FWIW this is something I've ran into in the past on Linux as a practical
matter, but that was many kernel versions ago, so maybe the semantics
changed.
We had an ad-hoc file format with each chunk a "<start
marker><length><content><end marker>\n" format (and the <content> was
guaranteed not to contain "\n"). These would be written to the same file
by N workers. We would get corrupt data because of this in cases where
we were writing more than PIPE_BUF, e.g. start markers for unrelated
payloads interleaved with content, lines that were incorrectly formed
etc.
But yeah, whether this is a practical concern for git trace output is
another matter. I just wanted to chime in to note that atomic appends to
files are only portable on POSIX up to PIPE_BUF.
From: Jeff King <hidden> Date: 2018-08-14 14:53:48
On Tue, Aug 14, 2018 at 03:47:54PM +0200, Ævar Arnfjörð Bjarmason wrote:
The relevant POSIX docs are here:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/write.html
Write requests of {PIPE_BUF} bytes or less shall not be interleaved
with data from other processes doing writes on the same pipe. Writes
of greater than {PIPE_BUF} bytes may have data interleaved, on
arbitrary boundaries, with writes by other processes, whether or not
the O_NONBLOCK flag of the file status flags is set.
Right, this is the part I've seen, but it's pretty clearly only about
pipes, not regular files.
quoted
Certainly atomic writes to _pipes_ are determined by PIPE_BUF (which
IIRC is not even a constant on Linux, but can be changed at run-time).
But is it relevant for regular-file writes?
I believe it's hardcoded at PIPE_BUF which is defined as PAGE_SIZE on
linux. I think you may be thinking of /proc/sys/fs/pipe-max-pages which
is the number of pages that a pipe will take before filling up, but I
may be wrong.
Yeah, you're probably right.
quoted
So obviously this is all a bit of a tangent. I'd be fine declaring that
trace output is generally small enough not to worry about this in the
first place. But those results show that it shouldn't matter even if
we're writing 1MB trace lines on Linux. I wouldn't be at all surprised
to see different results on other operating systems, though.
I don't know how this works internally in the kernel, but I'd be very
careful to make that assertion. Most likely this in practice depends on
what FS you're using, its mount options, whether fsync() is involved,
I/O pressure etc.
Definitely it depends on the filesystem (and I'm pretty sure that at
least old versions of NFS could not possibly do O_APPEND correctly,
because the protocol did not support an atomic seek+write).
I agree that the experiment I did doesn't really tell us anything for
sure. It _seems_ to work, but the machine was not under any kind of
memory or I/O pressure.
I'd feel pretty confident that writes under a page are always going to
be fine, but anything else is "seems to work". To me that's enough for
tracing, as the absolute worst case is jumbled output, not an on-disk
corruption.
FWIW this is something I've ran into in the past on Linux as a practical
matter, but that was many kernel versions ago, so maybe the semantics
changed.
We had an ad-hoc file format with each chunk a "<start
marker><length><content><end marker>\n" format (and the <content> was
guaranteed not to contain "\n"). These would be written to the same file
by N workers. We would get corrupt data because of this in cases where
we were writing more than PIPE_BUF, e.g. start markers for unrelated
payloads interleaved with content, lines that were incorrectly formed
etc.
Interesting. I wonder if it is because of PIPE_BUF, or it is simply the
page size, which also happens to be the value of PIPE_BUF.
But yeah, whether this is a practical concern for git trace output is
another matter. I just wanted to chime in to note that atomic appends to
files are only portable on POSIX up to PIPE_BUF.
I still think POSIX doesn't say anything either way here. The PIPE_BUF
bits are _just_ about pipes. At any rate, I think we have a decent
handle on what systems actually _do_, which is more important than POSIX
anyway.
-Peff
From: Johannes Sixt <hidden> Date: 2018-08-14 18:29:09
Am 14.08.2018 um 00:37 schrieb Jeff King:
And then you can do something like:
for size in 4097 8193 16385 32769 65537 131073 262145 524289 1048577; do
>out ;# clean up from last run
echo "Trying $size..."
timeout 5 ./write $size out
if ! ./check $size <out; then
echo "$size failed"
break
fi
done
On my Linux system, each of those seems to write several gigabytes
without overlapping. I did manage to hit some failing cases, but they
were never sheared writes, but rather cases where there was an
incomplete write at the end-of-file.
I used your programs with necessary adjustments (as fork() is not
available), and did similar tests with concurrent processes. With packet
sizes 1025, 4093, 7531 (just to include some odd number), and 8193 I did
not observe any overlapping or short writes.
I'm now very confident that we are on the safe side for our purposes.
-- Hannes
From: Jeff King <hidden> Date: 2018-08-14 19:17:12
On Tue, Aug 14, 2018 at 08:29:04PM +0200, Johannes Sixt wrote:
Am 14.08.2018 um 00:37 schrieb Jeff King:
quoted
And then you can do something like:
for size in 4097 8193 16385 32769 65537 131073 262145 524289 1048577; do
>out ;# clean up from last run
echo "Trying $size..."
timeout 5 ./write $size out
if ! ./check $size <out; then
echo "$size failed"
break
fi
done
On my Linux system, each of those seems to write several gigabytes
without overlapping. I did manage to hit some failing cases, but they
were never sheared writes, but rather cases where there was an
incomplete write at the end-of-file.
I used your programs with necessary adjustments (as fork() is not
available), and did similar tests with concurrent processes. With packet
sizes 1025, 4093, 7531 (just to include some odd number), and 8193 I did not
observe any overlapping or short writes.
I'm now very confident that we are on the safe side for our purposes.
Great, thanks for testing!
Re-reading what I wrote about end-of-file above and thinking about the
conversation with Ævar elsewhere in the thread, I suspect it _is_ easy
to get overlapping writes if the processes are receiving signals (since
clearly the TERM signal caused a partial write).
My experiment doesn't simulate that at all. I suppose the parent process
could send SIGUSR1 to the child in each loop, and the child would catch
it but keep going.
Hmm, that was easy enough to do (programs below for reference), but
surprisingly it didn't fail for me (except for the normal end-of-file
truncation). It's like the OS is willing to truncate the write of a
dying program but not one for a signal that is getting handled. Which is
great for us, since it's exactly what we want, but makes me even more
suspicious that a non-Linux kernel might behave completely differently.
I still think we're fine in practice, as I'd expect any kernel to be
atomic under the page size. So this was mostly just for my own
edification.
-Peff
-- >8 --
/* check.c, with separate short-read reporting */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
int block = 0;
char *buf;
buf = malloc(size);
while (1) {
int i;
/* assume atomic reads */
int r = read(0, buf, size);
if (!r)
break;
if (r < size) {
fprintf(stderr, "short read\n");
return 1;
}
for (i = 1; i < size; i++) {
if (buf[i] != buf[0]) {
fprintf(stderr, "overlap in block %d\n", block);
return 1;
}
}
block++;
}
}
-- >8 --
-- >8 --
/* write.c with signals; you can also confirm via strace
that each write is atomic */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>
#include <signal.h>
void handle_signal(int sig)
{
/* do nothing */
}
static void doit(int size, const char *fn, char c, pid_t pid)
{
int fd;
char *buf;
fd = open(fn, O_WRONLY|O_APPEND|O_CREAT, 0666);
if (fd < 0) {
perror("open");
return;
}
buf = malloc(size);
memset(buf, c, size);
while (1) {
if (pid)
kill(pid, SIGUSR1);
write(fd, buf, size);
}
}
int main(int argc, const char **argv)
{
int size = atoi(argv[1]);
pid_t pid;
signal(SIGUSR1, handle_signal);
pid = fork();
if (pid)
doit(size, argv[2], '1', pid);
else
doit(size, argv[2], '2', pid);
return 0;
}
-- >8 --