mjhjmtu

I am trying to understand the queuing mechanism of linux-htb QDisc and QDisc of linux tc in general. I am new to networking and want to get my basics cleared about how a packet is processed inside linux kernel.

What I could gather:
During TX, the packet is queued into the queue inside the linux tc. This queue by default follows a pfifo_fast QDisc with a txqueuelen of 1000. The packet scheduler dequeues the packet from this queue and puts it onto the TX driver queue (ring buffer).

When we use linux-htb, the txqueuelen is inherited only for the default queue. [Link].
My question:
Consider the tree (rates are specified in kbits/sec in parenthesis ()):

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

1. Are there internal queues maintained for each of the parent htb classes (1:1, 1:2 and 1:3)? If yes what is their queue length? If not, how many queues are actually maintained and for what purpose? What is their queue length?




2. What exactly is meant by Queueing Discipline (QDisc)? Is it the property of the data structure used (queue)? or it is a property of the packet scheduler? Or maybe both combined?




3. While reading the source code of htb QDisc [Link], I came accross something called a direct queue. What is a direct_queue?

Provide link to relevant sources if possible.

Disclaimer: Those are a lot of questions and I haven't used HTB in like a decade? So I can't answer with confidence. But since you got zero replies so far, maybe this is still of some help.

Are there internal queues maintained for each of the parent htb classes (1:1, 1:2 and 1:3)?

They are leaf classes, and each is represented by a qdisc queue struct, so I assume that counts as internal queues. Not sure about the queue length - sorry.

Code from sch_htb.c:

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

the Qdisc structure is defined in include/net/sch_generic.h

What exactly is meant by Queueing Discipline (QDisc)?

This depends on context but basically, it's a kernel API in which packets are enqueued and dequeued; so the QDisc is given some control about the order in which (or time when) packets that come in should go out again (or dropped altogether, even). That is how QDiscs like HTB, SFQ or PRIO then shape traffic in various ways, like prioritize or impose bandwidth limits.

Comment from 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.

And HTB is just one of several such algorithms.

What is a direct_queue?

Not part of the API but handled internally... so you could consider it part of the HTB algorithm.

If you deliberately classify packets to X:0 or if the default class doesn't exist, HTB decided to put them in a separate queue, and on dequeue it will attempt to send those packets out first.

Comment from 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.

...and this is where it dequeues direct packets first.

This is usually the result of a misconfiguration (sending packets to nonexistent class), but the HTB devs decided in that case, all traffic should be passed, instead of all traffic should be dropped (too destructive).

Some quick searches based on vague memories:

HTB is flexible. By default I think you get a FIFO for each leaf class, maybe it uses the default configuration for FIFO. However you can also e.g. use PFIFO or FQ_CODEL for a leaf class. See e.g. "optionally attach queuing disciplines to the leaf classes" here: http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm

I think you will see them if you run tc qdisc show.

"This 'direct' queue is only used if one of your filter explicitly targets the '0' classid of htb qdisc" https://lists.bufferbloat.net/pipermail/cerowrt-devel/2013-June/006507.html . The direct queue is not shaped. Apparently the length of the direct queue can now be controlled, although I do not know how (or whether) tc supports this. https://patchwork.ozlabs.org/patch/225546/

I would not say there is a separate "packet scheduler". A packet scheduler is a QDisc (although, man tc-tbf describes itself as "never schedules traffic"; what it means is that it never re-orders it).

I am going to answer my own question since I have done some source code reading and research work myself. If I had not done some research work myself, the answers by frostschutz and sourcejedi would be of a great help too - they seem to be correct as far as my knowledge goes (although not into as much detail, but they give you a starting point to do the rest of the research yourself).

Some theory:
There are two kinds of queuing disciplines: classful and classless.

Classful disciplines are (as the answer by sourcejedi says) flexible. They allow you to attach children classful qdiscs to them and can share bandwidth with other classes, when possible. Leaf classes have a classless qdisc (elementary/fundamental qdisc) attached to them (also called an elementary qdisc). The queues managed by these elementary qdiscs is where the packets get queued and dequeued. The packets are dequeued and enqueued from these classes by an algorithm corresponding to the class. Examples of classful qdiscs are: HTB and CBQ.

