housecarl/internal/render/render.go

// Package render builds the nftables ruleset from a configuration: one
// table, inet housecarl, replaced as a whole in one transaction. Nothing
// else on the machine is touched (docs/design.md).
//
// A rule can become several nftables rules: one per address family it
// matches, per named set it refers to (a set can't be ORed with another in
// one rule) and per transport protocol of its services. Each carries a
// counter and a comment "hc:<kind><id>", which is how counters are read
// back, and Ruleset.Lines maps each line to its object, for nftables'
// error messages.
//
// In shadow mode (Options.Shadow, docs/shadow.md) the same rules are
// written so that they change nothing: drops and rejects accept instead
// (an accept only ends Housecarl's chain; the packet goes on to other
// tables' chains, which decide), policies accept, NAT only counts, and
// what alters packets (MSS clamping, the flowtable) is left out. What
// would be dropped, rejected or translated carries a marker in its
// comment ("[would drop]"), which the tracer reads.
package render

import (
	"fmt"
	"net/netip"
	"sort"
	"strings"

	"housecarl/internal/model"
)

// Table is Housecarl's table.
const Table = "housecarl"

// LogGroup is the netlink log group logged packets are sent to, where
// housecarld reads them (internal/nflog).
const LogGroup = 4171

// Options carry what rendering needs from the running system.
type Options struct {
	// Interfaces that exist now; flowtable devices that don't are left
	// out (nftables refuses them). Nil: assume they all exist.
	Interfaces map[string]bool
	// Elements are dynamic sets' current entries, re-added in the same
	// transaction so a reload keeps them: set name → entries.
	Elements map[string][]Element
	// Quotas are the rules' quotas' used bytes (quota name, quota_r12),
	// and QuotaSets the per-address quotas' entries (set name,
	// quota_r12_v4), so a reload keeps what was used.
	Quotas    map[string]int64
	QuotaSets map[string][]Element
	// DeviceSets are the per-device traffic counters' entries
	// (stats_up_v4 …), so a reload keeps them.
	DeviceSets map[string][]Element
	// Shadow renders for shadow mode: nothing is blocked, rejected,
	// translated or changed (see the package comment).
	Shadow bool
	// ShadowBefore runs the filter chains just before other tables' on
	// their hooks (priority - 10) instead of just after (+ 10).
	ShadowBefore bool
}

// Would marks, in shadow mode, a rule's comment with what it would do:
// "[would drop]".
func Would(action string) string { return "[would " + action + "]" }

// Element is a dynamic set's entry with its remaining lifetime, or a
// per-address quota's entry with what it used.
type Element struct {
	Addr    string `json:"address"`
	Timeout int    `json:"timeout,omitempty"` // seconds left (0: none)
	Used    int64  `json:"used,omitempty"`    // bytes
	// Packets and Bytes are a per-device counter's.
	Packets uint64 `json:"packets,omitempty"`
	Bytes   uint64 `json:"bytes,omitempty"`
}

// QuotaName is the name of a rule's quota: the named quota of a total
// quota, and (with _v4, _v6) the sets of a per-address one.
func QuotaName(ruleID int64) string { return fmt.Sprintf("quota_r%d", ruleID) }

// Ruleset is the rendered nftables script.
type Ruleset struct {
	Text string
	// Lines maps a line number (1-based) to the object it came from
	// ("input #12 (ssh)", "built-in: established").
	Lines map[int]string
}

// Object returns what the line belongs to (nearest object above it).
func (r *Ruleset) Object(line int) string {
	for l := line; l > 0; l-- {
		if o, ok := r.Lines[l]; ok {
			return o
		}
	}
	return ""
}

type writer struct {
	b     strings.Builder
	line  int
	lines map[int]string
}

func (w *writer) emit(obj, format string, args ...any) {
	w.line++
	if obj != "" {
		w.lines[w.line] = obj
	}
	fmt.Fprintf(&w.b, format, args...)
	w.b.WriteByte('\n')
}

// Render builds the ruleset for st.
func Render(st *model.State, opt Options) *Ruleset {
	w := &writer{lines: map[int]string{}}
	r := &renderer{st: st, opt: opt, w: w}
	r.render()
	return &Ruleset{Text: w.b.String(), Lines: w.lines}
}

type renderer struct {
	st  *model.State
	opt Options
	w   *writer
	// meters are the per-address limit, connection and quota sets, and
	// the named quotas, the rules need.
	meters []string
}

