mightsleep

Four lanes, one CAS

· 16 min read

The first post mentioned a router I wrote over a weekend: it sits on port 443, reads the server name from the TLS handshake and passes the connection on without decrypting anything. A week later it has grown IPv6, a plaintext port, the PROXY protocol, metrics, and three kinds of connection limits, two of which are small sketches packed four lanes to a 64-bit word. This post goes through all of it, including the parts that broke.

Why a router at all

The server has one public address. Two things want its port 443: this site, and a tunnel that exists because some networks I sit in let out TCP on 80 and 443 and nothing else. Whoever connects to 443 says, in the first message of the TLS handshake, which name it wants (Server Name Indication, SNI). That is enough to tell the two apart before any cryptography happens. Unknown names get the website, so somebody poking at the tunnel's address sees an ordinary web server.

The first post already told how this almost went wrong: the web server behind the router picks a virtual host by the HTTP Host header, not by SNI, so "public site" in the handshake and "internal dashboard" in the request would have served the dashboard to the internet. The public site now runs on its own instance that knows nothing else.

Where is layer 4, anyway

Load balancer vendors sort themselves into "L4" and "L7", and this router would be filed under L4. I have never found the layers much use, and not only because the network ignores them.

Start with the hardware. A network card does the physical layer and the MAC, computes IP and TCP checksums, cuts TCP segments for the kernel (TSO), hashes the addresses and ports to spread packets over its queues (RSS), and newer ones encrypt TLS records. One chip, five layers.

Then debugging, where problems refuse to stay on one floor. A DPI-evasion tool on my laptop once split the ClientHello across TCP segments, which is layer 4, and the TLS library on the other end refused the handshake, which is layer 7. A firewall that drops ICMP, layer 3, makes a TCP connection hang the first time it sends a large packet. Further down this post a web server's HTTP redirect depends on a port number from a header in front of the TCP stream. You switch between layers all the time, so they do not even work as a filing system for bugs.

And the stack is not seven floors. The tunnel behind this router carries IP inside WireGuard inside WebSocket inside TLS inside TCP inside IP: layer 3 inside layer 7. A fixed list of seven floors cannot say that. What the wire carries is envelopes inside envelopes: a frame is a header followed either by data or by another frame, as deep as anyone likes. A "layer" is just how many envelopes deep you are.

What the layers are good for is a contract about encapsulation: who owns which header and who may change it. That contract is why IPv6 could slide in under an unchanged TCP and why QUIC could be built on UDP. It is a model for designing protocols, not for where the work happens or where the failures hide. Even as a contract it gets broken: middleboxes read into TCP, so new transport protocols like SCTP never made it through the internet, and QUIC encrypts its own headers so that nobody can touch them.

The model I actually use is where on the wire is the packet, and what happens to it there. A packet travels a chain of places, and each place is a queue, a transformation and a decision:

application buffer → socket send queue → qdisc → driver ring
  → NIC (TSO, checksums) → wire → switches → … → NIC (RSS)
  → driver ring → NAPI/GRO → TCP receive queue → application

The tools are built for this view: ss for socket queues, tc -s for qdiscs, ethtool -S for the card's rings and drops, perf trace -e skb:kfree_skb for where the kernel threw a packet away and why. "Where are we losing time" is a question about a queue, not about a layer.

It needs one more axis: which bytes a place reads. A layer is then a property of a decision, not of a box. RSS reads TCP ports from the bottom of the stack. This router sits at the end of a TCP connection and decides on bytes of TLS. It gets called "L4" for where it sits: it terminates TCP, holds two sockets per connection, and never terminates TLS. Packet-level balancers such as Maglev or Katran are "L4" too, and never terminate even TCP: they only rewrite packets.

Put together: a packet's trip is a chain of steps, and each step looks at some bytes at the front (headers) or at the end (the Ethernet checksum) and acts on them. The layered picture is the special case where every step opens exactly one envelope. Almost nothing behaves that way.

Reading one message

The ClientHello is the only thing the router ever parses, and the only code here that reads bytes chosen by strangers. TLS wraps it in records: five bytes of header (type 22, version, length), then the payload. A hello can be split across several records, and DPI-evasion tools split it on purpose, sometimes in the middle of the name, to confuse middleboxes exactly like this one.

So the parser does not wait for "enough bytes". It is a function of the prefix read so far, answering one of four things: the name, no name, not TLS at all, or need more. After every read the router calls it again on the whole prefix:

