Linux内核中流量控制(7)

本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn: [e-mail]
来源：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)>>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 < 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内部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) < 0) {
    walker->stop = 1;
    return;
   }
  walker->count++;
 }
}
// 查找分类过滤规则, 空函数
static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
{
 return NULL;
}

...... 待续 ......