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

[pcc]

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.

[ruiu]

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

[ruiu]

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

[zturner]

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]

In D38570#889021, @zturner wrote:

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.

[amccarth]

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]

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]

In D38570#889483, @amccarth wrote:

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]

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]

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

[pcc]

• Address review comments

[rnk]

lgtm, thanks!

[grimar]

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.

llvm/trunk/include/llvm/Support/FileSystem.h

 
 /// @brief Recursively delete a directory.
 ///
 /// @param path Input path.
 /// @returns errc::success if path has been removed or didn't exist, otherwise a
 ///          platform-specific error code.
 std::error_code remove_directories(const Twine &path, bool IgnoreErrors = true);
 
-/// @brief Rename \a from to \a to. Files are renamed as if by POSIX rename().
+/// @brief Rename \a from to \a to.
+///
+/// Files are renamed as if by POSIX rename(), except that on Windows there may
+/// be a short interval of time during which the destination file does not
+/// exist.
 ///
 /// @param from The path to rename from.
 /// @param to The path to rename to. This is created.
 std::error_code rename(const Twine &from, const Twine &to);
 
 /// @brief Copy the contents of \a From to \a To.
 ///
 /// @param From The path to copy from.

llvm/trunk/lib/Support/Windows/Path.inc

if (Len == 0)
       return mapWindowsError(::GetLastError());
   } while (Len > FinalPath.capacity());
 
   FinalPath.set_size(Len);
 
   return is_local_internal(FinalPath, Result);
 }
 
