Queueing Disciplines qdisc

A queueing discipline (qdisc) is the Linux kernel’s per-interface packet scheduler: the object, represented by struct Qdisc, that decides which queued packet leaves next and when. Every network device has a root qdisc, and the transmit path hands every outgoing struct sk_buff to it via two operations — enqueue (accept a packet into the queue, or drop it) and dequeue (produce the next packet to transmit) (struct Qdisc in include/net/sch_generic.h, v6.12). A qdisc can be as simple as a first-in-first-out buffer or as sophisticated as a per-flow fair scheduler with active queue management; the kernel’s running default on a modern systemd host is fq_codel (Fair Queuing with Controlled Delay), chosen specifically to fight bufferbloat. This note is the mechanism behind Traffic Control Overview: the data structure, the two ops, the call from the transmit path, the lockless fast path, and the three qdiscs you meet by default — pfifo_fast, fq_codel, and mq.

All code is pinned to Linux 6.12 LTS (2024-11-17) and spot-checked against 6.18 LTS (2025-11-30); struct Qdisc, the ops, and the default-qdisc pointer are byte-for-byte identical between the two. For where qdiscs sit in the larger picture and the qdisc/class/filter model, read Traffic Control Overview first; the class hierarchy is in Classful and Classless Qdiscs.

Mental Model — A Pluggable enqueue/dequeue Pair

Think of a qdisc as a black box with two doors and a policy inside. The transmit path pushes a packet through the in door (enqueue); later, when the link is ready, the path pulls a packet out the out door (dequeue). What happens between the doors — which packet comes out, in what order, after what delay, and whether some packets are silently dropped — is the policy, and swapping the policy means swapping the qdisc. This is classic object-oriented dispatch in C: struct Qdisc holds function pointers (->enqueue, ->dequeue) that point into a specific qdisc’s implementation (pfifo_fast_enqueue, fq_codel_enqueue, …), so the generic transmit code calls q->enqueue(skb, q, ...) without knowing or caring which scheduler it is.

flowchart LR
  XMIT["__dev_queue_xmit()<br/>net/core/dev.c"] --> EQ["q->enqueue(skb, q)<br/><i>accept or drop</i>"]
  EQ --> POL{"qdisc policy<br/>(FIFO / prio /<br/>fair queue / AQM)"}
  POL --> RUN["__qdisc_run(q)<br/>loop: dequeue + xmit"]
  RUN --> DQ["q->dequeue(q)<br/><i>next packet, or NULL</i>"]
  DQ --> SDX["sch_direct_xmit()<br/>to driver ring"]
  DQ -->|"empty"| STOP["stop: queue drained"]

The qdisc as a two-door black box. What it shows: the transmit path calls enqueue to insert a packet, then drives __qdisc_run, which repeatedly calls dequeue and transmits each returned skb until the queue is empty or a budget is exhausted; the policy lives entirely inside the enqueue/dequeue implementations. The insight to take: the generic code is policy-agnostic — every qdisc, from a dumb FIFO to fq_codel, plugs into the exact same two-function interface, which is why you can hot-swap an interface’s scheduler at runtime with tc qdisc replace.

struct Qdisc and the Ops Vtable

The core structure begins, tellingly, with its two operations (v6.12 sch_generic.h):

