inetpeer.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311
  1. /*
  2. * INETPEER - A storage for permanent information about peers
  3. *
  4. * This source is covered by the GNU GPL, the same as all kernel sources.
  5. *
  6. * Authors: Andrey V. Savochkin <saw@msu.ru>
  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. /*
  25. * Theory of operations.
  26. * We keep one entry for each peer IP address. The nodes contains long-living
  27. * information about the peer which doesn't depend on routes.
  28. *
  29. * Nodes are removed only when reference counter goes to 0.
  30. * When it's happened the node may be removed when a sufficient amount of
  31. * time has been passed since its last use. The less-recently-used entry can
  32. * also be removed if the pool is overloaded i.e. if the total amount of
  33. * entries is greater-or-equal than the threshold.
  34. *
  35. * Node pool is organised as an RB tree.
  36. * Such an implementation has been chosen not just for fun. It's a way to
  37. * prevent easy and efficient DoS attacks by creating hash collisions. A huge
  38. * amount of long living nodes in a single hash slot would significantly delay
  39. * lookups performed with disabled BHs.
  40. *
  41. * Serialisation issues.
  42. * 1. Nodes may appear in the tree only with the pool lock held.
  43. * 2. Nodes may disappear from the tree only with the pool lock held
  44. * AND reference count being 0.
  45. * 3. Global variable peer_total is modified under the pool lock.
  46. * 4. struct inet_peer fields modification:
  47. * rb_node: pool lock
  48. * refcnt: atomically against modifications on other CPU;
  49. * usually under some other lock to prevent node disappearing
  50. * daddr: unchangeable
  51. */
  52. static struct kmem_cache *peer_cachep __ro_after_init;
  53. void inet_peer_base_init(struct inet_peer_base *bp)
  54. {
  55. bp->rb_root = RB_ROOT;
  56. seqlock_init(&bp->lock);
  57. bp->total = 0;
  58. }
  59. EXPORT_SYMBOL_GPL(inet_peer_base_init);
  60. #define PEER_MAX_GC 32
  61. /* Exported for sysctl_net_ipv4. */
  62. int inet_peer_threshold __read_mostly = 65536 + 128; /* start to throw entries more
  63. * aggressively at this stage */
  64. int inet_peer_minttl __read_mostly = 120 * HZ; /* TTL under high load: 120 sec */
  65. int inet_peer_maxttl __read_mostly = 10 * 60 * HZ; /* usual time to live: 10 min */
  66. /* Called from ip_output.c:ip_init */
  67. void __init inet_initpeers(void)
  68. {
  69. struct sysinfo si;
  70. /* Use the straight interface to information about memory. */
  71. si_meminfo(&si);
  72. /* The values below were suggested by Alexey Kuznetsov
  73. * <kuznet@ms2.inr.ac.ru>. I don't have any opinion about the values
  74. * myself. --SAW
  75. */
  76. if (si.totalram <= (32768*1024)/PAGE_SIZE)
  77. inet_peer_threshold >>= 1; /* max pool size about 1MB on IA32 */
  78. if (si.totalram <= (16384*1024)/PAGE_SIZE)
  79. inet_peer_threshold >>= 1; /* about 512KB */
  80. if (si.totalram <= (8192*1024)/PAGE_SIZE)
  81. inet_peer_threshold >>= 2; /* about 128KB */
  82. peer_cachep = kmem_cache_create("inet_peer_cache",
  83. sizeof(struct inet_peer),
  84. 0, SLAB_HWCACHE_ALIGN | SLAB_PANIC,
  85. NULL);
  86. }
  87. /* Called with rcu_read_lock() or base->lock held */
  88. static struct inet_peer *lookup(const struct inetpeer_addr *daddr,
  89. struct inet_peer_base *base,
  90. unsigned int seq,
  91. struct inet_peer *gc_stack[],
  92. unsigned int *gc_cnt,
  93. struct rb_node **parent_p,
  94. struct rb_node ***pp_p)
  95. {
  96. struct rb_node **pp, *parent, *next;
  97. struct inet_peer *p;
  98. pp = &base->rb_root.rb_node;
  99. parent = NULL;
  100. while (1) {
  101. int cmp;
  102. next = rcu_dereference_raw(*pp);
  103. if (!next)
  104. break;
  105. parent = next;
  106. p = rb_entry(parent, struct inet_peer, rb_node);
  107. cmp = inetpeer_addr_cmp(daddr, &p->daddr);
  108. if (cmp == 0) {
  109. if (!refcount_inc_not_zero(&p->refcnt))
  110. break;
  111. return p;
  112. }
  113. if (gc_stack) {
  114. if (*gc_cnt < PEER_MAX_GC)
  115. gc_stack[(*gc_cnt)++] = p;
  116. } else if (unlikely(read_seqretry(&base->lock, seq))) {
  117. break;
  118. }
  119. if (cmp == -1)
  120. pp = &next->rb_left;
  121. else
  122. pp = &next->rb_right;
  123. }
  124. *parent_p = parent;
  125. *pp_p = pp;
  126. return NULL;
  127. }
  128. static void inetpeer_free_rcu(struct rcu_head *head)
  129. {
  130. kmem_cache_free(peer_cachep, container_of(head, struct inet_peer, rcu));
  131. }
  132. /* perform garbage collect on all items stacked during a lookup */
  133. static void inet_peer_gc(struct inet_peer_base *base,
  134. struct inet_peer *gc_stack[],
  135. unsigned int gc_cnt)
  136. {
  137. struct inet_peer *p;
  138. __u32 delta, ttl;
  139. int i;
  140. if (base->total >= inet_peer_threshold)
  141. ttl = 0; /* be aggressive */
  142. else
  143. ttl = inet_peer_maxttl
  144. - (inet_peer_maxttl - inet_peer_minttl) / HZ *
  145. base->total / inet_peer_threshold * HZ;
  146. for (i = 0; i < gc_cnt; i++) {
  147. p = gc_stack[i];
  148. /* The READ_ONCE() pairs with the WRITE_ONCE()
  149. * in inet_putpeer()
  150. */
  151. delta = (__u32)jiffies - READ_ONCE(p->dtime);
  152. if (delta < ttl || !refcount_dec_if_one(&p->refcnt))
  153. gc_stack[i] = NULL;
  154. }
  155. for (i = 0; i < gc_cnt; i++) {
  156. p = gc_stack[i];
  157. if (p) {
  158. rb_erase(&p->rb_node, &base->rb_root);
  159. base->total--;
  160. call_rcu(&p->rcu, inetpeer_free_rcu);
  161. }
  162. }
  163. }
  164. struct inet_peer *inet_getpeer(struct inet_peer_base *base,
  165. const struct inetpeer_addr *daddr,
  166. int create)
  167. {
  168. struct inet_peer *p, *gc_stack[PEER_MAX_GC];
  169. struct rb_node **pp, *parent;
  170. unsigned int gc_cnt, seq;
  171. int invalidated;
  172. /* Attempt a lockless lookup first.
  173. * Because of a concurrent writer, we might not find an existing entry.
  174. */
  175. rcu_read_lock();
  176. seq = read_seqbegin(&base->lock);
  177. p = lookup(daddr, base, seq, NULL, &gc_cnt, &parent, &pp);
  178. invalidated = read_seqretry(&base->lock, seq);
  179. rcu_read_unlock();
  180. if (p)
  181. return p;
  182. /* If no writer did a change during our lookup, we can return early. */
  183. if (!create && !invalidated)
  184. return NULL;
  185. /* retry an exact lookup, taking the lock before.
  186. * At least, nodes should be hot in our cache.
  187. */
  188. parent = NULL;
  189. write_seqlock_bh(&base->lock);
  190. gc_cnt = 0;
  191. p = lookup(daddr, base, seq, gc_stack, &gc_cnt, &parent, &pp);
  192. if (!p && create) {
  193. p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
  194. if (p) {
  195. p->daddr = *daddr;
  196. p->dtime = (__u32)jiffies;
  197. refcount_set(&p->refcnt, 2);
  198. atomic_set(&p->rid, 0);
  199. p->metrics[RTAX_LOCK-1] = INETPEER_METRICS_NEW;
  200. p->rate_tokens = 0;
  201. p->n_redirects = 0;
  202. /* 60*HZ is arbitrary, but chosen enough high so that the first
  203. * calculation of tokens is at its maximum.
  204. */
  205. p->rate_last = jiffies - 60*HZ;
  206. rb_link_node(&p->rb_node, parent, pp);
  207. rb_insert_color(&p->rb_node, &base->rb_root);
  208. base->total++;
  209. }
  210. }
  211. if (gc_cnt)
  212. inet_peer_gc(base, gc_stack, gc_cnt);
  213. write_sequnlock_bh(&base->lock);
  214. return p;
  215. }
  216. EXPORT_SYMBOL_GPL(inet_getpeer);
  217. void inet_putpeer(struct inet_peer *p)
  218. {
  219. /* The WRITE_ONCE() pairs with itself (we run lockless)
  220. * and the READ_ONCE() in inet_peer_gc()
  221. */
  222. WRITE_ONCE(p->dtime, (__u32)jiffies);
  223. if (refcount_dec_and_test(&p->refcnt))
  224. call_rcu(&p->rcu, inetpeer_free_rcu);
  225. }
  226. EXPORT_SYMBOL_GPL(inet_putpeer);
  227. /*
  228. * Check transmit rate limitation for given message.
  229. * The rate information is held in the inet_peer entries now.
  230. * This function is generic and could be used for other purposes
  231. * too. It uses a Token bucket filter as suggested by Alexey Kuznetsov.
  232. *
  233. * Note that the same inet_peer fields are modified by functions in
  234. * route.c too, but these work for packet destinations while xrlim_allow
  235. * works for icmp destinations. This means the rate limiting information
  236. * for one "ip object" is shared - and these ICMPs are twice limited:
  237. * by source and by destination.
  238. *
  239. * RFC 1812: 4.3.2.8 SHOULD be able to limit error message rate
  240. * SHOULD allow setting of rate limits
  241. *
  242. * Shared between ICMPv4 and ICMPv6.
  243. */
  244. #define XRLIM_BURST_FACTOR 6
  245. bool inet_peer_xrlim_allow(struct inet_peer *peer, int timeout)
  246. {
  247. unsigned long now, token;
  248. bool rc = false;
  249. if (!peer)
  250. return true;
  251. token = peer->rate_tokens;
  252. now = jiffies;
  253. token += now - peer->rate_last;
  254. peer->rate_last = now;
  255. if (token > XRLIM_BURST_FACTOR * timeout)
  256. token = XRLIM_BURST_FACTOR * timeout;
  257. if (token >= timeout) {
  258. token -= timeout;
  259. rc = true;
  260. }
  261. peer->rate_tokens = token;
  262. return rc;
  263. }
  264. EXPORT_SYMBOL(inet_peer_xrlim_allow);
  265. void inetpeer_invalidate_tree(struct inet_peer_base *base)
  266. {
  267. struct rb_node *p = rb_first(&base->rb_root);
  268. while (p) {
  269. struct inet_peer *peer = rb_entry(p, struct inet_peer, rb_node);
  270. p = rb_next(p);
  271. rb_erase(&peer->rb_node, &base->rb_root);
  272. inet_putpeer(peer);
  273. cond_resched();
  274. }
  275. base->total = 0;
  276. }
  277. EXPORT_SYMBOL(inetpeer_invalidate_tree);