cc/tiles/software_image_decode_cache.cc

// Copyright 2015 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 "cc/tiles/software_image_decode_cache.h"

#include <inttypes.h>
#include <stdint.h>

#include <algorithm>
#include <functional>

#include "base/format_macros.h"
#include "base/macros.h"
#include "base/memory/discardable_memory.h"
#include "base/memory/memory_coordinator_client_registry.h"
#include "base/memory/ptr_util.h"
#include "base/metrics/histogram_macros.h"
#include "base/strings/stringprintf.h"
#include "base/threading/thread_task_runner_handle.h"
#include "base/trace_event/memory_dump_manager.h"
#include "cc/debug/devtools_instrumentation.h"
#include "cc/raster/tile_task.h"
#include "cc/resources/resource_format_utils.h"
#include "cc/tiles/mipmap_util.h"
#include "third_party/skia/include/core/SkCanvas.h"
#include "third_party/skia/include/core/SkImage.h"
#include "third_party/skia/include/core/SkPixmap.h"
#include "ui/gfx/skia_util.h"

using base::trace_event::MemoryAllocatorDump;
using base::trace_event::MemoryDumpLevelOfDetail;

namespace cc {
namespace {

// The largest single high quality image to try and process. Images above this
// size will drop down to medium quality.
const size_t kMaxHighQualityImageSizeBytes = 64 * 1024 * 1024;

// The number of entries to keep around in the cache. This limit can be breached
// if more items are locked. That is, locked items ignore this limit.
// Depending on the memory state of the system, we limit the amount of items
// differently.
const size_t kNormalMaxItemsInCache = 1000;
const size_t kThrottledMaxItemsInCache = 100;
const size_t kSuspendedMaxItemsInCache = 0;

// If the size of the original sized image breaches kMemoryRatioToSubrect but we
// don't need to scale the image, consider caching only the needed subrect.
// The second part that much be true is that we cache only the needed subrect if
// the total size needed for the subrect is at most kMemoryRatioToSubrect *
// (size needed for the full original image).
// Note that at least one of the dimensions has to be at least
// kMinDimensionToSubrect before an image can breach the threshold.
const size_t kMemoryThresholdToSubrect = 64 * 1024 * 1024;
const int kMinDimensionToSubrect = 4 * 1024;
const float kMemoryRatioToSubrect = 0.5f;

class AutoRemoveKeyFromTaskMap {
 public:
  AutoRemoveKeyFromTaskMap(
      std::unordered_map<SoftwareImageDecodeCache::ImageKey,
                         scoped_refptr<TileTask>,
                         SoftwareImageDecodeCache::ImageKeyHash>* task_map,
      const SoftwareImageDecodeCache::ImageKey& key)
      : task_map_(task_map), key_(key) {}
  ~AutoRemoveKeyFromTaskMap() { task_map_->erase(key_); }

 private:
  std::unordered_map<SoftwareImageDecodeCache::ImageKey,
                     scoped_refptr<TileTask>,
                     SoftwareImageDecodeCache::ImageKeyHash>* task_map_;
  const SoftwareImageDecodeCache::ImageKey& key_;
};

class AutoDrawWithImageFinished {
 public:
  AutoDrawWithImageFinished(SoftwareImageDecodeCache* cache,
                            const DrawImage& draw_image,
                            const DecodedDrawImage& decoded_draw_image)
      : cache_(cache),
        draw_image_(draw_image),
        decoded_draw_image_(decoded_draw_image) {}
  ~AutoDrawWithImageFinished() {
    cache_->DrawWithImageFinished(draw_image_, decoded_draw_image_);
  }

 private:
  SoftwareImageDecodeCache* cache_;
  const DrawImage& draw_image_;
  const DecodedDrawImage& decoded_draw_image_;
};

class ImageDecodeTaskImpl : public TileTask {
 public:
  ImageDecodeTaskImpl(SoftwareImageDecodeCache* cache,
                      const SoftwareImageDecodeCache::ImageKey& image_key,
                      const DrawImage& image,
                      SoftwareImageDecodeCache::DecodeTaskType task_type,
                      const ImageDecodeCache::TracingInfo& tracing_info)
      : TileTask(true),
        cache_(cache),
        image_key_(image_key),
        image_(image),
        task_type_(task_type),
        tracing_info_(tracing_info) {}

  // Overridden from Task:
  void RunOnWorkerThread() override {
    TRACE_EVENT2("cc", "ImageDecodeTaskImpl::RunOnWorkerThread", "mode",
                 "software", "source_prepare_tiles_id",
                 tracing_info_.prepare_tiles_id);
    devtools_instrumentation::ScopedImageDecodeTask image_decode_task(
        image_.image().get(),
        devtools_instrumentation::ScopedImageDecodeTask::SOFTWARE);
    cache_->DecodeImage(image_key_, image_, task_type_);
  }

  // Overridden from TileTask:
  void OnTaskCompleted() override {
    cache_->RemovePendingTask(image_key_, task_type_);
  }

 protected:
  ~ImageDecodeTaskImpl() override {}

 private:
  SoftwareImageDecodeCache* cache_;
  SoftwareImageDecodeCache::ImageKey image_key_;
  DrawImage image_;
  SoftwareImageDecodeCache::DecodeTaskType task_type_;
  const ImageDecodeCache::TracingInfo tracing_info_;

