Support: Rewrite Windows implementation of sys::fs::rename to be more POSIXy.
ClosedPublic

Authored by pcc on Oct 4 2017, 5:05 PM.

Details

Summary

The current implementation of rename uses ReplaceFile if the
destination file already exists. According to the documentation for
ReplaceFile, the source file is opened without a sharing mode. This
means that there is a short interval of time between when ReplaceFile
renames the file and when it closes the file during which the
destination file cannot be opened.

This behaviour is not POSIX compliant because rename is supposed
to be atomic. It was also causing intermittent link failures when
linking with a ThinLTO cache; the ThinLTO cache implementation expects
all cache files to be openable.

This patch addresses that problem by re-implementing rename
using CreateFile and SetFileInformationByHandle. It is roughly a
reimplementation of ReplaceFile with a better sharing policy as well
as support for renaming in the case where the destination file does
not exist.

This implementation is still not fully POSIX. Specifically in the case
where the destination file is open at the point when rename is called,
there will be a short interval of time during which the destination
file will not exist. It isn't clear whether it is possible to avoid
this using the Windows API.

Diff Detail

Repository
rL LLVM
pcc created this revision.Oct 4 2017, 5:05 PM
smeenai added a subscriber: smeenai.Oct 4 2017, 5:07 PM
ruiu added a subscriber: ruiu.Oct 4 2017, 5:21 PM

Could you try https://reviews.llvm.org/D38571 to see if it will fix your problem?

ruiu added a comment.Oct 4 2017, 5:22 PM

Oh, sorry, I replied to a wrong thread. Please ignore my previous message.

So if I understand the problem correctly, you don't have any issue with ReplaceFile's behavior on the destination, only the source. So, for example, you call ReplaceFile, it returns, and then some other process tries to open the source file and fails.

If this is correct, then what about this idea?

  1. Move the source file to a temporary file name.
  2. Call ReplaceFile specifying the new temporary file as the source.

This is still not atomic, but neither is the code here, so it's a question of which tradeoffs do we prefer. With a truly atomic rename, there are two outcomes:

  1. Dest exists before rename. After the rename, there was never a window of time where Dest existed but not Source. Either They both exist, or exactly 1 exists at it is Dest with Source's original content.
  2. Dest doesn't exist before rename. After the rename, there was never a window of time where 0 or 2 files existed. There was always exactly 1 file.

With the approach mentioned above, you can still satisfy 2, but not 1. There will be a short window of time where Dest is moved to a temporary location but not yet overwritten onto Source.

