1// Copyright 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "cc/resources/prioritized_resource_manager.h"
6
7#include <algorithm>
8
9#include "base/debug/trace_event.h"
10#include "base/stl_util.h"
11#include "cc/resources/prioritized_resource.h"
12#include "cc/resources/priority_calculator.h"
13#include "cc/trees/proxy.h"
14
15namespace cc {
16
17PrioritizedResourceManager::PrioritizedResourceManager(const Proxy* proxy)
18    : max_memory_limit_bytes_(DefaultMemoryAllocationLimit()),
19      external_priority_cutoff_(PriorityCalculator::AllowEverythingCutoff()),
20      memory_use_bytes_(0),
21      memory_above_cutoff_bytes_(0),
22      max_memory_needed_bytes_(0),
23      memory_available_bytes_(0),
24      proxy_(proxy),
25      backings_tail_not_sorted_(false),
26      memory_visible_bytes_(0),
27      memory_visible_and_nearby_bytes_(0),
28      memory_visible_last_pushed_bytes_(0),
29      memory_visible_and_nearby_last_pushed_bytes_(0) {}
30
31PrioritizedResourceManager::~PrioritizedResourceManager() {
32  while (textures_.size() > 0)
33    UnregisterTexture(*textures_.begin());
34
35  UnlinkAndClearEvictedBackings();
36  DCHECK(evicted_backings_.empty());
37
38  // Each remaining backing is a leaked opengl texture. There should be none.
39  DCHECK(backings_.empty());
40}
41
42size_t PrioritizedResourceManager::MemoryVisibleBytes() const {
43  DCHECK(proxy_->IsImplThread());
44  return memory_visible_last_pushed_bytes_;
45}
46
47size_t PrioritizedResourceManager::MemoryVisibleAndNearbyBytes() const {
48  DCHECK(proxy_->IsImplThread());
49  return memory_visible_and_nearby_last_pushed_bytes_;
50}
51
52void PrioritizedResourceManager::PrioritizeTextures() {
53  TRACE_EVENT0("cc", "PrioritizedResourceManager::PrioritizeTextures");
54  DCHECK(proxy_->IsMainThread());
55
56  // Sorting textures in this function could be replaced by a slightly
57  // modified O(n) quick-select to partition textures rather than
58  // sort them (if performance of the sort becomes an issue).
59
60  TextureVector& sorted_textures = temp_texture_vector_;
61  sorted_textures.clear();
62
63  // Copy all textures into a vector, sort them, and collect memory requirements
64  // statistics.
65  memory_visible_bytes_ = 0;
66  memory_visible_and_nearby_bytes_ = 0;
67  for (TextureSet::iterator it = textures_.begin(); it != textures_.end();
68       ++it) {
69    PrioritizedResource* texture = (*it);
70    sorted_textures.push_back(texture);
71    if (PriorityCalculator::priority_is_higher(
72            texture->request_priority(),
73            PriorityCalculator::AllowVisibleOnlyCutoff()))
74      memory_visible_bytes_ += texture->bytes();
75    if (PriorityCalculator::priority_is_higher(
76            texture->request_priority(),
77            PriorityCalculator::AllowVisibleAndNearbyCutoff()))
78      memory_visible_and_nearby_bytes_ += texture->bytes();
79  }
80  std::sort(sorted_textures.begin(), sorted_textures.end(), CompareTextures);
81
82  // Compute a priority cutoff based on memory pressure
83  memory_available_bytes_ = max_memory_limit_bytes_;
84  priority_cutoff_ = external_priority_cutoff_;
85  size_t memory_bytes = 0;
86  for (TextureVector::iterator it = sorted_textures.begin();
87       it != sorted_textures.end();
88       ++it) {
89    if ((*it)->is_self_managed()) {
90      // Account for self-managed memory immediately by reducing the memory
91      // available (since it never gets acquired).
92      size_t new_memory_bytes = memory_bytes + (*it)->bytes();
93      if (new_memory_bytes > memory_available_bytes_) {
94        priority_cutoff_ = (*it)->request_priority();
95        memory_available_bytes_ = memory_bytes;
96        break;
97      }
98      memory_available_bytes_ -= (*it)->bytes();
99    } else {
100      size_t new_memory_bytes = memory_bytes + (*it)->bytes();
101      if (new_memory_bytes > memory_available_bytes_) {
102        priority_cutoff_ = (*it)->request_priority();
103        break;
104      }
105      memory_bytes = new_memory_bytes;
106    }
107  }
108
109  // Disallow any textures with priority below the external cutoff to have
110  // backings.
111  for (TextureVector::iterator it = sorted_textures.begin();
112       it != sorted_textures.end();
113       ++it) {
114    PrioritizedResource* texture = (*it);
115    if (!PriorityCalculator::priority_is_higher(texture->request_priority(),
116                                                external_priority_cutoff_) &&
117        texture->have_backing_texture())
118      texture->Unlink();
119  }
120
121  // Only allow textures if they are higher than the cutoff. All textures
122  // of the same priority are accepted or rejected together, rather than
123  // being partially allowed randomly.
124  max_memory_needed_bytes_ = 0;
125  memory_above_cutoff_bytes_ = 0;
126  for (TextureVector::iterator it = sorted_textures.begin();
127       it != sorted_textures.end();
128       ++it) {
129    PrioritizedResource* resource = *it;
130    bool is_above_priority_cutoff = PriorityCalculator::priority_is_higher(
131        resource->request_priority(), priority_cutoff_);
132    resource->set_above_priority_cutoff(is_above_priority_cutoff);
133    if (!resource->is_self_managed()) {
134      max_memory_needed_bytes_ += resource->bytes();
135      if (is_above_priority_cutoff)
136        memory_above_cutoff_bytes_ += resource->bytes();
137    }
138  }
139  sorted_textures.clear();
140
141  DCHECK_LE(memory_above_cutoff_bytes_, memory_available_bytes_);
142  DCHECK_LE(MemoryAboveCutoffBytes(), MaxMemoryLimitBytes());
143}
144
145void PrioritizedResourceManager::PushTexturePrioritiesToBackings() {
146  TRACE_EVENT0("cc",
147               "PrioritizedResourceManager::PushTexturePrioritiesToBackings");
148  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
149
150  AssertInvariants();
151  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
152       ++it)
153    (*it)->UpdatePriority();
154  SortBackings();
155  AssertInvariants();
156
157  // Push memory requirements to the impl thread structure.
158  memory_visible_last_pushed_bytes_ = memory_visible_bytes_;
159  memory_visible_and_nearby_last_pushed_bytes_ =
160      memory_visible_and_nearby_bytes_;
161}
162
163void PrioritizedResourceManager::UpdateBackingsState(
164    ResourceProvider* resource_provider) {
165  TRACE_EVENT0("cc",
166               "PrioritizedResourceManager::UpdateBackingsInDrawingImplTree");
167  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
168
169  AssertInvariants();
170  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
171       ++it) {
172    PrioritizedResource::Backing* backing = (*it);
173    backing->UpdateState(resource_provider);
174  }
175  SortBackings();
176  AssertInvariants();
177}
178
179void PrioritizedResourceManager::SortBackings() {
180  TRACE_EVENT0("cc", "PrioritizedResourceManager::SortBackings");
181  DCHECK(proxy_->IsImplThread());
182
183  // Put backings in eviction/recycling order.
184  backings_.sort(CompareBackings);
185  backings_tail_not_sorted_ = false;
186}
187
188void PrioritizedResourceManager::ClearPriorities() {
189  DCHECK(proxy_->IsMainThread());
190  for (TextureSet::iterator it = textures_.begin(); it != textures_.end();
191       ++it) {
192    // TODO(reveman): We should remove this and just set all priorities to
193    // PriorityCalculator::lowestPriority() once we have priorities for all
194    // textures (we can't currently calculate distances for off-screen
195    // textures).
196    (*it)->set_request_priority(
197        PriorityCalculator::LingeringPriority((*it)->request_priority()));
198  }
199}
200
201bool PrioritizedResourceManager::RequestLate(PrioritizedResource* texture) {
202  DCHECK(proxy_->IsMainThread());
203
204  // This is already above cutoff, so don't double count it's memory below.
205  if (texture->is_above_priority_cutoff())
206    return true;
207
208  // Allow textures that have priority equal to the cutoff, but not strictly
209  // lower.
210  if (PriorityCalculator::priority_is_lower(texture->request_priority(),
211                                            priority_cutoff_))
212    return false;
213
214  // Disallow textures that do not have a priority strictly higher than the
215  // external cutoff.
216  if (!PriorityCalculator::priority_is_higher(texture->request_priority(),
217                                              external_priority_cutoff_))
218    return false;
219
220  size_t new_memory_bytes = memory_above_cutoff_bytes_ + texture->bytes();
221  if (new_memory_bytes > memory_available_bytes_)
222    return false;
223
224  memory_above_cutoff_bytes_ = new_memory_bytes;
225  texture->set_above_priority_cutoff(true);
226  return true;
227}
228
229void PrioritizedResourceManager::AcquireBackingTextureIfNeeded(
230    PrioritizedResource* texture,
231    ResourceProvider* resource_provider) {
232  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
233  DCHECK(!texture->is_self_managed());
234  DCHECK(texture->is_above_priority_cutoff());
235  if (texture->backing() || !texture->is_above_priority_cutoff())
236    return;
237
238  // Find a backing below, by either recycling or allocating.
239  PrioritizedResource::Backing* backing = NULL;
240
241  // First try to recycle
242  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
243       ++it) {
244    if (!(*it)->CanBeRecycledIfNotInExternalUse())
245      break;
246    if (resource_provider->InUseByConsumer((*it)->id()))
247      continue;
248    if ((*it)->size() == texture->size() &&
249        (*it)->format() == texture->format()) {
250      backing = (*it);
251      backings_.erase(it);
252      break;
253    }
254  }
255
256  // Otherwise reduce memory and just allocate a new backing texures.
257  if (!backing) {
258    EvictBackingsToReduceMemory(memory_available_bytes_ - texture->bytes(),
259                                PriorityCalculator::AllowEverythingCutoff(),
260                                EVICT_ONLY_RECYCLABLE,
261                                DO_NOT_UNLINK_BACKINGS,
262                                resource_provider);
263    backing =
264        CreateBacking(texture->size(), texture->format(), resource_provider);
265  }
266
267  // Move the used backing to the end of the eviction list, and note that
268  // the tail is not sorted.
269  if (backing->owner())
270    backing->owner()->Unlink();
271  texture->Link(backing);
272  backings_.push_back(backing);
273  backings_tail_not_sorted_ = true;
274
275  // Update the backing's priority from its new owner.
276  backing->UpdatePriority();
277}
278
279bool PrioritizedResourceManager::EvictBackingsToReduceMemory(
280    size_t limit_bytes,
281    int priority_cutoff,
282    EvictionPolicy eviction_policy,
283    UnlinkPolicy unlink_policy,
284    ResourceProvider* resource_provider) {
285  DCHECK(proxy_->IsImplThread());
286  if (unlink_policy == UNLINK_BACKINGS)
287    DCHECK(proxy_->IsMainThreadBlocked());
288  if (MemoryUseBytes() <= limit_bytes &&
289      PriorityCalculator::AllowEverythingCutoff() == priority_cutoff)
290    return false;
291
292  // Destroy backings until we are below the limit,
293  // or until all backings remaining are above the cutoff.
294  bool evicted_anything = false;
295  while (backings_.size() > 0) {
296    PrioritizedResource::Backing* backing = backings_.front();
297    if (MemoryUseBytes() <= limit_bytes &&
298        PriorityCalculator::priority_is_higher(
299            backing->request_priority_at_last_priority_update(),
300            priority_cutoff))
301      break;
302    if (eviction_policy == EVICT_ONLY_RECYCLABLE &&
303        !backing->CanBeRecycledIfNotInExternalUse())
304      break;
305    if (unlink_policy == UNLINK_BACKINGS && backing->owner())
306      backing->owner()->Unlink();
307    EvictFirstBackingResource(resource_provider);
308    evicted_anything = true;
309  }
310  return evicted_anything;
311}
312
313void PrioritizedResourceManager::ReduceWastedMemory(
314    ResourceProvider* resource_provider) {
315  // We currently collect backings from deleted textures for later recycling.
316  // However, if we do that forever we will always use the max limit even if
317  // we really need very little memory. This should probably be solved by
318  // reducing the limit externally, but until then this just does some "clean
319  // up" of unused backing textures (any more than 10%).
320  size_t wasted_memory = 0;
321  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
322       ++it) {
323    if ((*it)->owner())
324      break;
325    if ((*it)->in_parent_compositor())
326      continue;
327    wasted_memory += (*it)->bytes();
328  }
329  size_t wasted_memory_to_allow = memory_available_bytes_ / 10;
330  // If the external priority cutoff indicates that unused memory should be
331  // freed, then do not allow any memory for texture recycling.
332  if (external_priority_cutoff_ != PriorityCalculator::AllowEverythingCutoff())
333    wasted_memory_to_allow = 0;
334  if (wasted_memory > wasted_memory_to_allow)
335    EvictBackingsToReduceMemory(MemoryUseBytes() -
336                                (wasted_memory - wasted_memory_to_allow),
337                                PriorityCalculator::AllowEverythingCutoff(),
338                                EVICT_ONLY_RECYCLABLE,
339                                DO_NOT_UNLINK_BACKINGS,
340                                resource_provider);
341}
342
343void PrioritizedResourceManager::ReduceMemory(
344    ResourceProvider* resource_provider) {
345  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
346  EvictBackingsToReduceMemory(memory_available_bytes_,
347                              PriorityCalculator::AllowEverythingCutoff(),
348                              EVICT_ANYTHING,
349                              UNLINK_BACKINGS,
350                              resource_provider);
351  DCHECK_LE(MemoryUseBytes(), memory_available_bytes_);
352
353  ReduceWastedMemory(resource_provider);
354}
355
356void PrioritizedResourceManager::ClearAllMemory(
357    ResourceProvider* resource_provider) {
358  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
359  if (!resource_provider) {
360    DCHECK(backings_.empty());
361    return;
362  }
363  EvictBackingsToReduceMemory(0,
364                              PriorityCalculator::AllowEverythingCutoff(),
365                              EVICT_ANYTHING,
366                              DO_NOT_UNLINK_BACKINGS,
367                              resource_provider);
368}
369
370bool PrioritizedResourceManager::ReduceMemoryOnImplThread(
371    size_t limit_bytes,
372    int priority_cutoff,
373    ResourceProvider* resource_provider) {
374  DCHECK(proxy_->IsImplThread());
375  DCHECK(resource_provider);
376
377  // If we are in the process of uploading a new frame then the backings at the
378  // very end of the list are not sorted by priority. Sort them before doing the
379  // eviction.
380  if (backings_tail_not_sorted_)
381    SortBackings();
382  return EvictBackingsToReduceMemory(limit_bytes,
383                                     priority_cutoff,
384                                     EVICT_ANYTHING,
385                                     DO_NOT_UNLINK_BACKINGS,
386                                     resource_provider);
387}
388
389void PrioritizedResourceManager::UnlinkAndClearEvictedBackings() {
390  DCHECK(proxy_->IsMainThread());
391  base::AutoLock scoped_lock(evicted_backings_lock_);
392  for (BackingList::const_iterator it = evicted_backings_.begin();
393       it != evicted_backings_.end();
394       ++it) {
395    PrioritizedResource::Backing* backing = (*it);
396    if (backing->owner())
397      backing->owner()->Unlink();
398    delete backing;
399  }
400  evicted_backings_.clear();
401}
402
403bool PrioritizedResourceManager::LinkedEvictedBackingsExist() const {
404  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
405  base::AutoLock scoped_lock(evicted_backings_lock_);
406  for (BackingList::const_iterator it = evicted_backings_.begin();
407       it != evicted_backings_.end();
408       ++it) {
409    if ((*it)->owner())
410      return true;
411  }
412  return false;
413}
414
415void PrioritizedResourceManager::RegisterTexture(PrioritizedResource* texture) {
416  DCHECK(proxy_->IsMainThread());
417  DCHECK(texture);
418  DCHECK(!texture->resource_manager());
419  DCHECK(!texture->backing());
420  DCHECK(!ContainsKey(textures_, texture));
421
422  texture->set_manager_internal(this);
423  textures_.insert(texture);
424}
425
426void PrioritizedResourceManager::UnregisterTexture(
427    PrioritizedResource* texture) {
428  DCHECK(proxy_->IsMainThread() ||
429         (proxy_->IsImplThread() && proxy_->IsMainThreadBlocked()));
430  DCHECK(texture);
431  DCHECK(ContainsKey(textures_, texture));
432
433  ReturnBackingTexture(texture);
434  texture->set_manager_internal(NULL);
435  textures_.erase(texture);
436  texture->set_above_priority_cutoff(false);
437}
438
439void PrioritizedResourceManager::ReturnBackingTexture(
440    PrioritizedResource* texture) {
441  DCHECK(proxy_->IsMainThread() ||
442         (proxy_->IsImplThread() && proxy_->IsMainThreadBlocked()));
443  if (texture->backing())
444    texture->Unlink();
445}
446
447PrioritizedResource::Backing* PrioritizedResourceManager::CreateBacking(
448    gfx::Size size,
449    ResourceFormat format,
450    ResourceProvider* resource_provider) {
451  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
452  DCHECK(resource_provider);
453  ResourceProvider::ResourceId resource_id =
454      resource_provider->CreateManagedResource(
455          size,
456          GL_TEXTURE_2D,
457          GL_CLAMP_TO_EDGE,
458          ResourceProvider::TextureUsageAny,
459          format);
460  PrioritizedResource::Backing* backing = new PrioritizedResource::Backing(
461      resource_id, resource_provider, size, format);
462  memory_use_bytes_ += backing->bytes();
463  return backing;
464}
465
466void PrioritizedResourceManager::EvictFirstBackingResource(
467    ResourceProvider* resource_provider) {
468  DCHECK(proxy_->IsImplThread());
469  DCHECK(resource_provider);
470  DCHECK(!backings_.empty());
471  PrioritizedResource::Backing* backing = backings_.front();
472
473  // Note that we create a backing and its resource at the same time, but we
474  // delete the backing structure and its resource in two steps. This is because
475  // we can delete the resource while the main thread is running, but we cannot
476  // unlink backings while the main thread is running.
477  backing->DeleteResource(resource_provider);
478  memory_use_bytes_ -= backing->bytes();
479  backings_.pop_front();
480  base::AutoLock scoped_lock(evicted_backings_lock_);
481  evicted_backings_.push_back(backing);
482}
483
484void PrioritizedResourceManager::AssertInvariants() {
485#ifndef NDEBUG
486  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
487
488  // If we hit any of these asserts, there is a bug in this class. To see
489  // where the bug is, call this function at the beginning and end of
490  // every public function.
491
492  // Backings/textures must be doubly-linked and only to other backings/textures
493  // in this manager.
494  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
495       ++it) {
496    if ((*it)->owner()) {
497      DCHECK(ContainsKey(textures_, (*it)->owner()));
498      DCHECK((*it)->owner()->backing() == (*it));
499    }
500  }
501  for (TextureSet::iterator it = textures_.begin(); it != textures_.end();
502       ++it) {
503    PrioritizedResource* texture = (*it);
504    PrioritizedResource::Backing* backing = texture->backing();
505    base::AutoLock scoped_lock(evicted_backings_lock_);
506    if (backing) {
507      if (backing->ResourceHasBeenDeleted()) {
508        DCHECK(std::find(backings_.begin(), backings_.end(), backing) ==
509               backings_.end());
510        DCHECK(std::find(evicted_backings_.begin(),
511                         evicted_backings_.end(),
512                         backing) != evicted_backings_.end());
513      } else {
514        DCHECK(std::find(backings_.begin(), backings_.end(), backing) !=
515               backings_.end());
516        DCHECK(std::find(evicted_backings_.begin(),
517                         evicted_backings_.end(),
518                         backing) == evicted_backings_.end());
519      }
520      DCHECK(backing->owner() == texture);
521    }
522  }
523
524  // At all times, backings that can be evicted must always come before
525  // backings that can't be evicted in the backing texture list (otherwise
526  // ReduceMemory will not find all textures available for eviction/recycling).
527  bool reached_unrecyclable = false;
528  PrioritizedResource::Backing* previous_backing = NULL;
529  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
530       ++it) {
531    PrioritizedResource::Backing* backing = *it;
532    if (previous_backing &&
533        (!backings_tail_not_sorted_ ||
534         !backing->was_above_priority_cutoff_at_last_priority_update()))
535      DCHECK(CompareBackings(previous_backing, backing));
536    if (!backing->CanBeRecycledIfNotInExternalUse())
537      reached_unrecyclable = true;
538    if (reached_unrecyclable)
539      DCHECK(!backing->CanBeRecycledIfNotInExternalUse());
540    else
541      DCHECK(backing->CanBeRecycledIfNotInExternalUse());
542    previous_backing = backing;
543  }
544#endif
545}
546
547const Proxy* PrioritizedResourceManager::ProxyForDebug() const {
548  return proxy_;
549}
550
551}  // namespace cc
552