  DISALLOW_COPY_AND_ASSIGN(ImageDecodeTaskImpl);
};

SkSize GetScaleAdjustment(const ImageDecodeCacheKey& key) {
  // If the requested filter quality did not require scale, then the adjustment
  // is identity.
  if (key.can_use_original_decode() || key.should_use_subrect()) {
    return SkSize::Make(1.f, 1.f);
  } else if (key.filter_quality() == kMedium_SkFilterQuality) {
    return MipMapUtil::GetScaleAdjustmentForSize(key.src_rect().size(),
                                                 key.target_size());
  } else {
    float x_scale =
        key.target_size().width() / static_cast<float>(key.src_rect().width());
    float y_scale = key.target_size().height() /
                    static_cast<float>(key.src_rect().height());
    return SkSize::Make(x_scale, y_scale);
  }
}

SkFilterQuality GetDecodedFilterQuality(const ImageDecodeCacheKey& key) {
  return std::min(key.filter_quality(), kLow_SkFilterQuality);
}

SkImageInfo CreateImageInfo(size_t width,
                            size_t height,
                            ResourceFormat format) {
  return SkImageInfo::Make(width, height,
                           ResourceFormatToClosestSkColorType(format),
                           kPremul_SkAlphaType);
}

void RecordLockExistingCachedImageHistogram(TilePriority::PriorityBin bin,
                                            bool success) {
  switch (bin) {
    case TilePriority::NOW:
      UMA_HISTOGRAM_BOOLEAN("Renderer4.LockExistingCachedImage.Software.NOW",
                            success);
    case TilePriority::SOON:
      UMA_HISTOGRAM_BOOLEAN("Renderer4.LockExistingCachedImage.Software.SOON",
                            success);
    case TilePriority::EVENTUALLY:
      UMA_HISTOGRAM_BOOLEAN(
          "Renderer4.LockExistingCachedImage.Software.EVENTUALLY", success);
  }
}

gfx::Rect GetSrcRect(const DrawImage& image) {
  const SkIRect& src_rect = image.src_rect();
  int x = std::max(0, src_rect.x());
  int y = std::max(0, src_rect.y());
  int right = std::min(image.image()->width(), src_rect.right());
  int bottom = std::min(image.image()->height(), src_rect.bottom());
  if (x >= right || y >= bottom)
    return gfx::Rect();
  return gfx::Rect(x, y, right - x, bottom - y);
}

}  // namespace

SoftwareImageDecodeCache::SoftwareImageDecodeCache(
    ResourceFormat format,
    size_t locked_memory_limit_bytes)
    : decoded_images_(ImageMRUCache::NO_AUTO_EVICT),
      at_raster_decoded_images_(ImageMRUCache::NO_AUTO_EVICT),
      locked_images_budget_(locked_memory_limit_bytes),
      format_(format),
      max_items_in_cache_(kNormalMaxItemsInCache) {
  // In certain cases, ThreadTaskRunnerHandle isn't set (Android Webview).
  // Don't register a dump provider in these cases.
  if (base::ThreadTaskRunnerHandle::IsSet()) {
    base::trace_event::MemoryDumpManager::GetInstance()->RegisterDumpProvider(
        this, "cc::SoftwareImageDecodeCache",
        base::ThreadTaskRunnerHandle::Get());
  }
  // Register this component with base::MemoryCoordinatorClientRegistry.
  base::MemoryCoordinatorClientRegistry::GetInstance()->Register(this);
}

SoftwareImageDecodeCache::~SoftwareImageDecodeCache() {
  // Debugging crbug.com/650234
  CHECK_EQ(0u, decoded_images_ref_counts_.size());
  CHECK_EQ(0u, at_raster_decoded_images_ref_counts_.size());

  // It is safe to unregister, even if we didn't register in the constructor.
  base::trace_event::MemoryDumpManager::GetInstance()->UnregisterDumpProvider(
      this);
  // Unregister this component with memory_coordinator::ClientRegistry.
  base::MemoryCoordinatorClientRegistry::GetInstance()->Unregister(this);
}

bool SoftwareImageDecodeCache::GetTaskForImageAndRef(
    const DrawImage& image,
    const TracingInfo& tracing_info,
    scoped_refptr<TileTask>* task) {
  return GetTaskForImageAndRefInternal(
      image, tracing_info, DecodeTaskType::USE_IN_RASTER_TASKS, task);
}

bool SoftwareImageDecodeCache::GetOutOfRasterDecodeTaskForImageAndRef(
    const DrawImage& image,
    scoped_refptr<TileTask>* task) {
  return GetTaskForImageAndRefInternal(
      image, TracingInfo(), DecodeTaskType::USE_OUT_OF_RASTER_TASKS, task);
}

bool SoftwareImageDecodeCache::GetTaskForImageAndRefInternal(
    const DrawImage& image,
    const TracingInfo& tracing_info,
    DecodeTaskType task_type,
    scoped_refptr<TileTask>* task) {
  // If the image already exists or if we're going to create a task for it, then
  // we'll likely need to ref this image (the exception is if we're prerolling
  // the image only). That means the image is or will be in the cache. When the
  // ref goes to 0, it will be unpinned but will remain in the cache. If the
  // image does not fit into the budget, then we don't ref this image, since it
  // will be decoded at raster time which is when it will be temporarily put in
  // the cache.
  ImageKey key = ImageKey::FromDrawImage(image);
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::GetTaskForImageAndRef", "key",
               key.ToString());

  // If the target size is empty, we can skip this image during draw (and thus
  // we don't need to decode it or ref it).
  if (key.target_size().IsEmpty()) {
    *task = nullptr;
    return false;
  }

  base::AutoLock lock(lock_);

  // If we already have the image in cache, then we can return it.
  auto decoded_it = decoded_images_.Get(key);
  bool new_image_fits_in_memory =
      locked_images_budget_.AvailableMemoryBytes() >= key.locked_bytes();
  if (decoded_it != decoded_images_.end()) {
    bool image_was_locked = decoded_it->second->is_locked();
    if (image_was_locked ||
        (new_image_fits_in_memory && decoded_it->second->Lock())) {
      RefImage(key);
      *task = nullptr;
      SanityCheckState(__LINE__, true);

      // If the image wasn't locked, then we just succeeded in locking it.
      if (!image_was_locked) {
        RecordLockExistingCachedImageHistogram(tracing_info.requesting_tile_bin,
                                               true);
      }
      return true;
    }

    // If the image fits in memory, then we at least tried to lock it and
    // failed. This means that it's not valid anymore.
    if (new_image_fits_in_memory) {
      RecordLockExistingCachedImageHistogram(tracing_info.requesting_tile_bin,
                                             false);
      decoded_images_.Erase(decoded_it);
    }
  }

