1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * INETPEER - A storage for permanent information about peers 4 * 5 * Authors: Andrey V. Savochkin <saw@msu.ru> 6 */ 7 8 #include <linux/cache.h> 9 #include <linux/module.h> 10 #include <linux/types.h> 11 #include <linux/slab.h> 12 #include <linux/interrupt.h> 13 #include <linux/spinlock.h> 14 #include <linux/random.h> 15 #include <linux/timer.h> 16 #include <linux/time.h> 17 #include <linux/kernel.h> 18 #include <linux/mm.h> 19 #include <linux/net.h> 20 #include <linux/workqueue.h> 21 #include <net/ip.h> 22 #include <net/inetpeer.h> 23 #include <net/secure_seq.h> 24 #include <linux/siphash.h> 25 26 /* 27 * Theory of operations. 28 * We keep one entry for each peer IP address. The nodes contains long-living 29 * information about the peer which doesn't depend on routes. 30 * 31 * Nodes are removed only when reference counter goes to 0. 32 * When it's happened the node may be removed when a sufficient amount of 33 * time has been passed since its last use. The less-recently-used entry can 34 * also be removed if the pool is overloaded i.e. if the total amount of 35 * entries is greater-or-equal than the threshold. 36 * 37 * Node pool is organised as an RB tree. 38 * Such an implementation has been chosen not just for fun. It's a way to 39 * prevent easy and efficient DoS attacks by creating hash collisions. A huge 40 * amount of long living nodes in a single hash slot would significantly delay 41 * lookups performed with disabled BHs. 42 * 43 * Serialisation issues. 44 * 1. Nodes may appear in the tree only with the pool lock held. 45 * 2. Nodes may disappear from the tree only with the pool lock held 46 * AND reference count being 0. 47 * 3. Global variable peer_total is modified under the pool lock. 48 * 4. struct inet_peer fields modification: 49 * rb_node: pool lock 50 * refcnt: atomically against modifications on other CPU; 51 * usually under some other lock to prevent node disappearing 52 * daddr: unchangeable 53 */ 54 55 static struct kmem_cache *peer_cachep __ro_after_init; 56 static siphash_aligned_key_t inetpeer_hash_key __read_mostly; 57 58 static u64 inetpeer_addr_hash(const struct inetpeer_addr *a) 59 { 60 net_get_random_once(&inetpeer_hash_key, sizeof(inetpeer_hash_key)); 61 62 if (a->family == AF_INET) 63 return siphash_2u32((__force u32)a->a4.addr, a->a4.vif, 64 &inetpeer_hash_key); 65 66 return siphash_4u32((__force u32)a->a6.s6_addr32[0], 67 (__force u32)a->a6.s6_addr32[1], 68 (__force u32)a->a6.s6_addr32[2], 69 (__force u32)a->a6.s6_addr32[3], 70 &inetpeer_hash_key); 71 } 72 73 static int inetpeer_entry_cmp(u64 dhash, 74 const struct inetpeer_addr *daddr, 75 const struct inet_peer *p) 76 { 77 if (dhash < p->hash) 78 return -1; 79 if (dhash > p->hash) 80 return 1; 81 82 return inetpeer_addr_cmp(daddr, &p->daddr); 83 } 84 85 void inet_peer_base_init(struct inet_peer_base *bp) 86 { 87 bp->rb_root = RB_ROOT; 88 seqlock_init(&bp->lock); 89 bp->total = 0; 90 } 91 92 #define PEER_MAX_GC 32 93 94 /* Exported for sysctl_net_ipv4. */ 95 int inet_peer_threshold __read_mostly; /* start to throw entries more 96 * aggressively at this stage */ 97 int inet_peer_minttl __read_mostly = 120 * HZ; /* TTL under high load: 120 sec */ 98 int inet_peer_maxttl __read_mostly = 10 * 60 * HZ; /* usual time to live: 10 min */ 99 100 /* Called from ip_output.c:ip_init */ 101 void __init inet_initpeers(void) 102 { 103 u64 nr_entries; 104 105 /* 1% of physical memory */ 106 nr_entries = div64_ul((u64)totalram_pages() << PAGE_SHIFT, 107 100 * L1_CACHE_ALIGN(sizeof(struct inet_peer))); 108 109 inet_peer_threshold = clamp_val(nr_entries, 4096, 65536 + 128); 110 111 peer_cachep = KMEM_CACHE(inet_peer, SLAB_HWCACHE_ALIGN | SLAB_PANIC); 112 } 113 114 /* Called with rcu_read_lock() or base->lock held */ 115 static struct inet_peer *lookup(const struct inetpeer_addr *daddr, 116 u64 dhash, 117 struct inet_peer_base *base, 118 unsigned int seq, 119 struct inet_peer *gc_stack[], 120 unsigned int *gc_cnt, 121 struct rb_node **parent_p, 122 struct rb_node ***pp_p) 123 { 124 struct rb_node **pp, *parent, *next; 125 struct inet_peer *p; 126 u32 now; 127 128 pp = &base->rb_root.rb_node; 129 parent = NULL; 130 while (1) { 131 int cmp; 132 133 next = rcu_dereference_raw(*pp); 134 if (!next) 135 break; 136 parent = next; 137 p = rb_entry(parent, struct inet_peer, rb_node); 138 cmp = inetpeer_entry_cmp(dhash, daddr, p); 139 if (cmp == 0) { 140 now = jiffies; 141 if (READ_ONCE(p->dtime) != now) 142 WRITE_ONCE(p->dtime, now); 143 return p; 144 } 145 if (gc_stack) { 146 if (*gc_cnt < PEER_MAX_GC) 147 gc_stack[(*gc_cnt)++] = p; 148 } else if (unlikely(read_seqretry(&base->lock, seq))) { 149 break; 150 } 151 if (cmp == -1) 152 pp = &next->rb_left; 153 else 154 pp = &next->rb_right; 155 } 156 *parent_p = parent; 157 *pp_p = pp; 158 return NULL; 159 } 160 161 /* perform garbage collect on all items stacked during a lookup */ 162 static void inet_peer_gc(struct inet_peer_base *base, 163 struct inet_peer *gc_stack[], 164 unsigned int gc_cnt) 165 { 166 int peer_threshold, peer_maxttl, peer_minttl; 167 struct inet_peer *p; 168 __u32 delta, ttl; 169 int i; 170 171 peer_threshold = READ_ONCE(inet_peer_threshold); 172 peer_maxttl = READ_ONCE(inet_peer_maxttl); 173 peer_minttl = READ_ONCE(inet_peer_minttl); 174 175 if (base->total >= peer_threshold) 176 ttl = 0; /* be aggressive */ 177 else 178 ttl = peer_maxttl - (peer_maxttl - peer_minttl) / HZ * 179 base->total / peer_threshold * HZ; 180 for (i = 0; i < gc_cnt; i++) { 181 p = gc_stack[i]; 182 183 delta = (__u32)jiffies - READ_ONCE(p->dtime); 184 185 if (delta < ttl || !refcount_dec_if_one(&p->refcnt)) 186 gc_stack[i] = NULL; 187 } 188 for (i = 0; i < gc_cnt; i++) { 189 p = gc_stack[i]; 190 if (p) { 191 rb_erase(&p->rb_node, &base->rb_root); 192 base->total--; 193 kfree_rcu(p, rcu); 194 } 195 } 196 } 197 198 /* Must be called under RCU : No refcount change is done here. */ 199 struct inet_peer *inet_getpeer(struct inet_peer_base *base, 200 const struct inetpeer_addr *daddr) 201 { 202 struct inet_peer *p, *gc_stack[PEER_MAX_GC]; 203 u64 dhash = inetpeer_addr_hash(daddr); 204 struct rb_node **pp, *parent; 205 unsigned int gc_cnt, seq; 206 207 /* Attempt a lockless lookup first. 208 * Because of a concurrent writer, we might not find an existing entry. 209 */ 210 seq = read_seqbegin(&base->lock); 211 p = lookup(daddr, dhash, base, seq, NULL, &gc_cnt, &parent, &pp); 212 213 /* Make sure tree was not modified during our lookup. */ 214 if (p && !read_seqretry(&base->lock, seq)) 215 return p; 216 217 /* retry an exact lookup, taking the lock before. 218 * At least, nodes should be hot in our cache. 219 */ 220 parent = NULL; 221 write_seqlock_bh(&base->lock); 222 223 gc_cnt = 0; 224 p = lookup(daddr, dhash, base, seq, gc_stack, &gc_cnt, &parent, &pp); 225 if (!p) { 226 p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC); 227 if (p) { 228 p->daddr = *daddr; 229 p->hash = dhash; 230 p->dtime = (__u32)jiffies; 231 refcount_set(&p->refcnt, 1); 232 atomic_set(&p->rid, 0); 233 p->metrics[RTAX_LOCK-1] = INETPEER_METRICS_NEW; 234 p->rate_tokens = 0; 235 p->n_redirects = 0; 236 /* 60*HZ is arbitrary, but chosen enough high so that the first 237 * calculation of tokens is at its maximum. 238 */ 239 p->rate_last = jiffies - 60*HZ; 240 241 rb_link_node(&p->rb_node, parent, pp); 242 rb_insert_color(&p->rb_node, &base->rb_root); 243 base->total++; 244 } 245 } 246 if (gc_cnt) 247 inet_peer_gc(base, gc_stack, gc_cnt); 248 write_sequnlock_bh(&base->lock); 249 250 return p; 251 } 252 253 void inet_putpeer(struct inet_peer *p) 254 { 255 if (refcount_dec_and_test(&p->refcnt)) 256 kfree_rcu(p, rcu); 257 } 258 259 /* 260 * Check transmit rate limitation for given message. 261 * The rate information is held in the inet_peer entries now. 262 * This function is generic and could be used for other purposes 263 * too. It uses a Token bucket filter as suggested by Alexey Kuznetsov. 264 * 265 * Note that the same inet_peer fields are modified by functions in 266 * route.c too, but these work for packet destinations while xrlim_allow 267 * works for icmp destinations. This means the rate limiting information 268 * for one "ip object" is shared - and these ICMPs are twice limited: 269 * by source and by destination. 270 * 271 * RFC 1812: 4.3.2.8 SHOULD be able to limit error message rate 272 * SHOULD allow setting of rate limits 273 * 274 * Shared between ICMPv4 and ICMPv6. 275 */ 276 #define XRLIM_BURST_FACTOR 6 277 bool inet_peer_xrlim_allow(struct inet_peer *peer, int timeout) 278 { 279 unsigned long now, token, otoken, delta; 280 bool rc = false; 281 282 if (!peer) 283 return true; 284 285 token = otoken = READ_ONCE(peer->rate_tokens); 286 now = jiffies; 287 delta = now - READ_ONCE(peer->rate_last); 288 if (delta) { 289 WRITE_ONCE(peer->rate_last, now); 290 token += delta; 291 if (token > XRLIM_BURST_FACTOR * timeout) 292 token = XRLIM_BURST_FACTOR * timeout; 293 } 294 if (token >= timeout) { 295 token -= timeout; 296 rc = true; 297 } 298 if (token != otoken) 299 WRITE_ONCE(peer->rate_tokens, token); 300 return rc; 301 } 302 303 void inetpeer_invalidate_tree(struct inet_peer_base *base) 304 { 305 struct rb_node *p = rb_first(&base->rb_root); 306 307 while (p) { 308 struct inet_peer *peer = rb_entry(p, struct inet_peer, rb_node); 309 310 p = rb_next(p); 311 rb_erase(&peer->rb_node, &base->rb_root); 312 inet_putpeer(peer); 313 cond_resched(); 314 } 315 316 base->total = 0; 317 } 318