[BlobStorage] BlobMemoryController & tests

storage/browser/blob/blob_memory_controller.cc

+// Copyright 2016 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 "storage/browser/blob/blob_memory_controller.h"
+
+#include <algorithm>
+
+#include "base/callback.h"
+#include "base/callback_helpers.h"
+#include "base/containers/small_map.h"
+#include "base/files/file_util.h"
+#include "base/guid.h"
+#include "base/location.h"
+#include "base/memory/ptr_util.h"
+#include "base/metrics/histogram_macros.h"
+#include "base/numerics/safe_conversions.h"
+#include "base/numerics/safe_math.h"
+#include "base/single_thread_task_runner.h"
+#include "base/stl_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/task_runner.h"
+#include "base/task_runner_util.h"
+#include "base/threading/thread_restrictions.h"
+#include "base/time/time.h"
+#include "base/trace_event/trace_event.h"
+#include "base/tuple.h"
+#include "storage/browser/blob/blob_data_builder.h"
+#include "storage/browser/blob/blob_data_item.h"
+#include "storage/browser/blob/shareable_blob_data_item.h"
+#include "storage/browser/blob/shareable_file_reference.h"
+#include "storage/common/data_element.h"
+
+using base::File;
+using base::FilePath;
+using FileCreationInfo = storage::BlobMemoryController::FileCreationInfo;
+
+namespace storage {
+namespace {
+using QuotaAllocationTask = BlobMemoryController::QuotaAllocationTask;
+
+File::Error CreateBlobDirectory(const FilePath& blob_storage_dir) {
+  File::Error error;
+  bool success = base::CreateDirectoryAndGetError(blob_storage_dir, &error);
+  UMA_HISTOGRAM_BOOLEAN("Storage.Blob.DirectorySuccess", success);
+  if (!success) {
+    UMA_HISTOGRAM_ENUMERATION("Storage.Blob.DirectorySuccess.Error", -error,
+                              -File::FILE_ERROR_MAX);
+    return error;
+  }
+  return File::FILE_OK;
+}
+
+// Used for new unpopulated file items. Caller must populate file reference in
+// returned FileCreationInfos.
+std::vector<FileCreationInfo> CreateEmptyFiles(
+    const FilePath& blob_storage_dir,
+    std::vector<base::FilePath> file_paths) {
+  base::ThreadRestrictions::AssertIOAllowed();
+
+  if (CreateBlobDirectory(blob_storage_dir) != File::FILE_OK)
+    return std::vector<FileCreationInfo>();
+
+  std::vector<FileCreationInfo> result;
+  for (const base::FilePath& file_path : file_paths) {
+    FileCreationInfo creation_info;
+    // Try to open our file.
+    File file(file_path, File::FLAG_CREATE_ALWAYS | File::FLAG_WRITE);
+    creation_info.path = std::move(file_path);
+    creation_info.error = file.error_details();
+    UMA_HISTOGRAM_ENUMERATION("Storage.Blob.TransportFileCreate",
+                              -creation_info.error, -File::FILE_ERROR_MAX);
+    if (creation_info.error != File::FILE_OK)
+      return std::vector<FileCreationInfo>();
+
+    // Grab the file info to get the "last modified" time and store the file.
+    File::Info file_info;
+    bool success = file.GetInfo(&file_info);
+    UMA_HISTOGRAM_BOOLEAN("Storage.Blob.TransportFileInfoSuccess", success);
+    creation_info.error = success ? File::FILE_OK : File::FILE_ERROR_FAILED;
+    if (!success)
+      return std::vector<FileCreationInfo>();
+    creation_info.file = std::move(file);
+
+    result.push_back(std::move(creation_info));
+  }
+  return result;
+}
+
+// Used to evict multiple memory items out to a single file. Caller must
+// populate file reference in returned FileCreationInfo.
+FileCreationInfo CreateFileAndWriteItems(const FilePath& blob_storage_dir,
+                                         const FilePath& file_path,
+                                         std::vector<DataElement*> items,
+                                         size_t total_size_bytes) {
+  DCHECK_NE(0u, total_size_bytes);
+  UMA_HISTOGRAM_MEMORY_KB("Storage.Blob.PageFileSize", total_size_bytes / 1024);
+  base::ThreadRestrictions::AssertIOAllowed();
+
+  FileCreationInfo creation_info;
+  creation_info.error = CreateBlobDirectory(blob_storage_dir);
+  if (creation_info.error != File::FILE_OK)
+    return creation_info;
+
+  // Create the page file.
+  File file(file_path, File::FLAG_CREATE_ALWAYS | File::FLAG_WRITE);
+  creation_info.path = std::move(file_path);

[michaeln, 2016/10/04 00:11:54]

stupid c++ question? does this do anything the callers underlying file_path
value? seems like this might move the constref such that the file_path local is
not longer refers to the underlaying path data. i don't quite get it? aren't we
going to have to copy the bytes into the creation_info struct.

{
  const FilePath path("fred");
  CreateFileAndWriteItems(..., path, ...);
  assert(path == "fred");  // this assertion holds, right?
}

[dmurph, 2016/10/06 00:45:39]

Ah, actually, this does a copy. If we std::move'd it into this method, then yes,
that file path would be gone in the caller. But because we're given a const ref,
then this doesn't actually change that object and does a copy-then-move, which
is weird.

+  creation_info.error = file.error_details();
+  UMA_HISTOGRAM_ENUMERATION("Storage.Blob.PageFileCreate", -creation_info.error,
+                            -File::FILE_ERROR_MAX);
+  if (creation_info.error != File::FILE_OK)
+    return creation_info;
+
+  // Write data.
+  file.SetLength(total_size_bytes);
+  int bytes_written = 0;
+  for (DataElement* element : items) {
+    DCHECK_EQ(DataElement::TYPE_BYTES, element->type());
+    size_t length = base::checked_cast<size_t>(element->length());
+    size_t bytes_left = length;
+    while (bytes_left > 0) {
+      bytes_written =
+          file.WriteAtCurrentPos(element->bytes() + (length - bytes_left),
+                                 base::saturated_cast<int>(bytes_left));
+      if (bytes_written < 0)
+        break;
+      DCHECK_LE(static_cast<size_t>(bytes_written), bytes_left);
+      bytes_left -= bytes_written;
+    }
+    if (bytes_written < 0)
+      break;
+  }
+  UMA_HISTOGRAM_BOOLEAN("Storage.Blob.PageFileWriteSuccess", bytes_written > 0);
+
+  File::Info info;
+  bool success = file.GetInfo(&info);
+  UMA_HISTOGRAM_BOOLEAN("Storage.Blob.PageFileInfoSuccess", success);
+  creation_info.error =
+      bytes_written < 0 || !success ? File::FILE_ERROR_FAILED : File::FILE_OK;
+  creation_info.last_modified = info.last_modified;
+  return creation_info;
+}
+
+std::vector<scoped_refptr<ShareableBlobDataItem>> WrapInRefPtrs(

[michaeln, 2016/10/04 00:11:54]

if the sig of the methods are changed, might not need this helper

[dmurph, 2016/10/06 00:45:39]

Done.

+    const std::vector<ShareableBlobDataItem*> items_ptrs) {
+  std::vector<scoped_refptr<ShareableBlobDataItem>> result;
+  for (ShareableBlobDataItem* item : items_ptrs) {
+    result.push_back(make_scoped_refptr(item));
+  }
+  return result;
+}
+
+uint64_t GetTotalSizeAndFileSizes(
+    const std::vector<scoped_refptr<ShareableBlobDataItem>>&
+        unreserved_file_items,
+    std::vector<uint64_t>* file_sizes_output) {
+  uint64_t total_size_output = 0;
+  base::SmallMap<std::map<uint64_t, uint64_t>> file_sizes;
+  for (const auto& item : unreserved_file_items) {
+    const DataElement& element = item->item()->data_element();
+    uint64_t file_id = BlobDataBuilder::GetFutureFileID(element);
+    auto it = file_sizes.find(file_id);
+    if (it != file_sizes.end()) {
+      it->second = std::max(it->second, element.offset() + element.length());
+    } else {
+      file_sizes[file_id] = element.offset() + element.length();
+    }
+    total_size_output += element.length();
+  }
+  for (const auto& size_pair : file_sizes) {
+    file_sizes_output->push_back(size_pair.second);

[michaeln, 2016/10/04 00:11:55]

does the order of values in the array matter?

[dmurph, 2016/10/06 00:45:39]

Yeah, it needs to be in file_id order, which is enforced by SmallMap<map<>>

+  }
+  return total_size_output;
+}
+
+}  // namespace
+
+BlobMemoryController::QuotaAllocationTask::~QuotaAllocationTask() {}
+
+// The my_list_position_ iterator is stored so that we can remove ourself from
+// the task list when it is cancelled.
+template <typename T>
+class BlobMemoryController::BaseQuotaAllocationTask
+    : public BlobMemoryController::QuotaAllocationTask {
+ public:
+  BaseQuotaAllocationTask() : allocation_size_(0) {}
+  explicit BaseQuotaAllocationTask(uint64_t allocation_size)
+      : allocation_size_(allocation_size) {}
+
+  ~BaseQuotaAllocationTask() override {}
+
+  void set_my_list_position(typename T::iterator my_list_position) {
+    my_list_position_ = my_list_position;
+  }
+  typename T::iterator my_list_position() { return my_list_position_; }
+
+  uint64_t allocation_size() { return allocation_size_; }
+  void set_allocation_size(uint64_t allocation_size) {
+    allocation_size_ = allocation_size;
+  }
+
+ private:
+  uint64_t allocation_size_;
+  typename T::iterator my_list_position_;
+};
+
+class BlobMemoryController::MemoryQuotaAllocationTask
+    : public BlobMemoryController::BaseQuotaAllocationTask<
+          PendingMemoryQuotaTaskList> {
+ public:
+  MemoryQuotaAllocationTask(
+      BlobMemoryController* controller,
+      uint64_t quota_request_size,
+      std::vector<scoped_refptr<ShareableBlobDataItem>> pending_items,
+      MemoryQuotaRequestCallback done_callback)
+      : BaseQuotaAllocationTask(quota_request_size),
+        controller_(controller),
+        pending_items_(std::move(pending_items)),
+        done_callback_(done_callback),
+        weak_factory_(this) {}
+
+  ~MemoryQuotaAllocationTask() override = default;
+
+  void RunDoneCallback(bool success) const {
+    if (success) {
+      for (const auto& item : pending_items_) {
+        item->set_state(ShareableBlobDataItem::QUOTA_GRANTED);
+      }
+    }
+    done_callback_.Run(success);
+  }
+
+  void Cancel() override {
+    controller_->pending_memory_quota_total_size_ -= allocation_size();
+    // This call destroys this object.
+    controller_->pending_memory_quota_tasks_.erase(my_list_position());
+  }
+
+  BlobMemoryController* controller_;
+  std::vector<scoped_refptr<ShareableBlobDataItem>> pending_items_;
+  MemoryQuotaRequestCallback done_callback_;
+
+  base::WeakPtrFactory<MemoryQuotaAllocationTask> weak_factory_;
+  DISALLOW_COPY_AND_ASSIGN(MemoryQuotaAllocationTask);
+};
+
+class BlobMemoryController::FileQuotaAllocationTask
+    : public BlobMemoryController::BaseQuotaAllocationTask<
+          PendingFileQuotaTaskList> {
+ public:
+  FileQuotaAllocationTask(
+      BlobMemoryController* memory_controller,
+      std::vector<scoped_refptr<ShareableBlobDataItem>> unreserved_file_items,
+      const FileQuotaRequestCallback& done_callback)
+      : controller_(memory_controller),
+        done_callback_(done_callback),
+        weak_factory_(this) {
+    // Get the file sizes and total size.
+    std::vector<uint64_t> file_sizes;
+    uint64_t total_size =
+        GetTotalSizeAndFileSizes(unreserved_file_items, &file_sizes);
+    DCHECK_LE(total_size, controller_->GetAvailableFileSpaceForBlobs());
+    set_allocation_size(total_size);
+
+    // Check & set our item states.
+    for (const auto& shareable_item : unreserved_file_items) {
+      DCHECK_EQ(ShareableBlobDataItem::QUOTA_NEEDED, shareable_item->state());
+      DCHECK_EQ(DataElement::TYPE_FILE, shareable_item->item()->type());
+      shareable_item->set_state(ShareableBlobDataItem::QUOTA_REQUESTED);
+    }
+    pending_items_ = std::move(unreserved_file_items);
+
+    // Increment disk usage and create our file references.
+    controller_->disk_used_ += total_size;

[michaeln, 2016/10/04 00:11:54]

nit: i was looking around for += allocation_size() to balance the -=
allocation_size() statements elsewhere

[dmurph, 2016/10/06 00:45:39]

Done.

+    std::vector<base::FilePath> file_paths;
+    std::vector<scoped_refptr<ShareableFileReference>> references;
+    for (size_t i = 0; i < file_sizes.size(); i++) {
+      file_paths.push_back(controller_->GenerateNextPageFileName());
+      references.push_back(ShareableFileReference::GetOrCreate(
+          file_paths.back(), ShareableFileReference::DELETE_ON_FINAL_RELEASE,
+          controller_->file_runner_.get()));
+      references.back()->AddFinalReleaseCallback(
+          base::Bind(&BlobMemoryController::OnBlobFileDelete,
+                     controller_->weak_factory_.GetWeakPtr(), file_sizes[i]));
+    }
+
+    // Send file creation task to file thread.
+    base::PostTaskAndReplyWithResult(
+        controller_->file_runner_.get(), FROM_HERE,
+        base::Bind(&CreateEmptyFiles, controller_->blob_storage_dir_,
+                   base::Passed(&file_paths)),
+        base::Bind(&FileQuotaAllocationTask::OnCreateEmptyFiles,
+                   weak_factory_.GetWeakPtr(), base::Passed(&references)));
+    controller_->RecordTracingCounters();
+  }
+  ~FileQuotaAllocationTask() override {}
+
+  void RunDoneCallback(bool success,
+                       std::vector<FileCreationInfo> file_info) const {
+    done_callback_.Run(success, std::move(file_info));
+  }
+
+  void Cancel() override {
+    controller_->disk_used_ -= allocation_size();
+    // This call destroys this object.
+    controller_->pending_file_quota_tasks_.erase(my_list_position());
+  }
+
+  void OnCreateEmptyFiles(
+      std::vector<scoped_refptr<ShareableFileReference>> references,
+      std::vector<FileCreationInfo> files) {
+    if (files.empty()) {
+      controller_->disk_used_ -= allocation_size();
+      // This will call call our callback and delete the object correctly.
+      controller_->DisableFilePaging();
+      return;
+    }
+    DCHECK_EQ(files.size(), references.size());
+    for (size_t i = 0; i < files.size(); i++) {
+      files[i].file_reference = std::move(references[i]);
+    }
+    for (const auto& item : pending_items_) {
+      item->set_state(ShareableBlobDataItem::QUOTA_GRANTED);
+    }
+    RunDoneCallback(true, std::move(files));
+  }
+
+  BlobMemoryController* controller_;
+  std::vector<scoped_refptr<ShareableBlobDataItem>> pending_items_;
+  scoped_refptr<base::TaskRunner> file_runner_;
+  FileQuotaRequestCallback done_callback_;
+
+  base::WeakPtrFactory<FileQuotaAllocationTask> weak_factory_;
+  DISALLOW_COPY_AND_ASSIGN(FileQuotaAllocationTask);
+};
+
+FileCreationInfo::FileCreationInfo() = default;
+FileCreationInfo::~FileCreationInfo() = default;
+FileCreationInfo::FileCreationInfo(FileCreationInfo&&) = default;
+FileCreationInfo& FileCreationInfo::operator=(FileCreationInfo&&) = default;
+
+BlobMemoryController::BlobMemoryController(
+    const base::FilePath& storage_directory,
+    scoped_refptr<base::TaskRunner> file_runner)
+    : file_paging_enabled_(file_runner.get() != nullptr),
+      blob_storage_dir_(storage_directory),
+      file_runner_(std::move(file_runner)),
+      recent_item_cache_(
+          base::MRUCache<uint64_t, ShareableBlobDataItem*>::NO_AUTO_EVICT),
+      weak_factory_(this) {}
+
+BlobMemoryController::~BlobMemoryController() {}
+
+void BlobMemoryController::DisableFilePaging() {
+  file_paging_enabled_ = false;
+  blob_memory_used_ += in_flight_memory_used_;
+  in_flight_memory_used_ = 0;
+  items_saving_to_disk_.clear();
+  for (const auto& file_request : pending_file_quota_tasks_) {
+    DCHECK_GE(disk_used_, file_request->allocation_size());
+    disk_used_ -= file_request->allocation_size();
+  }
+  pending_evictions_ = 0;
+  pending_memory_quota_total_size_ = 0;
+  recent_item_cache_.Clear();
+  recent_item_cache_bytes_ = 0;
+  file_runner_ = nullptr;
+
+  PendingMemoryQuotaTaskList old_memory_tasks;
+  PendingFileQuotaTaskList old_file_tasks;
+  std::swap(old_memory_tasks, pending_memory_quota_tasks_);
+  std::swap(old_file_tasks, pending_file_quota_tasks_);
+  // Kill all disk operation callbacks.
+  weak_factory_.InvalidateWeakPtrs();
+
+  // Don't call the callbacks until we have a consistant state.
+  for (const auto& memory_request : old_memory_tasks) {
+    memory_request->RunDoneCallback(false);
+  }
+  for (const auto& file_request : old_file_tasks) {
+    file_request->RunDoneCallback(false, std::vector<FileCreationInfo>());
+  }
+}
+
+BlobMemoryController::Strategy BlobMemoryController::DetermineStrategy(
+    size_t preemptive_transported_bytes,
+    uint64_t total_transportation_bytes) const {
+  if (total_transportation_bytes == 0) {
+    return Strategy::NONE_NEEDED;
+  }
+  if (!CanReserveQuota(total_transportation_bytes)) {
+    return Strategy::TOO_LARGE;
+  }
+  // Handle the case where we have all the bytes preemptively transported, and
+  // we can also fit them.
+  if (preemptive_transported_bytes == total_transportation_bytes &&
+      pending_memory_quota_tasks_.empty() &&
+      preemptive_transported_bytes < GetAvailableMemoryForBlobs()) {
+    return Strategy::NONE_NEEDED;
+  }
+  if (file_paging_enabled_ &&
+      (total_transportation_bytes > limits_.max_blob_in_memory_space)) {
+    return Strategy::FILE;
+  }
+  if (total_transportation_bytes > limits_.max_ipc_memory_size) {
+    return Strategy::SHARED_MEMORY;
+  }
+  return Strategy::IPC;
+}
+
+bool BlobMemoryController::CanReserveQuota(uint64_t size) const {
+  // We check each size independently as a blob can't be constructed in both
+  // disk and memory.
+  return size <= GetAvailableMemoryForBlobs() ||
+         size <= GetAvailableFileSpaceForBlobs();
+}
+
+base::WeakPtr<QuotaAllocationTask> BlobMemoryController::ReserveMemoryQuota(
+    std::vector<ShareableBlobDataItem*> unreserved_memory_items,
+    const MemoryQuotaRequestCallback& done_callback) {
+  base::CheckedNumeric<uint64_t> unsafe_total_bytes_needed = 0;
+  for (ShareableBlobDataItem* item : unreserved_memory_items) {
+    DCHECK_EQ(ShareableBlobDataItem::QUOTA_NEEDED, item->state());
+    DCHECK(item->item()->type() == DataElement::TYPE_BYTES_DESCRIPTION ||
+           item->item()->type() == DataElement::TYPE_BYTES);
+    DCHECK(item->item()->length() > 0);
+    unsafe_total_bytes_needed += item->item()->length();
+    item->set_state(ShareableBlobDataItem::QUOTA_REQUESTED);
+  }
+
+  uint64_t total_bytes_needed = unsafe_total_bytes_needed.ValueOrDie();
+  if (total_bytes_needed == 0) {
+    done_callback.Run(true);
+    return base::WeakPtr<QuotaAllocationTask>();
+  }
+
+  // If we're currently waiting for blobs to page already, then we add
+  // ourselves to the end of the queue. Once paging is complete, we'll schedule
+  // more paging for any more pending blobs.
+  if (!pending_memory_quota_tasks_.empty()) {

[michaeln, 2016/10/04 00:11:54]

it'd might be good to share this block of code with the block below at line 471,
amybe a helper function to AppendMemoryTask()

[dmurph, 2016/10/06 00:45:39]

Done.

+    DCHECK(!file_paging_enabled_);
+    std::vector<scoped_refptr<ShareableBlobDataItem>> item_handles =
+        WrapInRefPtrs(unreserved_memory_items);
+
+    pending_memory_quota_total_size_ += total_bytes_needed;
+    pending_memory_quota_tasks_.push_back(
+        base::MakeUnique<MemoryQuotaAllocationTask>(
+            this, total_bytes_needed, std::move(item_handles), done_callback));
+    pending_memory_quota_tasks_.back()->set_my_list_position(
+        --pending_memory_quota_tasks_.end());
+
+    return pending_memory_quota_tasks_.back()->weak_factory_.GetWeakPtr();
+  }
+
+  // Store right away if we can.
+  if (total_bytes_needed <= GetAvailableMemoryForBlobs()) {
+    // If we're past our blob memory limit, then schedule our paging.
+    blob_memory_used_ += total_bytes_needed;
+    for (ShareableBlobDataItem* item : unreserved_memory_items) {
+      item->set_state(ShareableBlobDataItem::QUOTA_GRANTED);
+    }
+    if (file_paging_enabled_)
+      MaybeScheduleEvictionUntilSystemHealthy();
+    done_callback.Run(true);
+    return base::WeakPtr<QuotaAllocationTask>();
+  }
+
+  // Size is larger than available memory.
+  DCHECK(pending_memory_quota_tasks_.empty());
+  DCHECK_EQ(0u, pending_memory_quota_total_size_);
+  std::vector<scoped_refptr<ShareableBlobDataItem>> item_handles =
+      WrapInRefPtrs(unreserved_memory_items);
+
+  pending_memory_quota_total_size_ = total_bytes_needed;
+  pending_memory_quota_tasks_.push_back(
+      base::MakeUnique<MemoryQuotaAllocationTask>(
+          this, total_bytes_needed, std::move(item_handles), done_callback));
+  pending_memory_quota_tasks_.back()->set_my_list_position(
+      --pending_memory_quota_tasks_.end());
+
+  auto weak_ptr =
+      pending_memory_quota_tasks_.back()->weak_factory_.GetWeakPtr();
+  MaybeScheduleEvictionUntilSystemHealthy();
+  return weak_ptr;
+}
+
+base::WeakPtr<QuotaAllocationTask> BlobMemoryController::ReserveFileQuota(
+    std::vector<scoped_refptr<ShareableBlobDataItem>> unreserved_file_items,
+    const FileQuotaRequestCallback& done_callback) {
+  pending_file_quota_tasks_.push_back(base::MakeUnique<FileQuotaAllocationTask>(
+      this, std::move(unreserved_file_items), done_callback));
+  pending_file_quota_tasks_.back()->set_my_list_position(
+      --pending_file_quota_tasks_.end());
+  return pending_file_quota_tasks_.back()->weak_factory_.GetWeakPtr();
+}
+
+void BlobMemoryController::MaybeFreeMemoryQuotaForItems(
+    const std::vector<scoped_refptr<ShareableBlobDataItem>>& items) {
+  base::CheckedNumeric<size_t> memory_to_be_freed = 0;
+  std::unordered_set<uint64_t> visited_items;
+  for (const scoped_refptr<ShareableBlobDataItem>& item : items) {
+    if (!item->HasGrantedQuota())
+      continue;
+    // We only care about bytes items that don't have blobs referencing them,
+    // and we remove duplicates.
+    DataElement::Type type = item->item()->type();
+    if (!item->referencing_blobs().empty() ||
+        (type != DataElement::TYPE_BYTES &&
+         type != DataElement::TYPE_BYTES_DESCRIPTION) ||
+        base::ContainsKey(visited_items, item->item_id()))
+      continue;
+    visited_items.insert(item->item_id());
+    memory_to_be_freed += base::checked_cast<size_t>(item->item()->length());
+    RemoveItemInRecents(*item);
+  }
+  size_t checked_memory = memory_to_be_freed.ValueOrDie();
+  if (checked_memory != 0) {
+    DCHECK_GE(blob_memory_used_, checked_memory);
+    blob_memory_used_ -= checked_memory;
+    MaybeGrantPendingQuotaRequests();
+  }
+}
+
+void BlobMemoryController::ForceFreeMemoryQuotaForItem(
+    const scoped_refptr<ShareableBlobDataItem>& item) {
+  CHECK(item->HasGrantedQuota());
+  size_t size = base::checked_cast<size_t>(item->item()->length());
+  DCHECK_GE(blob_memory_used_, size);
+  blob_memory_used_ -= size;
+  RemoveItemInRecents(*item);
+  MaybeGrantPendingQuotaRequests();
+}
+
+void BlobMemoryController::NotifyMemoryItemUsed(ShareableBlobDataItem* item) {
+  DCHECK_EQ(DataElement::TYPE_BYTES, item->item()->type());
+  DCHECK_EQ(ShareableBlobDataItem::POPULATED_WITH_QUOTA, item->state());
+  // We don't want to re-add the item if we're currently paging it to disk.
+  if (items_saving_to_disk_.find(item->item_id()) !=
+      items_saving_to_disk_.end())
+    return;
+  auto iterator = recent_item_cache_.Get(item->item_id());
+  if (iterator == recent_item_cache_.end()) {
+    recent_item_cache_bytes_ += static_cast<size_t>(item->item()->length());
+    recent_item_cache_.Put(item->item_id(), item);
+    MaybeScheduleEvictionUntilSystemHealthy();
+  }
+}
+
+void BlobMemoryController::RemoveItemInRecents(
+    const ShareableBlobDataItem& item) {
+  auto iterator = recent_item_cache_.Get(item.item_id());
+  if (iterator == recent_item_cache_.end())
+    return;
+  size_t size = base::checked_cast<size_t>(item.item()->length());
+  DCHECK_GE(recent_item_cache_bytes_, size);
+  recent_item_cache_bytes_ -= size;
+  recent_item_cache_.Erase(iterator);
+}
+
+void BlobMemoryController::MaybeGrantPendingQuotaRequests() {
+  while (!pending_memory_quota_tasks_.empty() &&
+         limits_.max_blob_in_memory_space - blob_memory_used_ >=
+             pending_memory_quota_tasks_.front()->allocation_size()) {
+    std::unique_ptr<MemoryQuotaAllocationTask> memory_task =
+        std::move(pending_memory_quota_tasks_.front());
+    pending_memory_quota_tasks_.pop_front();
+    size_t request_size = memory_task->allocation_size();
+    pending_memory_quota_total_size_ -= request_size;
+    blob_memory_used_ += request_size;
+    memory_task->RunDoneCallback(true);
+  }
+  RecordTracingCounters();
+}
+
+size_t BlobMemoryController::CollectItemsForEviction(
+    std::vector<scoped_refptr<ShareableBlobDataItem>>* output) {
+  base::CheckedNumeric<size_t> total_items_size = 0;
+  // Process the recent item list and remove items until we have at least
+  while (total_items_size.ValueOrDie() < limits_.min_page_file_size &&
+         !recent_item_cache_.empty()) {
+    auto iterator = --recent_item_cache_.end();
+    ShareableBlobDataItem* item = iterator->second;
+    DCHECK(item);
+    DCHECK_EQ(item->item()->type(), DataElement::TYPE_BYTES);
+    recent_item_cache_.Erase(iterator);
+    size_t size = base::checked_cast<size_t>(item->item()->length());
+    recent_item_cache_bytes_ -= size;
+    total_items_size += size;
+    output->push_back(make_scoped_refptr(item));
+  }
+  return total_items_size.ValueOrDie();
+}
+
+void BlobMemoryController::MaybeScheduleEvictionUntilSystemHealthy() {
+  // Don't do eviction when others are happening, as we don't change our
+  // pending_memory_quota_total_size_ value until after the paging files have
+  // been written.
+  if (pending_evictions_ != 0 || !file_paging_enabled_)
+    return;
+
+  // We try to page items to disk until our current system size + requested
+  // memory is below our size limit.
+  while (pending_memory_quota_total_size_ + blob_memory_used_ >
+         limits_.max_blob_in_memory_space) {
+    // We only page when we have enough items to fill a whole page file.
+    if (recent_item_cache_bytes_ < limits_.min_page_file_size)
+      break;
+    DCHECK_LE(limits_.min_page_file_size,
+              static_cast<uint64_t>(blob_memory_used_));
+
+    std::vector<scoped_refptr<ShareableBlobDataItem>> items_to_swap;
+    size_t total_items_size = CollectItemsForEviction(&items_to_swap);
+    if (total_items_size == 0)
+      break;
+
+    std::vector<DataElement*> items_for_disk;
+    for (const auto& shared_blob_item : items_to_swap) {
+      items_saving_to_disk_.insert(shared_blob_item->item_id());
+      items_for_disk.push_back(shared_blob_item->item()->data_element_ptr());
+    }
+
+    // Update our bookkeeping.
+    pending_evictions_++;
+    disk_used_ += total_items_size;
+    DCHECK_GE(blob_memory_used_, total_items_size);
+    blob_memory_used_ -= total_items_size;
+    in_flight_memory_used_ += total_items_size;
+
+    // Create our file reference.
+    scoped_refptr<ShareableFileReference> file_reference =
+        ShareableFileReference::GetOrCreate(
+            GenerateNextPageFileName(),
+            ShareableFileReference::DELETE_ON_FINAL_RELEASE,
+            file_runner_.get());
+    // Add the release callback so we decrement our disk usage on file deletion.
+    file_reference->AddFinalReleaseCallback(
+        base::Bind(&BlobMemoryController::OnBlobFileDelete,
+                   weak_factory_.GetWeakPtr(), total_items_size));
+
+    // Post the file writing task.
+    base::PostTaskAndReplyWithResult(
+        file_runner_.get(), FROM_HERE,
+        base::Bind(&CreateFileAndWriteItems, blob_storage_dir_,
+                   file_reference->path(), base::Passed(&items_for_disk),
+                   total_items_size),
+        base::Bind(&BlobMemoryController::OnEvictionComplete,
+                   weak_factory_.GetWeakPtr(), base::Passed(&file_reference),
+                   base::Passed(&items_to_swap), total_items_size));
+  }
+  RecordTracingCounters();
+}
+
+void BlobMemoryController::OnEvictionComplete(
+    scoped_refptr<ShareableFileReference> file_reference,
+    std::vector<scoped_refptr<ShareableBlobDataItem>> items,
+    size_t total_items_size,
+    FileCreationInfo result) {
+  if (!file_paging_enabled_)
+    return;
+
+  if (result.error != File::FILE_OK) {
+    UMA_HISTOGRAM_ENUMERATION("Storage.Blob.PagingError", -result.error,
+                              -File::FILE_ERROR_MAX);
+    disk_used_ -= total_items_size;
+    DisableFilePaging();
+    return;
+  }
+  result.file_reference = std::move(file_reference);
+
+  DCHECK_LT(0u, pending_evictions_);
+  pending_evictions_--;
+
+  // Switch item from memory to the new file.
+  uint64_t offset = 0;
+  for (const scoped_refptr<ShareableBlobDataItem>& shareable_item : items) {
+    scoped_refptr<BlobDataItem> new_item(new BlobDataItem(
+        base::WrapUnique(new DataElement()), result.file_reference));
+    new_item->data_element_ptr()->SetToFilePathRange(
+        result.file_reference->path(), offset, shareable_item->item()->length(),
+        result.last_modified);
+    shareable_item->set_item(new_item);
+    items_saving_to_disk_.erase(shareable_item->item_id());
+    offset += shareable_item->item()->length();
+  }
+  in_flight_memory_used_ -= total_items_size;
+
+  // We want callback on blobs up to the amount we've freed.
+  MaybeGrantPendingQuotaRequests();
+
+  // If we still have more blobs waiting and we're not waiting on more paging
+  // operations, schedule more.
+  MaybeScheduleEvictionUntilSystemHealthy();
+}
+
+FilePath BlobMemoryController::GenerateNextPageFileName() {
+  std::string file_name = base::Uint64ToString(current_file_num_++);
+  return blob_storage_dir_.Append(file_name);
+}
+
+void BlobMemoryController::RecordTracingCounters() const {
+  TRACE_COUNTER2("Blob", "MemoryUsage", "RegularStorage", blob_memory_used_,
+                 "InFlightToDisk", in_flight_memory_used_);
+  TRACE_COUNTER1("Blob", "DiskUsage", disk_used_);
+  TRACE_COUNTER1("Blob", "TranfersPendingOnDisk",
+                 pending_memory_quota_tasks_.size());
+  TRACE_COUNTER1("Blob", "TranfersBytesPendingOnDisk",
+                 pending_memory_quota_total_size_);
+}
+
+size_t BlobMemoryController::GetAvailableMemoryForBlobs() const {
+  if (limits_.total_memory_space() < memory_usage())
+    return 0;
+  return limits_.total_memory_space() - memory_usage();
+}
+
+uint64_t BlobMemoryController::GetAvailableFileSpaceForBlobs() const {
+  if (!file_paging_enabled_)
+    return 0;
+  return limits_.max_blob_disk_space - disk_used_ -
+         pending_memory_quota_total_size_;
+}
+
+void BlobMemoryController::OnBlobFileDelete(uint64_t size,
+                                            const FilePath& path) {
+  DCHECK_LE(size, disk_used_);
+  disk_used_ -= size;
+}
+
+}  // namespace storage