android: add ThumbnailCache

chrome/browser/android/thumbnail/thumbnail_cache.cc

+// Copyright 2014 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 "chrome/browser/android/thumbnail/thumbnail_cache.h"
+
+#include <algorithm>
+#include <cmath>
+
+#include "base/file_util.h"
+#include "base/files/file.h"
+#include "base/files/file_enumerator.h"
+#include "base/files/file_path.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/time/time.h"
+#include "content/public/browser/android/ui_resource_provider.h"
+#include "content/public/browser/browser_thread.h"
+#include "third_party/skia/include/core/SkBitmap.h"
+#include "third_party/skia/include/core/SkCanvas.h"
+#include "ui/gfx/geometry/size_conversions.h"
+
+namespace {
+
+const bool kDropCachedNTPOnLowMemory = true;
+const float kApproximationScaleFactor = 4.f;
+const base::TimeDelta kCaptureMinRequestTimeMs(
+    base::TimeDelta::FromMilliseconds(1000));
+
+}  // anonymous namespace
+
+ThumbnailCache::ThumbnailCache(const std::string& disk_cache_path_str,
+                               size_t default_cache_size,
+                               size_t approximation_cache_size,
+                               size_t compression_queue_max_size,
+                               size_t write_queue_max_size,
+                               bool use_approximation_thumbnail)
+    : disk_cache_path_(disk_cache_path_str),
+      compression_queue_max_size_(compression_queue_max_size),
+      write_queue_max_size_(write_queue_max_size),
+      use_approximation_thumbnail_(use_approximation_thumbnail),
+      cache_(default_cache_size),
+      approximation_cache_(approximation_cache_size),
+      ui_resource_provider_(NULL),
+      compression_thread_("thumbnail_compression"),
+      weak_factory_(this) {
+  compression_thread_.Start();
+}
+
+ThumbnailCache::~ThumbnailCache() {
+  compression_thread_.Stop();
+  SetUIResourceProvider(NULL);
+}
+
+void ThumbnailCache::SetUIResourceProvider(
+    content::UIResourceProvider* ui_resource_provider) {
+  if (ui_resource_provider_ == ui_resource_provider)
+    return;
+
+  approximation_cache_.Clear();
+  cache_.Clear();
+
+  ui_resource_provider_ = ui_resource_provider;
+}
+
+void ThumbnailCache::AddThumbnailCacheObserver(
+    ThumbnailCacheObserver* observer) {
+  if (!observers_.HasObserver(observer))
+    observers_.AddObserver(observer);
+}
+
+void ThumbnailCache::RemoveThumbnailCacheObserver(
+    ThumbnailCacheObserver* observer) {
+  if (observers_.HasObserver(observer))
+    observers_.RemoveObserver(observer);
+}
+
+void ThumbnailCache::Put(TabId tab_id,
+                         const SkBitmap& bitmap,
+                         float thumbnail_scale) {
+  if (!ui_resource_provider_ || bitmap.empty() || thumbnail_scale <= 0)
+    return;
+
+  scoped_refptr<ThumbnailImpl> thumbnail = make_scoped_refptr(new ThumbnailImpl(
+      tab_id, bitmap, thumbnail_scale, this, ui_resource_provider_));
+
+  RemoveFromQueues(tab_id);
+  MakeSpaceForNewItemIfNecessary(tab_id);
+  cache_.Put(tab_id, thumbnail);
+
+  if (use_approximation_thumbnail_) {
+    std::pair<SkBitmap, float> approximation =
+        CreateApproximation(bitmap, thumbnail_scale);
+    scoped_refptr<ThumbnailImpl> approx_thumbnail =
+        make_scoped_refptr(new ThumbnailImpl(tab_id,
+                                             approximation.first,
+                                             approximation.second,
+                                             this,
+                                             ui_resource_provider_));
+    approximation_cache_.Put(tab_id, approx_thumbnail);
+  }
+
+  CompressThumbnailIfNecessary(thumbnail);
+}
+
+void ThumbnailCache::Remove(TabId tab_id) {
+  cache_.Remove(tab_id);
+  approximation_cache_.Remove(tab_id);
+  thumbnail_meta_data_.erase(tab_id);
+  RemoveFileFromDisk(GetFilePath(tab_id));
+  RemoveFromQueues(tab_id);
+}
+
+scoped_refptr<Thumbnail> ThumbnailCache::Get(TabId tab_id) {
+  scoped_refptr<ThumbnailImpl> thumbnail = cache_.Get(tab_id);
+  if (!thumbnail)
+    thumbnail = approximation_cache_.Get(tab_id);
+
+  // If we are trying to find a thumbnail that is not in memory cache and yet is
+  // visible, then try paging it in from disk.
+  if (!thumbnail &&
+      std::find(visible_ids_.begin(), visible_ids_.end(), tab_id) !=
+          visible_ids_.end() &&
+      std::find(read_queue_.begin(), read_queue_.end(), tab_id) ==
+          read_queue_.end()) {
+    read_queue_.push_back(tab_id);
+    ReadNextThumbnail();
+  }
+  return thumbnail;
+}
+
+void ThumbnailCache::RemoveFromDiskAtAndAboveId(TabId min_id) {
+  base::Closure remove_task =
+      base::Bind(&ThumbnailCache::RemoveFromDiskAtAndAboveIdTask,
+                 disk_cache_path_,
+                 min_id);
+  content::BrowserThread::PostTask(
+      content::BrowserThread::FILE, FROM_HERE, remove_task);
+}
+
+void ThumbnailCache::InvalidateThumbnailIfChanged(TabId tab_id,
+                                                  const GURL& url) {
+  ThumbnailMetaDataMap::iterator meta_data_iter =
+      thumbnail_meta_data_.find(tab_id);
+  if (meta_data_iter == thumbnail_meta_data_.end()) {
+    thumbnail_meta_data_[tab_id] = ThumbnailMetaData(base::Time(), url);
+  } else if (meta_data_iter->second.url() != url) {
+    Remove(tab_id);
+  }
+}
+
+bool ThumbnailCache::CheckAndUpdateThumbnailMetaData(TabId tab_id,
+                                                     const GURL& url) {
+  ThumbnailMetaDataMap::iterator meta_data_iter =
+      thumbnail_meta_data_.find(tab_id);
+  if (meta_data_iter != thumbnail_meta_data_.end() &&
+      meta_data_iter->second.url() == url &&
+      (CurrentTime() - meta_data_iter->second.capture_time()) <
+          kCaptureMinRequestTimeMs) {
+    return false;
+  }
+
+  thumbnail_meta_data_[tab_id] = ThumbnailMetaData(CurrentTime(), url);
+  return true;
+}
+
+void ThumbnailCache::UpdateVisibleIds(const TabIdList& priority) {
+  if (priority.empty()) {
+    visible_ids_.clear();
+    return;
+  }
+
+  size_t ids_size = std::min(priority.size(), cache_.MaximumCacheSize());
+  if (visible_ids_.size() == ids_size) {
+    // Early out if called with the same input as last time (We only care
+    // about the first mCache.MaximumCacheSize() entries).
+    bool lists_differ = false;
+    for (TabIdList::const_iterator visible_iter = visible_ids_.begin(),

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

A while loop might look a bit cleaner.

[powei, 2014/06/19 23:05:59]

Done.

+                                   priority_iter = priority.begin();
+         visible_iter != visible_ids_.end() && priority_iter != priority.end();
+         visible_iter++, priority_iter++) {
+      if (*priority_iter != *visible_iter) {
+        lists_differ = true;
+        break;
+      }
+    }
+    if (!lists_differ)
+      return;
+  }
+
+  read_queue_.clear();
+  visible_ids_.clear();
+  size_t count = 0;
+  for (TabIdList::const_iterator iter = priority.begin();
+       iter != priority.end() && count < ids_size;
+       iter++, count++) {
+    TabId tab_id = *iter;
+    visible_ids_.push_back(tab_id);
+    if (!cache_.Get(tab_id) &&
+        std::find(read_queue_.begin(), read_queue_.end(), tab_id) ==

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Is this to check if the same id is in the list twice?

[powei, 2014/06/19 23:05:59]

Yes it is.  We probably don't need this if we're sure that ids in |priority| are
unique.  Removed.

+            read_queue_.end()) {
+      read_queue_.push_back(tab_id);
+    }
+  }
+
+  ReadNextThumbnail();
+}
+
+void ThumbnailCache::RemoveFileFromDisk(const base::FilePath& file_path) {
+  base::Closure task =
+      base::Bind(&ThumbnailCache::RemoveFileFromDiskTask, file_path);
+  content::BrowserThread::PostTask(
+      content::BrowserThread::FILE, FROM_HERE, task);
+}
+
+void ThumbnailCache::RemoveFileFromDiskTask(const base::FilePath& file_path) {
+  base::DeleteFile(file_path, false);
+}
+
+void ThumbnailCache::RemoveFromDiskAtAndAboveIdTask(
+    const base::FilePath& dir_path,
+    TabId min_id) {
+  base::FileEnumerator enumerator(dir_path, false, base::FileEnumerator::FILES);
+  while (true) {
+    base::FilePath path = enumerator.Next();
+    if (path.empty())
+      break;
+    base::FileEnumerator::FileInfo info = enumerator.GetInfo();
+    TabId tab_id;
+    bool success = base::StringToInt(info.GetName().value(), &tab_id);
+    if (success && tab_id >= min_id)
+      base::DeleteFile(path, false);
+  }
+}
+
+void ThumbnailCache::WriteThumbnailIfNecessary(
+    scoped_refptr<ThumbnailImpl> thumbnail) {
+  RemoveDuplicateIdsFromQueueHelper(write_queue_, thumbnail);
+  if (write_queue_.size() > write_queue_max_size_)
+    write_queue_.pop_front();
+
+  write_queue_.push_back(thumbnail);
+  WriteNextThumbnail();
+}
+
+void ThumbnailCache::CompressThumbnailIfNecessary(
+    scoped_refptr<ThumbnailImpl> thumbnail) {
+  RemoveDuplicateIdsFromQueueHelper(compression_queue_, thumbnail);
+  if (compression_queue_.size() > compression_queue_max_size_)
+    compression_queue_.pop_front();
+
+  compression_queue_.push_back(thumbnail);
+  CompressNextThumbnail();
+}
+
+void ThumbnailCache::MakeSpaceForNewItemIfNecessary(TabId tab_id) {
+  if (cache_.Get(tab_id) ||
+      std::find(visible_ids_.begin(), visible_ids_.end(), tab_id) ==
+          visible_ids_.end() ||
+      cache_.size() < cache_.MaximumCacheSize()) {
+    return;
+  }
+
+  TabId key_to_remove;
+  bool found_key_to_remove = false;
+
+  // 1. Find a cached item not in this list
+  for (ExpiringThumbnailCache::iterator iter = cache_.begin();
+       iter != cache_.end();
+       iter++) {
+    if (std::find(visible_ids_.begin(), visible_ids_.end(), iter->first) ==
+        visible_ids_.end()) {
+      key_to_remove = iter->first;
+      found_key_to_remove = true;
+      break;
+    }
+  }
+
+  if (!found_key_to_remove) {
+    // 2. Find the least important id we can remove.
+    for (TabIdList::reverse_iterator riter = visible_ids_.rbegin();
+         riter != visible_ids_.rend();
+         riter++) {
+      if (cache_.Get(*riter)) {
+        key_to_remove = *riter;
+        break;
+        found_key_to_remove = true;
+      }
+    }
+  }
+
+  if (found_key_to_remove)
+    cache_.Remove(key_to_remove);
+}
+
+void ThumbnailCache::RemoveFromQueues(TabId tab_id) {
+  TabIdList::iterator read_iter =
+      std::find(read_queue_.begin(), read_queue_.end(), tab_id);
+  if (read_iter != read_queue_.end())
+    read_queue_.erase(read_iter);
+
+  ThumbnailQueue new_write_queue;
+  for (ThumbnailQueue::iterator iter = write_queue_.begin();
+       iter != write_queue_.end();
+       iter++) {
+    scoped_refptr<ThumbnailImpl> write_thumbnail = *iter;
+    if (write_thumbnail->tab_id() != tab_id)

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Why not if (==) iter.remove()?  Same below and for
RemoveDuplicateIdsFromQueueHelper

[powei, 2014/06/19 23:05:59]

Done. changed to "iter = write_queue_.erase(iter);"

+      new_write_queue.push_back(write_thumbnail);
+  }
+  write_queue_ = new_write_queue;
+
+  ThumbnailQueue new_compression_queue;
+  for (ThumbnailQueue::iterator iter = compression_queue_.begin();
+       iter != compression_queue_.end();
+       iter++) {
+    scoped_refptr<ThumbnailImpl> compress_thumbnail = *iter;
+    if (compress_thumbnail->tab_id() != tab_id)
+      new_compression_queue.push_back(compress_thumbnail);
+  }
+  compression_queue_ = new_compression_queue;
+}
+
+bool ThumbnailCache::RemoveDuplicateIdsFromQueueHelper(
+    ThumbnailQueue& queue,
+    scoped_refptr<ThumbnailImpl> thumbnail) {
+  bool found = false;
+  ThumbnailQueue::iterator iter = queue.begin();
+  ThumbnailQueue good_queue;
+  for (ThumbnailQueue::iterator iter = queue.begin(); iter != queue.end();
+       iter++) {
+    if ((*iter)->tab_id() != thumbnail->tab_id()) {
+      good_queue.push_back(thumbnail);
+    } else {
+      found = true;
+    }
+  }
+  queue = good_queue;
+  return found;
+}
+
+void ThumbnailCache::InvalidateCachedThumbnail(
+    scoped_refptr<ThumbnailImpl> thumbnail) {
+  TabId tab_id = thumbnail->tab_id();
+  if (cache_.Get(tab_id) == thumbnail)
+    cache_.Remove(tab_id);
+
+  if (approximation_cache_.Get(tab_id) == thumbnail)
+    approximation_cache_.Remove(tab_id);
+}
+
+base::FilePath ThumbnailCache::GetFilePath(TabId tab_id) const {
+  return disk_cache_path_.Append(base::IntToString(tab_id));
+}
+
+base::Time ThumbnailCache::CurrentTime() {
+  return base::Time::Now();
+}
+
+void ThumbnailCache::WriteNextThumbnail() {

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

What if we're already waiting for a write to finish?  Also (not sure if other
version handled this) what if the thumbail should be removed (tab closed) during
the write task?  I assume the delete task will be queued behind this?

