11da177e4SLinus Torvalds /*
21da177e4SLinus Torvalds * INETPEER - A storage for permanent information about peers
31da177e4SLinus Torvalds *
41da177e4SLinus Torvalds * This source is covered by the GNU GPL, the same as all kernel sources.
51da177e4SLinus Torvalds *
61da177e4SLinus Torvalds * Authors: Andrey V. Savochkin <saw@msu.ru>
71da177e4SLinus Torvalds */
81da177e4SLinus Torvalds
908009a76SAlexey Dobriyan #include <linux/cache.h>
101da177e4SLinus Torvalds #include <linux/module.h>
111da177e4SLinus Torvalds #include <linux/types.h>
121da177e4SLinus Torvalds #include <linux/slab.h>
131da177e4SLinus Torvalds #include <linux/interrupt.h>
141da177e4SLinus Torvalds #include <linux/spinlock.h>
151da177e4SLinus Torvalds #include <linux/random.h>
161da177e4SLinus Torvalds #include <linux/timer.h>
171da177e4SLinus Torvalds #include <linux/time.h>
181da177e4SLinus Torvalds #include <linux/kernel.h>
191da177e4SLinus Torvalds #include <linux/mm.h>
201da177e4SLinus Torvalds #include <linux/net.h>
215faa5df1SSteffen Klassert #include <linux/workqueue.h>
2220380731SArnaldo Carvalho de Melo #include <net/ip.h>
231da177e4SLinus Torvalds #include <net/inetpeer.h>
246e5714eaSDavid S. Miller #include <net/secure_seq.h>
251da177e4SLinus Torvalds
261da177e4SLinus Torvalds /*
271da177e4SLinus Torvalds * Theory of operations.
281da177e4SLinus Torvalds * We keep one entry for each peer IP address. The nodes contains long-living
291da177e4SLinus Torvalds * information about the peer which doesn't depend on routes.
301da177e4SLinus Torvalds *
311da177e4SLinus Torvalds * Nodes are removed only when reference counter goes to 0.
321da177e4SLinus Torvalds * When it's happened the node may be removed when a sufficient amount of
331da177e4SLinus Torvalds * time has been passed since its last use. The less-recently-used entry can
341da177e4SLinus Torvalds * also be removed if the pool is overloaded i.e. if the total amount of
351da177e4SLinus Torvalds * entries is greater-or-equal than the threshold.
361da177e4SLinus Torvalds *
37b145425fSEric Dumazet * Node pool is organised as an RB tree.
381da177e4SLinus Torvalds * Such an implementation has been chosen not just for fun. It's a way to
391da177e4SLinus Torvalds * prevent easy and efficient DoS attacks by creating hash collisions. A huge
401da177e4SLinus Torvalds * amount of long living nodes in a single hash slot would significantly delay
411da177e4SLinus Torvalds * lookups performed with disabled BHs.
421da177e4SLinus Torvalds *
431da177e4SLinus Torvalds * Serialisation issues.
44aa1039e7SEric Dumazet * 1. Nodes may appear in the tree only with the pool lock held.
45aa1039e7SEric Dumazet * 2. Nodes may disappear from the tree only with the pool lock held
461da177e4SLinus Torvalds * AND reference count being 0.
474b9d9be8SEric Dumazet * 3. Global variable peer_total is modified under the pool lock.
484b9d9be8SEric Dumazet * 4. struct inet_peer fields modification:
49b145425fSEric Dumazet * rb_node: pool lock
501da177e4SLinus Torvalds * refcnt: atomically against modifications on other CPU;
511da177e4SLinus Torvalds * usually under some other lock to prevent node disappearing
52582a72daSDavid S. Miller * daddr: unchangeable
531da177e4SLinus Torvalds */
541da177e4SLinus Torvalds
5508009a76SAlexey Dobriyan static struct kmem_cache *peer_cachep __ro_after_init;
561da177e4SLinus Torvalds
inet_peer_base_init(struct inet_peer_base * bp)57c3426b47SDavid S. Miller void inet_peer_base_init(struct inet_peer_base *bp)
58c3426b47SDavid S. Miller {
59b145425fSEric Dumazet bp->rb_root = RB_ROOT;
60c3426b47SDavid S. Miller seqlock_init(&bp->lock);
61c3426b47SDavid S. Miller bp->total = 0;
62c3426b47SDavid S. Miller }
63c3426b47SDavid S. Miller EXPORT_SYMBOL_GPL(inet_peer_base_init);
64021e9299SDavid S. Miller
65b145425fSEric Dumazet #define PEER_MAX_GC 32
661da177e4SLinus Torvalds
671da177e4SLinus Torvalds /* Exported for sysctl_net_ipv4. */
688bd2a055SYejune Deng int inet_peer_threshold __read_mostly; /* start to throw entries more
691da177e4SLinus Torvalds * aggressively at this stage */
70243bbcaaSEric Dumazet int inet_peer_minttl __read_mostly = 120 * HZ; /* TTL under high load: 120 sec */
71243bbcaaSEric Dumazet int inet_peer_maxttl __read_mostly = 10 * 60 * HZ; /* usual time to live: 10 min */
721da177e4SLinus Torvalds
731da177e4SLinus Torvalds /* Called from ip_output.c:ip_init */
inet_initpeers(void)741da177e4SLinus Torvalds void __init inet_initpeers(void)
751da177e4SLinus Torvalds {
768bd2a055SYejune Deng u64 nr_entries;
771da177e4SLinus Torvalds
788bd2a055SYejune Deng /* 1% of physical memory */
798bd2a055SYejune Deng nr_entries = div64_ul((u64)totalram_pages() << PAGE_SHIFT,
808bd2a055SYejune Deng 100 * L1_CACHE_ALIGN(sizeof(struct inet_peer)));
818bd2a055SYejune Deng
828bd2a055SYejune Deng inet_peer_threshold = clamp_val(nr_entries, 4096, 65536 + 128);
831da177e4SLinus Torvalds
84*57f2c635SKunwu Chan peer_cachep = KMEM_CACHE(inet_peer, SLAB_HWCACHE_ALIGN | SLAB_PANIC);
85d6cc1d64SEric Dumazet }
861da177e4SLinus Torvalds
87b145425fSEric Dumazet /* Called with rcu_read_lock() or base->lock held */
lookup(const struct inetpeer_addr * daddr,struct inet_peer_base * base,unsigned int seq,struct inet_peer * gc_stack[],unsigned int * gc_cnt,struct rb_node ** parent_p,struct rb_node *** pp_p)88b145425fSEric Dumazet static struct inet_peer *lookup(const struct inetpeer_addr *daddr,
89b145425fSEric Dumazet struct inet_peer_base *base,
90b145425fSEric Dumazet unsigned int seq,
91b145425fSEric Dumazet struct inet_peer *gc_stack[],
92b145425fSEric Dumazet unsigned int *gc_cnt,
93b145425fSEric Dumazet struct rb_node **parent_p,
94b145425fSEric Dumazet struct rb_node ***pp_p)
95aa1039e7SEric Dumazet {
964cc5b44bSEric Dumazet struct rb_node **pp, *parent, *next;
97b145425fSEric Dumazet struct inet_peer *p;
98aa1039e7SEric Dumazet
99b145425fSEric Dumazet pp = &base->rb_root.rb_node;
100b145425fSEric Dumazet parent = NULL;
1014cc5b44bSEric Dumazet while (1) {
102b145425fSEric Dumazet int cmp;
103b145425fSEric Dumazet
1044cc5b44bSEric Dumazet next = rcu_dereference_raw(*pp);
1054cc5b44bSEric Dumazet if (!next)
1064cc5b44bSEric Dumazet break;
1074cc5b44bSEric Dumazet parent = next;
108b145425fSEric Dumazet p = rb_entry(parent, struct inet_peer, rb_node);
109b145425fSEric Dumazet cmp = inetpeer_addr_cmp(daddr, &p->daddr);
11002663045SDavid S. Miller if (cmp == 0) {
111b145425fSEric Dumazet if (!refcount_inc_not_zero(&p->refcnt))
112b145425fSEric Dumazet break;
113b145425fSEric Dumazet return p;
1141cc9a98bSReshetova, Elena }
115b145425fSEric Dumazet if (gc_stack) {
116b145425fSEric Dumazet if (*gc_cnt < PEER_MAX_GC)
117b145425fSEric Dumazet gc_stack[(*gc_cnt)++] = p;
118b145425fSEric Dumazet } else if (unlikely(read_seqretry(&base->lock, seq))) {
119aa1039e7SEric Dumazet break;
120aa1039e7SEric Dumazet }
121b145425fSEric Dumazet if (cmp == -1)
12235f493b8SEric Dumazet pp = &next->rb_left;
123b145425fSEric Dumazet else
12435f493b8SEric Dumazet pp = &next->rb_right;
125b145425fSEric Dumazet }
126b145425fSEric Dumazet *parent_p = parent;
127b145425fSEric Dumazet *pp_p = pp;
128aa1039e7SEric Dumazet return NULL;
129aa1039e7SEric Dumazet }
130aa1039e7SEric Dumazet
inetpeer_free_rcu(struct rcu_head * head)131aa1039e7SEric Dumazet static void inetpeer_free_rcu(struct rcu_head *head)
132aa1039e7SEric Dumazet {
133aa1039e7SEric Dumazet kmem_cache_free(peer_cachep, container_of(head, struct inet_peer, rcu));
134aa1039e7SEric Dumazet }
135aa1039e7SEric Dumazet
1364b9d9be8SEric Dumazet /* perform garbage collect on all items stacked during a lookup */
inet_peer_gc(struct inet_peer_base * base,struct inet_peer * gc_stack[],unsigned int gc_cnt)137b145425fSEric Dumazet static void inet_peer_gc(struct inet_peer_base *base,
138b145425fSEric Dumazet struct inet_peer *gc_stack[],
139b145425fSEric Dumazet unsigned int gc_cnt)
14098158f5aSDavid S. Miller {
1413d32edf1SKuniyuki Iwashima int peer_threshold, peer_maxttl, peer_minttl;
142b145425fSEric Dumazet struct inet_peer *p;
1434b9d9be8SEric Dumazet __u32 delta, ttl;
144b145425fSEric Dumazet int i;
14598158f5aSDavid S. Miller
1463d32edf1SKuniyuki Iwashima peer_threshold = READ_ONCE(inet_peer_threshold);
1473d32edf1SKuniyuki Iwashima peer_maxttl = READ_ONCE(inet_peer_maxttl);
1483d32edf1SKuniyuki Iwashima peer_minttl = READ_ONCE(inet_peer_minttl);
1493d32edf1SKuniyuki Iwashima
1503d32edf1SKuniyuki Iwashima if (base->total >= peer_threshold)
1514b9d9be8SEric Dumazet ttl = 0; /* be aggressive */
1524b9d9be8SEric Dumazet else
1533d32edf1SKuniyuki Iwashima ttl = peer_maxttl - (peer_maxttl - peer_minttl) / HZ *
1543d32edf1SKuniyuki Iwashima base->total / peer_threshold * HZ;
155b145425fSEric Dumazet for (i = 0; i < gc_cnt; i++) {
156b145425fSEric Dumazet p = gc_stack[i];
15771685eb4SEric Dumazet
15871685eb4SEric Dumazet /* The READ_ONCE() pairs with the WRITE_ONCE()
15971685eb4SEric Dumazet * in inet_putpeer()
16071685eb4SEric Dumazet */
16171685eb4SEric Dumazet delta = (__u32)jiffies - READ_ONCE(p->dtime);
16271685eb4SEric Dumazet
163b145425fSEric Dumazet if (delta < ttl || !refcount_dec_if_one(&p->refcnt))
164b145425fSEric Dumazet gc_stack[i] = NULL;
165b145425fSEric Dumazet }
166b145425fSEric Dumazet for (i = 0; i < gc_cnt; i++) {
167b145425fSEric Dumazet p = gc_stack[i];
168b145425fSEric Dumazet if (p) {
169b145425fSEric Dumazet rb_erase(&p->rb_node, &base->rb_root);
170b145425fSEric Dumazet base->total--;
171b145425fSEric Dumazet call_rcu(&p->rcu, inetpeer_free_rcu);
1724b9d9be8SEric Dumazet }
1734b9d9be8SEric Dumazet }
1746d1a3e04SEric Dumazet }
175d71209deSPavel Emelyanov
inet_getpeer(struct inet_peer_base * base,const struct inetpeer_addr * daddr,int create)176c0efc887SDavid S. Miller struct inet_peer *inet_getpeer(struct inet_peer_base *base,
177c8a627edSGao feng const struct inetpeer_addr *daddr,
178c8a627edSGao feng int create)
1791da177e4SLinus Torvalds {
180b145425fSEric Dumazet struct inet_peer *p, *gc_stack[PEER_MAX_GC];
181b145425fSEric Dumazet struct rb_node **pp, *parent;
182b145425fSEric Dumazet unsigned int gc_cnt, seq;
183b145425fSEric Dumazet int invalidated;
1841da177e4SLinus Torvalds
1854b9d9be8SEric Dumazet /* Attempt a lockless lookup first.
186aa1039e7SEric Dumazet * Because of a concurrent writer, we might not find an existing entry.
187aa1039e7SEric Dumazet */
1887b46ac4eSDavid S. Miller rcu_read_lock();
189b145425fSEric Dumazet seq = read_seqbegin(&base->lock);
190b145425fSEric Dumazet p = lookup(daddr, base, seq, NULL, &gc_cnt, &parent, &pp);
191b145425fSEric Dumazet invalidated = read_seqretry(&base->lock, seq);
1927b46ac4eSDavid S. Miller rcu_read_unlock();
1931da177e4SLinus Torvalds
1944b9d9be8SEric Dumazet if (p)
1951da177e4SLinus Torvalds return p;
1961da177e4SLinus Torvalds
19765e8354eSEric Dumazet /* If no writer did a change during our lookup, we can return early. */
19865e8354eSEric Dumazet if (!create && !invalidated)
19965e8354eSEric Dumazet return NULL;
20065e8354eSEric Dumazet
201aa1039e7SEric Dumazet /* retry an exact lookup, taking the lock before.
202aa1039e7SEric Dumazet * At least, nodes should be hot in our cache.
203aa1039e7SEric Dumazet */
204b145425fSEric Dumazet parent = NULL;
20565e8354eSEric Dumazet write_seqlock_bh(&base->lock);
206b145425fSEric Dumazet
207b145425fSEric Dumazet gc_cnt = 0;
208b145425fSEric Dumazet p = lookup(daddr, base, seq, gc_stack, &gc_cnt, &parent, &pp);
209b145425fSEric Dumazet if (!p && create) {
210b145425fSEric Dumazet p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
211aa1039e7SEric Dumazet if (p) {
212b534ecf1SDavid S. Miller p->daddr = *daddr;
213b6a37e5eSEric Dumazet p->dtime = (__u32)jiffies;
2141cc9a98bSReshetova, Elena refcount_set(&p->refcnt, 2);
215aa1039e7SEric Dumazet atomic_set(&p->rid, 0);
216144001bdSDavid S. Miller p->metrics[RTAX_LOCK-1] = INETPEER_METRICS_NEW;
21792d86829SDavid S. Miller p->rate_tokens = 0;
218c09551c6SLorenzo Bianconi p->n_redirects = 0;
219bc9259a8SNicolas Dichtel /* 60*HZ is arbitrary, but chosen enough high so that the first
220bc9259a8SNicolas Dichtel * calculation of tokens is at its maximum.
221bc9259a8SNicolas Dichtel */
222bc9259a8SNicolas Dichtel p->rate_last = jiffies - 60*HZ;
2231da177e4SLinus Torvalds
224b145425fSEric Dumazet rb_link_node(&p->rb_node, parent, pp);
225b145425fSEric Dumazet rb_insert_color(&p->rb_node, &base->rb_root);
22698158f5aSDavid S. Miller base->total++;
227aa1039e7SEric Dumazet }
228b145425fSEric Dumazet }
229b145425fSEric Dumazet if (gc_cnt)
230b145425fSEric Dumazet inet_peer_gc(base, gc_stack, gc_cnt);
23165e8354eSEric Dumazet write_sequnlock_bh(&base->lock);
2321da177e4SLinus Torvalds
2331da177e4SLinus Torvalds return p;
2341da177e4SLinus Torvalds }
235b3419363SDavid S. Miller EXPORT_SYMBOL_GPL(inet_getpeer);
23698158f5aSDavid S. Miller
inet_putpeer(struct inet_peer * p)2374663afe2SEric Dumazet void inet_putpeer(struct inet_peer *p)
2384663afe2SEric Dumazet {
23971685eb4SEric Dumazet /* The WRITE_ONCE() pairs with itself (we run lockless)
24071685eb4SEric Dumazet * and the READ_ONCE() in inet_peer_gc()
24171685eb4SEric Dumazet */
24271685eb4SEric Dumazet WRITE_ONCE(p->dtime, (__u32)jiffies);
243b145425fSEric Dumazet
244b145425fSEric Dumazet if (refcount_dec_and_test(&p->refcnt))
245b145425fSEric Dumazet call_rcu(&p->rcu, inetpeer_free_rcu);
2464663afe2SEric Dumazet }
247b3419363SDavid S. Miller EXPORT_SYMBOL_GPL(inet_putpeer);
24892d86829SDavid S. Miller
24992d86829SDavid S. Miller /*
25092d86829SDavid S. Miller * Check transmit rate limitation for given message.
25192d86829SDavid S. Miller * The rate information is held in the inet_peer entries now.
25292d86829SDavid S. Miller * This function is generic and could be used for other purposes
25392d86829SDavid S. Miller * too. It uses a Token bucket filter as suggested by Alexey Kuznetsov.
25492d86829SDavid S. Miller *
25592d86829SDavid S. Miller * Note that the same inet_peer fields are modified by functions in
25692d86829SDavid S. Miller * route.c too, but these work for packet destinations while xrlim_allow
25792d86829SDavid S. Miller * works for icmp destinations. This means the rate limiting information
25892d86829SDavid S. Miller * for one "ip object" is shared - and these ICMPs are twice limited:
25992d86829SDavid S. Miller * by source and by destination.
26092d86829SDavid S. Miller *
26192d86829SDavid S. Miller * RFC 1812: 4.3.2.8 SHOULD be able to limit error message rate
26292d86829SDavid S. Miller * SHOULD allow setting of rate limits
26392d86829SDavid S. Miller *
26492d86829SDavid S. Miller * Shared between ICMPv4 and ICMPv6.
26592d86829SDavid S. Miller */
26692d86829SDavid S. Miller #define XRLIM_BURST_FACTOR 6
inet_peer_xrlim_allow(struct inet_peer * peer,int timeout)26792d86829SDavid S. Miller bool inet_peer_xrlim_allow(struct inet_peer *peer, int timeout)
26892d86829SDavid S. Miller {
26992d86829SDavid S. Miller unsigned long now, token;
27092d86829SDavid S. Miller bool rc = false;
27192d86829SDavid S. Miller
27292d86829SDavid S. Miller if (!peer)
27392d86829SDavid S. Miller return true;
27492d86829SDavid S. Miller
27592d86829SDavid S. Miller token = peer->rate_tokens;
27692d86829SDavid S. Miller now = jiffies;
27792d86829SDavid S. Miller token += now - peer->rate_last;
27892d86829SDavid S. Miller peer->rate_last = now;
27992d86829SDavid S. Miller if (token > XRLIM_BURST_FACTOR * timeout)
28092d86829SDavid S. Miller token = XRLIM_BURST_FACTOR * timeout;
28192d86829SDavid S. Miller if (token >= timeout) {
28292d86829SDavid S. Miller token -= timeout;
28392d86829SDavid S. Miller rc = true;
28492d86829SDavid S. Miller }
28592d86829SDavid S. Miller peer->rate_tokens = token;
28692d86829SDavid S. Miller return rc;
28792d86829SDavid S. Miller }
28892d86829SDavid S. Miller EXPORT_SYMBOL(inet_peer_xrlim_allow);
2895faa5df1SSteffen Klassert
inetpeer_invalidate_tree(struct inet_peer_base * base)29056a6b248SDavid S. Miller void inetpeer_invalidate_tree(struct inet_peer_base *base)
2915faa5df1SSteffen Klassert {
2928f1975e3SEric Dumazet struct rb_node *p = rb_first(&base->rb_root);
2935faa5df1SSteffen Klassert
2948f1975e3SEric Dumazet while (p) {
2958f1975e3SEric Dumazet struct inet_peer *peer = rb_entry(p, struct inet_peer, rb_node);
2968f1975e3SEric Dumazet
2978f1975e3SEric Dumazet p = rb_next(p);
2988f1975e3SEric Dumazet rb_erase(&peer->rb_node, &base->rb_root);
2998f1975e3SEric Dumazet inet_putpeer(peer);
300b145425fSEric Dumazet cond_resched();
3015faa5df1SSteffen Klassert }
3025faa5df1SSteffen Klassert
303b145425fSEric Dumazet base->total = 0;
3045faa5df1SSteffen Klassert }
3055faa5df1SSteffen Klassert EXPORT_SYMBOL(inetpeer_invalidate_tree);
306