分类： LINUX
2012-07-20 11:27:42
本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。
E-mail:
（一）基本概念为了更好的描述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
