Linux内核中流量控制(12)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，
严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn
5.11.3 HTB一些操作函数5.11.3.1 转换函数/* TODO: maybe compute rate when size is too large .. or drop ? */// 将长度转换为令牌数static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate, int size){// 根据大小计算合适的槽位 int slot = size >> rate->rate.cell_log;// 如果超过了255, 限制为255 if (slot > 255) { cl->xstats.giants++; slot = 255; } return rate->data[slot];} // HTB哈希计算, 限制哈希结果小于16, 因为只有16个HASH表, 这个大小是定死的static inline int htb_hash(u32 h){#if HTB_HSIZE != 16#error "Declare new hash for your HTB_HSIZE"#endif h ^= h >> 8; /* stolen from cbq_hash */ h ^= h >> 4; return h & 0xf;}5.11.3.2 查询函数/* find class in global hash table using given handle */// 根据句柄handle查找HTB节点static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); struct hlist_node *p; struct htb_class *cl; if (TC_H_MAJ(handle) != sch->handle) return NULL;// 根据句柄计算哈希值, 然后遍历该哈希链表 hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {// 查找类别ID和句柄handle相等的HTB节点返回 if (cl->classid == handle) return cl; } return NULL;} 5.11.3.3 分类函数/** * htb_classify - classify a packet into class * * It returns NULL if the packet should be dropped or -1 if the packet * should be passed directly thru. In all other cases leaf class is returned. * We allow direct class selection by classid in priority. The we examine * filters in qdisc and in inner nodes (if higher filter points to the inner * node). If we end up with classid MAJOR:0 we enqueue the skb into special * internal fifo (direct). These packets then go directly thru. If we still * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull * then finish and return direct queue. */#define HTB_DIRECT (struct htb_class*)-1// 获取HTB类别结构的IDstatic inline u32 htb_classid(struct htb_class *cl){// 如果类别结构有效(非空而且不是直接通过), 返回其类别ID, 否则返回TC_H_UNSPEC// 表示没指定类别ID return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;}// HTB分类操作, 对数据包进行分类, 然后根据类别进行相关操作// 返回NULL表示没找到, 返回-1表示是直接通过(不分类)的数据包static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr){// HTB私有结构 struct htb_sched *q = qdisc_priv(sch); struct htb_class *cl;// 分类规则处理结果 struct tcf_result res;// 分类过滤规则表 struct tcf_proto *tcf; int result; /* allow to select class by setting skb->priority to valid classid; note that nfmark can be used too by attaching filter fw with no rules in it */// 如果数据包优先权值就等于流控节点和句柄handle, 属于根节点操作, 直接处理 if (skb->priority == sch->handle) return HTB_DIRECT; /* X:0 (direct flow) selected */// 查找和数据包优先权值对应的HTB叶子节点, 找到则返回 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0) return cl;// 以下处理是没有找到和skb->priority直接对应的HTB叶子节点, 应该说实际应用中大部分// 都是skb->priority为0的, 所以一般都会运行到这里 *qerr = NET_XMIT_BYPASS; tcf = q->filter_list;// 进行标准TC分类, 分类方法由TC命令定义的规则来实现 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {#ifdef CONFIG_NET_CLS_ACT// 定义了可对分类结果进行动作的内核选项的情况 switch (result) { case TC_ACT_QUEUED: case TC_ACT_STOLEN:// 发送成功 *qerr = NET_XMIT_SUCCESS;// 丢包 case TC_ACT_SHOT: return NULL; }#elif defined(CONFIG_NET_CLS_POLICE)// 没定义NET_CLS_ACT而定义了NET_CLS_POLICE的情况// 如果分类结果是TC_POLICE_SHOT, 属于HTB直接处理 if (result == TC_POLICE_SHOT) return HTB_DIRECT;#endif// 如果分类结果为空 if ((cl = (void *)res.class) == NULL) {// 如果分类结果的ID等于流控句柄, 直接处理 if (res.classid == sch->handle) return HTB_DIRECT; /* X:0 (direct flow) */// 再根据结果的类别ID查找HTB叶子节点, 找不到的话退出循环 if ((cl = htb_find(res.classid, sch)) == NULL) break; /* filter selected invalid classid */ }// 分类找到的情况, 如果是叶子节点, 直接返回 if (!cl->level) return cl; /* we hit leaf; return it */// 如果不是叶子节点,更新过滤表, 用该类别的内部过滤规则表重新搜索,// 从这里就可看出HTB的多层次结构, 由上层向下层细化 /* we have got inner class; apply inner filter chain */ tcf = cl->filter_list; }// 循环外是没找到分类的情况 /* classification failed; try to use default class */// 用缺省类别ID查找, 看是否定义了缺省类别 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);// 没找到或者是只是中间节点, 返回直接处理 if (!cl || cl->level) return HTB_DIRECT; /* bad default .. this is safe bet */ return cl;}5.11.3.4 激活类别/** * htb_activate - inserts leaf cl into appropriate active feeds * * Routine learns (new) priority of leaf and activates feed chain * for the prio. It can be called on already active leaf safely. * It also adds leaf into droplist. */// 激活类别结构, 将该类别节点作为数据包提供者, 而数据类别表提供是一个// 有序表, 以RB树形式实现static inline void htb_activate(struct htb_sched *q, struct htb_class *cl){ BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);// 如果类别的prio_activity参数为0才进行操作, 非0表示已经激活了 if (!cl->prio_activity) {// prio_activity是通过叶子节点的prio值来设置的, 至少是1, 最大是1<<7, 非0值// leaf.aprio保存当前的leaf.prio cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);// 进行实际的激活操作 htb_activate_prios(q, cl);// 根据leaf.aprio添加到指定的优先权位置的丢包链表 list_add_tail(&cl->un.leaf.drop_list, q->drops + cl->un.leaf.aprio); }}/** * htb_activate_prios - creates active classe's feed chain * * The class is connected to ancestors and/or appropriate rows * for priorities it is participating on. cl->cmode must be new * (activated) mode. It does nothing if cl->prio_activity == 0. */// 激活操作, 建立数据提供树// cl->prio_activity为0时就是一个空函数, 不过从前面看prio_activity似乎是不会为0的static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl){// 父节点 struct htb_class *p = cl->parent;// prio_activity是作为一个掩码, 可应该只有一位为1 long m, mask = cl->prio_activity;// 在当前模式是HTB_MAY_BORROW情况下进入循环, 某些情况下这些类别是可以激活的// 绝大多数情况p和mask的初始值应该都是非0值 while (cl->cmode == HTB_MAY_BORROW && p && mask) {// 备份mask值 m = mask; while (m) {// 掩码取反, 找第一个0位的位置, 也就是原来最低为1的位的位置// prio越小, 等级越高, 取数据包也是先从prio值小的节点取 int prio = ffz(~m);// 清除该位 m &= ~(1 << prio);// p是父节点, 所以inner结构肯定有效, 不会使用leaf结构的// 如果父节点的prio优先权的数据包的提供树已经存在, 在掩码中去掉该位 if (p->un.inner.feed[prio].rb_node) /* parent already has its feed in use so that reset bit in mask as parent is already ok */ mask &= ~(1 << prio);// 将该类别加到父节点的prio优先权提供数据包的节点树中 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio); }// 父节点的prio_activity或上mask中的置1位, 某位为1表示该位对应的优先权的// 数据可用 p->prio_activity |= mask;// 循环到上一层, 当前类别更新父节点, 父节点更新为祖父节点 cl = p; p = cl->parent; }// 如果cl是HTB_CAN_SEND模式, 将该类别添加到合适的ROW中// 此时的cl可能已经不是原来的cl了,而是原cl的长辈节点了 if (cl->cmode == HTB_CAN_SEND && mask) htb_add_class_to_row(q, cl, mask);// 如果cl是HTB_CANT_SEND模式则不进行任何操作了, 因为是阻塞状态} /** * htb_add_to_id_tree - adds class to the round robin list * * Routine adds class to the list (actually tree) sorted by classid. * Make sure that class is not already on such list for given prio. */static void htb_add_to_id_tree(struct rb_root *root, struct htb_class *cl, int prio){ struct rb_node **p = &root->rb_node, *parent = NULL;// RB树是有序表, 根据类别ID排序, 值大的到右节点, 小的到左节点// 循环, 查找树中合适的位置插入类别节点cl while (*p) { struct htb_class *c; parent = *p; c = rb_entry(parent, struct htb_class, node[prio]); if (cl->classid > c->classid) p = &parent->rb_right; else p = &parent->rb_left; }// 进行RB树的插入操作, RB树标准函数操作 rb_link_node(&cl->node[prio], parent, p); rb_insert_color(&cl->node[prio], root);}/** * htb_add_class_to_row - add class to its row * * The class is added to row at priorities marked in mask. * It does nothing if mask == 0. */static inline void htb_add_class_to_row(struct htb_sched *q, struct htb_class *cl, int mask){// 将cl层次对应的ROW的row_mask或上新的mask, 表示有对应prio的数据了 q->row_mask[cl->level] |= mask;// 循环mask, 将cl插入mask每一位对应的prio的树中 while (mask) {// prio是mask中最低为1的位的位置 int prio = ffz(~mask);// 清除该位 mask &= ~(1 << prio);// 添加到具体的RB树中 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio); }}5.11.3.4 关闭类别/** * htb_deactivate - remove leaf cl from active feeds * * Make sure that leaf is active. In the other words it can't be called * with non-active leaf. It also removes class from the drop list. */// 将类别叶子节点从活动的数据包提供树中去掉static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl){ BUG_TRAP(cl->prio_activity);// 关闭 htb_deactivate_prios(q, cl);// 类别的活性值prio_activity清零 cl->prio_activity = 0;// 将类别节点从drop表断开并重新初始化list结构 list_del_init(&cl->un.leaf.drop_list);}/** * htb_deactivate_prios - remove class from feed chain * * cl->cmode must represent old mode (before deactivation). It does * nothing if cl->prio_activity == 0. Class is removed from all feed * chains and rows. */static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl){// 类别节点的父节点 struct htb_class *p = cl->parent;// 类别结构的优先权活性值作为掩码, 如果是0的话本函数相当于空函数 long m, mask = cl->prio_activity;// 在当前模式是HTB_MAY_BORROW情况下进入循环,// 绝大多数情况p和mask的初始值应该都是非0值 while (cl->cmode == HTB_MAY_BORROW && p && mask) {// 备份掩码 m = mask;// 掩码清零 mask = 0; while (m) {// prio为m的第一个1值的位(取反后第一个0值的位) int prio = ffz(~m);// 去除该位 m &= ~(1 << prio);// 如果该类别prio对应的rb树是父节点中正在处理的 if (p->un.inner.ptr[prio] == cl->node + prio) { /* we are removing child which is pointed to from parent feed - forget the pointer but remember classid */// 将cl的类别ID保存到last_ptr_id中prio对应位置 p->un.inner.last_ptr_id[prio] = cl->classid;// 清空父节点指向rb根指针 p->un.inner.ptr[prio] = NULL; }// 类别节点从与prio相应rb树中断开 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);// 对已经空了的rb树保存其位置 if (!p->un.inner.feed[prio].rb_node) mask |= 1 << prio; }// 将已经空了的rb数掩码从父节点的活性值掩码中去掉 p->prio_activity &= ~mask;// 转到上一层处理 cl = p; p = cl->parent; }// 如果当前类别cl的模式是可以发送(无阻塞, 无借带宽), 将cl从ROW的相关树中断开 if (cl->cmode == HTB_CAN_SEND && mask) htb_remove_class_from_row(q, cl, mask);} /** * htb_remove_class_from_row - removes class from its row * * The class is removed from row at priorities marked in mask. * It does nothing if mask == 0. */// mask为0时等价于一个空函数static inline void htb_remove_class_from_row(struct htb_sched *q, struct htb_class *cl, int mask){ int m = 0; while (mask) {// prio为mask第一个1位的位置 int prio = ffz(~mask);// 去掉该位 mask &= ~(1 << prio);// 如果流控节点的该层该prio的rb树节点指向的是cl的prio的rb树节点, 更新到树的下一个rb节点 if (q->ptr[cl->level][prio] == cl->node + prio) htb_next_rb_node(q->ptr[cl->level] + prio);// 从ROW树中断开cl htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);// 如果该层该prio的rb树位空, 记录其位置 if (!q->row[cl->level][prio].rb_node) m |= 1 << prio; }// 在ROW掩码中将与rb树为空的那些prio位清空 q->row_mask[cl->level] &= ~m;}5.11.4 初始化static int htb_init(struct Qdisc *sch, struct rtattr *opt){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); struct rtattr *tb[TCA_HTB_INIT]; struct tc_htb_glob *gopt; int i;// 检查用户空间传过来的初始化数据的合法性 if (!opt || rtattr_parse_nested(tb, TCA_HTB_INIT, opt) || tb[TCA_HTB_INIT - 1] == NULL || RTA_PAYLOAD(tb[TCA_HTB_INIT - 1]) < sizeof(*gopt)) { printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n"); return -EINVAL; } gopt = RTA_DATA(tb[TCA_HTB_INIT - 1]);// 检查版本信息是否匹配 if (gopt->version != HTB_VER >> 16) { printk(KERN_ERR "HTB: need tc/htb version %d (minor is %d), you have %d\n", HTB_VER >> 16, HTB_VER & 0xffff, gopt->version); return -EINVAL; }// 初始化各链表和哈希表结构 INIT_LIST_HEAD(&q->root); for (i = 0; i < HTB_HSIZE; i++) INIT_HLIST_HEAD(q->hash + i); for (i = 0; i < TC_HTB_NUMPRIO; i++) INIT_LIST_HEAD(q->drops + i);// 初始化定时器 init_timer(&q->timer);// 初始化HTB流控节点的直接发送的数据包队列 skb_queue_head_init(&q->direct_queue);// 直接发送队列长度初始化为网卡设备的发送队列长度, 至少为2 q->direct_qlen = sch->dev->tx_queue_len; if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */ q->direct_qlen = 2;// HTB定时函数 q->timer.function = htb_timer; q->timer.data = (unsigned long)sch;#ifdef HTB_RATECM// 使用HTB进行流控的情况// 速率定时器初始化, 并开始定时 init_timer(&q->rttim); q->rttim.function = htb_rate_timer; q->rttim.data = (unsigned long)sch; q->rttim.expires = jiffies + HZ; add_timer(&q->rttim);#endif// 流量到定额转换参数, 是TC命令中的r2q参数 if ((q->rate2quantum = gopt->rate2quantum) < 1) q->rate2quantum = 1;// 缺省类别 q->defcls = gopt->defcls; return 0;}// HTB定时器函数static void htb_timer(unsigned long arg){ struct Qdisc *sch = (struct Qdisc *)arg;// 去掉流控节点的阻塞标志 sch->flags &= ~TCQ_F_THROTTLED; wmb();// 重新调度网卡 netif_schedule(sch->dev);}#ifdef HTB_RATECM// 递增试速率计算#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0// HTB速率定时器函数static void htb_rate_timer(unsigned long arg){// HTB流控节点 struct Qdisc *sch = (struct Qdisc *)arg;// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); struct hlist_node *p; struct htb_class *cl; /* lock queue so that we can muck with it */ spin_lock_bh(&sch->dev->queue_lock);// 定时一秒 q->rttim.expires = jiffies + HZ;// 再次添加定时器 add_timer(&q->rttim); /* scan and recompute one bucket at time */// 每次更新计算一个哈希表的数据 if (++q->recmp_bucket >= HTB_HSIZE) q->recmp_bucket = 0;// 更新recmp_bucket所对应的哈希链表中每个类别节点的字节和数据包流量率 hlist_for_each_entry(cl,p, q->hash + q->recmp_bucket, hlist) { RT_GEN(cl->sum_bytes, cl->rate_bytes); RT_GEN(cl->sum_packets, cl->rate_packets); } spin_unlock_bh(&sch->dev->queue_lock);}#endif5.11.5 丢包/* try to drop from each class (by prio) until one succeed */static unsigned int htb_drop(struct Qdisc *sch){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); int prio;// 遍历各个级别的丢包链表, 最先操作的是7号链表, 最后操作的是0号链表 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) { struct list_head *p;// 遍历链表 list_for_each(p, q->drops + prio) {// 类别结构 struct htb_class *cl = list_entry(p, struct htb_class, un.leaf.drop_list); unsigned int len;// 如果该类别的叶子节点流控定义了丢包操作, 进行相应丢包操作 if (cl->un.leaf.q->ops->drop && (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {// 丢包操作成功 sch->q.qlen--;// 子流控节点为空, 停止该类别 if (!cl->un.leaf.q->q.qlen) htb_deactivate(q, cl); return len; } } } return 0;} 5.11.6 复位/* reset all classes *//* always caled under BH & queue lock */static void htb_reset(struct Qdisc *sch){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); int i;// 遍历所有哈希表 for (i = 0; i < HTB_HSIZE; i++) { struct hlist_node *p; struct htb_class *cl;// 遍历链表中每个类别结构 hlist_for_each_entry(cl, p, q->hash + i, hlist) { if (cl->level)// 中间节点, 直接清零操作 memset(&cl->un.inner, 0, sizeof(cl->un.inner)); else {// 叶子节点, 复位内部流控结构 if (cl->un.leaf.q) qdisc_reset(cl->un.leaf.q);// 重新初始化丢弃链表 INIT_LIST_HEAD(&cl->un.leaf.drop_list); } cl->prio_activity = 0; cl->cmode = HTB_CAN_SEND; } }// 去掉阻塞标志 sch->flags &= ~TCQ_F_THROTTLED;// 删除定时器 del_timer(&q->timer);// 删除当前直接发送的数据包队列中的所有数据包 __skb_queue_purge(&q->direct_queue);// 参数清零 sch->q.qlen = 0; memset(q->row, 0, sizeof(q->row)); memset(q->row_mask, 0, sizeof(q->row_mask)); memset(q->wait_pq, 0, sizeof(q->wait_pq)); memset(q->ptr, 0, sizeof(q->ptr));// 初始化丢弃队列 for (i = 0; i < TC_HTB_NUMPRIO; i++) INIT_LIST_HEAD(q->drops + i);} 5.11.7 释放 /* always caled under BH & queue lock */static void htb_destroy(struct Qdisc *sch){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch);// 删除定时器 del_timer_sync(&q->timer);#ifdef HTB_RATECM del_timer_sync(&q->rttim);#endif /* This line used to be after htb_destroy_class call below and surprisingly it worked in 2.4. But it must precede it because filter need its target class alive to be able to call unbind_filter on it (without Oops). */// 释放过滤器规则表 htb_destroy_filters(&q->filter_list);// 遍历当前的HTB类别树, 释放类别结构 while (!list_empty(&q->root)) htb_destroy_class(sch, list_entry(q->root.next, struct htb_class, sibling));// 释放直接处理的数据队列 __skb_queue_purge(&q->direct_queue);} 5.11.8 输出HTB参数 static int htb_dump(struct Qdisc *sch, struct sk_buff *skb){// HTB私有数据结构 struct htb_sched *q = qdisc_priv(sch); unsigned char *b = skb->tail; struct rtattr *rta; struct tc_htb_glob gopt; spin_lock_bh(&sch->dev->queue_lock);// 直接发送的数据包数量 gopt.direct_pkts = q->direct_pkts;// HTB版本号 gopt.version = HTB_VER;// 类别转额度 gopt.rate2quantum = q->rate2quantum;// 缺省类别 gopt.defcls = q->defcls; gopt.debug = 0;// 返回数据在数据包中的具体位置 rta = (struct rtattr *)b; RTA_PUT(skb, TCA_OPTIONS, 0, NULL);// 填入选项参数 RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt); rta->rta_len = skb->tail - b; spin_unlock_bh(&sch->dev->queue_lock); return skb->len;rtattr_failure: spin_unlock_bh(&sch->dev->queue_lock); skb_trim(skb, skb->tail - skb->data); return -1;} ...... 待续 ......