loop {
    if let Some(&kind) = hs.first() && kind != CLIENT_HELLO {
        return Hello::Invalid;
    }
    if let Some(len) = hs.get(1..4).map(u24) {
        if 4 + len > MAX_HELLO {
            return Hello::Invalid;
        }
        if let Some(body) = hs.get(4..4 + len) {
            return client_hello(body).unwrap_or(Hello::Invalid);
        }
    }
    // Header first: a non-TLS client must hear "no" now, not after it
    // sends as many bytes as its first five happen to spell.
    let Some(h) = records.take(5) else { return Hello::NeedMore };
    let len = u16::from_be_bytes([h[3], h[4]]) as usize;
    // 1 <= len <= MAX_RECORD in one unsigned compare.
    if u16::from_be_bytes([h[0], h[1]]) != RECORD_MAGIC
        || len.wrapping_sub(1) >= MAX_RECORD
    {
        return Hello::Invalid;
    }
    let Some(payload) = records.take(len) else { return Hello::NeedMore };
    hs.extend_from_slice(payload);
}

Re-parsing from the start after each read is quadratic, but only in the number of reads, and a cap on the hello (32 KiB) plus a timeout keep that small. The comment about the header is about plain HTTP: if the parser waited for a whole record before checking the header, a client that sends GET / would have its first five bytes read as a record length, and the router would politely wait for kilobytes that never come.

The first post has this parser compiled to WebAssembly, where you can split a hello into records and send it byte by byte.

The decision costs nothing compared to what follows. Every byte read so far goes to the backend first, so it sees the stream exactly as the client sent it.

Splicing without buffers

After the decision the router copies bytes both ways until both sides close. Tokio's copy_bidirectional does this with two 8 KiB buffers per connection, held for the whole life of the connection, and most connections spend most of their life idle. Add the hello buffer, which the first version kept until the end too, and an idle connection held about 21 KiB of user-space memory. Four thousand of them, about 84 MiB, for nothing.

The replacement waits for readability holding nothing. When the socket is readable it reads into a 16 KiB scratch buffer that belongs to the worker thread, and writes straight on. There is no .await between the read and the write, so the scratch is free again before the task yields and another connection on the same thread can use it:

from.readable().await?;
let rest = SCRATCH.with_borrow_mut(|buf| {
    let n = match from.try_read(buf) { /* 0 = EOF, WouldBlock = spurious */ };
    let m = match to.try_write(&buf[..n]) { /* WouldBlock = 0 */ };
    // Empty when everything went out: no allocation.
    Ok(Some(buf[m..n].to_vec()))
})?;

Only what the other side does not take right away is copied into a buffer of its own, and that buffer is dropped, not just emptied, once it drains. An idle connection now holds its task, around a kilobyte. That number is computed from the sizes, not measured on the server.

One detail I did measure. The first version tracked a partly written remainder with an offset, and a mutation (sent = m instead of sent += m) survived every test. To catch it I shrank the socket send buffer to 4 KiB and counted: 29 MiB through the relay, over 1800 remainders, and every one went out in a single write. On loopback the kernel lets a write overshoot the send buffer by a segment, so two short writes in a row never happen. Instead of a test that cannot fail, the offset went away: left.drain(..m) has nothing to get wrong, and the memmove of at most 16 KiB on a rare short write costs nothing.

Four lanes, one CAS

The first limit is on concurrent connections per client, where a client is an IPv4 address or an IPv6 /64 (what one subscriber usually gets). Without it, one machine opens four thousand connections, never sends a hello, and the router is full.

The obvious version is a mutex around a HashMap from client to count, and that is what I wrote first. It works, but every connection takes a lock, and the map grows with whatever addresses the internet throws at it. The current version is a count-min sketch in a fixed table: each AtomicU64 holds four 16-bit counters (lanes), and a client counts against two lanes of one word, picked by a keyed hash. Six ways to choose two lanes of four, so the pair comes from the hash too.

Admitting a connection means checking that not both of the client's lanes are at the cap, and adding one to both. All four lanes compare against the cap at once:

const ONES: u64 = 0x0001_0001_0001_0001;
const HIGH: u64 = ONES << 15;

/// Lanes of `word` that are at least `limit`, as their top bit.
const fn lanes_at_least(word: u64, limit: u64) -> u64 {
    ((word | HIGH) - limit * ONES) & HIGH
}

Every lane stays below 2^15. Setting its top bit and subtracting the limit therefore cannot borrow from the next lane, and the top bit survives exactly when the lane was at least the limit. A lane holding 5 with limit 8: 0x8005 - 8 = 0x7ffd, top bit gone, below. A lane holding 9: 0x8009 - 8 = 0x8001, still set. The whole admission is one compare-and-swap:

