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::UpdateBackingsInDrawingImplTree() {
164  TRACE_EVENT0("cc",
165               "PrioritizedResourceManager::UpdateBackingsInDrawingImplTree");
166  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
167
168  AssertInvariants();
169  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
170       ++it) {
171    PrioritizedResource::Backing* backing = (*it);
172    backing->UpdateInDrawingImplTree();
173  }
174  SortBackings();
175  AssertInvariants();
176}
177
178void PrioritizedResourceManager::SortBackings() {
179  TRACE_EVENT0("cc", "PrioritizedResourceManager::SortBackings");
180  DCHECK(proxy_->IsImplThread());
181
182  // Put backings in eviction/recycling order.
183  backings_.sort(CompareBackings);
184  backings_tail_not_sorted_ = false;
185}
186
187void PrioritizedResourceManager::ClearPriorities() {
188  DCHECK(proxy_->IsMainThread());
189  for (TextureSet::iterator it = textures_.begin(); it != textures_.end();
190       ++it) {
191    // TODO(reveman): We should remove this and just set all priorities to
192    // PriorityCalculator::lowestPriority() once we have priorities for all
193    // textures (we can't currently calculate distances for off-screen
194    // textures).
195    (*it)->set_request_priority(
196        PriorityCalculator::LingeringPriority((*it)->request_priority()));
197  }
198}
199
200bool PrioritizedResourceManager::RequestLate(PrioritizedResource* texture) {
201  DCHECK(proxy_->IsMainThread());
202
203  // This is already above cutoff, so don't double count it's memory below.
204  if (texture->is_above_priority_cutoff())
205    return true;
206
207  // Allow textures that have priority equal to the cutoff, but not strictly
208  // lower.
209  if (PriorityCalculator::priority_is_lower(texture->request_priority(),
210                                            priority_cutoff_))
211    return false;
212
213  // Disallow textures that do not have a priority strictly higher than the
214  // external cutoff.
215  if (!PriorityCalculator::priority_is_higher(texture->request_priority(),
216                                              external_priority_cutoff_))
217    return false;
218
219  size_t new_memory_bytes = memory_above_cutoff_bytes_ + texture->bytes();
220  if (new_memory_bytes > memory_available_bytes_)
221    return false;
222
223  memory_above_cutoff_bytes_ = new_memory_bytes;
224  texture->set_above_priority_cutoff(true);
225  return true;
226}
227
228void PrioritizedResourceManager::AcquireBackingTextureIfNeeded(
229    PrioritizedResource* texture,
230    ResourceProvider* resource_provider) {
231  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
232  DCHECK(!texture->is_self_managed());
233  DCHECK(texture->is_above_priority_cutoff());
234  if (texture->backing() || !texture->is_above_priority_cutoff())
235    return;
236
237  // Find a backing below, by either recycling or allocating.
238  PrioritizedResource::Backing* backing = NULL;
239
240  // First try to recycle
241  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
242       ++it) {
243    if (!(*it)->CanBeRecycled())
244      break;
245    if (resource_provider->InUseByConsumer((*it)->id()))
246      continue;
247    if ((*it)->size() == texture->size() &&
248        (*it)->format() == texture->format()) {
249      backing = (*it);
250      backings_.erase(it);
251      break;
252    }
253  }
254
255  // Otherwise reduce memory and just allocate a new backing texures.
256  if (!backing) {
257    EvictBackingsToReduceMemory(memory_available_bytes_ - texture->bytes(),
258                                PriorityCalculator::AllowEverythingCutoff(),
259                                EVICT_ONLY_RECYCLABLE,
260                                DO_NOT_UNLINK_BACKINGS,
261                                resource_provider);
262    backing =
263        CreateBacking(texture->size(), texture->format(), resource_provider);
264  }
265
266  // Move the used backing to the end of the eviction list, and note that
267  // the tail is not sorted.
268  if (backing->owner())
269    backing->owner()->Unlink();
270  texture->Link(backing);
271  backings_.push_back(backing);
272  backings_tail_not_sorted_ = true;
273
274  // Update the backing's priority from its new owner.
275  backing->UpdatePriority();
276}
277
278bool PrioritizedResourceManager::EvictBackingsToReduceMemory(
279    size_t limit_bytes,
280    int priority_cutoff,
281    EvictionPolicy eviction_policy,
282    UnlinkPolicy unlink_policy,
283    ResourceProvider* resource_provider) {
284  DCHECK(proxy_->IsImplThread());
285  if (unlink_policy == UNLINK_BACKINGS)
286    DCHECK(proxy_->IsMainThreadBlocked());
287  if (MemoryUseBytes() <= limit_bytes &&
288      PriorityCalculator::AllowEverythingCutoff() == priority_cutoff)
289    return false;
290
291  // Destroy backings until we are below the limit,
292  // or until all backings remaining are above the cutoff.
293  bool evicted_anything = false;
294  while (backings_.size() > 0) {
295    PrioritizedResource::Backing* backing = backings_.front();
296    if (MemoryUseBytes() <= limit_bytes &&
297        PriorityCalculator::priority_is_higher(
298            backing->request_priority_at_last_priority_update(),
299            priority_cutoff))
300      break;
301    if (eviction_policy == EVICT_ONLY_RECYCLABLE && !backing->CanBeRecycled())
302      break;
303    if (unlink_policy == UNLINK_BACKINGS && backing->owner())
304      backing->owner()->Unlink();
305    EvictFirstBackingResource(resource_provider);
306    evicted_anything = true;
307  }
308  return evicted_anything;
309}
310
311void PrioritizedResourceManager::ReduceWastedMemory(
312    ResourceProvider* resource_provider) {
313  // We currently collect backings from deleted textures for later recycling.
314  // However, if we do that forever we will always use the max limit even if
315  // we really need very little memory. This should probably be solved by
316  // reducing the limit externally, but until then this just does some "clean
317  // up" of unused backing textures (any more than 10%).
318  size_t wasted_memory = 0;
319  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
320       ++it) {
321    if ((*it)->owner())
322      break;
323    wasted_memory += (*it)->bytes();
324  }
325  size_t ten_percent_of_memory = memory_available_bytes_ / 10;
326  if (wasted_memory > ten_percent_of_memory)
327    EvictBackingsToReduceMemory(MemoryUseBytes() -
328                                (wasted_memory - ten_percent_of_memory),
329                                PriorityCalculator::AllowEverythingCutoff(),
330                                EVICT_ONLY_RECYCLABLE,
331                                DO_NOT_UNLINK_BACKINGS,
332                                resource_provider);
333}
334
335void PrioritizedResourceManager::ReduceMemory(
336    ResourceProvider* resource_provider) {
337  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
338  EvictBackingsToReduceMemory(memory_available_bytes_,
339                              PriorityCalculator::AllowEverythingCutoff(),
340                              EVICT_ANYTHING,
341                              UNLINK_BACKINGS,
342                              resource_provider);
343  DCHECK_LE(MemoryUseBytes(), memory_available_bytes_);
344
345  ReduceWastedMemory(resource_provider);
346}
347
348void PrioritizedResourceManager::ClearAllMemory(
349    ResourceProvider* resource_provider) {
350  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
351  if (!resource_provider) {
352    DCHECK(backings_.empty());
353    return;
354  }
355  EvictBackingsToReduceMemory(0,
356                              PriorityCalculator::AllowEverythingCutoff(),
357                              EVICT_ANYTHING,
358                              DO_NOT_UNLINK_BACKINGS,
359                              resource_provider);
360}
361
362bool PrioritizedResourceManager::ReduceMemoryOnImplThread(
363    size_t limit_bytes,
364    int priority_cutoff,
365    ResourceProvider* resource_provider) {
366  DCHECK(proxy_->IsImplThread());
367  DCHECK(resource_provider);
368  // If we are in the process of uploading a new frame then the backings at the
369  // very end of the list are not sorted by priority. Sort them before doing the
370  // eviction.
371  if (backings_tail_not_sorted_)
372    SortBackings();
373  return EvictBackingsToReduceMemory(limit_bytes,
374                                     priority_cutoff,
375                                     EVICT_ANYTHING,
376                                     DO_NOT_UNLINK_BACKINGS,
377                                     resource_provider);
378}
379
380void PrioritizedResourceManager::ReduceWastedMemoryOnImplThread(
381    ResourceProvider* resource_provider) {
382  DCHECK(proxy_->IsImplThread());
383  DCHECK(resource_provider);
384  // If we are in the process of uploading a new frame then the backings at the
385  // very end of the list are not sorted by priority. Sort them before doing the
386  // eviction.
387  if (backings_tail_not_sorted_)
388    SortBackings();
389  ReduceWastedMemory(resource_provider);
390}
391
392void PrioritizedResourceManager::UnlinkAndClearEvictedBackings() {
393  DCHECK(proxy_->IsMainThread());
394  base::AutoLock scoped_lock(evicted_backings_lock_);
395  for (BackingList::const_iterator it = evicted_backings_.begin();
396       it != evicted_backings_.end();
397       ++it) {
398    PrioritizedResource::Backing* backing = (*it);
399    if (backing->owner())
400      backing->owner()->Unlink();
401    delete backing;
402  }
403  evicted_backings_.clear();
404}
405
406bool PrioritizedResourceManager::LinkedEvictedBackingsExist() const {
407  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
408  base::AutoLock scoped_lock(evicted_backings_lock_);
409  for (BackingList::const_iterator it = evicted_backings_.begin();
410       it != evicted_backings_.end();
411       ++it) {
412    if ((*it)->owner())
413      return true;
414  }
415  return false;
416}
417
418void PrioritizedResourceManager::RegisterTexture(PrioritizedResource* texture) {
419  DCHECK(proxy_->IsMainThread());
420  DCHECK(texture);
421  DCHECK(!texture->resource_manager());
422  DCHECK(!texture->backing());
423  DCHECK(!ContainsKey(textures_, texture));
424
425  texture->set_manager_internal(this);
426  textures_.insert(texture);
427}
428
429void PrioritizedResourceManager::UnregisterTexture(
430    PrioritizedResource* texture) {
431  DCHECK(proxy_->IsMainThread() ||
432         (proxy_->IsImplThread() && proxy_->IsMainThreadBlocked()));
433  DCHECK(texture);
434  DCHECK(ContainsKey(textures_, texture));
435
436  ReturnBackingTexture(texture);
437  texture->set_manager_internal(NULL);
438  textures_.erase(texture);
439  texture->set_above_priority_cutoff(false);
440}
441
442void PrioritizedResourceManager::ReturnBackingTexture(
443    PrioritizedResource* texture) {
444  DCHECK(proxy_->IsMainThread() ||
445         (proxy_->IsImplThread() && proxy_->IsMainThreadBlocked()));
446  if (texture->backing())
447    texture->Unlink();
448}
449
450PrioritizedResource::Backing* PrioritizedResourceManager::CreateBacking(
451    gfx::Size size,
452    GLenum format,
453    ResourceProvider* resource_provider) {
454  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
455  DCHECK(resource_provider);
456  ResourceProvider::ResourceId resource_id =
457      resource_provider->CreateManagedResource(
458          size, format, ResourceProvider::TextureUsageAny);
459  PrioritizedResource::Backing* backing = new PrioritizedResource::Backing(
460      resource_id, resource_provider, size, format);
461  memory_use_bytes_ += backing->bytes();
462  return backing;
463}
464
465void PrioritizedResourceManager::EvictFirstBackingResource(
466    ResourceProvider* resource_provider) {
467  DCHECK(proxy_->IsImplThread());
468  DCHECK(resource_provider);
469  DCHECK(!backings_.empty());
470  PrioritizedResource::Backing* backing = backings_.front();
471
472  // Note that we create a backing and its resource at the same time, but we
473  // delete the backing structure and its resource in two steps. This is because
474  // we can delete the resource while the main thread is running, but we cannot
475  // unlink backings while the main thread is running.
476  backing->DeleteResource(resource_provider);
477  memory_use_bytes_ -= backing->bytes();
478  backings_.pop_front();
479  base::AutoLock scoped_lock(evicted_backings_lock_);
480  evicted_backings_.push_back(backing);
481}
482
483void PrioritizedResourceManager::AssertInvariants() {
484#ifndef NDEBUG
485  DCHECK(proxy_->IsImplThread() && proxy_->IsMainThreadBlocked());
486
487  // If we hit any of these asserts, there is a bug in this class. To see
488  // where the bug is, call this function at the beginning and end of
489  // every public function.
490
491  // Backings/textures must be doubly-linked and only to other backings/textures
492  // in this manager.
493  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
494       ++it) {
495    if ((*it)->owner()) {
496      DCHECK(ContainsKey(textures_, (*it)->owner()));
497      DCHECK((*it)->owner()->backing() == (*it));
498    }
499  }
500  for (TextureSet::iterator it = textures_.begin(); it != textures_.end();
501       ++it) {
502    PrioritizedResource* texture = (*it);
503    PrioritizedResource::Backing* backing = texture->backing();
504    base::AutoLock scoped_lock(evicted_backings_lock_);
505    if (backing) {
506      if (backing->ResourceHasBeenDeleted()) {
507        DCHECK(std::find(backings_.begin(), backings_.end(), backing) ==
508               backings_.end());
509        DCHECK(std::find(evicted_backings_.begin(),
510                         evicted_backings_.end(),
511                         backing) != evicted_backings_.end());
512      } else {
513        DCHECK(std::find(backings_.begin(), backings_.end(), backing) !=
514               backings_.end());
515        DCHECK(std::find(evicted_backings_.begin(),
516                         evicted_backings_.end(),
517                         backing) == evicted_backings_.end());
518      }
519      DCHECK(backing->owner() == texture);
520    }
521  }
522
523  // At all times, backings that can be evicted must always come before
524  // backings that can't be evicted in the backing texture list (otherwise
525  // ReduceMemory will not find all textures available for eviction/recycling).
526  bool reached_unrecyclable = false;
527  PrioritizedResource::Backing* previous_backing = NULL;
528  for (BackingList::iterator it = backings_.begin(); it != backings_.end();
529       ++it) {
530    PrioritizedResource::Backing* backing = *it;
531    if (previous_backing &&
532        (!backings_tail_not_sorted_ ||
533         !backing->was_above_priority_cutoff_at_last_priority_update()))
534      DCHECK(CompareBackings(previous_backing, backing));
535    if (!backing->CanBeRecycled())
536      reached_unrecyclable = true;
537    if (reached_unrecyclable)
538      DCHECK(!backing->CanBeRecycled());
539    else
540      DCHECK(backing->CanBeRecycled());
541    previous_backing = backing;
542  }
543#endif
544}
545
546const Proxy* PrioritizedResourceManager::ProxyForDebug() const {
547  return proxy_;
548}
549
550}  // namespace cc
551