func (r *renderer) render() {
	w := r.w
	w.emit("", "# Built by Housecarl from its database; changes made here are lost.")
	if r.opt.Shadow {
		w.emit("", "# Shadow mode: nothing here drops, rejects or translates; other tables decide.")
	}
	w.emit("", "table inet %s {}", Table)
	w.emit("", "delete table inet %s", Table)
	w.emit("", "table inet %s {", Table)
	r.sets()
	r.deviceSets()
	devices := r.flowtableDevices()
	if len(devices) > 0 {
		w.emit("built-in: flowtable", "\tflowtable ft { hook ingress priority filter; devices = { %s }; }", strings.Join(quoteAll(devices), ", "))
	}
	// The chains are written to a buffer first: per-source limits add
	// meter sets, which must come before them.
	chains := &writer{lines: map[int]string{}}
	saved := r.w
	r.w = chains
	r.early()
	r.input()
	r.forward(len(devices) > 0)
	r.output()
	r.dstnat()
	r.srcnat()
	r.w = saved
	for _, m := range r.meters {
		w.emit("built-in: meters", "%s", m)
	}
	base := w.line
	w.b.WriteString(chains.b.String())
	for l, o := range chains.lines {
		w.lines[base+l] = o
	}
	w.line = base + chains.line
	w.emit("", "}")
	r.elements()
}

// ---- sets

func (r *renderer) sets() {
	for _, s := range r.st.Sets {
		obj := "set " + s.Name
		if s.Dynamic {
			for _, f := range []string{"v4", "v6"} {
				timeout := ""
				if s.Timeout > 0 {
					timeout = fmt.Sprintf(" timeout %ds;", s.Timeout)
				}
				r.w.emit(obj, "\tset %s { type %s; flags timeout;%s }", setName(s.Name, f == "v6"), addrType(f == "v6"), timeout)
			}
			continue
		}
		has4, has6 := s.Families()
		for _, v6 := range []bool{false, true} {
			if v6 && !has6 || !v6 && !has4 {
				continue
			}
			r.w.emit(obj, "\tset %s { type %s; flags interval; auto-merge; elements = { %s } }",
				setName(s.Name, v6), addrType(v6), strings.Join(s.FamilyEntries(v6), ", "))
		}
	}
}

func (r *renderer) elements() {
	names := make([]string, 0, len(r.opt.Elements))
	for n := range r.opt.Elements {
		names = append(names, n)
	}
	sort.Strings(names)
	for _, n := range names {
		s := r.st.Set(n)
		if s == nil || !s.Dynamic {
			continue
		}
		for _, e := range r.opt.Elements[n] {
			a, err := model.ParseAddress(e.Addr)
			if err != nil {
				continue
			}
			timeout := ""
			if e.Timeout > 0 {
				timeout = fmt.Sprintf(" timeout %ds", e.Timeout)
			}
			r.w.emit("set "+s.Name, "add element inet %s %s { %s%s }", Table, setName(s.Name, a.IsV6()), a.String(), timeout)
		}
	}
}

// IsDeviceSet reports whether a set is a per-device traffic counter.
func IsDeviceSet(name string) bool {
	return strings.HasPrefix(name, "stats_up_") || strings.HasPrefix(name, "stats_down_")
}

// deviceSets declares the per-device traffic counters, with what they
// counted before a reload.
func (r *renderer) deviceSets() {
	if !r.st.Settings.StatsPerDevice || len(r.st.ExternalInterfaces()) == 0 {
		return
	}
	for _, dir := range []string{"up", "down"} {
		for _, v6 := range []bool{false, true} {
			name := setName("stats_"+dir, v6)
			var elems []string
			for _, e := range r.opt.DeviceSets[name] {
				a, err := netip.ParseAddr(e.Addr)
				if err != nil || a.Is6() != v6 {
					continue
				}
				timeout := ""
				if e.Timeout > 0 {
					timeout = fmt.Sprintf(" timeout %ds", e.Timeout)
				}
				elems = append(elems, fmt.Sprintf("%s%s counter packets %d bytes %d", a, timeout, e.Packets, e.Bytes))
			}
			list := ""
			if len(elems) > 0 {
				list = " elements = { " + strings.Join(elems, ", ") + " }"
			}
			r.w.emit("built-in: stats", "\tset %s { type %s; flags dynamic,timeout; timeout 1h; size 65535; counter;%s }", name, addrType(v6), list)
		}
	}
}

// deviceCounts counts forwarded traffic per inside address: what leaves
// for an external zone by its source, what comes from one by its
// destination (IPv6 by /64).
func (r *renderer) deviceCounts() {
	ext := r.st.ExternalInterfaces()
	if !r.st.Settings.StatsPerDevice || len(ext) == 0 {
		return
	}
	e := ifaces(ext)
	r.builtin("stats", "iifname != %s oifname %s update @stats_up_v4 { ip saddr }", e, e)
	r.builtin("stats", "iifname != %s oifname %s update @stats_up_v6 { ip6 saddr and ffff:ffff:ffff:ffff:: }", e, e)
	r.builtin("stats", "iifname %s oifname != %s update @stats_down_v4 { ip daddr }", e, e)
	r.builtin("stats", "iifname %s oifname != %s update @stats_down_v6 { ip6 daddr and ffff:ffff:ffff:ffff:: }", e, e)
}

// SetName is the nftables name of a set's family part.
func SetName(name string, v6 bool) string { return setName(name, v6) }

func setName(name string, v6 bool) string {
	if v6 {
		return name + "_v6"
	}
	return name + "_v4"
}