-std::error_code rename(const Twine &from, const Twine &to) {
-  // Convert to utf-16.
-  SmallVector<wchar_t, 128> wide_from;
-  SmallVector<wchar_t, 128> wide_to;
-  if (std::error_code ec = widenPath(from, wide_from))
-    return ec;
-  if (std::error_code ec = widenPath(to, wide_to))
-    return ec;
+static std::error_code rename_internal(HANDLE FromHandle, const Twine &To,
+                                       bool ReplaceIfExists) {
+  SmallVector<wchar_t, 0> ToWide;
+  if (auto EC = widenPath(To, ToWide))
+    return EC;
 
-  std::error_code ec = std::error_code();
+  std::vector<char> RenameInfoBuf(sizeof(FILE_RENAME_INFO) - sizeof(wchar_t) +
+                                  (ToWide.size() * sizeof(wchar_t)));
+  FILE_RENAME_INFO &RenameInfo =
+      *reinterpret_cast<FILE_RENAME_INFO *>(RenameInfoBuf.data());
+  RenameInfo.ReplaceIfExists = ReplaceIfExists;
+  RenameInfo.RootDirectory = 0;
+  RenameInfo.FileNameLength = ToWide.size();
+  std::copy(ToWide.begin(), ToWide.end(), RenameInfo.FileName);
 
-  // Retry while we see recoverable errors.
-  // System scanners (eg. indexer) might open the source file when it is written
-  // and closed.
+  if (!SetFileInformationByHandle(FromHandle, FileRenameInfo, &RenameInfo,
+                                  RenameInfoBuf.size()))
+    return mapWindowsError(GetLastError());
 
-  bool TryReplace = true;
+  return std::error_code();
+}
 
-  for (int i = 0; i < 2000; i++) {
-    if (i > 0)
-      ::Sleep(1);
+std::error_code rename(const Twine &From, const Twine &To) {
+  // Convert to utf-16.
+  SmallVector<wchar_t, 128> WideFrom;
+  SmallVector<wchar_t, 128> WideTo;
+  if (std::error_code EC = widenPath(From, WideFrom))
+    return EC;
+  if (std::error_code EC = widenPath(To, WideTo))
+    return EC;
 
-    if (TryReplace) {
-      // Try ReplaceFile first, as it is able to associate a new data stream
-      // with the destination even if the destination file is currently open.
-      if (::ReplaceFileW(wide_to.data(), wide_from.data(), NULL, 0, NULL, NULL))
-        return std::error_code();
+  ScopedFileHandle FromHandle;
+  // Retry this a few times to defeat badly behaved file system scanners.
+  for (unsigned Retry = 0; Retry != 200; ++Retry) {
+    if (Retry != 0)
+      ::Sleep(10);
+    FromHandle =
+        ::CreateFileW(WideFrom.begin(), GENERIC_READ | DELETE,
+                      FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
+                      NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
+    if (FromHandle)
+      break;
+  }
+  if (!FromHandle)
+    return mapWindowsError(GetLastError());
 
-      DWORD ReplaceError = ::GetLastError();
-      ec = mapWindowsError(ReplaceError);
+  // We normally expect this loop to succeed after a few iterations. If it
+  // requires more than 200 tries, it's more likely that the failures are due to
+  // a true error, so stop trying.
+  for (unsigned Retry = 0; Retry != 200; ++Retry) {
+    auto EC = rename_internal(FromHandle, To, true);
+    if (!EC || EC != errc::permission_denied)
+      return EC;
 
-      // If ReplaceFileW returned ERROR_UNABLE_TO_MOVE_REPLACEMENT or
-      // ERROR_UNABLE_TO_MOVE_REPLACEMENT_2, retry but only use MoveFileExW().
-      if (ReplaceError == ERROR_UNABLE_TO_MOVE_REPLACEMENT ||
-          ReplaceError == ERROR_UNABLE_TO_MOVE_REPLACEMENT_2) {
-        TryReplace = false;
+    // The destination file probably exists and is currently open in another
+    // process, either because the file was opened without FILE_SHARE_DELETE or
+    // it is mapped into memory (e.g. using MemoryBuffer). Rename it in order to
+    // move it out of the way of the source file. Use FILE_FLAG_DELETE_ON_CLOSE
+    // to arrange for the destination file to be deleted when the other process
+    // closes it.
+    ScopedFileHandle ToHandle(
+        ::CreateFileW(WideTo.begin(), GENERIC_READ | DELETE,
+                      FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
+                      NULL, OPEN_EXISTING,
+                      FILE_ATTRIBUTE_NORMAL | FILE_FLAG_DELETE_ON_CLOSE, NULL));
+    if (!ToHandle) {
+      auto EC = mapWindowsError(GetLastError());
+      // Another process might have raced with us and moved the existing file
+      // out of the way before we had a chance to open it. If that happens, try
+      // to rename the source file again.
+      if (EC == errc::no_such_file_or_directory)
         continue;
+      return EC;
+    }
+
+    BY_HANDLE_FILE_INFORMATION FI;
+    if (!GetFileInformationByHandle(ToHandle, &FI))
+      return mapWindowsError(GetLastError());
+
+    // Try to find a unique new name for the destination file.
+    for (unsigned UniqueId = 0; UniqueId != 200; ++UniqueId) {
+      std::string TmpFilename = (To + ".tmp" + utostr(UniqueId)).str();
+      if (auto EC = rename_internal(ToHandle, TmpFilename, false)) {
+        if (EC == errc::file_exists || EC == errc::permission_denied) {
+          // Again, another process might have raced with us and moved the file
+          // before we could move it. Check whether this is the case, as it
+          // might have caused the permission denied error. If that was the
+          // case, we don't need to move it ourselves.
+          ScopedFileHandle ToHandle2(::CreateFileW(
+              WideTo.begin(), 0,
+              FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE, NULL,
+              OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL));
+          if (!ToHandle2) {
+            auto EC = mapWindowsError(GetLastError());
+            if (EC == errc::no_such_file_or_directory)
+              break;
+            return EC;
           }
-      // If ReplaceFileW returned ERROR_UNABLE_TO_REMOVE_REPLACED, retry
-      // using ReplaceFileW().
-      if (ReplaceError == ERROR_UNABLE_TO_REMOVE_REPLACED)
+          BY_HANDLE_FILE_INFORMATION FI2;
+          if (!GetFileInformationByHandle(ToHandle2, &FI2))
+            return mapWindowsError(GetLastError());
+          if (FI.nFileIndexHigh != FI2.nFileIndexHigh ||
+              FI.nFileIndexLow != FI2.nFileIndexLow ||
+              FI.dwVolumeSerialNumber != FI2.dwVolumeSerialNumber)
+            break;
           continue;
-      // We get ERROR_FILE_NOT_FOUND if the destination file is missing.
-      // MoveFileEx can handle this case.
-      if (ReplaceError != ERROR_ACCESS_DENIED &&
-          ReplaceError != ERROR_FILE_NOT_FOUND &&
-          ReplaceError != ERROR_SHARING_VIOLATION)
-        break;
+        }
+        return EC;
+      }
     }
 
-    if (::MoveFileExW(wide_from.begin(), wide_to.begin(),
-                      MOVEFILE_COPY_ALLOWED | MOVEFILE_REPLACE_EXISTING))
-      return std::error_code();
-
-    DWORD MoveError = ::GetLastError();
-    ec = mapWindowsError(MoveError);
-    if (MoveError != ERROR_ACCESS_DENIED) break;
+    // Okay, the old destination file has probably been moved out of the way at
+    // this point, so try to rename the source file again. Still, another
+    // process might have raced with us to create and open the destination
+    // file, so we need to keep doing this until we succeed.
   }
 
-  return ec;
+  // The most likely root cause.
+  return errc::permission_denied;
 }
 
 std::error_code resize_file(int FD, uint64_t Size) {
 #ifdef HAVE__CHSIZE_S
   errno_t error = ::_chsize_s(FD, Size);
 #else
   errno_t error = ::_chsize(FD, Size);
 #endif

llvm/trunk/unittests/Support/ReplaceFileTest.cpp

class ScopedFD {
   ScopedFD(const ScopedFD &) = delete;
   ScopedFD &operator=(const ScopedFD &) = delete;
 
  public:
   explicit ScopedFD(int Descriptor) : FD(Descriptor) {}
   ~ScopedFD() { Process::SafelyCloseFileDescriptor(FD); }
 };
 
+bool FDHasContent(int FD, StringRef Content) {
+  auto Buffer = MemoryBuffer::getOpenFile(FD, "", -1);
+  assert(Buffer);
+  return Buffer.get()->getBuffer() == Content;
+}
+
+bool FileHasContent(StringRef File, StringRef Content) {
+  int FD = 0;
+  auto EC = fs::openFileForRead(File, FD);
+  (void)EC;
+  assert(!EC);
+  ScopedFD EventuallyCloseIt(FD);
+  return FDHasContent(FD, Content);
+}
+
 TEST(rename, FileOpenedForReadingCanBeReplaced) {
   // Create unique temporary directory for this test.
   SmallString<128> TestDirectory;
   ASSERT_NO_ERROR(fs::createUniqueDirectory(
       "FileOpenedForReadingCanBeReplaced-test", TestDirectory));
 
   // Add a couple of files to the test directory.
   SmallString<128> SourceFileName(TestDirectory);
ASSERT_NO_ERROR(CreateFileWithContent(TargetFileName, "!!target!!"));
     ASSERT_NO_ERROR(fs::openFileForRead(TargetFileName, ReadFD));
     ScopedFD EventuallyCloseIt(ReadFD);
 
     // Confirm we can replace the file while it is open.
     EXPECT_TRUE(!fs::rename(SourceFileName, TargetFileName));
 
     // We should still be able to read the old data through the existing
     // descriptor.
-    auto Buffer = MemoryBuffer::getOpenFile(ReadFD, TargetFileName, -1);
-    ASSERT_TRUE(static_cast<bool>(Buffer));
-    EXPECT_EQ(Buffer.get()->getBuffer(), "!!target!!");
+    EXPECT_TRUE(FDHasContent(ReadFD, "!!target!!"));
 
     // The source file should no longer exist
     EXPECT_FALSE(fs::exists(SourceFileName));
   }
 
-  {
-    // If we obtain a new descriptor for the target file, we should find that it
-    // contains the content that was in the source file.
-    int ReadFD = 0;
-    ASSERT_NO_ERROR(fs::openFileForRead(TargetFileName, ReadFD));
-    ScopedFD EventuallyCloseIt(ReadFD);
-    auto Buffer = MemoryBuffer::getOpenFile(ReadFD, TargetFileName, -1);
-    ASSERT_TRUE(static_cast<bool>(Buffer));
-
-    EXPECT_EQ(Buffer.get()->getBuffer(), "!!source!!");
-  }
+  EXPECT_TRUE(FileHasContent(TargetFileName, "!!source!!"));
 
   // Rename the target file back to the source file name to confirm that rename
   // still works if the destination does not already exist.
   EXPECT_TRUE(!fs::rename(TargetFileName, SourceFileName));
   EXPECT_FALSE(fs::exists(TargetFileName));
   ASSERT_TRUE(fs::exists(SourceFileName));
 
   // Clean up.
   ASSERT_NO_ERROR(fs::remove(SourceFileName));
   ASSERT_NO_ERROR(fs::remove(TestDirectory.str()));
 }
 
+TEST(rename, ExistingTemp) {
+  // Test that existing .tmpN files don't get deleted by the Windows
+  // sys::fs::rename implementation.
+  SmallString<128> TestDirectory;
+  ASSERT_NO_ERROR(
+      fs::createUniqueDirectory("ExistingTemp-test", TestDirectory));
+
+  SmallString<128> SourceFileName(TestDirectory);
+  path::append(SourceFileName, "source");
+
+  SmallString<128> TargetFileName(TestDirectory);
+  path::append(TargetFileName, "target");
+
+  SmallString<128> TargetTmp0FileName(TestDirectory);
+  path::append(TargetTmp0FileName, "target.tmp0");
+
+  SmallString<128> TargetTmp1FileName(TestDirectory);
+  path::append(TargetTmp1FileName, "target.tmp1");
+
+  ASSERT_NO_ERROR(CreateFileWithContent(SourceFileName, "!!source!!"));
+  ASSERT_NO_ERROR(CreateFileWithContent(TargetFileName, "!!target!!"));
+  ASSERT_NO_ERROR(CreateFileWithContent(TargetTmp0FileName, "!!target.tmp0!!"));
+
+  {
+    // Use mapped_file_region to make sure that the destination file is mmap'ed.
+    // This will cause SetInformationByHandle to fail when renaming to the
+    // destination, and we will follow the code path that tries to give target
+    // a temporary name.
+    int TargetFD;
+    std::error_code EC;
+    ASSERT_NO_ERROR(fs::openFileForRead(TargetFileName, TargetFD));
+    ScopedFD X(TargetFD);
+    sys::fs::mapped_file_region MFR(
+        TargetFD, sys::fs::mapped_file_region::readonly, 10, 0, EC);
+    ASSERT_FALSE(EC);
+
+    ASSERT_NO_ERROR(fs::rename(SourceFileName, TargetFileName));
+
+#ifdef _WIN32
+    // Make sure that target was temporarily renamed to target.tmp1 on Windows.
+    // This is signified by a permission denied error as opposed to no such file
+    // or directory when trying to open it.
+    int Tmp1FD;
+    EXPECT_EQ(errc::permission_denied,
+              fs::openFileForRead(TargetTmp1FileName, Tmp1FD));
+#endif
+  }
+
+  EXPECT_TRUE(FileHasContent(TargetTmp0FileName, "!!target.tmp0!!"));
+
+  ASSERT_NO_ERROR(fs::remove(TargetFileName));
+  ASSERT_NO_ERROR(fs::remove(TargetTmp0FileName));
+  ASSERT_NO_ERROR(fs::remove(TestDirectory.str()));
+}
+
 }  // anonymous namespace