struct Qdisc {
    int  (*enqueue)(struct sk_buff *skb, struct Qdisc *sch,
                    struct sk_buff **to_free);
    struct sk_buff * (*dequeue)(struct Qdisc *sch);
    unsigned int     flags;
#define TCQ_F_BUILTIN     1
#define TCQ_F_INGRESS     2
#define TCQ_F_CAN_BYPASS  4
#define TCQ_F_MQROOT      8
#define TCQ_F_ONETXQUEUE  0x10
#define TCQ_F_CPUSTATS    0x20
#define TCQ_F_NOLOCK      0x100   /* qdisc does not require locking */
#define TCQ_F_OFFLOADED   0x200   /* qdisc is offloaded to HW */
    u32                    limit;          /* max queue length */
    const struct Qdisc_ops *ops;           /* the full vtable */
    u32                    handle;          /* this qdisc's major:0 id */
    u32                    parent;          /* parent class id */
    struct netdev_queue    *dev_queue;      /* the TX queue we serve */
    /* ... per-CPU stats, refcount ... */
    struct sk_buff_head    gso_skb ____cacheline_aligned_in_smp; /* requeued GSO */
    struct qdisc_skb_head  q;               /* the actual packet list */
    spinlock_t             busylock ____cacheline_aligned_in_smp;
    spinlock_t             seqlock;         /* for lockless qdiscs */
    long                   privdata[];      /* per-qdisc private state */
};

The fields that matter for understanding behaviour: enqueue/dequeue are the hot-path function pointers; ops points to the full struct Qdisc_ops vtable (which also has init, reset, destroy, change, dump, peek, and the class-ops sub-vtable for classful qdiscs); flags carries the per-qdisc capability bits (the TCQ_F_* macros — most importantly TCQ_F_NOLOCK and TCQ_F_CAN_BYPASS, discussed below); limit is the maximum queue length; handle and parent are the major:minor identifiers from Traffic Control Overview; dev_queue points back at the hardware transmit queue this qdisc feeds; and privdata[] is a flexible array the qdisc casts to its own private struct (e.g., fq_codel’s flow table lives here). The ____cacheline_aligned_in_smp annotations on gso_skb, q, and busylock are deliberate: these are the most-contended fields, so they are pushed onto their own cache lines to avoid false sharing between CPUs.

The Qdisc_ops vtable carries a static_flags field that seeds a new qdisc’s flags. For example pfifo_fast_ops sets .static_flags = TCQ_F_NOLOCK | TCQ_F_CPUSTATS (v6.12 sch_generic.c) — i.e., the default FIFO is lockless and keeps per-CPU statistics.

How the Transmit Path Calls the Qdisc

The qdisc is invoked from __dev_queue_xmit() → __dev_xmit_skb() in net/core/dev.c. After picking the transmit queue and reading its qdisc, the kernel takes one of three routes inside __dev_xmit_skb (v6.12 dev.c):

1. Lockless bypass (the fast path). If the qdisc is lockless (TCQ_F_NOLOCK), can bypass (TCQ_F_CAN_BYPASS), is currently empty (nolock_qdisc_is_empty), and we win the run lock (qdisc_run_begin), the kernel skips queueing entirely and calls sch_direct_xmit() to send the packet straight to the driver. There is no point enqueueing then immediately dequeueing a single packet when nobody else is using the queue.

2. Lockless enqueue. Otherwise, for a lockless qdisc, it calls dev_qdisc_enqueue() (which calls q->enqueue) and then qdisc_run(q) to drain.

3. Locked path. For a classic locking qdisc, it acquires qdisc_lock(q) (the root lock), optionally serializing first on busylock to reduce contention, then enqueues and runs. The comment in the source is explicit that busylock exists “to force contended enqueues to serialize on a separate lock before trying to get qdisc main lock,” so the CPU that currently owns the queue can dequeue faster.

Once a packet is enqueued, __qdisc_run(q) does the draining (v6.12 sch_generic.c):

void __qdisc_run(struct Qdisc *q)
{
    int quota = READ_ONCE(net_hotdata.dev_tx_weight);  /* budget */
    int packets;
 
    while (qdisc_restart(q, &packets)) {   /* dequeue + sch_direct_xmit */
        quota -= packets;
        if (quota <= 0) {                  /* budget exhausted */
            if (q->flags & TCQ_F_NOLOCK)
                set_bit(__QDISC_STATE_MISSED, &q->state);
            else
                __netif_schedule(q);       /* defer rest to NET_TX softirq */
            break;
        }
    }
}

