TC流量控制实现分析（初步）

本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。

E-mail:

来源: http://blog.csdn.net/wwwlkk

（一）基本概念

为了更好的描述TC流量控制，先明确一些概念。

流控对象：队列规定。

无类流控对象：无类队列规定。

分类流控对象：分类的队列规定。

每个分类流控对象都有默认的子流控对象，默认的子流控对象必定是无类流控对象。

子流控对象：分类流控对象中包含的流控对象。

无类流控对象必定包含一个或者多个的数据包队列，用于存储数据包。

无类和分类流控对象都有默认的分类规定，也可以使用过滤器增加分类规则。

分类流控对象是流控对象的容器(包含无类和分类)，无类流控对象是数据包的容器。(注意：一些复杂的流控对象可同时作为流控对象和数据包的容器，比如分层的令牌桶)

数据包进入一个分类流控对象，分类流控对象将根据分类规则(默认的或者过滤器)，决定将数据包送到某个子流控对象。

数据包进入一个无类流控对象，无类流控对象将根据分类规则(默认的或者过滤器)，决定将数据包加入到某个数据包队列。

分类流控对象出队操作：分类流控对象将根据出队规则(固定的)，选择一个子流控对象，并执行子流控对象的出队操作。

无类流控对象出队操作：无类流控对象将根据出队规则(固定的)，选择一个数据包出队。

每块网卡都有一个出口根流控对象。每个流控对象都指定一个句柄，以便以后的配置语句能够引用这个流控对象。除了出口流控对象之外，每块网卡还有一个入口流控对象,入口流控对象的类型是固定的(是ingress类型)。

运行流控对象：都是指运行出口流控对象，也就是根据出口流控对象的出队规则(固定的)，发送流控对象中的所有数据包。

流控对象为空：流控对象中没有数据包。

入口流控对象没有真正意义上的出队和入队操作，只是根据过滤规则来决定是否丢弃数据包，流控的实现主要在出口流控对象，下面先分析出口流控的实现。

数据到达出口流控时，上层的所有处理已经完成，数据包已经可以交到网卡设备进行发送，在数据交到网卡设备发送前将会进入出口流控，进入出口流控的函数为dev_queue_xmit(); 如果是入口流控, 数据只是刚从网卡设备中收到, 还未交到网络上层处理, 不过网卡的入口流控不是必须的, 缺省情况下并不进行流控，进入入口流控函数为ing_filter()函数，该函数被skb_receive_skb()调用。

dev_queue_xmit中进入出口流控对象的函数段如下：

       txq = dev_pick_tx(dev, skb);//获取出口流控的控制结构

       q = rcu_dereference(txq->qdisc);//获取出口流控的根流控对象

       if (q->enqueue) {

              rc = __dev_xmit_skb(skb, q, dev, txq);//使用流控对象发送数据包(包含入队和出队)

              goto out;

       }

__dev_xmit_skb函数主要做两件事情：

1.      如果流控对象为空的，试图直接发送数据包。

2.      如果流控对象不空，将数据包加入流控对象，并运行流控对象。

 

调用qdisc_run()将会运行一个流控对象，有两个时机将会调用qdisc_run()：

1．__dev_xmit_skb()

2. 软中断服务线程NET_TX_SOFTIRQ

软中断线程NET_TX_SOFTIRQ中将会运行的流控对象组织如下：

图1 软中断中的流控对象组织

static inline void qdisc_run(struct Qdisc *q)

{

       if (!test_and_set_bit(__QDISC_STATE_RUNNING, &q->state))//测试是否有其他例程正在运行本对象

              __qdisc_run(q);

}

__QDISC_STATE_RUNNING标志用于保证一个流控对象不会同时被多个例程运行。

软中断线程的动作：运行加入到output_queue链表中的所有流控对象，如果试图运行某个流控对象时，发现已经有其他内核路径在运行这个对象，直接返回，并试图运行下一个流控对象。

void __qdisc_run(struct Qdisc *q)//运行流控对象q

{

       unsigned long start_time = jiffies;

       while (qdisc_restart(q)) {//返回值大于0，说明流控对象非空。

              /*

               * Postpone processing if

               * 1. another process needs the CPU;

               * 2. we've been doing it for too long.

               */

              if (need_resched() || jiffies != start_time) {//已经不允许继续运行本流控对象。

                     __netif_schedule(q);//将本队列加入软中断的output_queue链表中。

                     break;

              }

       }

       clear_bit(__QDISC_STATE_RUNNING, &q->state);

}

如果发现本队列运行的时间太长了，将会停止队列的运行，并将队列加入output_queue链表头。

 

