jarl/internal/blocking/zone.go

package blocking

import (
	"bufio"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"io"
	"os"
	"sort"
	"strings"
)

// Policy zone names. They are under .invalid (RFC 6761), so they can
// never clash with a real zone, and named only uses them internally.
const (
	// RulesZone holds the rules entered in Jarl (one copy per view).
	RulesZone = "rules.jarl.invalid"
	// listSuffix follows a list's name: hagezi.blocklist.jarl.invalid.
	listSuffix = ".blocklist.jarl.invalid"
)

// ListZone returns the policy zone name of a blocklist.
func ListZone(name string) string { return name + listSuffix }

// ListName returns the blocklist name of a policy zone ("" for the rules
// zone and zones that aren't Jarl's).
func ListName(zone string) string {
	zone = strings.TrimSuffix(strings.ToLower(zone), ".")
	if n, ok := strings.CutSuffix(zone, listSuffix); ok && !strings.Contains(n, ".") {
		return n
	}
	return ""
}

// Match says what blocking does with a name in one view.
type Match struct {
	View   string `json:"view,omitempty"`
	Result string `json:"result"`          // blocked, allowed or none
	Entry  string `json:"entry,omitempty"` // the matching entry: the name, or *.parent
	RuleID int64  `json:"rule_id,omitempty"`
	List   string `json:"list,omitempty"` // the blocklist, when a list matched
	// Step is the list's step when it is above normal: only clients at
	// that step or above get this answer (others: none).
	Step string `json:"step,omitempty"`
}

// Actions of rules.
const (
	ActionBlock = "block"
	ActionAllow = "allow"
)

// cname is the CNAME target of each action: "." answers NXDOMAIN,
// rpz-passthru. answers as if there were no rule.
var cname = map[string]string{ActionBlock: ".", ActionAllow: "rpz-passthru."}

// header starts a policy zone file. There is no $ORIGIN: names are
// relative to the zone, so a list can be renamed without rewriting its
// file. The short TTLs make a change reach clients' caches quickly.
func header(title string, serial uint32) string {
	return fmt.Sprintf("; %s\n; Generated by Jarl. DO NOT EDIT.\n$TTL 60\n@\tSOA\tlocalhost. hostmaster.localhost. %d 3600 600 86400 60\n\tNS\tlocalhost.\n", title, serial)
}

// Placeholder is the content of a list's zone file before the list has
// been downloaded: a valid, empty policy zone.
func Placeholder() string {
	return header("Blocklist not downloaded yet.", 1)
}

// Rule is a block or allow rule entered by hand.
type Rule struct {
	Name   string // lowercase, without the final dot
	Action string // ActionBlock or ActionAllow
	Exact  bool   // only the name itself, not the names below it
}

// RuleEntries returns the policy zone owners for rules (relative names,
// "*." for wildcards) and their actions, with the entries that make the
// most specific rule win added: named won't apply a wildcard below a name
// that exists in the zone, so every name below a wildcard that exists
// (because a more specific rule mentions it) gets the wildcard's action
// for itself and for the names below it, unless a rule says otherwise.
// Callers make sure no two rules have the same name and scope.
func RuleEntries(rules []Rule) map[string]string {
	e := map[string]string{}
	for _, r := range rules {
		e[r.Name] = r.Action
		if !r.Exact {
			e["*."+r.Name] = r.Action
		}
	}
	// Every name that exists in the zone: owners and their ancestors.
	nodes := map[string]bool{}
	for owner := range e {
		n := strings.TrimPrefix(owner, "*.")
		for {
			nodes[n] = true
			i := strings.IndexByte(n, '.')
			if i < 0 {
				break
			}
			n = n[i+1:]
		}
	}
	ordered := make([]string, 0, len(nodes))
	for n := range nodes {
		ordered = append(ordered, n)
	}
	// Shallow names first, so a filled-in wildcard is inherited further
	// down.
	sort.Slice(ordered, func(i, j int) bool {
		di, dj := strings.Count(ordered[i], "."), strings.Count(ordered[j], ".")
		if di != dj {
			return di < dj
		}
		return ordered[i] < ordered[j]
	})
	for _, n := range ordered {
		inherited := ""
		for a := n; ; {
			i := strings.IndexByte(a, '.')
			if i < 0 {
				break
			}
			a = a[i+1:]
			if act, ok := e["*."+a]; ok {
				inherited = act
				break
			}
		}
		if inherited == "" {
			continue
		}
		if _, ok := e[n]; !ok {
			e[n] = inherited
		}
		if _, ok := e["*."+n]; !ok {
			e["*."+n] = inherited
		}
	}
	return e
}

// PausedZoneFile renders a rules zone that lets every name through, for
// while blocking is paused: the rules zone comes first, and its match
// stops named from looking at the lists.
func PausedZoneFile(title string) string {
	return header(title+" (blocking is paused)", 1) + "*\tCNAME\trpz-passthru.\n"
}