Reading this: __qdisc_run loops, each iteration calling qdisc_restart() which dequeues one packet and transmits it via sch_direct_xmit(). It is governed by a budget (dev_tx_weight) so a single send() cannot monopolize the CPU draining a huge queue; when the budget runs out, the rest is deferred — to the NET_TX_SOFTIRQ via __netif_schedule() for locked qdiscs, or by setting the MISSED bit for lockless ones (see NET_RX and NET_TX Softirqs). This budgeting is the same “do bounded work then yield” pattern the receive side uses with NAPI (see NAPI and Polled Receive).

The Lockless Qdisc — TCQ_F_NOLOCK

On a busy multi-core server, a single spinlock guarding one qdisc serializes every CPU that wants to transmit on that queue — a brutal scaling bottleneck. The lockless qdisc (TCQ_F_NOLOCK), introduced for pfifo_fast, replaces the heavyweight root spinlock with a lighter seqlock that only one CPU holds while it runs the qdisc, plus a per-CPU statistics scheme so the hot counters do not bounce between cores.

The clever part is the qdisc_run_begin/qdisc_run_end dance with a MISSED bit, which prevents a packet from being stranded (v6.12 sch_generic.h):

static inline bool qdisc_run_begin(struct Qdisc *qdisc)
{
    if (qdisc->flags & TCQ_F_NOLOCK) {
        if (spin_trylock(&qdisc->seqlock))
            return true;                    /* got it: we run the qdisc */
        /* Someone else is running it. Set MISSED so the running CPU
         * knows it must re-check the queue before leaving. */
        if (test_and_set_bit(__QDISC_STATE_MISSED, &qdisc->state))
            return false;                   /* MISSED already set, give up */
        return spin_trylock(&qdisc->seqlock); /* one more try */
    }
    return !__test_and_set_bit(__QDISC_STATE2_RUNNING, &qdisc->state2);
}
 
static inline void qdisc_run_end(struct Qdisc *qdisc)
{
    if (qdisc->flags & TCQ_F_NOLOCK) {
        spin_unlock(&qdisc->seqlock);
        smp_mb();                           /* full barrier: unlock then test */
        if (unlikely(test_bit(__QDISC_STATE_MISSED, &qdisc->state)))
            __netif_schedule(qdisc);        /* re-run: someone enqueued */
    } else {
        __clear_bit(__QDISC_STATE2_RUNNING, &qdisc->state2);
    }
}

The scenario this solves: CPU A is running the qdisc (holds seqlock); CPU B enqueues a packet but spin_trylock fails, so B sets MISSED and gives up — without this, B’s packet could sit in the queue forever because A might have already passed the point where it checks for more work. When A finishes, qdisc_run_end sees MISSED set (after a full smp_mb() barrier ordering the unlock before the test) and reschedules the qdisc, guaranteeing B’s packet gets sent. The barrier matters because spin_unlock only has store-release semantics, and the unlock-then-test pattern is a store-load ordering that needs the explicit smp_mb() — a textbook example of why memory ordering is load-bearing in lockless code (cross-link Linux Kernel Synchronization MOC).

pfifo_fast — The Three-Band Legacy Default

pfifo_fast is the kernel’s hard-coded compile-time default qdisc (default_qdisc_ops = &pfifo_fast_ops, identical in v6.12 and v6.18). It is classless but internally implements three priority bands — a “prio + fifo” combination. It keeps three separate skb ring buffers and, on enqueue, maps the packet’s skb->priority to a band through a fixed table (v6.12 sch_generic.c):

const u8 sch_default_prio2band[TC_PRIO_MAX + 1] = {
    1, 2, 2, 2, 1, 2, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1
};
 
static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc, ...)
{
    int band = sch_default_prio2band[skb->priority & TC_PRIO_MAX];
    struct skb_array *q = band2list(priv, band);
    err = skb_array_produce(q, skb);   /* lockless ring insert */
    ...
}

