在 linux-htb 中排队

免责声明：这些问题很多，我已经有十年没用过 HTB 了？所以我不能自信地回答。但是由于到目前为止您的回复为零，也许这仍然有一些帮助。

是否为每个父 htb 类（1:1、1:2 和 1:3）维护内部队列？

它们是叶类，每个都由一个 qdisc 队列结构表示，所以我假设它算作内部队列。不确定队列长度 - 抱歉。

来自 sch_htb.c 的代码：

struct htb_class_leaf {
    int     deficit[TC_HTB_MAXDEPTH];
    struct Qdisc    *q;
} leaf;

Qdisc 结构在 include/net/sch_generic.h 中定义

排队规则 (QDisc) 究竟是什么意思？

这取决于上下文，但基本上，它是一个内核 API，数据包在其中入队和出队；因此，QDisc 可以控制进入的数据包应该再次发出（或完全丢弃，甚至）的顺序（或时间）。这就是 HTB、SFQ 或 PRIO 等 QDisc 以各种方式塑造流量的方式，例如优先级或施加带宽限制。

来自 sch_api.c 的评论：

   Generally, queueing discipline ("qdisc") is a black box,
   which is able to enqueue packets and to dequeue them (when
   device is ready to send something) in order and at times
   determined by algorithm hidden in it.

而 HTB 只是几个这样的算法之一。

什么是 direct_queue？

不是 API 的一部分，而是在内部处理......因此您可以将其视为 HTB 算法的一部分。

如果您故意将数据包分类到X:0或默认类别不存在，HTB 决定将它们放在单独的队列中，并且在出队时它将尝试首先将这些数据包发送出去。

来自 sch_htb.c 的评论

 * [...] If we end up with classid MAJOR:0 we enqueue the skb into special
 * internal fifo (direct). These packets then go directly thru. If we still
 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
 * then finish and return direct queue.

...这是它首先将直接数据包出列的地方。

这通常是错误配置的结果（将数据包发送到不存在的类），但 HTB 开发人员在这种情况下决定，所有流量都应该通过，而不是所有流量都应该被丢弃（破坏性太大）。

我将回答我自己的问题，因为我自己已经完成了一些源代码阅读和研究工作。如果我自己没有做一些研究工作，frostschutz 和 sourcejedi 的答案也会有很大帮助——就我的知识而言，它们似乎是正确的（虽然没有那么详细，但它们给了你一个起点自己做剩下的研究）。

一些理论：有两种排队规则：有类和无类。

有类学科（正如sourcejedi的回答所说）是灵活的。它们允许您将子类 qdisc 附加到它们，并且可以在可能的情况下与其他类共享带宽。叶类具有附加到它们的无类 qdisc（基本/基本 qdisc）（也称为基本 qdisc）。由这些基本 qdisc 管理的队列是数据包排队和出队的地方。分组通过对应于类的算法从这些类中出列和入队。有类 qdisc 的示例有：HTB 和 CBQ。

无类qdisc 是基本的或基本的 qdisc，它们是刚性的，因为它们不能有子 qdisc 连接到它们，也不能共享带宽。用幼稚的话来说，他们是靠自己的。这些 qdisc 拥有一个队列，根据与 qdisc 对应的算法，它们从该队列中对数据包进行排队和出队。无类 qdisc 的示例：pfifo、bfifo、pfifo_fast（Linux tc 默认使用）、tbf、sfq 等等。

在问题的示例树中，每个叶子 htb 类 1:1、1:2 和 1:3 都附加了一个基本 qdisc，默认情况下是 pfifo（不是 pfifo_fast）。tc可以使用用户空间实用程序通过以下方式更改附加到叶子的基本 qdisc  ：

tc qdisc add dev eth0 parent 1:11 handle 30: pfifo limit 5 
tc qdisc add dev eth0 parent 1:12 handle 40: sfq perturb 10

有关这方面的更多详细信息，请参阅HTB Linux 排队规则手册。因此，树实际上看起来像这样：

       1: root qdisc (class htb)
     (100)
     / | \ 
    /  |  \
   /   |   \
 1:1  1:2  1:3    parent qdiscs (class htb)
(30)  (10)  (60)
 ||    ||    || -----> pfifo qdiscs (queue length: txqueuelen (default, can be changed by tc utitlity))