func addrType(v6 bool) string {
	if v6 {
		return "ipv6_addr"
	}
	return "ipv4_addr"
}

func (r *renderer) flowtableDevices() []string {
	if r.opt.Shadow {
		// Offloaded connections skip every table's forward chain.
		return nil
	}
	var out []string
	for _, d := range r.st.Settings.FlowtableDevices {
		if r.opt.Interfaces == nil || r.opt.Interfaces[d] {
			out = append(out, d)
		}
	}
	return out
}

// ---- chains

func (r *renderer) chain(name, hook, prio, policy string) {
	nat := prio == "dstnat" || prio == "srcnat"
	if r.opt.Shadow {
		// NAT chains are asked in turn only until one translates: to
		// count anything, Housecarl's must come first.
		if nat || r.opt.ShadowBefore {
			prio += " - 10"
		} else {
			prio += " + 10"
		}
		policy = model.PolicyAccept
	}
	r.w.emit("", "\tchain %s {", name)
	r.w.emit("", "\t\ttype %s hook %s priority %s; policy %s;", map[bool]string{true: "nat", false: "filter"}[nat], hook, prio, policy)
}

func (r *renderer) end() { r.w.emit("", "\t}") }

func (r *renderer) builtin(name, format string, args ...any) {
	r.w.emit("built-in: "+name, "\t\t"+format+" comment \"hc:b-%s\"", append(args, name)...)
}

// builtinDrop writes a built-in that drops what it matches, or in shadow
// mode counts it.
func (r *renderer) builtinDrop(name, format string, args ...any) {
	if r.opt.Shadow {
		r.w.emit("built-in: "+name, "\t\t"+format+" counter accept comment \"hc:b-%s %s\"", append(args, name, Would("drop"))...)
		return
	}
	r.builtin(name, format+" counter drop", args...)
}

func (r *renderer) early() {
	st := r.st
	r.chain("early", "prerouting", "raw", "accept")
	ext := st.ExternalInterfaces()
	if st.Settings.Builtins.Antispoof && len(ext) > 0 {
		v4 := append([]string(nil), st.Settings.AntispoofV4...)
		v6 := append([]string(nil), st.Settings.AntispoofV6...)
		for _, p := range st.Settings.OwnPrefixes {
			if a, err := model.ParseAddress(p); err == nil && a.IsV6() {
				v6 = append(v6, a.String())
			} else if err == nil {
				v4 = append(v4, a.String())
			}
		}
		if len(v4) > 0 {
			r.builtinDrop("antispoof", "iifname %s ip saddr { %s }", ifaces(ext), strings.Join(v4, ", "))
		}
		if len(v6) > 0 {
			r.builtinDrop("antispoof6", "iifname %s ip6 saddr { %s }", ifaces(ext), strings.Join(v6, ", "))
		}
	}
	r.rules(model.ChainEarly, true)
	r.rules(model.ChainEarly, false)
	r.end()
}

var (
	icmpv6Errors = "destination-unreachable, packet-too-big, time-exceeded, parameter-problem"
	icmpv6ND     = "nd-router-solicit, nd-router-advert, nd-neighbor-solicit, nd-neighbor-advert"
	icmpv6MLD    = "mld-listener-query, mld-listener-report, mld-listener-done, mld2-listener-report"
)

func (r *renderer) connBuiltins() {
	b := r.st.Settings.Builtins
	if b.Established {
		r.builtin("established", "ct state established,related counter accept")
	}
	if b.DropInvalid {
		r.builtinDrop("invalid", "ct state invalid")
	}
}

func (r *renderer) input() {
	st := r.st
	b := st.Settings.Builtins
	r.chain("input", "input", "filter", st.Settings.InputPolicy)
	if b.Loopback {
		r.builtin("loopback", "iifname \"lo\" accept")
	}
	// Rules that count traffic see every packet: before the established
	// connections are accepted.
	r.rules(model.ChainInput, true)
	r.connBuiltins()
	ext := st.ExternalInterfaces()
	if b.ICMPv6 {
		r.builtin("icmpv6", "icmpv6 type { %s, echo-request, echo-reply } counter accept", icmpv6Errors)
		r.builtin("icmpv6-nd", "icmpv6 type { %s } ip6 hoplimit 255 counter accept", icmpv6ND)
		r.builtin("icmpv6-mld", "ip6 saddr fe80::/10 icmpv6 type { %s } counter accept", icmpv6MLD)
	}
	if b.PingInternal {
		if len(ext) > 0 {
			r.builtin("ping", "iifname != %s icmp type echo-request counter accept", ifaces(ext))
		} else {
			r.builtin("ping", "icmp type echo-request counter accept")
		}
	}
	if b.DHCPv6Client && len(ext) > 0 {
		r.builtin("dhcpv6-client", "iifname %s ip6 saddr fe80::/10 udp dport 546 counter accept", ifaces(ext))
	}
	r.rules(model.ChainInput, false)
	r.policyTail("input", st.Settings.InputPolicy)
	r.end()
}

