Cache backend for devices with flash storage

BUG=157187
TEST=net_unittest --gtest_filter="SegmentTest.*;FlashCacheTest.*"


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

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

7 files changed, 550 insertions, 0 deletions

diff --git a/net/disk_cache/flash/format.h b/net/disk_cache/flash/format.h
new file mode 100644
index 0000000..12a5a48
--- /dev/null
+++ b/net/disk_cache/flash/format.h
@@ -0,0 +1,26 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_DISK_CACHE_FLASH_FORMAT_H
+#define NET_DISK_CACHE_FLASH_FORMAT_H
+
+namespace disk_cache {
+
+// Storage constants.
+const int32 kFlashPageSize = 8 * 1024;
+const int32 kFlashBlockSize = 512 * kFlashPageSize;
+
+// Segment constants.
+const int32 kFlashSegmentSize = 4 * 1024 * 1024;
+const int32 kFlashSmallEntrySize = 4 * 1024;
+const size_t kFlashMaxEntryCount = kFlashSegmentSize / kFlashSmallEntrySize - 1;
+
+// Segment summary consists of a fixed region at the end of the segment
+// containing a counter specifying the number of saved offsets followed by the
+// offsets.
+const int32 kFlashSummarySize = (1 + kFlashMaxEntryCount) * sizeof(int32);
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_FLASH_FORMAT_H
diff --git a/net/disk_cache/flash/segment.cc b/net/disk_cache/flash/segment.cc
new file mode 100644
index 0000000..a63a5a3
--- /dev/null
+++ b/net/disk_cache/flash/segment.cc
@@ -0,0 +1,99 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/logging.h"
+#include "net/disk_cache/flash/format.h"
+#include "net/disk_cache/flash/segment.h"
+#include "net/disk_cache/flash/storage.h"
+
+namespace disk_cache {
+
+Segment::Segment(int32 index, bool read_only, Storage* storage)
+    : read_only_(read_only),
+      init_(false),
+      storage_(storage),
+      offset_(index * kFlashSegmentSize),
+      summary_offset_(offset_ + kFlashSegmentSize - kFlashSummarySize),
+      write_offset_(offset_) {
+  DCHECK(storage);
+  DCHECK(storage->size() % kFlashSegmentSize == 0);
+  DCHECK(offset_ >= 0 && offset_ + kFlashSegmentSize <= storage->size());
+}
+
+Segment::~Segment() {
+  DCHECK(read_only_);
+}
+
+bool Segment::Init() {
+  if (init_)
+    return false;
+
+  if (!read_only_) {
+    init_ = true;
+    return true;
+  }
+
+  int32 summary[kFlashMaxEntryCount + 1];
+  if (!storage_->Read(summary, kFlashSummarySize, summary_offset_))
+    return false;
+
+  size_t entry_count = summary[0];
+  DCHECK_LE(entry_count, kFlashMaxEntryCount);
+
+  std::vector<int32> tmp(summary + 1, summary + 1 + entry_count);
+  header_offsets_.swap(tmp);
+  init_ = true;
+  return true;
+}
+
+bool Segment::WriteData(const void* buffer, int32 size, int32* offset) {
+  DCHECK(init_ && !read_only_);
+  DCHECK(CanHold(size));
+
+  if (!storage_->Write(buffer, size, write_offset_))
+    return false;
+  if (offset)
+    *offset = write_offset_;
+  write_offset_ += size;
+  return true;
+}
+
+bool Segment::WriteHeader(const void* header, int32 size, int32* offset) {
+  int32 my_offset;
+  if (!WriteData(header, size, &my_offset))
+    return false;
+  if (offset)
+    *offset = my_offset;
+  header_offsets_.push_back(my_offset);
+  return true;
+}
+
+bool Segment::ReadData(void* buffer, int32 size, int32 offset) const {
+  DCHECK(offset >= offset_ && offset + size <= offset_ + kFlashSegmentSize);
+  return storage_->Read(buffer, size, offset);
+}
+
+bool Segment::Close() {
+  DCHECK(init_);
+  if (read_only_)
+    return true;
+
+  DCHECK(header_offsets_.size() <= kFlashMaxEntryCount);
+
+  int32 summary[kFlashMaxEntryCount + 1];
+  summary[0] = header_offsets_.size();
+  std::copy(header_offsets_.begin(), header_offsets_.end(), summary + 1);
+  if (!storage_->Write(summary, kFlashSummarySize, summary_offset_))
+    return false;
+
+  read_only_ = true;
+  return true;
+}
+
+bool Segment::CanHold(int32 size) const {
+  return header_offsets_.size() < kFlashMaxEntryCount &&
+      write_offset_ + size <= summary_offset_;
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/flash/segment.h b/net/disk_cache/flash/segment.h
new file mode 100644
index 0000000..6dcdf46
--- /dev/null
+++ b/net/disk_cache/flash/segment.h
@@ -0,0 +1,115 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_DISK_CACHE_FLASH_SEGMENT_H_
+#define NET_DISK_CACHE_FLASH_SEGMENT_H_
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/gtest_prod_util.h"
+#include "net/base/net_export.h"
+
+namespace disk_cache {
+
+class Storage;
+
+// The underlying storage represented by Storage class, is divided into fixed
+// size logical segments, represented by this class.  Since segment size is
+// fixed, the storage size should be a multiple of segment size.  The picture
+// below describes the relation between storage and segments:
+//
+//   |-----------+-----------+-----+-------------+-----------|
+//   | segment 0 | segment 1 | ... | segment n-1 | segment n |
+//   |-----------+-----------+-----+-------------+-----------|
+//
+//   |-------------------------------------------------------|
+//   |                       storage                         |
+//   |-------------------------------------------------------|
+//
+// A segment is constructed by taking its index within the storage, a flag
+// indicating whether it is a read-only segment and a pointer to the storage on
+// which it resides.  It provides an API for reading/writing entries residing on
+// it.  Init() function must be called right after the construction of a segment
+// and one should proceed to calling other functions only if Init() has
+// succeeded.  After a successful initialization, one may proceed to call
+// non-mutating functions; mutating functions can be called if the segment is
+// not read-only.  Finally, Close() function must be called right before the
+// destruction.  Calling Close() makes the segment immutable, which means
+// mutating functions cannot be called on the object after that.
+//
+// Segment can only be used as a log, i.e. all writes are laid out sequentially
+// on a segment.  As a result, write APIs do not take an offset, but can return
+// an offset of where the write took place.  The entries living on a segment are
+// expected to consist of data part and header part where the header holds
+// enough information to identify all the data belonging to it.  The difference
+// between WriteData and WriteHeader is that writes issued with the latter have
+// their offsets saved in the metadata, which can later be retrieved.  Thus, it
+// is up to the client to specify data layout and associate the header with
+// data.  For example the client may issue WriteData calls and save the offsets
+// which then can be written using WriteHeader.  Note that it is possible to
+// write entries using just WriteHeader as well, for example if it is an entry
+// of the format where header specifies the length of the following data.
+// Before attempting to write an entry, the client should call CanHold to make
+// sure that there is enough space in the segment.
+//
+// ReadData can be called over the range that was previously written with
+// WriteData/WriteHeader.  Reading from area that was not written will fail.
+
+class NET_EXPORT_PRIVATE Segment {
+ public:
+  // |index| is the index of this segment on |storage|.  If the storage size is
+  // X and the segment size is Y, where X >> Y and X % Y == 0, then the valid
+  // values for the index are integers within the range [0, X/Y).  Thus, if
+  // |index| is given value Z, then it covers bytes on storage starting at the
+  // offset Z*Y and ending at the offset Z*Y+Y-1.
+  Segment(int32 index, bool read_only, Storage* storage);
+  ~Segment();
+
+  const std::vector<int32>& header_offsets() const { return header_offsets_; }
+
+  // Performs segment initialization.  Must be the first function called on the
+  // segment and further calls should be made only if it is successful.
+  bool Init();
+
+  // Writes |size| bytes of data from |buffer| to segment, returns false if
+  // fails and true if succeeds and sets the |offset|, if it is not NULL.  Can
+  // block for a long time.
+  bool WriteData(const void* buffer, int32 size, int32* offset);
+
+  // Writes |header| of |size| bytes, returns false if fails and true if
+  // succeeds and sets the |offset|, if it is not NULL.  Can block for a long
+  // time.  The difference between this function and WriteData is that the
+  // offset of this write operation is saved in the segment metadata and can
+  // later be retrieved via |header_offsets|.
+  bool WriteHeader(const void* header, int32 size, int32* offset);
+
+  // Reads |size| bytes of data living at |offset| into |buffer|, returns true
+  // on success and false on failure.
+  bool ReadData(void* buffer, int32 size, int32 offset) const;
+
+  // Closes the segment, returns true on success and false on failure.  Closing
+  // a segment makes it immutable.
+  bool Close();
+
+  // Returns true if segment can accommodate an entry of |size| bytes.
+  bool CanHold(int32 size) const;
+
+ private:
+  FRIEND_TEST_ALL_PREFIXES(SegmentTest, CreateDestroy);
+
+  bool read_only_;  // Indicates whether the segment can be written to.
+  bool init_;  // Indicates whether segment was initialized.
+  Storage* storage_;  // Storage on which the segment resides.
+  const int32 offset_;  // Offset of the segment on |storage_|.
+  const int32 summary_offset_;  // Offset of the segment summary.
+  int32 write_offset_;  // Current write offset.
+  std::vector<int32> header_offsets_;
+
+  DISALLOW_COPY_AND_ASSIGN(Segment);
+};
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_FLASH_SEGMENT_H_
diff --git a/net/disk_cache/flash/segment_unittest.cc b/net/disk_cache/flash/segment_unittest.cc
new file mode 100644
index 0000000..5bf3b6b
--- /dev/null
+++ b/net/disk_cache/flash/segment_unittest.cc
@@ -0,0 +1,167 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <map>
+
+#include "base/logging.h"
+#include "base/scoped_temp_dir.h"
+#include "base/stl_util.h"
+#include "base/memory/scoped_ptr.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/disk_cache_test_util.h"
+#include "net/disk_cache/flash/segment.h"
+#include "net/disk_cache/flash/storage.h"
+#include "net/disk_cache/flash/format.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+const int kSegmentCount = 3;
+const int kEntryCount = 10;
+const int32 kStorageSize = disk_cache::kFlashSegmentSize * kSegmentCount;
+const int32 kSegmentFreeSpace = disk_cache::kFlashSegmentSize -
+    disk_cache::kFlashSummarySize;
+
+template<int SIZE>
+struct Entry {
+  enum { size = SIZE };
+
+  Entry() { CacheTestFillBuffer(data, size, false); }
+
+  bool operator==(const Entry& rhs) const {
+    return std::equal(data, data + size, rhs.data);
+  }
+
+  char data[size];
+};
+
+const int32 kSmallEntrySize = 100;
+const int32 kLargeEntrySize = disk_cache::kFlashSegmentSize / 4;
+
+typedef Entry<kSmallEntrySize> SmallEntry;
+typedef Entry<kLargeEntrySize> LargeEntry;
+
+}  // namespace
+
+class SegmentTest : public testing::Test {
+ protected:
+  virtual void SetUp() {
+    ASSERT_TRUE(temp_dir_.CreateUniqueTempDir());
+    const FilePath path(temp_dir_.path().Append(FILE_PATH_LITERAL("cache")));
+    storage_.reset(new disk_cache::Storage(path, kStorageSize));
+    ASSERT_TRUE(storage_->Init());
+  }
+
+  virtual void TearDown() {
+    storage_.reset();
+  }
+
+  scoped_ptr<disk_cache::Storage> storage_;
+  ScopedTempDir temp_dir_;
+};
+
+namespace disk_cache {
+
+TEST_F(SegmentTest, CreateDestroy) {
+  for (int i = 0; i < kSegmentCount; ++i) {
+    scoped_ptr<disk_cache::Segment> segment(
+        new disk_cache::Segment(i, false, storage_.get()));
+
+    EXPECT_TRUE(segment->Init());
+    // TODO(agayev): check offset validity via Init.
+    EXPECT_EQ(segment->offset_, disk_cache::kFlashSegmentSize * i);
+    EXPECT_EQ(segment->write_offset_, segment->offset_);
+    EXPECT_EQ(segment->summary_offset_, disk_cache::kFlashSegmentSize * (i+1) -
+              disk_cache::kFlashSummarySize);
+    EXPECT_TRUE(segment->Close());
+  }
+}
+
+TEST_F(SegmentTest, WriteDataReadData) {
+  for (int i = 0; i < kSegmentCount; ++i) {
+    scoped_ptr<disk_cache::Segment> segment(
+        new disk_cache::Segment(i, false, storage_.get()));
+
+    EXPECT_TRUE(segment->Init());
+    SmallEntry entry1;
+    EXPECT_TRUE(segment->CanHold(entry1.size));
+    int32 offset;
+    EXPECT_TRUE(segment->WriteData(entry1.data, entry1.size, &offset));
+    EXPECT_TRUE(segment->Close());
+
+    segment.reset(new disk_cache::Segment(i, true, storage_.get()));
+    EXPECT_TRUE(segment->Init());
+    SmallEntry entry2;
+    EXPECT_TRUE(segment->ReadData(entry2.data, entry2.size, offset));
+    EXPECT_EQ(entry1, entry2);
+    EXPECT_TRUE(segment->Close());
+  }
+}
+
+TEST_F(SegmentTest, WriteHeaderReadData) {
+  for (int i = 0; i < kSegmentCount; ++i) {
+    scoped_ptr<disk_cache::Segment> segment(
+        new disk_cache::Segment(i, false, storage_.get()));
+
+    EXPECT_TRUE(segment->Init());
+    SmallEntry entry1;
+    EXPECT_TRUE(segment->CanHold(entry1.size));
+    int32 offset;
+    EXPECT_TRUE(segment->WriteHeader(entry1.data, entry1.size, &offset));
+    EXPECT_EQ(1u, segment->header_offsets().size());
+    EXPECT_EQ(offset, segment->header_offsets().front());
+    EXPECT_TRUE(segment->Close());
+
+    segment.reset(new disk_cache::Segment(i, true, storage_.get()));
+    EXPECT_TRUE(segment->Init());
+    SmallEntry entry2;
+    EXPECT_EQ(1u, segment->header_offsets().size());
+    offset = segment->header_offsets().front();
+    EXPECT_TRUE(segment->ReadData(entry2.data, entry2.size, offset));
+    EXPECT_EQ(entry1, entry2);
+    EXPECT_TRUE(segment->Close());
+  }
+}
+
+TEST_F(SegmentTest, FillWithSmallEntries) {
+  for (int i = 0; i < kSegmentCount; ++i) {
+    scoped_ptr<disk_cache::Segment> segment(
+        new disk_cache::Segment(i, false, storage_.get()));
+
+    EXPECT_TRUE(segment->Init());
+    SmallEntry entry;
+    int32 num_bytes_written = 0;
+    while (segment->CanHold(entry.size)) {
+      EXPECT_TRUE(segment->WriteHeader(entry.data, entry.size, NULL));
+      num_bytes_written += entry.size;
+    }
+    int32 space_left = kSegmentFreeSpace - num_bytes_written;
+    EXPECT_GE(space_left, entry.size);
+    EXPECT_EQ(segment->header_offsets().size(),
+              disk_cache::kFlashMaxEntryCount);
+    EXPECT_TRUE(segment->Close());
+  }
+}
+
+TEST_F(SegmentTest, FillWithLargeEntries) {
+  for (int i = 0; i < kSegmentCount; ++i) {
+    scoped_ptr<disk_cache::Segment> segment(
+        new disk_cache::Segment(i, false, storage_.get()));
+
+    EXPECT_TRUE(segment->Init());
+    LargeEntry entry;
+    int32 num_bytes_written = 0;
+    while (segment->CanHold(entry.size)) {
+      EXPECT_TRUE(segment->WriteHeader(entry.data, entry.size, NULL));
+      num_bytes_written += entry.size;
+    }
+    int32 space_left = kSegmentFreeSpace - num_bytes_written;
+    EXPECT_LT(space_left, entry.size);
+    EXPECT_LT(segment->header_offsets().size(),
+              disk_cache::kFlashMaxEntryCount);
+    EXPECT_TRUE(segment->Close());
+  }
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/flash/storage.cc b/net/disk_cache/flash/storage.cc
new file mode 100644
index 0000000..24c2774
--- /dev/null
+++ b/net/disk_cache/flash/storage.cc
@@ -0,0 +1,63 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/disk_cache/flash/storage.h"
+
+#include <fcntl.h>
+
+#include "base/logging.h"
+#include "base/platform_file.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/flash/format.h"
+
+namespace disk_cache {
+
+Storage::Storage(const FilePath& path, int32 size) : path_(path), size_(size) {
+  COMPILE_ASSERT(kFlashPageSize % 2 == 0, invalid_page_size);
+  COMPILE_ASSERT(kFlashBlockSize % kFlashPageSize == 0, invalid_block_size);
+  DCHECK(size_ % kFlashBlockSize == 0);
+}
+
+bool Storage::Init() {
+  int flags = base::PLATFORM_FILE_READ |
+              base::PLATFORM_FILE_WRITE |
+              base::PLATFORM_FILE_OPEN_ALWAYS;
+
+  file_ = base::CreatePlatformFile(path_, flags, NULL, NULL);
+  if (file_ == base::kInvalidPlatformFileValue)
+    return false;
+
+  // TODO(agayev): if file already exists, do some validation and return either
+  // true or false based on the result.
+
+#if defined(OS_LINUX)
+  fallocate(file_, 0, 0, size_);
+#endif
+
+  return true;
+}
+
+Storage::~Storage() {
+  base::ClosePlatformFile(file_);
+}
+
+bool Storage::Read(void* buffer, int32 size, int32 offset) {
+  DCHECK(buffer);
+  DCHECK(offset >= 0 && offset + size <= size_);
+
+  int rv = base::ReadPlatformFile(file_, offset, static_cast<char*>(buffer),
+                                  size);
+  return rv == size;
+}
+
+bool Storage::Write(const void* buffer, int32 size, int32 offset) {
+  DCHECK(buffer);
+  DCHECK(offset >= 0 && offset + size <= size_);
+
+  int rv = base::WritePlatformFile(file_, offset,
+                                   static_cast<const char*>(buffer), size);
+  return rv == size;
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/flash/storage.h b/net/disk_cache/flash/storage.h
new file mode 100644
index 0000000..756014f
--- /dev/null
+++ b/net/disk_cache/flash/storage.h
@@ -0,0 +1,35 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_DISK_CACHE_FLASH_STORAGE_H_
+#define NET_DISK_CACHE_FLASH_STORAGE_H_
+
+#include "base/basictypes.h"
+#include "base/platform_file.h"
+#include "net/base/net_export.h"
+
+namespace disk_cache {
+
+class NET_EXPORT_PRIVATE Storage {
+ public:
+  Storage(const FilePath& path, int32 size);
+  bool Init();
+  ~Storage();
+
+  int32 size() const { return size_; }
+
+  bool Read(void* buffer, int32 size, int32 offset);
+  bool Write(const void* buffer, int32 size, int32 offset);
+
+ private:
+  FilePath path_;
+  int32 size_;
+  base::PlatformFile file_;
+
+  DISALLOW_COPY_AND_ASSIGN(Storage);
+};
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_FLASH_STORAGE_H_
diff --git a/net/disk_cache/flash/storage_unittest.cc b/net/disk_cache/flash/storage_unittest.cc
new file mode 100644
index 0000000..73a78ef
--- /dev/null
+++ b/net/disk_cache/flash/storage_unittest.cc
@@ -0,0 +1,45 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/file_path.h"
+#include "base/scoped_temp_dir.h"
+#include "net/base/io_buffer.h"
+#include "net/disk_cache/disk_cache_test_util.h"
+#include "net/disk_cache/flash/storage.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+const int32 kSizes[]   = {512, 1024, 4096, 133, 1333, 13333};
+const int32 kOffsets[] = {0,   1,    3333, 125, 12443, 4431};
+const int32 kStorageSize = 16 * 1024 * 1024;
+
+}  // namespace
+
+TEST(FlashCacheTest, StorageReadWrite) {
+  ScopedTempDir tempdir;
+  ASSERT_TRUE(tempdir.CreateUniqueTempDir());
+  const FilePath path(tempdir.path().Append(FILE_PATH_LITERAL("cache")));
+
+  disk_cache::Storage storage(path, kStorageSize);
+  EXPECT_TRUE(storage.Init());
+
+  for (size_t i = 0; i < arraysize(kOffsets); ++i) {
+    int32 size = kSizes[i];
+    int32 offset = kOffsets[i];
+
+    scoped_refptr<net::IOBuffer> write_buffer(new net::IOBuffer(size));
+    scoped_refptr<net::IOBuffer> read_buffer(new net::IOBuffer(size));
+
+    CacheTestFillBuffer(write_buffer->data(), size, false);
+
+    bool rv = storage.Write(write_buffer->data(), size, offset);
+    EXPECT_TRUE(rv);
+
+    rv = storage.Read(read_buffer->data(), size, offset);
+    EXPECT_TRUE(rv);
+
+    EXPECT_EQ(0, memcmp(read_buffer->data(), write_buffer->data(), size));
+  }
+}