Documentation
¶
Overview ¶
Package policy decides what to do with a query before it is resolved.
It answers three questions in order: is this name allowed for this device, should it be answered locally rather than forwarded, and if it is blocked, what should the client be told. Everything else — who the device is, where the lists came from, what happens to the answer afterwards — belongs to the layers around it.
Matching is the whole cost ¶
A blocklist is not a few hundred names. A working deployment loads several lists totalling somewhere between a hundred thousand and several million entries, and every query is checked against all of them before anything else happens. A matcher that is linear in the number of entries is not slow, it is unusable: at a million entries and ten thousand queries a second it is ten billion comparisons a second.
So the shape of the data decides the design. Almost every entry in a real blocklist is "this name and everything under it", which is a suffix question, and a domain name has a small fixed number of suffixes — at most 127, in practice four or five. Matcher therefore walks the query name's own parent chain and looks each one up in a hash set, which costs the same at a million entries as at ten. Regular expressions cannot be answered that way and are checked separately, last, and only when nothing cheaper has decided.
Why regular expressions are safe here ¶
Operator-supplied regular expressions are usually a denial-of-service waiting to happen: a backtracking engine can be made to spend exponential time on a short input, and the operator writing the pattern is rarely the person who will notice. Go's regexp package implements RE2, which runs in time linear in the length of the input and has no backtracking, so a pathological pattern costs more than a simple one but cannot be made to cost unboundedly more. That is the only reason this package accepts them at all.
Precedence, and why allow beats block ¶
An allow rule always wins over a block rule, whatever their specificity. This is the rule operators expect and the only one that makes large lists usable: a list of a million names is impossible to audit, so the way anyone recovers from a false positive in one is to add the name to an allowlist. If specificity decided instead, recovering from a broad block would mean editing a list somebody else maintains.
Within each kind, the most specific rule wins: an exact name beats a suffix, and a longer suffix beats a shorter one. A regular expression is considered only when no literal rule matched, because a literal rule is both cheaper and easier for an operator to reason about.
What a blocked client is told ¶
There is no answer here that is both honest and universally compatible, so the choice is the operator's and the trade is worth stating. NXDOMAIN is understood by everything and stops the client immediately, but it is a lie: the name usually does exist, and a client that asks a second resolver will get a different answer. REFUSED is honest about the refusal but makes some clients retry or fail slowly. Returning an address the client cannot reach — 0.0.0.0 or :: — is the oldest approach and the worst: the client believes it resolved and then hangs on a connection that will never open.
Whichever is chosen, the reply carries an EDNS Extended DNS Error saying it was filtered (RFC 8914), which is what makes NXDOMAIN honest to a client that reads one.
Where this runs ¶
As [Middleware], outside the cache and outside deduplication. That placement is not incidental: a rule evaluated after the cache would let a name blocked at noon go on being answered from an entry stored at eleven, and one evaluated inside deduplication would apply the first caller's device policy to every device sharing the query.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Action ¶
type Action uint8
Action is what a policy decided to do with a query.
type BlockMode ¶
type BlockMode uint8
BlockMode is what a blocked client is told. See the package documentation for why none of these is simply correct.
const ( // BlockNXDomain answers "no such name". Universally understood and it stops // the client at once, at the cost of being untrue. BlockNXDomain BlockMode = iota // BlockRefused answers REFUSED, which is honest about the refusal. Some // clients retry it or fail slowly. BlockRefused // BlockNoData answers NOERROR with no records: the name exists, this type // does not. The gentlest answer, and the one least likely to make a client // try another resolver. BlockNoData )
Block modes.
type Decision ¶
type Decision struct {
Action Action
// Match is the rule responsible, empty for a default allow. Every block is
// followed by somebody asking why, and this is the answer.
Match Match
// Policy names the policy that decided, so an operator can tell a
// device-specific rule from the default.
Policy string
}
Decision is the outcome of evaluating one query.
type Engine ¶
type Engine struct {
// contains filtered or unexported fields
}
Engine evaluates policy for every query and answers the blocked ones.
Its rules are swapped atomically, so reloading a million-entry blocklist never blocks a query: the new Rules are built off to the side and the pointer is replaced.
func (*Engine) Evaluate ¶
Evaluate decides one query without answering it, which is what a caller wanting to log or count a decision needs.
func (*Engine) Middleware ¶
func (e *Engine) Middleware() resolver.Middleware
Middleware returns the resolver.Middleware that applies this engine.
It must be installed outside the cache and outside deduplication, which resolver.New guarantees by running middleware first: a rule evaluated after the cache would let a name blocked at noon go on being answered from an entry stored at eleven, and one evaluated inside deduplication would apply the first caller's device policy to every device sharing that query.
func (*Engine) SetDefault ¶
SetDefault replaces the default policy atomically.
This is the reload path, and the atomic swap is the point: rebuilding a matcher from several million entries takes seconds, and holding a lock over the query path for that long would be an outage. The new rules are built first and installed in one store.
type Format ¶
type Format uint8
Format is a blocklist's on-disk shape.
const ( // FormatAuto sniffs the format from the content. It is the default because // an operator pasting a URL from a forum post generally does not know which // of these they have picked. FormatAuto Format = iota // FormatHosts is a hosts(5) file: an address, whitespace, one or more // names. It is the most common blocklist format by a wide margin, and the // address is ignored — a list that maps a name to 0.0.0.0 and one that maps // it to 127.0.0.1 are saying the same thing. FormatHosts // FormatDomains is one name per line, which is what most modern lists ship. FormatDomains // FormatAdBlock is the subset of Adblock Plus syntax that is expressible in // DNS: "||example.com^" and its exception form "@@||example.com^". // Everything else in that syntax — element hiding, path and query matching, // resource-type options — describes parts of a request a DNS server never // sees, and is skipped rather than half-honoured. FormatAdBlock )
Recognised list formats.
type Kind ¶
type Kind uint8
Kind is how a rule matches a name.
const ( // KindExact matches one name and nothing below it. "example.com" does not // match "www.example.com". KindExact Kind = iota // KindSuffix matches a name and everything under it. "example.com" matches // "example.com" and "www.example.com" but not "notexample.com" — the match // is on label boundaries, never on the string. // // This is what almost every blocklist entry means, and it is the default // for a bare name. KindSuffix // KindRegex matches names whose presentation form the pattern matches. It is // checked last and only when no literal rule has decided, because it costs // more and is harder for an operator to reason about. KindRegex )
Rule kinds, ordered by specificity: a more specific kind wins.
type ListStats ¶
type ListStats struct {
// Lines read, including comments and blanks.
Lines int
// Blocked and Allowed are rules added to each set.
Blocked int
Allowed int
// Skipped is lines that carried no rule: comments, blanks, and Adblock
// syntax that has no DNS meaning.
Skipped int
// Rejected is lines that looked like rules and were not parseable.
Rejected int
// Format is what was used, which after FormatAuto is what was detected.
Format Format
}
ListStats reports what a load produced.
func LoadList ¶
func LoadList(r io.Reader, format Format, source string, block, allow *MatcherBuilder) (ListStats, error)
LoadList parses a blocklist from r into the two builders.
Names are added as KindSuffix rules, which is what a blocklist entry almost always means: a list saying "doubleclick.net" intends to block "ad.doubleclick.net" too, and a list that meant only the bare name would be nearly useless. It is worth being explicit because the hosts(5) format does not mean that — a hosts file maps exactly one name — and this package deliberately does not honour that reading, because nobody publishing a hosts file as a blocklist intends it.
A single unparseable line never fails the load. Real lists contain stray markup, unicode, and half-edited entries, and discarding a million good rules over one bad one is the wrong trade; the count comes back in ListStats and the first few examples through MatcherBuilder.Rejected.
type Match ¶
type Match struct {
// Rule is the pattern as the operator wrote it, for logs and for the
// "why was this blocked" question that follows every block.
Rule string
Kind Kind
// Source names the list the rule came from, empty for a rule configured
// directly. An operator who wants a name unblocked needs to know which of
// eleven lists to look in.
Source string
// Depth is the number of labels the rule matched, so a caller can compare
// specificity between two suffix rules. It is zero for a regex, which has
// no meaningful depth.
Depth int
}
Match reports which rule matched a name and how.
type Matcher ¶
type Matcher struct {
// contains filtered or unexported fields
}
Matcher answers "does any rule match this name" in time that does not grow with the number of rules.
The literal rules live in two hash sets keyed by the canonical wire form of a name, so a lookup is a handful of map probes — one per label of the query name — however many million rules there are. Only the regular expressions are scanned, and only when nothing literal matched.
A Matcher is immutable once built, which is what lets a running server swap in a freshly loaded set of lists by replacing the pointer rather than by locking every query out of the old one. Use MatcherBuilder to construct one.
func (*Matcher) Empty ¶
Empty reports whether the matcher holds no rules at all. It exists so the query path can skip a matcher that would never match rather than walking a name's parents to find that out.
func (*Matcher) Len ¶
Len reports how many rules the matcher holds, which is what an operator wants after loading eleven lists of unknown quality.
func (*Matcher) Match ¶
Match reports the most specific rule matching name, if any.
The walk is from the name itself outward to the root, so the first suffix hit is by construction the longest one, and an exact rule on the full name beats every suffix. That ordering is why nothing here has to compare specificity afterwards.
type MatcherBuilder ¶
type MatcherBuilder struct {
// contains filtered or unexported fields
}
MatcherBuilder accumulates rules and produces an immutable Matcher.
It exists because loading several million entries and then serving from them are different problems: loading wants to append cheaply and tolerate duplicates, serving wants a structure nothing can write to. A builder is safe for concurrent use so that several lists can be parsed in parallel.
func NewMatcherBuilder ¶
func NewMatcherBuilder() *MatcherBuilder
NewMatcherBuilder returns an empty builder.
func (*MatcherBuilder) Add ¶
func (b *MatcherBuilder) Add(kind Kind, pattern, source string) bool
Add records one rule, reporting whether it was accepted.
An empty or unparseable pattern is counted as rejected rather than returned as an error, because a single bad line in a list of a million must not discard the other 999,999.
The boolean matters more than it looks. A caller that instead compared Rejected() before and after each Add would allocate a copy of the problem slice twice per rule — about a kilobyte per line once the cap is reached — and would get the wrong answer entirely when two lists are parsed into one builder concurrently, which this type documents as supported: another goroutine's rejection between the two reads is indistinguishable from this one's.
func (*MatcherBuilder) Build ¶
func (b *MatcherBuilder) Build() *Matcher
Build returns the immutable matcher. The builder may be reused afterwards; the returned matcher does not share its maps.
func (*MatcherBuilder) Rejected ¶
func (b *MatcherBuilder) Rejected() (int, []string)
Rejected returns how many entries could not be parsed, and up to [maxRecordedProblems] of them verbatim. Loading a list is the moment an operator finds out it is the wrong format, and "0 of 1,204,900 loaded" with three example lines is the difference between a fixable mistake and a mystery.
type Options ¶
type Options struct {
// Default governs every client no policy is found for. Nil allows
// everything, which is the right default for a resolver nobody has
// configured yet: a filtering resolver that fails closed would take the
// network down on a configuration mistake.
Default *Rules
// Devices maps clients to policies. Nil means every client gets Default.
Devices Resolver
// Mode is what a blocked client is told.
Mode BlockMode
// TTL is how long a blocked answer may be cached, in seconds. Zero selects
// [resolver.DefaultBlockTTL].
TTL uint32
Metrics metrics.Recorder
Events *events.Bus
Logger *slog.Logger
}
Options configure an Engine.
type Resolver ¶
type Resolver interface {
// PolicyFor returns the rules governing a client, or nil for the default.
// It is called on every query and must be cheap and safe for concurrent
// use.
PolicyFor(c resolver.Client) *Rules
}
Resolver maps a client to the policy that governs it.
It is an interface because this package has no idea what a device is: the mapping might come from a DHCP lease table, a MAC address, a configuration file or an authenticated session, and all of those live above the engine. Returning nil means "the default policy", which is what an unknown device gets.
type ResolverFunc ¶
ResolverFunc adapts a function to Resolver.
type Rules ¶
type Rules struct {
// Name identifies the policy in logs and metrics.
Name string
// Allow, when it matches, resolves the query whatever Block says.
Allow *Matcher
// Block, when it matches and Allow does not, blocks the query.
Block *Matcher
}
Rules are one policy's matchers.
Allow is consulted first and wins outright; see the package documentation for why specificity does not decide between them.
Source Files