在 linux-htb 中排隊

我試圖了解linux-htb QDisc和linux tc的QDisc的排隊機制。

我可以收集到的資訊：在 TX 期間，數據包排隊進入 linux tc 內的隊列。預設情況下，此隊列遵循 txqueuelen 為 1000 的 pfifo_fast QDisc。數據包調度程序從該隊列中取出數據包並將其放入 TX 驅動程序隊列（環形緩衝區）。

當我們使用 linux-htb 時，只為預設隊列繼承 txqueuelen。[連結]。我的問題：考慮樹（速率在括號 () 中以 kbits/sec 為單位指定）：

     1:   root qdisc (class htb)
    (100)
    / | \ 
   /  |  \
  /   |   \
1:1  1:2  1:3    parent qdiscs (class htb)
(30)  (10)  (60)

1. 是否為每個父 htb 類（1:1、1:2 和 1:3）維護內部隊列？如果是，他們的隊列長度是多少？如果沒有，實際維護了多少個隊列以及出於什麼目的？他們的隊列長度是多少？
2. 排隊規則 (QDisc) 究竟是什麼意思？它是使用的資料結構（隊列）的屬性嗎？或者它是數據包調度程序的屬性？或者也許兩者結合？
3. 在閱讀 htb QDisc [ Link ] 的原始碼時，我遇到了一個叫做直接隊列的東西。什麼是 direct_queue？

如果可能，提供相關來源的連結。

我將回答我自己的問題，因為我自己已經完成了一些原始碼閱讀和研究工作。如果我自己沒有做一些研究工作，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 了？所以我不能自信地回答。但是由於到目前為止您的回復為零，也許這仍然有一些幫助。

---

是否為每個父 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 開發人員在這種情況下決定，所有流量都應該通過，而不是所有流量都應該被丟棄（破壞性太大）。

引用自：https://unix.stackexchange.com/questions/503563