func (r *renderer) forward(flowtable bool) {
	st := r.st
	b := st.Settings.Builtins
	r.chain("forward", "forward", "filter", st.Settings.ForwardPolicy)
	ext := st.ExternalInterfaces()
	// Shadow mode changes no packet.
	if b.MSSClamp && len(ext) > 0 && !r.opt.Shadow {
		r.builtin("mss-clamp", "oifname %s tcp flags syn tcp option maxseg size set rt mtu", ifaces(ext))
	}
	r.rules(model.ChainForward, true)
	r.deviceCounts()
	if flowtable {
		r.builtin("flowtable", "meta l4proto { tcp, udp } flow add @ft")
	}
	r.connBuiltins()
	if b.ICMPv6 {
		r.builtin("icmpv6", "icmpv6 type { %s } counter accept", icmpv6Errors)
	}
	r.forwardAccepts()
	r.rules(model.ChainForward, false)
	r.policyTail("forward", st.Settings.ForwardPolicy)
	r.end()
}

func (r *renderer) output() {
	st := r.st
	r.chain("output", "output", "filter", st.Settings.OutputPolicy)
	r.rules(model.ChainOutput, true)
	if st.Settings.OutputPolicy == model.PolicyDrop {
		if st.Settings.Builtins.Loopback {
			r.builtin("loopback", "oifname \"lo\" accept")
		}
		if st.Settings.Builtins.Established {
			r.builtin("established", "ct state established,related counter accept")
		}
		if st.Settings.Builtins.ICMPv6 {
			r.builtin("icmpv6", "icmpv6 type { %s, echo-request, echo-reply, %s, %s } counter accept", icmpv6Errors, icmpv6ND, icmpv6MLD)
		}
	}
	r.rules(model.ChainOutput, false)
	r.policyTail("output", st.Settings.OutputPolicy)
	r.end()
}

// policyTail counts (and optionally logs) what reaches the policy. In
// shadow mode, where the policy accepts, that is what it would drop, and
// it is always logged: the log is how shadow mode shows it.
func (r *renderer) policyTail(chain, policy string) {
	if policy != model.PolicyDrop {
		return
	}
	obj := "policy: " + chain
	if r.opt.Shadow || r.st.Settings.LogPolicyDrops && chain != "output" {
		r.w.emit(obj, "\t\tlimit rate 10/second burst 20 packets log prefix %s group %d", quote("hc "+chain+" policy drop: "), LogGroup)
	}
	if r.opt.Shadow {
		r.w.emit(obj, "\t\tcounter comment \"hc:p-%s %s\"", chain, Would("drop"))
		return
	}
	r.w.emit(obj, "\t\tcounter comment \"hc:p-%s\"", chain)
}

// ---- rules

// rules writes a chain's rules: those that count traffic (traffic true),
// or the others.
func (r *renderer) rules(chain string, traffic bool) {
	for _, rule := range r.st.Rules {
		if rule.Chain != chain || rule.Disabled || rule.ChecksEveryPacket() != traffic {
			continue
		}
		obj := rule.Label()
		mark := fmt.Sprintf("r%d", rule.ID)
		if rule.Raw != "" {
			raw := rule.Raw
			if r.opt.Shadow {
				var ok bool
				if raw, ok = ShadowRaw(raw); !ok {
					r.w.emit(obj, "\t\t# left out in shadow mode: %s", rule.Raw)
					continue
				}
			}
			r.w.emit(obj, "\t\t%s", raw)
			continue
		}
		var tail []string
		if len(rule.CtState) > 0 {
			tail = append(tail, "ct state "+list(rule.CtState))
		}
		if len(rule.CtStatus) > 0 {
			tail = append(tail, "ct status "+list(rule.CtStatus))
		}
		if len(rule.Days) > 0 {
			var ds []string
			for _, d := range rule.Days {
				ds = append(ds, quote(strings.ToUpper(d[:1])+strings.ToLower(d[1:])))
			}
			tail = append(tail, "meta day "+set(ds))
		}
		if rule.HourFrom != "" {
			tail = append(tail, hours(rule.HourFrom, rule.HourTo))
		}
		verdict := r.verdict(rule, mark)
		perAddress := rule.ConnLimit > 0 || rule.Limit.PerAddress() != "" || rule.Quota.PerAddress() != ""
		for _, line := range r.expand(rule.Match, perAddress) {
			parts := append([]string{}, line.parts...)
			parts = append(parts, tail...)
			if l := rule.Limit; l != nil {
				parts = append(parts, r.limit(rule, line, l))
			}
			if rule.ConnLimit > 0 {
				parts = append(parts, r.connLimit(rule, line))
			}
			if rule.Quota != nil {
				parts = append(parts, r.quota(rule, line))
			}
			parts = append(parts, verdict)
			r.w.emit(obj, "\t\t%s", strings.Join(nonEmpty(parts), " "))
		}
	}
}

