Linux内核中流量控制(7)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn
5.7 RED(Random Early Detection queue)RED算法由Sally Floyd和Van Jacobson提出, 论文为"Random Early Detection Gateways for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking.基本算法:对新数据包计算平均队列长度:平均长度avg=(1-W) * avg + W*当前队列长度 W是参数, 取值为1/(2^Wlog), Wlog可配置, W越小, 平滑能力越强. 算法中两个阈值: th_min和th_max, 这两个参数可配置当avg > th_max时, 该新包被丢弃;当avg < th_min时, 该新包允许通过;当th_min <= avg <= th_max时, 计算概率: Pb = max_P * (avg - th_min)/(th_max-th_min)然后按此概率丢包, max_P为一小数, 通常为0.01, 0.02等, 一般在算法中通过右移操作来实现: max_P = (qth_max-qth_min)>>PlogPlog为可配置参数5.7.1 RED操作结构定义// RED算法参数struct red_parms{ /* Parameters */// 最小队列长度 u32 qth_min; /* Min avg length threshold: A scaled */// 最大队列长度 u32 qth_max; /* Max avg length threshold: A scaled */// 最大休眠时间 u32 Scell_max;// 保存随机掩码 u32 Rmask; /* Cached random mask, see red_rmask */// u8 Scell_log;// Wlog, Plog参数含义如上所示 u8 Wlog; /* log(W) */ u8 Plog; /* random number bits */// 256个元素 u8 Stab[RED_STAB_SIZE]; /* Variables */// 以下的参数是在处理过程中会改变的参数// 从上次随机数产生时的处理的数据包数 int qcount; /* Number of packets since last random number generation */// 缓存的随机数 u32 qR; /* Cached random number */// 平均队列长度 unsigned long qavg; /* Average queue length: A scaled */// 当前休眠起始时间 psched_time_t qidlestart; /* Start of current idle period */};// RED私有数据struct red_sched_data{// 最大队列长度, 这是硬限制 u32 limit; /* HARD maximal queue length */// 标志 unsigned char flags;// RED算法参数 struct red_parms parms;// RED统计值 struct red_stats stats; struct Qdisc *qdisc;};// RED流控操作结构static struct Qdisc_ops red_qdisc_ops = { .id = "red", .priv_size = sizeof(struct red_sched_data), .cl_ops = &red_class_ops, .enqueue = red_enqueue, .dequeue = red_dequeue, .requeue = red_requeue, .drop = red_drop, .init = red_init, .reset = red_reset, .destroy = red_destroy, .change = red_change, .dump = red_dump, .dump_stats = red_dump_stats, .owner = THIS_MODULE,};// RED类别操作结构static struct Qdisc_class_ops red_class_ops = { .graft = red_graft, .leaf = red_leaf, .get = red_get, .put = red_put, .change = red_change_class, .delete = red_delete, .walk = red_walk, .tcf_chain = red_find_tcf, .dump = red_dump_class,}; 5.7.2 RED一些基本操作函数在include/net/red.h中定义// 返回Plog对应RED掩码, 和网络掩码不同,RED掩码值是从低位开始算的// 掩码值位2^Plog-1, , Plog超过31后就和31相同static inline u32 red_rmask(u8 Plog){ return Plog < 32 ? ((1 << Plog) - 1) : ~0UL;}// 设置RED参数, 平均长度阈值的最大最小值等static inline void red_set_parms(struct red_parms *p, u32 qth_min, u32 qth_max, u8 Wlog, u8 Plog, u8 Scell_log, u8 *stab){ /* Reset average queue length, the value is strictly bound * to the parameters below, reseting hurts a bit but leaving * it might result in an unreasonable qavg for a while. --TGR */ p->qavg = 0;// 队列元素统计 p->qcount = -1;// 内部平均长度阈值的最大最小值为设置值的2^Wlog倍 p->qth_min = qth_min << Wlog; p->qth_max = qth_max << Wlog; p->Wlog = Wlog; p->Plog = Plog;// 随机掩码 p->Rmask = red_rmask(Plog); p->Scell_log = Scell_log;// 最大休眠时间 p->Scell_max = (255 << Scell_log);// stab memcpy(p->Stab, stab, sizeof(p->Stab));}// 算法是否在休眠状态, 也就是看qidlestart是否为0, qidlestart非0表示正在休眠static inline int red_is_idling(struct red_parms *p){ return !PSCHED_IS_PASTPERFECT(p->qidlestart);}// RED休眠, 将p->qidlestart设置为当前时间static inline void red_start_of_idle_period(struct red_parms *p){ PSCHED_GET_TIME(p->qidlestart);}// RED停止休眠, 将p->qidlestart设置清零static inline void red_end_of_idle_period(struct red_parms *p){ PSCHED_SET_PASTPERFECT(p->qidlestart);}// RED算法重新启动static inline void red_restart(struct red_parms *p){// RED数值清零, red_end_of_idle_period(p); p->qavg = 0; p->qcount = -1;}// 从休眠恢复后重新计算队列平均值static inline unsigned long red_calc_qavg_from_idle_time(struct red_parms *p){ psched_time_t now; long us_idle; int shift;// 获取当前时间 PSCHED_GET_TIME(now);// 计算当前时间与休眠时的时间差, 也就是计算休眠了多少时间// p->Scell_max是休眠时间上限 us_idle = PSCHED_TDIFF_SAFE(now, p->qidlestart, p->Scell_max); /* * The problem: ideally, average length queue recalcultion should * be done over constant clock intervals. This is too expensive, so * that the calculation is driven by outgoing packets. * When the queue is idle we have to model this clock by hand. * * SF+VJ proposed to "generate": * * m = idletime / (average_pkt_size / bandwidth) * * dummy packets as a burst after idle time, i.e. * * p->qavg *= (1-W)^m * * This is an apparently overcomplicated solution (f.e. we have to * precompute a table to make this calculation in reasonable time) * I believe that a simpler model may be used here, * but it is field for experiments. */// 根据休眠数和Scell_log计算索引值获取stab数组中的偏移值 shift = p->Stab[(us_idle >> p->Scell_log) & RED_STAB_MASK]; if (shift)// 偏移值非0, 当前平均队列值左移后返回 return p->qavg >> shift; else { /* Approximate initial part of exponent with linear function: * * (1-W)^m ~= 1-mW + ... * * Seems, it is the best solution to * problem of too coarse exponent tabulation. */// 重新计算休眠时间 us_idle = (p->qavg * (u64)us_idle) >> p->Scell_log;// 如果休眠时间数值小于队列长度一半 if (us_idle < (p->qavg >> 1))// 返回队列长度减休眠时间 return p->qavg - us_idle; else// 否则返回队列长度的一半 return p->qavg >> 1; }}// 非休眠情况下计算队列平均值static inline unsigned long red_calc_qavg_no_idle_time(struct red_parms *p, unsigned int backlog){ /* * NOTE: p->qavg is fixed point number with point at Wlog. * The formula below is equvalent to floating point * version: * * qavg = qavg*(1-W) + backlog*W; * * --ANK (980924) */ return p->qavg + (backlog - (p->qavg >> p->Wlog));}// RED计算滑动队列平均值static inline unsigned long red_calc_qavg(struct red_parms *p, unsigned int backlog){// 分活动状态和非活动状态, 分别计算 if (!red_is_idling(p)) return red_calc_qavg_no_idle_time(p, backlog); else return red_calc_qavg_from_idle_time(p);}// 生成RED随机数static inline u32 red_random(struct red_parms *p){ return net_random() & p->Rmask;}// 概率随机决定是否丢包static inline int red_mark_probability(struct red_parms *p, unsigned long qavg){ /* The formula used below causes questions. OK. qR is random number in the interval 0..Rmask i.e. 0..(2^Plog). If we used floating point arithmetics, it would be: (2^Plog)*rnd_num, where rnd_num is less 1. Taking into account, that qavg have fixed point at Wlog, and Plog is related to max_P by max_P = (qth_max-qth_min)/2^Plog; two lines below have the following floating point equivalent: max_P*(qavg - qth_min)/(qth_max-qth_min) < rnd/qcount Any questions? --ANK (980924) */// 根据当前队列平均值计算出一个值是否小于随机数qR来实现概率丢包 return !(((qavg - p->qth_min) >> p->Wlog) * p->qcount < p->qR);}enum { RED_BELOW_MIN_THRESH, RED_BETWEEN_TRESH, RED_ABOVE_MAX_TRESH,};// 将当前队列平均值与阈值进行比较static inline int red_cmp_thresh(struct red_parms *p, unsigned long qavg){// 小于低阈值 if (qavg < p->qth_min) return RED_BELOW_MIN_THRESH;// 不小于高阈值 else if (qavg >= p->qth_max) return RED_ABOVE_MAX_TRESH; else// 高低阈值之间 return RED_BETWEEN_TRESH;}enum {// 放行 RED_DONT_MARK,// 根据概率标记 RED_PROB_MARK,// 标记 RED_HARD_MARK,};// RED动作判定static inline int red_action(struct red_parms *p, unsigned long qavg){// 将当前平均队列值与阈值进行比较 switch (red_cmp_thresh(p, qavg)) { case RED_BELOW_MIN_THRESH:// 低于低阈值, 放行 p->qcount = -1; return RED_DONT_MARK; case RED_BETWEEN_TRESH:// 高低之间, 按概率标记 if (++p->qcount) {// 是否根据概率标记 if (red_mark_probability(p, qavg)) {// 标记 p->qcount = 0; p->qR = red_random(p); return RED_PROB_MARK; } } else p->qR = red_random(p);// 不标记 return RED_DONT_MARK; case RED_ABOVE_MAX_TRESH:// 超过高阈值, 直接标记 p->qcount = -1; return RED_HARD_MARK; } BUG(); return RED_DONT_MARK;}5.7.3 初始化static int red_init(struct Qdisc* sch, struct rtattr *opt){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 内部Qdisc初始化为noop_qdisc q->qdisc = &noop_qdisc;// 调用change函数进行初始化 return red_change(sch, opt);}5.7.4 参数修改static int red_change(struct Qdisc *sch, struct rtattr *opt){ struct red_sched_data *q = qdisc_priv(sch); struct rtattr *tb[TCA_RED_MAX]; struct tc_red_qopt *ctl; struct Qdisc *child = NULL;// 检查数据范围是否合法 if (opt == NULL || rtattr_parse_nested(tb, TCA_RED_MAX, opt)) return -EINVAL; if (tb[TCA_RED_PARMS-1] == NULL || RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) || tb[TCA_RED_STAB-1] == NULL || RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < RED_STAB_SIZE) return -EINVAL; ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);// 如果流量限制值有效, 建立RED流控的内部缺省流控结构, 为一BFIFO流控结构 if (ctl->limit > 0) { child = red_create_dflt(sch->dev, ctl->limit); if (child == NULL) return -ENOMEM; } sch_tree_lock(sch);// 设置RED流控结构标志和流量限制参数 q->flags = ctl->flags; q->limit = ctl->limit;// 对内部流控赋值 if (child) qdisc_destroy(xchg(&q->qdisc, child));// 设置RED流控算法参数 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog, ctl->Scell_log, RTA_DATA(tb[TCA_RED_STAB-1]));// 如果队列空, RED进入休眠状态 if (skb_queue_empty(&sch->q)) red_end_of_idle_period(&q->parms); sch_tree_unlock(sch); return 0;}// 建立缺省的RED内部Qdiscstatic struct Qdisc *red_create_dflt(struct net_device *dev, u32 limit){// 内部Qdisc使用的是bfifo, 按字节数限制 struct Qdisc *q = qdisc_create_dflt(dev, &bfifo_qdisc_ops); struct rtattr *rta; int ret; if (q) { rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL); if (rta) {// 填写rtattr结构, 实际有效数据就是流量限制值limit rta->rta_type = RTM_NEWQDISC; rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt)); ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;// 调用bfifo的修改函数设置bfifo流控结构的limit参数 ret = q->ops->change(q, rta); kfree(rta); if (ret == 0) return q; } qdisc_destroy(q); } return NULL;}5.7.5 入队static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// RED内部流控节点: bfifo struct Qdisc *child = q->qdisc; int ret;// 计算队列滑动平均值 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);// 如果在休眠, 停止休眠 if (red_is_idling(&q->parms)) red_end_of_idle_period(&q->parms);// 根据队列平均值获取判定结果 switch (red_action(&q->parms, q->parms.qavg)) {// 通过 case RED_DONT_MARK: break;// 概率标记 case RED_PROB_MARK: sch->qstats.overlimits++;// 如果没用ECN拥塞标志, 丢包 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) { q->stats.prob_drop++; goto congestion_drop; }// 概率标记增加,允许入队 q->stats.prob_mark++; break;// 直接标记 case RED_HARD_MARK:// overlimits增加 sch->qstats.overlimits++;// 如果RED设置HARDDROP标志或没使用ECN, 丢包 if (red_use_harddrop(q) || !red_use_ecn(q) || !INET_ECN_set_ce(skb)) { q->stats.forced_drop++; goto congestion_drop; }// forced_mask增加, 允许入队 q->stats.forced_mark++; break; }// 调度内部流控的入队函数 ret = child->enqueue(skb, child);// 根据入队是否成功更新相关统计 if (likely(ret == NET_XMIT_SUCCESS)) { sch->bstats.bytes += skb->len; sch->bstats.packets++; sch->q.qlen++; } else { q->stats.pdrop++; sch->qstats.drops++; } return ret;congestion_drop:// 拥塞丢包处理 qdisc_drop(skb, sch); return NET_XMIT_CN;}5.7.6 重入队static int red_requeue(struct sk_buff *skb, struct Qdisc* sch){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 内部流控 struct Qdisc *child = q->qdisc; int ret;// 如果在休眠, 停止休眠 if (red_is_idling(&q->parms)) red_end_of_idle_period(&q->parms);// 使用内部流控的重入队函数 ret = child->ops->requeue(skb, child);// 成功的话更新统计数据 if (likely(ret == NET_XMIT_SUCCESS)) { sch->qstats.requeues++; sch->q.qlen++; } return ret;}5.7.7 出队static struct sk_buff * red_dequeue(struct Qdisc* sch){ struct sk_buff *skb;// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 内部流控 struct Qdisc *child = q->qdisc;// 调用内部流控的出队函数 skb = child->dequeue(child);// 如果出队成功, RED队列长度减1, 返回数据包 if (skb) sch->q.qlen--; else if (!red_is_idling(&q->parms))// 否则队列空, RED进入休眠状态 red_start_of_idle_period(&q->parms); return skb;}5.7.8 丢包static unsigned int red_drop(struct Qdisc* sch){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 内部流控 struct Qdisc *child = q->qdisc; unsigned int len;// 如果内部流控结构定义的丢包函数, 执行该丢包函数, 更新统计返回 if (child->ops->drop && (len = child->ops->drop(child)) > 0) { q->stats.other++; sch->qstats.drops++; sch->q.qlen--; return len; }// 否则使RED进入休眠状态 if (!red_is_idling(&q->parms)) red_start_of_idle_period(&q->parms); return 0;} 5.7.9 复位// 就是内部流控的复位函数, RED队列长度清零static void red_reset(struct Qdisc* sch){ struct red_sched_data *q = qdisc_priv(sch); qdisc_reset(q->qdisc); sch->q.qlen = 0; red_restart(&q->parms);}5.7.10 释放// 就是内部流控的释放函数static void red_destroy(struct Qdisc *sch){ struct red_sched_data *q = qdisc_priv(sch); qdisc_destroy(q->qdisc);}5.7.11 输出参数static int red_dump(struct Qdisc *sch, struct sk_buff *skb){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch); struct rtattr *opts = NULL;// 填写RED参数结构 struct tc_red_qopt opt = { .limit = q->limit, .flags = q->flags, .qth_min = q->parms.qth_min >> q->parms.Wlog, .qth_max = q->parms.qth_max >> q->parms.Wlog, .Wlog = q->parms.Wlog, .Plog = q->parms.Plog, .Scell_log = q->parms.Scell_log, };// 将参数拷贝到skb数据区 opts = RTA_NEST(skb, TCA_OPTIONS); RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);// 发送数据包 return RTA_NEST_END(skb, opts);rtattr_failure: return RTA_NEST_CANCEL(skb, opts);}5.7.12 输出统计值static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 构造标准TC统计结构, 填写相关参数 struct tc_red_xstats st = {// 提早丢包数: 概率丢和强迫丢 .early = q->stats.prob_drop + q->stats.forced_drop,// 丢包数 .pdrop = q->stats.pdrop,// 其他 .other = q->stats.other,// 被标记的包数 .marked = q->stats.prob_mark + q->stats.forced_mark, };// 返回 return gnet_stats_copy_app(d, &st, sizeof(st));}5.7.13 RED类别操作// 输出分类static int red_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, struct tcmsg *tcm){ struct red_sched_data *q = qdisc_priv(sch); if (cl != 1) return -ENOENT;// 设置tcm参数:// handle或1 tcm->tcm_handle |= TC_H_MIN(1);// 信息为内部流控handle tcm->tcm_info = q->qdisc->handle; return 0;}// 嫁接, 增加叶子qdiscstatic int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old){// RED私有数据 struct red_sched_data *q = qdisc_priv(sch);// 如果没定义新流控, 用noop_qdisc if (new == NULL) new = &noop_qdisc; sch_tree_lock(sch);// 将当前RED内部流控和新流控结构指针对换 *old = xchg(&q->qdisc, new);// 复位老流控结构 qdisc_reset(*old);// 流控队列长度清零 sch->q.qlen = 0; sch_tree_unlock(sch); return 0;}// 获取叶子流控节点static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg){ struct red_sched_data *q = qdisc_priv(sch);// 返回RED内部流控: bfifo return q->qdisc;}// 引用计数static unsigned long red_get(struct Qdisc *sch, u32 classid){ return 1;}// 释放计数,空函数static void red_put(struct Qdisc *sch, unsigned long arg){ return;}// 更改类别, 无定义static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca, unsigned long *arg){ return -ENOSYS;}// 删除节点, 无定义static int red_delete(struct Qdisc *sch, unsigned long cl){ return -ENOSYS;}// 遍历static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker){// 其实也说不上遍历, 因为就只执行一次 if (!walker->stop) { if (walker->count >= walker->skip) if (walker->fn(sch, 1, walker) < 0) { walker->stop = 1; return; } walker->count++; }}// 查找分类过滤规则, 空函数static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl){ return NULL;}...... 待续 ......