Database-backed storage and pattern matching

[supriyo-biswas]

The current design of DNS66 performs well, but it lacks flexibility for allowing wildcards in the domain pattern (#33), or the use of Adblock Plus style lists (#185). I propose moving to a SQLite database, which would make things very flexible.

The database schema would consist of three columns:

• domain: This is the domain, without any wildcards.
• action: Holds a value representing allow/deny.
• behaviour: This defines the behaviour of the rule. A rule may be of three types:
  • The action applies to the domain, but not any subdomains under it(0).
  • The action applies to the domain and any subdomain under it(1).

During an update from a hosts file, all entries are supposed to be exact matches, so every rule is added with behaviour = 0. When parsing a wildcard entry (such as *.example.com) or domain-blocking Adblock Plus rules (such as ||example.com^), each rule could be added with behaviour = 1.

Now, assume that we are given a domain X. The result is determined as follows:

• Start with Y = X.
• Does Y exist in the database? If it does:
  • If behaviour = 1, or if behaviour = 0 and Y = X, return allow/deny according to action.
  • If there is only one label in Y, return allow.
  • Otherwise, remove the 1st label from Y and repeat step 2.

The above proposal doesn't allow for wildcards in the middle or end (such as abc*.com, abc.* or foo.*.com), but this should be a good place to start, and would cover the common use cases.

[julian-klode]

I had an SQLite branch, but I was not too happy with it (it also restarts too fast, causing Android to seriously mess up VPNs and break everything until you manually restart it). Support for wildcard entries is not that hard to do with the current hash table either, you can do the same stuff there.

[julian-klode]

Oh, JFTR: Wildcards are tracked in #33