cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

xt_limit.c (6228B)


      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
     16struct xt_limit_priv {
     17	unsigned long prev;
     18	u32 credit;
     19};
     20
     21MODULE_LICENSE("GPL");
     22MODULE_AUTHOR("Herve Eychenne <rv@wallfire.org>");
     23MODULE_DESCRIPTION("Xtables: rate-limit match");
     24MODULE_ALIAS("ipt_limit");
     25MODULE_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
     62static bool
     63limit_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. */
     95static 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
    105static 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(r->avg * r->burst) < user2credits(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(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(r->avg * r->burst); /* Credits full. */
    128	if (r->cost == 0) {
    129		r->credit_cap = priv->credit; /* Credits full. */
    130		r->cost = user2credits(r->avg);
    131	}
    132
    133	return 0;
    134}
    135
    136static void limit_mt_destroy(const struct xt_mtdtor_param *par)
    137{
    138	const struct xt_rateinfo *info = par->matchinfo;
    139
    140	kfree(info->master);
    141}
    142
    143#ifdef CONFIG_NETFILTER_XTABLES_COMPAT
    144struct 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. */
    157static 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
    171static 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(dst, &cm, sizeof(cm)) ? -EFAULT : 0;
    184}
    185#endif /* CONFIG_NETFILTER_XTABLES_COMPAT */
    186
    187static 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
    204static int __init limit_mt_init(void)
    205{
    206	return xt_register_match(&limit_mt_reg);
    207}
    208
    209static void __exit limit_mt_exit(void)
    210{
    211	xt_unregister_match(&limit_mt_reg);
    212}
    213
    214module_init(limit_mt_init);
    215module_exit(limit_mt_exit);