hashlimit模块实现分析

68 阅读 0 评论 45 点赞

我是靠谱客的博主内向火车，最近开发中收集的这篇文章主要介绍hashlimit模块实现分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

免责声明：有些地方没有仔细看，如有错误，不负责任，欢迎指正
好久不发贴子了，来骗点积分。
1、引言
一直用tc来做流控，偶然发现Netfilter有一个名为hashlimit的东东，是基于TBF（令牌桶算法）的简单的流量控制的。例如：
QUOTE:
iptables -A INPUT -p tcp --dport 22 -m hashlimit --hashlimit-name foo --hashlimit 100/sec --hashlimit-burst 10 --hashlimit-mode srcip -j ACCEPT
iptables -A INPUT -p tcp --dport 22 -j DROP
TBF算法还是比较简单的，著名的《计算机网络》一书中有算法介绍，这里就不重复了。注意的是，TBF可以是基于字节，也可以是基于数据包数量的。hashlimit使用了后者。
--hashlimit-name foo ：取个名，反映在proc中；
--hashlimit 100/sec：每秒的数据包小于或等于XXX；
--hashlimit-burst 10 ：每秒允许的突发；
都是“每秒”，究竟是谁的每秒呢？主要就是看hashlimit-mode srcip(hash模式)，也就是限制的标的取哪一个，可以是四种：源地址、目的地址、源端口、目的端口；
以源地址为例，如果规则中增加了-s 192.168.0.0/24，那么只有来源地址符合这个的进入-m hashlimit，hash模式为源地址，意味着将每个来源地址都做为一个限制标的！！
--hashlimit 100/sec：每秒的数据包小于或等于XXX；
准确点就是192.168.0.0/24上的每一个主机每秒……
要实现TBF，有几个基本的要素：
1、桶最大的令牌数；credit_cap
2、可发放的令牌数，它是根据单位时间定时刷新的；credit
3、令牌的消耗，每通过一个包，消耗多少个令牌。cost
基本关系是：
每过一个包，都要进行credit -= cost，直至credit <=0，即没有可供分配的令牌了——超限溢出；
定时刷新credit，但是总量不得超过credit_cap。
2、实现
废话少说，来看代码。
[Copy to clipboard] [ - ]CODE:
static int
hashlimit_match(const struct sk_buff *skb,
const struct net_device *in,
const struct net_device *out,
const void *matchinfo,
int offset,
int *hotdrop)
{
struct ipt_hashlimit_info *r =
((struct ipt_hashlimit_info *)matchinfo)->u.master;
struct ipt_hashlimit_htable *hinfo = r->hinfo;
unsigned long now = jiffies;
struct dsthash_ent *dh;
struct dsthash_dst dst;
/* 根据hash mode和当前包，构建dst结构 */
memset(&dst, 0, sizeof(dst));
if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DIP)
//目的IP
dst.dst_ip = skb->nh.iph->daddr;
if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SIP)
//源IP
dst.src_ip = skb->nh.iph->saddr;
if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DPT
//端口
||hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SPT) {
u_int16_t ports[2];
if (get_ports(skb, offset, ports)) {
/* We've been asked to examine this packet, and we
can't.
Hence, no choice but to drop. */
*hotdrop = 1;
return 0;
}
if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SPT)
dst.src_port = ports[0];
if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DPT)
dst.dst_port = ports[1];
}
这段代码根据hash模块，取出数据包相应的元素。struct dsthash_dst是hash表使用的结构。
[Copy to clipboard] [ - ]CODE:
spin_lock_bh(&hinfo->lock);
//查找hash表
dh = __dsthash_find(hinfo, &dst);
查看hash表中，是否有与dst一匹备的节点，之所以叫hashlimit，就是因为每一个元素（例如以来源地址每一个IP），都被存放在hash表中（一个来源地址占据一个hash节点）。
[Copy to clipboard] [ - ]CODE:
if (!dh) {
dh = __dsthash_alloc_init(hinfo, &dst);
//未命中，分配新的接点，并增加至hash 表
if (!dh) {
/* enomem... don't match == DROP */
if (net_ratelimit())
printk(KERN_ERR "%s: ENOMEM/n", __FUNCTION__);
spin_unlock_bh(&hinfo->lock);
return 0;
}
//构建结点成员
dh->expires = jiffies + msecs_to_jiffies(hinfo->cfg.expire);
//定时器
dh->rateinfo.prev = jiffies;
//最后修改时间定为当前时间
dh->rateinfo.credit = user2credits(hinfo->cfg.avg *
//初始化令牌
hinfo->cfg.burst);
//初始化令牌桶大小，在令牌没有被消耗前，两者是相同的
dh->rateinfo.credit_cap = user2credits(hinfo->cfg.avg *
hinfo->cfg.burst);
dh->rateinfo.cost = user2credits(hinfo->cfg.avg);
//初始化当前包的开销，每过一个包递减
spin_unlock_bh(&hinfo->lock);
return 1;
}
如果不在hash表中，则分配新的节点，插入hash表，然后初始化节点成员dh。代码很简单，但是关键是对这些东东的计算，后文分析：
[Copy to clipboard] [ - ]CODE:
dh->rateinfo.credit = user2credits(hinfo->cfg.avg *
//初始化令牌
hinfo->cfg.burst);
//初始化令牌桶大小，在令牌没有被消耗前，两者是相同的
dh->rateinfo.credit_cap = user2credits(hinfo->cfg.avg *
hinfo->cfg.burst);
dh->rateinfo.cost = user2credits(hinfo->cfg.avg);
//初始化当前包的开销，每过一个包递
因为前面已经return 1了，接下来是hash命中的情况了：
[Copy to clipboard] [ - ]CODE:
/* 更新超时时间戳 */
dh->expires = now + msecs_to_jiffies(hinfo->cfg.expire);
/* 重新计算令牌 */
rateinfo_recalc(dh, now);
if (dh->rateinfo.credit >= dh->rateinfo.cost) {
//如果还有令牌
/* We're underlimit. */
dh->rateinfo.credit -= dh->rateinfo.cost;
//减去当前包消耗掉的令牌，通过
spin_unlock_bh(&hinfo->lock);
return 1;
}
这段代码意思是，周期性地刷新令牌，并且判断是否还有可供分配的令牌。对于每经过一个包，都会递减令牌数。直接
dh->rateinfo.credit < dh->rateinfo.cost
这也就意味着没有可供分配令牌了。所以，最后return 0；
代码结构非常简单，与TBF算法一模一样，关键是两个地方，一个是初始化时，对于令牌的分配。另一个是得新计算令牌数函数rateinfo_recalc()
需要重点理解的是令牌刷新的时间周期，虽然用户态使用了秒、分、小时……不过内核是使用的jiffy。在初始计算的时候，user2credits() 函数被调用：
[Copy to clipboard] [ - ]CODE:
dh->rateinfo.credit = user2credits(hinfo->cfg.avg *
hinfo->cfg.burst);
dh->rateinfo.credit_cap = user2credits(hinfo->cfg.avg *
hinfo->cfg.burst);
dh->rateinfo.cost = user2credits(hinfo->cfg.avg);
注意到的，cost比前者差了一个burst倍。举个例子，如果初始允许突发包是10个。那么credit可能是3200，而cost 320，相差10倍。这也意味着，在credit不被更新的情况下（在一个jiffy周期之内），超过被允许的突发值后，令牌就用完了。
来看user2credits的实现：
[Copy to clipboard] [ - ]CODE:
/* Precision saver. */
static inline u_int32_t
user2credits(u_int32_t user)
{
/* If multiplying would overflow... */
if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))
/* Divide first. */
return (user / IPT_HASHLIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;
return (user * HZ * CREDITS_PER_JIFFY) / IPT_HASHLIMIT_SCALE;
}
CREDITS_PER_JIFFY宏表示的是每个jiffy要产生的令牌数，乘以HZ，则表示为每秒。之所以要除以IPT_HASHLIMIT_SCALE，是因为在iptables获取值的时候，有一个反向操作(难道不想让用户态传递的时候，这个值过大，需要转换一下？？？)：
[Copy to clipboard] [ - ]CODE:
*val = IPT_DSTLIMIT_SCALE * mult / r;
最重要的函数是rateinfo_recalc，它负责在每个jiffy周期，产生新的令牌，以使游戏能够继续下去：
[Copy to clipboard] [ - ]CODE:
static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)
{
dh->rateinfo.credit += (now - xchg(&dh->rateinfo.prev, now))
* CREDITS_PER_JIFFY;
if (dh->rateinfo.credit > dh->rateinfo.credit_cap)
dh->rateinfo.credit = dh->rateinfo.credit_cap;
}
以前一个包至目前时间的jiffy的差值N，并乘上CREDITS_PER_JIFFY得到新的令牌数。并且，它最大不能超过令牌桶的大小。
3、一个现实的例子
假如设定以下参数：
每秒平均值：100/sec
允许突发：10；
每jiffy产生的令牌为32，即CREDITS_PER_JIFFY = 32；
那么可以计算出：credit = 3200,cost = 320；
如果每秒是100个包，因为每个包消耗320，则每秒共需要的令牌数总计为320 * 100 + 320 * 10 = 32000 + 3200
因为CREDITS_PER_JIFFY为32，则每秒产生的令牌是32 * 1000 ，并且，初始化时，credit = 3200，总计32000 + 3200
嘿嘿，刚刚好！！