3Network Cards and Kernel Bypass

Between the wire and a UDP socket’s recv a datagram is copied by the card into the host’s memory, announced by an interrupt, picked up by the kernel’s networking code in a software interrupt, matched to a socket, queued, and copied again into the buffer the program handed to recv; the program, meanwhile, was asleep and must be woken. On the laptop this book is written on, the median datagram spends under a microsecond getting into the kernel over loopback and about fifteen more microseconds getting out of it to a sleeping reader. None of that work decides anything a trading program cares about.

This chapter follows a packet through the network card and the kernel, then removes the kernel from the path. One Quant Book 13 (chapter 13) tuned the host so that busy polling and kernel bypass can do their job; this chapter looks at the same machinery from the card’s side: descriptor rings, interrupts and their coalescing, the steering of flows to queues, the stacks that run in user space, and the timestamps the card itself can take.

3.1 The path of a packet through the kernel

A network card and its driver share memory. The card writes arriving packets into buffers that the driver has given it, and says which ones it has filled; the driver takes them, hands the buffers back, and passes the packets up.

On Linux the kernel side of this is NAPI, the networking stack’s event mechanism: the card raises an interrupt, the kernel schedules the ring’s processing in a software interrupt, and the processing runs until the ring is empty or a budget is spent, with further interrupts from that ring disabled meanwhile. Under load the kernel is thus already polling; what it does not do by default is spare the program the socket queue, the copy and the wake-up.

3.2 Interrupts, coalescing and receive-side scaling

An interrupt costs the host a switch into the kernel, the handler, and, for a sleeping reader, the scheduler’s wake-up: microseconds, paid per interrupt. Cards therefore wait before interrupting.

A trading host uses both against RSS’s intent. RSS spreads load evenly, which is what a web server wants; a feed handler wants every packet of line A on the one ring its pinned core polls, and nothing else there. Flow steering puts the venue’s groups on the rings of the cores that handle them and the rest of the machine’s traffic elsewhere, and the core that polls a ring should sit on the socket the card is attached to (One Quant Book 13, chapter 4).

3.3 Polling drivers and user-space stacks

    bool nic_rx(std::uint64_t seq, std::uint32_t length) {
        const std::uint32_t i = head_;
        if (owner_[i] == 1) { ++drops; return false; }   // still the host's: the ring is full
        seq_[i] = seq, len_[i] = length, owner_[i] = 1;
        head_ = (i + 1) & (size_ - 1);
        ++rx;
        return true;
    }

    std::uint32_t poll(std::uint32_t budget) {
        std::uint32_t n = 0;
        while (n < budget && rx > processed) {
            const std::uint32_t i = tail_;
            mix(seq_[i]), mix(len_[i]);
            tail_ = (i + 1) & (size_ - 1);
            ++processed, ++pending_, ++n;
            if (pending_ >= refill_) give_back();
        }
        return n;
    }

3.4 Zero copy and the transmit side

A copy of a 100-byte datagram is a few nanoseconds of memory traffic; what zero copy saves on the receive side is less the copy than the machinery around it (the socket buffer, its accounting, the cache lines of a second location). On the transmit side the same ring structure runs in reverse: the program writes an order into a transmit buffer, fills a descriptor and writes the card’s doorbell register, and the card fetches the frame by direct memory access. Each of those steps is a crossing of the processor’s interconnect to the card (One Quant Book 13, chapter 4). Some cards let the program push the frame’s bytes into the card’s own memory with processor writes instead: AMD’s ef_vi documents such a programmed-I/O region, which “avoids the latency associated with a DMA read”, can be filled before the critical path and updated on it, and, in a cut-through mode, starts transmitting while the frame is still crossing the bus. The cheapest transmit is the one prepared before it is needed: the order’s frame built in advance, with only price, size and identifier to fill, the same idea chapter 7 takes into hardware.

3.5 Timestamps on the card

