liux2.6.35内核u32分类器逻辑架构分析.doc

本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。
E-mail: wwwlkk@
来源:
liux2.6.35内核u32分类器逻辑架构分析
前言：1.在使用u32分类器的时候会发现，内核的行为会与用户规则的行为不一致。2.想找到具备高性能的u32分类器规则，需要对u32分类器的内核实现架构有深入的理解。基于以上2个原因，分析了linux2.6.35内核的u32分类器源码，重点是给出u32分类器的逻辑架构。
（一）在理解u32分类器的逻辑架构前，需要先理解几个概念：
1. 队列分类器链：每个可分类整形队列都有一个分类器链，这条链上的所有分类器都有相同的数据结构，如下：
struct tcf_proto {
/* Fast access part */
struct tcf_proto *next;
void *root;
int (*classify)(struct sk_buff*, struct tcf_proto*,
struct tcf_result *);
__be16 protocol;

/* All the rest */
u32 prio;
u32 classid;
struct Qdisc *q;
void *data;
struct tcf_proto_ops *ops;
};

2. 第1级分类器：tcf_proto分类器看不到分类器的具体实现（不同的分类器内部实现是完全不同），可以把这样的分类器称为1级分类器。

3. u32分类器：进行u32功能匹配的分类器，可以认为是第2级分类器。结构如下：
struct tc_u_knode
{
struct tc_u_knode *next;
u32 handle;
struct tc_u_hnode *ht_up;
struct tcf_exts exts;
#ifdef CONFIG_NET_CLS_IND
char indev[IFNAMSIZ];
#endif
u8 fshift;
struct tcf_result res;
struct tc_u_hnode *ht_down;
#ifdef CONFIG_CLS_U32_PERF
struct tc_u32_pcnt *pf;
#endif
#ifdef CONFIG_CLS_U32_MARK
struct tc_u32_mark mark;
#endif
struct tc_u32_sel sel;
};

4. u32哈希表：所有的u32分类器必须附属在一个u32哈希表上，u32哈希表最多可以有256个表项，每个表项都可以附属一个u32分类器链。结构如下：
struct tc_u_hnode
{
struct tc_u_hnode *next;
u32 handle;
u32 prio;
struct tc_u_common *tp_c;
int refcnt;
unsigned divisor;
struct tc_u_knode *ht[1];
};

5. 队列的u32哈希表链：为了便于管理和查找u32哈希表，内核将创建的u32哈希表加入队列的u32哈希表链。

（二）下面用关系图具体说明各种逻辑关系：
1）1级分类器和u32哈希表的逻辑关系图：

图1
图1涉及到1级分类器链头指针filter_list，是放在队列的私有数据中，不同种类的队列放置的位置是不同的，但是必须存在，当队列对数据包进行分类的时候，将会遍历这个分类器链。

2）u32哈希表和u32分类器的逻辑关系图：

图2
图2里面才真正出现了u32分类器，u32哈希表只是u32分类器的一个容器，只有在u32哈希中添加了u32分类器才能进行u32功能过滤。

3）队列和u32哈希表的逻辑关系图：

图3
所有的u32哈希表都会被加入这个哈希链中，但是，并不是所有的u32哈希表都关联到1级分类器中（如图1所示），如果u32哈希表被关联到了1级分类器（我们将这样的u32哈希称为第1级u32哈希表），那么在队列遍历分类器时，遍历流程就可以到达这个u32哈希表，也就是，可以到达这个u32哈希表内的u32分类器链。（我们可以将遍历1级分类器链称为第1级遍历，遍历第1级u32哈希表内的u32分类器链称为第2级遍历）
其它的u32哈希表是用户创建的，在1级遍历的时候，不会被遍历到。
可以看到1级u32哈希表是具有特殊地位的，它只能由内核来创建，它的哈希句柄也是由内核来分配。
为了保证逻辑和遍历过程的一致性，内核要求不能有相同优先级的1级分类器，由于1级u32哈希表和1级分类器是一一关联的，那么，1级u32哈希表的优先级也是不能相同。
如果要添加一个u32分类器，由于u32分类器必须附属在u32哈希表上，所以必须要有一个u32哈希表。这个u32哈希表可以是内核自动创建的，也可以是用户要求创建的。

有2种情况内核会自动创建1级u32哈希表：
1． 用户要求添加优先级是a的u32分类器，那么内核会自动创建一个优先级是a的1级分类器和一个1级u32哈希表（如果已经创建过了，就不会再创建），然后将这个u32分类器加入这个u32哈希表的唯一的一个分类器链中。
2． 用户要求添加一个优先级是a的u32哈希表，那么内核会自动创建一个优先级是a的1级分类器和一个1级u32哈希表（如果已经创建过了，就不会再创建），然后再创建u32哈希表，加入队列的u32哈希链中。

（三）以上就是u32分类器的逻辑架构（应该大体上是讲清楚了），下面是一些补充内容。
1.为什么1级分类器的优先级不能相同：我想是为了保证逻辑上的优先级和实际的流程上的优先级一致性，如果逻辑上两个分类器的优先级相同，那么实际匹配中到底是哪个分类器先进行分类呢，从实际的匹配流程看，分类器的优先级是不可能相同的。

2.有了以上的逻辑架构，就可以很好的理解为什么u32分类器的完整句柄是由3个数组成：H：B：I，其中H就是所在的u32哈希表的句柄，B就是哈希表项的偏移位置，I就是u32分类器的标识。（H是12bit的无符号整数，B是8bit的无符号整数，I是12bit的无符号整数，一共32bit）

3.u32分类器可以使用link功能将匹配流程转向其它的分类器链，如果在子分类器链中匹配成功，那么整个匹配流程结束，如果未匹配成功，返回原始的分类器链，继续想下匹配。

4.内核添加分类器的函数是：
/* Add/change/delete/get a filter node */
static int tc_ctl_tfilter(struct sk_buff *skb, struct nlmsghdr *n, void *arg)

5.不同种类的队列提供统一获取1级分类器链指针接口
struct Qdisc_class_ops {
struct tcf_proto **(*tcf_chain)(struct Qdisc *, unsigned long);就是这个接口
}
cbq的具体实现：
static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
{
struct cbq_sched_data *q = qdisc_priv(sch);
struct cbq_class *cl = (struct cbq_class *)arg;这里可以看到cbq的每个类都可以有分类器链
if (cl == NULL)
cl = &q->link;
return &cl->filter_list;
}

6.第1级分类器链遍历函数
int tc_classify_compat(struct sk_buff *skb, struct tcf_proto *tp,就是分类器链的指针地址
struct tcf_result *res)
{
__be16 protocol = skb->protocol;
int err = 0;
for (; tp; tp = tp->next) {
if ((tp->protocol == protocol ||
tp->protocol == htons(ETH_P_ALL)) &&
(err = tp->classify(skb, tp, res)) >= 0) {过滤操作
#ifdef CONFIG_NET_CLS_ACT
if (err != TC_ACT_RECLASSIFY && skb->tc_verd)
skb->tc_verd = SET_TC_VERD(skb->tc_verd, 0);
#endif
return err;
}
}
return -1;
}

2.6.35内核u32分类器逻辑架构分析 2011-8-11 5 /5