Linux内核中流量控制(7)

Godbach

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
Pb = max_P * (avg - th_min)/(th_max-th_min)
然后按此概率丢包, max_P为一小数, 通常为0.01, 0.02等, 一般在算法中通过右移操作来实现:
max_P = (qth_max-qth_min)>>Plog
Plog为可配置参数
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
// 设置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 qth_max = qth_max Wlog  = Wlog;
p->Plog  = Plog;
// 随机掩码
p->Rmask = red_rmask(Plog);
p->Scell_log = Scell_log;
// 最大休眠时间
p->Scell_max = (255 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 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)
    Any questions? --ANK (980924)
  */
// 根据当前队列平均值计算出一个值是否小于随机数qR来实现概率丢包
return !(((qavg - p->qth_min) >> p->Wlog) * p->qcount 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 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])
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内部Qdisc
static 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;
}
// 嫁接, 增加叶子qdisc
static 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) stop = 1;
    return;
   }
  walker->count++;
}
}
// 查找分类过滤规则, 空函数
static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
{
return NULL;
}
...... 待续 ......
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/33048/showart_2094269.html