1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* (C) 1999 Jérôme de Vivie <devivie@info.enserb.u-bordeaux.fr> |
3 | * (C) 1999 Hervé Eychenne <eychenne@info.enserb.u-bordeaux.fr> |
4 | * (C) 2006-2012 Patrick McHardy <kaber@trash.net> |
5 | */ |
6 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
7 | |
8 | #include <linux/slab.h> |
9 | #include <linux/module.h> |
10 | #include <linux/skbuff.h> |
11 | #include <linux/interrupt.h> |
12 | |
13 | #include <linux/netfilter/x_tables.h> |
14 | #include <linux/netfilter/xt_limit.h> |
15 | |
16 | struct xt_limit_priv { |
17 | unsigned long prev; |
18 | u32 credit; |
19 | }; |
20 | |
21 | MODULE_LICENSE("GPL" ); |
22 | MODULE_AUTHOR("Herve Eychenne <rv@wallfire.org>" ); |
23 | MODULE_DESCRIPTION("Xtables: rate-limit match" ); |
24 | MODULE_ALIAS("ipt_limit" ); |
25 | MODULE_ALIAS("ip6t_limit" ); |
26 | |
27 | /* The algorithm used is the Simple Token Bucket Filter (TBF) |
28 | * see net/sched/sch_tbf.c in the linux source tree |
29 | */ |
30 | |
31 | /* Rusty: This is my (non-mathematically-inclined) understanding of |
32 | this algorithm. The `average rate' in jiffies becomes your initial |
33 | amount of credit `credit' and the most credit you can ever have |
34 | `credit_cap'. The `peak rate' becomes the cost of passing the |
35 | test, `cost'. |
36 | |
37 | `prev' tracks the last packet hit: you gain one credit per jiffy. |
38 | If you get credit balance more than this, the extra credit is |
39 | discarded. Every time the match passes, you lose `cost' credits; |
40 | if you don't have that many, the test fails. |
41 | |
42 | See Alexey's formal explanation in net/sched/sch_tbf.c. |
43 | |
44 | To get the maximum range, we multiply by this factor (ie. you get N |
45 | credits per jiffy). We want to allow a rate as low as 1 per day |
46 | (slowest userspace tool allows), which means |
47 | CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32. ie. */ |
48 | #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24)) |
49 | |
50 | /* Repeated shift and or gives us all 1s, final shift and add 1 gives |
51 | * us the power of 2 below the theoretical max, so GCC simply does a |
52 | * shift. */ |
53 | #define _POW2_BELOW2(x) ((x)|((x)>>1)) |
54 | #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2)) |
55 | #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4)) |
56 | #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8)) |
57 | #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16)) |
58 | #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1) |
59 | |
60 | #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ) |
61 | |
62 | static bool |
63 | limit_mt(const struct sk_buff *skb, struct xt_action_param *par) |
64 | { |
65 | const struct xt_rateinfo *r = par->matchinfo; |
66 | struct xt_limit_priv *priv = r->master; |
67 | unsigned long now; |
68 | u32 old_credit, new_credit, credit_increase = 0; |
69 | bool ret; |
70 | |
71 | /* fastpath if there is nothing to update */ |
72 | if ((READ_ONCE(priv->credit) < r->cost) && (READ_ONCE(priv->prev) == jiffies)) |
73 | return false; |
74 | |
75 | do { |
76 | now = jiffies; |
77 | credit_increase += (now - xchg(&priv->prev, now)) * CREDITS_PER_JIFFY; |
78 | old_credit = READ_ONCE(priv->credit); |
79 | new_credit = old_credit; |
80 | new_credit += credit_increase; |
81 | if (new_credit > r->credit_cap) |
82 | new_credit = r->credit_cap; |
83 | if (new_credit >= r->cost) { |
84 | ret = true; |
85 | new_credit -= r->cost; |
86 | } else { |
87 | ret = false; |
88 | } |
89 | } while (cmpxchg(&priv->credit, old_credit, new_credit) != old_credit); |
90 | |
91 | return ret; |
92 | } |
93 | |
94 | /* Precision saver. */ |
95 | static u32 user2credits(u32 user) |
96 | { |
97 | /* If multiplying would overflow... */ |
98 | if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY)) |
99 | /* Divide first. */ |
100 | return (user / XT_LIMIT_SCALE) * HZ * CREDITS_PER_JIFFY; |
101 | |
102 | return (user * HZ * CREDITS_PER_JIFFY) / XT_LIMIT_SCALE; |
103 | } |
104 | |
105 | static int limit_mt_check(const struct xt_mtchk_param *par) |
106 | { |
107 | struct xt_rateinfo *r = par->matchinfo; |
108 | struct xt_limit_priv *priv; |
109 | |
110 | /* Check for overflow. */ |
111 | if (r->burst == 0 |
112 | || user2credits(user: r->avg * r->burst) < user2credits(user: r->avg)) { |
113 | pr_info_ratelimited("Overflow, try lower: %u/%u\n" , |
114 | r->avg, r->burst); |
115 | return -ERANGE; |
116 | } |
117 | |
118 | priv = kmalloc(size: sizeof(*priv), GFP_KERNEL); |
119 | if (priv == NULL) |
120 | return -ENOMEM; |
121 | |
122 | /* For SMP, we only want to use one set of state. */ |
123 | r->master = priv; |
124 | /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies * |
125 | 128. */ |
126 | priv->prev = jiffies; |
127 | priv->credit = user2credits(user: r->avg * r->burst); /* Credits full. */ |
128 | if (r->cost == 0) { |
129 | r->credit_cap = priv->credit; /* Credits full. */ |
130 | r->cost = user2credits(user: r->avg); |
131 | } |
132 | |
133 | return 0; |
134 | } |
135 | |
136 | static void limit_mt_destroy(const struct xt_mtdtor_param *par) |
137 | { |
138 | const struct xt_rateinfo *info = par->matchinfo; |
139 | |
140 | kfree(objp: info->master); |
141 | } |
142 | |
143 | #ifdef CONFIG_NETFILTER_XTABLES_COMPAT |
144 | struct compat_xt_rateinfo { |
145 | u_int32_t avg; |
146 | u_int32_t burst; |
147 | |
148 | compat_ulong_t prev; |
149 | u_int32_t credit; |
150 | u_int32_t credit_cap, cost; |
151 | |
152 | u_int32_t master; |
153 | }; |
154 | |
155 | /* To keep the full "prev" timestamp, the upper 32 bits are stored in the |
156 | * master pointer, which does not need to be preserved. */ |
157 | static void limit_mt_compat_from_user(void *dst, const void *src) |
158 | { |
159 | const struct compat_xt_rateinfo *cm = src; |
160 | struct xt_rateinfo m = { |
161 | .avg = cm->avg, |
162 | .burst = cm->burst, |
163 | .prev = cm->prev | (unsigned long)cm->master << 32, |
164 | .credit = cm->credit, |
165 | .credit_cap = cm->credit_cap, |
166 | .cost = cm->cost, |
167 | }; |
168 | memcpy(dst, &m, sizeof(m)); |
169 | } |
170 | |
171 | static int limit_mt_compat_to_user(void __user *dst, const void *src) |
172 | { |
173 | const struct xt_rateinfo *m = src; |
174 | struct compat_xt_rateinfo cm = { |
175 | .avg = m->avg, |
176 | .burst = m->burst, |
177 | .prev = m->prev, |
178 | .credit = m->credit, |
179 | .credit_cap = m->credit_cap, |
180 | .cost = m->cost, |
181 | .master = m->prev >> 32, |
182 | }; |
183 | return copy_to_user(to: dst, from: &cm, n: sizeof(cm)) ? -EFAULT : 0; |
184 | } |
185 | #endif /* CONFIG_NETFILTER_XTABLES_COMPAT */ |
186 | |
187 | static struct xt_match limit_mt_reg __read_mostly = { |
188 | .name = "limit" , |
189 | .revision = 0, |
190 | .family = NFPROTO_UNSPEC, |
191 | .match = limit_mt, |
192 | .checkentry = limit_mt_check, |
193 | .destroy = limit_mt_destroy, |
194 | .matchsize = sizeof(struct xt_rateinfo), |
195 | #ifdef CONFIG_NETFILTER_XTABLES_COMPAT |
196 | .compatsize = sizeof(struct compat_xt_rateinfo), |
197 | .compat_from_user = limit_mt_compat_from_user, |
198 | .compat_to_user = limit_mt_compat_to_user, |
199 | #endif |
200 | .usersize = offsetof(struct xt_rateinfo, prev), |
201 | .me = THIS_MODULE, |
202 | }; |
203 | |
204 | static int __init limit_mt_init(void) |
205 | { |
206 | return xt_register_match(target: &limit_mt_reg); |
207 | } |
208 | |
209 | static void __exit limit_mt_exit(void) |
210 | { |
211 | xt_unregister_match(target: &limit_mt_reg); |
212 | } |
213 | |
214 | module_init(limit_mt_init); |
215 | module_exit(limit_mt_exit); |
216 | |