String matcher enhancement: DNS support & better matchers

[Vigilans]

Port mph string matcher to DNS domain matching

I really appreciate @darsvador ‘s work in #587, #639, #743, and am impressed by its design and performance improvement. So I would like to port this string matcher to DNS module and use v2ray as the main DNS server in my asuswrt router's private network, since from source code dnsmasq seems to traverse all domains linearly without optimization, hence may suffering from both cpu and memory bottleneck when working in a router and scaling to things like domain-list-community.

Some modifications have to be done for MphMatcherGroup to properly work in DNS module. This is because MphMatcherGroup is implemented as a "boolean" matcher: MphMatcherGroup.Match only returns a 1-element array with the only value 1, while the DNS module expects the IndexMatcher to work in this way:

1. DNS module get a Matcher (full, domain, substr or regex) from a specific domain rule bound to a DNS server.
2. DNS module feeds the matcher to IndexMatcher by calling Add() and gets a returned index.
3. DNS module registers this index (representing the matcher) with the domain rule and the corresponding DNS server.
4. When querying, DNS module calls IndexMatcher.Match and gets a list of indices.
5. DNS module uses these indices to retrieve the DNS servers to use along with the lookup ordering.

Therefore, the IndexMatcher.Match should have following guarantees for DNS module:

1. It should return index of the matching matcher, where the index originates from Add(matcher)'s return value.
2. It should return all matches, and orders them with stable priority specification, instead of early exit in first match.

To provide first guarantee for IndexMatcher, I plan to append additional fields for MphMatcherGroup and ACAutomata:

• a values field of type [][]uint32 for MphMatcherGroup, for each index n corrsponding to g.rules[n], there is a value array g.values[n]. Value array is used here because the same rule can be added multiple times from different DNS servers.
• a values field of type [][]uint32 for ACAutomata, for each matched node n, there is a value array ac.values[n] corresponding to the indices of the matchers (maybe further operations needed for different match type?).

@darsvador How much do you think these fields would affect the memory efficiency of mph matcher?

To provide second guarantee for IndexMatcher, I plan to refactor MphMatcherGroup.Match, as well as strmatcher package:

• IndexMatcher should be refactored to add an Add method, with the matching result's priority stablized as a specification in IndexMatcher interface.
• To preserve MphMatcherGroup's performance in routing matching, we may add a boolean flag firstMatchOnly to early return on first match.

[Vigilans]

Refactoring strmatcher

To untangle the messing organization of strmatcher package, we may define a hierarchy of matcher interfaces as follows:

Matcher
Basic matcher to represent a certain kind of match semantic. Implemented by fullMatcher, substrMatcher, domainMatcher, regexMatcher.

A Matcher also provides their own Match() method, but seldom used for performance reason, and is generally taken over by their corresponding MatcherGroup.

MatcherGroup
An advanced type of matcher to accept a bunch of basic Matchers (of certain type, not all four types).

For example, FullMatcherGroup accepts fullMatcher and uses a hash table to facilitate lookup, while DomainMatcherGroup accepts domainMatcher and uses a trie to optimize both memory consumption and lookup speed.

IndexMatcher
A general string matcher thats accepts all kinds of basic matchers and optimize them with a combination of matcher groups.

The "linear" matcher group and "mph" matcher group are such kind of matcher.

After refactoring, the folder structure of `strmatcher` packge may looks like:

strmatcher
  |- strmatcher.go
  |- strmatcher_test.go
  |- matchers.go
  |- matchers_test.go
  |- matchergroup_full_map.go
  |- matchergroup_full_map_test.go
  |- matchergroup_domain_trie.go
  |- matchergroup_domain_trie_test.go
  |- matchergroup_ac_automation.go
  |- matchergroup_ac_automation_test.go
  |- indexmatcher_linear.go
  |- indexmatcher_linear_test.go
  |- indexmatcher_mph.go
  |- indexmatcher_mph_test.go

Match result priority specification

1. Priority between matcher types: full > domain > substr = regex.
2. Priority in the same-priority matching matcher and the same-level domain matcher: the early added takes precedence.
3. Priority across multi-level domain matcher: the further matched subdomain takes precedence.

[Loyalsoldier]

Please file a PR.

[Vigilans]

Refactoring ACAutomationMatcherGroup

Current v2ray provides an implementation of AC Automation, firstly used for Full, Domain and Substr matching, but soonly reduced to only Substr matching for memory consumption reason.

There are some problems with current implementation:

Algorithm not implemented correctly

In AC Automation's algorithm, when entering a new node, its path through the fail pointer must be traversed until back to root node, or else it will fail to produce correct answers like this test case:

