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
