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

本文档的Copyleft归wwwlkk所有，使用GPL发布，可以自由拷贝、转载，转载时请保持文档的完整性，严禁用于任何商业用途。 E-mail: 来源: /?business&aid=6&un=wwwlkk#7liux2.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 *);_be16protocol;/* All the rest */u32prio;u32classid;struct Qdisc*q;void*data;struct tcf_proto_ops*ops;2. 第1级分类器：tcf_proto分类器看不到分类器的具体实现（不同的分类器内部实现是完全不同），可以把这样的分类器称为1级分类器。3. u32分类器：进行u32功能匹配的分类器，可以认为是第2级分类器。结构如下：struct tc_u_knodestruct tc_u_knode*next;u32handle;struct tc_u_hnode*ht_up;struct tcf_extsexts;#ifdef CONFIG_NET_CLS_INDchar indevIFNAMSIZ;#endifu8fshift;struct tcf_resultres;struct tc_u_hnode*ht_down;#ifdef CONFIG_CLS_U32_PERFstruct tc_u32_pcnt*pf;#endif#ifdef CONFIG_CLS_U32_MARKstruct tc_u32_markmark;#endifstruct tc_u32_selsel;4. u32哈希表：所有的u32分类器必须附属在一个u32哈希表上，u32哈希表最多可以有256个表项，每个表项都可以附属一个u32分类器链。结构如下：struct tc_u_hnodestruct tc_u_hnode*next;u32handle;u32prio;struct tc_u_common*tp_c;intrefcnt;unsigneddivisor;struct tc_u_knode*ht1;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)