Updating the mapped_file_avoid_mmap_posix implementation.

 This implementation use copy on write mmap and read-only protection to
be notified when a new page is written to in memory so that only the
changed pages have to be written to disk.

 It allows to divide by 2 the memory used, as well as prevent a linear
search when saving data back to disk

R=digit@chromium.org
BUG=245782,248489

Review URL: https://chromiumcodereview.appspot.com/16415005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@205833 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 292 insertions, 25 deletions

diff --git a/net/disk_cache/backend_unittest.cc b/net/disk_cache/backend_unittest.cc
index 2b0a155..9c2583a 100644
--- a/net/disk_cache/backend_unittest.cc
+++ b/net/disk_cache/backend_unittest.cc
@@ -2759,7 +2759,11 @@ TEST_F(DiskCacheBackendTest, FileSharing) {
   InitCache();
 
   disk_cache::Addr address(0x80000001);
-  ASSERT_TRUE(cache_impl_->CreateExternalFile(&address));
+
+  RunTaskForTest(base::Bind(
+      base::IgnoreResult(&disk_cache::BackendImpl::CreateExternalFile),
+      base::Unretained(cache_impl_),
+      &address));
   base::FilePath name = cache_impl_->GetFileName(address);
 
   scoped_refptr<disk_cache::File> file(new disk_cache::File(false));
diff --git a/net/disk_cache/disk_cache_test_util.cc b/net/disk_cache/disk_cache_test_util.cc
index 8f334f0..12eea85 100644
--- a/net/disk_cache/disk_cache_test_util.cc
+++ b/net/disk_cache/disk_cache_test_util.cc
@@ -42,6 +42,10 @@ void CacheTestFillBuffer(char* buffer, size_t len, bool no_nulls) {
 }
 
 bool CreateCacheTestFile(const base::FilePath& name) {
+  return CreateCacheTestFileWithSize(name, 4 * 1024 * 1024);
+}
+
+bool CreateCacheTestFileWithSize(const base::FilePath& name, size_t size){
   int flags = base::PLATFORM_FILE_CREATE_ALWAYS |
               base::PLATFORM_FILE_READ |
               base::PLATFORM_FILE_WRITE;
@@ -51,7 +55,7 @@ bool CreateCacheTestFile(const base::FilePath& name) {
   if (!file->IsValid())
     return false;
 
-  file->SetLength(4 * 1024 * 1024);
+  file->SetLength(size);
   return true;
 }
 
diff --git a/net/disk_cache/disk_cache_test_util.h b/net/disk_cache/disk_cache_test_util.h
index 2c9a573..2671827 100644
--- a/net/disk_cache/disk_cache_test_util.h
+++ b/net/disk_cache/disk_cache_test_util.h
@@ -16,6 +16,9 @@
 // Re-creates a given test file inside the cache test folder.
 bool CreateCacheTestFile(const base::FilePath& name);
 
+// Re-creates a given test file inside the cache test folder of the given size.
+bool CreateCacheTestFileWithSize(const base::FilePath& name, size_t size);
+
 // Deletes all file son the cache.
 bool DeleteCache(const base::FilePath& path);
 
diff --git a/net/disk_cache/mapped_file.h b/net/disk_cache/mapped_file.h
index 4649b90..a60fca8 100644
--- a/net/disk_cache/mapped_file.h
+++ b/net/disk_cache/mapped_file.h
@@ -50,9 +50,6 @@ class NET_EXPORT_PRIVATE MappedFile : public File {
 #endif
   void* buffer_;  // Address of the memory mapped buffer.
   size_t view_size_;  // Size of the memory pointed by buffer_.
-#if defined(POSIX_AVOID_MMAP)
-  void* snapshot_;  // Copy of the buffer taken when it was last flushed.
-#endif
 
   DISALLOW_COPY_AND_ASSIGN(MappedFile);
 };
diff --git a/net/disk_cache/mapped_file_avoid_mmap_posix.cc b/net/disk_cache/mapped_file_avoid_mmap_posix.cc
index cd514a3..bb1de0c 100644
--- a/net/disk_cache/mapped_file_avoid_mmap_posix.cc
+++ b/net/disk_cache/mapped_file_avoid_mmap_posix.cc
@@ -5,9 +5,199 @@
 #include "net/disk_cache/mapped_file.h"
 
 #include <stdlib.h>
+#include <sys/mman.h>
+
+#include <map>
 
 #include "base/files/file_path.h"
+#include "base/lazy_instance.h"
 #include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/scoped_vector.h"
+#include "base/threading/thread_local.h"
+
+// This implementation of MappedFile doesn't use a shared RW mmap for
+// performance reason. Instead it will use a private RO mmap and install a SEGV
+// signal handler. When the memory is modified, the handler will register the
+// modified address and change the protection of the page to RW. When a flush is
+// then executed, it has access to the exact pages that have been modified and
+// will only write those to disk. The handler will only track half of the dirty
+// pages. If more than half the pages are modified, the flush will instead write
+// the full buffer to disk.
+
+namespace {
+
+// Choose 4k as a reasonable page size. As this file is used mainly on Android,
+// this is the real android page size.
+const size_t kPageSize = 4096;
+
+// Variable capacity array, optimized for capacity of 1. Most of the mapped file
+// are used to map exactly 2 pages. Tracking 1 page is then optimal because if
+// both pages are modified, writing the full view is the optimal behavior.
+class SmallArray {
+ public:
+  SmallArray() : capacity_(0), array_(NULL) {}
+  ~SmallArray() { SetCapacity(0); }
+
+  size_t capacity() { return capacity_; }
+  char** array() { return array_; }
+  void SetCapacity(size_t capacity) {
+    if (capacity_ > 1)
+      delete[] array_;
+    capacity_ = capacity;
+    if (capacity > 1)
+      array_ = new char*[capacity];
+    else
+      array_ = small_array_;
+  }
+
+ private:
+  size_t capacity_;
+  char** array_;
+  char* small_array_[1];
+};
+
+// Information about the memory mapped part of a file.
+struct MappedFileInfo {
+  // Stat address of the memory.
+  char* start_address;
+  // Size of the memory map.
+  size_t size;
+  // Number of dirty page. A page is dirty if the memory content is different
+  // from the file content.
+  size_t num_dirty_pages;
+  // The  dirty pages.
+  SmallArray dirty_pages;
+};
+
+// The maximum number of dirty pages that can be tracked. Limit the memory
+// overhead to 2kb per file.
+const size_t kMaxDirtyPagesCacheSize =
+    kPageSize / sizeof(char*) / 2 - sizeof(MappedFileInfo);
+
+class ThreadLocalMappedFileInfo {
+ public:
+  ThreadLocalMappedFileInfo() {}
+  ~ThreadLocalMappedFileInfo() {}
+
+  void RegisterMappedFile(disk_cache::MappedFile* mapped_file, size_t size) {
+    scoped_ptr<MappedFileInfo> new_info(new MappedFileInfo);
+    new_info->start_address = static_cast<char*>(mapped_file->buffer());
+    new_info->size = size;
+    new_info->num_dirty_pages = 0;
+    // Track half of the dirty pages, after this, just overwrite the full
+    // content.
+    size_t capacity = (size + kPageSize - 1) / kPageSize / 2;
+    if (capacity > kMaxDirtyPagesCacheSize)
+      capacity = kMaxDirtyPagesCacheSize;
+    new_info->dirty_pages.SetCapacity(capacity);
+    info_per_map_file_[mapped_file] = new_info.get();
+    infos_.push_back(new_info.release());
+    Update();
+  }
+
+  void UnregisterMappedFile(disk_cache::MappedFile* mapped_file) {
+    MappedFileInfo* info = InfoForMappedFile(mapped_file);
+    DCHECK(info);
+    info_per_map_file_.erase(mapped_file);
+    infos_.erase(std::find(infos_.begin(), infos_.end(), info));
+    Update();
+  }
+
+  MappedFileInfo* InfoForMappedFile(disk_cache::MappedFile* mapped_file) {
+    return info_per_map_file_[mapped_file];
+  }
+
+  MappedFileInfo** infos_ptr() { return infos_ptr_; }
+  size_t infos_size() { return infos_size_; }
+
+ private:
+  // Update |infos_ptr_| and |infos_size_| when |infos_| change.
+  void Update() {
+    infos_ptr_ = &infos_[0];
+    infos_size_ = infos_.size();
+  }
+
+  // Link to the MappedFileInfo for a given MappedFile.
+  std::map<disk_cache::MappedFile*, MappedFileInfo*> info_per_map_file_;
+  // Vector of information about all current MappedFile belonging to the current
+  // thread.
+  ScopedVector<MappedFileInfo> infos_;
+  // Pointer to the storage part of |infos_|. This is kept as a variable to
+  // prevent the signal handler from calling any C++ method that might allocate
+  // memory.
+  MappedFileInfo** infos_ptr_;
+  // Size of |infos_|.
+  size_t infos_size_;
+};
+
+class SegvHandler {
+ public:
+  // Register the signal handler.
+  SegvHandler();
+  ~SegvHandler() {}
+
+  // SEGV signal handler. This handler will check that the address that
+  // generated the fault is one associated with a mapped file. If that's the
+  // case, it will register the address and change the protection to RW then
+  // return. This will cause the instruction that generated the fault to be
+  // re-executed. If not, it will just reinstall the old handler and return,
+  // which will generate the fault again and let the initial handler get called.
+  static void SigSegvHandler(int sig, siginfo_t* si, void* unused);
+
+  base::ThreadLocalPointer<ThreadLocalMappedFileInfo>& thread_local_infos() {
+    return thread_local_infos_;
+  }
+
+ private:
+  base::ThreadLocalPointer<ThreadLocalMappedFileInfo> thread_local_infos_;
+  struct sigaction old_sigaction_;
+};
+
+static base::LazyInstance<SegvHandler> g_segv_handler =
+    LAZY_INSTANCE_INITIALIZER;
+
+// Initialisation method.
+SegvHandler::SegvHandler() {
+  // Setup the SIGV signal handler.
+  struct sigaction action;
+  action.sa_sigaction = SigSegvHandler;
+  sigemptyset(&action.sa_mask);
+  action.sa_flags = SA_SIGINFO | SA_RESTART;
+  sigaction(SIGSEGV, &action, &old_sigaction_);
+}
+
+void SegvHandler::SigSegvHandler(int sig, siginfo_t* si, void* unused) {
+  ThreadLocalMappedFileInfo* thread_local_info =
+      g_segv_handler.Pointer()->thread_local_infos().Get();
+  if (thread_local_info) {
+    char* addr = reinterpret_cast<char*>(si->si_addr);
+    for (size_t i = 0; i < thread_local_info->infos_size(); ++i) {
+      MappedFileInfo* info = thread_local_info->infos_ptr()[i];
+      if (info->start_address <= addr &&
+          addr < info->start_address + info->size) {
+        // Only track new dirty pages if the array has still some capacity.
+        // Otherwise, the full buffer will be written to disk and it is not
+        // necessary to track changes until the next flush.
+        if (info->num_dirty_pages < info->dirty_pages.capacity()) {
+          char* aligned_address = reinterpret_cast<char*>(
+              reinterpret_cast<size_t>(addr) & ~(kPageSize - 1));
+          mprotect(aligned_address, kPageSize, PROT_READ | PROT_WRITE);
+          info->dirty_pages.array()[info->num_dirty_pages] = aligned_address;
+        } else {
+          mprotect(info->start_address, info->size, PROT_READ | PROT_WRITE);
+        }
+        info->num_dirty_pages++;
+        return;
+      }
+    }
+  }
+  // The address it not handled by any mapped filed. Let the default handler get
+  // called.
+  sigaction(SIGSEGV, &g_segv_handler.Pointer()->old_sigaction_, NULL);
+}
+
+}  // namespace
 
 namespace disk_cache {
 
@@ -19,14 +209,21 @@ void* MappedFile::Init(const base::FilePath& name, size_t size) {
   if (!size)
     size = GetLength();
 
-  buffer_ = malloc(size);
-  snapshot_ = malloc(size);
-  if (buffer_ && snapshot_ && Read(buffer_, size, 0)) {
-    memcpy(snapshot_, buffer_, size);
-  } else {
-    free(buffer_);
-    free(snapshot_);
-    buffer_ = snapshot_ = 0;
+  buffer_ = mmap(NULL, size, PROT_READ, MAP_PRIVATE, platform_file(), 0);
+  if (reinterpret_cast<ptrdiff_t>(buffer_) == -1) {
+    NOTREACHED();
+    buffer_ = 0;
+  }
+
+  if (buffer_) {
+    ThreadLocalMappedFileInfo* thread_local_info =
+        g_segv_handler.Pointer()->thread_local_infos().Get();
+    if (!thread_local_info) {
+      thread_local_info = new ThreadLocalMappedFileInfo();
+      g_segv_handler.Pointer()->thread_local_infos().Set(thread_local_info);
+    }
+    DCHECK(size);
+    thread_local_info->RegisterMappedFile(this, size);
   }
 
   init_ = true;
@@ -46,28 +243,39 @@ bool MappedFile::Store(const FileBlock* block) {
 
 void MappedFile::Flush() {
   DCHECK(buffer_);
-  DCHECK(snapshot_);
-  const char* buffer_ptr = static_cast<const char*>(buffer_);
-  char* snapshot_ptr = static_cast<char*>(snapshot_);
-  const size_t block_size = 4096;
-  for (size_t offset = 0; offset < view_size_; offset += block_size) {
-    size_t size = std::min(view_size_ - offset, block_size);
-    if (memcmp(snapshot_ptr + offset, buffer_ptr + offset, size)) {
-      memcpy(snapshot_ptr + offset, buffer_ptr + offset, size);
-      Write(snapshot_ptr + offset, size, offset);
+  MappedFileInfo* info = g_segv_handler.Pointer()->thread_local_infos().Get()->
+      InfoForMappedFile(this);
+  DCHECK(info);
+  if (info->num_dirty_pages > info->dirty_pages.capacity()) {
+    Write(buffer_, view_size_, 0);
+  } else {
+    const char* buffer_ptr = static_cast<const char*>(buffer_);
+    for (size_t i = 0; i < info->num_dirty_pages; ++i) {
+      const char* ptr = info->dirty_pages.array()[i];
+      size_t size_to_write = kPageSize;
+      // The view_size is not a full number of page. Only write the fraction of
+      // the page that is in the view.
+      if (ptr - buffer_ptr + kPageSize > view_size_)
+        size_to_write = view_size_ - (ptr - buffer_ptr);
+      Write(ptr, size_to_write, ptr - buffer_ptr);
     }
   }
+  info->num_dirty_pages = 0;
+  mprotect(buffer_, view_size_, PROT_READ);
 }
 
 MappedFile::~MappedFile() {
   if (!init_)
     return;
 
-  if (buffer_ && snapshot_) {
+  if (buffer_) {
     Flush();
+    ThreadLocalMappedFileInfo* thread_local_info =
+        g_segv_handler.Pointer()->thread_local_infos().Get();
+    DCHECK(thread_local_info);
+    thread_local_info->UnregisterMappedFile(this);
+    munmap(buffer_, 0);
   }
-  free(buffer_);
-  free(snapshot_);
 }
 
 }  // namespace disk_cache
diff --git a/net/disk_cache/mapped_file_unittest.cc b/net/disk_cache/mapped_file_unittest.cc
index 8798db01..f4cbada 100644
--- a/net/disk_cache/mapped_file_unittest.cc
+++ b/net/disk_cache/mapped_file_unittest.cc
@@ -89,3 +89,54 @@ TEST_F(DiskCacheTest, MappedFile_AsyncIO) {
   EXPECT_FALSE(helper.callback_reused_error());
   EXPECT_STREQ(buffer1, buffer2);
 }
+
+TEST_F(DiskCacheTest, MappedFile_MemoryAccess) {
+  const size_t page_size = 4096;
+  const size_t buffer_size = 20;
+  size_t file_sizes[] = { 2 * page_size,
+                          8 * page_size + buffer_size};
+  bool full_writes[] = { false, true };
+  for (size_t i = 0; i < arraysize(file_sizes); ++i) {
+    size_t file_size = file_sizes[i];
+    for (size_t j = 0; j < arraysize(full_writes); ++j) {
+      bool full_write = full_writes[j];
+      base::FilePath filename = cache_path_.AppendASCII("a_test");
+      scoped_refptr<disk_cache::MappedFile> file(new disk_cache::MappedFile);
+      ASSERT_TRUE(CreateCacheTestFileWithSize(filename, file_size));
+      ASSERT_TRUE(file->Init(filename, file_size));
+
+      char buffer1[buffer_size];
+      char buffer2[buffer_size];
+      CacheTestFillBuffer(buffer1, buffer_size, false);
+
+      char* buffer = reinterpret_cast<char*>(file->buffer());
+
+      memcpy(buffer, buffer1, buffer_size);
+      if (full_write) {
+        for (size_t k = page_size; k <= file_size / 2; k += page_size) {
+          memcpy(buffer + k, buffer1, buffer_size);
+        }
+      }
+
+      file->Flush();
+
+      file->Read(buffer2, buffer_size, 0);
+      EXPECT_EQ(0, strncmp(buffer1, buffer2, buffer_size));
+      if (full_write) {
+        for (size_t k = page_size; k <= file_size / 2; k += page_size) {
+          file->Read(buffer2, buffer_size, k);
+          EXPECT_EQ(0, strncmp(buffer1, buffer2, buffer_size));
+        }
+      }
+
+      // Checking writes at the end of the file.
+      memcpy(buffer + file_size - buffer_size, buffer1, buffer_size);
+      file->Flush();
+      file->Read(buffer2, buffer_size, file_size - buffer_size);
+      EXPECT_EQ(0, strncmp(buffer1, buffer2, buffer_size));
+      file->Flush();
+
+      EXPECT_EQ(file_size, file->GetLength());
+    }
+  }
+}