// RulesZoneFile renders the rules zone of a view.
func RulesZoneFile(title string, rules []Rule) string {
	e := RuleEntries(rules)
	owners := make([]string, 0, len(e))
	for o := range e {
		owners = append(owners, o)
	}
	sort.Slice(owners, func(i, j int) bool { return ownerLess(owners[i], owners[j]) })
	var sb strings.Builder
	sb.WriteString(header(title, 1))
	for _, o := range owners {
		fmt.Fprintf(&sb, "%s\tCNAME\t%s\n", o, cname[e[o]])
	}
	return sb.String()
}

// ownerLess sorts names by their labels from the right (example,
// ads.example, *.ads.example, cdn.ads.example), so related rules are next
// to each other.
func ownerLess(a, b string) bool {
	ka, kb := reverseLabels(a), reverseLabels(b)
	return ka < kb
}

func reverseLabels(n string) string {
	labels := strings.Split(n, ".")
	for i, j := 0, len(labels)-1; i < j; i, j = i+1, j-1 {
		labels[i], labels[j] = labels[j], labels[i]
	}
	// A wildcard sorts right after the name it belongs to.
	return strings.ReplaceAll(strings.Join(labels, "\x00"), "*", "\x01")
}

// MatchRules finds the rule entry named would apply to name (lowercase,
// without the final dot) in a rules zone with entries e: the name itself,
// or else the wildcard of its closest existing ancestor. ok is false when
// no entry applies.
func MatchRules(e map[string]string, name string) (owner, action string, ok bool) {
	if act, found := e[name]; found {
		return name, act, true
	}
	nodes := map[string]bool{}
	for o := range e {
		n := strings.TrimPrefix(o, "*.")
		for {
			nodes[n] = true
			i := strings.IndexByte(n, '.')
			if i < 0 {
				break
			}
			n = n[i+1:]
		}
	}
	if nodes[name] {
		return "", "", false // the name exists without a rule of its own
	}
	for a := name; ; {
		i := strings.IndexByte(a, '.')
		if i < 0 {
			return "", "", false
		}
		a = a[i+1:]
		if nodes[a] {
			if act, found := e["*."+a]; found {
				return "*." + a, act, true
			}
			return "", "", false
		}
	}
}

// Compact drops entries another entry already covers (a name below a
// name whose subdomains are blocked). That keeps the zone small, and it
// matters for correctness: no name exists below a wildcard, so every
// wildcard applies to all names below it.
func Compact(l *List) {
	for n := range l.Domains {
		for a := n; ; {
			i := strings.IndexByte(a, '.')
			if i < 0 {
				break
			}
			a = a[i+1:]
			if l.Domains[a]&Below != 0 {
				delete(l.Domains, n)
				break
			}
		}
	}
}

// FeedZone writes a list's policy zone to w and returns the number of
// records and a hash of them (the serial isn't part of the hash, so it
// tells whether the content changed). l must be compacted.
func FeedZone(w io.Writer, title string, serial uint32, l *List) (records int, hash string, err error) {
	names := make([]string, 0, len(l.Domains))
	for n := range l.Domains {
		names = append(names, n)
	}
	sort.Strings(names)
	bw := bufio.NewWriterSize(w, 256*1024)
	h := sha256.New()
	if _, err := bw.WriteString(header(title, serial)); err != nil {
		return 0, "", err
	}
	write := func(owner string) error {
		line := owner + "\tCNAME\t.\n"
		h.Write([]byte(line))
		records++
		_, err := bw.WriteString(line)
		return err
	}
	for _, n := range names {
		f := l.Domains[n]
		if f&Exact != 0 {
			if err := write(n); err != nil {
				return 0, "", err
			}
		}
		if f&Below != 0 {
			if err := write("*." + n); err != nil {
				return 0, "", err
			}
		}
	}
	if err := bw.Flush(); err != nil {
		return 0, "", err
	}
	return records, hex.EncodeToString(h.Sum(nil)), nil
}

// MatchFeed reports which entry of a list's zone file blocks name: the
// name itself, or a wildcard of one of its ancestors (the closest).
// Lists are compacted, so no name exists below a wildcard and the
// closest wildcard ancestor is the one named uses.
func MatchFeed(path, name string) (owner string, ok bool, err error) {
	want := map[string]int{name: 0}
	depth := 1
	for a := name; ; depth++ {
		i := strings.IndexByte(a, '.')
		if i < 0 {
			break
		}
		a = a[i+1:]
		want["*."+a] = depth
	}
	f, err := os.Open(path)
	if err != nil {
		return "", false, err
	}
	defer f.Close()
	best := -1
	sc := bufio.NewScanner(f)
	for sc.Scan() {
		line := sc.Text()
		o, _, found := strings.Cut(line, "\t")
		if !found {
			continue
		}
		if d, hit := want[o]; hit && (best < 0 || d < best) {
			best, owner = d, o
		}
	}
	return owner, best >= 0, sc.Err()
}