53665 2011-02-03 00:45:40 -0800 Make XSSFilter go fast by adding a SuffixTree 2011-02-04 02:40:44 -0800 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Other OS X 10.5 RESOLVED FIXED P2 Normal --- 49845 1 abarth abarth abarth dbates eric webkit.review.bot oldest_to_newest 344561 0 abarth 2011-02-03 00:45:40 -0800 Make XSSFilter go fast by adding a SuffixTree 344564 1 81038 abarth 2011-02-03 00:46:46 -0800 Created attachment 81038 Patch 344566 2 81038 eric 2011-02-03 00:48:42 -0800 Comment on attachment 81038 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=81038&action=review > Source/WebCore/html/parser/XSSFilter.cpp:146 > + const size_t miniumLengthForSuffixTree = 512; // FIXME: Tune this parameter. How would we tune it? > Source/WebCore/html/parser/XSSFilter.cpp:183 > + m_decodedHTTPBodySuffixTree = adoptPtr(new SuffixTree<ASCIICodebook>(m_decodedHTTPBody, suffixTreeDepth)); No create? 344568 3 81038 abarth 2011-02-03 00:54:24 -0800 Comment on attachment 81038 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=81038&action=review >> Source/WebCore/html/parser/XSSFilter.cpp:146 >> + const size_t miniumLengthForSuffixTree = 512; // FIXME: Tune this parameter. > > How would we tune it? Dunno. With some sort of benchmark. >> Source/WebCore/html/parser/XSSFilter.cpp:183 >> + m_decodedHTTPBodySuffixTree = adoptPtr(new SuffixTree<ASCIICodebook>(m_decodedHTTPBody, suffixTreeDepth)); > > No create? It's adoptPtr, not adoptRef. We could add a create method, but we don't usually. 345100 4 81134 abarth 2011-02-03 16:11:21 -0800 Created attachment 81134 Patch 345115 5 81134 eric 2011-02-03 16:24:26 -0800 Comment on attachment 81134 Patch What's the perf improvement? 345116 6 abarth 2011-02-03 16:26:17 -0800 https://bugs.webkit.org/show_bug.cgi?id=36694 345121 7 abarth 2011-02-03 16:29:00 -0800 We can add these benchmarks to PerformanceTests/XSSFilter if you like. 345123 8 eric 2011-02-03 16:30:03 -0800 (In reply to comment #7) > We can add these benchmarks to PerformanceTests/XSSFilter if you like. I would very much like that. As is, there is too much hidden-knowledge around the filter. Adding the perf tests to a common place makes it easier for others to hack on this (and possibly make it even faster). 345124 9 81134 eric 2011-02-03 16:31:02 -0800 Comment on attachment 81134 Patch OK. I look forward to you landing the perf tests. 345142 10 abarth 2011-02-03 16:42:13 -0800 Committed r77560: <http://trac.webkit.org/changeset/77560> 345241 11 abarth 2011-02-03 18:41:18 -0800 Perf test in https://bugs.webkit.org/show_bug.cgi?id=53741 345421 12 webkit.review.bot 2011-02-04 02:40:44 -0800 http://trac.webkit.org/changeset/77560 might have broken GTK Linux 32-bit Release, GTK Linux 32-bit Debug, and GTK Linux 64-bit Debug The following tests are not passing: fast/events/pagehide-timeout.html 81038 2011-02-03 00:46:46 -0800 2011-02-03 16:11:18 -0800 Patch bug-53665-20110203004644.patch text/plain 3369 abarth ZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZyBiL1NvdXJjZS9XZWJDb3JlL0No YW5nZUxvZwppbmRleCA4MjhmNTE4NzI1OTI0MjBlZGYyNmEyMDI5YWQzYzIwODIxNWQ4Nzg1Li5m YTQ0ZTg4MjM5ZWQ3NzUyYzg2OThhMzY1YTFiNzFlZWJlN2U3OTRjIDEwMDY0NAotLS0gYS9Tb3Vy Y2UvV2ViQ29yZS9DaGFuZ2VMb2cKKysrIGIvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCkBAIC0y LDYgKzIsMjEgQEAKIAogICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KIAorICAg ICAgICBNYWtlIFhTU0ZpbHRlciBnbyBmYXN0IGJ5IGFkZGluZyBhIFN1ZmZpeFRyZWUKKyAgICAg ICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTUzNjY1CisKKyAgICAg ICAgVGhlIFN1ZmZpeFRyZWUgbGV0cyB1cyBxdWlja2x5IHJlamVjdCBzbmlwcGV0cyBpZiB0aGUg UE9TVCBkYXRhIGlzCisgICAgICAgIGxhcmdlIChiZWNhdXNlIHdlIGNhbiBhdm9pZCBhIGxpbmVh ciBzY2FuIG92ZXIgdGhlIFBPU1QgZGF0YSkuCisKKyAgICAgICAgKiBodG1sL3BhcnNlci9YU1NG aWx0ZXIuY3BwOgorICAgICAgICAoV2ViQ29yZTo6WFNTRmlsdGVyOjppbml0KToKKyAgICAgICAg KFdlYkNvcmU6OlhTU0ZpbHRlcjo6aXNDb250YWluZWRJblJlcXVlc3QpOgorICAgICAgICAqIGh0 bWwvcGFyc2VyL1hTU0ZpbHRlci5oOgorCisyMDExLTAyLTAzICBBZGFtIEJhcnRoICA8YWJhcnRo QHdlYmtpdC5vcmc+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisKICAg ICAgICAgWFNTRmlsdGVyIHNob3VsZG4ndCBib3RoZXIgdG8gYW5hbHl6ZSBwYWdlcyB3aXRob3V0 ICJpbmplY3Rpb24iCiAgICAgICAgIGNoYXJhY3RlcnMgaW4gdGhlIHJlcXVlc3QKICAgICAgICAg aHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTUzNjY0CmRpZmYgLS1naXQg YS9Tb3VyY2UvV2ViQ29yZS9odG1sL3BhcnNlci9YU1NGaWx0ZXIuY3BwIGIvU291cmNlL1dlYkNv cmUvaHRtbC9wYXJzZXIvWFNTRmlsdGVyLmNwcAppbmRleCA0MmNkZjU0MjdjZDI2YWYxNWQwMTg5 NjdlMzhmMzI3MTUwMjcwNDlhLi40MTcwMmEzNzFhZTRmMjNiMGRmZDUyMjQwMzgyNzE4NGFmYzc0 MmIyIDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9odG1sL3BhcnNlci9YU1NGaWx0ZXIuY3Bw CisrKyBiL1NvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5jcHAKQEAgLTE0Myw2 ICsxNDMsOSBAQCBYU1NGaWx0ZXI6OlhTU0ZpbHRlcihIVE1MRG9jdW1lbnRQYXJzZXIqIHBhcnNl cikKIAogdm9pZCBYU1NGaWx0ZXI6OmluaXQoKQogeworICAgIGNvbnN0IHNpemVfdCBtaW5pdW1M ZW5ndGhGb3JTdWZmaXhUcmVlID0gNTEyOyAvLyBGSVhNRTogVHVuZSB0aGlzIHBhcmFtZXRlci4K KyAgICBjb25zdCBpbnQgc3VmZml4VHJlZURlcHRoID0gNTsKKwogICAgIEFTU0VSVCghbV9pc0lu aXRpYWxpemVkKTsKICAgICBBU1NFUlQobV9zdGF0ZSA9PSBJbml0aWFsKTsKICAgICBtX2lzSW5p dGlhbGl6ZWQgPSB0cnVlOwpAQCAtMTc2LDYgKzE3OSw4IEBAIHZvaWQgWFNTRmlsdGVyOjppbml0 KCkKICAgICAgICAgICAgIG1fZGVjb2RlZEhUVFBCb2R5ID0gZGVjb2RlVVJMKGh0dHBCb2R5LT5m bGF0dGVuVG9TdHJpbmcoKSwgZW5jb2RpbmcpOwogICAgICAgICAgICAgaWYgKG1fZGVjb2RlZEhU VFBCb2R5LmZpbmQoaXNSZXF1aXJlZEZvckluamVjdGlvbiwgMCkgPT0gbm90Rm91bmQpCiAgICAg ICAgICAgICAgICAgbV9kZWNvZGVkSFRUUEJvZHkgPSBTdHJpbmcoKTsKKyAgICAgICAgICAgIGlm IChtX2RlY29kZWRIVFRQQm9keS5sZW5ndGgoKSA+PSBtaW5pdW1MZW5ndGhGb3JTdWZmaXhUcmVl KQorICAgICAgICAgICAgICAgIG1fZGVjb2RlZEhUVFBCb2R5U3VmZml4VHJlZSA9IGFkb3B0UHRy KG5ldyBTdWZmaXhUcmVlPEFTQ0lJQ29kZWJvb2s+KG1fZGVjb2RlZEhUVFBCb2R5LCBzdWZmaXhU cmVlRGVwdGgpKTsKICAgICAgICAgfQogICAgIH0KIApAQCAtNDI0LDggKzQyOSwxMSBAQCBib29s IFhTU0ZpbHRlcjo6aXNDb250YWluZWRJblJlcXVlc3QoY29uc3QgU3RyaW5nJiBzbmlwcGV0KQog ICAgIEFTU0VSVCghc25pcHBldC5pc0VtcHR5KCkpOwogICAgIFN0cmluZyBjYW5vbmljYWxpemVk U25pcHBldCA9IGNhbm9uaWNhbGl6ZShzbmlwcGV0KTsKICAgICBBU1NFUlQoIWNhbm9uaWNhbGl6 ZWRTbmlwcGV0LmlzRW1wdHkoKSk7Ci0gICAgcmV0dXJuIG1fZGVjb2RlZFVSTC5maW5kKGNhbm9u aWNhbGl6ZWRTbmlwcGV0LCAwLCBmYWxzZSkgIT0gbm90Rm91bmQKLSAgICAgICAgfHwgbV9kZWNv ZGVkSFRUUEJvZHkuZmluZChjYW5vbmljYWxpemVkU25pcHBldCwgMCwgZmFsc2UpICE9IG5vdEZv dW5kOworICAgIGlmIChtX2RlY29kZWRVUkwuZmluZChjYW5vbmljYWxpemVkU25pcHBldCwgMCwg ZmFsc2UpICE9IG5vdEZvdW5kKQorICAgICAgICByZXR1cm4gdHJ1ZTsKKyAgICBpZiAobV9kZWNv ZGVkSFRUUEJvZHlTdWZmaXhUcmVlICYmICFtX2RlY29kZWRIVFRQQm9keVN1ZmZpeFRyZWUtPm1p Z2h0Q29udGFpbihjYW5vbmljYWxpemVkU25pcHBldCkpCisgICAgICAgIHJldHVybiBmYWxzZTsK KyAgICByZXR1cm4gbV9kZWNvZGVkSFRUUEJvZHkuZmluZChjYW5vbmljYWxpemVkU25pcHBldCwg MCwgZmFsc2UpICE9IG5vdEZvdW5kOwogfQogCiBib29sIFhTU0ZpbHRlcjo6aXNTYW1lT3JpZ2lu UmVzb3VyY2UoY29uc3QgU3RyaW5nJiB1cmwpCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9o dG1sL3BhcnNlci9YU1NGaWx0ZXIuaCBiL1NvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0Zp bHRlci5oCmluZGV4IGY3YmMwMjA2ZmJhNmJkNGUzZTVhOGIzMTBhNWI3OWI4NzRkMTUyYjkuLmY5 NzM5NmM0MWM3YzhmZWQyODBhMTgwOTM4YTZkYzBkN2M4YzgwYTggMTAwNjQ0Ci0tLSBhL1NvdXJj ZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5oCisrKyBiL1NvdXJjZS9XZWJDb3JlL2h0 bWwvcGFyc2VyL1hTU0ZpbHRlci5oCkBAIC0yOCw2ICsyOCw3IEBACiAKICNpbmNsdWRlICJIVE1M VG9rZW4uaCIKICNpbmNsdWRlICJIVFRQUGFyc2Vycy5oIgorI2luY2x1ZGUgIlN1ZmZpeFRyZWUu aCIKIAogbmFtZXNwYWNlIFdlYkNvcmUgewogCkBAIC03NSw2ICs3Niw3IEBAIHByaXZhdGU6CiAK ICAgICBTdHJpbmcgbV9kZWNvZGVkVVJMOwogICAgIFN0cmluZyBtX2RlY29kZWRIVFRQQm9keTsK KyAgICBPd25QdHI8U3VmZml4VHJlZTxBU0NJSUNvZGVib29rPiA+IG1fZGVjb2RlZEhUVFBCb2R5 U3VmZml4VHJlZTsKIAogICAgIFN0YXRlIG1fc3RhdGU7CiAgICAgU3RyaW5nIG1fY2FjaGVkU25p cHBldDsK 81134 2011-02-03 16:11:21 -0800 2011-02-03 16:31:01 -0800 Patch bug-53665-20110203161120.patch text/plain 3063 abarth SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDc3NTQ1KQorKysgU291cmNlL1dlYkNvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMTggQEAKKzIwMTEtMDItMDMgIEFkYW0gQmFy dGggIDxhYmFydGhAd2Via2l0Lm9yZz4KKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9P UFMhKS4KKworICAgICAgICBNYWtlIFhTU0ZpbHRlciBnbyBmYXN0IGJ5IGFkZGluZyBhIFN1ZmZp eFRyZWUKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTUz NjY1CisKKyAgICAgICAgVGhlIFN1ZmZpeFRyZWUgbGV0cyB1cyBxdWlja2x5IHJlamVjdCBzbmlw cGV0cyBpZiB0aGUgUE9TVCBkYXRhIGlzCisgICAgICAgIGxhcmdlIChiZWNhdXNlIHdlIGNhbiBh dm9pZCBhIGxpbmVhciBzY2FuIG92ZXIgdGhlIFBPU1QgZGF0YSkuCisKKyAgICAgICAgKiBodG1s L3BhcnNlci9YU1NGaWx0ZXIuY3BwOgorICAgICAgICAoV2ViQ29yZTo6WFNTRmlsdGVyOjppbml0 KToKKyAgICAgICAgKFdlYkNvcmU6OlhTU0ZpbHRlcjo6aXNDb250YWluZWRJblJlcXVlc3QpOgor ICAgICAgICAqIGh0bWwvcGFyc2VyL1hTU0ZpbHRlci5oOgorCiAyMDExLTAyLTAzICBBZGFtIEJh cnRoICA8YWJhcnRoQHdlYmtpdC5vcmc+CiAKICAgICAgICAgUmV2aWV3ZWQgYnkgRGFuaWVsIEJh dGVzLgpJbmRleDogU291cmNlL1dlYkNvcmUvaHRtbC9wYXJzZXIvWFNTRmlsdGVyLmNwcAo9PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09Ci0tLSBTb3VyY2UvV2ViQ29yZS9odG1sL3BhcnNlci9YU1NGaWx0ZXIuY3BwCShyZXZp c2lvbiA3NzU0NSkKKysrIFNvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5jcHAJ KHdvcmtpbmcgY29weSkKQEAgLTE0Miw2ICsxNDIsOSBAQCBYU1NGaWx0ZXI6OlhTU0ZpbHRlcihI VE1MRG9jdW1lbnRQYXJzZXIqCiAKIHZvaWQgWFNTRmlsdGVyOjppbml0KCkKIHsKKyAgICBjb25z dCBzaXplX3QgbWluaXVtTGVuZ3RoRm9yU3VmZml4VHJlZSA9IDUxMjsgLy8gRklYTUU6IFR1bmUg dGhpcyBwYXJhbWV0ZXIuCisgICAgY29uc3QgaW50IHN1ZmZpeFRyZWVEZXB0aCA9IDU7CisKICAg ICBBU1NFUlQobV9zdGF0ZSA9PSBVbmluaXRpYWxpemVkKTsKICAgICBtX3N0YXRlID0gSW5pdGlh bDsKIApAQCAtMTc0LDYgKzE3Nyw4IEBAIHZvaWQgWFNTRmlsdGVyOjppbml0KCkKICAgICAgICAg ICAgIG1fZGVjb2RlZEhUVFBCb2R5ID0gZGVjb2RlVVJMKGh0dHBCb2R5LT5mbGF0dGVuVG9TdHJp bmcoKSwgZW5jb2RpbmcpOwogICAgICAgICAgICAgaWYgKG1fZGVjb2RlZEhUVFBCb2R5LmZpbmQo aXNSZXF1aXJlZEZvckluamVjdGlvbiwgMCkgPT0gbm90Rm91bmQpCiAgICAgICAgICAgICAgICAg bV9kZWNvZGVkSFRUUEJvZHkgPSBTdHJpbmcoKTsKKyAgICAgICAgICAgIGlmIChtX2RlY29kZWRI VFRQQm9keS5sZW5ndGgoKSA+PSBtaW5pdW1MZW5ndGhGb3JTdWZmaXhUcmVlKQorICAgICAgICAg ICAgICAgIG1fZGVjb2RlZEhUVFBCb2R5U3VmZml4VHJlZSA9IGFkb3B0UHRyKG5ldyBTdWZmaXhU cmVlPEFTQ0lJQ29kZWJvb2s+KG1fZGVjb2RlZEhUVFBCb2R5LCBzdWZmaXhUcmVlRGVwdGgpKTsK ICAgICAgICAgfQogICAgIH0KIApAQCAtNDI3LDggKzQzMiwxMSBAQCBib29sIFhTU0ZpbHRlcjo6 aXNDb250YWluZWRJblJlcXVlc3QoY29uCiAgICAgQVNTRVJUKCFzbmlwcGV0LmlzRW1wdHkoKSk7 CiAgICAgU3RyaW5nIGNhbm9uaWNhbGl6ZWRTbmlwcGV0ID0gY2Fub25pY2FsaXplKHNuaXBwZXQp OwogICAgIEFTU0VSVCghY2Fub25pY2FsaXplZFNuaXBwZXQuaXNFbXB0eSgpKTsKLSAgICByZXR1 cm4gbV9kZWNvZGVkVVJMLmZpbmQoY2Fub25pY2FsaXplZFNuaXBwZXQsIDAsIGZhbHNlKSAhPSBu b3RGb3VuZAotICAgICAgICB8fCBtX2RlY29kZWRIVFRQQm9keS5maW5kKGNhbm9uaWNhbGl6ZWRT bmlwcGV0LCAwLCBmYWxzZSkgIT0gbm90Rm91bmQ7CisgICAgaWYgKG1fZGVjb2RlZFVSTC5maW5k KGNhbm9uaWNhbGl6ZWRTbmlwcGV0LCAwLCBmYWxzZSkgIT0gbm90Rm91bmQpCisgICAgICAgIHJl dHVybiB0cnVlOworICAgIGlmIChtX2RlY29kZWRIVFRQQm9keVN1ZmZpeFRyZWUgJiYgIW1fZGVj b2RlZEhUVFBCb2R5U3VmZml4VHJlZS0+bWlnaHRDb250YWluKGNhbm9uaWNhbGl6ZWRTbmlwcGV0 KSkKKyAgICAgICAgcmV0dXJuIGZhbHNlOworICAgIHJldHVybiBtX2RlY29kZWRIVFRQQm9keS5m aW5kKGNhbm9uaWNhbGl6ZWRTbmlwcGV0LCAwLCBmYWxzZSkgIT0gbm90Rm91bmQ7CiB9CiAKIGJv b2wgWFNTRmlsdGVyOjppc1NhbWVPcmlnaW5SZXNvdXJjZShjb25zdCBTdHJpbmcmIHVybCkKSW5k ZXg6IFNvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5oCj09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0t IFNvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5oCShyZXZpc2lvbiA3NzU0NSkK KysrIFNvdXJjZS9XZWJDb3JlL2h0bWwvcGFyc2VyL1hTU0ZpbHRlci5oCSh3b3JraW5nIGNvcHkp CkBAIC0yOCw2ICsyOCw3IEBACiAKICNpbmNsdWRlICJIVE1MVG9rZW4uaCIKICNpbmNsdWRlICJI VFRQUGFyc2Vycy5oIgorI2luY2x1ZGUgIlN1ZmZpeFRyZWUuaCIKIAogbmFtZXNwYWNlIFdlYkNv cmUgewogCkBAIC03NSw2ICs3Niw3IEBAIHByaXZhdGU6CiAKICAgICBTdHJpbmcgbV9kZWNvZGVk VVJMOwogICAgIFN0cmluZyBtX2RlY29kZWRIVFRQQm9keTsKKyAgICBPd25QdHI8U3VmZml4VHJl ZTxBU0NJSUNvZGVib29rPiA+IG1fZGVjb2RlZEhUVFBCb2R5U3VmZml4VHJlZTsKIAogICAgIFN0 YXRlIG1fc3RhdGU7CiAgICAgU3RyaW5nIG1fY2FjaGVkU25pcHBldDsK