llvm/lib/Support/Windows/Path.inc
368–369 ↗(On Diff #117766)

I think this is allocating 1 character too many. ToWide.size() already includes the null terminator, but so does sizeof(FILE_RENAME_INFO) since it has a 1 character array.

374 ↗(On Diff #117766)

If I understand correctly, ToWide.size() contains the number of characters including null terminator, but this value should be number of characters *not* including null terminator.

pcc added a comment.Oct 4 2017, 6:38 PM

So if I understand the problem correctly, you don't have any issue with ReplaceFile's behavior on the destination, only the source. So, for example, you call ReplaceFile, it returns, and then some other process tries to open the source file and fails.

Not quite. From the ThinLTO perspective I don't care about the behaviour on the source file before it is renamed, because all source files are temporary files whose names are unknown to other processes. The problem is with the behaviour on the source file after it has been renamed to the destination file. ThinLTO does this for each new cache file that it creates:

rename("thinlto-cache/temporary file name", "thinlto-cache/llvmcache-ABC123") // ABC123 is a unique hash that is computed from the linker's input files and command line options. There is a many-to-one mapping from hashes to object files (modulo collisions, but that's unlikely enough not to matter).

In parallel, another process will be doing this in order to try and open an existing cache file:

open("thinlto-cache/llvmcache-ABC123") // This is expected to either succeed (cache hit) or return "no such file or directory" (cache miss).

Where this breaks is when rename is implemented in terms of ReplaceFile. In pseudocode, here's what I think is going on in the important part of ReplaceFile:

void ReplaceFile(char *Src, char *Dst) {
  HANDLE h = CreateFile(Src, no sharing); // (1) Src cannot be opened
  SetFileInformationByHandle(h, Rename, Dst); // (2) Now Dst cannot be opened
  CloseFile(h); // (3) Now Dst can be opened
}

So if the open happens between 2 and 3, it will get a permission denied error, which is not what the caller of open is expecting.

I'm with Zach in that I'm also concerned about the extra complexity. Then again ReplaceFile does all sorts of extra work we don't need (like preserving file creation times) that could potentially create confusion and even bugs.

Would it be reasonble to have the callers cope with the possibility of an access violation and either retry or treat it as a failure?

rnk added a subscriber: dyung.Oct 5 2017, 10:46 AM
rnk added inline comments.
llvm/lib/Support/Windows/Path.inc
381 ↗(On Diff #117766)

Are you sure you want to remove the Sleep? Consider the case where LLD is rapidly re-linking the same executable, and there is some silly virus scanner opening the file with a bad sharing mode. @dyung added this.

400 ↗(On Diff #117766)

Let's make this fail after some time. Say 200 attempts? I doubt we need 2000... We can probably return something like errc::resource_unavailable_try_again` (EAGAIN)?

429–430 ↗(On Diff #117766)

At first, I wanted to say we should use the same random file name generation used for createUniqueEntity, but these files should not accumulate if FILE_FLAG_DELETE_ON_CLOSE works as intended.

We should limit the number of retries, though. (also 10?)

pcc added a comment.Oct 5 2017, 10:50 AM

Would it be reasonble to have the callers cope with the possibility of an access violation and either retry or treat it as a failure?

Retry means that there will still be a race, it will just happen less often.

I'm not sure what you mean by "treat it as a failure". If you mean "treat it as if the file does not exist i.e. a cache miss" -- that might work, but I think it could disguise real access problems with the cache directory, and because a cache miss would lead to a ReplaceFile I think there could still be races between multiple callers of ReplaceFile due to the interval of no sharing.

pcc added inline comments.Oct 5 2017, 4:15 PM
llvm/lib/Support/Windows/Path.inc
368–369 ↗(On Diff #117766)

Yeah, looks like we can subtract 2 here, I'll do that.

374 ↗(On Diff #117766)

http://llvm-cs.pcc.me.uk/lib/Support/Windows/Path.inc#1130

Looks like the string is null terminated, but will not contain a null terminator.

381 ↗(On Diff #117766)

Actually it looks like this was added by Takumi back in r156380. Seems like the equivalent thing in the new code would be to do a sleep/retry when calling CreateFile on the source file. I'll do that.

400 ↗(On Diff #117766)

My instinct was to not limit the number of retries because a limit seems unsound, but limiting to a large number is probably fine if the probability of a false negative becomes infinitesimal. In general I think we shouldn't expect more than the number of logical CPUs to be trying to replace the file, and I wouldn't expect them all to be trying to replace the same file, so 200 seems like an ok number.

429–430 ↗(On Diff #117766)

I think I'd also make this based on a reasonable upper limit for the number of logical CPUs (i.e. 200).

rnk added a comment.Oct 5 2017, 5:15 PM

You might consider extending unittests/Support/ReplaceFileTest.cpp with any non-racy scenarios that needed thought.

pcc updated this revision to Diff 117954.Oct 5 2017, 8:52 PM
  • Address review comments
rnk accepted this revision.Oct 6 2017, 9:59 AM

lgtm, thanks!

This revision is now accepted and ready to land.Oct 6 2017, 9:59 AM
This revision was automatically updated to reflect the committed changes.
grimar added a subscriber: grimar.Oct 9 2017, 10:13 AM
grimar added inline comments.
llvm/trunk/lib/Support/Windows/Path.inc
375

This asserts under windows/debug.
RenameInfo.FileName here is WCHAR FileName[1]; and std::copy checks it's size
for overflow and fails:

	_Myiter& operator+=(difference_type _Off)
		{	// increment by integer
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Size < _Idx + _Off)
			{	// report error
			_DEBUG_ERROR("array iterator + offset out of range");
			_SCL_SECURE_OUT_OF_RANGE;
			}
template<class _InIt,
	class _OutTy,
	size_t _OutSize> inline
	_OutTy *copy(_InIt _First, _InIt _Last,
		_OutTy (&_Dest)[_OutSize])
	{	// copy [_First, _Last) to [_Dest, ...)

I would suggest to use memcpy instead.