Right now we have a gigantic DFA that uses way too much memory. Changing the DFANode structure to not use a HashSet would make it a lot smaller.
Created attachment 251337 [details] Patch
Comment on attachment 251337 [details] Patch This patch was work in progress.
Comment on attachment 251337 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=251337&action=review > Source/WebCore/contentextensions/CombinedURLFilters.cpp:46 > +static size_t recursiveMemoryUsed(const std::unique_ptr<PrefixTreeVertex>& node) Seems to me this should take const PrefixTreeVertex&. > Source/WebCore/contentextensions/CombinedURLFilters.cpp:51 > + for (const std::unique_ptr<PrefixTreeVertex>& child : node->edges.values()) Should use auto& here. > Source/WebCore/contentextensions/CombinedURLFilters.cpp:52 > + size += recursiveMemoryUsed(child); Seems a shame to use explicit recursion here since we’re just trying to walk the tree. Is there no non-recursive way to traverse the tree? We could keep an explicit stack, I suppose. > Source/WebCore/contentextensions/CombinedURLFilters.cpp:58 > + return recursiveMemoryUsed(m_prefixTreeRoot); If this is guaranteed to be non-null, then we should just pass *m_prefixTreeRoot. > Source/WebCore/contentextensions/DFA.cpp:58 > + vector.append(dfa.actions[i]); This can be appendUnchecked since you have reserved capacity. > Source/WebCore/contentextensions/DFA.cpp:68 > + vector.append(dfa.transitions[i]); This can be appendUnchecked since you have reserved capacity. > Source/WebCore/contentextensions/DFABytecodeCompiler.cpp:136 > + for (const std::pair<uint8_t, uint32_t>& pair : node.transitions(m_dfa)) { Should use auto& here instead of the long type. > Source/WebCore/contentextensions/DFANode.h:52 > + DFANode() > + : m_actionsStart(0) > + , m_transitionsStart(0) > + , m_actionsLength(0) > + , m_transitionsLength(0) > + , m_flags(0) > + { > + } Should initialize these members where they are defined, then we would not need to define a constructor at all. > Source/WebCore/contentextensions/DFANode.h:70 > + uint32_t m_actionsStart; This is how to do that: uint32_t m_actionsStart { 0 }; > Source/WebCore/contentextensions/NFA.cpp:57 > + size += sizeof(node) > + + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>) > + + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned) > + + node.finalRuleIds.size() * sizeof(uint64_t); Wrong indentation. > Source/WebCore/contentextensions/NFAToDFA.cpp:385 > + dfa.transitions.append(std::pair<uint8_t, uint32_t>(static_cast<uint8_t>(key), targetNodeId)); Should be able to use make_pair or { } syntax and not need to specify the types of the pair. > Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:52 > + for (unsigned i = 0; i < dfa.nodes.size(); ++i) { > + if (!dfa.nodes[i].isKilled()) > ++counter; > } Should use modern for loop now; we couldn’t before.
Created attachment 251351 [details] Patch
(In reply to comment #3) > Seems a shame to use explicit recursion here since we’re just trying to walk > the tree. Is there no non-recursive way to traverse the tree? We could keep > an explicit stack, I suppose. This function is not used except in LOG_LARGE_STRUCTURES to help me debug the memory usage, so speed and efficiency are not important here.
Comment on attachment 251351 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=251351&action=review > Source/WebCore/contentextensions/DFAMinimizer.cpp:73 > + // FIXME: Use the same location to write new transitions followed by unused memory. By the way, Ben if you could get this working that'd be great! :)
Comment on attachment 251351 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=251351&action=review > Source/WebCore/contentextensions/DFA.h:40 > class WEBCORE_EXPORT DFA { Should change this to a struct instead of a class. > Source/WebCore/contentextensions/DFA.h:42 > DFA(); Should omit this and just let the members initialize themselves. > Source/WebCore/contentextensions/DFA.h:54 > + unsigned root; Should initialize this here: unsigned root { 0 }; > Source/WebCore/contentextensions/DFABytecodeCompiler.cpp:130 > + for (const std::pair<uint8_t, uint32_t>& pair : node.transitions(m_dfa)) { Should use const auto& here. > Source/WebCore/contentextensions/DFABytecodeCompiler.cpp:131 > + RELEASE_ASSERT(pair.first < 128); Would be better if this compared with WTF_ARRAY_LENGTH(destinations) instead of 128. > Source/WebCore/contentextensions/DFABytecodeCompiler.cpp:132 > + ASSERT_WITH_MESSAGE(destinations[pair.first] == noDestination, "Transitions should be unique"); I think this assertion would be fine without the message. Are you sure you want that message? > Source/WebCore/contentextensions/DFAMinimizer.cpp:480 > relocationVector.append(i); Since you reserved capacity, you can use appendUnchecked here. > Source/WebCore/contentextensions/DFAMinimizer.h:31 > +#include "DFA.h" Don't need to include DFA.h here. Just forward declare the struct. > Source/WebCore/contentextensions/DFAMinimizer.h:32 > #include <wtf/Vector.h> Don't need to include this header. > Source/WebCore/contentextensions/DFANode.h:43 > class DFANode { This class is super hard to read because it’s got so many functions all mushed together mixed in with implementations. Should paragraph the functions into logical groups, and put the function bodies separate after the class definition, marked inline since you want them inlined. > Source/WebCore/contentextensions/DFANode.h:45 > + Excess blank line here. > Source/WebCore/contentextensions/NFAToDFA.cpp:384 > + RELEASE_ASSERT_WITH_MESSAGE(key <= std::numeric_limits<uint8_t>::max(), "ASCII transition should always fit in 8 bits"); Plain old RELEASE_ASSERT should be fine. I don't think we need this message. Can put it in a comment if you like. > Source/WebCore/contentextensions/NFAToDFA.cpp:391 > + RELEASE_ASSERT_WITH_MESSAGE(transitionsLength <= std::numeric_limits<uint8_t>::max(), "ASCII transition count should always fit in 8 bits"); Plain old RELEASE_ASSERT should be fine. I don't think we need this message. Can put it in a comment if you like.
Created attachment 251393 [details] Patch
Comment on attachment 251393 [details] Patch This latest version is almost functionally ok. It still fails ContentExtensionTest.IgnorePrevious. I'll polish it up, fix that bug, address the comments, and land tomorrow or Friday.
Comment on attachment 251393 [details] Patch Attachment 251393 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.appspot.com/results/4624308198440960 New failing tests: http/tests/contentextensions/loading/main-resource-redirect-blocked.php http/tests/contentextensions/text-track-blocked.html http/tests/contentextensions/popups.html http/tests/contentextensions/subresource-redirect-blocked.html http/tests/contentextensions/media-filtered.html http/tests/contentextensions/block-cookies-basic.html http/tests/contentextensions/whitelist.html http/tests/contentextensions/css-display-none.html http/tests/contentextensions/basic-filter.html http/tests/contentextensions/block-cookies-send.html http/tests/contentextensions/character-set-basic-support.html
Created attachment 251397 [details] Archive of layout-test-results from ews104 for mac-mavericks-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: ews104 Port: mac-mavericks-wk2 Platform: Mac OS X 10.9.5
Comment on attachment 251393 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=251393&action=review I had a quick look. Probably useless to review at this point, this is WIP. > Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:234 > + unsigned actionsStart = dfa.actions.size(); > for (uint64_t actionLocation : universalActionLocations) Since you know the size of universalActionLocations and dfa.actions is big, it would be good to allocate the memory before the loop. > Source/WebCore/contentextensions/DFA.cpp:47 > + + transitions.size() * sizeof(std::pair<uint8_t, uint32_t>) If you want to better pack the transitions, you could have 2 vectors: one for the character, one for the target. > Source/WebCore/contentextensions/DFA.h:54 > + Vector<uint64_t> actions; > + Vector<std::pair<uint8_t, uint32_t>> transitions; > + Vector<DFANode> nodes; > + unsigned root; I am a bit worried about making everything public. That is something JSC does a lot, and it leads to a lot of weird depedencies.
Created attachment 251402 [details] Patch
Comment on attachment 251402 [details] Patch Attachment 251402 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.appspot.com/results/6472748306006016 New failing tests: http/tests/contentextensions/loading/main-resource-redirect-blocked.php http/tests/contentextensions/text-track-blocked.html http/tests/contentextensions/popups.html http/tests/contentextensions/subresource-redirect-blocked.html http/tests/contentextensions/media-filtered.html http/tests/contentextensions/block-cookies-basic.html http/tests/contentextensions/whitelist.html http/tests/contentextensions/css-display-none.html http/tests/contentextensions/basic-filter.html http/tests/contentextensions/block-cookies-send.html http/tests/contentextensions/character-set-basic-support.html
Created attachment 251406 [details] Archive of layout-test-results from ews107 for mac-mavericks-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: ews107 Port: mac-mavericks-wk2 Platform: Mac OS X 10.9.5
Tests definitely pass locally. Not sure what to do.
Comment on attachment 251402 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=251402&action=review The patch is really good. Pretty cool given how little time you had. The tests fail though so I r-. I did not see the error while reviewing :( > Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:137 > + LOG_LARGE_STRUCTURES(actions, actions.size() * sizeof(SerializedActionByte)); Should be actions.capacity(); > Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:169 > + LOG_LARGE_STRUCTURES(parsedRuleList, parsedRuleList.size() * sizeof(ContentExtensionRule)); // Doesn't include strings. > + LOG_LARGE_STRUCTURES(actionLocations, actionLocations.size() * sizeof(unsigned)); capacity() in both cases. > Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:245 > + LOG_LARGE_STRUCTURES(universalActionLocations, universalActionLocations.size() * sizeof(unsigned)); capacity() > Source/WebCore/contentextensions/ContentExtensionCompiler.cpp:260 > + LOG_LARGE_STRUCTURES(bytecode, bytecode.size() * sizeof(uint8_t)); capacity() * sizeof(DFABytecode) > Source/WebCore/contentextensions/ContentExtensionsDebugging.h:38 > +#define LOG_LARGE_STRUCTURES(name, size) /* if (size > 1000000) { WTFLogAlways("NAME: %s SIZE %d", #name, (int)(size)); }; */ Another way would be to have LOG_LARGE_STRUCTURES extend to nothing if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING is zero. > Source/WebCore/contentextensions/DFA.cpp:46 > +// FIXME: Make DFANode.cpp. Oops :) > Source/WebCore/contentextensions/DFAMinimizer.cpp:442 > + hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(&dfa->actions[actionsStart]), actionsLength * sizeof(uint64_t) / sizeof(UChar)); This does not look correct. There is no guarantee the action order will be the same in two nodes. > Source/WebCore/contentextensions/DFANode.h:103 > +// FIXME: Pack this down to 12. __attribute__((packed)) may do the trick but I am a bit worried about it. A loadPair instruction on any attribute would crash. > Source/WebCore/contentextensions/NFAToDFA.cpp:384 > + RELEASE_ASSERT(key <= std::numeric_limits<uint8_t>::max()); Wouldn't <= 127 be good too? > Tools/ChangeLog:6 > + Reviewed by Darin Adler. ? > Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:490 > + // FIXME: This does not make multiple DFAs anymore. Add a test that does. Still a good test, it caught a bug in the minimizer :)
Created attachment 251432 [details] Patch
Created attachment 251433 [details] Patch
(In reply to comment #17) > > Source/WebCore/contentextensions/DFAMinimizer.cpp:442 > > + hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(&dfa->actions[actionsStart]), actionsLength * sizeof(uint64_t) / sizeof(UChar)); > > This does not look correct. There is no guarantee the action order will be > the same in two nodes. I added a FIXME for sorting the actions. For now this is correct because if the order is not the same, then they will also be unequal. Sorting would only make minimization more effective but not more correct. I cannot reproduce the errors on Mavericks. I'm wondering if it's an issue with the EWS bot.
Comment on attachment 251433 [details] Patch Attachment 251433 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.appspot.com/results/6154858985947136 New failing tests: http/tests/contentextensions/loading/main-resource-redirect-blocked.php http/tests/contentextensions/text-track-blocked.html http/tests/contentextensions/popups.html http/tests/contentextensions/subresource-redirect-blocked.html http/tests/contentextensions/media-filtered.html http/tests/contentextensions/block-cookies-basic.html http/tests/contentextensions/whitelist.html http/tests/contentextensions/css-display-none.html http/tests/contentextensions/basic-filter.html http/tests/contentextensions/block-cookies-send.html http/tests/contentextensions/character-set-basic-support.html
Created attachment 251434 [details] Archive of layout-test-results from ews105 for mac-mavericks-wk2 The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews. Bot: ews105 Port: mac-mavericks-wk2 Platform: Mac OS X 10.9.5
Sure enough, there are a bunch of release-only failures. Don't have time to look into them right now. Maybe tonight or tomorrow.
Created attachment 251461 [details] Patch
Inlining ActionKeyHash::equal seemed to be the problem. Not sure why. It should work fine now.
Comment on attachment 251461 [details] Patch Clearing flags on attachment: 251461 Committed r183204: <http://trac.webkit.org/changeset/183204>
All reviewed patches have been landed. Closing bug.