hashlimit模块实现分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
免责声明：有些地方没有仔细看，如有错误，不负责任，欢迎指正
好久不发贴子了，来骗点积分。
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
嘿嘿，刚刚好！！