Linux内核中流量控制(3)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，
严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn

5.2 FIFO

FIFO算法在net/sched/sch_fifo.c中定义, 既可以单独使用, 也可以被其他流控算法(如TBF)作为内
部流控算法使用.

5.2.1 流控结构
FIFO分两种, 一种是PFIFO, 一种是BFIFO, 分别按包数和字节数进行FIFO的流量控制.
 
// 私有数据结构, 就是流量参数
struct fifo_sched_data
{
 u32 limit;
};
// 包数流控
struct Qdisc_ops pfifo_qdisc_ops = {
 .id  = "pfifo",
 .priv_size = sizeof(struct fifo_sched_data),
 .enqueue = pfifo_enqueue,
 .dequeue = qdisc_dequeue_head,
 .requeue = qdisc_requeue,
 .drop  = qdisc_queue_drop,
 .init  = fifo_init,
 .reset  = qdisc_reset_queue,
 .change  = fifo_init,
 .dump  = fifo_dump,
 .owner  = THIS_MODULE,
};

// 字节数流控
struct Qdisc_ops bfifo_qdisc_ops = {
 .id  = "bfifo",
 .priv_size = sizeof(struct fifo_sched_data),
 .enqueue = bfifo_enqueue,
 .dequeue = qdisc_dequeue_head,
 .requeue = qdisc_requeue,
 .drop  = qdisc_queue_drop,
 .init  = fifo_init,
 .reset  = qdisc_reset_queue,
 .change  = fifo_init,
 .dump  = fifo_dump,
 .owner  = THIS_MODULE,
};
在这两个结构中, 处理enqueue, init, reset, dump外, 其他操作函数都是用流控缺省操作函数.

5.2.2 初始化

static int fifo_init(struct Qdisc *sch, struct rtattr *opt)
{
// FIFO私有数据
 struct fifo_sched_data *q = qdisc_priv(sch);
 if (opt == NULL) {
// 如果没提供流量参数情况
// limit缺省取网卡的发送队列长度, 而且至少为1
  u32 limit = sch->dev->tx_queue_len ? : 1;
// 如果是字节流控, 用的是队列长度*MTU作为限制值
  if (sch->ops == &bfifo_qdisc_ops)
   limit *= sch->dev->mtu;
// 如果是包流控, 直接用队列长度作为限制值
  q->limit = limit;
 } else {
// 提供合法流量参数时用提供的流控值作为流控限制参数
  struct tc_fifo_qopt *ctl = RTA_DATA(opt);
  if (RTA_PAYLOAD(opt) < sizeof(*ctl))
   return -EINVAL;
  q->limit = ctl->limit;
 }
 return 0;
}

5.2.3 入队

// 字节流控入队
static int bfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
 struct fifo_sched_data *q = qdisc_priv(sch);
// 如果当前队列数据总长加数据包长度不超过限制值, 将数据包添加到队列尾
 if (likely(sch->qstats.backlog + skb->len <= q->limit))
  return qdisc_enqueue_tail(skb, sch);
 return qdisc_reshape_fail(skb, sch);
}

// 包数流控入队
static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
 struct fifo_sched_data *q = qdisc_priv(sch);
// 如果缓存队列数据包数小于限制值, 将数据包添加到队列尾
 if (likely(skb_queue_len(&sch->q) < q->limit))
  return qdisc_enqueue_tail(skb, sch);
 return qdisc_reshape_fail(skb, sch);
}
 
5.2.4 输出

// 就是将私有数据limit作为参数返回, 用的应该是netlink套接口
static int fifo_dump(struct Qdisc *sch, struct sk_buff *skb)
{
 struct fifo_sched_data *q = qdisc_priv(sch);
 struct tc_fifo_qopt opt = { .limit = q->limit };
 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 return skb->len;
rtattr_failure:
 return -1;
}
 
5.3 TBF(Token Bucket Filter queue, 令牌桶过滤队列)

TBF算法是一种限制流量算法，基本原理是将入队的数据包缓存在队列中，同时按指定的速度产生令
牌，只有拥有令牌才能数据包出队，这样就控制了出口流量，目前netfilter中的limit匹配实际也是
用TBF算法, 该算法在net/sched/sch_tbf.c中定义，在该文件的注释中定义的算法如下：
/*
 Description.
 ------------
 A data flow obeys TBF with rate R and depth B, if for any
 time interval t_i...t_f the number of transmitted bits
 does not exceed B + R*(t_f-t_i).
 Packetized version of this definition:
 The sequence of packets of sizes s_i served at moments t_i
 obeys TBF, if for any i<=k:
 s_i+....+s_k <= B + R*(t_k - t_i)
 Algorithm.
 ----------
 Let N(t_i) be B/R initially and N(t) grow continuously with time as:
 N(t+delta) = min{B/R, N(t) + delta}
 If the first packet in queue has length S, it may be
 transmitted only at the time t_* when S/R <= N(t_*),
 and in this case N(t) jumps:
 N(t_* + 0) = N(t_* - 0) - S/R.
 
 Actually, QoS requires two TBF to be applied to a data stream.
 One of them controls steady state burst size, another
 one with rate P (peak rate) and depth M (equal to link MTU)
 limits bursts at a smaller time scale.
 It is easy to see that P>R, and B>M. If P is infinity, this double
 TBF is equivalent to a single one.
 When TBF works in reshaping mode, latency is estimated as:
 lat = max ((L-B)/R, (L-M)/P)
*/
 
5.3.1 操作结构定义

// TBF属性结构
struct tc_tbf_qopt
{
// 速率
 struc