  DCHECK(task_type == DecodeTaskType::USE_IN_RASTER_TASKS ||
         task_type == DecodeTaskType::USE_OUT_OF_RASTER_TASKS);
  // If the task exists, return it. Note that if we always need to create a new
  // task, then just set |existing_task| to reference the passed in task (which
  // is set to nullptr above).
  scoped_refptr<TileTask>& existing_task =
      (task_type == DecodeTaskType::USE_IN_RASTER_TASKS)
          ? pending_in_raster_image_tasks_[key]
          : pending_out_of_raster_image_tasks_[key];
  if (existing_task) {
    RefImage(key);
    *task = existing_task;
    SanityCheckState(__LINE__, true);
    return true;
  }

  // At this point, we have to create a new image/task, so we need to abort if
  // it doesn't fit into memory and there are currently no raster tasks that
  // would have already accounted for memory. The latter part is possible if
  // there's a running raster task that could not be canceled, and still has a
  // ref to the image that is now being reffed for the new schedule.
  if (!new_image_fits_in_memory && (decoded_images_ref_counts_.find(key) ==
                                    decoded_images_ref_counts_.end())) {
    *task = nullptr;
    SanityCheckState(__LINE__, true);
    return false;
  }

  // Actually create the task. RefImage will account for memory on the first
  // ref.
  RefImage(key);
  existing_task = make_scoped_refptr(
      new ImageDecodeTaskImpl(this, key, image, task_type, tracing_info));
  *task = existing_task;
  SanityCheckState(__LINE__, true);
  return true;
}

void SoftwareImageDecodeCache::RefImage(const ImageKey& key) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::RefImage", "key", key.ToString());
  lock_.AssertAcquired();
  int ref = ++decoded_images_ref_counts_[key];
  if (ref == 1) {
    DCHECK_GE(locked_images_budget_.AvailableMemoryBytes(), key.locked_bytes());
    locked_images_budget_.AddUsage(key.locked_bytes());
  }
}

void SoftwareImageDecodeCache::UnrefImage(const DrawImage& image) {
  // When we unref the image, there are several situations we need to consider:
  // 1. The ref did not reach 0, which means we have to keep the image locked.
  // 2. The ref reached 0, we should unlock it.
  //   2a. The image isn't in the locked cache because we didn't get to decode
  //       it yet (or failed to decode it).
  //   2b. Unlock the image but keep it in list.
  const ImageKey& key = ImageKey::FromDrawImage(image);
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::UnrefImage", "key", key.ToString());

  base::AutoLock lock(lock_);
  auto ref_count_it = decoded_images_ref_counts_.find(key);
  DCHECK(ref_count_it != decoded_images_ref_counts_.end());

  --ref_count_it->second;
  if (ref_count_it->second == 0) {
    decoded_images_ref_counts_.erase(ref_count_it);
    locked_images_budget_.SubtractUsage(key.locked_bytes());

    auto decoded_image_it = decoded_images_.Peek(key);
    // If we've never decoded the image before ref reached 0, then we wouldn't
    // have it in our cache. This would happen if we canceled tasks.
    if (decoded_image_it == decoded_images_.end()) {
      SanityCheckState(__LINE__, true);
      return;
    }
    DCHECK(decoded_image_it->second->is_locked());
    decoded_image_it->second->Unlock();
  }
  SanityCheckState(__LINE__, true);
}

void SoftwareImageDecodeCache::DecodeImage(const ImageKey& key,
                                           const DrawImage& image,
                                           DecodeTaskType task_type) {
  TRACE_EVENT1("cc", "SoftwareImageDecodeCache::DecodeImage", "key",
               key.ToString());
  base::AutoLock lock(lock_);
  AutoRemoveKeyFromTaskMap remove_key_from_task_map(
      (task_type == DecodeTaskType::USE_IN_RASTER_TASKS)
          ? &pending_in_raster_image_tasks_
          : &pending_out_of_raster_image_tasks_,
      key);

  // We could have finished all of the raster tasks (cancelled) while the task
  // was just starting to run. Since this task already started running, it
  // wasn't cancelled. So, if the ref count for the image is 0 then we can just
  // abort.
  if (decoded_images_ref_counts_.find(key) ==
      decoded_images_ref_counts_.end()) {
    return;
  }

  auto image_it = decoded_images_.Peek(key);
  if (image_it != decoded_images_.end()) {
    if (image_it->second->is_locked() || image_it->second->Lock())
      return;
    decoded_images_.Erase(image_it);
  }

  std::unique_ptr<DecodedImage> decoded_image;
  {
    base::AutoUnlock unlock(lock_);
    decoded_image = DecodeImageInternal(key, image);
  }

  // Abort if we failed to decode the image.
  if (!decoded_image)
    return;

  // At this point, it could have been the case that this image was decoded in
  // place by an already running raster task from a previous schedule. If that's
  // the case, then it would have already been placed into the cache (possibly
  // locked). Remove it if that was the case.
  image_it = decoded_images_.Peek(key);
  if (image_it != decoded_images_.end()) {
    if (image_it->second->is_locked() || image_it->second->Lock()) {
      // Make sure to unlock the decode we did in this function.
      decoded_image->Unlock();
      return;
    }
    decoded_images_.Erase(image_it);
  }

  // We could have finished all of the raster tasks (cancelled) while this image
  // decode task was running, which means that we now have a locked image but no
  // ref counts. Unlock it immediately in this case.
  if (decoded_images_ref_counts_.find(key) ==
      decoded_images_ref_counts_.end()) {
    decoded_image->Unlock();
  }

  decoded_images_.Put(key, std::move(decoded_image));
  SanityCheckState(__LINE__, true);
}

std::unique_ptr<SoftwareImageDecodeCache::DecodedImage>
SoftwareImageDecodeCache::DecodeImageInternal(const ImageKey& key,
                                              const DrawImage& draw_image) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::DecodeImageInternal", "key",
               key.ToString());
  sk_sp<const SkImage> image = draw_image.image();
  if (!image)
    return nullptr;

  switch (key.filter_quality()) {
    case kNone_SkFilterQuality:
    case kLow_SkFilterQuality:
      if (key.should_use_subrect())
        return GetSubrectImageDecode(key, std::move(image));
      return GetOriginalImageDecode(std::move(image));
    case kMedium_SkFilterQuality:
    case kHigh_SkFilterQuality:
      return GetScaledImageDecode(key, std::move(image));
    default:
      NOTREACHED();
      return nullptr;
  }
}