func (r *renderer) verdict(rule *model.Rule, mark string) string {
	var v []string
	v = append(v, "counter")
	if rule.Log || rule.Action == model.ActionLog {
		prefix := rule.LogPrefix
		if prefix == "" {
			prefix = fmt.Sprintf("hc %s #%d %s: ", rule.Chain, rule.ID, rule.Action)
		}
		v = append(v, fmt.Sprintf("log prefix %s group %d", quote(prefix), LogGroup))
	}
	text := rule.Comment
	switch {
	case r.opt.Shadow && (rule.Action == model.ActionDrop || rule.Action == model.ActionReject):
		// It ends Housecarl's chain as the drop would, and no more.
		v = append(v, model.ActionAccept)
		text = Would(rule.Action) + " " + text
	case rule.Action == model.ActionAccept, rule.Action == model.ActionDrop:
		v = append(v, rule.Action)
	case rule.Action == model.ActionReject:
		if rule.RejectWith == "tcp-reset" {
			v = append(v, "reject with tcp reset")
		} else {
			v = append(v, "reject")
		}
	}
	v = append(v, "comment "+comment(mark, text))
	return strings.Join(v, " ")
}

// limit renders a rate limit: of packets or bytes; per source or
// destination with a meter set per family, whose entries are refreshed
// by each packet (update) and forgotten once a source is quiet.
func (r *renderer) limit(rule *model.Rule, line expanded, l *model.Limit) string {
	unit := ""
	if _, ok := model.ByteUnits[l.Unit]; ok {
		unit = " " + l.Unit
	}
	rate := fmt.Sprintf("limit rate %s%d%s/%s", map[bool]string{true: "over ", false: ""}[l.Over], l.Rate, unit, l.Per)
	if l.Burst > 0 {
		burstUnit := " packets"
		if unit != "" {
			burstUnit = unit
		}
		rate += fmt.Sprintf(" burst %d%s", l.Burst, burstUnit)
	}
	addr := l.PerAddress()
	if addr == "" {
		return rate
	}
	name := fmt.Sprintf("meter_r%d_%s", rule.ID, line.fam)
	if !r.hasMeter(name) {
		r.meters = append(r.meters, fmt.Sprintf("\tset %s { type %s; flags dynamic,timeout; timeout 1%s; }", name, addrType(line.fam == "v6"), map[string]string{"second": "m", "minute": "m", "hour": "h", "day": "d"}[l.Per]))
	}
	return fmt.Sprintf("update @%s { %s %s }", name, r.addrKey(rule, line.fam, addr), rate)
}

// addrKey is what a per-address meter counts by: "ip saddr", or grouped
// by a prefix, "ip6 saddr and ffff:ffff:ffff:ffff::".
func (r *renderer) addrKey(rule *model.Rule, fam, addr string) string {
	v4, v6 := rule.Groups()
	bits, size := v4, 32
	if fam == "v6" {
		bits, size = v6, 128
	}
	key := ipKeyword(fam) + " " + addr
	if bits >= size {
		return key
	}
	mask := make([]byte, size/8)
	for i := 0; i < bits; i++ {
		mask[i/8] |= 0x80 >> (i % 8)
	}
	m, _ := netip.AddrFromSlice(mask)
	return key + " and " + m.String()
}

func (r *renderer) connLimit(rule *model.Rule, line expanded) string {
	name := fmt.Sprintf("conn_r%d_%s", rule.ID, line.fam)
	if !r.hasMeter(name) {
		r.meters = append(r.meters, fmt.Sprintf("\tset %s { type %s; flags dynamic; size 65535; }", name, addrType(line.fam == "v6")))
	}
	return fmt.Sprintf("add @%s { %s ct count over %d }", name, r.addrKey(rule, line.fam, "saddr"), rule.ConnLimit)
}

// quota renders a rule's quota: a named quota shared by the rule's lines
// (both families count against one allowance), or per address a set of
// quotas per family. What was used comes back from Options, so a reload
// doesn't reset it.
func (r *renderer) quota(rule *model.Rule, line expanded) string {
	q := rule.Quota
	amount := quotaAmount(q)
	name := QuotaName(rule.ID)
	addr := q.PerAddress()
	if addr == "" {
		if !r.hasMeter(name) {
			used := ""
			if u := r.opt.Quotas[name]; u > 0 {
				used = fmt.Sprintf(" used %d bytes", u)
			}
			r.meters = append(r.meters, fmt.Sprintf("\tquota %s { %s%s }", name, amount, used))
		}
		return fmt.Sprintf("quota name %s", quote(name))
	}
	set := name + "_" + line.fam
	if !r.hasMeter(set) {
		var elems []string
		for _, e := range r.opt.QuotaSets[set] {
			a, err := netip.ParseAddr(e.Addr)
			if err != nil || a.Is6() != (line.fam == "v6") {
				continue
			}
			used := ""
			if e.Used > 0 {
				used = fmt.Sprintf(" used %d bytes", e.Used)
			}
			elems = append(elems, fmt.Sprintf("%s quota %s%s", a, amount, used))
		}
		list := ""
		if len(elems) > 0 {
			list = " elements = { " + strings.Join(elems, ", ") + " }"
		}
		r.meters = append(r.meters, fmt.Sprintf("\tset %s { type %s; flags dynamic; size 65535;%s }", set, addrType(line.fam == "v6"), list))
	}
	return fmt.Sprintf("add @%s { %s quota %s }", set, r.addrKey(rule, line.fam, addr), amount)
}

