Merge pull request #779 from nico/statcache

Use FindFirstFileEx() for stat()ing files on Windows.

6 files changed, 158 insertions, 21 deletions

diff --git a/src/debug_flags.cc b/src/debug_flags.cc
index 75f1ea5..ccd4396 100644
--- a/src/debug_flags.cc
+++ b/src/debug_flags.cc
@@ -15,3 +15,5 @@
 bool g_explaining = false;
 
 bool g_keep_rsp = false;
+
+bool g_experimental_win_statcache = true;
diff --git a/src/debug_flags.h b/src/debug_flags.h
index ba3ebf3..4ffef75 100644
--- a/src/debug_flags.h
+++ b/src/debug_flags.h
@@ -26,4 +26,6 @@ extern bool g_explaining;
 
 extern bool g_keep_rsp;
 
+extern bool g_experimental_win_statcache;
+
 #endif // NINJA_EXPLAIN_H_
diff --git a/src/disk_interface.cc b/src/disk_interface.cc
index 4dfae1a..50a2d97 100644
--- a/src/disk_interface.cc
+++ b/src/disk_interface.cc
@@ -55,6 +55,63 @@ int MakeDir(const string& path) {
 #endif
 }
 
+#ifdef _WIN32
+TimeStamp TimeStampFromFileTime(const FILETIME& filetime) {
+  // FILETIME is in 100-nanosecond increments since the Windows epoch.
+  // We don't much care about epoch correctness but we do want the
+  // resulting value to fit in an integer.
+  uint64_t mtime = ((uint64_t)filetime.dwHighDateTime << 32) |
+    ((uint64_t)filetime.dwLowDateTime);
+  mtime /= 1000000000LL / 100; // 100ns -> s.
+  mtime -= 12622770400LL;  // 1600 epoch -> 2000 epoch (subtract 400 years).
+  return (TimeStamp)mtime;
+}
+
+TimeStamp StatSingleFile(const string& path, bool quiet) {
+  WIN32_FILE_ATTRIBUTE_DATA attrs;
+  if (!GetFileAttributesEx(path.c_str(), GetFileExInfoStandard, &attrs)) {
+    DWORD err = GetLastError();
+    if (err == ERROR_FILE_NOT_FOUND || err == ERROR_PATH_NOT_FOUND)
+      return 0;
+    if (!quiet) {
+      Error("GetFileAttributesEx(%s): %s", path.c_str(),
+            GetLastErrorString().c_str());
+    }
+    return -1;
+  }
+  return TimeStampFromFileTime(attrs.ftLastWriteTime);
+}
+
+bool StatAllFilesInDir(const string& dir, map<string, TimeStamp>* stamps,
+                       bool quiet) {
+  // FindExInfoBasic is 30% faster than FindExInfoStandard.
+  WIN32_FIND_DATAA ffd;
+  HANDLE find_handle = FindFirstFileExA((dir + "\\*").c_str(), FindExInfoBasic,
+                                        &ffd, FindExSearchNameMatch, NULL, 0);
+
+  if (find_handle == INVALID_HANDLE_VALUE) {
+    DWORD err = GetLastError();
+    if (err == ERROR_FILE_NOT_FOUND || err == ERROR_PATH_NOT_FOUND)
+      return true;
+    if (!quiet) {
+      Error("FindFirstFileExA(%s): %s", dir.c_str(),
+            GetLastErrorString().c_str());
+    }
+    return false;
+  }
+  do {
+    if (ffd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
+      continue;
+    string lowername = ffd.cFileName;
+    transform(lowername.begin(), lowername.end(), lowername.begin(), ::tolower);
+    stamps->insert(make_pair(lowername,
+                             TimeStampFromFileTime(ffd.ftLastWriteTime)));
+  } while (FindNextFileA(find_handle, &ffd));
+  FindClose(find_handle);
+  return true;
+}
+#endif  // _WIN32
+
 }  // namespace
 
 // DiskInterface ---------------------------------------------------------------
@@ -89,26 +146,26 @@ TimeStamp RealDiskInterface::Stat(const string& path) {
     }
     return -1;
   }