On dequeue, pfifo_fast_dequeue scans the three bands in strict priority order (band 0 first, then 1, then 2) and returns the first available packet:

for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) {
    struct skb_array *q = band2list(priv, band);
    if (__skb_array_empty(q)) continue;
    skb = __skb_array_consume(q);
}

So band 0 (the highest priority — used for interactive/control traffic via the priomap) is always drained before band 1, which is drained before band 2. The bands are skb_array (lockless ring) structures, which is what lets pfifo_fast carry TCQ_F_NOLOCK | TCQ_F_CPUSTATS and TCQ_F_CAN_BYPASS. The crucial limitation: pfifo_fast is prioritization without fairness or AQM — within a band it is pure FIFO, so a bulk flow in band 1 will happily build a giant standing queue and bloat latency for everything else in band 1. That weakness is exactly why the practical default moved to fq_codel.

fq_codel — Flow Queuing + CoDel AQM (the Running Default)

fq_codel (“Fair Queuing Controlled Delay”) is the qdisc systemd installs as the running default to fight bufferbloat (systemd 50-default.conf; the kernel-vs-systemd story is detailed in Traffic Control Overview). It combines two ideas: fair queuing across flows, and the CoDel active-queue-management algorithm within each flow (tc-fq_codel(8)).

Flow queuing. On enqueue, the packet is hashed to one of flows_cnt (default 1024) per-flow queues by fq_codel_hash → reciprocal_scale(skb_get_hash(skb), q->flows_cnt) (v6.12 sch_fq_codel.c). Each flow is an independent FIFO. Flows are scheduled by Deficit Round Robin (DRR): there are two lists, new_flows and old_flows. A flow that has just become active is appended to new_flows and given a deficit of one quantum of bytes; fq_codel_dequeue services new_flows before old_flows, which is precisely what gives sparse flows priority over bulk flows — a DNS query or TCP SYN, arriving into a fresh flow queue, jumps ahead of a long-running download (bufferbloat.net). When a flow’s deficit runs out it is moved to old_flows and recharged by a quantum next round:

flow = list_first_entry(head, struct fq_codel_flow, flowchain);
if (flow->deficit <= 0) {
    flow->deficit += q->quantum;                  /* recharge */
    list_move_tail(&flow->flowchain, &q->old_flows);
    goto begin;                                   /* try the next flow */
}
skb = codel_dequeue(sch, ..., &flow->cvars, ...); /* CoDel picks/marks */
flow->deficit -= qdisc_pkt_len(skb);              /* spend deficit */

The quantum is not a hardcoded constant — it is computed at init as q->quantum = psched_mtu(qdisc_dev(sch)), which is dev->mtu + dev->hard_header_len (v6.12 pkt_sched.h). On a standard Ethernet interface that is 1500 + 14 = 1514 bytes, which is exactly the default tc-fq_codel(8) reports.

CoDel AQM within a flow. CoDel does not measure the queue’s byte length; it measures sojourn time — how long each packet actually sat in the queue — and acts on time, not occupancy (bufferbloat.net). Two parameters govern it, set by codel_params_init (v6.12 codel_impl.h): target = 5 ms (the acceptable standing queue delay) and interval = 100 ms (roughly a worst-case RTT). The rule: if the minimum sojourn time stays above target for at least one interval, CoDel enters the dropping state and begins dropping (or ECN-marking) packets, spacing the drops by the control law t + interval / sqrt(count) — i.e., it drops more aggressively the longer the overload persists (the count-th drop is scheduled at interval/sqrt(count) after the previous one). The reciprocal-square-root is maintained incrementally (rec_inv_sqrt) to avoid a real sqrt in the fast path. Because it keys on minimum delay over a window, CoDel ignores brief bursts (which are good — they keep the link busy) and only punishes a persistent standing queue (which is bufferbloat).

