gosub_baleen

Experimental network request filter for Gosub (baleen: how a whale filters krill). Loads adblock rule lists (ABP/uBO syntax) and answers "should this request be blocked?" without iterating over rules.

Layout

• crates/gosub_baleen: engine library (parser, classifier, matcher, artifact layout)
• crates/filter-bench: benchmark harness against adblock-rust (Brave's engine) on Brave's real request corpus. bin/scale.rs measures scaling across many lists; bin/flat.rs runs the artifact write/mmap/load round trip; bin/overlay.rs validates the dynamic-overlay stack against a merged rebuild; bin/fuzz.rs is a differential fuzzer against adblock-rust; bin/probe.rs is a scratch tool for diffing single rules and requests. Engine::check_explain reports which rule fired for a request.
• data/ (gitignored), fetch with:

  mkdir -p data && cd data
  curl -sLO https://easylist.to/easylist/easylist.txt
  curl -sLO https://easylist.to/easylist/easyprivacy.txt
  curl -sLO https://raw.githubusercontent.com/brave/adblock-rust/master/data/requests.json

• data-huge/ (gitignored): the 27-list stack used by the scaling runs: EasyList + EasyPrivacy, uBO filters/privacy/badware/quick-fixes/unbreak, Fanboy annoyance + social, AdGuard base/tracking/social/annoyances, ten regional EasyLists, Peter Lowe's, HaGeZi Pro + Ultimate, OISD Big. Numbered filenames set the cumulative order.

Design

Rules are split by class at build time; each class gets its own structure:

1. Hostname fast path: ||host^ rules without options (~86k of ~105k EasyList+EasyPrivacy network rules) go into a sorted hash array. Matching walks the request hostname's dot-suffixes: at most label-count binary searches, no pattern code.
2. Token index: remaining pattern rules are indexed under their globally rarest alphanumeric token (frequency counted across the whole ruleset; only tokens that must appear in any matching URL are eligible). Matching tokenizes the URL (10-30 tokens) and evaluates only rules in hit buckets. Max bucket on EasyList+EasyPrivacy is 27, typical is 0-2.
3. Regex bucket: /.../ rules (18 in EL+EP), lazily compiled, mask-filtered before evaluation.
4. Exceptions (@@): same structures, consulted only after a block hit. $important block rules are duplicated into a small priority index that is consulted only when an exception fired; a hit there restores the block.
5. Masks first: $third-party, $script, $domain= resolve with integer compares and hash probes before any string matching.

Match cost is O(URL tokens), independent of rule count.

Flat artifact

The compiled ruleset is one position-independent, 8-byte-aligned buffer (artifact.rs): a header with a section table, then typed sections (string arena, rule table, domain entries, hostname hash arrays, open-addressing token tables, zero-token and regex id lists, stats). Engine::from_lists always builds this buffer and matches against it; Engine::as_bytes exposes it for writing to a file or memfd, and Engine::load accepts any byte-backed buffer (an mmap, a slice) after a single validation pass that checks every stored offset. Loading copies nothing; the only runtime state besides the buffer is the lazily compiled regex cache. Builds are deterministic: the same lists produce the same bytes. Only the regex sources need compilation at load time, and that stays lazy.

Measured with flat: EasyList+EasyPrivacy compile to a 4.4 MiB artifact that mmap-loads in ~220 µs with zero heap allocation and matches at the same speed as the freshly built engine (0 verdict differences over the corpus). The 27-list stack is 32.4 MiB, loads in ~70 ms (validation is one linear pass over 719k rules), same parity.

Dynamic overlay

Layered stacks any number of rulesets — typically one big mmap'd base plus small Engine::from_lists-built overlays for user rules, per-site toggles and runtime list installs — without recompiling the base artifact. Verdicts follow merged-list semantics exactly: the stack returns what one engine built from all lists concatenated would return. The overlay bench checks that property over the whole corpus (0 differences; a 5-rule user overlay builds in ~20 µs and flips 2,083 corpus verdicts, identical to a full rebuild). Per-request state (host, party, origin suffixes, URL token hashes) is prepared once via PreparedRequest and shared across layers; one small overlay costs ~100-150 ns/request on top of the base engine. A per-site kill switch is just an overlay rule: @@*$domain=example.com. Caveat: $badfilter cancellation is per-layer, so an overlay badfilter cannot cancel a rule already compiled into the base.

Hash safety

URLs are attacker-controlled, so anywhere a hash comparison is the verdict (hostname sets, $domain= sets), a hit is verified against the actual bytes stored in the arena; a hash collision can cost nanoseconds, never flip a verdict. The token index needs no verification because candidate rules are always fully evaluated against the URL. This allows a fast unkeyed wyhash-style hash (types::hash_bytes) and keeps the artifact deterministic and position-independent. A keyed hash (SipHash) would force either load-time rehashing or shipping the key in the artifact; neither is needed when hits are verified.

Results (2026-08-11, EasyList+EasyPrivacy, 242,945 real requests)

	gosub_baleen	adblock-rust 0.13
avg per request	~1.6 µs	~2.7-3.5 µs
p50 / p99	1.3 / 7.1 µs	2.3 / 11.6 µs
engine heap	4.4 MiB²	6.0 MiB¹
build time	~40 ms	~55 ms
blocked	105,652 (43.5%)	105,652 (43.5%)
verdict agreement	99.999% (2 disagreements)

Numbers are noisy run-to-run (laptop, no CPU pinning); the ~1.7-2x ratio is stable.

¹ adblock-rust's 6.0 MiB includes its cosmetic filter engine for the 24,451 ## rules we skip. Fed network-only lists it builds in 4.5 MiB, so memory on the network engine proper is near parity while the speed gap remains.

² The heap is the flat artifact itself (4.1 MiB before the artifact refactor; the open-addressing token tables trade ~0.3 MiB for a position-independent layout).

Scaling (2026-08-11, 27 lists, 719,502 network rules)

scale builds the engine over the growing data-huge/ stack and fits t = c * N^k by log-log least squares. Each point runs in a fresh process (--only N): repeated build/drop cycles in one process fragment the heap and inflated the largest configurations about 4x until measured separately.

net rules	hostname	pattern	ns/req	heap
49,468 (EasyList)	43,499	5,956	951	1.9 MiB
105,131 (+EasyPrivacy)	86,249	18,854	1,659	4.1 MiB
142,513 (+uBO/Fanboy/AdGuard base)	95,853	46,289	4,776	6.6 MiB
363,783 (+AdGuard rest, regionals)	165,888	197,327	8,475	20.6 MiB
719,502 (+HaGeZi, OISD)	521,607	197,327	7,665	32.5 MiB

Per rule class:

• Hostname rules: k ≈ 0. Growing from 166k to 522k hostname rules leaves latency unchanged (8.5 to 7.7 µs, within noise), and the three DNS lists alone run at ~400 ns/req while doubling from 215k to 432k rules (k = 0.005). The dot-suffix lookup is O(labels * log n) and the log term is invisible under cache noise.
• Pattern rules: k ≈ 0.62. Growing from 6k to 197k pattern rules takes latency from 0.95 to 8.3 µs: more URL tokens hit non-empty buckets and buckets get deeper (max bucket 17 to 476). If this ever needs work, the candidate fix is splitting hot buckets by a second token.
• Build time k ≈ 1.15, heap k ≈ 1.04 (~47 bytes/rule).

Full 27-list stack vs adblock-rust 0.13 on the same corpus: 7.2 vs 13.0 µs per request, 32.5 vs 63.0 MiB heap, build 628 vs 742 ms, verdict agreement 99.996% (9 of 242,945; see below).

Semantics

Implemented, verified request-by-request against adblock-rust:

• PSL-based third-party classification (harness-side; the engine takes third_party as an input)
• document semantics: generic pattern rules don't block top-level navigations; optionless ||host^ rules strict-block them (uBO behaviour); exception rules always apply to document requests (uBlock-issues #1501)
• tokenization parity: at most 256 URL tokens, single-char tokens skipped on both the rule and URL side
• $badfilter: cancels rules with identical pattern and options at build time, across lists (uBO-unbreak ships 215 of them, e.g. ||consensu.org^$badfilter cancelling Peter Lowe's ||consensu.org^)
• $important: a matching important block rule overrides exceptions
• $redirect= and $rewrite=abp-resource:... block; the stub resource is not served
• trailing ^| is normalized to ^ (the DNS-list allowlist idiom @@||host^|), which also keeps such rules on the hostname fast path

Known deltas:

• $match-case accepted but ignored
• rules with modifiers that can't be evaluated at request time ($csp, $removeparam, $redirect-rule, entity domains example.*, ...) are excluded (3,234 lines in EL+EP); adblock-rust keeps some of these
• EL+EP corpus, 2 of 242,945 requests disagree; both are adblock-rust deviating from uBO/ABP semantics (checked against its source):
  1. /webtracking/*$~document,~subdocument,domain=~wwwapps.ups.com: adblock-rust rejects any filter containing $~document (NetworkFilterError::NegatedDocument) and drops the rule. gosub parses it and blocks the request, matching list intent.
  2. ://ads.$~image,~xmlhttprequest,domain=~... vs a cpt=fetch request: adblock-rust types fetch as other, so the ~xmlhttprequest negation doesn't exempt it. uBO and gosub classify fetch as xmlhttprequest, which the rule exempts.
• 27-list stack, 9 of 242,945 requests disagree: 8 where adblock-rust honors @@...$redirect-rule=... exceptions (not meaningful here until a redirect subsystem exists) and 1 more instance of the fetch typing above.

Robustness

• fuzz generates random rulesets and URLs (constrained to the semantics subset both engines implement identically) and compares every verdict against adblock-rust: 540k checks across 7 seeds, ~28% block rate, 0 divergences.
• In-crate tests feed the parser 50k lines of metacharacter soup, run 50k random URLs through an engine with pathological glob rules, and load 4,000 single-bit-corrupted artifacts (each must be rejected by validation or produce an engine that checks without panicking).
• Request::host_bounds handles user:pass@ userinfo (the password colon was previously taken for a port separator, yielding user as the host) and IPv6 literals (previously yielded [). Non-network schemes (data:, about:) should not be fed through the filter; they have no meaningful host.

Run

cargo test -p gosub_baleen
cargo build --release
./target/release/filter-bench --passes 5   # needs data/, see above
./target/release/flat                      # artifact write/mmap round trip
./target/release/overlay                   # dynamic-overlay parity + overhead
./target/release/fuzz --iters 2000         # differential fuzz vs adblock-rust
./target/release/scale                     # needs data-huge/

Next steps

• Sonar integration: compile the artifact in a utility process, ship it over memfd, mmap read-only in the network process
• Perf: token-presence bitmap prefilter before map probes; perfect-hash or FST experiment for the hostname set