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 WARN_ON(atomic_read(&fq
->refcnt
) != 1);
150 inet_frag_put(fq
, f
);
154 /* suppress xmit of (icmp) error packet */
155 fq
->flags
&= ~INET_FRAG_FIRST_IN
;
156 fq
->flags
|= INET_FRAG_EVICTED
;
157 hlist_del(&fq
->list
);
158 hlist_add_head(&fq
->list
, &expired
);
162 spin_unlock(&hb
->chain_lock
);
164 hlist_for_each_entry_safe(fq
, n
, &expired
, list
)
165 f
->frag_expire((unsigned long) fq
);
170 static void inet_frag_worker(struct work_struct
*work
)
172 unsigned int budget
= INETFRAGS_EVICT_BUCKETS
;
173 unsigned int i
, evicted
= 0;
174 struct inet_frags
*f
;
176 f
= container_of(work
, struct inet_frags
, frags_work
);
178 BUILD_BUG_ON(INETFRAGS_EVICT_BUCKETS
>= INETFRAGS_HASHSZ
);
182 for (i
= ACCESS_ONCE(f
->next_bucket
); budget
; --budget
) {
183 evicted
+= inet_evict_bucket(f
, &f
->hash
[i
]);
184 i
= (i
+ 1) & (INETFRAGS_HASHSZ
- 1);
185 if (evicted
> INETFRAGS_EVICT_MAX
)
193 if (f
->rebuild
&& inet_frag_may_rebuild(f
))
194 inet_frag_secret_rebuild(f
);
197 static void inet_frag_schedule_worker(struct inet_frags
*f
)
199 if (unlikely(!work_pending(&f
->frags_work
)))
200 schedule_work(&f
->frags_work
);
203 void inet_frags_init(struct inet_frags
*f
)
207 INIT_WORK(&f
->frags_work
, inet_frag_worker
);
209 for (i
= 0; i
< INETFRAGS_HASHSZ
; i
++) {
210 struct inet_frag_bucket
*hb
= &f
->hash
[i
];
212 spin_lock_init(&hb
->chain_lock
);
213 INIT_HLIST_HEAD(&hb
->chain
);
216 seqlock_init(&f
->rnd_seqlock
);
217 f
->last_rebuild_jiffies
= 0;
219 EXPORT_SYMBOL(inet_frags_init
);
221 void inet_frags_init_net(struct netns_frags
*nf
)
223 init_frag_mem_limit(nf
);
225 EXPORT_SYMBOL(inet_frags_init_net
);
227 void inet_frags_fini(struct inet_frags
*f
)
229 cancel_work_sync(&f
->frags_work
);
231 EXPORT_SYMBOL(inet_frags_fini
);
233 void inet_frags_exit_net(struct netns_frags
*nf
, struct inet_frags
*f
)
242 seq
= read_seqbegin(&f
->rnd_seqlock
);
244 for (i
= 0; i
< INETFRAGS_HASHSZ
; i
++)
245 inet_evict_bucket(f
, &f
->hash
[i
]);
247 if (read_seqretry(&f
->rnd_seqlock
, seq
))
252 percpu_counter_destroy(&nf
->mem
);
254 EXPORT_SYMBOL(inet_frags_exit_net
);
256 static struct inet_frag_bucket
*
257 get_frag_bucket_locked(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
258 __acquires(hb
->chain_lock
)
260 struct inet_frag_bucket
*hb
;
261 unsigned int seq
, hash
;
264 seq
= read_seqbegin(&f
->rnd_seqlock
);
266 hash
= inet_frag_hashfn(f
, fq
);
269 spin_lock(&hb
->chain_lock
);
270 if (read_seqretry(&f
->rnd_seqlock
, seq
)) {
271 spin_unlock(&hb
->chain_lock
);
278 static inline void fq_unlink(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
280 struct inet_frag_bucket
*hb
;
282 hb
= get_frag_bucket_locked(fq
, f
);
283 hlist_del(&fq
->list
);
284 spin_unlock(&hb
->chain_lock
);
287 void inet_frag_kill(struct inet_frag_queue
*fq
, struct inet_frags
*f
)
289 if (del_timer(&fq
->timer
))
290 atomic_dec(&fq
->refcnt
);
292 if (!(fq
->flags
& INET_FRAG_COMPLETE
)) {
294 atomic_dec(&fq
->refcnt
);
295 fq
->flags
|= INET_FRAG_COMPLETE
;
298 EXPORT_SYMBOL(inet_frag_kill
);
300 static inline void frag_kfree_skb(struct netns_frags
*nf
, struct inet_frags
*f
,
308 void inet_frag_destroy(struct inet_frag_queue
*q
, struct inet_frags
*f
)
311 struct netns_frags
*nf
;
312 unsigned int sum
, sum_truesize
= 0;
314 WARN_ON(!(q
->flags
& INET_FRAG_COMPLETE
));
315 WARN_ON(del_timer(&q
->timer
) != 0);
317 /* Release all fragment data. */
321 struct sk_buff
*xp
= fp
->next
;
323 sum_truesize
+= fp
->truesize
;
324 frag_kfree_skb(nf
, f
, fp
);
327 sum
= sum_truesize
+ f
->qsize
;
328 sub_frag_mem_limit(q
, sum
);
334 EXPORT_SYMBOL(inet_frag_destroy
);
336 static struct inet_frag_queue
*inet_frag_intern(struct netns_frags
*nf
,
337 struct inet_frag_queue
*qp_in
,
338 struct inet_frags
*f
,
341 struct inet_frag_bucket
*hb
= get_frag_bucket_locked(qp_in
, f
);
342 struct inet_frag_queue
*qp
;
345 /* With SMP race we have to recheck hash table, because
346 * such entry could have been created on other cpu before
347 * we acquired hash bucket lock.
349 hlist_for_each_entry(qp
, &hb
->chain
, list
) {
350 if (qp
->net
== nf
&& f
->match(qp
, arg
)) {
351 atomic_inc(&qp
->refcnt
);
352 spin_unlock(&hb
->chain_lock
);
353 qp_in
->flags
|= INET_FRAG_COMPLETE
;
354 inet_frag_put(qp_in
, f
);
360 if (!mod_timer(&qp
->timer
, jiffies
+ nf
->timeout
))
361 atomic_inc(&qp
->refcnt
);
363 atomic_inc(&qp
->refcnt
);
364 hlist_add_head(&qp
->list
, &hb
->chain
);
366 spin_unlock(&hb
->chain_lock
);
371 static struct inet_frag_queue
*inet_frag_alloc(struct netns_frags
*nf
,
372 struct inet_frags
*f
,
375 struct inet_frag_queue
*q
;
377 if (frag_mem_limit(nf
) > nf
->high_thresh
) {
378 inet_frag_schedule_worker(f
);
382 q
= kzalloc(f
->qsize
, GFP_ATOMIC
);
387 f
->constructor(q
, arg
);
388 add_frag_mem_limit(q
, f
->qsize
);
390 setup_timer(&q
->timer
, f
->frag_expire
, (unsigned long)q
);
391 spin_lock_init(&q
->lock
);
392 atomic_set(&q
->refcnt
, 1);
397 static struct inet_frag_queue
*inet_frag_create(struct netns_frags
*nf
,
398 struct inet_frags
*f
,
401 struct inet_frag_queue
*q
;
403 q
= inet_frag_alloc(nf
, f
, arg
);
407 return inet_frag_intern(nf
, q
, f
, arg
);
410 struct inet_frag_queue
*inet_frag_find(struct netns_frags
*nf
,
411 struct inet_frags
*f
, void *key
,
414 struct inet_frag_bucket
*hb
;
415 struct inet_frag_queue
*q
;
418 if (frag_mem_limit(nf
) > nf
->low_thresh
)
419 inet_frag_schedule_worker(f
);
421 hash
&= (INETFRAGS_HASHSZ
- 1);
424 spin_lock(&hb
->chain_lock
);
425 hlist_for_each_entry(q
, &hb
->chain
, list
) {
426 if (q
->net
== nf
&& f
->match(q
, key
)) {
427 atomic_inc(&q
->refcnt
);
428 spin_unlock(&hb
->chain_lock
);
433 spin_unlock(&hb
->chain_lock
);
435 if (depth
<= INETFRAGS_MAXDEPTH
)
436 return inet_frag_create(nf
, f
, key
);
438 if (inet_frag_may_rebuild(f
)) {
441 inet_frag_schedule_worker(f
);
444 return ERR_PTR(-ENOBUFS
);
446 EXPORT_SYMBOL(inet_frag_find
);
448 void inet_frag_maybe_warn_overflow(struct inet_frag_queue
*q
,
451 static const char msg
[] = "inet_frag_find: Fragment hash bucket"
452 " list length grew over limit " __stringify(INETFRAGS_MAXDEPTH
)
453 ". Dropping fragment.\n";
455 if (PTR_ERR(q
) == -ENOBUFS
)
456 LIMIT_NETDEBUG(KERN_WARNING
"%s%s", prefix
, msg
);
458 EXPORT_SYMBOL(inet_frag_maybe_warn_overflow
);