patterns: "apis", "googleapis.com"
input: "gapis.com"

It has the substr "apis", but since it matches on "apis.com" out of "[google] apis.com" (the match is done on the input reversely), it will neglect the "apis" pattern since it fails to check the node at "apis". This test has been examinated on current AC Automation's implementation and it did not pass.

Memory overhead: struct alignment

Sizeof type Edge struct { edgeType bool nextNode int } is 16 in 64-bit machine, since it has a 7-byte padding: (1 + 7) + 8 = 16. This edge struct will repeat 53 times (size of charset), So a node will occupy 16*53=848 bytes, very inefficient in memory.

We could reduce the size from 16 to 5 by:

1. Change nextNode from int to uint32.
2. Use data-oriented design, split the edge info into plain 2 arrays: type node struct { next [53]uint32 edge [53]bool }.

Now edge infos will now occupy (4*53+1*53+3)=268 bytes, 68.4% memory is saved for each node.

Memory overhead: charset size

The current implementation's charset size is 53, from a-zA-Z(26) + 0-9(10) + !$&\()*+,;=:%-._~(17).

But currently, the strmatcher is only used for domains, known to be in a charset named Letter-Digit-Hyphen (LDH) subset, which only allows for a-zA-Z + 0-9 + - + . with size 38. If reduced to this charset, (53-38)/53=28.3% memory could be saved for each node.

We could add a new function NewDomainPattern(pattern string) (string, error) to validate and convert the string to be in the LDH subset. If for future the strmatcher are used for other scenarios, we could add a new Charset interface for it.

[Vigilans]

Refactoring MphMatcherGroup

MphMatcherGroup uses an algorithm Hash, displace, and compress to construct a minimal perfect hash table. It involves 1. a normal hash function, and 2. a series of hash functions independent to each others.

This is how this MphMatcherGroup works:

First level hash: RollingHash

Rolling hash is chosen here because we can easily calculate the hash of a full domain and all its subdomains.

We obtain a seed from the result of first level hash.

Second level hash: MemHash

One of second level functions is selected according to the seed obtained from first level hash.

This is done by choosing golang runtime's memhash, because memhash requires a seed as argument, and with different seeds, memhash behaves exactly like distinct hash functions independent to each other.

To use memhash, current implementation of MphMatcherGroup copies source code (unoptimized version) from golang runtime. However, we could directly reference the runtime 'simplementation using compiler directive go:linkname:

//go:noescape
//go:linkname memhash runtime.memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr

While avoiding duplicate code, the runtime's memhash implementation could also benefit from hardware optimizations like AES if supported. Current MphMatcherGroup unconditionally uses the unoptimized fallback version.

[Vigilans]

(Draft)

eTLD Index Matcher

The strmatcher had long been a memory-consuming module when used with very large domain lists. Part of its memory consumption derives from the storage of pattern strings.

The EtldIndexMatcher is hence designed with the purpose to dramatically reduce the memory usage, meanwhile optimizing the lookup speed by choosing the MatcherGroups best suit for each part of a domain string: subdomain, domain and etld.

eTLD Index Matcher: Data Structure

The domain string is split into three parts:

• eTLD: Dynamic segments (.com or .com.hk), but with very small and predicable counts (no more than public suffix list). So, they could be trustingly saved in an AC Automata occupying only small amount of memory.
• domain: Fixed segments (only 1), with a relatively more variants (google, facebook, etc.). So they could be efficiently stored and looked up using a hash table.
• subdomain: Dynamic segments (sub or sub.sub), and inpredicable variants (could be defined randomly by the domain owner). To match segments one by one, we could choose MphMatcherGroup to strike a balance between memory consumption and lookup speed.

eTLD Index Matcher: Match Algorithm

Domain Matcher: Break the domain into three parts when adding the matcher:

• eTLD: Dynamic segments (.com or .com.hk), match using AC Automata for longgest suffix.
• domain: Fixed segments (only 1), match as Full Matcher, uses golang built-in map for best performance.
• subdomain: Dynamic segments, match using Mph Matcher group to compute rolling hash.

Substr Matcher: Use AC Automata.

Regex Matcher: Use simple matcher entry array.

Full Matcher: Consider two cases:

• Contains Substr matcher: Since matching Substr patterns will iterate through the whole input string once, so Full patterns could also be matched using AC Automata to eliminate one more round of iteration.
• Not contains Substr matcher: We directly store the computed rolling hash of eTLD and domain. After obtaining the rolling hash of subdomain, we combine them together to get the rolling hash of the whole string, then look it up in the Mph hash table.