[powei, 2014/06/19 23:05:59]

Are you thinking about how the size of the write_queue_ does not reflect the
number of write tasks in-flight?  Maybe I can add a count of the currently
in-flight write-tasks.  So then the block in WriteThumbnailIfNecessary() would
be

if (write_queue_.size() + executing_write_task_count_ > write_queue_max_size_)
  return;

or something similar.

The delete task is posted to the same FILE thread.  So delete and write tasks
are sequenced.

[David Trainor- moved to gerrit, 2014/06/25 07:40:15]

I'm more worried that we have a write queue that doesn't really represent what's
actually queued up.  The idea of the queue was that we don't write more than one
thing at a time.  Can this queue ever be non-empty?  It looks like we just push
stuff on the queue and immediately pop it and post the task to the IO thread.

Then we also need to look at how easy/hard it is to cancel write tasks if we
need to (ie: how would we cancel a pending write task if the tab was closed
after we grabbed a thumbnail?  how would we clean that up if we hit that
somewhat common case?).

[powei, 2014/07/07 17:24:51]

Agreed offline that we'd keep a count instead of an actual queue.  Canceling is
tabled fo rnow.

+  if (write_queue_.empty())
+    return;
+
+  scoped_refptr<ThumbnailImpl> thumbnail = write_queue_.front();
+  write_queue_.pop_front();
+
+  if (!thumbnail->IsValid())
+    return;
+
+  scoped_refptr<ThumbnailImpl> in_thumbnail =
+      thumbnail->PassDataToNewThumbnail();

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Won't this steal the reference from the object in the cache?  Also, why are we
passing a new instance of this in here?  The class should be thread safe or we
should just pass the ref counted pixel data.