现在数据包的发送流程可以总结如下：(流控对象为空表示对象中没有数据包)

1.      调用dev_queue_xmit()发送一个数据包，如果出口流控对象为空，试图直接发送数据包。

2.      如果出口流控对象非空，数据包加入出口流控对象。

3.      调用qdisc_run(struct Qdisc *q)运行出口流控对象，也就是，调用对象对象的出队函数选择一个数据包，并发送这个数据包，如果时间允许就循环执行这个过程，直到流控对象为空。注意：如果已经有其他内核路径正在运行队列，函数将不做任何事情，并提前返回。

4.      本流控对象运行时间太长了，停止本对象运行，并且将本流控对象加入软中断服务NET_TX_SOFTIRQ的output_queue链表头。

5.      当执行软中断服务线程NET_TX_SOFTIRQ时，将从output_queue链表头开始顺序运行链表中的所有流控对象。

 

）建立一个根流控对象

下面使用具体的例子来说明流控对象的具体实现

首先使用如下命令在eth0建立一个根流控对象。

#tc qdisc add dev eth0 root handle 22 prio bands 4

其中流控对象的类型是”prio”，对象句柄是22，对象使用4个带(也就是包含4个子流控对象，默认的子流控对象类型是”pfifo”，出队时第一个子流控对象的优先级最高)

则内核中建立的流控对象如图2，3所示：

图3  建立”prio”类型的根流控对象_2

这个prio流控对象的句柄是22，使用4个带，每个带都是一个pfifo类型的对象，每个pfifo类型的对象都有一个数据包队列，用于存储数据包。根据数据包的skb->priority值确定数据包加入哪个带，这里使用默认的prio2band，默认的skb->priority值与带的对应关系如图3中所示。

 

现在假设要发送一个skb->priority值是8的数据包，发送流程如下：

1.      使用网卡的根流控对象的入队函数将数据包入队

2.      由于未设置过滤器，则直接根据数据包的skb->priority=8找到对应的带是0，则将数据包加入第一个pfifo流控对象。

3.      调用pfifo流控对象的入队函数，将数据包加入对象中的数据包队列。

4.      调用qdisc_run()启动根流控对象。

5.      调用根流控对象的出队函数，函数内先选择第一个pfifo流控对象并调用其出队函数选择一个数据包，出队函数返回，如果第一个pfifo流控对象为空，选择第二个pfifo流控对象并调用其出队函数选择一个数据包，直到找到一个数据包。

6.      发送5找到的数据包。

7.      只要时间允许且流控对象不为空，就一直循环5，6的过程。

3.2）建立一个子流控对象

prio流控对象是分类对象，可以添加子对象(未添加子对象时使用默认子对象)。

接下来使用以下命令在根队列的第4个带增加一个prio类型的子队列（此前第4个带是pfifo类型的对象，现在将替换为prio类型的对象。）

#tc qdisc add dev eth0 parent 22:4 handle 33 prio bands 5 priomap 3 3 2 2 1 2 0 0 1 1 1 1 1 1 1 1

这个prio对象是根对象的第4个带的子对象，句柄是33，并且这个子对象有5个带，skb->priority和带的映射关系是3 3 2 2 1 2 0 0 1 1 1 1 1 1 1 1。

则内核中建立的子流控对象如图4所示：

3.3）添加一个过滤器

由于根对象的使用默认的prio2band映射，默认映射只映射前3个带，而prio子对象在第4个带，所以在这里，数据包是不会被加入prio子对象，下面使用过滤器将目的ip是4.3.2.1的数据包加入到prio子对象，命令如下：

# tc filter add dev eth0 protocol ip parent 22: prio 2 u32 /

> match ip dst 4.3.2.1/32 flowid 22:4

在网卡eth0的根队列增加一个优先级是2且类型是u32的过滤器，过滤器将目的ip是4.3.2.1的数据包定位到第4个带。

u32过滤器的结构如图5所示：

 

图5 u32类型过滤器结构

其中val存储4.3.2.1的信息，off存储偏移位置(目的ip字段的偏移)。

现在数据包的入队流程如下：

1.      根对象的过滤器链非空，遍历根对象的过滤器链，遇到第一个匹配的过滤器就返回，并根据返回的结果选择子类。

2.      每个过滤器都调用相应的分类函数，并根据过滤器的私有数据来匹配数据包。

 

3.4）流控类和过滤器类型的的组织

