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