[powei, 2014/06/19 23:05:58]

The point is to steal the reference.  This way we're sure about the lifetime of
the pixels.  After the |in_thumbnail| is written it goes out of scope and the
pixels are gone.

[David Trainor- moved to gerrit, 2014/06/25 07:40:16]

But since we're building the ui resource id on demand who's to say the
ThumnailImpl in the cache doesn't need those pixels?

1. cache_->put(new ThumbnailImpl);
2. WriteTask()
3. cache_->get() (pixels dead, need to build the ui resource id).

[powei, 2014/07/07 17:24:51]

Done. Moved to more explicit passing of ref-counted pixels.

+
+  base::Closure write_task = base::Bind(&ThumbnailCache::WriteTask,
+                                        in_thumbnail,
+                                        GetFilePath(thumbnail->tab_id()));
+  base::Closure post_write_task = base::Bind(
+      &ThumbnailCache::WriteNextThumbnail, weak_factory_.GetWeakPtr());
+
+  content::BrowserThread::PostTaskAndReply(
+      content::BrowserThread::FILE, FROM_HERE, write_task, post_write_task);
+}
+
+void ThumbnailCache::WriteTask(scoped_refptr<ThumbnailImpl> thumbnail,
+                               const base::FilePath& file_path) {
+  DCHECK(thumbnail);
+  DCHECK(thumbnail->IsValid());
+
+  base::File file(file_path,
+                  base::File::FLAG_CREATE_ALWAYS | base::File::FLAG_WRITE);
+  bool success = ThumbnailImpl::WriteToFile(thumbnail, file);
+  file.Close();
+
+  if (!success)
+    RemoveFileFromDisk(file_path);

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Is posting this safe?  What if the app dies before this task runs?  Then we have
an invalid file on disk.  Since we're already on the FILE thread can we just
delete it here?

[powei, 2014/06/19 23:05:59]

Done.  Good catch.  called DeleteFile directly instead of posting.

+}
+
+void ThumbnailCache::ReadNextThumbnail() {
+  if (read_queue_.empty())
+    return;
+
+  TabId tab_id = read_queue_.front();
+
+  // Create an empty thumbnail to hold the content of the read.
+  scoped_refptr<ThumbnailImpl> output_thumbnail = make_scoped_refptr(
+      new ThumbnailImpl(tab_id, SkBitmap(), 0.f, this, ui_resource_provider_));
+
+  base::FilePath file_path = GetFilePath(tab_id);
+  base::Closure read_task =
+      base::Bind(&ThumbnailCache::ReadTask, file_path, output_thumbnail);
+  base::Closure post_read_task = base::Bind(&ThumbnailCache::PostReadTask,
+                                            weak_factory_.GetWeakPtr(),
+                                            output_thumbnail);
+  content::BrowserThread::PostTaskAndReply(
+      content::BrowserThread::FILE, FROM_HERE, read_task, post_read_task);
+}
+
+void ThumbnailCache::ReadTask(const base::FilePath& file_path,
+                              scoped_refptr<ThumbnailImpl> thumbnail) {
+  DCHECK(thumbnail);
+  if (!base::PathExists(file_path))
+    return;
+
+  base::File file(file_path, base::File::FLAG_OPEN | base::File::FLAG_READ);
+  DCHECK(file.IsValid());
+  bool success = ThumbnailImpl::ReadFromFile(file, thumbnail);
+  file.Close();
+
+  if (!success)
+    RemoveFileFromDisk(file_path);
+}
+
+void ThumbnailCache::PostReadTask(scoped_refptr<ThumbnailImpl> thumbnail) {
+  DCHECK(thumbnail);
+  TabIdList::iterator iter =
+      std::find(read_queue_.begin(), read_queue_.end(), thumbnail->tab_id());
+  if (iter == read_queue_.end())
+    return;
+
+  read_queue_.erase(iter);
+  TabId tab_id = thumbnail->tab_id();
+  MakeSpaceForNewItemIfNecessary(tab_id);
+  cache_.Put(tab_id, thumbnail);
+  NotifyObserversOfThumbnailRead(tab_id);
+  ReadNextThumbnail();
+}
+
+void ThumbnailCache::CompressNextThumbnail() {

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Shouldn't this queue up the tasks and only run one at once?  Otherwise what's
the point of the compression_queue_/size limit/the ability to cancel stuff
that's waiting to be compressed?

[powei, 2014/06/19 23:05:59]

see comment for write task.

+  if (!compression_queue_.empty()) {
+    scoped_refptr<ThumbnailImpl> thumbnail = compression_queue_.front();
+    compression_queue_.pop_front();
+
+    scoped_refptr<ThumbnailImpl> in_thumbnail =
+        thumbnail->PassDataToNewThumbnail();

[David Trainor- moved to gerrit, 2014/06/17 08:12:11]

Doesn't this also steal the bitmap/data from the thumbnail in the cache?

[powei, 2014/06/19 23:05:59]

This does steal the reference, and once compression is complete, the reference
goes out of scope and pixels are gone.

[David Trainor- moved to gerrit, 2014/06/25 07:40:15]

Still not sure how this works if we compress before building the resource id.

+
+    scoped_refptr<ThumbnailImpl> out_thumbnail =
+        scoped_refptr<ThumbnailImpl>(new ThumbnailImpl(in_thumbnail->tab_id(),
+                                                       SkBitmap(),
+                                                       0.f,
+                                                       this,
+                                                       ui_resource_provider_));
+    base::Closure compression_task =
+        base::Bind(&ThumbnailImpl::Compress, in_thumbnail, out_thumbnail);
+    base::Closure post_compression_task =
+        base::Bind(&ThumbnailCache::PostCompressionTask,
+                   weak_factory_.GetWeakPtr(),
+                   out_thumbnail);
+
+    DCHECK(compression_thread_.message_loop_proxy());
+    compression_thread_.message_loop_proxy()->PostTaskAndReply(
+        FROM_HERE, compression_task, post_compression_task);
+  }
+}
+
+void ThumbnailCache::PostCompressionTask(
+    scoped_refptr<ThumbnailImpl> compressed_thumbnail) {
+  DCHECK(compressed_thumbnail);
+  TabId tab_id = compressed_thumbnail->tab_id();
+  cache_.Remove(tab_id);
+  if (compressed_thumbnail->IsValid()) {
+    cache_.Put(tab_id, compressed_thumbnail);
+    WriteThumbnailIfNecessary(compressed_thumbnail);
+  }
+  CompressNextThumbnail();
+}
+
+void ThumbnailCache::NotifyObserversOfThumbnailRead(TabId tab_id) {
+  FOR_EACH_OBSERVER(
+      ThumbnailCacheObserver, observers_, OnFinishedThumbnailRead(tab_id));
+}
+
+ThumbnailCache::ThumbnailMetaData::ThumbnailMetaData() {
+}
+
+ThumbnailCache::ThumbnailMetaData::ThumbnailMetaData(
+    const base::Time& current_time,
+    const GURL& url)
+    : capture_time_(current_time), url_(url) {
+}
+
+std::pair<SkBitmap, float> ThumbnailCache::CreateApproximation(
+    const SkBitmap& bitmap,
+    float scale) {
+  DCHECK(!bitmap.empty());
+  DCHECK_GT(scale, 0);
+  SkAutoLockPixels bitmap_lock(bitmap);
+  float new_scale = 1.f / kApproximationScaleFactor;
+
+  gfx::Size dst_size = gfx::ToFlooredSize(
+      gfx::ScaleSize(gfx::Size(bitmap.width(), bitmap.height()), new_scale));
+  SkBitmap dst_bitmap;
+  dst_bitmap.setConfig(bitmap.getConfig(), dst_size.width(), dst_size.height());
+  dst_bitmap.allocPixels();
+  dst_bitmap.eraseColor(0);
+  SkAutoLockPixels dst_bitmap_lock(dst_bitmap);
+
+  SkCanvas canvas(dst_bitmap);
+  canvas.scale(new_scale, new_scale);
+  canvas.drawBitmap(bitmap, 0, 0, NULL);
+  dst_bitmap.setImmutable();
+
+  return std::make_pair(dst_bitmap, new_scale * scale);
+}