Allow eviction of ImageBitmaps that are created from ImageElements.

Source/core/loader/cache/MemoryCache.cpp

 /*
     Copyright (C) 1998 Lars Knoll (knoll@mpi-hd.mpg.de)
     Copyright (C) 2001 Dirk Mueller (mueller@kde.org)
     Copyright (C) 2002 Waldo Bastian (bastian@kde.org)
     Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
 
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
     License as published by the Free Software Foundation; either
     version 2 of the License, or (at your option) any later version.
@@ skipping 168 matching lines @@
 {
     if (m_inPruneResources)
         return;
     TemporaryChange<bool> reentrancyProtector(m_inPruneResources, true);
 
     double currentTime = FrameView::currentPaintTimeStamp();
     if (!currentTime) // In case prune is called directly, outside of a Frame paint.
         currentTime = WTF::currentTime();
     
     // Destroy any decoded data in live objects that we can.
-    // Start from the tail, since this is the least recently accessed of the objects.
+    // Start from the tail, since this is the lowest priority
+    // and least recently accessed of the objects.
 
     // The list might not be sorted by the m_lastDecodedAccessTime. The impact
     // of this weaker invariant is minor as the below if statement to check the
     // elapsedTime will evaluate to false as the currentTime will be a lot
     // greater than the current->m_lastDecodedAccessTime.
     // For more details see: https://bugs.webkit.org/show_bug.cgi?id=30209
     CachedResource* current = m_liveDecodedResources.m_tail;
     while (current) {
         CachedResource* prev = current->m_prevInLiveResourcesList;
         ASSERT(current->hasClients());
@@ skipping 270 matching lines @@
     else if (m_liveDecodedResources.m_head == resource)
         m_liveDecodedResources.m_head = next;
 }
 
 void MemoryCache::insertInLiveDecodedResourcesList(CachedResource* resource)
 {
     // Make sure we aren't in the list already.
     ASSERT(!resource->m_nextInLiveResourcesList && !resource->m_prevInLiveResourcesList && !resource->m_inLiveDecodedResourcesList);
     resource->m_inLiveDecodedResourcesList = true;
 
-    resource->m_nextInLiveResourcesList = m_liveDecodedResources.m_head;
-    if (m_liveDecodedResources.m_head)
-        m_liveDecodedResources.m_head->m_prevInLiveResourcesList = resource;
-    m_liveDecodedResources.m_head = resource;
-    
-    if (!resource->m_nextInLiveResourcesList)
+    bool inserted = false;
+    for (CachedResource* next = m_liveDecodedResources.m_head; next; next = next->m_nextInLiveResourcesList) {

[Justin Novosad, 2013/07/19 21:09:53]

This algorithm is not good, you are making successive insertion into an O(N^2)
process. You should make m_liveDecodedResources into an array in order to have
one list per priority level. That way successive insertion could still be done
in linear time. IT would also keep the code as almost as simple as before

+        // Insert here if the next item is of the same or lower priority
+        // TODO: make this more efficient by storing separate lists for each priority
+        if (resource->decodeCachePriority() >= next->decodeCachePriority()) {
+            if (CachedResource* prev = next->m_prevInLiveResourcesList) {
+                prev->m_nextInLiveResourcesList = resource;
+                resource->m_prevInLiveResourcesList = prev;
+            }
+            resource->m_nextInLiveResourcesList = next;
+            next->m_prevInLiveResourcesList = resource;
+
+            if (next == m_liveDecodedResources.m_head)
+                m_liveDecodedResources.m_head = resource;
+
+            inserted = true;
+            break;
+        }
+    }
+    if (!inserted) {
+        // The new resource should become the tail
+        if (m_liveDecodedResources.m_tail) {
+            resource->m_prevInLiveResourcesList = m_liveDecodedResources.m_tail;
+            m_liveDecodedResources.m_tail->m_nextInLiveResourcesList = resource;
+        }
         m_liveDecodedResources.m_tail = resource;
-        
+        if (!m_liveDecodedResources.m_head) {
+            m_liveDecodedResources.m_head = resource;
+        }
+    }
+
 #if !ASSERT_DISABLED
+    // Verify that we are in the correct position in the list according to our decodeCachePriority.
+    ASSERT(!resource->m_nextInLiveResourcesList || resource->decodeCachePriority() >= resource->m_nextInLiveResourcesList->decodeCachePriority());
+    ASSERT(!resource->m_prevInLiveResourcesList || resource->decodeCachePriority() <= resource->m_prevInLiveResourcesList->decodeCachePriority());
+
     // Verify that we are in now in the list like we should be.
     bool found = false;
     for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
         if (current == resource) {
             found = true;
             break;
         }
     }
     ASSERT(found);
 #endif
@@ skipping 159 matching lines @@
                 printf("(%.1fK, %.1fK, %uA, %dR, %d, %d); ", current->decodedSize() / 1024.0f, (current->encodedSize() + current->overheadSize()) / 1024.0f, current->accessCount(), current->hasClients(), current->isPurgeable(), current->wasPurged());
 
             current = prev;
         }
     }
 }
 
 #endif // MEMORY_CACHE_STATS
 
 } // namespace WebCore