请注意，参数 txqueuelen 是一个特定于接口的参数。这意味着参数是接口的属性，可以使用iproute2或进行更改ifconfig。默认情况下，它的值为 1000。这是一个如何通过以下方式将其更改为 200 的示例iproute2：

ip link set eth0 txqueuelen 200

创建叶节点时（在 HTB qdisc 的上下文中），默认情况下将 pfifo qdisc 附加到叶类。此 pfifo 使用接口的 txqueuelen 队列限制进行初始化。这可以htb_change_class() 在sch_htb.c的函数中找到，第 1395 行：

/* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
 * so that can't be used inside of sch_tree_lock
 * -- thanks to Karlis Peisenieks
 */
new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
                          classid, NULL);

对于 pfifo 队列的默认队列长度，请参阅sch_fifo.c的第 61 行：

u32 limit = qdisc_dev(sch)->tx_queue_len;

当内核想要对数据包进行排队或出队时，它会直接与根 qdisc（可能是有类或无类）交互。如果根 qdisc 是有类的并且有孩子，那么它首先对数据包进行分类（决定将数据包发送到哪个孩子）。完成的内核源代码：sch_htb.c，第 209 行：

static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
                                      int *qerr)

在阅读评论时，可以很容易地推断出此函数返回以下之一：

1. NULL，如果数据包应该被丢弃

2. -1，如果数据包应该排队进入direct_queue

3. 一个叶子节点（包含一个基本的 qdisc，数据包实际结束的地方） 这个函数遍历树的所有内部节点（类），直到它返回一个叶子节点，数据包应该在其中排队。

在出队时，每个类都遵循与其 qdisc 关联的算法来决定从哪个孩子中出队，并且孩子们做同样的事情，直到一个数据包从附加到叶类的基本 qdisc 中出队。这也确保了子类的速率不超过其父类。（因为父母将决定数据包是否通过）。我没有经历过htb中出队的来源，所以我无法提供来源。

直接队列：它是由 HTB qdisc 维护的特殊内部 fifo 队列，数据包以硬件速度从该队列中出列。它的队列长度是 txqueuelen。如果 HTB 无法将数据包分类到其中一个子 qdisc 中，则数据包最终会进入直接队列，并且未指定默认值。

所以我自己的问题的答案：

1. 是的，因为它们是叶节点，默认情况下它们是 pfifo 队列，接口的队列长度为 txqueuelen，默认为 1000，可以更改。

2. 排队规则就像算法和队列组合在一个包中！如果您问我，排队规则是队列类型和数据包调度程序的属性（这里的数据包调度程序是指使数据包入队和出队的算法）。例如，队列可能是 pfifo 或 bfifo 类型。用于入队和出队的算法是相同的，但队列长度以字节 fifo (bfifo) 为单位。当达到字节限制时，数据包将被丢弃在 bfifo 中。默认字节限制计算为mtu*txqueuelen。例如，当数据包入队时，数据包长度会添加到当前队列长度。类似地，当数据包出队时，从队列长度中减去数据包长度。

3. 上面回答了。

一些来源可能会参考：

1. Linux 网络流量控制 — 实施概述 (PDF)

2. Linux内核中心之旅：流量控制、整形和QoS

3. 揭秘 TC - Criteo 研发博客

4. Linux 网络堆栈中的排队 - Linux Journal

一些基于模糊记忆的快速搜索：

HTB 很灵活。默认情况下，我认为每个叶类都有一个 FIFO，也许它使用 FIFO 的默认配置。但是，您也可以将 PFIFO 或 FQ_CODEL 用于叶类。参见例如“可选地将排队规则附加到叶类”：http: //luxik.cdi.cz/~devik/qos/htb/manual/userg.htm

我想你会看到他们，如果你跑tc qdisc show。

“仅当您的过滤器之一明确针对 htb qdisc 的“0”类 ID 时，才使用此“直接”队列” https://lists.bufferbloat.net/pipermail/cerowrt-devel/2013-June/006507.html。直接队列未定型。显然现在可以控制直接队列的长度，尽管我不知道 tc 如何（或是否）支持这一点。https://patchwork.ozlabs.org/patch/225546/

我不会说有一个单独的“数据包调度程序”。数据包调度程序是一个 QDisc（虽然，man tc-tbf将自己描述为“从不调度流量”；这意味着它从不重新排序）。