DecodedDrawImage SoftwareImageDecodeCache::GetDecodedImageForDraw(
    const DrawImage& draw_image) {
  ImageKey key = ImageKey::FromDrawImage(draw_image);
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::GetDecodedImageForDraw", "key",
               key.ToString());
  // If the target size is empty, we can skip this image draw.
  if (key.target_size().IsEmpty())
    return DecodedDrawImage(nullptr, kNone_SkFilterQuality);

  return GetDecodedImageForDrawInternal(key, draw_image);
}

DecodedDrawImage SoftwareImageDecodeCache::GetDecodedImageForDrawInternal(
    const ImageKey& key,
    const DrawImage& draw_image) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::GetDecodedImageForDrawInternal",
               "key", key.ToString());
  base::AutoLock lock(lock_);
  auto decoded_images_it = decoded_images_.Get(key);
  // If we found the image and it's locked, then return it. If it's not locked,
  // erase it from the cache since it might be put into the at-raster cache.
  std::unique_ptr<DecodedImage> scoped_decoded_image;
  DecodedImage* decoded_image = nullptr;
  if (decoded_images_it != decoded_images_.end()) {
    decoded_image = decoded_images_it->second.get();
    if (decoded_image->is_locked()) {
      RefImage(key);
      decoded_image->mark_used();
      SanityCheckState(__LINE__, true);
      return DecodedDrawImage(
          decoded_image->image(), decoded_image->src_rect_offset(),
          GetScaleAdjustment(key), GetDecodedFilterQuality(key));
    } else {
      scoped_decoded_image = std::move(decoded_images_it->second);
      decoded_images_.Erase(decoded_images_it);
    }
  }

  // See if another thread already decoded this image at raster time. If so, we
  // can just use that result directly.
  auto at_raster_images_it = at_raster_decoded_images_.Get(key);
  if (at_raster_images_it != at_raster_decoded_images_.end()) {
    DCHECK(at_raster_images_it->second->is_locked());
    RefAtRasterImage(key);
    SanityCheckState(__LINE__, true);
    DecodedImage* at_raster_decoded_image = at_raster_images_it->second.get();
    at_raster_decoded_image->mark_used();
    auto decoded_draw_image =
        DecodedDrawImage(at_raster_decoded_image->image(),
                         at_raster_decoded_image->src_rect_offset(),
                         GetScaleAdjustment(key), GetDecodedFilterQuality(key));
    decoded_draw_image.set_at_raster_decode(true);
    return decoded_draw_image;
  }

  // Now we know that we don't have a locked image, and we seem to be the first
  // thread encountering this image (that might not be true, since other threads
  // might be decoding it already). This means that we need to decode the image
  // assuming we can't lock the one we found in the cache.
  bool check_at_raster_cache = false;
  if (!decoded_image || !decoded_image->Lock()) {
    // Note that we have to release the lock, since this lock is also accessed
    // on the compositor thread. This means holding on to the lock might stall
    // the compositor thread for the duration of the decode!
    base::AutoUnlock unlock(lock_);
    scoped_decoded_image = DecodeImageInternal(key, draw_image);
    decoded_image = scoped_decoded_image.get();

    // Skip the image if we couldn't decode it.
    if (!decoded_image)
      return DecodedDrawImage(nullptr, kNone_SkFilterQuality);
    check_at_raster_cache = true;
  }

  DCHECK(decoded_image == scoped_decoded_image.get());

  // While we unlocked the lock, it could be the case that another thread
  // already decoded this already and put it in the at-raster cache. Look it up
  // first.
  if (check_at_raster_cache) {
    at_raster_images_it = at_raster_decoded_images_.Get(key);
    if (at_raster_images_it != at_raster_decoded_images_.end()) {
      // We have to drop our decode, since the one in the cache is being used by
      // another thread.
      decoded_image->Unlock();
      decoded_image = at_raster_images_it->second.get();
      scoped_decoded_image = nullptr;
    }
  }

  // If we really are the first ones, or if the other thread already unlocked
  // the image, then put our work into at-raster time cache.
  if (scoped_decoded_image)
    at_raster_decoded_images_.Put(key, std::move(scoped_decoded_image));

  DCHECK(decoded_image);
  DCHECK(decoded_image->is_locked());
  RefAtRasterImage(key);
  SanityCheckState(__LINE__, true);
  decoded_image->mark_used();
  auto decoded_draw_image =
      DecodedDrawImage(decoded_image->image(), decoded_image->src_rect_offset(),
                       GetScaleAdjustment(key), GetDecodedFilterQuality(key));
  decoded_draw_image.set_at_raster_decode(true);
  return decoded_draw_image;
}

std::unique_ptr<SoftwareImageDecodeCache::DecodedImage>
SoftwareImageDecodeCache::GetOriginalImageDecode(sk_sp<const SkImage> image) {
  SkImageInfo decoded_info =
      CreateImageInfo(image->width(), image->height(), format_);
  std::unique_ptr<base::DiscardableMemory> decoded_pixels;
  {
    TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                 "SoftwareImageDecodeCache::GetOriginalImageDecode - "
                 "allocate decoded pixels");
    decoded_pixels =
        base::DiscardableMemoryAllocator::GetInstance()
            ->AllocateLockedDiscardableMemory(decoded_info.minRowBytes() *
                                              decoded_info.height());
  }
  {
    TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                 "SoftwareImageDecodeCache::GetOriginalImageDecode - "
                 "read pixels");
    bool result = image->readPixels(decoded_info, decoded_pixels->data(),
                                    decoded_info.minRowBytes(), 0, 0,
                                    SkImage::kDisallow_CachingHint);

    if (!result) {
      decoded_pixels->Unlock();
      return nullptr;
    }
  }
  return base::MakeUnique<DecodedImage>(decoded_info, std::move(decoded_pixels),
                                        SkSize::Make(0, 0),
                                        next_tracing_id_.GetNext());
}

