Opened 12 months ago

Closed 10 months ago

Last modified 8 months ago

#7089 closed change (fixed)

Use type-specific maps for matching non-default types

Reported by: mjethani Assignee: mjethani
Priority: P2 Milestone:
Module: Core Keywords:
Cc: Blocked By:
Blocking: #7000 Platform: Unknown / Cross platform
Ready: no Confidential: no
Tester: Unknown Verified working: no
Review URL(s):

https://codereview.adblockplus.org/29933592/

Description (last modified by mjethani)

Background

Most filters apply to at least one default content type like $script, $image, $stylesheet, and so on, but only some filters apply to non-default types like $csp, $elemhide, $genericblock, etc. Yet the non-default types are queried for each document.

Right now filters in the matcher are divided into blacklist (blocking) and whitelist. After #6994, they are further divided into "simple" (location only) and "complex". A filter with a non-default type like $csp goes in the "complex" map.

Looking at the data structures in the matcher with EasyList+AA, there are ~6,200 whitelist filters in the "complex" category, but only ~900 of these are $elemhide filters. Similarly, there are ~18,500 "complex" blocking filters, but of these only ~90 are $csp filters. If there were separate type-specific maps for $csp, $elemhide, and so on, matching would be a lot faster. In most cases, especially for $csp, matching would terminate immediately since no filters would be found for the keywords in the URL.

After applying the patch, I found filter matching for whitelisting and CSP to be faster by roughly 40-45% with a URL containing three known keywords.

What to change

See patch.

Hints for testers

Test blocking and whitelisting filters thoroughly.

Specifically make sure that $csp, $popup, $document, $genericblock, $elemhide, and $generichide work as expected.

Here are some examples:

  1. If there's a filter ^test.html^$csp=script-src 'none' and the page test.html contains an inline <script> element, the script should not be executed
  2. If there are two filters ##.foo and ^test.html^$elemhide, the element <div class="foo">X</div> in test.html should not be hidden
  3. If there are two filters /foo^ and ^test.html^$document, a request for https://example.com/foo from test.html should not be blocked

Change History (8)

comment:1 Changed 12 months ago by mjethani

  • Description modified (diff)

comment:2 Changed 12 months ago by mjethani

  • Blocking 7000 added

comment:3 Changed 12 months ago by mjethani

  • Status changed from new to reviewing

comment:4 Changed 10 months ago by abpbot

A commit referencing this issue has landed:
Issue 7089 - Match filters by type for non-default types

comment:5 Changed 10 months ago by mjethani

  • Description modified (diff)

comment:6 Changed 10 months ago by mjethani

  • Description modified (diff)

comment:7 Changed 10 months ago by mjethani

  • Description modified (diff)
  • Resolution set to fixed
  • Status changed from reviewing to closed

comment:8 Changed 8 months ago by abpbot

A commit referencing this issue has landed:
Issue 7089 - Match filters by type for non-default types

Note: See TracTickets for help on using tickets.