fq_codel enables ECN by default: fq_codel_init sets q->cparams.ecn = true, overriding the codel_params_init default of false (v6.12 sch_fq_codel.c), so ECN-capable flows get marked rather than dropped. The ce_threshold feature (mark when delay exceeds a hard threshold) is disabled by default (CODEL_DISABLED_THRESHOLD).

The defaults, verified from source (fq_codel_init, v6.12): limit = 10*1024 = 10240 packets (total across all flows), flows_cnt = 1024, memory_limit = 32 MB (32 << 20), drop_batch_size = 64, quantum = psched_mtu (≈1514 on Ethernet), target = 5 ms, interval = 100 ms.

Overload handling. When the qdisc is full (over limit packets or over memory_limit bytes), fq_codel_enqueue calls fq_codel_drop, which does not drop the just-arrived packet — it finds the fattest flow (largest backlog) by a linear scan of backlogs[] and drops half that flow’s backlog, up to drop_batch_size (64) packets at once. The source comment explains the batching: dropping 64 at a time amortizes the expensive linear search to “one cache line per drop.” This is a deliberate fairness choice — punish the flow that is causing the congestion, not the innocent packet that happened to arrive when the queue filled.

mq — One Qdisc Per Hardware TX Queue

Modern NICs are multiqueue: they expose several independent hardware transmit rings so different CPUs can transmit in parallel without contending on one queue. Putting a single root qdisc in front of all of them would re-serialize exactly what the hardware parallelized. The mq qdisc solves this: it is a thin classful root that owns one child qdisc per hardware TX queue, and it is installed automatically by attach_default_qdiscs() whenever netif_is_multiqueue(dev) is true (v6.12 sch_generic.c).

In mq_init, the qdisc allocates dev->num_tx_queues child qdiscs, one per netdev_get_tx_queue(dev, ntx), each created from the system default qdisc ops and handed a class id of TC_H_MAKE(TC_H_MAJ(sch->handle), TC_H_MIN(ntx + 1)) — i.e., child N gets minor N+1 under mq’s major (v6.12 sch_mq.c). Then mq_attach grafts each child onto its hardware queue. The effect: on an 8-queue NIC you actually have one mq root plus eight fq_codel children, visible as 1:1 … 1:8, each scheduling its own queue lock-free in parallel. mq itself does no queueing — it has no enqueue; packets reach the children directly because each child’s dev_queue points at a specific hardware ring and netdev_core_pick_tx already chose the ring before the qdisc layer. This is why tc qdisc show on a server typically lists mq as root with N fq_codel leaves, and why replacing the root with a single classful qdisc collapses that parallelism (the gotcha noted in Traffic Control Overview). Related siblings mqprio and taprio extend this for hardware-offloaded priority/time-aware scheduling.

The Ingress Qdisc — Not a Real Queue

The ingress qdisc (and its superset clsact) is a qdisc only in the structural sense: it has a struct Qdisc and a handle (TC_H_INGRESS = 0xFFFFFFF1), but it carries TCQ_F_INGRESS | TCQ_F_CPUSTATS and implements no scheduling enqueue/dequeue — ingress_init requires sch->parent == TC_H_INGRESS and sets up a tc filter/BPF block (mini_qdisc), not a packet queue (v6.12 sch_ingress.c). It exists purely as the attach point for ingress filters, policers, and tc-BPF programs on the receive path; it can drop, mark, classify, or redirect inbound packets but cannot hold and reschedule them, for the reason given in Traffic Control Overview (you cannot un-receive a packet). The egress-side hook clsact adds is what sch_handle_egress() calls on the transmit path. The eBPF program-type machinery behind tc-BPF lives in Linux eBPF MOC.

Failure Modes and Common Misunderstandings