// quotaAmount writes a quota: "over 5000 mbytes" (nftables 1.1.3 has no
// gbytes).
func quotaAmount(q *model.Quota) string {
	n, unit := q.Bytes, "bytes"
	for _, u := range []string{"mbytes", "kbytes"} {
		if n >= model.ByteUnits[u] && n%model.ByteUnits[u] == 0 {
			n, unit = n/model.ByteUnits[u], u
			break
		}
	}
	if q.Over {
		return fmt.Sprintf("over %d %s", n, unit)
	}
	return fmt.Sprintf("until %d %s", n, unit)
}

func (r *renderer) hasMeter(name string) bool {
	for _, m := range r.meters {
		if strings.Contains(m, "set "+name+" ") || strings.Contains(m, "quota "+name+" ") {
			return true
		}
	}
	return false
}

// expanded is one nftables rule's match: its family ("v4", "v6" or ""
// for both) and its parts.
type expanded struct {
	fam   string
	parts []string
}

// expand turns a Match into nftables matches: one per family, named set
// and protocol it needs (see the package comment).
func (r *renderer) expand(m model.Match, perSource bool) []expanded {
	st := r.st
	var head []string
	if len(m.InZones) > 0 {
		head = append(head, "iifname "+neg(m.NotIn)+ifaces(r.zoneIfaces(m.InZones)))
	}
	if len(m.OutZones) > 0 {
		head = append(head, "oifname "+neg(m.NotOut)+ifaces(r.zoneIfaces(m.OutZones)))
	}
	s4, s6 := st.SplitRefs(m.Sources)
	d4, d6 := st.SplitRefs(m.Destinations)
	entries := st.ServiceEntries(m.Services)
	hasICMP := false
	for _, e := range entries {
		hasICMP = hasICMP || e.IsICMP()
	}
	// A rule that names no addresses and no ICMP needs no family split,
	// unless it is limited to one family or keeps per-source state.
	perFamily := perSource || len(m.Sources) > 0 || len(m.Destinations) > 0 || hasICMP || m.Family != ""
	if !perFamily {
		var out []expanded
		for _, svc := range serviceAlts(entries, "") {
			out = append(out, expanded{"", append(append([]string{}, head...), svc...)})
		}
		return out
	}
	var out []expanded
	for _, fam := range []string{"v4", "v6"} {
		if m.Family == model.FamilyIPv4 && fam == "v6" || m.Family == model.FamilyIPv6 && fam == "v4" {
			continue
		}
		src, dst := s4, d4
		if fam == "v6" {
			src, dst = s6, d6
		}
		srcAlts, ok := addrAlts(fam, "saddr", src, len(m.Sources) > 0, m.NotSources)
		if !ok {
			continue
		}
		dstAlts, ok := addrAlts(fam, "daddr", dst, len(m.Destinations) > 0, m.NotDests)
		if !ok {
			continue
		}
		svcs := serviceAlts(entries, fam)
		if svcs == nil {
			continue
		}
		for _, sa := range srcAlts {
			for _, da := range dstAlts {
				for _, sv := range svcs {
					parts := append([]string{}, head...)
					if sa == "" && da == "" && !strings.HasPrefix(strings.Join(sv, " "), "icmp") {
						parts = append(parts, "meta nfproto "+map[string]string{"v4": "ipv4", "v6": "ipv6"}[fam])
					}
					parts = append(parts, sa, da)
					parts = append(parts, sv...)
					out = append(out, expanded{fam, parts})
				}
			}
		}
	}
	return out
}

// addrAlts returns the alternatives for one side's addresses in one
// family: one per named set, plus one for the literals. Negated, all go
// into one rule. ok is false when the side was given but has nothing of
// this family (the rule can't match it).
func addrAlts(fam, dir string, refs model.FamilyRefs, given, negated bool) (alts []string, ok bool) {
	kw := ipKeyword(fam) + " " + dir + " "
	if !given {
		return []string{""}, true
	}
	if negated {
		var parts []string
		for _, s := range refs.Sets {
			parts = append(parts, kw+"!= @"+setName(s, fam == "v6"))
		}
		if len(refs.Literals) > 0 {
			parts = append(parts, kw+"!= "+set(refs.Literals))
		}
		return []string{strings.Join(parts, " ")}, true
	}
	if refs.Empty() {
		return nil, false
	}
	for _, s := range refs.Sets {
		alts = append(alts, kw+"@"+setName(s, fam == "v6"))
	}
	if len(refs.Literals) > 0 {
		alts = append(alts, kw+set(refs.Literals))
	}
	return alts, true
}