相同类型的对象将使用相同的操作函数(比如出/入队函数)，相同类型的过滤器也是相同的操作函数(比如分类函数)。对象中struct Qdisc_ops    *ops字段指向并对象的操作函数，过滤器中struct tcf_proto_ops* ops字段指向本过滤器的操作函数。

下面看一下对象类型和过滤器类型是如何组织的：图6对象类型的组织，图7过滤器类型的组织。

 

图6 对象类型组织

图7 过滤器类型组织

使用int register_qdisc(struct Qdisc_ops *qops)注册对象类型。

使用int register_tcf_proto_ops(struct tcf_proto_ops *ops)注册过滤器类型。

以上分析了prio类型流控对象，pfifo类型流控对象，u32类型的过滤器的实现机制，内核还提供了很多其它的更复杂的流控对象和过滤器对象，有待进一步分析，但是基本的框架还是类似的。

 

3.5）入口流控对象

int netif_receive_skb(struct sk_buff *skb)à

skb = handle_ing(skb, &pt_prev, &ret, orig_dev);à

ing_filter(skb)

增加一个入口流控队列# tc qdisc add dev eth0 ingress

入口流控的对象类型必定是：

static struct Qdisc_ops ingress_qdisc_ops __read_mostly = {

       .cl_ops           =     &ingress_class_ops,

       .id           =     "ingress",

       .priv_size =     sizeof(struct ingress_qdisc_data),

       .enqueue  =     ingress_enqueue,

       .destroy   =     ingress_destroy,

       .dump            =     ingress_dump,

       .owner           =     THIS_MODULE,

};

入口流控对象的私有数据是：

struct ingress_qdisc_data {

       struct tcf_proto      *filter_list;

};

入口流控对象只有入队函数，没有出队函数。

入队动作：先遍历过滤器，如果某个过滤器匹配，执行action（接收或者丢弃数据包），并将结果返回，最终根据这个返回的结果决定是否丢弃数据包。

 

iproute2是一个用户空间的程序，它的功能是解释以tc开头的命令，如果解释成功，把它们通过AF_NETLINK的socket传给Linux的内核空间，使用的netlink协议类型是NETLINK_ROUTE。

发送的netlink数据包都必须包含两个字段：protocol和msgtype，内核根据这两个字段来定位接收函数。

在系统初始化的时候将会调用如下函数：

static int __init pktsched_init(void)

{

       register_qdisc(&pfifo_qdisc_ops);

       register_qdisc(&bfifo_qdisc_ops);

       register_qdisc(&mq_qdisc_ops);

       proc_net_fops_create(&init_net, "psched", 0, &psched_fops);

       rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);

       rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);

       rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);

       rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);

       rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);

       rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);

       return 0;

}

其中的rtnl_register()函数用于注册TC要接收的消息类型以及对应的接收函数。注册到图8所示的结构中。

 

图8 接收函数的组织

下面以命令#tc qdisc add dev eth0 root handle 22 prio bands 4为例子说明如何进行通信的。

分析tc：main(int argc, char **argv)被调用，此函数在tc/tc.c中；

分析tc qdisc：do_qdisc(argc-2, argv+2);被调用，此函数在tc/tc_qdisc.c中；

分析tc qdisc add： tc_qdisc_modify(RTM_NEWQDISC, NLM_F_EXCL|NLM_F_CREATE, argc-1, argv+1); 被调用，此函数在tc/tc_qdisc.c中，在这个函数中，将分析完这一行tc的命令，各种参数（例如RTM_NEWQDISC） 被写到netlink包中，并且开始与核心通信。

Netlink包携带的数据如下

struct {

              struct nlmsghdr        n;

              struct tcmsg              t;

              char                  buf[TCA_BUF_MAX];

       } req;

       req.n.nlmsg_type = cmd; = RTM_NEWQDISC

       req.t.tcm_family = AF_UNSPEC;

内核是根据以上两个参数定位接收函数。

内核接收函数是static int rtnetlink_rcv_msg(struct sk_buff *skb, struct nlmsghdr *nlh)

根据以上两个参数选择接收函数：

doit = rtnl_get_doit(family, type);

从前面初始化时注册的处理函数是：

rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);

可以知道对应的接收函数是：

static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)

 

通信总结如下：

1.      内核调用void rtnl_register(int protocol, int msgtype, rtnl_doit_func doit, rtnl_dumpit_func dumpit)将接收函数注册到rtnl_msg_handlers中。

2.      用户空间填充netlink数据包，使用的netlink协议是NETLINK_ROUTE。

3.      内核根据netlink数据包中的protocol和msgtype字段，搜索rtnl_msg_handlers，定位接收函数。

 

 

 

图2 建立”prio”类型的根流控对象_1