<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[180207] trunk/Source/WebCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/180207">180207</a></dd>
<dt>Author</dt> <dd>cdumez@apple.com</dd>
<dt>Date</dt> <dd>2015-02-16 20:54:56 -0800 (Mon, 16 Feb 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Keep all memory cache resources in ListHashSets
https://bugs.webkit.org/show_bug.cgi?id=141667
Reviewed by Andreas Kling.
Keep all memory cache resources in ListHashSets instead of manual linked
lists. This simplifies the code a lot and is also more efficient for
retrieving / removing particular CachedResources.
* loader/cache/CachedResource.cpp:
(WebCore::CachedResource::CachedResource):
* loader/cache/CachedResource.h:
* loader/cache/MemoryCache.cpp:
(WebCore::MemoryCache::pruneDeadResourcesToSize):
(WebCore::MemoryCache::removeFromLRUList):
(WebCore::MemoryCache::insertInLRUList):
(WebCore::MemoryCache::dumpLRULists):
(WebCore::MemoryCache::lruListFor): Deleted.
* loader/cache/MemoryCache.h:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoreloadercacheCachedResourcecpp">trunk/Source/WebCore/loader/cache/CachedResource.cpp</a></li>
<li><a href="#trunkSourceWebCoreloadercacheCachedResourceh">trunk/Source/WebCore/loader/cache/CachedResource.h</a></li>
<li><a href="#trunkSourceWebCoreloadercacheMemoryCachecpp">trunk/Source/WebCore/loader/cache/MemoryCache.cpp</a></li>
<li><a href="#trunkSourceWebCoreloadercacheMemoryCacheh">trunk/Source/WebCore/loader/cache/MemoryCache.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (180206 => 180207)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-02-17 04:26:58 UTC (rev 180206)
+++ trunk/Source/WebCore/ChangeLog 2015-02-17 04:54:56 UTC (rev 180207)
</span><span class="lines">@@ -1,3 +1,25 @@
</span><ins>+2015-02-16 Chris Dumez <cdumez@apple.com>
+
+ Keep all memory cache resources in ListHashSets
+ https://bugs.webkit.org/show_bug.cgi?id=141667
+
+ Reviewed by Andreas Kling.
+
+ Keep all memory cache resources in ListHashSets instead of manual linked
+ lists. This simplifies the code a lot and is also more efficient for
+ retrieving / removing particular CachedResources.
+
+ * loader/cache/CachedResource.cpp:
+ (WebCore::CachedResource::CachedResource):
+ * loader/cache/CachedResource.h:
+ * loader/cache/MemoryCache.cpp:
+ (WebCore::MemoryCache::pruneDeadResourcesToSize):
+ (WebCore::MemoryCache::removeFromLRUList):
+ (WebCore::MemoryCache::insertInLRUList):
+ (WebCore::MemoryCache::dumpLRULists):
+ (WebCore::MemoryCache::lruListFor): Deleted.
+ * loader/cache/MemoryCache.h:
+
</ins><span class="cx"> 2015-02-16 Benjamin Poulain <benjamin@webkit.org>
</span><span class="cx">
</span><span class="cx"> CSS JIT: finish :nth-last-child()
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheCachedResourcecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/CachedResource.cpp (180206 => 180207)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/CachedResource.cpp 2015-02-17 04:26:58 UTC (rev 180206)
+++ trunk/Source/WebCore/loader/cache/CachedResource.cpp 2015-02-17 04:54:56 UTC (rev 180207)
</span><span class="lines">@@ -135,8 +135,6 @@
</span><span class="cx"> , m_deleted(false)
</span><span class="cx"> , m_lruIndex(0)
</span><span class="cx"> #endif
</span><del>- , m_nextInAllResourcesList(0)
- , m_prevInAllResourcesList(0)
</del><span class="cx"> , m_owningCachedResourceLoader(0)
</span><span class="cx"> , m_resourceToRevalidate(0)
</span><span class="cx"> , m_proxyResource(0)
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheCachedResourceh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/CachedResource.h (180206 => 180207)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/CachedResource.h 2015-02-17 04:26:58 UTC (rev 180206)
+++ trunk/Source/WebCore/loader/cache/CachedResource.h 2015-02-17 04:54:56 UTC (rev 180207)
</span><span class="lines">@@ -319,9 +319,6 @@
</span><span class="cx"> unsigned m_lruIndex;
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- CachedResource* m_nextInAllResourcesList;
- CachedResource* m_prevInAllResourcesList;
-
</del><span class="cx"> CachedResourceLoader* m_owningCachedResourceLoader; // only non-null for resources that are not in the cache
</span><span class="cx">
</span><span class="cx"> // If this field is non-null we are using the resource as a proxy for checking whether an existing resource is still up to date
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheMemoryCachecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/MemoryCache.cpp (180206 => 180207)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/MemoryCache.cpp 2015-02-17 04:26:58 UTC (rev 180206)
+++ trunk/Source/WebCore/loader/cache/MemoryCache.cpp 2015-02-17 04:54:56 UTC (rev 180207)
</span><span class="lines">@@ -347,59 +347,69 @@
</span><span class="cx"> if (m_inPruneResources)
</span><span class="cx"> return;
</span><span class="cx"> TemporaryChange<bool> reentrancyProtector(m_inPruneResources, true);
</span><del>-
- int size = m_allResources.size();
</del><span class="cx">
</span><span class="cx"> if (targetSize && m_deadSize <= targetSize)
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> bool canShrinkLRULists = true;
</span><del>- for (int i = size - 1; i >= 0; i--) {
- // Remove from the tail, since this is the least frequently accessed of the objects.
- CachedResource* current = m_allResources[i].m_tail;
-
</del><ins>+ for (int i = m_allResources.size() - 1; i >= 0; i--) {
+ LRUList& list = *m_allResources[i];
+
</ins><span class="cx"> // First flush all the decoded data in this queue.
</span><del>- while (current) {
- // Protect 'previous' so it can't get deleted during destroyDecodedData().
- CachedResourceHandle<CachedResource> previous = current->m_prevInAllResourcesList;
- ASSERT(!previous || previous->inCache());
- if (!current->hasClients() && !current->isPreloaded() && current->isLoaded()) {
</del><ins>+ // Remove from the head, since this is the least frequently accessed of the objects.
+ auto it = list.begin();
+ while (it != list.end()) {
+ CachedResource& current = **it;
+
+ // Increment the iterator now as the call to destroyDecodedData() below may
+ // invalidate the current iterator.
+ ++it;
+
+ // Protect 'next' so it can't get deleted during destroyDecodedData().
+ CachedResourceHandle<CachedResource> next = it != list.end() ? *it : nullptr;
+ ASSERT(!next || next->inCache());
+ if (!current.hasClients() && !current.isPreloaded() && current.isLoaded()) {
</ins><span class="cx"> // Destroy our decoded data. This will remove us from
</span><span class="cx"> // m_liveDecodedResources, and possibly move us to a different
</span><span class="cx"> // LRU list in m_allResources.
</span><del>- current->destroyDecodedData();
</del><ins>+ current.destroyDecodedData();
</ins><span class="cx">
</span><span class="cx"> if (targetSize && m_deadSize <= targetSize)
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>- // Decoded data may reference other resources. Stop iterating if 'previous' somehow got
</del><ins>+ // Decoded data may reference other resources. Stop iterating if 'next' somehow got
</ins><span class="cx"> // kicked out of cache during destroyDecodedData().
</span><del>- if (previous && !previous->inCache())
</del><ins>+ if (next && !next->inCache())
</ins><span class="cx"> break;
</span><del>- current = previous.get();
</del><span class="cx"> }
</span><span class="cx">
</span><del>- // Now evict objects from this queue.
- current = m_allResources[i].m_tail;
- while (current) {
- CachedResourceHandle<CachedResource> previous = current->m_prevInAllResourcesList;
- ASSERT(!previous || previous->inCache());
- if (!current->hasClients() && !current->isPreloaded() && !current->isCacheValidator()) {
- remove(*current);
</del><ins>+ // Now evict objects from this list.
+ // Remove from the head, since this is the least frequently accessed of the objects.
+ it = list.begin();
+ while (it != list.end()) {
+ CachedResource& current = **it;
+
+ // Increment the iterator now as the call to remove() below will
+ // invalidate the current iterator.
+ ++it;
+
+ CachedResourceHandle<CachedResource> next = it != list.end() ? *it : nullptr;
+ ASSERT(!next || next->inCache());
+ if (!current.hasClients() && !current.isPreloaded() && !current.isCacheValidator()) {
+ remove(current);
</ins><span class="cx"> if (targetSize && m_deadSize <= targetSize)
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>- if (previous && !previous->inCache())
</del><ins>+ if (next && !next->inCache())
</ins><span class="cx"> break;
</span><del>- current = previous.get();
</del><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Shrink the vector back down so we don't waste time inspecting
</span><span class="cx"> // empty LRU lists on future prunes.
</span><del>- if (m_allResources[i].m_head)
</del><ins>+ if (!m_allResources[i]->isEmpty())
</ins><span class="cx"> canShrinkLRULists = false;
</span><span class="cx"> else if (canShrinkLRULists)
</span><del>- m_allResources.resize(i);
</del><ins>+ m_allResources.shrink(i);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -445,16 +455,18 @@
</span><span class="cx"> resource.deleteIfPossible();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-MemoryCache::LRUList* MemoryCache::lruListFor(CachedResource& resource)
</del><ins>+auto MemoryCache::lruListFor(CachedResource& resource) -> LRUList&
</ins><span class="cx"> {
</span><span class="cx"> unsigned accessCount = std::max(resource.accessCount(), 1U);
</span><span class="cx"> unsigned queueIndex = WTF::fastLog2(resource.size() / accessCount);
</span><span class="cx"> #ifndef NDEBUG
</span><span class="cx"> resource.m_lruIndex = queueIndex;
</span><span class="cx"> #endif
</span><del>- if (m_allResources.size() <= queueIndex)
- m_allResources.grow(queueIndex + 1);
- return &m_allResources[queueIndex];
</del><ins>+
+ m_allResources.reserveCapacity(queueIndex + 1);
+ while (m_allResources.size() <= queueIndex)
+ m_allResources.uncheckedAppend(std::make_unique<LRUList>());
+ return *m_allResources[queueIndex];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MemoryCache::removeFromLRUList(CachedResource& resource)
</span><span class="lines">@@ -467,73 +479,22 @@
</span><span class="cx"> unsigned oldListIndex = resource.m_lruIndex;
</span><span class="cx"> #endif
</span><span class="cx">
</span><del>- LRUList* list = lruListFor(resource);
</del><ins>+ LRUList& list = lruListFor(resource);
</ins><span class="cx">
</span><del>-#if !ASSERT_DISABLED
</del><span class="cx"> // Verify that the list we got is the list we want.
</span><span class="cx"> ASSERT(resource.m_lruIndex == oldListIndex);
</span><span class="cx">
</span><del>- // Verify that we are in fact in this list.
- bool found = false;
- for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
- if (current == &resource) {
- found = true;
- break;
- }
- }
- ASSERT(found);
-#endif
-
- CachedResource* next = resource.m_nextInAllResourcesList;
- CachedResource* prev = resource.m_prevInAllResourcesList;
-
- if (!next && !prev && list->m_head != &resource)
- return;
-
- resource.m_nextInAllResourcesList = nullptr;
- resource.m_prevInAllResourcesList = nullptr;
-
- if (next)
- next->m_prevInAllResourcesList = prev;
- else if (list->m_tail == &resource)
- list->m_tail = prev;
-
- if (prev)
- prev->m_nextInAllResourcesList = next;
- else if (list->m_head == &resource)
- list->m_head = next;
</del><ins>+ bool removed = list.remove(&resource);
+ ASSERT_UNUSED(removed, removed);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MemoryCache::insertInLRUList(CachedResource& resource)
</span><span class="cx"> {
</span><del>- // Make sure we aren't in some list already.
- ASSERT(!resource.m_nextInAllResourcesList && !resource.m_prevInAllResourcesList);
</del><span class="cx"> ASSERT(resource.inCache());
</span><span class="cx"> ASSERT(resource.accessCount() > 0);
</span><span class="cx">
</span><del>- LRUList* list = lruListFor(resource);
-
- resource.m_nextInAllResourcesList = list->m_head;
- if (list->m_head)
- list->m_head->m_prevInAllResourcesList = &resource;
- list->m_head = &resource;
-
- if (!resource.m_nextInAllResourcesList)
- list->m_tail = &resource;
-
-#if !ASSERT_DISABLED
- // Verify that we are in now in the list like we should be.
- list = lruListFor(resource);
- bool found = false;
- for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
- if (current == &resource) {
- found = true;
- break;
- }
- }
- ASSERT(found);
-#endif
-
</del><ins>+ auto addResult = lruListFor(resource).add(&resource);
+ ASSERT_UNUSED(addResult, addResult.isNewEntry);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void MemoryCache::resourceAccessed(CachedResource& resource)
</span><span class="lines">@@ -751,13 +712,9 @@
</span><span class="cx"> int size = m_allResources.size();
</span><span class="cx"> for (int i = size - 1; i >= 0; i--) {
</span><span class="cx"> printf("\n\nList %d: ", i);
</span><del>- CachedResource* current = m_allResources[i].m_tail;
- while (current) {
- CachedResource* prev = current->m_prevInAllResourcesList;
- if (includeLive || !current->hasClients())
- printf("(%.1fK, %.1fK, %uA, %dR); ", current->decodedSize() / 1024.0f, (current->encodedSize() + current->overheadSize()) / 1024.0f, current->accessCount(), current->hasClients());
-
- current = prev;
</del><ins>+ for (auto* resource : *m_allResources[i]) {
+ if (includeLive || !resource->hasClients())
+ printf("(%.1fK, %.1fK, %uA, %dR); ", resource->decodedSize() / 1024.0f, (resource->encodedSize() + resource->overheadSize()) / 1024.0f, resource->accessCount(), resource->hasClients());
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCoreloadercacheMemoryCacheh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/loader/cache/MemoryCache.h (180206 => 180207)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/loader/cache/MemoryCache.h 2015-02-17 04:26:58 UTC (rev 180206)
+++ trunk/Source/WebCore/loader/cache/MemoryCache.h 2015-02-17 04:54:56 UTC (rev 180207)
</span><span class="lines">@@ -166,19 +166,15 @@
</span><span class="cx"> #else
</span><span class="cx"> typedef HashMap<URL, CachedResource*> CachedResourceMap;
</span><span class="cx"> #endif
</span><ins>+ typedef ListHashSet<CachedResource*> LRUList;
</ins><span class="cx">
</span><del>- struct LRUList {
- CachedResource* m_head {nullptr};
- CachedResource* m_tail {nullptr};
- };
-
</del><span class="cx"> WEBCORE_EXPORT void pruneDeadResourcesToSize(unsigned targetSize);
</span><span class="cx"> WEBCORE_EXPORT void pruneLiveResourcesToSize(unsigned targetSize, bool shouldDestroyDecodedDataForAllLiveResources = false);
</span><span class="cx">
</span><span class="cx"> MemoryCache();
</span><span class="cx"> ~MemoryCache(); // Not implemented to make sure nobody accidentally calls delete -- WebCore does not delete singletons.
</span><span class="cx">
</span><del>- LRUList* lruListFor(CachedResource&);
</del><ins>+ LRUList& lruListFor(CachedResource&);
</ins><span class="cx"> #ifndef NDEBUG
</span><span class="cx"> void dumpStats();
</span><span class="cx"> void dumpLRULists(bool includeLive) const;
</span><span class="lines">@@ -206,10 +202,10 @@
</span><span class="cx"> // Size-adjusted and popularity-aware LRU list collection for cache objects. This collection can hold
</span><span class="cx"> // more resources than the cached resource map, since it can also hold "stale" multiple versions of objects that are
</span><span class="cx"> // waiting to die when the clients referencing them go away.
</span><del>- Vector<LRUList, 32> m_allResources;
</del><ins>+ Vector<std::unique_ptr<LRUList>, 32> m_allResources;
</ins><span class="cx">
</span><span class="cx"> // List just for live resources with decoded data. Access to this list is based off of painting the resource.
</span><del>- ListHashSet<CachedResource*> m_liveDecodedResources;
</del><ins>+ LRUList m_liveDecodedResources;
</ins><span class="cx">
</span><span class="cx"> // A URL-based map of all resources that are in the cache (including the freshest version of objects that are currently being
</span><span class="cx"> // referenced by a Web page).
</span></span></pre>
</div>
</div>
</body>
</html>