2 * inet fragments management
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.
9 * Authors: Pavel Emelyanov <xemul@openvz.org>
10 * Started as consolidation of ipv4/ip_fragment.c,
11 * ipv6/reassembly. and ipv6 nf conntrack reassembly
14 #include <linux/list.h>
15 #include <linux/spinlock.h>
16 #include <linux/module.h>
17 #include <linux/timer.h>
19 #include <linux/random.h>
20 #include <linux/skbuff.h>
21 #include <linux/rtnetlink.h>
22 #include <linux/slab.h>
25 #include <net/inet_frag.h>
26 #include <net/inet_ecn.h>
28 #define INETFRAGS_EVICT_BUCKETS 128
29 #define INETFRAGS_EVICT_MAX 512
31 /* don't rebuild inetfrag table with new secret more often than this */
32 #define INETFRAGS_MIN_REBUILD_INTERVAL (5 * HZ)
34 /* Given the OR values of all fragments, apply RFC 3168 5.3 requirements
35 * Value : 0xff if frame should be dropped.
36 * 0 or INET_ECN_CE value, to be ORed in to final iph->tos field
38 const u8 ip_frag_ecn_table
[16] = {
39 /* at least one fragment had CE, and others ECT_0 or ECT_1 */
40 [IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_0
] = INET_ECN_CE
,
41 [IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_1
] = INET_ECN_CE
,
42 [IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_0
| IPFRAG_ECN_ECT_1
] = INET_ECN_CE
,
44 /* invalid combinations : drop frame */
45 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_CE
] = 0xff,
46 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_ECT_0
] = 0xff,
47 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_ECT_1
] = 0xff,
48 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_ECT_0
| IPFRAG_ECN_ECT_1
] = 0xff,
49 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_0
] = 0xff,
50 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_1
] = 0xff,
51 [IPFRAG_ECN_NOT_ECT
| IPFRAG_ECN_CE
| IPFRAG_ECN_ECT_0
| IPFRAG_ECN_ECT_1
] = 0xff,
53 EXPORT_SYMBOL(ip_frag_ecn_table
);
56 inet_frag_hashfn(const struct inet_frags
*f
, const struct inet_frag_queue
*q
)
58 return f
->hashfn(q
) & (INETFRAGS_HASHSZ
- 1);
61 static bool inet_frag_may_rebuild(struct inet_frags
*f
)
63 return time_after(jiffies
,
64 f
->last_rebuild_jiffies
+ INETFRAGS_MIN_REBUILD_INTERVAL
);
67 static void inet_frag_secret_rebuild(struct inet_frags
*f
)
71 write_seqlock_bh(&f
->rnd_seqlock
);
73 if (!inet_frag_may_rebuild(f
))
76 get_random_bytes(&f
->rnd
, sizeof(u32
));
78 for (i
= 0; i
< INETFRAGS_HASHSZ
; i
++) {
79 struct inet_frag_bucket
*hb
;
80 struct inet_frag_queue
*q
;
84 spin_lock(&hb
->chain_lock
);
86 hlist_for_each_entry_safe(q
, n
, &hb
->chain
, list
) {
87 unsigned int hval
= inet_frag_hashfn(f
, q
);
90 struct inet_frag_bucket
*hb_dest
;
94 /* Relink to new hash chain. */
95 hb_dest
= &f
->hash
[hval
];
97 /* This is the only place where we take
98 * another chain_lock while already holding
99 * one. As this will not run concurrently,
100 * we cannot deadlock on hb_dest lock below, if its
101 * already locked it will be released soon since
102 * other caller cannot be waiting for hb lock
103 * that we've taken above.
105 spin_lock_nested(&hb_dest
->chain_lock
,
106 SINGLE_DEPTH_NESTING
);
107 hlist_add_head(&q
->list
, &hb_dest
->chain
);
108 spin_unlock(&hb_dest
->chain_lock
);
111 spin_unlock(&hb
->chain_lock
);
115 f
->last_rebuild_jiffies
= jiffies
;
117 write_sequnlock_bh(&f
->rnd_seqlock
);
120 static bool inet_fragq_should_evict(const struct inet_frag_queue
*q
)
122 return q
->net
->low_thresh
== 0 ||
123 frag_mem_limit(q
->net
) >= q
->net
->low_thresh
;
127 inet_evict_bucket(struct inet_frags
*f
, struct inet_frag_bucket
*hb
)
129 struct inet_frag_queue
*fq
;
130 struct hlist_node
*n
;
131 unsigned int evicted
= 0;
135 spin_lock(&hb
->chain_lock
);
137 hlist_for_each_entry_safe(fq
, n
, &hb
->chain
, list
) {
138 if (!inet_fragq_should_evict(fq
))
141 if (!del_timer(&fq
->timer
)) {
142 /* q expiring right now thus increment its refcount so
143 * it won't be freed under us and wait until the timer
144 * has finished executing then destroy it
146 atomic_inc(&fq
->refcnt
);
147 spin_unlock(&hb
->chain_lock
);
148 del_timer_sync(&fq
->timer
);
149 inet_frag_put(fq
, f
);
153 fq
->flags
|= INET_FRAG_EVICTED
;
154 hlist_add_head(&fq
->list_evictor
, &expired
);
158 spin_unlock(&hb
->chain_lock
);
160 hlist_for_each_entry_safe(fq
, n
, &expired
, list_evictor
)
161 f
->frag_expire((unsigned long) fq
);
166 static void inet_frag_worker(struct work_struct
*work
)
168 unsigned int budget
= INETFRAGS_EVICT_BUCKETS
;
169 unsigned int i
, evicted
= 0;
170 struct inet_frags
*f
;
172 f
= container_of(work
, struct inet_frags
, frags_work
);
174 BUILD_BUG_ON(INETFRAGS_EVICT_BUCKETS
>= INETFRAGS_HASHSZ
);
178 for (i
= ACCESS_ONCE(f
->next_bucket
); budget
; --budget
) {
179 evicted
+= inet_evict_bucket(f
, &f
->hash
[i
]);
180 i
= (i
+ 1) & (INETFRAGS_HASHSZ
- 1);
181 if (evicted
> INETFRAGS_EVICT_MAX
)
189 if (f
->rebuild
&& inet_frag_may_rebuild(f
))
190 inet_frag_secret_rebuild(f
);
193 static void inet_frag_schedule_worker(struct inet_frags
*f
)
195 if (unlikely(!work_pending(&f
->frags_work
)))
196 schedule_work(&f
->frags_work
);
199 int inet_frags_init(struct inet_frags
*f
)
203 INIT_WORK(&f
->frags_work
, inet_frag_worker
);
205 for (i
= 0; i
< INETFRAGS_HASHSZ
; i
++) {
206 struct inet_frag_bucket
*hb
= &f
->hash
[i
];
208 spin_lock_init(&hb
->chain_lock
);
209 INIT_HLIST_HEAD(&hb
->chain
);
212 seqlock_init(&f
->rnd_seqlock
);
213 f
->last_rebuild_jiffies
= 0;
214 f
->frags_cachep
= kmem_cache_create(f
->frags_cache_name
, f
->qsize
, 0, 0,
216 if (!f
->frags_cachep
)
221 EXPORT_SYMBOL(inet_frags_init
);
223 void inet_frags_init_net(struct netns_frags
*nf
)
225 init_frag_mem_limit(nf
);
227 EXPORT_SYMBOL(inet_frags_init_net
);
229 void inet_frags_fini(struct inet_frags
*f
)
231 cancel_work_sync(&f
->frags_work
);
232 kmem_cache_destroy(f
->frags_cachep
);
234 EXPORT_SYMBOL(inet_frags_fini
);
236 void inet_frags_exit_net(struct netns_frags
*nf
, struct inet_frags
*f
)
245 seq
= read_seqbegin(&f
->rnd_seqlock
);
247 for (i
= 0; i
< INETFRAGS_HASHSZ
; i
++)
248 inet_evict_bucket(f
, &f
->hash
[i
]);
250 if (read_seqretry(&f
->rnd_seqlock
, seq
))
255 percpu_counter_destroy(&nf
->mem
);
257 EXPORT_SYMBOL(inet_frags_exit_net
);
259 static struct inet_frag_bucket
*
260 get_frag_bucket_locked(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
261 __acquires(hb
->chain_lock
)
263 struct inet_frag_bucket
*hb
;
264 unsigned int seq
, hash
;
267 seq
= read_seqbegin(&f
->rnd_seqlock
);
269 hash
= inet_frag_hashfn(f
, fq
);
272 spin_lock(&hb
->chain_lock
);
273 if (read_seqretry(&f
->rnd_seqlock
, seq
)) {
274 spin_unlock(&hb
->chain_lock
);
281 static inline void fq_unlink(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
283 struct inet_frag_bucket
*hb
;
285 hb
= get_frag_bucket_locked(fq
, f
);
286 hlist_del(&fq
->list
);
287 spin_unlock(&hb
->chain_lock
);
290 void inet_frag_kill(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
292 if (del_timer(&fq
->timer
))
293 atomic_dec(&fq
->refcnt
);
295 if (!(fq
->flags
& INET_FRAG_COMPLETE
)) {
297 atomic_dec(&fq
->refcnt
);
298 fq
->flags
|= INET_FRAG_COMPLETE
;
301 EXPORT_SYMBOL(inet_frag_kill
);
303 static inline void frag_kfree_skb(struct netns_frags
*nf
, struct inet_frags
*f
,
311 void inet_frag_destroy(struct inet_frag_queue
*q
, struct inet_frags
*f
)
314 struct netns_frags
*nf
;
315 unsigned int sum
, sum_truesize
= 0;
317 WARN_ON(!(q
->flags
& INET_FRAG_COMPLETE
));
318 WARN_ON(del_timer(&q
->timer
) != 0);
320 /* Release all fragment data. */
324 struct sk_buff
*xp
= fp
->next
;
326 sum_truesize
+= fp
->truesize
;
327 frag_kfree_skb(nf
, f
, fp
);
330 sum
= sum_truesize
+ f
->qsize
;
331 sub_frag_mem_limit(q
, sum
);
335 kmem_cache_free(f
->frags_cachep
, q
);
337 EXPORT_SYMBOL(inet_frag_destroy
);
339 static struct inet_frag_queue
*inet_frag_intern(struct netns_frags
*nf
,
340 struct inet_frag_queue
*qp_in
,
341 struct inet_frags
*f
,
344 struct inet_frag_bucket
*hb
= get_frag_bucket_locked(qp_in
, f
);
345 struct inet_frag_queue
*qp
;
348 /* With SMP race we have to recheck hash table, because
349 * such entry could have been created on other cpu before
350 * we acquired hash bucket lock.
352 hlist_for_each_entry(qp
, &hb
->chain
, list
) {
353 if (qp
->net
== nf
&& f
->match(qp
, arg
)) {
354 atomic_inc(&qp
->refcnt
);
355 spin_unlock(&hb
->chain_lock
);
356 qp_in
->flags
|= INET_FRAG_COMPLETE
;
357 inet_frag_put(qp_in
, f
);
363 if (!mod_timer(&qp
->timer
, jiffies
+ nf
->timeout
))
364 atomic_inc(&qp
->refcnt
);
366 atomic_inc(&qp
->refcnt
);
367 hlist_add_head(&qp
->list
, &hb
->chain
);
369 spin_unlock(&hb
->chain_lock
);
374 static struct inet_frag_queue
*inet_frag_alloc(struct netns_frags
*nf
,
375 struct inet_frags
*f
,
378 struct inet_frag_queue
*q
;
380 if (frag_mem_limit(nf
) > nf
->high_thresh
) {
381 inet_frag_schedule_worker(f
);
385 q
= kmem_cache_zalloc(f
->frags_cachep
, GFP_ATOMIC
);
390 f
->constructor(q
, arg
);
391 add_frag_mem_limit(q
, f
->qsize
);
393 setup_timer(&q
->timer
, f
->frag_expire
, (unsigned long)q
);
394 spin_lock_init(&q
->lock
);
395 atomic_set(&q
->refcnt
, 1);
400 static struct inet_frag_queue
*inet_frag_create(struct netns_frags
*nf
,
401 struct inet_frags
*f
,
404 struct inet_frag_queue
*q
;
406 q
= inet_frag_alloc(nf
, f
, arg
);
410 return inet_frag_intern(nf
, q
, f
, arg
);
413 struct inet_frag_queue
*inet_frag_find(struct netns_frags
*nf
,
414 struct inet_frags
*f
, void *key
,
417 struct inet_frag_bucket
*hb
;
418 struct inet_frag_queue
*q
;
421 if (frag_mem_limit(nf
) > nf
->low_thresh
)
422 inet_frag_schedule_worker(f
);
424 hash
&= (INETFRAGS_HASHSZ
- 1);
427 spin_lock(&hb
->chain_lock
);
428 hlist_for_each_entry(q
, &hb
->chain
, list
) {
429 if (q
->net
== nf
&& f
->match(q
, key
)) {
430 atomic_inc(&q
->refcnt
);
431 spin_unlock(&hb
->chain_lock
);
436 spin_unlock(&hb
->chain_lock
);
438 if (depth
<= INETFRAGS_MAXDEPTH
)
439 return inet_frag_create(nf
, f
, key
);
441 if (inet_frag_may_rebuild(f
)) {
444 inet_frag_schedule_worker(f
);
447 return ERR_PTR(-ENOBUFS
);
449 EXPORT_SYMBOL(inet_frag_find
);
451 void inet_frag_maybe_warn_overflow(struct inet_frag_queue
*q
,
454 static const char msg
[] = "inet_frag_find: Fragment hash bucket"
455 " list length grew over limit " __stringify(INETFRAGS_MAXDEPTH
)
456 ". Dropping fragment.\n";
458 if (PTR_ERR(q
) == -ENOBUFS
)
459 net_dbg_ratelimited("%s%s", prefix
, msg
);
461 EXPORT_SYMBOL(inet_frag_maybe_warn_overflow
);