Allow eviction of ImageBitmaps that are created from ImageElements.

Source/core/loader/cache/MemoryCache.cpp

Index: Source/core/loader/cache/MemoryCache.cpp
diff --git a/Source/core/loader/cache/MemoryCache.cpp b/Source/core/loader/cache/MemoryCache.cpp
index 3a2bf6863ddb7ea52c30c71879a129bb9bad2185..e50de5f5a92e4c58ce24af238323532b43130c2b 100644
--- a/Source/core/loader/cache/MemoryCache.cpp
+++ b/Source/core/loader/cache/MemoryCache.cpp
@@ -186,7 +186,8 @@ void MemoryCache::pruneLiveResourcesToSize(unsigned targetSize)
         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
@@ -477,15 +478,42 @@ void MemoryCache::insertInLiveDecodedResourcesList(CachedResource* resource)
     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) {