std::unique_ptr<SoftwareImageDecodeCache::DecodedImage>
SoftwareImageDecodeCache::GetSubrectImageDecode(const ImageKey& key,
                                                sk_sp<const SkImage> image) {
  // Construct a key to use in GetDecodedImageForDrawInternal().
  // This allows us to reuse an image in any cache if available.
  gfx::Rect full_image_rect(image->width(), image->height());
  DrawImage original_size_draw_image(std::move(image),
                                     gfx::RectToSkIRect(full_image_rect),
                                     kNone_SkFilterQuality, SkMatrix::I());
  ImageKey original_size_key =
      ImageKey::FromDrawImage(original_size_draw_image);
  // Sanity checks.
  DCHECK(original_size_key.can_use_original_decode())
      << original_size_key.ToString();
  DCHECK(full_image_rect.size() == original_size_key.target_size());

  auto decoded_draw_image = GetDecodedImageForDrawInternal(
      original_size_key, original_size_draw_image);
  AutoDrawWithImageFinished auto_finish_draw(this, original_size_draw_image,
                                             decoded_draw_image);
  if (!decoded_draw_image.image())
    return nullptr;

  SkImageInfo subrect_info = CreateImageInfo(
      key.target_size().width(), key.target_size().height(), format_);
  std::unique_ptr<base::DiscardableMemory> subrect_pixels;
  {
    TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                 "SoftwareImageDecodeCache::GetSubrectImageDecode - "
                 "allocate subrect pixels");
    // TODO(vmpstr): This is using checked math to diagnose a problem reported
    // in crbug.com/662217. If this is causing crashes, then it should be fixed
    // elsewhere by skipping images that are too large.
    base::CheckedNumeric<size_t> byte_size = subrect_info.minRowBytes();
    byte_size *= subrect_info.height();
    subrect_pixels =
        base::DiscardableMemoryAllocator::GetInstance()
            ->AllocateLockedDiscardableMemory(byte_size.ValueOrDie());
  }
  {
    TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                 "SoftwareImageDecodeCache::GetSubrectImageDecode - "
                 "read pixels");
    bool result = decoded_draw_image.image()->readPixels(
        subrect_info, subrect_pixels->data(), subrect_info.minRowBytes(),
        key.src_rect().x(), key.src_rect().y(), SkImage::kDisallow_CachingHint);
    // We have a decoded image, and we're reading into already allocated memory.
    // This should never fail.
    DCHECK(result);
  }
  return base::WrapUnique(
      new DecodedImage(subrect_info, std::move(subrect_pixels),
                       SkSize::Make(-key.src_rect().x(), -key.src_rect().y()),
                       next_tracing_id_.GetNext()));
}

std::unique_ptr<SoftwareImageDecodeCache::DecodedImage>
SoftwareImageDecodeCache::GetScaledImageDecode(const ImageKey& key,
                                               sk_sp<const SkImage> image) {
  // Construct a key to use in GetDecodedImageForDrawInternal().
  // This allows us to reuse an image in any cache if available.
  gfx::Rect full_image_rect(image->width(), image->height());
  DrawImage original_size_draw_image(std::move(image),
                                     gfx::RectToSkIRect(full_image_rect),
                                     kNone_SkFilterQuality, SkMatrix::I());
  ImageKey original_size_key =
      ImageKey::FromDrawImage(original_size_draw_image);
  // Sanity checks.
  DCHECK(original_size_key.can_use_original_decode())
      << original_size_key.ToString();
  DCHECK(full_image_rect.size() == original_size_key.target_size());

  auto decoded_draw_image = GetDecodedImageForDrawInternal(
      original_size_key, original_size_draw_image);
  AutoDrawWithImageFinished auto_finish_draw(this, original_size_draw_image,
                                             decoded_draw_image);
  if (!decoded_draw_image.image())
    return nullptr;

  SkPixmap decoded_pixmap;
  bool result = decoded_draw_image.image()->peekPixels(&decoded_pixmap);
  DCHECK(result) << key.ToString();
  if (key.src_rect() != full_image_rect) {
    result = decoded_pixmap.extractSubset(&decoded_pixmap,
                                          gfx::RectToSkIRect(key.src_rect()));
    DCHECK(result) << key.ToString();
  }

  DCHECK(!key.target_size().IsEmpty());
  SkImageInfo scaled_info = CreateImageInfo(
      key.target_size().width(), key.target_size().height(), format_);
  std::unique_ptr<base::DiscardableMemory> scaled_pixels;
  {
    TRACE_EVENT0(
        TRACE_DISABLED_BY_DEFAULT("cc.debug"),
        "SoftwareImageDecodeCache::ScaleImage - allocate scaled pixels");
    scaled_pixels = base::DiscardableMemoryAllocator::GetInstance()
                        ->AllocateLockedDiscardableMemory(
                            scaled_info.minRowBytes() * scaled_info.height());
  }
  SkPixmap scaled_pixmap(scaled_info, scaled_pixels->data(),
                         scaled_info.minRowBytes());
  DCHECK(key.filter_quality() == kHigh_SkFilterQuality ||
         key.filter_quality() == kMedium_SkFilterQuality);
  {
    TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
                 "SoftwareImageDecodeCache::ScaleImage - scale pixels");
    bool result =
        decoded_pixmap.scalePixels(scaled_pixmap, key.filter_quality());
    DCHECK(result) << key.ToString();
  }

  return base::MakeUnique<DecodedImage>(
      scaled_info, std::move(scaled_pixels),
      SkSize::Make(-key.src_rect().x(), -key.src_rect().y()),
      next_tracing_id_.GetNext());
}

void SoftwareImageDecodeCache::DrawWithImageFinished(
    const DrawImage& image,
    const DecodedDrawImage& decoded_image) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::DrawWithImageFinished", "key",
               ImageKey::FromDrawImage(image).ToString());
  ImageKey key = ImageKey::FromDrawImage(image);
  if (!decoded_image.image())
    return;

  if (decoded_image.is_at_raster_decode())
    UnrefAtRasterImage(key);
  else
    UnrefImage(image);
  SanityCheckState(__LINE__, false);
}

void SoftwareImageDecodeCache::RefAtRasterImage(const ImageKey& key) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::RefAtRasterImage", "key",
               key.ToString());
  DCHECK(at_raster_decoded_images_.Peek(key) !=
         at_raster_decoded_images_.end());
  ++at_raster_decoded_images_ref_counts_[key];
}

