Chute Devs

Hello everyone.

If you subscribe to a large rule-set — a regional IP list, a big ad-block domain feed, a Surge-style remote list that gets refreshed every night — the engine has to answer one awkward question on every connection: which of these fifty thousand lines applies to this flow? For years, the honest answer was: scan them. Every connection, every direction, every line, until one matched. It worked, it was exactly correct, and it was eating iOS alive.

We spent the last week of August replacing “scan everything” with “ask an index,” and then fixing the index’s own leaks. Two new layers landed in the rule engine, and then a review pass caught three real defects they introduced. The headline numbers, measured on a 50,000-line classical RULE-SET over loopback:

• p50 lookup time: 0.60 ms → 0.06 ms (10×)
• Memory per indexed RULE-SET: ~316 KB → ~105 KB
• UDP flows: matched once per flow instead of once per datagram

The important part is not that the index exists — it’s that the index fails honestly. If anything is off, the engine quietly falls back to the scan you already trust, and it says so.

The Problem With “Just Scan It”

A RULE-SET payload is a text file. Fifty thousand lines of DOMAIN-SUFFIX,example.com and IP-CIDR,203.0.113.0/24,no-resolve and a handful of GEOIP,CN and port rules. The legacy matcher did the only safe thing: for each lookup, walk the lines top to bottom, first match wins. That ordering matters — it is the whole point of Surge semantics — so we can’t sort, can’t hash the whole list, can’t cache “the answer.” Every new connection paid full price.

The second bad behavior was on iOS specifically. On iOS, every UDP datagram used to be matched twice — once by the rule engine, then again by the UDP tunnel layer as the flow fanned out — and the small result cache thrashes as soon as real UDP traffic starts. A large rule-set turned into “stream the whole file per connection, plus again per flow,” for every session that couldn’t answer from cache.

Two Indexes, One Invariant

The fix is two layers of indexing, both held to a single correctness rule: a lookup through the index must return the same rule the legacy scan would have returned. First-match-wins is the contract; the index is an optimization, never a semantic change.

A persistent per-file index

For RULE-SET payloads (classical, ipcidr, mixed Surge lists), we build a small embedded database next to the staged file:

• Domain exact / suffix lines land in keyed buckets, carrying their source line number and the payload text.
• IPv4 / IPv6 CIDR lines land in a CIDR bucket keyed by prefix, with IPv4 stored v6-mapped so bucket keys read from the same offset.
• GEOIP codes get their own bucket.
• Everything else — ports, compound AND/OR/NOT rules, odd formats — stays in an ordered residual table, matched as before.

A lookup merges candidates from every relevant bucket with an ascending walk of the residual, then returns the smallest line number whose rebuilt rule verifies against the session. That last step is the contract enforcer: buckets nominate candidates, the existing rule verifier decides. The build runs when a payload is downloaded or restored from cache; a failed build is non-fatal and silently keeps the legacy preload or streaming path.

A plan over the published rule table

Above the per-list index is a second layer: a plan of the top-level rule table, rebuilt on every publish. When the published table is purely domain-shaped — no RULE-SET / DOMAIN-SET entries — domain and domain-suffix rules hash into buckets and the matcher only consults them when that purity holds. A plan miss in that shape is provably final, so the lookup can stop without touching residual scans.

The Numbers

Both numbers are measured, not derived.

Metric	Before	After	How measured
Lookup p50, 50k-line set	~0.60 ms	~0.06 ms	Parity scenario, 50k-line list
Memory per indexed RULE-SET	~316 KB	~105 KB	iOS extension, idle UDP load
Peak memory, UDP fan-out	—	−7 MB vs naive index	File-mapped reads + small page cache

The memory side was a two-step lesson. The first index traded “stream the file, zero resident memory” for one read connection per RULE-SET — ~316 KB each once you count the runtime’s lookaside allocations and a default-sized private page cache. On iOS, with the double-match and a thrashing result cache, that added +3 MB at rest and +7 MB peaks under UDP load. Not acceptable.

The fix: read connections drop the lookaside cache, map the file instead of reading it with a fallback when the embedded library is compiled without mmap, and keep a much smaller page cache. ~105 KB per index instead of ~316 KB, p50 unchanged, p99 better.

A second optimization fell out of the review: the lookup used to re-parse each residual line per candidate. The index format now records the payload’s shape up front — which buckets exist, which prefix lengths the CIDR lines use, how many residual lines — so a lookup only probes what can answer. A v6 session no longer pays a walk through dozens of buckets per index; a pure-domain list pays zero.

The UDP Memo

The single biggest UDP win wasn’t in the index at all. The tunnel layer used to match every datagram twice and, if the flow was proxied, resolve the domain between the two passes. It now remembers the flow’s decision (rule + resolved IP) for sixty seconds as long as the rule table hasn’t been republished since. Repeat datagrams skip both matching passes and the DNS query. Every reload, clean, repoint, or payload publish drops the memo — so a rule change invalidates caches exactly when it should.

A Review That Earned Its Keep

Two days after the index shipped we reviewed our own work against the legacy scan and found three real defects, each pinned by a regression scenario that fails on the previous build:

1. Resolved-IP sessions stopped matching IP lists. The tunnel matches a domain session twice — once pre-DNS, then again with the resolved address — and the index only probed IP buckets for sessions already marked as raw IP flows. Every RULE-SET IP list (regional CIDR feeds, private-range lists) stopped matching domain requests on iOS/tvOS. The fix: IP and GEOIP buckets answer whenever the session carries an address at all; the no-resolve hint stays with the candidate’s own check.
2. Cache restore treated the index file as a payload. The index sits next to the file it describes, and the restore scan was comparing its name against the payload’s as if both were candidate lists. The comparison was loose enough that on a modern file system the wrong file could win roughly half the time — the loser served the binary index as if it were the text list, and every lookup missed silently until the next update. The suffix is now a first-class marker; every folder walk that knows about it skips it.
3. Residual-line fetch was the p50 bottleneck. Each candidate’s text came back from a by-line-number query that the embedded library answered with a full scan of the entries table, because there was no index on line number: roughly a millisecond per candidate. The candidate query now returns the line itself; the two by-line-number statements are gone. That alone is where the 0.60 → 0.06 ms came from.

All three are in the committed review doc, with links to the failing-then-passing tests. The rule suite is fully green, and the parity scenario now passes every run instead of failing once in six runs by luck.

What This Means for You

If you subscribe to large rule-sets on iOS:

• Memory pressure drops. Big subscriptions no longer pin megabytes of resident pages per list.
• Latency drops on cold connections. The first lookup against a 50k list used to be the slowest part of a new session; now it’s noise.
• UDP-heavy apps — calls, games, anything with real datagram fan-out — stop paying the double-match and the DNS repeat.
• Nothing changes semantically. First-match-wins, same rule, same order. If you ever suspect the index, look for the log line it emits when it falls back: “index build failed, using scan.” That line is the whole design philosophy — speed is a best-effort layer, correctness is the floor.

These changes are rolling out now on Chute iOS, macOS, and tvOS. No configuration change is required; rule-sets index themselves on the next download or restore. Details are in the Chute Manual.

Thanks.

Chute Devs