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

5.5 SFQ(Stochastic Fairness Queueing discipline)

SFQ算法是个比较简单的算法，速度也比较快，算法维护一定数量的数据包队列，入队是将数据包进
行哈希后插入某队列，出队则是轮询方式出队列，另外可设置一定的随机因子，在计算哈希值时能碰
撞少些，流控算法在net/sched/sch_sfq.c中定义,在实现中, 队列数量最大为128个，这是保证SFQ私
有数据结构能小于4K，能在一个页面内分配。在使用用不建议作为网卡的根节点流控，而是最好作为
分类流控方法如CBQ等的叶子节点。

5.5.1 SFQ操作结构定义

// TC使用的SFQ配置参数结构
struct tc_sfq_qopt
{
// 定额
 unsigned quantum; /* Bytes per round allocated to flow */
// 扰动周期
 int  perturb_period; /* Period of hash perturbation */
// 队列中的数据包数量限制
 __u32  limit;  /* Maximal packets in queue */
 unsigned divisor; /* Hash divisor  */
// 最大队列数
 unsigned flows;  /* Maximal number of flows  */
};

#define SFQ_DEPTH  128
#define SFQ_HASH_DIVISOR 1024
/* This type should contain at least SFQ_DEPTH*2 values */
// SFQ索引值是无符合8位数
typedef unsigned char sfq_index;
struct sfq_head
{
 sfq_index next;
 sfq_index prev;
};

// SFQ私有数据
struct sfq_sched_data
{
/* Parameters */
// 扰动间隔, 隔一定时间修改HASH扰动 值
 int  perturb_period;
//
 unsigned quantum; /* Allotment per round: MUST BE >= MTU */
// 流量限制值
 int  limit;
/* Variables */
// 扰动更新定时器
 struct timer_list perturb_timer;
// HASH扰动值
 int  perturbation;
// 出队队列索引
 sfq_index tail;  /* Index of current slot in round */
// 最大深度
 sfq_index max_depth; /* Maximal depth */
// HASH值对应的槽位索引表, 1024项, HASH值范围为0~1023
 sfq_index ht[SFQ_HASH_DIVISOR]; /* Hash table */
// 活动槽
 sfq_index next[SFQ_DEPTH]; /* Active slots link */
 short  allot[SFQ_DEPTH]; /* Current allotment per slot */
// 哈希值索引数组
 unsigned short hash[SFQ_DEPTH]; /* Hash value indexed by slots */
// 数据包队列, 128个队列
 struct sk_buff_head qs[SFQ_DEPTH];  /* Slot queue */
// 深度值, 256个成员
 struct sfq_head dep[SFQ_DEPTH*2]; /* Linked list of slots, indexed by
depth */
};

SFQ数据结构比较怪异, 数据存储是数组, 但逻辑上又是双向链表, 访问时又使用数组索引。

// SFQ流控操作结构
static struct Qdisc_ops sfq_qdisc_ops = {
 .next  = NULL,
 .cl_ops  = NULL,
 .id  = "sfq",
 .priv_size = sizeof(struct sfq_sched_data),
 .enqueue = sfq_enqueue,
 .dequeue = sfq_dequeue,
 .requeue = sfq_requeue,
 .drop  = sfq_drop,
 .init  = sfq_init,
 .reset  = sfq_reset,
 .destroy = sfq_destroy,
// 注意没有change函数
 .change  = NULL,
 .dump  = sfq_dump,
 .owner  = THIS_MODULE,
};

5.5.2 SFQ一些基本操作
// HASH函数
static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
{
// 哈希扰动值
 int pert = q->perturbation;
 /* Have we any rotation primitives? If not, WHY? */
// 计算哈希值, 最大值0x3ff=1023
 h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
 h ^= h>>10;
 return h & 0x3FF;
}
// SFQ哈希函数
static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
{
 u32 h, h2;
// skb->protocol是链路层中的协议值
 switch (skb->protocol) {
// IPV4
 case __constant_htons(ETH_P_IP):
 {
  struct iphdr *iph = skb->nh.iph;
// 哈希函数中用到了源地址,目的地址, 协议, 端口或SPI值
  h = iph->daddr;
  h2 = iph->saddr^iph->protocol;
  if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
      (iph->protocol == IPPROTO_TCP ||
       iph->protocol == IPPROTO_UDP ||
       iph->protocol == IPPROTO_SCTP ||
       iph->protocol == IPPROTO_DCCP ||
       iph->protocol == IPPROTO_ESP))
   h2 ^= *(((u32*)iph) + iph->ihl);
  break;
 }
// IPV6
 case __constant_htons(ETH_P_IPV6):
 {
  struct ipv6hdr *iph = skb->nh.ipv6h;
// 用地址的最后4字节
  h = iph->daddr.s6_addr32[3];
  h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
  if (iph->nexthdr == IPPROTO_TCP ||
      iph->nexthdr == IPPROTO_UDP ||
      iph->nexthdr == IPPROTO_SCTP ||
      iph->nexthdr == IPPROTO_DCCP ||
      iph->nexthdr == IPPROTO_ESP)
   h2 ^= *(u32*)&iph[1];
  break;
 }
 default:
// 其他协议就用路由参数, 链路层协议和sock指针
  h = (u32)(unsigned long)skb->dst^skb->protocol;
  h2 = (u32)(unsigned long)skb->sk;
 }
// 计算哈希值
 return sfq_fold_hash(q, h, h2);
}

// 链接操作
static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
{
 sfq_index p