void SoftwareImageDecodeCache::UnrefAtRasterImage(const ImageKey& key) {
  TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
               "SoftwareImageDecodeCache::UnrefAtRasterImage", "key",
               key.ToString());
  base::AutoLock lock(lock_);

  auto ref_it = at_raster_decoded_images_ref_counts_.find(key);
  DCHECK(ref_it != at_raster_decoded_images_ref_counts_.end());
  --ref_it->second;
  if (ref_it->second == 0) {
    at_raster_decoded_images_ref_counts_.erase(ref_it);
    auto at_raster_image_it = at_raster_decoded_images_.Peek(key);
    DCHECK(at_raster_image_it != at_raster_decoded_images_.end());

    // The ref for our image reached 0 and it's still locked. We need to figure
    // out what the best thing to do with the image. There are several
    // situations:
    // 1. The image is not in the main cache and...
    //    1a. ... its ref count is 0: unlock our image and put it in the main
    //    cache.
    //    1b. ... ref count is not 0: keep the image locked and put it in the
    //    main cache.
    // 2. The image is in the main cache...
    //    2a. ... and is locked: unlock our image and discard it
    //    2b. ... and is unlocked and...
    //       2b1. ... its ref count is 0: unlock our image and replace the
    //       existing one with ours.
    //       2b2. ... its ref count is not 0: this shouldn't be possible.
    auto image_it = decoded_images_.Peek(key);
    if (image_it == decoded_images_.end()) {
      if (decoded_images_ref_counts_.find(key) ==
          decoded_images_ref_counts_.end()) {
        at_raster_image_it->second->Unlock();
      }
      decoded_images_.Put(key, std::move(at_raster_image_it->second));
    } else if (image_it->second->is_locked()) {
      at_raster_image_it->second->Unlock();
    } else {
      DCHECK(decoded_images_ref_counts_.find(key) ==
             decoded_images_ref_counts_.end());
      at_raster_image_it->second->Unlock();
      decoded_images_.Erase(image_it);
      decoded_images_.Put(key, std::move(at_raster_image_it->second));
    }
    at_raster_decoded_images_.Erase(at_raster_image_it);
  }
}

void SoftwareImageDecodeCache::ReduceCacheUsageUntilWithinLimit(size_t limit) {
  TRACE_EVENT0("cc", "SoftwareImageDecodeCache::ReduceCacheUsage");
  size_t num_to_remove =
      (decoded_images_.size() > limit) ? (decoded_images_.size() - limit) : 0;
  for (auto it = decoded_images_.rbegin();
       num_to_remove != 0 && it != decoded_images_.rend();) {
    if (it->second->is_locked()) {
      ++it;
      continue;
    }

    it = decoded_images_.Erase(it);
    --num_to_remove;
  }
}

void SoftwareImageDecodeCache::ReduceCacheUsage() {
  base::AutoLock lock(lock_);
  ReduceCacheUsageUntilWithinLimit(max_items_in_cache_);
}

void SoftwareImageDecodeCache::RemovePendingTask(const ImageKey& key,
                                                 DecodeTaskType task_type) {
  base::AutoLock lock(lock_);
  switch (task_type) {
    case DecodeTaskType::USE_IN_RASTER_TASKS:
      pending_in_raster_image_tasks_.erase(key);
      break;
    case DecodeTaskType::USE_OUT_OF_RASTER_TASKS:
      pending_out_of_raster_image_tasks_.erase(key);
      break;
  }
}

bool SoftwareImageDecodeCache::OnMemoryDump(
    const base::trace_event::MemoryDumpArgs& args,
    base::trace_event::ProcessMemoryDump* pmd) {
  base::AutoLock lock(lock_);

  if (args.level_of_detail == MemoryDumpLevelOfDetail::BACKGROUND) {
    std::string dump_name = base::StringPrintf(
        "cc/image_memory/cache_0x%" PRIXPTR, reinterpret_cast<uintptr_t>(this));
    MemoryAllocatorDump* dump = pmd->CreateAllocatorDump(dump_name);
    dump->AddScalar("locked_size", MemoryAllocatorDump::kUnitsBytes,
                    locked_images_budget_.GetCurrentUsageSafe());
  } else {
    // Dump each of our caches.
    DumpImageMemoryForCache(decoded_images_, "cached", pmd);
    DumpImageMemoryForCache(at_raster_decoded_images_, "at_raster", pmd);
  }

  // Memory dump can't fail, always return true.
  return true;
}

void SoftwareImageDecodeCache::DumpImageMemoryForCache(
    const ImageMRUCache& cache,
    const char* cache_name,
    base::trace_event::ProcessMemoryDump* pmd) const {
  lock_.AssertAcquired();

  for (const auto& image_pair : cache) {
    std::string dump_name = base::StringPrintf(
        "cc/image_memory/cache_0x%" PRIXPTR "/%s/image_%" PRIu64 "_id_%d",
        reinterpret_cast<uintptr_t>(this), cache_name,
        image_pair.second->tracing_id(), image_pair.first.image_id());
    // CreateMemoryAllocatorDump will automatically add tracking values for the
    // total size. We also add a "locked_size" below.
    MemoryAllocatorDump* dump =
        image_pair.second->memory()->CreateMemoryAllocatorDump(
            dump_name.c_str(), pmd);
    DCHECK(dump);
    size_t locked_bytes =
        image_pair.second->is_locked() ? image_pair.first.locked_bytes() : 0u;
    dump->AddScalar("locked_size", MemoryAllocatorDump::kUnitsBytes,
                    locked_bytes);
  }
}