// serviceAlts groups service entries into nftables matches: one per
// transport protocol, and one for the family's ICMP types. fam "" is both
// families (no ICMP then). nil means nothing matches this family.
func serviceAlts(entries []model.ServiceEntry, fam string) [][]string {
	if len(entries) == 0 {
		return [][]string{{}}
	}
	ports := map[string][]string{}
	var protos []string
	var icmp []string
	for _, e := range entries {
		switch {
		case e.Proto == "icmp" && fam == "v4", e.Proto == "icmpv6" && fam == "v6":
			icmp = append(icmp, e.Type)
		case !e.IsICMP():
			if _, ok := ports[e.Proto]; !ok {
				protos = append(protos, e.Proto)
			}
			ports[e.Proto] = append(ports[e.Proto], e.Ports)
		}
	}
	var out [][]string
	for _, p := range protos {
		out = append(out, []string{p + " dport " + set(ports[p])})
	}
	if len(icmp) > 0 {
		out = append(out, []string{map[string]string{"v4": "icmp", "v6": "icmpv6"}[fam] + " type " + set(icmp)})
	}
	return out
}

func (r *renderer) zoneIfaces(zones []string) []string {
	var out []string
	for _, n := range zones {
		if z := r.st.Zone(n); z != nil {
			out = append(out, z.Interfaces...)
		}
	}
	return out
}

// ---- NAT

func (r *renderer) dstnat() {
	st := r.st
	r.chain("dstnat", "prerouting", "dstnat", "accept")
	for _, x := range st.Redirects {
		if x.Disabled {
			continue
		}
		obj := x.Label()
		mark := fmt.Sprintf("d%d", x.ID)
		for _, line := range r.expand(x.Match, false) {
			to := x.ToPort
			if to == "" {
				for _, e := range st.ServiceEntries(x.Services) {
					if !e.IsICMP() {
						lo, _ := model.PortRange(e.Ports)
						to = fmt.Sprint(lo)
						break
					}
				}
			}
			r.w.emit(obj, "\t\t%s counter %s", strings.Join(nonEmpty(line.parts), " "), r.nat("redirect to :"+to, mark, x.Comment))
		}
	}
	ext := st.ExternalInterfaces()
	for _, f := range st.Forwards {
		if f.Disabled || f.To == "" {
			continue
		}
		obj := f.Label()
		mark := fmt.Sprintf("f%d", f.ID)
		where := []string{}
		if len(f.PublicAddresses) > 0 {
			pub, _ := st.SplitRefs(f.PublicAddresses)
			alts, _ := addrAlts("v4", "daddr", pub, true, false)
			where = alts
		} else {
			where = []string{"iifname " + ifaces(ext) + " meta nfproto ipv4"}
		}
		src4, _ := st.SplitRefs(f.Sources)
		srcAlts, ok := addrAlts("v4", "saddr", src4, len(f.Sources) > 0, false)
		if !ok {
			continue
		}
		to := f.To
		if f.ToPort != "" {
			to += ":" + f.ToPort
		}
		for _, wh := range where {
			for _, sa := range srcAlts {
				for _, p := range f.Protocols {
					r.w.emit(obj, "\t\t%s counter %s", strings.Join(nonEmpty([]string{wh, sa, p + " dport " + f.Ports}), " "), r.nat("dnat ip to "+to, mark, f.Name+" "+f.Comment))
				}
			}
		}
	}
	r.end()
}

// forwardAccepts lets port-forwarded connections through, and opens the
// IPv6 pinholes.
func (r *renderer) forwardAccepts() {
	st := r.st
	for _, f := range st.Forwards {
		if f.Disabled {
			continue
		}
		obj := f.Label()
		mark := fmt.Sprintf("f%d", f.ID)
		ports := f.Ports
		if f.ToPort != "" {
			ports = f.ToPort
		}
		src4, src6 := st.SplitRefs(f.Sources)
		if f.To != "" {
			if srcAlts, ok := addrAlts("v4", "saddr", src4, len(f.Sources) > 0, false); ok {
				for _, sa := range srcAlts {
					for _, p := range f.Protocols {
						r.w.emit(obj, "\t\t%s counter accept comment %s", strings.Join(nonEmpty([]string{"ip daddr " + f.To, sa, p + " dport " + ports, "ct status dnat"}), " "), comment(mark, f.Name))
					}
				}
			}
		}
		if f.To6 != "" {
			if srcAlts, ok := addrAlts("v6", "saddr", src6, len(f.Sources) > 0, false); ok {
				for _, sa := range srcAlts {
					for _, p := range f.Protocols {
						// No translation for IPv6: the host's own port.
						r.w.emit(obj, "\t\t%s counter accept comment %s", strings.Join(nonEmpty([]string{"ip6 daddr " + f.To6, sa, p + " dport " + ports}), " "), comment(mark+"-6", f.Name))
					}
				}
			}
		}
	}
}

