Linux内核中流量控制(21)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn
7.12 routeroute分类是根据数据包的路由信息进行分类的, 路由信息中会带tclassid参数用于分类, 代码在net/sched/cls_route.c中定义, 只支持IPV4。7.12.1 数据结构和过滤器操作结构// route 快速映射结构, 相当于分类结果的cachestruct route4_fastmap{ struct route4_filter *filter; u32 id; int iif;};// route头结构struct route4_head{// 16个快速映射结构 struct route4_fastmap fastmap[16];// 257个bucket链表 struct route4_bucket *table[256+1];};struct route4_bucket{ /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */ struct route4_filter *ht[16+16+1];};// route过滤器结构struct route4_filter{// 链表中的下一项 struct route4_filter *next;// ID u32 id;// 网卡索引号 int iif;// 分类结构 struct tcf_result res;// TCF扩展 struct tcf_exts exts;// 句柄 u32 handle;// 所在的bucket struct route4_bucket *bkt;};#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))static struct tcf_ext_map route_ext_map = { .police = TCA_ROUTE4_POLICE, .action = TCA_ROUTE4_ACT};static struct tcf_ext_map tcindex_ext_map = { .police = TCA_TCINDEX_POLICE, .action = TCA_TCINDEX_ACT}; // 分类操作结构static struct tcf_proto_ops cls_route4_ops = { .next = NULL, .kind = "route", .classify = route4_classify, .init = route4_init, .destroy = route4_destroy, .get = route4_get, .put = route4_put, .change = route4_change, .delete = route4_delete, .walk = route4_walk, .dump = route4_dump, .owner = THIS_MODULE,};7.12.2 一些哈希函数// 快速映射表位置哈希static __inline__ int route4_fastmap_hash(u32 id, int iif){// 取ID的低4位, 结果在0~15之间 return id&0xF;}// 进入方向路由哈希static __inline__ int route4_hash_to(u32 id){// 取ID的低8位, 结果在0~255之间 return id&0xFF;}// 来源方向路由哈希static __inline__ int route4_hash_from(u32 id){// 取ID的16~19位, 结果在0~15之间 return (id>>16)&0xF;}// 网卡索引号哈希static __inline__ int route4_hash_iif(int iif){// 取网卡索引号的16~19位再加16, 结果在16~31之间 return 16 + ((iif>>16)&0xF);}// 外卡哈希, 返回外卡哈希表号:32static __inline__ int route4_hash_wild(void){ return 32;}// 插入哈希, 从哈希表中删除时计算static inline u32 to_hash(u32 id){// 取低8位 u32 h = id&0xFF;// 第15位为1的话哈希值增加256 if (id&0x8000) h += 256;// 结果范围应该是0~511 return h;}// 来源哈希, 插入哈希表时计算static inline u32 from_hash(u32 id){// 高16位清零 id &= 0xFFFF;// 低16位全1的话返回32, 外卡值 if (id == 0xFFFF) return 32;// 如果第15位为0 if (!(id & 0x8000)) {// 超过255的话返回256 if (id > 255) return 256;// 否则返回低4位, 范围为0~15 return id&0xF; }// 第15位为1// 返回低4位加16, 范围为16~31 return 16 + (id&0xF);}7.12.3 初始化// 空函数static int route4_init(struct tcf_proto *tp){ return 0;} 7.12.4 分类// 分类结果处理宏#define ROUTE4_APPLY_RESULT() \{ \// 要返回的分类结果 *res = f->res; \ if (tcf_exts_is_available(&f->exts)) { \// 执行TCF扩展操作 int r = tcf_exts_exec(skb, &f->exts, res); \ if (r < 0) { \// 操作失败, 不需要将结果进cache, 继续循环 dont_cache = 1; \ continue; \ } \ return r; \ } else if (!dont_cache) \// 将结果进cache, route4_set_fastmap(head, id, iif, f); \ return 0; \}static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res){// route头节点 struct route4_head *head = (struct route4_head*)tp->root; struct dst_entry *dst; struct route4_bucket *b; struct route4_filter *f; u32 id, h; int iif, dont_cache = 0;// 如果数据包路由项为空, 分类失败 if ((dst = skb->dst) == NULL) goto failure;// 类别ID id = dst->tclassid;// 如果头节点空, 用老方法分类 if (head == NULL) goto old_method;// 网卡索引号 iif = ((struct rtable*)dst)->fl.iif;// 根据ID和网卡索引号计算快速映射哈希值 h = route4_fastmap_hash(id, iif);// 如果快速映射表中元素和此ID和网卡匹配, 而且过滤结构有效 if (id == head->fastmap[h].id && iif == head->fastmap[h].iif && (f = head->fastmap[h].filter) != NULL) {// 如果是错误分类, 返回失败 if (f == ROUTE4_FAILURE) goto failure;// 否则返回分类结构, 分类成功 *res = f->res; return 0; }// 单独根据ID计算路由to哈希值 h = route4_hash_to(id);restart:// 如果该哈希值对应的表有效 if ((b = head->table[h]) != NULL) {// 根据ID哈希, 遍历合适的链表 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)// 如果ID匹配, 成功返回 if (f->id == id) ROUTE4_APPLY_RESULT();// 根据网卡索引哈希, 遍历合适链表 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)// 如果网卡索引匹配, 成功返回 if (f->iif == iif) ROUTE4_APPLY_RESULT();// 还没找到, 如果外卡链表存在的话, 也成功返回 for (f = b->ht[route4_hash_wild()]; f; f = f->next) ROUTE4_APPLY_RESULT(); }// 哈希值对应的表为空的情况// 如果哈希值太小, 更新其值后重新查找 if (h < 256) { h = 256; id &= ~0xFFFF; goto restart; }// 否则分类失败// 如果需要保存在cache中, 将ID和网卡索引号保存到快速索引表中 if (!dont_cache) route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);failure: return -1;old_method:// 老分类方法// 如果ID有效, 而且ID高16位为0或高16位和handle的高16位相同 if (id && (TC_H_MAJ(id) == 0 || !(TC_H_MAJ(id^tp->q->handle)))) {// 将ID作为类别ID返回 res->classid = id; res->class = 0; return 0; } return -1;} 7.12.5 释放 static void route4_destroy(struct tcf_proto *tp){// 将根节点换出来准备释放 struct route4_head *head = xchg(&tp->root, NULL); int h1, h2;// 如果根节点空, 直接返回 if (head == NULL) return;// 遍历257个表 for (h1=0; h1<=256; h1++) { struct route4_bucket *b;// 如果链表头非空 if ((b = head->table[h1]) != NULL) {// 遍历bucket结构的33个filter链表 for (h2=0; h2<=32; h2++) { struct route4_filter *f;// 遍历每个链表 while ((f = b->ht[h2]) != NULL) {// 断开节点 b->ht[h2] = f->next;// 删除filter route4_delete_filter(tp, f); } }// 释放bucket kfree(b); } }// 释放根节点 kfree(head);}static inline voidroute4_delete_filter(struct tcf_proto *tp, struct route4_filter *f){// 解除绑定 tcf_unbind_filter(tp, &f->res);// 释放TCF扩展结构 tcf_exts_destroy(tp, &f->exts);// 释放过滤器空间 kfree(f);}7.12.6 获取// 根据handle查找route4_filter结构static unsigned long route4_get(struct tcf_proto *tp, u32 handle){// 根节点 struct route4_head *head = (struct route4_head*)tp->root; struct route4_bucket *b; struct route4_filter *f; unsigned h1, h2;// 根节点空的话返回0 if (!head) return 0;// 根据handle计算哈希值 h1 = to_hash(handle);// 超过256的话返回0 if (h1 > 256) return 0;// 根据handle的高16位计算哈希找bucket h2 = from_hash(handle>>16);// 超过32的话返回0 if (h2 > 32) return 0;// 如果bucket非空 if ((b = head->table[h1]) != NULL) {// 遍历链表 for (f = b->ht[h2]; f; f = f->next)// 查找handle匹配的filter节点返回 if (f->handle == handle) return (unsigned long)f; } return 0;} 7.12.7 放下// 空函数static void route4_put(struct tcf_proto *tp, unsigned long f){}7.12.8 修改// 增加和修改tc filter规则时调用static int route4_change(struct tcf_proto *tp, unsigned long base, u32 handle, struct rtattr **tca, unsigned long *arg){// 根节点 struct route4_head *head = tp->root; struct route4_filter *f, *f1, **fp; struct route4_bucket *b;// 输入的选项参数 struct rtattr *opt = tca[TCA_OPTIONS-1]; struct rtattr *tb[TCA_ROUTE4_MAX]; unsigned int h, th; u32 old_handle = 0; int err;// 选项参数空, 返回 if (opt == NULL) return handle ? -EINVAL : 0;// 解析选项参数, 结果保存到tb数组 if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0) return -EINVAL;// 过滤器参数非空, 是修改操作 if ((f = (struct route4_filter*)*arg) != NULL) {// 比较handle是否正确 if (f->handle != handle && handle) return -EINVAL;// 如果已经在某bucket的链表里, 保存handle if (f->bkt) old_handle = f->handle;// 设置过滤器参数, 函数最后一个参数为0表示是修改 err = route4_set_parms(tp, base, f, handle, head, tb, tca[TCA_RATE-1], 0);// 操作失败, 返回错误 if (err < 0) return err;// 成功则跳转重新插入, 将f从原链表中断开的操作也在后面进行 goto reinsert; }// 过滤器参数空, 是新建操作 err = -ENOBUFS; if (head == NULL) {// 如果根节点为空, 分配更节点空间 head = kzalloc(sizeof(struct route4_head), GFP_KERNEL); if (head == NULL) goto errout; tcf_tree_lock(tp);// 将其作为tcf_proto的根参数指针 tp->root = head; tcf_tree_unlock(tp); }// 分配新的过滤器空间 f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL); if (f == NULL) goto errout;// 设置过滤器参数, 函数最后一个参数为1表示是新建 err = route4_set_parms(tp, base, f, handle, head, tb, tca[TCA_RATE-1], 1);// 失败的话转失败处理 if (err < 0) goto errout;reinsert:// 重新插入操作, 将过滤器f插入合适的bucket链表, 对于修改操作, 因为参数变了,// 所以要重新插入到合适的bucket中// 计算from哈希 h = from_hash(f->handle >> 16);// 遍历相应的哈希链表查找插入位置, 该链表是按handle值排序, 小的在前, 大的在后 for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next) if (f->handle < f1->handle) break;// 将新节点插入链表 f->next = f1; tcf_tree_lock(tp); *fp = f;// 如果handle发生了变化, 需要将该过滤器从原来的链表中断开// 不过找哪个哈希表的过程确挺费解的 if (old_handle && f->handle != old_handle) {// 计算老handle的to哈希 th = to_hash(old_handle);// 计算老handle高16位的from哈希 h = from_hash(old_handle >> 16);// to哈希链表非空 if ((b = head->table[th]) != NULL) {// 遍历链表 for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {// 查找过滤器节点 if (*fp == f) {// 从链表中断开 *fp = f->next; break; } } } } tcf_tree_unlock(tp);// 复位快速映射数组, 全部清零 route4_reset_fastmap(tp->q->dev, head, f->id);// 返回f的地址 *arg = (unsigned long)f; return 0;errout: kfree(f); return err;}// 设置过滤器参数static int route4_set_parms(struct tcf_proto *tp, unsigned long base, struct route4_filter *f, u32 handle, struct route4_head *head, struct rtattr **tb, struct rtattr *est, int new){ int err; u32 id = 0, to = 0, nhandle = 0x8000; struct route4_filter *fp; unsigned int h1; struct route4_bucket *b; struct tcf_exts e;// TCF扩展验证 err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map); if (err < 0) return err; err = -EINVAL;// 判断类别ID是否合法 if (tb[TCA_ROUTE4_CLASSID-1]) if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32)) goto errout;// 解析TO参数 if (tb[TCA_ROUTE4_TO-1]) { if (new && handle & 0x8000) goto errout; if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32)) goto errout; to = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);// TO参数不能超过255 if (to > 0xFF) goto errout;// 将TO参数作为nhandle的低0~8位 nhandle = to; }// 如果存在FROM参数 if (tb[TCA_ROUTE4_FROM-1]) {// 解析FROM参数 if (tb[TCA_ROUTE4_IIF-1]) goto errout; if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32)) goto errout; id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);// FROM参数也不能超过255 if (id > 0xFF) goto errout;// 将FROM参数作为nhandle的16~23位 nhandle |= id << 16; } else if (tb[TCA_ROUTE4_IIF-1]) {// 否则如果存在网卡参数 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32)) goto errout; id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);// 网卡参数不能超过0x7ffff if (id > 0x7FFF) goto errout;// 将网卡参数作为nhandle的16~30位, 同时第15位置1 nhandle |= (id | 0x8000) << 16; } else// 否则nhandle高16位全1 nhandle |= 0xFFFF << 16; if (handle && new) {// 如果是新建而且handle非0// 更新nhandle, 前面的计算全部费了 nhandle |= handle & 0x7F00;// 对于新建的filter, handle只能是在16~22位可以为1 if (nhandle != handle) goto errout; }// 计算新handle的to哈希 h1 = to_hash(nhandle);// 如果对应哈希值的bucket为空 if ((b = head->table[h1]) == NULL) { err = -ENOBUFS;// 分配bucket空间 b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL); if (b == NULL) goto errout; tcf_tree_lock(tp);// 赋值到bucket头数组 head->table[h1] = b; tcf_tree_unlock(tp); } else {// 否则计算高16位的from哈希 unsigned int h2 = from_hash(nhandle >> 16); err = -EEXIST;// 遍历bucket中相应的链表, 查找是否已经有相同的handle, 找到的话返回错误 for (fp = b->ht[h2]; fp; fp = fp->next) if (fp->handle == f->handle) goto errout; } tcf_tree_lock(tp);// 如果TO参数存在的话, ID取TO参数 if (tb[TCA_ROUTE4_TO-1]) f->id = to;// 如果FROM参数存在的话, ID放到ID的高16位 if (tb[TCA_ROUTE4_FROM-1]) f->id = to | id<<16; else if (tb[TCA_ROUTE4_IIF-1]) f->iif = id;// 过滤器的新handle f->handle = nhandle;// 过滤器所在的bucket f->bkt = b; tcf_tree_unlock(tp);// 设置类别ID, 绑定过滤器 if (tb[TCA_ROUTE4_CLASSID-1]) { f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]); tcf_bind_filter(tp, &f->res, base); }// TCF扩展修改操作 tcf_exts_change(tp, &f->exts, &e); return 0;errout: tcf_exts_destroy(tp, &e); return err;} 7.12.9 删除static int route4_delete(struct tcf_proto *tp, unsigned long arg){// 更节点 struct route4_head *head = (struct route4_head*)tp->root;// f是要删除的节点 struct route4_filter **fp, *f = (struct route4_filter*)arg; unsigned h = 0; struct route4_bucket *b; int i;// 根节点或要删除的节点为空, 参数错误 if (!head || !f) return -EINVAL;// 获取过滤器节点的handle和所在的bucket h = f->handle; b = f->bkt;// 遍历该bucket的链表 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {// 查找f节点 if (*fp == f) {// 找到 tcf_tree_lock(tp);// 将该节点从链表中断开 *fp = f->next; tcf_tree_unlock(tp);// 复位快速映射表, 是将fastmap数组全部清零了, 好象是连坐一样 route4_reset_fastmap(tp->q->dev, head, f->id);// 释放该过滤器f route4_delete_filter(tp, f); /* Strip tree */// 检查该f所在bucket是否已经空了 for (i=0; i<=32; i++) if (b->ht[i]) return 0; /* OK, session has no flows */// 如果空了, 就准备删除该bucket tcf_tree_lock(tp);// 哈希表头置空 head->table[to_hash(h)] = NULL; tcf_tree_unlock(tp);// 释放bucket kfree(b); return 0; } } return 0;}7.12.10 遍历static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg){// 根节点 struct route4_head *head = tp->root; unsigned h, h1;// 根节点空的话设置停止标志 if (head == NULL) arg->stop = 1;// 设置了停止标志时直接返回 if (arg->stop) return;// 遍历257个bucket for (h = 0; h <= 256; h++) { struct route4_bucket *b = head->table[h];// 如果该bucket非空 if (b) {// 遍历33个链表 for (h1 = 0; h1 <= 32; h1++) { struct route4_filter *f;// 遍历链表 for (f = b->ht[h1]; f; f = f->next) {// 检查是否是需要跳过的节点 if (arg->count < arg->skip) { arg->count++; continue; }// 执行单节点处理函数 if (arg->fn(tp, (unsigned long)f, arg) < 0) {// 失败的话设置停止标志, 返回 arg->stop = 1; return; } arg->count++; } } } }} 7.12.11 输出static int route4_dump(struct tcf_proto *tp, unsigned long fh, struct sk_buff *skb, struct tcmsg *t){// 要输出的route过滤器节点 struct route4_filter *f = (struct route4_filter*)fh;// skb数据包缓冲区定位 unsigned char *b = skb->tail; struct rtattr *rta; u32 id;// 过滤器空, 返回 if (f == NULL) return skb->len;// 填写handle t->tcm_handle = f->handle;// 结构定位 rta = (struct rtattr*)b; RTA_PUT(skb, TCA_OPTIONS, 0, NULL);// 输出ROUTE_TO if (!(f->handle&0x8000)) { id = f->id&0xFF; RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id); } if (f->handle&0x80000000) {// handle最高位为1 if ((f->handle>>16) != 0xFFFF)// handle高16非全1的话输出网卡索引号 RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif); } else {// handle最高位为0// ID高16位是ROUTE_FROM id = f->id>>16; RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id); }// 类别ID if (f->res.classid) RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);// TCF扩展输出 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0) goto rtattr_failure; rta->rta_len = skb->tail - b;// TCF扩展统计 if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0) goto rtattr_failure; return skb->len;rtattr_failure: skb_trim(skb, b - skb->data); return -1;} 7.13 小结分类操作结构分析告一段落, 基本的特点就是对节点操作时都不直接操作, 而是先在链表中查找确认后才操作, 这也是sched各种代码的共同特征, 为什么不能直接操作呢? 难道是怕在get操作时获取的结构指针在后来操作时已经被删除了? 不过的确这些结构中不是所有都有引用计数的原子操作; 另外一点就是handle的取值, 每个操作结构所对应的handle各个位的定义是不同, 同时进行各种哈希操作也不同, 这些都需要注意, 不过在此不仔细比较各类型的handle的不同了, 有兴趣的自己去分析。...... 待续 ......