void SoftwareImageDecodeCache::SanityCheckState(int line, bool lock_acquired) {
#if DCHECK_IS_ON()
  if (!lock_acquired) {
    base::AutoLock lock(lock_);
    SanityCheckState(line, true);
    return;
  }

  MemoryBudget budget(locked_images_budget_.total_limit_bytes());
  for (const auto& image_pair : decoded_images_) {
    const auto& key = image_pair.first;
    const auto& image = image_pair.second;

    auto ref_it = decoded_images_ref_counts_.find(key);
    if (image->is_locked()) {
      budget.AddUsage(key.locked_bytes());
      DCHECK(ref_it != decoded_images_ref_counts_.end()) << line;
    } else {
      DCHECK(ref_it == decoded_images_ref_counts_.end() ||
             pending_in_raster_image_tasks_.find(key) !=
                 pending_in_raster_image_tasks_.end() ||
             pending_out_of_raster_image_tasks_.find(key) !=
                 pending_out_of_raster_image_tasks_.end())
          << line;
    }
  }
  DCHECK_GE(budget.AvailableMemoryBytes(),
            locked_images_budget_.AvailableMemoryBytes())
      << line;
#endif  // DCHECK_IS_ON()
}

// SoftwareImageDecodeCacheKey
ImageDecodeCacheKey ImageDecodeCacheKey::FromDrawImage(const DrawImage& image) {
  const SkSize& scale = image.scale();
  // If the src_rect falls outside of the image, we need to clip it since
  // otherwise we might end up with uninitialized memory in the decode process.
  // Note that the scale is still unchanged and the target size is now a
  // function of the new src_rect.
  const gfx::Rect& src_rect = GetSrcRect(image);
  gfx::Size target_size(
      SkScalarRoundToInt(std::abs(src_rect.width() * scale.width())),
      SkScalarRoundToInt(std::abs(src_rect.height() * scale.height())));

  // Start with the quality that was requested.
  SkFilterQuality quality = image.filter_quality();

  // If we're not going to do a scale, we can use low filter quality. Note that
  // checking if the sizes are the same is better than checking if scale is 1.f,
  // because even non-1 scale can result in the same (rounded) width/height.
  // If either dimension is a downscale, then use mipmaps (medium filter
  // quality).
  if (target_size.width() == src_rect.width() &&
      target_size.height() == src_rect.height()) {
    quality = std::min(quality, kLow_SkFilterQuality);
  } else if (target_size.width() < src_rect.width() ||
             target_size.height() < src_rect.height()) {
    quality = std::min(quality, kMedium_SkFilterQuality);
  }

  // Drop from high to medium if the the matrix we applied wasn't decomposable,
  // or if the scaled image will be too large.
  if (quality == kHigh_SkFilterQuality) {
    if (!image.matrix_is_decomposable()) {
      quality = kMedium_SkFilterQuality;
    } else {
      base::CheckedNumeric<size_t> size = 4u;
      size *= target_size.width();
      size *= target_size.height();
      if (size.ValueOrDefault(std::numeric_limits<size_t>::max()) >
          kMaxHighQualityImageSizeBytes) {
        quality = kMedium_SkFilterQuality;
      }
    }
  }

  // Drop from medium to low if the matrix we applied wasn't decomposable or if
  // we're enlarging the image in both dimensions.
  if (quality == kMedium_SkFilterQuality) {
    if (!image.matrix_is_decomposable() ||
        (scale.width() >= 1.f && scale.height() >= 1.f)) {
      quality = kLow_SkFilterQuality;
    }
  }

  bool can_use_original_decode =
      quality == kLow_SkFilterQuality || quality == kNone_SkFilterQuality;
  bool should_use_subrect = false;
  if (can_use_original_decode &&
      (image.image()->width() >= kMinDimensionToSubrect ||
       image.image()->height() >= kMinDimensionToSubrect)) {
    base::CheckedNumeric<size_t> checked_original_size = 4u;
    checked_original_size *= image.image()->width();
    checked_original_size *= image.image()->height();
    size_t original_size = checked_original_size.ValueOrDefault(
        std::numeric_limits<size_t>::max());

    base::CheckedNumeric<size_t> checked_src_rect_size = 4u;
    checked_src_rect_size *= src_rect.width();
    checked_src_rect_size *= src_rect.height();
    size_t src_rect_size = checked_src_rect_size.ValueOrDefault(
        std::numeric_limits<size_t>::max());
    if (original_size > kMemoryThresholdToSubrect &&
        src_rect_size <= original_size * kMemoryRatioToSubrect) {
      should_use_subrect = true;
      can_use_original_decode = false;
    }
  }

  // If we're going to use the original decode, then the target size should be
  // the full image size, since that will allow for proper memory accounting.
  // Note we skip the decode if the target size is empty altogether, so don't
  // update the target size in that case.
  if (!target_size.IsEmpty()) {
    if (should_use_subrect)
      target_size = src_rect.size();
    else if (can_use_original_decode)
      target_size = gfx::Size(image.image()->width(), image.image()->height());
  }

  if (quality == kMedium_SkFilterQuality && !target_size.IsEmpty()) {
    SkSize mip_target_size =
        MipMapUtil::GetScaleAdjustmentForSize(src_rect.size(), target_size);
    target_size.set_width(src_rect.width() * mip_target_size.width());
    target_size.set_height(src_rect.height() * mip_target_size.height());
  }

  return ImageDecodeCacheKey(image.image()->uniqueID(), src_rect, target_size,
                             quality, can_use_original_decode,
                             should_use_subrect);
}

ImageDecodeCacheKey::ImageDecodeCacheKey(uint32_t image_id,
                                         const gfx::Rect& src_rect,
                                         const gfx::Size& target_size,
                                         SkFilterQuality filter_quality,
                                         bool can_use_original_decode,
                                         bool should_use_subrect)
    : image_id_(image_id),
      src_rect_(src_rect),
      target_size_(target_size),
      filter_quality_(filter_quality),
      can_use_original_decode_(can_use_original_decode),
      should_use_subrect_(should_use_subrect) {
  if (can_use_original_decode_) {
    hash_ = std::hash<uint32_t>()(image_id_);
  } else {
    // TODO(vmpstr): This is a mess. Maybe it's faster to just search the vector
    // always (forwards or backwards to account for LRU).
    uint64_t src_rect_hash = base::HashInts(
        static_cast<uint64_t>(base::HashInts(src_rect_.x(), src_rect_.y())),
        static_cast<uint64_t>(
            base::HashInts(src_rect_.width(), src_rect_.height())));

    uint64_t target_size_hash =
        base::HashInts(target_size_.width(), target_size_.height());

    hash_ = base::HashInts(base::HashInts(src_rect_hash, target_size_hash),
                           base::HashInts(image_id_, filter_quality_));
  }
}

