在 linux-htb 中排队

Question 1

由于我自己做了一些源代码阅读和研究工作，所以我将回答我自己的问题。如果我自己没有做过一些研究工作，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）。附加到叶子的基本 qdisc 可以使用 tc用户空间实用程序按以下方式更改：

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)

阅读注释后，我们可以很容易地推断出该函数返回以下内容之一：

如果数据包应该被丢弃，则返回 NULL
-1，如果数据包应排队到 direct_queue 中
叶节点（包含基本 qdisc，数据包实际结束的位置）该函数遍历树的所有内部节点（类），直到返回叶节点，数据包应在该叶节点排队。

在出列时，每个类都遵循与其 qdisc 关联的算法来决定从哪个子级出列，并且子级执行相同的操作，直到数据包从附加到叶类的基本 qdisc 出列。这也保证了子类的速率不超过其父类。（因为父级将决定数据包是否通过）。我还没有了解 htb 中出队的来源，所以我无法提供相关来源。

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

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

是的，由于它们是叶子节点，所以默认情况下它们是pfifo队列，接口的队列长度txqueuelen默认为1000，可以更改。
排队规则就像算法和队列组合在一个包中！如果你问我，排队规则是队列类型和数据包调度程序的属性（这里数据包调度程序指的是使数据包入队和出队的算法）。例如，队列的类型可能是 pfifo 或 bfifo。用于入队和出队的算法是相同的，但队列长度以字节 fifo (bfifo) 为单位进行测量。当达到字节限制时，数据包将被丢弃在 bfifo 中。默认字节限制计算如下mtu*txqueuelen。例如，当数据包入队时，数据包长度将添加到当前队列长度中。类似地，当数据包出队时，从队列长度中减去数据包长度。
上面已经回答了。

人们可以查阅一些资料来源：

Answer

由于我自己做了一些源代码阅读和研究工作，所以我将回答我自己的问题。如果我自己没有做过一些研究工作，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）。附加到叶子的基本 qdisc 可以使用 tc用户空间实用程序按以下方式更改：

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)

阅读注释后，我们可以很容易地推断出该函数返回以下内容之一：

如果数据包应该被丢弃，则返回 NULL
-1，如果数据包应排队到 direct_queue 中
叶节点（包含基本 qdisc，数据包实际结束的位置）该函数遍历树的所有内部节点（类），直到返回叶节点，数据包应在该叶节点排队。

在出列时，每个类都遵循与其 qdisc 关联的算法来决定从哪个子级出列，并且子级执行相同的操作，直到数据包从附加到叶类的基本 qdisc 出列。这也保证了子类的速率不超过其父类。（因为父级将决定数据包是否通过）。我还没有了解 htb 中出队的来源，所以我无法提供相关来源。

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

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

是的，由于它们是叶子节点，所以默认情况下它们是pfifo队列，接口的队列长度txqueuelen默认为1000，可以更改。
排队规则就像算法和队列组合在一个包中！如果你问我，排队规则是队列类型和数据包调度程序的属性（这里数据包调度程序指的是使数据包入队和出队的算法）。例如，队列的类型可能是 pfifo 或 bfifo。用于入队和出队的算法是相同的，但队列长度以字节 fifo (bfifo) 为单位进行测量。当达到字节限制时，数据包将被丢弃在 bfifo 中。默认字节限制计算如下mtu*txqueuelen。例如，当数据包入队时，数据包长度将添加到当前队列长度中。类似地，当数据包出队时，从队列长度中减去数据包长度。
上面已经回答了。

人们可以查阅一些资料来源：

Question 2

免责声明：这些问题太多了，我已经有十年没有使用过 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 只是几种此类算法之一。

什么是直接队列？

不是 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 开发人员决定在这种情况下，所有流量都应该通过，而不是所有流量都应该被丢弃（破坏性太大）。

Answer