let mine = lanes << 15; // the client's two top bits
loop {
    if lanes_at_least(cur, per_client) & mine == mine {
        return Err(Refusal::MaxConnsPerClient);
    }
    match cell.compare_exchange_weak(cur, cur + lanes, AcqRel, Relaxed) {
        Ok(_) => break,
        Err(now) => cur = now,
    }
}

Releasing is fetch_sub(lanes). No lock, no allocation, 128 KiB of table for four thousand connections.

Why two lanes of one word and not a real count-min with lanes in two different words, which would collide less? Because two fetch_adds are not one atomic step. Let a client sit one below its cap, and two of its connections arrive at once. In word 1 the first increments before the second, in word 2 the other way round. Each sees one of its counters at cap - 1, the minimum is below the cap for both, and both get in. One word and one CAS keep the bound exact.

A lane is never below the number of live connections of any client on it, so nobody gets more than the cap. The reverse can fail: an honest client is refused when both of its lanes are full of other people. That mostly takes a twin, a client in the same word with the same pair, about clients / (6 * words) of them. A test with 600 clients all pushing toward a cap of 8 refuses 0.42 % of honest attempts. With the real cap of 64 an honest twin does not get there, so in practice being refused means sharing a cell with whoever is abusing it, and the keyed hash keeps anyone from choosing their cell.

The trick that fails, and then works

Count-min has a well-known improvement, conservative update: add one only to the lanes that hold the client's minimum. It cuts overestimates a lot, which here means fewer refused twins. It is also wrong here, even though each connection remembers which lanes it raised. Two clients, A on lanes (L1, L3), B on (L1, L2):

  1. A opens 5 connections: L1 = L3 = 5.
  2. B opens 3. L1 is above B's minimum, so only L2 grows: L2 = 3.
  3. A closes all 5: L1 = 0.

B now has three live connections and a minimum of zero. The bound is gone, and B can open its full cap on top of them.

Plain count-min survives this because every connection does the same thing to the table: opening adds one to both lanes, closing takes one from both, so a closing undoes its opening exactly, whatever happened in between. In algebra this is called a homomorphism of groups. Conservative update makes what an opening does depend on the lanes at that moment, and the closing, later, has no way to undo just that.

Below is one word of the table with the router's own comparison, three clients and a cap of 3. Open and close connections by hand and watch the top bits decide, or press replay for the same story as above with smaller numbers. With conservative update off, B stops at the cap. Switch it on and replay, and B ends up with five.

One word of the per-client table, checked by the router's own lanes_at_least.

The second limit is on the rate of new connections per client, which the first does not cover: a client that opens and closes connections in a loop never holds many at once. The classic algorithm is GCRA. It keeps one number per client, the theoretical arrival time (TAT): a connection at time now is let in when max(TAT, now) - now <= tau, and then TAT = max(TAT, now) + T, with T the interval at the sustained rate and tau = (burst - 1) * T. Nothing but max and +: arithmetic in the max-plus semiring.

The TATs go into the same shape of table: 16-bit lanes, two per client, one CAS. A lane holds the largest TAT of everybody on it, so it never says a client's TAT is earlier than it is, and a collision can only make the limit stricter. And here conservative update works: the new TAT estimate comes from the smaller lane, and each lane is raised only to that, lane = max(lane, tat + T).

Here nothing is ever undone. A TAT is not taken back when a connection closes, it just falls behind as time passes, and raising a lane with max twice is the same as raising it once. So a lane never drops below anyone's true TAT. Counting needs undoing and breaks; taking a maximum never does and holds. Algebra has names for the two, a group and a semilattice.

Lanes count ticks since an epoch, and 15 bits run out. Once the epoch is a window old, the next admission moves it to now and subtracts the difference from the whole table, four lanes per word at once, saturating at zero:

/// `max(lane - d, 0)` in every lane, for lanes and `d` below 2^15.
const fn saturating_sub(word: u64, d: u64) -> u64 {
    // Surviving lanes as 0xffff each: the comparison's top bits,
    // moved to the bottom of the lane and multiplied out.
    let keep = (lanes_at_least(word, d) >> 15) * 0xffff;
    ((word | HIGH) - d * ONES) & !HIGH & keep
}

The rebase moves the epoch first and the words after it. Admissions read the epoch before and after their word and start over if it moved, in the style of a seqlock. One that read a word before the shift and writes it after fails its CAS, unless the word was all zeros, in which case its write is late by the shift, which again only makes the limit stricter. The defaults are 10 new connections per second with bursts of 40, enough for a reload spree, far below a scanner.

Evicting the silent

A slowloris connects and says nothing until the hello timeout. The per-client caps limit how many slots one address can take, but a botnet has many addresses, and once the router is full the classic response, turn newcomers away, works for the attacker. An honest client sends its hello one round trip after connecting. So when the router is full, the connection that has been silent the longest goes, and the newcomer gets its slot.