Classless qdiscs are the fundamental or the elementary qdiscs, which are rigid in the sense that they cannot have children qdiscs attached to them, nor can they share bandwidth. In naive terms, they are on their own. These qdiscs own a queue from which they queue and dequeue packets according to the algorithm corresponding the qdisc. Examples of classless qdisc: pfifo, bfifo, pfifo_fast (default used by linux tc), tbf, sfq and a few more.

In the example tree in the question, each of the leaf htb classes 1:1, 1:2 and 1:3 have an elementary qdisc attached to them which is by default pfifo (not pfifo_fast). The elementary qdisc attached to the leaf can be changed using tc userpace utitlity in the following way:

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

More details about this can be found here: [Link]
Therefore the tree actually looks like this:

 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))

Notice the parameter txqueuelen is a interface specific parameter. That means, the parameter is a property of the interface and can be changed using iproute2 or ifconfig. By default, its value is 1000. Here is an example of how to change it to 200 it via iproute2:

ip link set eth0 txqueuelen 200 

When a leaf node is created (in context of HTB qdisc), pfifo qdisc is attached to the leaf class by default. This pfifo is initialized with a queue limit of txqueuelen of the interface. This can be found in the function htb_change_class() in sch_htb.c, line 1399:

 /* 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);

For the default queue length of a pfifo queue, refer to sch_fifo.c, line 65:

 u32 limit = qdisc_dev(sch)->tx_queue_len;

Kernel directly interacts with the root qdisc (maybe classful or classless) when it want to queue or dequeue packet. If the root qdisc is classful and has children, then it first classifies the packet (decides which child to send the packet to).
Kernel source where it is done: sch_htb.c, line 212:

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

On reading the comments, one can easily infer that this function either returns with one of the following:

1. NULL. if packet should be dropped




2. -1, if the packet should be queued into direct_queue




3. a leaf node (which contains an elementary qdisc, where the packets actually end up)
   This function traverses through all the interior nodes (Classes) of the tree, until it returns a leaf node, where the packet should be queued.

While dequeuing, each of the classes follow the algo associated with their qdisc to decide which of the children to dequeue from, and children do the same thing, until a packet is dequeued from an elementary qdisc attached to a leaf class. This also ensures that the rate of a child class is no more than its parent. (Since the parent will decide whether the packet will pass through or not). I have not gone through the source of dequeuing in htb, So can't provide a source for that.

Direct queue: It is a special internel fifo queue maintained by the HTB qdisc from which the packets are dequeued at hardware speed. Its queue length is txqueuelen. A packet ends up in a direct queue if HTB is unable to classify it into one of the children qdiscs, and the default is not specified.

So the answers to my own questions:

1. Yes, since they are leaf nodes, by default they are pfifo queues with queue length txqueuelen of the interface which is 1000 by default and can be changed.




2. A queuing discipline is like the algo together with the queue combined in a single package! If you ask me queuing discipline is property of both the type of queue and and the packet scheduler (Here packet scheduler means the algo which enqueues and dequeues the packet). For example, a queue might be of type pfifo or bfifo. The algo used for enqueuing and dequeuing is same, but the queue lengths are measured in bytes for the byte fifo (bfifo). Packets are dropped in a bfifo, when the byte limit is reached. The default byte limit is calculated as mtu*txqueuelen. When a packet is enqueued for example, the packet length is added to the current queue length. Similarly when the packet is dequeued, the packet length is subtracted from the queue length.




3. Answered above.

Some sources one might consult:

1. https://www.almesberger.net/cv/papers/tcio8.pdf




2. http://wiki.linuxwall.info/doku.php/en%3aressources%3adossiers%3anetworking%3atraffic_contro




3. https://medium.com/criteo-labs/demystification-of-tc-de3dfe4067c2




4. https://www.linuxjournal.com/content/queueing-linux-network-stack