func (r *renderer) srcnat() {
	st := r.st
	r.chain("srcnat", "postrouting", "srcnat", "accept")
	ext := st.ExternalInterfaces()
	for _, f := range st.Forwards {
		if f.Disabled || !f.Hairpin || f.To == "" {
			continue
		}
		obj := f.Label()
		mark := fmt.Sprintf("f%d-hairpin", f.ID)
		ports := f.Ports
		if f.ToPort != "" {
			ports = f.ToPort
		}
		var srcAlts []string
		if len(f.HairpinSources) > 0 {
			h4, _ := st.SplitRefs(f.HairpinSources)
			alts, ok := addrAlts("v4", "saddr", h4, true, false)
			if !ok {
				continue
			}
			srcAlts = alts
		} else if len(ext) > 0 {
			srcAlts = []string{"iifname != " + ifaces(ext)}
		} else {
			srcAlts = []string{""}
		}
		for _, sa := range srcAlts {
			for _, p := range f.Protocols {
				r.w.emit(obj, "\t\t%s counter %s", strings.Join(nonEmpty([]string{sa, "ip daddr " + f.To, p + " dport " + ports, "ct status dnat"}), " "), r.nat("masquerade", mark, f.Name))
			}
		}
	}
	for _, x := range st.SNATs {
		if x.Disabled {
			continue
		}
		obj := x.Label()
		mark := fmt.Sprintf("s%d", x.ID)
		for _, line := range r.expand(x.Match, false) {
			// Masquerading is for IPv4; IPv6 only when asked for (NAT66).
			if x.To == "" && line.fam == "v6" && x.Family != model.FamilyIPv6 {
				continue
			}
			if x.To == "" && line.fam == "" && x.Family != model.FamilyIPv6 {
				line.parts = append([]string{"meta nfproto ipv4"}, line.parts...)
			}
			action := "masquerade"
			if x.To != "" {
				if a, err := model.ParseAddress(x.To); err == nil && a.IsV6() {
					if line.fam == "v4" {
						continue
					}
					action = "snat ip6 to " + x.To
				} else {
					if line.fam == "v6" {
						continue
					}
					action = "snat ip to " + x.To
				}
			}
			r.w.emit(obj, "\t\t%s counter %s", strings.Join(nonEmpty(line.parts), " "), r.nat(action, mark, x.Comment))
		}
	}
	r.end()
}

// nat writes a NAT rule's statement and comment; in shadow mode only the
// comment, saying what it would do ("[would dnat]").
func (r *renderer) nat(action, mark, text string) string {
	if r.opt.Shadow {
		return "comment " + comment(mark, Would(strings.Fields(action)[0])+" "+text)
	}
	return action + " comment " + comment(mark, text)
}

// ---- helpers

// hours writes a time window. nftables can't take a range past midnight,
// so 22:00-06:00 becomes "not 06:00-21:59:59".
func hours(from, to string) string {
	if from <= to {
		return fmt.Sprintf("meta hour %s-%s", quote(from), quote(to))
	}
	h, m := 0, 0
	fmt.Sscanf(from, "%d:%d", &h, &m)
	mins := h*60 + m - 1
	return fmt.Sprintf("meta hour != %s-%s", quote(to), quote(fmt.Sprintf("%02d:%02d:59", mins/60, mins%60)))
}

func ipKeyword(fam string) string {
	if fam == "v6" {
		return "ip6"
	}
	return "ip"
}

func neg(b bool) string {
	if b {
		return "!= "
	}
	return ""
}

// ifaces writes interface names: one quoted, or an anonymous set.
func ifaces(names []string) string {
	q := quoteAll(names)
	if len(q) == 1 {
		return q[0]
	}
	return "{ " + strings.Join(q, ", ") + " }"
}

func quoteAll(in []string) []string {
	out := make([]string, len(in))
	for i, s := range in {
		out[i] = quote(s)
	}
	return out
}

func quote(s string) string {
	return `"` + strings.NewReplacer(`"`, `'`, `\`, `/`, "\n", " ").Replace(s) + `"`
}

// set writes one value, or an anonymous set of several.
func set(vals []string) string {
	if len(vals) == 1 {
		return vals[0]
	}
	return "{ " + strings.Join(vals, ", ") + " }"
}

// list writes ct state/status values: one, or a comma list.
func list(vals []string) string {
	return strings.Join(vals, ",")
}

func nonEmpty(in []string) []string {
	var out []string
	for _, s := range in {
		if s != "" {
			out = append(out, s)
		}
	}
	return out
}

// comment writes the "hc:<mark> text" comment counters are read back by
// (nftables allows 128 bytes).
func comment(mark, text string) string {
	c := strings.TrimSpace("hc:" + mark + " " + strings.TrimSpace(text))
	var b strings.Builder
	for _, r := range c {
		if r >= 32 && r != 127 && b.Len()+len(string(r)) <= 120 {
			b.WriteRune(r)
		}
	}
	return quote(b.String())
}