Service Workers: Cache.keys() does not obey "key insertion order"
Reported by
steffen....@gmail.com,
Jul 13 2016
|
|||||||||
Issue descriptionUserAgent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36 Example URL: https://jsfiddle.net/steffenweber/uf20bemq/ Steps to reproduce the problem: 1. Open https://jsfiddle.net/steffenweber/uf20bemq/ 2. Click "Run" 3. Open Developer Tools console What is the expected behavior? According to the Service Workers specification (https://www.w3.org/TR/service-workers/#cache-keys-method), Cache.keys() is supposed to return keys "in key insertion order". What went wrong? Cache keys are not returned in key insertion order but in a "random" order (probably the result of the underlying implementation using a hashmap or a similar data structure). Does it occur on multiple sites: Yes Is it a problem with a plugin? No Did this work before? No Does this work in other browsers? N/A Chrome version: 53.0.2785.8 Channel: dev OS Version: Flash Version: A similar issue with CacheStorage.keys() seems to have been fixed previously: https://bugs.chromium.org/p/chromium/issues/detail?id=408787 I'm trying to implement an LRU (least-recently-used) pruning algorithm for a cache. I cannot make it work if the keys are not returned in "key insertion order". Can you think of a workaround?
,
Jul 18 2016
,
Jul 19 2016
This should be doable. We can call the disk cache's GetLastModified() on each enumerated entry to determine insertion order.
,
Jul 19 2016
,
Jul 27 2016
,
Jul 27 2016
A nice way to handle this would be to sort the entries by GetLastModified() before running the callback in CacheStorageCache::OpenAllEntries. Then all of the operations that rely on OpenAllEntries will automatically process entries in order.
,
Jul 28 2016
,
Jul 29 2016
Ah, we can't use GetLastModified() because we update JavaScript entries with compiled script. We'll need to use the response time from the protobuf, which means we can't sort until later once we've read the response protobufs and can access response_time.
,
Aug 30 2016
If anyone isn't working on this, can I take this issue?
,
Aug 30 2016
Ah, thanks for asking! I actually have a patch mostly done but I forgot to mark as started.
,
Sep 8 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/92afbef3c43ccd4e0817d03a2166a98342a88d84 commit 92afbef3c43ccd4e0817d03a2166a98342a88d84 Author: jkarlin <jkarlin@chromium.org> Date: Thu Sep 08 14:05:33 2016 [CacheStorage] Sort QueryCache results by time entered into cache The spec says that QueryCache should iterate the request/response pairs in insertion order. The implementation backend (SimpleCache) has an unordered iterator. This CL adds an insertion time to each entry (defaulting to response time for pre-existing entries) and sorts QueryCache results before returning. In order to sort the QueryCache results, I had to clean up "QueryCacheResults": 1) Rename QueryCacheResults -> QueryCacheContext 2) Create a QueryCacheResult which contains a matching request, response, data handle, and entry time 3) QueryCache now returns a sorted std::vector<QueryCacheResult> BUG= 627821 Review-Url: https://codereview.chromium.org/2315253002 Cr-Commit-Position: refs/heads/master@{#417279} [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage.proto [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache.h [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache_unittest.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_dispatcher_host.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/resources/test-helpers.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-delete.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-keys.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-matchAll.js
,
Sep 8 2016
,
Sep 8 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/92afbef3c43ccd4e0817d03a2166a98342a88d84 commit 92afbef3c43ccd4e0817d03a2166a98342a88d84 Author: jkarlin <jkarlin@chromium.org> Date: Thu Sep 08 14:05:33 2016 [CacheStorage] Sort QueryCache results by time entered into cache The spec says that QueryCache should iterate the request/response pairs in insertion order. The implementation backend (SimpleCache) has an unordered iterator. This CL adds an insertion time to each entry (defaulting to response time for pre-existing entries) and sorts QueryCache results before returning. In order to sort the QueryCache results, I had to clean up "QueryCacheResults": 1) Rename QueryCacheResults -> QueryCacheContext 2) Create a QueryCacheResult which contains a matching request, response, data handle, and entry time 3) QueryCache now returns a sorted std::vector<QueryCacheResult> BUG= 627821 Review-Url: https://codereview.chromium.org/2315253002 Cr-Commit-Position: refs/heads/master@{#417279} [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage.proto [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache.h [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_cache_unittest.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/content/browser/cache_storage/cache_storage_dispatcher_host.cc [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/resources/test-helpers.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-delete.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-keys.js [modify] https://crrev.com/92afbef3c43ccd4e0817d03a2166a98342a88d84/third_party/WebKit/LayoutTests/http/tests/cachestorage/script-tests/cache-matchAll.js
,
Sep 14 2016
I can confirm the fix using Chrome 55.0.2859.0 dev (64-bit). Thank you! |
|||||||||
►
Sign in to add a comment |
|||||||||
Comment 1 by dtapu...@chromium.org
, Jul 13 2016