Linux FQ 队列实现原理浅析
enqueue入队过程
上一张图：
详细描述了fq队列的入队过程，其中着重理解几个数据结构：
- sock作为键的红黑树：用于关联skb和flow
- next_time作为键的红黑树：用于保存未来被调度的flow，并决定timer唤醒时间以调度skb
- new_list：用于保存新创建尚未发包的flow链表，用于优先调度触发第一包
- old_list：用于保存正在被调度的flow。
dequeue调度过程
dequeue操作要比enqueue操作更复杂一些，先看一张图：
这是一个相对动态的过程，由Linux的hrtimer来驱动，其超时时间则取决于每一个flow的最近要发送的skb的时间，诸多flow中的时间取最小，这明显倾向于使用红黑树来实现，我们来看一下dequeue的核心代码：
static struct sk_buff *fq_dequeue(struct Qdisc *sch)
{
...
/* 将红黑树上已经到期的flow从红黑树上摘除，加入old_list准备开始被调度 */
fq_check_throttled(q, now);
begin:
/* 优先无条件调度新创建的flow上的skb，触发其第一包发送，以计算next_time */
head = &q->new_flows;
if (!head->first) {
/* 如果没有新创建的flow，则调度old_list已经创建且被调度的flow */
head = &q->old_flows;
if (!head->first) {
/* 设置最短的超时，延后执行dequeue */
qdisc_watchdog_schedule_ns(&q->watchdog,
q->time_next_delayed_flow);
return NULL;
}
}
/* 从head到tail的顺序调度 */
f = head->first;
if (unlikely(f->head && now < f->time_next_packet)) {
/* 同一个flow的skb链表依次被调度，然而由于pacing，当前skb允许发送的时间 */
/* 在当前时间之后，则终止当前flow，将其插入delay rb-tree，同时调度old_list */
/* 下一个flow */
head->first = f->next;
fq_flow_set_throttled(q, f); // 冒泡找到最近的expires
goto begin;
}
/* 取出被调度的skb，根据pacing rate计算下一个包发送的时间 */
skb = fq_dequeue_head(sch, f);
//if (f->credit > 0 || !q->rate_enable)
if (!q->rate_enable)
goto out;
rate = skb->sk->sk_pacing_rate;
plen = qdisc_pkt_len(skb);
len = (u64)plen * NSEC_PER_SEC;
do_div(len, rate);
f->time_next_packet = now + len;
out:
return skb;
}
此其中的核心是
f->time_next_packet
这就是红黑树节点的键值。
速率pacing rate
Linux FQ中给定一个flow的pacing rate来计算发送下一个skb的时间依然沿用了传统的方案，即根据当前skb的长度来计算下一个skb发送的时间，依托于公式：
Δt=ΔSvΔt=ΔSv
很显然的事情，这里的ΔSΔS就是当前skb的长度，此公式的含义即，发送当前的skb一共需要ΔtΔt的时间，Linux的实现显然是粗粒度粗糙的：
len = (u64)plen * NSEC_PER_SEC; do_div(len, rate); f->time_next_packet = now + len;
它是基于skb来做pacing发送的，而不是基于字节来做pacing发送的，这也是主机和线路之间的矛盾，不多说。
和O(1)调度器以及CFS调度器比较
其实，FQ机制也CFS进程调度器以及磁盘IO的公平队列是完全一致的实现：
和CFS不同的是，FQ同时维护了一个正在被调度flow队列，即old_list(此处我们忽略作为开场作用的new_list)，显然在CFS中，CPU时间同时只能分配给一个task，这是不同。观察这个old_list，会发现这是一个静态优先级数据结构，它和O(1)调度器非常类似：
这个和磁盘IO公平队列几乎是完全一致的，时间片可以分配给多个entry。
后面两个小节说一下pacing的实现，而不是FQ。说白了pacing的实现并不一定非得用FQ，FQ的主要要解决的问题是如何用单一的timer去驱动任意多和flow，使其都能按照自己的pacing发送数据。然而，我们能不能把这个锅甩给Linux的调度器呢？
我自己实现的TCP Pacing机制
说起FQ，不得不提的是Google BBR拥塞控制算法，前年在初次接触BBR时被这个Pacing建议弄得着迷，说实话Linux TCP Pacing机制以及FQ早已有之，然而直到BBR才结合在一起起作用，我当时在想，既然TCP本身就是per flow的，干嘛还要Qdisc层再维护一个flow表，并且我发现这个FQ实现的公平队列在高并发TCP流时，其调度时间并不准确，所以我倾向于在TCP层直接实现Pacing：
彻底实现Linux TCP的Pacing发送逻辑-普通timer版：https://blog.csdn.net/dog250/article/details/54424629
彻底实现Linux TCP的Pacing发送逻辑-高精度hrtimer版：https://blog.csdn.net/dog250/article/details/54424751
我起初认为这可行，是因为我觉得TCP反正也有那么多timer了，再多一个也不多。然而却忽略了两个问题：
- 高速率TCP
pacing rate极大时，timer将会频繁超时，为Linux调度子系统造成压力。 - 高并发流
多个TCP流接连超时，将会持续加重Linux调度子系统的负担。
所以说，单流测试OK，不代表真的就可用。
OK，此问题何解？
一个timer调度100000条TCP连接不是吃力吗？100000个timer每一个调度一个TCP连接不是调度器吃力吗？看来简单的甩锅是不妥的，解法是，干嘛不搞固定的10个timer，或者5个，或者20个，或者30个，看你的CPU配置了，只要是固定的数量的timer就行，以10个timer为例，一个timer平均只要对付10000条TCP流就好了，数量级的差异！
FQ只需要多加一个层次就能解决问题！
社区的internal TCP Pacing补丁
你可以先读一下这个：
TCP Pacing：https://lwn.net/Articles/199644/
然后会问，为什么该patch没有被applied，请看我上一节的解释。
好吧，时隔10多年，又来了一个：
[v2,net-next] tcp: internal implementation for pacing：https://patchwork.ozlabs.org/patch/762899/
几乎是一样的东西。不多说。
插队策略
FQ针对retransmit的数据包实现了一个插队策略：
// flow_queue_add/* add skb to flow queue * flow queue is a linked list, kind of FIFO, except for TCP retransmits * We special case tcp retransmits to be transmitted before other packets. * We rely on fact that TCP retransmits are unlikely, so we do not waste * a separate queue or a pointer. * head-> [retrans pkt 1] * [retrans pkt 2] * [ normal pkt 1] * [ normal pkt 2] * [ normal pkt 3] * tail-> [ normal pkt 4] */
这里还有没有别的花式插队或者花式避让策略呢？比方说针对纯ACK，小包，持续大包中的小包，持续小包中的大包。这个就不细说了，类比一下我们在排队时来了一帮穿制服的人…然后还有道路上的特种车辆这种，嗯，我们还有FQ的internal队列没有用呢，同时，能不能再多实现几个类似的队列呢？
