inet_fragment.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437
  1. /*
  2. * inet fragments management
  3. *
  4. * This program is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU General Public License
  6. * as published by the Free Software Foundation; either version
  7. * 2 of the License, or (at your option) any later version.
  8. *
  9. * Authors: Pavel Emelyanov <xemul@openvz.org>
  10. * Started as consolidation of ipv4/ip_fragment.c,
  11. * ipv6/reassembly. and ipv6 nf conntrack reassembly
  12. */
  13. #include <linux/list.h>
  14. #include <linux/spinlock.h>
  15. #include <linux/module.h>
  16. #include <linux/timer.h>
  17. #include <linux/mm.h>
  18. #include <linux/random.h>
  19. #include <linux/skbuff.h>
  20. #include <linux/rtnetlink.h>
  21. #include <linux/slab.h>
  22. #include <net/sock.h>
  23. #include <net/inet_frag.h>
  24. #include <net/inet_ecn.h>
  25. #define INETFRAGS_EVICT_BUCKETS 128
  26. #define INETFRAGS_EVICT_MAX 512
  27. /* don't rebuild inetfrag table with new secret more often than this */
  28. #define INETFRAGS_MIN_REBUILD_INTERVAL (5 * HZ)
  29. /* Given the OR values of all fragments, apply RFC 3168 5.3 requirements
  30. * Value : 0xff if frame should be dropped.
  31. * 0 or INET_ECN_CE value, to be ORed in to final iph->tos field
  32. */
  33. const u8 ip_frag_ecn_table[16] = {
  34. /* at least one fragment had CE, and others ECT_0 or ECT_1 */
  35. [IPFRAG_ECN_CE | IPFRAG_ECN_ECT_0] = INET_ECN_CE,
  36. [IPFRAG_ECN_CE | IPFRAG_ECN_ECT_1] = INET_ECN_CE,
  37. [IPFRAG_ECN_CE | IPFRAG_ECN_ECT_0 | IPFRAG_ECN_ECT_1] = INET_ECN_CE,
  38. /* invalid combinations : drop frame */
  39. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_CE] = 0xff,
  40. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_ECT_0] = 0xff,
  41. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_ECT_1] = 0xff,
  42. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_ECT_0 | IPFRAG_ECN_ECT_1] = 0xff,
  43. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_CE | IPFRAG_ECN_ECT_0] = 0xff,
  44. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_CE | IPFRAG_ECN_ECT_1] = 0xff,
  45. [IPFRAG_ECN_NOT_ECT | IPFRAG_ECN_CE | IPFRAG_ECN_ECT_0 | IPFRAG_ECN_ECT_1] = 0xff,
  46. };
  47. EXPORT_SYMBOL(ip_frag_ecn_table);
  48. static unsigned int
  49. inet_frag_hashfn(const struct inet_frags *f, const struct inet_frag_queue *q)
  50. {
  51. return f->hashfn(q) & (INETFRAGS_HASHSZ - 1);
  52. }
  53. static bool inet_frag_may_rebuild(struct inet_frags *f)
  54. {
  55. return time_after(jiffies,
  56. f->last_rebuild_jiffies + INETFRAGS_MIN_REBUILD_INTERVAL);
  57. }
  58. static void inet_frag_secret_rebuild(struct inet_frags *f)
  59. {
  60. int i;
  61. write_seqlock_bh(&f->rnd_seqlock);
  62. if (!inet_frag_may_rebuild(f))
  63. goto out;
  64. get_random_bytes(&f->rnd, sizeof(u32));
  65. for (i = 0; i < INETFRAGS_HASHSZ; i++) {
  66. struct inet_frag_bucket *hb;
  67. struct inet_frag_queue *q;
  68. struct hlist_node *n;
  69. hb = &f->hash[i];
  70. spin_lock(&hb->chain_lock);
  71. hlist_for_each_entry_safe(q, n, &hb->chain, list) {
  72. unsigned int hval = inet_frag_hashfn(f, q);
  73. if (hval != i) {
  74. struct inet_frag_bucket *hb_dest;
  75. hlist_del(&q->list);
  76. /* Relink to new hash chain. */
  77. hb_dest = &f->hash[hval];
  78. /* This is the only place where we take
  79. * another chain_lock while already holding
  80. * one. As this will not run concurrently,
  81. * we cannot deadlock on hb_dest lock below, if its
  82. * already locked it will be released soon since
  83. * other caller cannot be waiting for hb lock
  84. * that we've taken above.
  85. */
  86. spin_lock_nested(&hb_dest->chain_lock,
  87. SINGLE_DEPTH_NESTING);
  88. hlist_add_head(&q->list, &hb_dest->chain);
  89. spin_unlock(&hb_dest->chain_lock);
  90. }
  91. }
  92. spin_unlock(&hb->chain_lock);
  93. }
  94. f->rebuild = false;
  95. f->last_rebuild_jiffies = jiffies;
  96. out:
  97. write_sequnlock_bh(&f->rnd_seqlock);
  98. }
  99. static bool inet_fragq_should_evict(const struct inet_frag_queue *q)
  100. {
  101. return q->net->low_thresh == 0 ||
  102. frag_mem_limit(q->net) >= q->net->low_thresh;
  103. }
  104. static unsigned int
  105. inet_evict_bucket(struct inet_frags *f, struct inet_frag_bucket *hb)
  106. {
  107. struct inet_frag_queue *fq;
  108. struct hlist_node *n;
  109. unsigned int evicted = 0;
  110. HLIST_HEAD(expired);
  111. spin_lock(&hb->chain_lock);
  112. hlist_for_each_entry_safe(fq, n, &hb->chain, list) {
  113. if (!inet_fragq_should_evict(fq))
  114. continue;
  115. if (!del_timer(&fq->timer))
  116. continue;
  117. hlist_add_head(&fq->list_evictor, &expired);
  118. ++evicted;
  119. }
  120. spin_unlock(&hb->chain_lock);
  121. hlist_for_each_entry_safe(fq, n, &expired, list_evictor)
  122. f->frag_expire((unsigned long) fq);
  123. return evicted;
  124. }
  125. static void inet_frag_worker(struct work_struct *work)
  126. {
  127. unsigned int budget = INETFRAGS_EVICT_BUCKETS;
  128. unsigned int i, evicted = 0;
  129. struct inet_frags *f;
  130. f = container_of(work, struct inet_frags, frags_work);
  131. BUILD_BUG_ON(INETFRAGS_EVICT_BUCKETS >= INETFRAGS_HASHSZ);
  132. local_bh_disable();
  133. for (i = ACCESS_ONCE(f->next_bucket); budget; --budget) {
  134. evicted += inet_evict_bucket(f, &f->hash[i]);
  135. i = (i + 1) & (INETFRAGS_HASHSZ - 1);
  136. if (evicted > INETFRAGS_EVICT_MAX)
  137. break;
  138. }
  139. f->next_bucket = i;
  140. local_bh_enable();
  141. if (f->rebuild && inet_frag_may_rebuild(f))
  142. inet_frag_secret_rebuild(f);
  143. }
  144. static void inet_frag_schedule_worker(struct inet_frags *f)
  145. {
  146. if (unlikely(!work_pending(&f->frags_work)))
  147. schedule_work(&f->frags_work);
  148. }
  149. int inet_frags_init(struct inet_frags *f)
  150. {
  151. int i;
  152. INIT_WORK(&f->frags_work, inet_frag_worker);
  153. for (i = 0; i < INETFRAGS_HASHSZ; i++) {
  154. struct inet_frag_bucket *hb = &f->hash[i];
  155. spin_lock_init(&hb->chain_lock);
  156. INIT_HLIST_HEAD(&hb->chain);
  157. }
  158. seqlock_init(&f->rnd_seqlock);
  159. f->last_rebuild_jiffies = 0;
  160. f->frags_cachep = kmem_cache_create(f->frags_cache_name, f->qsize, 0, 0,
  161. NULL);
  162. if (!f->frags_cachep)
  163. return -ENOMEM;
  164. return 0;
  165. }
  166. EXPORT_SYMBOL(inet_frags_init);
  167. void inet_frags_fini(struct inet_frags *f)
  168. {
  169. cancel_work_sync(&f->frags_work);
  170. kmem_cache_destroy(f->frags_cachep);
  171. }
  172. EXPORT_SYMBOL(inet_frags_fini);
  173. void inet_frags_exit_net(struct netns_frags *nf, struct inet_frags *f)
  174. {
  175. unsigned int seq;
  176. int i;
  177. nf->low_thresh = 0;
  178. evict_again:
  179. local_bh_disable();
  180. seq = read_seqbegin(&f->rnd_seqlock);
  181. for (i = 0; i < INETFRAGS_HASHSZ ; i++)
  182. inet_evict_bucket(f, &f->hash[i]);
  183. local_bh_enable();
  184. cond_resched();
  185. if (read_seqretry(&f->rnd_seqlock, seq) ||
  186. sum_frag_mem_limit(nf))
  187. goto evict_again;
  188. }
  189. EXPORT_SYMBOL(inet_frags_exit_net);
  190. static struct inet_frag_bucket *
  191. get_frag_bucket_locked(struct inet_frag_queue *fq, struct inet_frags *f)
  192. __acquires(hb->chain_lock)
  193. {
  194. struct inet_frag_bucket *hb;
  195. unsigned int seq, hash;
  196. restart:
  197. seq = read_seqbegin(&f->rnd_seqlock);
  198. hash = inet_frag_hashfn(f, fq);
  199. hb = &f->hash[hash];
  200. spin_lock(&hb->chain_lock);
  201. if (read_seqretry(&f->rnd_seqlock, seq)) {
  202. spin_unlock(&hb->chain_lock);
  203. goto restart;
  204. }
  205. return hb;
  206. }
  207. static inline void fq_unlink(struct inet_frag_queue *fq, struct inet_frags *f)
  208. {
  209. struct inet_frag_bucket *hb;
  210. hb = get_frag_bucket_locked(fq, f);
  211. hlist_del(&fq->list);
  212. fq->flags |= INET_FRAG_COMPLETE;
  213. spin_unlock(&hb->chain_lock);
  214. }
  215. void inet_frag_kill(struct inet_frag_queue *fq, struct inet_frags *f)
  216. {
  217. if (del_timer(&fq->timer))
  218. atomic_dec(&fq->refcnt);
  219. if (!(fq->flags & INET_FRAG_COMPLETE)) {
  220. fq_unlink(fq, f);
  221. atomic_dec(&fq->refcnt);
  222. }
  223. }
  224. EXPORT_SYMBOL(inet_frag_kill);
  225. void inet_frag_destroy(struct inet_frag_queue *q, struct inet_frags *f)
  226. {
  227. struct sk_buff *fp;
  228. struct netns_frags *nf;
  229. unsigned int sum, sum_truesize = 0;
  230. WARN_ON(!(q->flags & INET_FRAG_COMPLETE));
  231. WARN_ON(del_timer(&q->timer) != 0);
  232. /* Release all fragment data. */
  233. fp = q->fragments;
  234. nf = q->net;
  235. while (fp) {
  236. struct sk_buff *xp = fp->next;
  237. sum_truesize += fp->truesize;
  238. kfree_skb(fp);
  239. fp = xp;
  240. }
  241. sum = sum_truesize + f->qsize;
  242. if (f->destructor)
  243. f->destructor(q);
  244. kmem_cache_free(f->frags_cachep, q);
  245. sub_frag_mem_limit(nf, sum);
  246. }
  247. EXPORT_SYMBOL(inet_frag_destroy);
  248. static struct inet_frag_queue *inet_frag_intern(struct netns_frags *nf,
  249. struct inet_frag_queue *qp_in,
  250. struct inet_frags *f,
  251. void *arg)
  252. {
  253. struct inet_frag_bucket *hb = get_frag_bucket_locked(qp_in, f);
  254. struct inet_frag_queue *qp;
  255. #ifdef CONFIG_SMP
  256. /* With SMP race we have to recheck hash table, because
  257. * such entry could have been created on other cpu before
  258. * we acquired hash bucket lock.
  259. */
  260. hlist_for_each_entry(qp, &hb->chain, list) {
  261. if (qp->net == nf && f->match(qp, arg)) {
  262. atomic_inc(&qp->refcnt);
  263. spin_unlock(&hb->chain_lock);
  264. qp_in->flags |= INET_FRAG_COMPLETE;
  265. inet_frag_put(qp_in, f);
  266. return qp;
  267. }
  268. }
  269. #endif
  270. qp = qp_in;
  271. if (!mod_timer(&qp->timer, jiffies + nf->timeout))
  272. atomic_inc(&qp->refcnt);
  273. atomic_inc(&qp->refcnt);
  274. hlist_add_head(&qp->list, &hb->chain);
  275. spin_unlock(&hb->chain_lock);
  276. return qp;
  277. }
  278. static struct inet_frag_queue *inet_frag_alloc(struct netns_frags *nf,
  279. struct inet_frags *f,
  280. void *arg)
  281. {
  282. struct inet_frag_queue *q;
  283. if (!nf->high_thresh || frag_mem_limit(nf) > nf->high_thresh) {
  284. inet_frag_schedule_worker(f);
  285. return NULL;
  286. }
  287. q = kmem_cache_zalloc(f->frags_cachep, GFP_ATOMIC);
  288. if (!q)
  289. return NULL;
  290. q->net = nf;
  291. f->constructor(q, arg);
  292. add_frag_mem_limit(nf, f->qsize);
  293. setup_timer(&q->timer, f->frag_expire, (unsigned long)q);
  294. spin_lock_init(&q->lock);
  295. atomic_set(&q->refcnt, 1);
  296. return q;
  297. }
  298. static struct inet_frag_queue *inet_frag_create(struct netns_frags *nf,
  299. struct inet_frags *f,
  300. void *arg)
  301. {
  302. struct inet_frag_queue *q;
  303. q = inet_frag_alloc(nf, f, arg);
  304. if (!q)
  305. return NULL;
  306. return inet_frag_intern(nf, q, f, arg);
  307. }
  308. struct inet_frag_queue *inet_frag_find(struct netns_frags *nf,
  309. struct inet_frags *f, void *key,
  310. unsigned int hash)
  311. {
  312. struct inet_frag_bucket *hb;
  313. struct inet_frag_queue *q;
  314. int depth = 0;
  315. if (frag_mem_limit(nf) > nf->low_thresh)
  316. inet_frag_schedule_worker(f);
  317. hash &= (INETFRAGS_HASHSZ - 1);
  318. hb = &f->hash[hash];
  319. spin_lock(&hb->chain_lock);
  320. hlist_for_each_entry(q, &hb->chain, list) {
  321. if (q->net == nf && f->match(q, key)) {
  322. atomic_inc(&q->refcnt);
  323. spin_unlock(&hb->chain_lock);
  324. return q;
  325. }
  326. depth++;
  327. }
  328. spin_unlock(&hb->chain_lock);
  329. if (depth <= INETFRAGS_MAXDEPTH)
  330. return inet_frag_create(nf, f, key);
  331. if (inet_frag_may_rebuild(f)) {
  332. if (!f->rebuild)
  333. f->rebuild = true;
  334. inet_frag_schedule_worker(f);
  335. }
  336. return ERR_PTR(-ENOBUFS);
  337. }
  338. EXPORT_SYMBOL(inet_frag_find);
  339. void inet_frag_maybe_warn_overflow(struct inet_frag_queue *q,
  340. const char *prefix)
  341. {
  342. static const char msg[] = "inet_frag_find: Fragment hash bucket"
  343. " list length grew over limit " __stringify(INETFRAGS_MAXDEPTH)
  344. ". Dropping fragment.\n";
  345. if (PTR_ERR(q) == -ENOBUFS)
  346. net_dbg_ratelimited("%s%s", prefix, msg);
  347. }
  348. EXPORT_SYMBOL(inet_frag_maybe_warn_overflow);