“pfifo_fast prioritizes, so it’s fine.” Within a band, pfifo_fast is a dumb FIFO with no AQM — a bulk flow bloats the queue and adds latency to everything sharing its band. Prioritization across three coarse bands is not fairness within a band; this is the gap fq_codel fills.

“fq_codel reorders my packets.” It does not reorder within a flow — each flow queue is a strict FIFO, and packets of one connection keep their order. It interleaves across flows, which is the point. Misattributing reordering to fq_codel usually means traffic that hashes to the same slot (hash collision) or genuine multipath.

“My fq_codel drops look high under load.” That is fq_codel doing its job — CoDel drops to signal congestion before the buffer bloats, and fq_codel_drop deliberately punishes the fattest flow. High drop counts on a saturated link with low latency is success, not failure. Watch the latency, not the drop count.

Lockless-qdisc stranded packets (historical). Early lockless-qdisc code had races where a packet could be enqueued but never run; the MISSED-bit protocol above (and several follow-up fixes) exists precisely because the naive lockless design lost packets. If you see phantom stalls on a custom or very old kernel, the qdisc-run race is a known class of bug.

Replacing the root on a multiqueue NIC. tc qdisc replace dev eth0 root ... removes the mq arrangement and its per-queue parallelism, re-serializing transmit behind one locked qdisc — a real throughput regression on high-core-count servers. Configure per-queue (parent N:) if you need to keep mq.

Alternatives and When to Choose Them

The qdisc you pick depends on the goal (the full menu is in Classful and Classless Qdiscs): fq_codel is the safe general-purpose default (fairness + low latency, no tuning); plain fq (a different qdisc — sch_fq.c, not covered here) adds precise per-flow pacing and is the right pairing with the BBR congestion-control algorithm on high-throughput senders (see TCP Congestion Control); cake rolls fq_codel-style AQM, shaping, and more into one knob for the home-router edge; tbf for simple rate-limiting; htb when you need hierarchical bandwidth partitioning into classes. Below the qdisc layer entirely, XDP (see XDP Express Data Path) drops or redirects before an skb even exists — choose it when you do not want to queue at all (DDoS scrubbing, software load balancing).

Production Notes

fq_codel as the default measurably cut latency-under-load across the Linux fleet — it is the kernel-side half of the bufferbloat fix, paired with BQL-bounded driver rings (Byte Queue Limits and Buffer Bloat) so the standing queue forms in the qdisc where CoDel can manage it (the interplay is spelled out in Traffic Control Overview). On high-performance servers the standard arrangement is mq + per-queue fq (with TCP pacing) rather than a single shaped root, because a single locked root qdisc is the scaling bottleneck the lockless-qdisc work was created to avoid. The flows_cnt = 1024 and memory_limit = 32 MB defaults are sane for hosts but worth raising on a busy router serving many simultaneous flows; conversely, on a tightly memory-bounded embedded device the 32 MB limit is the knob to watch. The one durable operational lesson: judge a qdisc by the latency it holds under saturation, not by its drop counter — a low-latency, high-drop fq_codel is working exactly as designed.

See Also

• Traffic Control Overview — where qdiscs sit, the qdisc/class/filter model, the BQL interplay, the kernel-vs-systemd default story (the orientation note this expands)
• Classful and Classless Qdiscs — the class tree and HTB/PRIO/HFSC vs the single-policy qdiscs
• The tc Tool and Filters — configuring qdiscs from userspace and the classifier language
• The Network Transmit Path — the full egress pipeline that calls __dev_queue_xmit → the qdisc
• Byte Queue Limits and Buffer Bloat — bounding the driver ring so the queue forms in the qdisc
• NET_RX and NET_TX Softirqs — where over-budget qdisc draining is deferred (__netif_schedule)
• TCP Congestion Control — fq + BBR pacing; the congestion signals CoDel sends back to TCP
• XDP Express Data Path — the pre-skb alternative to queueing
• MOC: Linux Networking Stack MOC (§8 Traffic Control)