The kernel can timestamp a packet when it enters the kernel (SO_TIMESTAMPING, software receive timestamps), and a card with its own clock can timestamp it when it reaches the card’s port, a hardware timestamp in the sense of One Quant Book 13, chapter 5. The difference is the time the packet spent in the card and its ring, which is exactly what a firm tuning its receive path wants to see and what software timestamps cannot show. The card’s clock is only as good as its synchronisation to the firm’s time reference, the subject of chapter 4, and the timestamps of the whole cage are compared in chapter 5.

3.6 Tutorial: the kernel’s receive path, measured and modelled

    while (static_cast<int>(out.size()) < n) {
        int got = 0;
        if (mode == 2) {
            for (int k = 0; k < kBatch; ++k) mm[k].msg_hdr.msg_controllen = sizeof ctrl[k];
            got = recvmmsg(rx, mm, kBatch, 0, nullptr);
        } else {
            mm[0].msg_hdr.msg_controllen = sizeof ctrl[0];
            const ssize_t r = recvmsg(rx, &mm[0].msg_hdr, mode == 1 ? MSG_DONTWAIT : 0);
            got = r > 0 ? 1 : 0;
        }
        const std::int64_t app = now_ns();
        for (int k = 0; k < got; ++k) {
            std::int64_t sent = 0;
            std::memcpy(&sent, data[k], sizeof sent);
            out.push_back({sent, kernel_stamp(mm[k].msg_hdr), app});
        }
    }

The measurement shows the two halves of this chapter’s argument (Table 3.1). Getting a datagram into the kernel costs under a microsecond; getting it out to a sleeping program costs fifteen at the median and hundreds of microseconds at the 99th percentile, because the program must be woken and scheduled. A program that never sleeps removes that: busy polling brings the median down to $1.5\,\text{µ}\mathrm{s}$. And a program that never sleeps must never be interrupted: on a laptop whose cores are shared with everything else the poller is sometimes descheduled, and the datagrams that arrive meanwhile wait for milliseconds. Batching amortises the system call but not the wake-up, and waits for its batch. Loopback involves no card at all, so these figures are the kernel’s share alone; a real card adds its ring, its interrupt and its coalescing.

def coalesce(lam, u, m, c_irq=C_IRQ, w=WAKE, c_pkt=C_PKT, n=100_000, seed=1):
    rng = np.random.default_rng(seed)
    t = np.cumsum(rng.exponential(1.0 / lam, n))
    lat = np.empty(n)
    i, busy_until, irqs, cpu = 0, 0.0, 0, 0.0
    while i < n:
        first = t[i]
        deadline = first + u
        j = i
        while j < n and j - i < m and t[j] <= deadline:
            j += 1
        fire = t[j - 1] if j - i == m else deadline          # m-th packet or the timer
        start = max(fire + w, busy_until) + c_irq
        done = start + c_pkt * np.arange(1, j - i + 1)
        lat[i:j] = done - t[i:j]
        busy_until = done[-1]
        irqs += 1
        cpu += c_irq + c_pkt * (j - i)
        i = j
    span = t[-1] - t[0]
    return {"mean_us": float(lat.mean()), "p99_us": float(np.quantile(lat, 0.99)), "cpu": float(cpu / span),
            "irq_rate": float(irqs / span)}

The model (Listing 3.3) takes $2\,\text{µ}\mathrm{s}$ of CPU per interrupt, $3\,\text{µ}\mathrm{s}$ of wake-up and $0.3\,\text{µ}\mathrm{s}$ per packet: model values of the order of the laptop’s wake-up, not a particular card’s. At 100 000 packets a second an interrupt per packet gives $5.6\,\text{µ}\mathrm{s}$ of mean latency for 23% of a core; an $8\,\text{µ}\mathrm{s}$ timer gives $11.7\,\text{µ}\mathrm{s}$ for 14%; polling gives $0.4\,\text{µ}\mathrm{s}$ for the whole core. At 500 000 an interrupt per packet is beyond one core (the saturation rate of Proposition 3.4 is 435 000 a second), and coalescing is what keeps the host alive. A trading host resolves the trade-off by not choosing it: the hot path polls on cores bought for the purpose, and everything else coalesces.

3.7 Build: the descriptor ring

3.8 Exercises

3.9 Problem: Interrupts or Polling

3.10 Interview questions