-  WIN32_FILE_ATTRIBUTE_DATA attrs;
-  if (!GetFileAttributesEx(path.c_str(), GetFileExInfoStandard, &attrs)) {
-    DWORD err = GetLastError();
-    if (err == ERROR_FILE_NOT_FOUND || err == ERROR_PATH_NOT_FOUND)
-      return 0;
-    if (!quiet_) {
-      Error("GetFileAttributesEx(%s): %s", path.c_str(),
-            GetLastErrorString().c_str());
+  if (!use_cache_)
+    return StatSingleFile(path, quiet_);
+
+  string dir = DirName(path);
+  string base(path.substr(dir.size() ? dir.size() + 1 : 0));
+
+  transform(dir.begin(), dir.end(), dir.begin(), ::tolower);
+  transform(base.begin(), base.end(), base.begin(), ::tolower);
+
+  Cache::iterator ci = cache_.find(dir);
+  if (ci == cache_.end()) {
+    DirCache* dc = new DirCache;
+    if (!StatAllFilesInDir(dir.empty() ? "." : dir, dc, quiet_)) {
+      delete dc;
+      return -1;
     }
-    return -1;
+    ci = cache_.insert(make_pair(dir, dc)).first;
   }
-  const FILETIME& filetime = attrs.ftLastWriteTime;
-  // FILETIME is in 100-nanosecond increments since the Windows epoch.
-  // We don't much care about epoch correctness but we do want the
-  // resulting value to fit in an integer.
-  uint64_t mtime = ((uint64_t)filetime.dwHighDateTime << 32) |
-    ((uint64_t)filetime.dwLowDateTime);
-  mtime /= 1000000000LL / 100; // 100ns -> s.
-  mtime -= 12622770400LL;  // 1600 epoch -> 2000 epoch (subtract 400 years).
-  return (TimeStamp)mtime;
+  DirCache::iterator di = ci->second->find(base);
+  return di != ci->second->end() ? di->second : 0;
 #else
   struct stat st;
   if (stat(path.c_str(), &st) < 0) {
@@ -181,3 +238,19 @@ int RealDiskInterface::RemoveFile(const string& path) {
     return 0;
   }
 }
+
+void RealDiskInterface::AllowStatCache(bool allow) {
+#ifdef _WIN32
+  use_cache_ = allow;
+  if (!use_cache_)
+    ClearCache();
+#endif
+}
+
+void RealDiskInterface::ClearCache() {
+#ifdef _WIN32
+  for (Cache::iterator it = cache_.begin(), end = cache_.end(); it != end; ++it)
+    delete it->second;
+  cache_.clear();
+#endif
+}
diff --git a/src/disk_interface.h b/src/disk_interface.h
index ff1e21c..0f6dfd3 100644
--- a/src/disk_interface.h
+++ b/src/disk_interface.h
@@ -15,6 +15,7 @@
 #ifndef NINJA_DISK_INTERFACE_H_
 #define NINJA_DISK_INTERFACE_H_
 
+#include <map>
 #include <string>
 using namespace std;
 
@@ -55,8 +56,12 @@ struct DiskInterface {
 
 /// Implementation of DiskInterface that actually hits the disk.
 struct RealDiskInterface : public DiskInterface {
-  RealDiskInterface() : quiet_(false) {}
-  virtual ~RealDiskInterface() {}
+  RealDiskInterface() : quiet_(false)
+#ifdef _WIN32
+                      , use_cache_(false)
+#endif
+                      {}
+  virtual ~RealDiskInterface() { ClearCache(); }
   virtual TimeStamp Stat(const string& path);
   virtual bool MakeDir(const string& path);
   virtual bool WriteFile(const string& path, const string& contents);
@@ -65,6 +70,22 @@ struct RealDiskInterface : public DiskInterface {
 
   /// Whether to print on errors.  Used to make a test quieter.
   bool quiet_;
+
+  /// Whether stat information can be cached.  Only has an effect on Windows.
+  void AllowStatCache(bool allow);
+
+ private:
+#ifdef _WIN32
+  /// Whether stat information can be cached.
+  bool use_cache_;
+
+  typedef map<string, TimeStamp> DirCache;
+  // TODO: Neither a map nor a hashmap seems ideal here.  If the statcache
+  // works out, come up with a better data structure.
+  typedef map<string, DirCache*> Cache;
+  Cache cache_;
+#endif
+  void ClearCache();
 };
 
 #endif  // NINJA_DISK_INTERFACE_H_
diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc
index 51a1d14..69fd1ab 100644
--- a/src/disk_interface_test.cc
+++ b/src/disk_interface_test.cc
@@ -76,6 +76,33 @@ TEST_F(DiskInterfaceTest, StatExistingFile) {
   EXPECT_GT(disk_.Stat("file"), 1);
 }
 
+#ifdef _WIN32
+TEST_F(DiskInterfaceTest, StatCache) {
+  disk_.AllowStatCache(true);
+
+  ASSERT_TRUE(Touch("file1"));
+  ASSERT_TRUE(Touch("fiLE2"));
+  ASSERT_TRUE(disk_.MakeDir("subdir"));
+  ASSERT_TRUE(Touch("subdir\\subfile1"));
+  ASSERT_TRUE(Touch("subdir\\SUBFILE2"));
+  ASSERT_TRUE(Touch("subdir\\SUBFILE3"));
+
+  EXPECT_GT(disk_.Stat("FIle1"), 1);
+  EXPECT_GT(disk_.Stat("file1"), 1);
+
+  EXPECT_GT(disk_.Stat("subdir/subfile2"), 1);
+  EXPECT_GT(disk_.Stat("sUbdir\\suBFile1"), 1);
+
+  // Test error cases.
+  disk_.quiet_ = true;
+  string bad_path("cc:\\foo");
+  EXPECT_EQ(-1, disk_.Stat(bad_path));
+  EXPECT_EQ(-1, disk_.Stat(bad_path));
+  EXPECT_EQ(0, disk_.Stat("nosuchfile"));
+  EXPECT_EQ(0, disk_.Stat("nosuchdir/nosuchfile"));
+}
+#endif
+
 TEST_F(DiskInterfaceTest, ReadFile) {
   string err;
   EXPECT_EQ("", disk_.ReadFile("foobar", &err));
diff --git a/src/ninja.cc b/src/ninja.cc
index 4c8dab7..e555df4 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -760,6 +760,9 @@ bool DebugEnable(const string& name) {
 "  stats    print operation counts/timing info\n"
 "  explain  explain what caused a command to execute\n"
 "  keeprsp  don't delete @response files on success\n"
+#ifdef _WIN32
+"  nowinstatcache  don't batch stat() calls per directory and cache them\n"
+#endif
 "multiple modes can be enabled via -d FOO -d BAR\n");
     return false;
   } else if (name == "stats") {
@@ -771,9 +774,13 @@ bool DebugEnable(const string& name) {
   } else if (name == "keeprsp") {
     g_keep_rsp = true;
     return true;
+  } else if (name == "nowinstatcache") {
+    g_experimental_win_statcache = false;
+    return true;
   } else {
     const char* suggestion =
-        SpellcheckString(name.c_str(), "stats", "explain", "keeprsp", NULL);
+        SpellcheckString(name.c_str(), "stats", "explain", "keeprsp",
+        "nowinstatcache", NULL);
     if (suggestion) {
       Error("unknown debug setting '%s', did you mean '%s'?",
             name.c_str(), suggestion);
@@ -882,6 +889,8 @@ int NinjaMain::RunBuild(int argc, char** argv) {
     return 1;
   }
 
+  disk_interface_.AllowStatCache(g_experimental_win_statcache);
+
   Builder builder(&state_, config_, &build_log_, &deps_log_, &disk_interface_);
   for (size_t i = 0; i < targets.size(); ++i) {
     if (!builder.AddTarget(targets[i], &err)) {
@@ -895,6 +904,9 @@ int NinjaMain::RunBuild(int argc, char** argv) {
     }
   }
 
+  // Make sure restat rules do not see stale timestamps.
+  disk_interface_.AllowStatCache(false);
+
   if (builder.AlreadyUpToDate()) {
     printf("ninja: no work to do.\n");
     return 0;