Avoid fragmenting the heap too much while reconstructing the index.

net/disk_cache/simple/simple_index_file.cc

Index: net/disk_cache/simple/simple_index_file.cc
diff --git a/net/disk_cache/simple/simple_index_file.cc b/net/disk_cache/simple/simple_index_file.cc
index 7bcea7cdfa86255360a7416d4eff5731ca24ae7c..fda042fc163d8ada10c218cb55d4e3fcd0213b19 100644
--- a/net/disk_cache/simple/simple_index_file.cc
+++ b/net/disk_cache/simple/simple_index_file.cc
@@ -4,10 +4,11 @@
 
 #include "net/disk_cache/simple/simple_index_file.h"
 
+#include <algorithm>
+#include <cstring>
 #include <vector>
 
 #include "base/file_util.h"
-#include "base/files/file_enumerator.h"
 #include "base/files/memory_mapped_file.h"
 #include "base/hash.h"
 #include "base/logging.h"
@@ -22,9 +23,11 @@
 #include "net/disk_cache/simple/simple_util.h"
 #include "third_party/zlib/zlib.h"
 
-
 namespace {
 
+const int kEntryFilesHashLength = 16;
+const int kEntryFilesSuffixLength = 2;
+
 const uint64 kMaxEntiresInIndex = 100000000;
 
 uint32 CalculatePickleCRC(const Pickle& pickle) {
@@ -345,12 +348,74 @@ void SimpleIndexFile::Deserialize(const char* data, int data_len,
 }
 
 // static
+void SimpleIndexFile::ProcessEntryFile(const std::string& cache_path,
+                                       std::vector<char>* buffer,
+                                       SimpleIndex::EntrySet* entries,
+                                       const char* file_name) {
+  static const size_t kEntryFilesLength =
+      kEntryFilesHashLength + kEntryFilesSuffixLength;
+  const size_t file_name_length = strlen(file_name);
+  if (file_name_length != kEntryFilesLength) {
+    if (strcmp(file_name, "index") && strcmp(file_name, "fake_index"))

[pasko, 2013/08/21 11:37:56]

"the-real-index", reuse constants please

[gavinp, 2013/08/21 11:49:47]

Nit: I know it's well defined as written, but I can read

  if (strcmp(file_name, "index") != 0 && strcmp(file_name, "fake_index") != 0))
    ...

more easily. While we're here, what's with the vulgar strings? And what's
"fake_index"? There's some constants SimpleIndexFile::kIndexFileName and you
probably want to add kFakeIndexFileName too.

[Philippe, 2013/08/21 12:41:38]

Yeah, what a shame, I hadn't seen them (in the same file :)). I moved them to
the anonymous namespace btw.

+      LOG(ERROR) << "unexpected file " << file_name;
+    return;
+  }
+  const size_t kFullPathLength = cache_path.size() + 1 + kEntryFilesLength;
+  if (buffer->size() < kFullPathLength)
+    buffer->resize(kFullPathLength + 1);
+
+  // Note that base::FilePath is not used here to avoid extra heap allocations.
+  std::vector<char>::iterator range_end_it = std::copy(
+      cache_path.begin(), cache_path.end(), buffer->begin());
+  const char* const separator = &base::FilePath::kSeparators[0];
+  range_end_it = std::copy(separator, separator + 1, range_end_it);
+  std::copy(file_name, file_name + file_name_length, range_end_it);
+  const size_t file_name_start_pos = range_end_it - buffer->begin();
+
+  uint64 hash_key = 0;
+  const char* const buffer_data = &buffer->front();
+  const base::StringPiece hash_string(
+      buffer_data + file_name_start_pos, kEntryFilesHashLength);

[gavinp, 2013/08/21 11:49:47]

I don't believe a std::vector<> is guaranteed to be stored sequentially in
C++98.

[Philippe, 2013/08/21 12:41:38]

I got rid of the vector.

+  if (!simple_util::GetEntryHashKeyFromHexString(hash_string, &hash_key)) {
+    LOG(WARNING) << "Invalid entry hash key filename while restoring index from"
+                 << " disk: " << file_name;
+    // TODO(felipeg): Should we delete the invalid file here ?
+    return;
+  }
+
+  base::PlatformFileInfo file_info;
+  if (!GetPlatformFileInfo(buffer_data, &file_info)) {
+    LOG(INFO) << "Could not get file info for path " << buffer_data;
+    return;
+  }
+  base::Time last_used_time;
+#if defined(OS_POSIX)
+  // For POSIX systems, a last access time is available. However, it's not
+  // guaranteed to be more accurate than mtime. It is no worse though.
+  last_used_time = file_info.last_accessed;
+#endif
+  if (last_used_time.is_null())
+    last_used_time = file_info.last_modified;
+
+  int64 file_size = file_info.size;
+  SimpleIndex::EntrySet::iterator it = entries->find(hash_key);
+  if (it == entries->end()) {
+    SimpleIndex::InsertInEntrySet(
+        hash_key,
+        EntryMetadata(last_used_time, file_size),
+        entries);
+  } else {
+    // Summing up the total size of the entry through all the *_[0-2] files
+    it->second.SetEntrySize(it->second.GetEntrySize() + file_size);
+  }
+}
+
+// static
 void SimpleIndexFile::SyncRestoreFromDisk(
     const base::FilePath& cache_directory,
     const base::FilePath& index_file_path,
     SimpleIndexLoadResult* out_result) {
   LOG(INFO) << "Simple Cache Index is being restored from disk.";
-
   base::DeleteFile(index_file_path, /* recursive = */ false);
   out_result->Reset();
   SimpleIndex::EntrySet* entries = &out_result->entries;
@@ -359,53 +424,17 @@ void SimpleIndexFile::SyncRestoreFromDisk(
   COMPILE_ASSERT(kSimpleEntryFileCount == 3,
                  file_pattern_must_match_file_count);
 
-  const int kFileSuffixLength = sizeof("_0") - 1;
-  const base::FilePath::StringType file_pattern = FILE_PATH_LITERAL("*_[0-2]");
-  base::FileEnumerator enumerator(cache_directory,
-                                  false /* recursive */,
-                                  base::FileEnumerator::FILES,
-                                  file_pattern);
-  for (base::FilePath file_path = enumerator.Next(); !file_path.empty();
-       file_path = enumerator.Next()) {
-    const base::FilePath::StringType base_name = file_path.BaseName().value();
-    // Converting to std::string is OK since we never use UTF8 wide chars in our
-    // file names.
-    const std::string hash_key_string(base_name.begin(),
-                                      base_name.end() - kFileSuffixLength);
-    uint64 hash_key = 0;
-    if (!simple_util::GetEntryHashKeyFromHexString(
-            hash_key_string, &hash_key)) {
-      LOG(WARNING) << "Invalid Entry Hash Key filename while restoring "
-                   << "Simple Index from disk: " << base_name;
-      // TODO(felipeg): Should we delete the invalid file here ?
-      continue;
-    }
-
-    base::FileEnumerator::FileInfo info = enumerator.GetInfo();
-    base::Time last_used_time;
-#if defined(OS_POSIX)
-    // For POSIX systems, a last access time is available. However, it's not
-    // guaranteed to be more accurate than mtime. It is no worse though.
-    last_used_time = base::Time::FromTimeT(info.stat().st_atime);
-#endif
-    if (last_used_time.is_null())
-      last_used_time = info.GetLastModifiedTime();
-
-    int64 file_size = info.GetSize();
-    SimpleIndex::EntrySet::iterator it = entries->find(hash_key);
-    if (it == entries->end()) {
-      SimpleIndex::InsertInEntrySet(
-          hash_key,
-          EntryMetadata(last_used_time, file_size),
-          entries);
-    } else {
-      // Summing up the total size of the entry through all the *_[0-2] files
-      it->second.SetEntrySize(it->second.GetEntrySize() + file_size);
-    }
+  const std::string cache_path = cache_directory.value();

[pasko, 2013/08/21 11:37:56]

wstring to string conversion would probably not work on Windows. Generally you
should not call .value() on Windows, moving the .value() call to posix version
should be easy.

To avoid the trouble of testing on Windows (we don't want crashing the browser
for ~100 people who enabled Simple Cache with a flag on Windows, right?), I
would suggest using FilePath. This reallocation in the loop of the object(s) of
the same size would not cause heap fragmentation, and we could verify with the
memory benchmark that it is within bounds we want.

Let's not be emotional and too anal about allocations we know about. There are
so many other, bugger opportunities for memory reduction that we should spend
time on.

[Philippe, 2013/08/21 12:41:38]

Yeah we have been slightly paranoiac on this. Measurements show that there is
only a 8 KBytes overhead when not doing premature optimizations.

+  std::vector<char> buffer;
+  const bool did_succeed = TraverseCacheDirectory(
+      cache_path,
+      base::Bind(&SimpleIndexFile::ProcessEntryFile, cache_path, &buffer,
+                 entries));
+  if (!did_succeed) {
+    LOG(ERROR) << "Could not reconstruct index from disk";
+    return;
   }
-
   out_result->did_load = true;
-
   // When we restore from disk we write the merged index file to disk right
   // away, this might save us from having to restore again next time.
   out_result->flush_required = true;