ImageDecodeCacheKey::ImageDecodeCacheKey(const ImageDecodeCacheKey& other) =
    default;

std::string ImageDecodeCacheKey::ToString() const {
  std::ostringstream str;
  str << "id[" << image_id_ << "] src_rect[" << src_rect_.x() << ","
      << src_rect_.y() << " " << src_rect_.width() << "x" << src_rect_.height()
      << "] target_size[" << target_size_.width() << "x"
      << target_size_.height() << "] filter_quality[" << filter_quality_
      << "] can_use_original_decode [" << can_use_original_decode_
      << "] should_use_subrect [" << should_use_subrect_ << "] hash [" << hash_
      << "]";
  return str.str();
}

// DecodedImage
SoftwareImageDecodeCache::DecodedImage::DecodedImage(
    const SkImageInfo& info,
    std::unique_ptr<base::DiscardableMemory> memory,
    const SkSize& src_rect_offset,
    uint64_t tracing_id)
    : locked_(true),
      image_info_(info),
      memory_(std::move(memory)),
      src_rect_offset_(src_rect_offset),
      tracing_id_(tracing_id) {
  SkPixmap pixmap(image_info_, memory_->data(), image_info_.minRowBytes());
  image_ = SkImage::MakeFromRaster(
      pixmap, [](const void* pixels, void* context) {}, nullptr);
}

SoftwareImageDecodeCache::DecodedImage::~DecodedImage() {
  DCHECK(!locked_);
  // lock_count | used  | last lock failed | result state
  // ===========+=======+==================+==================
  //  1         | false | false            | WASTED
  //  1         | false | true             | WASTED
  //  1         | true  | false            | USED
  //  1         | true  | true             | USED_RELOCK_FAILED
  //  >1        | false | false            | WASTED_RELOCKED
  //  >1        | false | true             | WASTED_RELOCKED
  //  >1        | true  | false            | USED_RELOCKED
  //  >1        | true  | true             | USED_RELOCKED
  // Note that it's important not to reorder the following enums, since the
  // numerical values are used in the histogram code.
  enum State : int {
    DECODED_IMAGE_STATE_WASTED,
    DECODED_IMAGE_STATE_USED,
    DECODED_IMAGE_STATE_USED_RELOCK_FAILED,
    DECODED_IMAGE_STATE_WASTED_RELOCKED,
    DECODED_IMAGE_STATE_USED_RELOCKED,
    DECODED_IMAGE_STATE_COUNT
  } state = DECODED_IMAGE_STATE_WASTED;

  if (usage_stats_.lock_count == 1) {
    if (!usage_stats_.used)
      state = DECODED_IMAGE_STATE_WASTED;
    else if (usage_stats_.last_lock_failed)
      state = DECODED_IMAGE_STATE_USED_RELOCK_FAILED;
    else
      state = DECODED_IMAGE_STATE_USED;
  } else {
    if (usage_stats_.used)
      state = DECODED_IMAGE_STATE_USED_RELOCKED;
    else
      state = DECODED_IMAGE_STATE_WASTED_RELOCKED;
  }

  UMA_HISTOGRAM_ENUMERATION("Renderer4.SoftwareImageDecodeState", state,
                            DECODED_IMAGE_STATE_COUNT);
  UMA_HISTOGRAM_BOOLEAN("Renderer4.SoftwareImageDecodeState.FirstLockWasted",
                        usage_stats_.first_lock_wasted);
}

bool SoftwareImageDecodeCache::DecodedImage::Lock() {
  DCHECK(!locked_);
  bool success = memory_->Lock();
  if (!success) {
    usage_stats_.last_lock_failed = true;
    return false;
  }
  locked_ = true;
  ++usage_stats_.lock_count;
  return true;
}

void SoftwareImageDecodeCache::DecodedImage::Unlock() {
  DCHECK(locked_);
  memory_->Unlock();
  locked_ = false;
  if (usage_stats_.lock_count == 1)
    usage_stats_.first_lock_wasted = !usage_stats_.used;
}

// MemoryBudget
SoftwareImageDecodeCache::MemoryBudget::MemoryBudget(size_t limit_bytes)
    : limit_bytes_(limit_bytes), current_usage_bytes_(0u) {}

size_t SoftwareImageDecodeCache::MemoryBudget::AvailableMemoryBytes() const {
  size_t usage = GetCurrentUsageSafe();
  return usage >= limit_bytes_ ? 0u : (limit_bytes_ - usage);
}

void SoftwareImageDecodeCache::MemoryBudget::AddUsage(size_t usage) {
  current_usage_bytes_ += usage;
}

void SoftwareImageDecodeCache::MemoryBudget::SubtractUsage(size_t usage) {
  DCHECK_GE(current_usage_bytes_.ValueOrDefault(0u), usage);
  current_usage_bytes_ -= usage;
}

void SoftwareImageDecodeCache::MemoryBudget::ResetUsage() {
  current_usage_bytes_ = 0;
}

size_t SoftwareImageDecodeCache::MemoryBudget::GetCurrentUsageSafe() const {
  return current_usage_bytes_.ValueOrDie();
}

void SoftwareImageDecodeCache::OnMemoryStateChange(base::MemoryState state) {
  {
    base::AutoLock hold(lock_);
    switch (state) {
      case base::MemoryState::NORMAL:
        max_items_in_cache_ = kNormalMaxItemsInCache;
        break;
      case base::MemoryState::THROTTLED:
        max_items_in_cache_ = kThrottledMaxItemsInCache;
        break;
      case base::MemoryState::SUSPENDED:
        max_items_in_cache_ = kSuspendedMaxItemsInCache;
        break;
      case base::MemoryState::UNKNOWN:
        NOTREACHED();
        return;
    }
  }
}

void SoftwareImageDecodeCache::OnPurgeMemory() {
  base::AutoLock lock(lock_);
  ReduceCacheUsageUntilWithinLimit(0);
}

}  // namespace cc