That needs the oldest of the connections still waiting for a hello, and it needs it under a flood. Waiting connections go into a ring of 64 time slots, each a slice of the hello timeout over 32 (156 ms at the default 5 s), so everyone waiting fits in half the ring. A u64 says which slots are occupied. The oldest slot is the first set bit counting from the slot after the current one, which is the one 64 slices ago:

let from = (self.slot_at(now) + 1) % SLOTS;
let s = (from + ring.bits.rotate_right(from as u32).trailing_zeros() as usize) % SLOTS;

Rotate so the oldest possible slot is bit 0, count trailing zeros, done. The same structure sits in the allocator as its size-class bitmap; there it finds the smallest class with a free block, here the oldest slice with a silent connection. Since nobody waits longer than the timeout, one word is enough and the second level of the allocator's bitmap is not needed.

The oldest connection must also have been silent for at least a second before it is evicted. Under a flood of fresh connections that never waited, everyone is young, and evicting would only make honest clients evict each other; the newcomer is turned away as before.

PROXY, and a web server that believes it

The web server behind the router used to see every visitor as 127.0.0.1. The PROXY protocol fixes that: before the first byte of the connection the router sends a small binary header with the client's address and the address it connected to. Sixteen bytes of signature and lengths, then the addresses. The header and the hello go out in one write, so in one segment.

Then the plaintext port, so that http:// redirects to https://. The web server's PROXY support is global, so it now expects the header on port 80 too, and the router forwards port 80 without parsing anything, header first. In the local test the redirect returned 404 whatever I did. The reason: with PROXY on, the web server takes the server port from the header, which is the public port 80, while it listened on 8080, so its "this is my HTTP port, redirect" rule never fired. The fix was to give it the same ports on loopback that the world sees, 80 and 443. It is now consistent with the outside, and the redirect comes with a clean https://panacan.xyz/... instead of an internal port.

The access log now has real addresses. A pipeline adds country, city and network operator from the free DB-IP databases, and a dashboard shows where the visitors come from, which pages, which referrers, and which bots. City is approximate at best: my phone, lying next to the laptop, shows up in a village 350 km east, because mobile operators hand out addresses from large pools.

Testing against exact models

Most of the tests compare the router with something slower that is obviously right:

Then mutations: break one line, check that a test fails. Rebase without moving the epoch, raise only one lane, min turned into max, no rotation in the ring, no minimum age for eviction, eviction off: each fails a test, the first by hanging it. One survives by design: the epoch check against concurrent admissions. It is reasoned through in a comment, and the tests are single-threaded.

What broke this time

A timeout around nothing. The first version of the plaintext mode read let read = read_hello(&mut client).await; and then wrapped read in a timeout. The timeout guarded a value that was already there. Found on reading it back, before any test, which is the kind of luck that does not repeat.

Resets that were refusals. The new end-to-end tests failed with "connection reset by peer". A connection refused right after accept is closed with the client's bytes unread, and the kernel answers that with RST, not FIN. The tests now count a reset as the router hanging up, which is what it is.

Quotes. The dashboard's log queries worked against the log database and failed in Grafana: its plugin mangles quotes in queries on the way through. The fix was to compute the field in the log pipeline, so the queries need no regular expression at all.

The dashboard that took Grafana down. I gave the data sources fixed identifiers so the dashboard could refer to them. Grafana looks up existing sources by that identifier, did not find the old ones, and refused to start. The provisioning now deletes them by name and creates them again on every start.

The neighbourhood

Rust has a few relatives of this router. rpxy-l4 is the closest: TCP and UDP, routing by SNI and ALPN including QUIC, and PROXY in both directions, still marked as work in progress. Rama is a framework for programmable proxies and lists SNI proxies explicitly. ByteDance's g3proxy has an SNI proxy mode inside an enterprise forward proxy. What none of them does in this form is the sketches, as far as I could see: fixed memory under attack, one CAS per decision, and a bound that holds by algebra rather than by a lock.

Next

QUIC carries the same server name in its first packet, encrypted with keys anyone can derive from a public salt. Routing UDP on port 443 means decrypting that, reading the hello, and then following connection IDs instead of sockets. Others already do this well: rpxy-l4 routes QUIC by SNI today, and the big proxies have known QUIC inside out for years. So naturally I will try to implement it my own way, break it a few times on the way, and maybe learn something.

Further out is Encrypted Client Hello in split mode: the router would hold the key, decrypt the inner hello and route on the real name, while anything watching the wire sees only panacan.xyz. For a router whose reason to exist is a network that allows nothing but 443, that is the logical end.